主成分分析 - 分散最大化による定式化 - 導出その2

分散最大化

主成分分析 - 分散最大化による定式化 - 導出その1では $M=1$ 場合を定式化した後に
一般の $M$ について帰納法を使って定式化しましたが、それとは異なる方法(分散最大化という方針は変わらない)で定式化していきます。

${\bar{\bf x}}$ をデータ集合の平均とします。

$\begin{eqnarray} {\bar{\bf x}}=\frac{1}{N}\sum_{n=1}^N{\bf x}_n\tag{1} \end{eqnarray}$

${\bf S}$ をデータ集合の共分散行列とします。

$\begin{eqnarray} {\bf S}=\frac{1}{N}\sum_{n=1}^N({\bf x}_n-{\bar{\bf x}})({\bf x}_n-{\bar{\bf x}})^\top\tag{2} \end{eqnarray}$

$M$ 次元の正規直交基底を ${\bf u}_1,\ldots,{\bf u}_M$ とします。
${\bf u}_i\in\mathbb{R}^D$ です。

ここで、 ${\bf U}=({\bf u}_1,\cdots,{\bf u}_M)$ とします。正規直交性より、次が成り立ちます。

$\begin{eqnarray} {\bf U}^\top{\bf U}={\bf I}_M\tag{3} \end{eqnarray}$

${\bf x}_n$ は ${\bf U}^\top{\bf x}_n$ に射影されます。
射影されたデータの平均は ${\bf U}^\top{\bar{\bf x}}$ です。
射影されたデータの分散は

$\begin{eqnarray} \sigma^2=\frac{1}{N}\sum_{n=1}^N({\bf U}^\top{\bf x}_n-{\bf U}^\top{\bar{\bf x}})^\top({\bf U}^\top{\bf x}_n-{\bf U}^\top{\bar{\bf x}})\tag{4} \end{eqnarray}$

です。

※共分散行列ではなく、分散です。
　本記事の後半で「共分散行列」を使って分散を最大化するというアプローチも記載しておりますので、そちらもお読みください。

$(4)$ を計算していきます。

$\begin{eqnarray} \sigma^2&=&\frac{1}{N}\sum_{n=1}^N({\bf U}^\top({\bf x}_n-{\bar{\bf x}}))^\top({\bf U}^\top({\bf x}_n-{\bar{\bf x}}))\\ &=&\frac{1}{N}\sum_{n=1}^N{\rm Tr}({\bf U}^\top({\bf x}_n-{\bar{\bf x}})({\bf U}^\top({\bf x}_n-{\bar{\bf x}}))^\top)\\ &=&\frac{1}{N}\sum_{n=1}^N{\rm Tr}({\bf U}^\top({\bf x}_n-{\bar{\bf x}})({\bf x}_n-{\bar{\bf x}})^\top{\bf U})\\ &=&{\rm Tr}\left({\bf U}^\top\frac{1}{N}\sum_{n=1}^N({\bf x}_n-{\bar{\bf x}})({\bf x}_n-{\bar{\bf x}})^\top{\bf U}\right)\\ &=&{\rm Tr}({\bf U}^\top{\bf S}{\bf U})\tag{5} \end{eqnarray}$

$(5)$ の2行目で公式 ${\rm Tr}({\bf x}{\bf y}^\top)={\bf x}^\top{\bf y}$ を、4行目でトレースの線形性を用いました。

制約条件 ${\bf U}^\top{\bf U}={\bf I}_M$ の下で、 ${\rm Tr}({\bf U}^\top{\bf S}{\bf U})$ を最大化します。
ラグランジュの未定乗数法を用いると、ラグランジュ関数は以下のようになります。

$\begin{eqnarray} L({\bf U},{\bf\Lambda})={\rm Tr}({\bf U}^\top{\bf S}{\bf U})-{\rm Tr}(({\bf U}^\top{\bf U}-{\bf I}_M){\bf\Lambda})\tag{6} \end{eqnarray}$

$(6)$ を ${\bf U}$ で微分して、 $={\bf O}$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial{\bf U}}L({\bf U},{\bf\Lambda})={\bf O}\\ &&\Leftrightarrow\frac{\partial}{\partial{\bf U}}{\rm Tr}({\bf U}^\top{\bf S}{\bf U})-\frac{\partial}{\partial{\bf U}}{\rm Tr}(({\bf U}^\top{\bf U}-{\bf I}_M){\bf\Lambda})={\bf O}\\ &&\Leftrightarrow 2{\bf S}{\bf U}-2{\bf U}{\bf\Lambda}={\bf O}\\ &&\Leftrightarrow {\bf S}{\bf U}={\bf U}{\bf\Lambda}\\ &&\Leftrightarrow {\bf U}^\top{\bf S}{\bf U}={\bf\Lambda}\tag{7} \end{eqnarray}$

$(7)$ より、 ${\bf S}$ の固有値と固有ベクトルを求めればよいことが分かります。
${\rm Tr}({\bf U}^\top{\bf S}{\bf U})$ を最大化したいので、 ${\bf S}$ の固有値の大きい方から $M$ 個選べばよいです。

共分散を使って分散最大化

上で書いた通り、今度は射影されたデータの共分散行列を用いて定式化してみます。

射影されたデータの共分散行列は

$\begin{eqnarray} \frac{1}{N}\sum_{n=1}^N({\bf U}^\top({\bf x}_n-{\bar{\bf x}}))({\bf U}^\top({\bf x}_n-{\bar{\bf x}}))^\top&=&\frac{1}{N}\sum_{n=1}^N{\bf U}^\top({\bf x}_n-{\bar{\bf x}})({\bf x}_n-{\bar{\bf x}})^\top{\bf U}\\ &=&{\bf U}^\top\frac{1}{N}\sum_{n=1}^N({\bf x}_n-{\bar{\bf x}})({\bf x}_n-{\bar{\bf x}})^\top{\bf U}\\ &=&{\bf U}^\top{\bf S}{\bf U}\tag{8} \end{eqnarray}$

です。

分散の最大化をしたいのですが、共分散行列を使って分散(散らばり)を最大化を以下のように考えてみることにします。

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

行列 ${\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{9} \end{eqnarray}$

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