フィッシャーの線形判別法

統計検定準1級の勉強のため, フィッシャーの線形判別法をまとめる.
フィッシャーの線形判別法は線形判別法(LDA)の一つで, ２クラスの線形判別法のことをいう.

アイデア

フィッシャーの線形判別法では二つのクラス(ラベル)を分ける関数を求める.
図1のようにクラス$w_1$とクラス$w_2$を分ける$g(x)$を求める.

もともと識別関数法というのは, クラスごとに識別関数を用意する.
しかし, ２クラスの場合は, それぞれのクラスに識別関数を用意する必要はない.

\begin{gather}
g(x) = g_1(x)-g_2(x)=(\boldsymbol{w_1}-\boldsymbol{w_2})^t\boldsymbol{x} = \boldsymbol{w}^t\boldsymbol{x}\\
\boldsymbol{w}\equiv \boldsymbol{w_1}-\boldsymbol{w_2}
\end{gather}

ここで, $g(x)$の正負を調べる.正であれば, $g_1(x)$が大きく, 負なら$g_2(x)$が大きいことがわかる.
入力がクラス１に属する場合, $g(x)=\boldsymbol{w^tx}>0$になるように,
クラス２に属する場合, $g(x)=\boldsymbol{w^tx}<0$になるように$\boldsymbol{w}$を求める.

数式で表現すると次のようになる.

\begin{gather}
x \in \chi_1 \to g(x)={w^tx}>0\\
x \in \chi_2 \to g(x)={w^tx}<0
\end{gather}

$g(x)$は$d$次元あるベクトルを1次元に写像する. つまり$w^tx$はスカラーになる.

ここで図2のようなデータがあったときに, どのような分け方がいいのかを考える.
分け方は無限個存在する.

例えば, 図3(a), (b)のような分け方があったときに, 図3(b)のような分け方の方が誤認識がないことがわかる.
このような分け方をどうやって数学的に定式化するのかを考える.
これは, クラス内の分散をできるだけ小さく, そして, クラス間の分散はできるだけ大きくするような分け方である.

理論

定義

２クラス($w_1$, $w_2$)の識別問題を考える.
ここで, $w_1$に属していれば正, $w_2$に属していれば負となるような識別を行う$g(x)$を求める.
定義は以下の通りである.

\begin{align}
\boldsymbol{x}&:入力データ, d次元\\
n_i&:各クラスのデータ数\\
n&:学習データの総数( n = n_1+n_2)\\
\chi_i &: クラスw_iの学習データの集合\\
\boldsymbol{m_i}&: クラスw_iのパターンの平均(i = 1,2)\\
&\boldsymbol{m_i} = \frac{1}{n_i}\sum_{\boldsymbol{x}\in \chi_1} \boldsymbol{x}\\
\boldsymbol{m}&:すべての学習データの平均\\
&\boldsymbol{m} = \frac{1}{n}\sum \boldsymbol{x}=\frac{n_1m_1+n_2m_2}{n_1+n_2}\tag{A}
\end{align}

次に変動行列(ばらつき)を定義する.
これは, クラス$w_i$の変動を表す. 平均ベクトルに対してどれだけばらついているのかを示す.
\begin{align}
S_i &=\sum_{\boldsymbol{x} \in \boldsymbol{\chi_i}}(\boldsymbol{x-m_i})(\boldsymbol{x-m_i})^T \\
\end{align}
ここで,クラス内の変動行列と, クラス間の変動行列を定義する.
\begin{align}
\boldsymbol{S_W}&:クラス内の変動行列\\
&\boldsymbol{S_W}=S_1+S_2=\sum_{i=1,2}\sum_{\boldsymbol{x} \in \boldsymbol{\chi_i}}(\boldsymbol{x-m_i})(\boldsymbol{x-m_i})^T\\
\boldsymbol{S_B}&:クラス間の変動行列\\
&\boldsymbol{S_B} = \sum_{i = 1,2}n_i(\boldsymbol{m_i-m})(\boldsymbol{m_i-m})^T
\end{align}
$\boldsymbol{S_W}$は, 各クラスにおいて, データがどれだけそのクラス平均と離れているのかを示す. つまりなるべく小さい方がまとまりがある.
一方で, $\boldsymbol{S_B}$は, 各クラスの平均ベクトルが, 全体の平均に対してどれだばらついているのかを表す.
なので, これはなるべく大きいほうが(スカラーではなく, 行列だが)判別がしやすい. クラスによってデータの偏りがありうるため, 総数$n_i$で重みづけをしている.

$\boldsymbol{S_B}$は次のように式変形できる.
\begin{gather}
\boldsymbol{S_B} =n_1(\boldsymbol{m_1}-\boldsymbol{m})(\boldsymbol{m_1}-\boldsymbol{m})^T+n_2(\boldsymbol{m_2}-\boldsymbol{m})(\boldsymbol{m_2}-\boldsymbol{m})^T\\
=n_1(\boldsymbol{m_1}-\frac{n_1\boldsymbol{m_1}+n_2\boldsymbol{m_2}}{n_1+n_2})(\boldsymbol{m_1}-\frac{n_1\boldsymbol{m_1}+n_2\boldsymbol{m_2}}{n_1+n_2})^T\\+n_2(\boldsymbol{m_2}-\frac{n_1\boldsymbol{m_1}+n_2\boldsymbol{m_2}}{n_1+n_2})(\boldsymbol{m_2}-\frac{n_1\boldsymbol{m_1}+n_2\boldsymbol{m_2}}{n_1+n_2})^T\\
\end{gather}
通分すると,
\begin{gather}
=n_1(\frac{n_1\boldsymbol{m_1}+n_2\boldsymbol{m_1}-n_1\boldsymbol{m_1}-n_2\boldsymbol{m_2}}{n_1+n_2})(\frac{n_1\boldsymbol{m_1}+n_2\boldsymbol{m_1}-n_1\boldsymbol{m_1}-n_2\boldsymbol{m_2}}{n_1+n_2})^T\\
+n_2(\frac{n_1\boldsymbol{m_2}+n_2\boldsymbol{m_2}-n_1\boldsymbol{m_1}-n_2\boldsymbol{m_2}}{n_1+n_2})(\frac{n_1\boldsymbol{m_2}+n_2\boldsymbol{m_2}-n_1\boldsymbol{m_1}-n_2\boldsymbol{m_2}}{n_1+n_2})^T
\end{gather}
また,$n=n_1+n_2$より上式を整理すると次のようになる.
\begin{gather}
\boldsymbol{S_B}=\frac{n_1n_2}{n}(\boldsymbol{m_1}-\boldsymbol{m_2})(\boldsymbol{m_1}-\boldsymbol{m_2})^T
\end{gather}

写像後の定義

ここでは, 1次元に写像した後のことを定義する.
\begin{align}
y_i&:クラスw_iに属している学習データの集合\\
\tilde{m}_i&:写像後のw_iのパターンの平均, (i = 1,2)\\
\tilde{m}&:写像後の全体の平均\\
&\tilde{m}=\frac{1}{n}\sum g(x_p)=\frac{n_1\tilde{m}_1+n_2\tilde{m}_2}{n_1+n_2}
\end{align}

ここで, 写像後の平均を写像前の文字を使って書き換えることができる.
\begin{align}
\tilde{m}_i&=\frac{1}{n_i}\sum_{g(x) \in y_i}g(x)\\
&=\frac{1}{n_i}\sum_{\boldsymbol{x} \in \chi_i}(w_0+\boldsymbol{w^tx}) \tag{1}\\
&=w_0+\boldsymbol{w^tm_i}\tag{2}\\
&=g(m_i)
\end{align}
(1)式から(2)式への変換は, $m_i = \frac{1}{n_i}\sum_{\boldsymbol{x} \in \chi_i} x_i$が成り立つためである.
そして, 写った後の全体の平均$\tilde{m}$は,

\begin{align}
\tilde{m}&=\frac{n_1{\tilde{m_1}}+n_2{\tilde{m}_2}}{n_1+n_2}\\
&=\frac{n_1(w_0+\boldsymbol{w^tm_1})+n_2(w_0+\boldsymbol{w^tm_2})}{n_1+n_2}\\
&=\frac{w_0(n_1+n_2)}{n_1+n_2}+\frac{\boldsymbol{w^t}(n_1\boldsymbol{m_1}+n_2\boldsymbol{m_2})}{n_1+n_2}
\end{align}
式(A)より,
\begin{align}
{\tilde{m}}&=w_0+\boldsymbol{w^tm}\\
&=g(\boldsymbol{m})
\end{align}

次に写像後の変動行列を定義する.
\begin{gather}
S_i=\sum_{g(x)\in y_i}(g(\boldsymbol{x})-{\tilde{m}_i})^2
\end{gather}
また, 写像後のクラス内変動行列とクラス間変動行列を写像前と同じように, ここでも定義する. なお詳細は本記事の末に示す.
\begin{align}
\boldsymbol{\tilde{S}_W}&=\boldsymbol{\tilde{S}_1+\tilde{S}_2}\\
&=\sum_{i = 1,2}\sum_{g(x) \in y_i}(g(\boldsymbol{x})-{\tilde{m}_i})^2 \tag{3}\\
&=\boldsymbol{w^tS_ww} \tag{4}
\end{align}

\begin{align}
\boldsymbol{\tilde{S}_B}&=\sum_{i = 1,2}n_i ({\tilde{m}_i}-{\tilde{m}})^2 \tag{5}\\
&=\boldsymbol{w^tS_Bw} \tag{6}
\end{align}

目的関数への定式化

前節で, 写像後のクラス内の変動行列$\boldsymbol{\tilde{S}_W}$と, 写像後のクラス間変動行列$\boldsymbol{\tilde{S}_B}$を定義した. ここで, よりよく識別を行うためには, どのような空間に写像すべきかを考えると, 写像後のクラス間はできるだけ離れていたほうがいい. また同時に, クラスはできるだけまとまっていたほうが識別は容易である. したがって, 目的関数は次のように書ける.
\begin{gather}
J(w) = \frac{\boldsymbol{\tilde{S}_B}}{\boldsymbol{\tilde{S}_W}}=\frac{\boldsymbol{w^tS_Bw}}{\boldsymbol{w^tS_Ww}} \tag{7}
\end{gather}
式(7)を最大化する.

しかし分母にも分子にも$\boldsymbol{w}$が入っており, 最適化が困難であるため,
分母を固定して, 分子を最大にする.
\begin{align}
\max \quad \boldsymbol{\tilde{S}_B=w^tS_Bw}\quad \rm{, subject}\quad \rm{to} 　\it{\boldsymbol{\tilde{S}_W}=\boldsymbol{w^t S_{W}w=I}} \tag{8}
\end{align}
ここで, $\boldsymbol{w^t S_{W}w}$は微分して0ベクトルとおくため, 定数であればなんでも問題ない.
これは, 制約条件付きの最適化問題である.
これを解くために, ラグランジュ未定乗数法を用いると次のような目的関数に書き換えられる.\begin{align}
J(w) = \boldsymbol{w^t S_B w}-\lambda(\boldsymbol{w^tS_Ww-I}) \tag{9}
\end{align}
ここで, $\frac{\partial J(w)}{\partial \boldsymbol{w}}=0$を解き, $\boldsymbol{w}$を求める
\begin{align}
\frac{\partial J(\boldsymbol{w})}{\partial \boldsymbol{w}}&=\frac{\partial}{\partial \boldsymbol{w}}(\boldsymbol{w^t S_B w}-\lambda \boldsymbol{w^tS_Ww}-\lambda \boldsymbol{I})=0 \tag{10}\\
&=(\boldsymbol{S_B+S_B^t)w}-\lambda(\boldsymbol{S_w+S_w^t)w}=0 \tag{11}\\
&=2\boldsymbol{S_Bw}-2\lambda \boldsymbol{S_Ww}=0
\end{align}
式(10)から式(11)への変形は次の公式を用いた.

式(11)を満たす$\boldsymbol{w}$が$J(\boldsymbol{w})$の極値となる.
式(11)を２で割り, 移項すると,
\begin{gather}
\boldsymbol{S_Bw}=\lambda\boldsymbol{S_Ww} \tag{12}
\end{gather}
ここで$\boldsymbol{S_W}$が逆行列をもつと仮定すると,式(12)は
\begin{gather}
\boldsymbol{S_w^{-1}S_Bw}=\lambda\boldsymbol{w} \tag{13}
\end{gather}

式(13)から, $\boldsymbol{w}$は, $\boldsymbol{S_W^{-1}S_B}$の固有ベクトル, そして$\lambda$はそれに対する固有値であることがわかる.
ここで, $\boldsymbol{w}$は0ベクトルではない.0ベクトルであれば, 同じ場所に写像されることになってしまう.

式(7)に式(12)を入れると,
\begin{gather}
J(w) = \frac{\boldsymbol{\tilde{S}_B}}{\boldsymbol{\tilde{S}_W}}=\frac{\boldsymbol{w^tS_Bw}}{\boldsymbol{w^tS_Ww}} =\frac{\boldsymbol{w^t\lambda\boldsymbol{S_Ww}}}{\boldsymbol{w^tS_Ww}}=\lambda \tag{14}
\end{gather}
これはつまり, $n\times n$の正方行列$\boldsymbol{S_W^{-1}S_B}$の, $n$個ある固有値の中で一番大きな$\lambda$を選ぶと$J(w)$を最大化できることを示す.

$\boldsymbol{w}$の求め方

式(12)より,
\begin{align}
\lambda \boldsymbol{S_Ww}=\boldsymbol{S_Bw}\\
\end{align}
$\boldsymbol{S_B}=\frac{n_1n_2}{n}(\boldsymbol{m_1}-\boldsymbol{m_2})(\boldsymbol{m_1}-\boldsymbol{m_2})^T$より,
\begin{align}
\lambda \boldsymbol{S_Ww}=\frac{n_1n_2}{n}(\boldsymbol{m_1}-\boldsymbol{m_2})(\boldsymbol{m_1}-\boldsymbol{m_2})^T\boldsymbol{w}\\
\end{align}
$\boldsymbol{(m_1-m_2)^Tw}$はスカラーになるため, スカラー部分を取り除くと,

\begin{align}
\boldsymbol{S_Ww=(m_1-m_2)}\\よって
\boldsymbol{w}\propto \boldsymbol{S_W^{-1}(m_1-m_2)}
\end{align}

これは, $\boldsymbol{Ax}=\lambda \boldsymbol{x}$において,
$\boldsymbol{A}$に対する固有ベクトルが$\boldsymbol{x}$になる.$\boldsymbol{Ax}$が$c\boldsymbol{Ax}$とスカラー倍されていても, 同様で, $\boldsymbol{x}$が固有ベクトルである.これと同じ理屈で, $\boldsymbol{w}$が何に比例しているのかがわかればいい.

$\boldsymbol{w_0}$の求め方

ここでは等分散を仮定する.
最初のアイデアの部分に戻ると,
\begin{gather}
x \in \chi_1 \to g(x)={w^tx}>0\\
x \in \chi_2 \to g(x)={w^tx}<0
\end{gather}
であった.
そのため,　写像前のクラス１とクラス２の中間を識別関数$g(x)$に通すと0になる.
したがって,
\begin{gather}
g(\frac{\boldsymbol{m_1+m_2}}{2})=0
\end{gather}
$g(\boldsymbol{x})=w_0+\boldsymbol{w^tx}$であるため,
\begin{gather}
w_0+\frac{\boldsymbol{w^tm_1+w^tm_2}}{2}=0 \tag{15}
\end{gather}
式(15)より,
\begin{gather}
w_0=-\frac{\boldsymbol{w^tm_1+w^tm_2}}{2}
\end{gather}
と求まる.

例題_統計検定準１級2021年６月問6[2]

ここで, 統計検定準１級2021年６月問6[2]を例題として解く.

フィッシャーの線形判別は, 行列の固有値・固有ベクトルを計算して与えられる.具体的には,　対応する固有ベクトルを$\boldsymbol{w}$, 新しいデータを$\boldsymbol{z_0}$とおくとき, $\boldsymbol{v^Tz_0}$により, 線形判別が行われる. $\boldsymbol{S_W,S_B}$が

\begin{gather}
\boldsymbol{S_W}=\begin{pmatrix}
4&2\\
2&3
\end{pmatrix},\quad
\boldsymbol{S_B}=\begin{pmatrix}
4&2\\
2&1
\end{pmatrix}
\end{gather}と与えられたとき, 固有値を計算する行列と, 線形判別に用いる固有ベクトル$\boldsymbol{v}$の組み合わせとして, 次の１～４うちから最も適切なものを一つ選べ.

1.行列$\begin{pmatrix}1&\frac{1}{2}\\0&0\end{pmatrix}$,固有ベクトル：$\begin{pmatrix}-1\\2\end{pmatrix}$
2.行列$\begin{pmatrix}1&\frac{1}{2}\\0&0\end{pmatrix}$,固有ベクトル：$\begin{pmatrix}1\\0\end{pmatrix}$
3.行列$\begin{pmatrix}0&0\\0&-2\end{pmatrix}$,固有ベクトル：$\begin{pmatrix}-1\\0\end{pmatrix}$
4.行列$\begin{pmatrix}0&0\\0&-2\end{pmatrix}$,固有ベクトル：$\begin{pmatrix}0\\1\end{pmatrix}$

回答

式(13)より, $\boldsymbol{w}$は, $\boldsymbol{S_W^{-1}S_B}$の固有ベクトル, そして$\lambda$はそれに対する固有値でした.
したがって, 固有値を計算するための行列は,$\boldsymbol{S_W}^{-1}\boldsymbol{S_B}=\begin{pmatrix}1&\frac{1}{2}\\0&0\end{pmatrix}$と求まる.

ここから固有ベクトルを求めるために, まず固有値を求める.
\begin{gather}
\det \begin{pmatrix}
\lambda-1&\frac{1}{2}\\
0&\lambda-0
\end{pmatrix}=0\\
\lambda(\lambda-1)=0\\
\lambda=0,1
\end{gather}
一番大きな固有値を選ぶことで式(14)を最大化できる. そのため, ここでは1を選ぶ. 固有ベクトルは,
\begin{gather}
\begin{pmatrix}
1-1&\frac{1}{2}\\
0&1-0
\end{pmatrix}
\begin{pmatrix}
x_1\\x_2
\end{pmatrix}=0
\end{gather}
この等式を満たすのは選択肢の２のみである.

補足１：写像後の変動行列 式(3)から式(4)の変形

\begin{align}
\boldsymbol{\tilde{S}_W}&=\boldsymbol{\tilde{S}_1+\tilde{S}_2}\\
&=\sum_{i = 1,2}\sum_{g(x) \in y_i}(g(\boldsymbol{x})-{\tilde{m}_i})^2 \tag{A1}\\
\end{align}
式（3）において, スカラーは2乗と転置が等価であるため,
\begin{align}
\sum_{i = 1,2}\sum_{g(x) \in y_i}(g(\boldsymbol{x})-{\tilde{m}_i})(g(\boldsymbol{x})-{\tilde{m}_i})^t \tag{A2}
\end{align}
ここから写像する前に戻す.
\begin{align}
\sum_{i = 1,2}\sum_{\boldsymbol{x} \in \chi_i}(w_0+\boldsymbol{w^tx}-w_0-\boldsymbol{w^tm_i})(w_0+\boldsymbol{w^tx}-w_0-\boldsymbol{w^tm_i})^t\tag{A3}
\end{align}
式A(3)において, 式(2)より, $\tilde{m}_i=w_0+\boldsymbol{w^tm_i}$を用いた.
整理すると,
\begin{align}
\sum_{i = 1,2}\sum_{\boldsymbol{x} \in \chi_i}\boldsymbol{w^t(x-m_i)(w^t(x-m_i))^t}\tag{A4}
\end{align}
式(A4)の後半の$\boldsymbol{w^t}$はまた転置されるため,
\begin{gather}
\boldsymbol{w^t}\sum_{i = 1,2}\sum_{\boldsymbol{x} \in \chi_i}(\boldsymbol{x-m_i})(\boldsymbol{x-m_i})^t\boldsymbol{w} \tag{A5}
\end{gather}
$\sum_{i = 1,2}\sum_{\boldsymbol{x} \in \chi_i}(\boldsymbol{x-m_i})(\boldsymbol{x-m_i})^t=\boldsymbol{S_W}$より,
\begin{align}
\boldsymbol{\tilde{S}_W}=\boldsymbol{w^tS_ww}
\end{align}

補足２：写像後の変動行列 式(5)から式(6)の変形

\begin{align}
\boldsymbol{\tilde{S}_B}&=\sum_{i = 1,2}n_i ({\tilde{m}_i}-{\tilde{m}})^2 \tag{B1}\\
&=\sum_{i = 1,2}n_i(\tilde{m}_i-\tilde{m})(\tilde{m}_i-\tilde{m})^t\\
\end{align}
こちらも補足１と同様に, 写像前の文字で表現していく. $\tilde{m}_i=w_0+\boldsymbol{w^tm_i}$であるため,

\begin{align}
\boldsymbol{\tilde{S}_B}&=\sum_{i = 1,2}n_i(w_0+\boldsymbol{w^tm_i}-w_0-\boldsymbol{w^tm})(w_0+\boldsymbol{w^tm_i}-w_0-\boldsymbol{w^tm})^t\\
&=\sum_{i = 1,2}n_i(\boldsymbol{w^tm_i-w^tm})(\boldsymbol{w^tm_i-w^tm})^t\\
&=\boldsymbol{w^t}\sum_{i = 1,2}n_i(\boldsymbol{m_i-m})(\boldsymbol{m_i-m})^t\boldsymbol{w}\\
&=\boldsymbol{w^tS_Bw}
\end{align}

参考文献

[1]Bishop-Pattern-Recognition-and-Machine-Learning-2006.pdf