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

要件

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

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

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

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

※本記事では $D'$ 次元へ削減することを考えるので、求めるべきは行列 $\bf W$ です。

クラス内共分散行列とクラス間共分散行列

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

$\begin{eqnarray} &&{\bf S}_W=\sum_{k=1}^K\sum_{n\in C_k}({\bf x}_n-{\bf m}_k)({\bf x}_n-{\bf m}_k)^\top\tag{1}\\ &&{\bf S}_B=\sum_{k=1}^KN_k({\bf m}_k-{\bf m})({\bf m}_k-{\bf m})^\top\tag{2} \end{eqnarray}$

ここで、

$\begin{eqnarray} &&{\bf m}_k=\frac{1}{N_k}\sum_{n\in C_k}{\bf x}_n\tag{3}\\ &&{\bf m}=\frac{1}{N}\sum_{n=1}^N{\bf x}_n=\frac{1}{N}\sum_{k=1}^KN_k{\bf m}_k\tag{4} \end{eqnarray}$

とし、 $N_k$ はクラス $C_k$ のデータの個数とします。

$(3)$ より、 ${\bf m}_k$ はクラス $C_k$ のデータの平均を
$(4)$ より、 ${\bf m}$ は全データの平均を表しています。

$(1),(2)$ の意味を考えてみます。
${\bf S}_W$ は各クラスの共分散行列を足しわせたものになっています。
${\bf S}_B$ は各クラスの平均の共分散行列をクラスのデータの個数で重みづけしたものの和になっています。

変換後の空間でのクラス内共分散行列とクラス間共分散行列

$D$ 次元から $D'$ 次元への変換を行列 $\bf W$ で表すと、

$\begin{eqnarray} {\bf y}={\bf W}^\top{\bf x}\tag{5} \end{eqnarray}$

と書けます。
$(5)$ で、 ${\bf W}=({\bf w}_1,\cdots,{\bf w}_{D'})$ とします。

変換後の空間でのクラス内共分散行列 $\tilde{\bf S}_W$ とクラス間共分散行列 $\tilde{\bf S}_B$ を求めます。

$\begin{eqnarray} \tilde{\bf S}_W&=&\sum_{k=1}^K\sum_{n\in C_k}({\bf y}_n-{\boldsymbol\mu}_k)({\bf y}_n-{\boldsymbol\mu}_k)^\top\\ &=&\sum_{k=1}^K\sum_{n\in C_k}({\bf W}^\top{\bf x}_n-{\bf W}^\top{\bf m}_k)({\bf W}^\top{\bf x}_n-{\bf W}^\top{\bf m}_k)^\top\\ &=&\sum_{k=1}^K\sum_{n\in C_k}{\bf W}^\top({\bf x}_n-{\bf m}_k)({\bf W}^\top({\bf x}_n-{\bf m}_k))^\top\\ &=&\sum_{k=1}^K\sum_{n\in C_k}{\bf W}^\top({\bf x}_n-{\bf m}_k)({\bf x}_n-{\bf m}_k)^\top{\bf W}\\ &=&{\bf W}^\top\left(\sum_{k=1}^K\sum_{n\in C_k}({\bf x}_n-{\bf m}_k)({\bf x}_n-{\bf m}_k)^\top\right){\bf W}\\ &=&{\bf W}^\top{\bf S}_W{\bf W}\tag{6} \end{eqnarray}$

$\begin{eqnarray} \tilde{\bf S}_B&=&\sum_{k=1}^KN_k({\boldsymbol\mu}_k-{\boldsymbol\mu})({\boldsymbol\mu}_k-{\boldsymbol\mu})^\top\\ &=&\sum_{k=1}^KN_k({\bf W}^\top{\bf m}_k-{\bf W}^\top{\bf m})({\bf W}^\top{\bf m}_k-{\bf W}^\top{\bf m})^\top\\ &=&\sum_{k=1}^KN_k{\bf W}^\top({\bf m}_k-{\bf m})({\bf W}^\top({\bf m}_k-{\bf m}))^\top\\ &=&\sum_{k=1}^KN_k{\bf W}^\top({\bf m}_k-{\bf m})({\bf m}_k-{\bf m})^\top{\bf W}\\ &=&{\bf W}^\top\left(\sum_{k=1}^KN_k({\bf m}_k-{\bf m})({\bf m}_k-{\bf m})^\top\right){\bf W}\\ &=&{\bf W}^\top{\bf S}_B{\bf W}\tag{7} \end{eqnarray}$

ここで、

$\begin{eqnarray} &&{\boldsymbol\mu}_k=\frac{1}{N_k}\sum_{n\in C_k}{\bf y}_n\tag{8}\\ &&{\boldsymbol\mu}=\frac{1}{N}\sum_{n=1}^N{\bf y}_n=\frac{1}{N_k}\sum_{k=1}^KN_k{\boldsymbol\mu}_k\tag{9} \end{eqnarray}$

とします。

$\bf W$ の最適化 - その1

${\bf S}_W$ を ${\bf W}_1$ で正規化し、 ${\bf W}_1^\top{\bf S}_B{\bf W}_1$ に対するKL展開を行うことにより ${\bf W}$ を最適化します。

まず、 ${\bf S}_W$ を ${\bf W}_1$ で正規化します。
対象行列 ${\bf S}_W$ は、直交行列 $\bf U$ によって対角化できます。

$\begin{eqnarray} {\bf U}^\top{\bf S}_W{\bf U}={\bf \Lambda}_1\tag{10} \end{eqnarray}$

$(10)$ で ${\bf \Lambda}_1$ は ${\bf S}_W$ の固有値を対角成分に並べた対角行列です。

ここで、 ${\bf\Lambda}_1^{-\frac{1}{2}}$ は、 ${\bf \Lambda}_1$ の成分を $-\frac{1}{2}$ 乗したものとします。
$(10)$ の左辺に左から $({\bf\Lambda}_1^{-\frac{1}{2}})^\top$ を、右から ${\bf\Lambda}_1^{-\frac{1}{2}}$ 掛けます。

$\begin{eqnarray} ({\bf\Lambda}_1^{-\frac{1}{2}})^\top{\bf U}^\top{\bf S}_W{\bf U}{\bf\Lambda}_1^{-\frac{1}{2}}&=&({\bf\Lambda}_1^{-\frac{1}{2}})^\top{\bf \Lambda}_1{\bf\Lambda}_1^{-\frac{1}{2}}\\ &=&{\bf I}_{D'}\tag{11} \end{eqnarray}$

$(11)$ より、 ${\bf W}_1={\bf U}{\bf\Lambda}_1^{-\frac{1}{2}}$ で ${\bf S}_W$ が正規化できることとが分かります。

$\begin{eqnarray} {\bf W}_1^\top{\bf S}_W{\bf W}_1={\bf I}_{D'}\tag{12} \end{eqnarray}$

次に、 ${\bf W}_1^\top{\bf S}_B{\bf W}_1$ に対するKL展開を行います。
${\bf W}_1{\bf S}_B{\bf W}_1$ は半正定値行列です。
${\bf W}_1{\bf S}_B{\bf W}_1$ に対応する固有値を成分とする行列を ${\bf\Lambda}$ とすると、

$\begin{eqnarray} \left\{ \begin{array}{l} {\bf W}_1^\top{\bf S}_B{\bf W}_1{\bf W}_2={\bf W}_2{\bf\Lambda}\\ {\bf W}_2^\top{\bf W}_2={\bf I}_{D'} \end{array}\tag{13} \right. \end{eqnarray}$

が成り立ちます。

ここで、 ${\bf W}\equiv{\bf W}_1{\bf W}_2$ と定義します。

このとき、

$\begin{eqnarray} {\bf W}^\top{\bf S}_W{\bf W}&=&({\bf W}_1{\bf W}_2)^\top{\bf S}_W({\bf W}_1{\bf W}_2)\\ &=&{\bf W}_2^\top{\bf W}_1^\top{\bf S}_W{\bf W}_1{\bf W}_2\\ &=&{\bf W}_2^\top{\bf W}_2\\ &=&{\bf I}_{D'}\tag{14} \end{eqnarray}$

となり、また $(13)$ の第1式より

$\begin{eqnarray} &&{\bf W}_1^\top{\bf S}_B{\bf W}_1{\bf W}_2={\bf W}_2{\bf\Lambda}\\ &&\Leftrightarrow({\bf W}_1^\top)^{-1}{\bf W}_1^\top{\bf S}_B{\bf W}={\bf S}_W{\bf W}_1{\bf W}_2{\bf\Lambda}\\ &&\Leftrightarrow{\bf S}_B{\bf W}={\bf S}_W{\bf W}{\bf\Lambda}\\ &&\Leftrightarrow{\bf S}_W^{-1}{\bf S}_B{\bf W}={\bf W}{\bf\Lambda}\tag{15} \end{eqnarray}$

となります。

$(15)$ より、 ${\bf S}_W^{-1}{\bf S}_B$ の固有値に対応する固有ベクトル見つければよいことになります。
KL展開同様、 ${\bf S}_W^{-1}{\bf S}_B$ の固有値の大きい方から $D'$ 個選べばよいです。

${\bf W}$ の最適化 - その2

${\bf W}^\top{\bf S}_W{\bf W}={\bf I}_{D'}$ の条件の下で、 ${\bf W}^\top{\bf S}_B{\bf W}$ を散らばりを最大することにより ${\bf W}$ を最適化します。

まず、一般論として、射影後の散らばりについて考えます。

行列 ${\bf A}\in{\mathbb R}^{n\times n}$ は固有値 $\lambda_1,\ldots\lambda_n$ と固有ベクトル ${\bf u}_1,\ldots,{\bf u}_n$ を用いて次のように表せます。

$\begin{eqnarray} {\bf A}=\lambda_1{\bf u}_1{\bf u}_1^\top+\cdots+\lambda_n{\bf u}_n{\bf u}_n^\top\tag{16} \end{eqnarray}$

$\bf A$ は各点を各主軸方向に射影して、固有値倍して、すべて足しわせたものと解釈できます。
よって、 $\sum_{i=1}^n\lambda_i$ や $\prod_{i=1}^n\lambda_i$ が ${\bf A}$ の射影後の散らばりを表すと考えることができます。
本記事では、PRMLにならって射影後の散らばりは ${\rm Tr}{\bf A}=\sum_{i=1}^n\lambda_i$ と固有値の和で考えることにします。

ですので、 ${\bf W}^\top{\bf S}_W{\bf W}={\bf I}_{D'}$ の条件の下で、 ${\rm Tr}({\bf W}^\top{\bf S}_B{\bf W})$ を最大することにより ${\bf W}$ を最適化することにします。

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

$\begin{eqnarray} L({\bf W},{\bf\Lambda})={\rm Tr}({\bf W}^\top{\bf S}_B{\bf W})-{\rm Tr}(({\bf W}^\top{\bf S}_W{\bf W}-{\bf I}_{D'}){\bf\Lambda})\tag{17} \end{eqnarray}$

$(17)$ で対角行列を ${\bf\Lambda}$ としました。
$(17)$ の右辺の第二項ですが、ラグランジュ乗数は対角成分のみを考えればよいので、 ${\rm Tr}$ (トレース)を使って書いています。

$(17)$ を行列 $\bf W$ で微分して、 $\bf O$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial{\bf W}}L({\bf W},{\bf\Lambda})={\bf O}\\ &&\Leftrightarrow\frac{\partial}{\partial{\bf W}}{\rm Tr}({\bf W}^\top{\bf S}_B{\bf W})-\frac{\partial}{\partial{\bf W}}{\rm Tr}({\bf W}^\top{\bf S}_W{\bf W}{\bf\Lambda})={\bf O}\\ &&\Leftrightarrow({\bf S}_B^\top+{\bf S}_B){\bf W}-({\bf S}_W{\bf W}{\bf\Lambda}+{\bf S}_W^\top{\bf W}{\bf\Lambda}^\top)={\bf O}\\ &&\Leftrightarrow 2{\bf S}_B{\bf W}-2{\bf S}_W{\bf W}{\bf\Lambda}={\bf O}\\ &&\Leftrightarrow {\bf S}_B{\bf W}={\bf S}_W{\bf W}{\bf\Lambda}\\ &&\Leftrightarrow {\bf S}_W^{-1}{\bf S}_B{\bf W}={\bf W}{\bf\Lambda}\tag{18} \end{eqnarray}$

$(18)$ で、以下の公式を使用しました。

$\begin{eqnarray} &&\frac{\partial}{\partial\bf A}{\bf A}^\top{\bf B}{\bf A}=({\bf B}^\top+{\bf B}){\bf A}\tag{19}\\ &&\frac{\partial}{\partial{\bf X}}{\rm Tr}({\bf X}^\top{\bf A}{\bf X}{\bf B})={\bf A}{\bf X}{\bf B}+{\bf A}^\top{\bf X}{\bf B}^\top\tag{20} \end{eqnarray}$