フィッシャーの線形判別 - 2クラス - 機械学習基礎理論独習

要件

2個のクラス $C_1,C_2$ に割り振られた $N$ 個の $D$ 次元のデータ ${\bf x}_1,\dots,{\bf x}_N$ があります。
各クラスのデータの分離を保ちつつ、1次元へ削減することを考えます。

2次元の2クラスのデータを1次元に次元削減する例を下図で示しました。

f:id:olj611:20210430230447p:plain:w400

${\bf w}_2$ のようなクラス内分散が小さく、クラス間分散を大きくする $\bf w$ を求めればよいことになります。

フィッシャーの判別基準

以下の式で1次元に射影するとします。

$\begin{eqnarray} y={\bf w}^\top{\bf x}\tag{1} \end{eqnarray}$

クラス $C_k$ のデータの平均 ${\bf m}_k$ 、射影後のクラス $C_k$ のデータの平均 $m_k$ は

$\begin{eqnarray} &&{\bf m}_k=\frac{1}{N_k}\sum_{n\in \mathcal{C}_k}{\bf x}_n\tag{2}\\ &&m_k={\bf w}^\top{\bf m}_k\tag{3} \end{eqnarray}$

で与えられます。

射影されたクラス $C_k$ の分散 $s_k^2$ は

$\begin{eqnarray} s_k^2=\sum_{n\in\mathcal{C}_k}(y_n-m_k)^2\tag{4} \end{eqnarray}$

で与えられます。
ここで、 $y_n={\bf w}^\top{\bf x}_n$ です。

フィッシャーの判別基準 $J({\bf w})$ はクラス内分散とクラス間分散の比で定義されます。

$\begin{eqnarray} J({\bf w})=\frac{(m_2-m_1)^2}{s_1^2+s_2^2}\tag{5} \end{eqnarray}$

$(5)$ の右辺の分子を式変形します。

$\begin{eqnarray} (m_2-m_1)^2&=&({\bf w}^\top{\bf m}_2-{\bf w}^\top{\bf m}_1)^2\\ &=&({\bf w}^\top{\bf m}_2-{\bf w}^\top{\bf m}_1)({\bf w}^\top{\bf m}_2-{\bf w}^\top{\bf m}_1)\\ &=&({\bf w}^\top{\bf m}_2-{\bf w}^\top{\bf m}_1)({\bf m}_2^\top{\bf w}-{\bf m}_1^\top{\bf w})\\ &=&{\bf w}^\top({\bf m}_2-{\bf m}_1)({\bf m}_2^\top-{\bf m}_1^\top){\bf w}\\ &=&{\bf w}^\top({\bf m}_2-{\bf m}_1)({\bf m}_2-{\bf m}_1)^\top{\bf w}\tag{6} \end{eqnarray}$

$(5)$ の右辺の分母を式変形します。

$\begin{eqnarray} s_1^2+s_2^2&=&\sum_{n\in\mathcal{C}_1}(y_n-m_1)^2+\sum_{n\in\mathcal{C}_2}(y_n-m_2)^2\\ &=&\sum_{n\in\mathcal{C}_1}({\bf w}^\top{\bf x}_n-{\bf w}^\top{\bf m}_1)^2+\sum_{n\in\mathcal{C}_2}({\bf w}^\top{\bf x}_n-{\bf w}^\top{\bf m}_2)^2\\ &=&\sum_{n\in\mathcal{C}_1}{\bf w}^\top({\bf x}_n-{\bf m}_1)({\bf x}_n-{\bf m}_1)^\top{\bf w}+\sum_{n\in\mathcal{C}_2}{\bf w}^\top({\bf x}_n-{\bf m}_2)({\bf x}_n-{\bf m}_2)^\top{\bf w}\\ &=&{\bf w}^\top\left(\sum_{n\in\mathcal{C}_1}({\bf x}_n-{\bf m}_1)({\bf x}_n-{\bf m}_1)^\top+\sum_{n\in\mathcal{C}_2}({\bf x}_n-{\bf m}_2)({\bf x}_n-{\bf m}_2)^\top\right){\bf w}\tag{7} \end{eqnarray}$

ここで、クラス内共分散行列 ${\bf S}_W$ とクラス間共分散行列 ${\bf S}_B$ を以下のように定義します。

$\begin{eqnarray} &&{\bf S}_W=\sum_{n\in\mathcal{C}_1}({\bf x}_n-{\bf m}_1)({\bf x}_n-{\bf m}_1)^\top+\sum_{n\in\mathcal{C}_2}({\bf x}_n-{\bf m}_2)({\bf x}_n-{\bf m}_2)^\top\tag{8}\\ &&{\bf S}_B=({\bf m}_2-{\bf m}_1)({\bf m}_2-{\bf m}_1)^\top\tag{9} \end{eqnarray}$

以上より、 $J({\bf w})$ は以下のように表せます。

$\begin{eqnarray} J({\bf w})=\frac{{\bf w}^\top{\bf S}_B{\bf w}}{{\bf w}^\top{\bf S}_W{\bf w}}\tag{10} \end{eqnarray}$

最適化 - その1

$J({\bf w})$ を最大化することにより、クラス内分散が小さく、クラス間分散を大きくするような $\bf w$ を求めることができます。

${\bf w}^\top{\bf S}_W{\bf w}=1$ の制約の下で、 $J({\bf w})$ を最大化します。

${\bf w}^\top{\bf S}_W{\bf w}=1$ とする理由ですが、
例えば、 ${\bf w}$ の値が ${\bf w}=a\hat{\bf w}$ と求まったとします。
この時、 $J({\bf w})$ の分母と分子で $a$ は打ち消しあいます。これは、 ${\bf w}$ を定数倍しても一般性を失わないことを意味しています。
ですので、 ${\bf w}^\top{\bf S}_W{\bf w}=1$ と仮定しても問題ないわけです。

ラグランジュの未定乗数法により、ラグランジュ関数は以下のようになります。

$\begin{eqnarray} L({\bf w},\lambda)={\bf w}^\top{\bf S}_B{\bf w}-\lambda({\bf w}^\top{\bf S}_W{\bf w}-1)\tag{11} \end{eqnarray}$

$(11)$ を ${\bf w}$ で微分して、 $={\bf 0}$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial{\bf w}}L({\bf w},\lambda)={\bf 0}\\ &&\Leftrightarrow\frac{\partial}{\partial{\bf w}}({\bf w}^\top{\bf S}_B{\bf w}-\lambda({\bf w}^\top{\bf S}_W{\bf w}-1))={\bf 0}\\ &&\Leftrightarrow 2{\bf S}_B{\bf w}-2\lambda{\bf S}_W{\bf w}={\bf 0}\\ &&\Leftrightarrow {\bf S}_B{\bf w}=\lambda{\bf S}_W{\bf w}\\ &&\Leftrightarrow {\bf S}_W^{-1}{\bf S}_B{\bf w}=\lambda{\bf w}\tag{12} \end{eqnarray}$

$(12)$ は ${\bf S}_W^{-1}{\bf S}_B$ の固有ベクトルが $\bf w$ 、固有値が $\lambda$ であることを示しています。

最適化 - その2

上記では、 ${\bf w}^\top{\bf S}_W{\bf w}=1$ の制約の下で $J({\bf w})$ を最大化しましたが、
今度は、制約なしでやってみます。

$J({\bf w})$ を ${\bf w}$ で微分して、 $={\bf 0}$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial{\bf w}}J({\bf w})={\bf 0}\\ &&\Leftrightarrow\frac{\frac{\partial}{\partial{\bf w}}({\bf w}^\top{\bf S}_B{\bf w}){\bf w}^\top{\bf S}_W{\bf w}-{\bf w}^\top{\bf S}_B{\bf w}\frac{\partial}{\partial{\bf w}}({\bf w}^\top{\bf S}_W{\bf w})}{({\bf w}^\top{\bf S}_W{\bf w})^2}={\bf 0}\\ &&\Leftrightarrow 2{\bf S}_B{\bf w}{\bf w}^\top{\bf S}_W{\bf w}-2{\bf w}^\top{\bf S}_B{\bf w}{\bf S}_W{\bf w}={\bf 0}\\ &&\Leftrightarrow ({\bf w}^\top{\bf S}_B{\bf w}){\bf S}_W{\bf w}=({\bf w}^\top{\bf S}_W{\bf w}){\bf S}_B{\bf w}\\ &&\Leftrightarrow {\bf S}_W{\bf w}\propto{\bf S}_B{\bf w}\\ &&\Leftrightarrow {\bf S}_W{\bf w}\propto({\bf m}_2-{\bf m}_1)({\bf m}_2-{\bf m}_1)^\top{\bf w}\\ &&\Leftrightarrow {\bf S}_W{\bf w}\propto{\bf m}_2-{\bf m}_1\\ &&\Leftrightarrow {\bf w}\propto{\bf S}_W^{-1}({\bf m}_2-{\bf m}_1)\tag{13} \end{eqnarray}$