機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

勉強ログです。リンクフリーです
目次へ戻る

主成分分析 - 誤差最小化による定式化

主成分分析

{\bf x}_nの別の表現

D 次元の正規直交基底 \{{\bf u}_i\} を導入します。

各データ点 {\bf x}_n は次のように書けます。

\begin{eqnarray} {\bf x}_n=\sum_{i=1}^D\alpha_{ni}{\bf u}_i\tag{1} \end{eqnarray}

(1) の左から {\bf u}_i^\top をかけます。

\begin{eqnarray} &&{\bf u}_i^\top{\bf x}_n=\sum_{i=1}^D\alpha_{ni}{\bf u}_i^\top{\bf u}_i\\ &&\Leftrightarrow \alpha_{ni}={\bf x}_n^\top{\bf u}_i\tag{2} \end{eqnarray}

(2) を (1) に代入します。

\begin{eqnarray} {\bf x}_n=\sum_{i=1}^D({\bf x}_n^\top{\bf u}_i){\bf u}_i\tag{3} \end{eqnarray}

線形代数が得意な人は (3) が自然に見える(導くまでもない)と思います。

目的関数の定義

M 次元の線形部分空間は、最初の M 個の基底ベクトルを使って表現できるので、
各データ点 {\bf x}_n を近似します。
{\bf x}_n を近似した点を \tilde{\bf x}_n とすると、以下のようになります。

\begin{eqnarray} \tilde{\bf x}_n=\sum_{i=1}^Mz_{ni}{\bf u}_i+\sum_{i=M+1}^Db_i{\bf u}_i\tag{4} \end{eqnarray}

ここで、\{z_{ni}\} は特定のデータ点に依存しているが、
\{b_i\} はすべてのデータ点に共通な定数と考えることができます。

\{z_{ni}\} (1\leq i \leq M) だけデータ点に依存している理由ですが、
いま考えているのはデータの M 次元から D 次元への次元削減であり、
\{z_{ni}\} (1\leq i \leq D) としてしまうと、\hat{\bf x}_n={\bf x}_n となってしまうからです。

\{{\bf u}_i\},\{z_{ni}\},\{b_i\} を色々調整して、次元が減ることによる歪みを最小化したいわけです。
近似による歪みを以下で定義し、これを最小化することが目的となります。

\begin{eqnarray} J=\frac{1}{N}\sum_{n=1}^N||{\bf x}_n-\tilde{\bf x}_n||^2\tag{5} \end{eqnarray}

以下の式変形で正規直交性 {\bf u}_i^\top{\bf u}_j=\delta_{ij} を多用します。

J を z_{nj} で微分して、=0 とします。

\begin{eqnarray} &&\frac{\partial}{\partial z_{nj}}J = 0\\ &&\Leftrightarrow\frac{\partial}{\partial z_{nj}}\left(\frac{1}{N}\sum_{m=1}^N||{\bf x}_m-\tilde{\bf x}_m||^2\right)=0\\ &&\Leftrightarrow\frac{\partial}{\partial z_{nj}}||{\bf x}_n-\tilde{\bf x}_n||^2=0\\ &&\Leftrightarrow\frac{\partial}{\partial z_{nj}}\left({\bf x}_n-\sum_{i=1}^Mz_{ni}{\bf u}_i-\sum_{i=M+1}^Db_j{\bf u}_i\right)^\top\left({\bf x}_n-\sum_{i=1}^Mz_{ni}{\bf u}_i-\sum_{i=M+1}^Db_j{\bf u}_i\right)=0\\ &&\Leftrightarrow\left({\bf x}_n-\sum_{i=1}^Mz_{ni}{\bf u}_i\right)^\top{\bf u}_j=0\\ &&\Leftrightarrow{\bf x}_n^\top{\bf u}_j-z_{nj}=0\\ &&\Leftrightarrow z_{nj}={\bf x}_n^\top{\bf u}_j\tag{6} \end{eqnarray}

(6) の j は j=1,\ldots,M です。
(6) の 4 行目で \frac{\partial}{\partial z}({\bf x}+z{\bf u})^\top({\bf x}+z{\bf u})=2({\bf x}+z{\bf u})^\top{\bf u} を用いました。

J を b_j で微分して、=0 とします。

\begin{eqnarray} &&\frac{\partial}{\partial b_j}J = 0\\ &&\Leftrightarrow\sum_{n=1}^N\frac{\partial}{\partial b_j}\left({\bf x}_n-\sum_{i=1}^Mz_{ni}{\bf u}_i-\sum_{i=M+1}^Db_i{\bf u}_i\right)^\top\left({\bf x}_n-\sum_{i=1}^Mz_{ni}{\bf u}_i-\sum_{i=M+1}^Db_i{\bf u}_i\right)=0\\ &&\Leftrightarrow\sum_{n=1}^N\left({\bf x}_n-\sum_{i=M+1}^Db_i{\bf u}_i\right)^\top{\bf u}_j=0\\ &&\Leftrightarrow\sum_{n=1}^N\left({\bf x}_n^\top{\bf u}_j-b_j\right)=0\\ &&\Leftrightarrow\sum_{n=1}^N{\bf x}_n^\top{\bf u}_j-Nb_j=0\\ &&\Leftrightarrow b_j=\frac{1}{N}\sum_{n=1}^N{\bf x}_n^\top{\bf u}_j\\ &&\Leftrightarrow b_j=\bar{\bf x}^\top{\bf u}_j\tag{7} \end{eqnarray}

(7) の j は j=M+1,\ldots,D です。

(6),(7) を (4) に代入します。

\begin{eqnarray} \tilde{\bf x}_n=\sum_{i=1}^M({\bf x}_n^\top{\bf u}_i){\bf u}_i+\sum_{i=M+1}^D(\bar{\bf x}^\top{\bf u}_i){\bf u}_i\tag{8} \end{eqnarray}

(3),(8) より、

\begin{eqnarray} {\bf x}_n-\tilde{\bf x}_n=\sum_{i=M+1}^D(({\bf x}_n-\bar{\bf x})^\top{\bf u}_i){\bf u}_i\tag{9} \end{eqnarray}

となります。

J を変形するため、||{\bf x}_n-\tilde{\bf x}_n||^2 を計算します。

\begin{eqnarray} ||{\bf x}_n-\tilde{\bf x}_n||^2&=&({\bf x}_n-\tilde{\bf x}_n)^\top({\bf x}_n-\tilde{\bf x}_n)\\ &=&\sum_{i=M+1}^D\sum_{j=M+1}^D((({\bf x}_n-\bar{\bf x})^\top{\bf u}_i){\bf u}_i)^\top((({\bf x}_n-\bar{\bf x})^\top{\bf u}_j){\bf u}_j)\\ &=&\sum_{i=M+1}^D\sum_{j=M+1}^D(({\bf x}_n^\top {\bf u}_i - \bar{\bf x}^\top {\bf u}_i ){\bf u}_i)^\top({\bf x}_n^\top {\bf u}_j - \bar{\bf x}^\top{\bf u}_j){\bf u}_j\\ &=&\sum_{i=M+1}^D\sum_{j=M+1}^D{\bf u}_i^\top ({\bf x}_n^\top {\bf u}_i - \bar{\bf x}^\top {\bf u}_i )^\top({\bf x}_n^\top {\bf u}_j -\bar{\bf x}^\top {\bf u}_j ) {\bf u}_j\\ &=&\sum_{i=M+1}^D{\bf u}_i^\top ({\bf x}_n^\top {\bf u}_i - \bar{\bf x}^\top {\bf u}_i )^\top({\bf x}_n^\top {\bf u}_i -\bar{\bf x}^\top {\bf u}_i ) {\bf u}_i\\ &=&\sum_{i=M+1}^D ({\bf x}_n^\top {\bf u}_i - \bar{\bf x}^\top {\bf u}_i )^\top({\bf x}_n^\top {\bf u}_i -\bar{\bf x}^\top {\bf u}_i ) \\ &=&\sum_{i=M+1}^D || {\bf x}_n^\top {\bf u}_i - \bar{\bf x}^\top {\bf u}_i ||^2 \tag{10} \end{eqnarray}

(10) を (5) に代入します。

\begin{eqnarray} J&=&\frac{1}{N}\sum_{n=1}^N\sum_{i=M+1}^D || {\bf x}_n^\top {\bf u}_i - \bar{\bf x}^\top {\bf u}_i ||^2\\ &=&\sum_{i=M+1}^D{\bf u}_i{\bf S}{\bf u}_i\tag{11} \end{eqnarray}

M=1 の場合の誤差最小化

ここで一旦、2次元のデータ空間 D=2 と 1 次元の主部分空間 M=1 を考えることにします。
この場合、制約条件 {\bf u}_2^\top{\bf u}_2=1 の下で、射影された分散 {\bf u}_2^\top{\bf S}{\bf u}_2 を最小化すればよいことになります。
ラグランジュの未定乗数法を用いると、ラグランジュ関数は以下のようになります。

\begin{eqnarray} \tilde{J}={\bf u}_2^\top{\bf S}{\bf u}_2+\lambda_2(1-{\bf u}_2^\top{\bf u}_2)\tag{5} \end{eqnarray}

\tilde{J} を {\bf u}_2 で微分して、={\bf 0} とおきます。

\begin{eqnarray} &&\frac{\partial}{\partial{\bf u}_2}\tilde{J}={\bf 0}\\ &&\Leftrightarrow\frac{\partial}{\partial{\bf u}_2}{\bf u}_2^\top{\bf S}{\bf u}_2+\frac{\partial}{\partial{\bf u}_2}\lambda_2(1-{\bf u}_2^\top{\bf u}_2)={\bf 0}\\ &&\Leftrightarrow 2{\bf S}{\bf u}_2-2\lambda_2{\bf u}_2={\bf 0}\\ &&\Leftrightarrow{\bf S}{\bf u}_2=\lambda_2{\bf u}_2\\ &&\Leftrightarrow{\bf u}_2^\top{\bf S}{\bf u}_2=\lambda_2\tag{6} \end{eqnarray}

したがって、2 つある固有値のうち小さい方の固有値に対応する固有ベクトル {\bf u}_2 を選んだ時に歪み尺度 J の最小値を得ることができます。
よって、主部分空間は大きい方の固有値を持つ固有ベクトルに沿うように選ぶとよいことが分かります。

一般的な M の場合の誤差最小化

今度は一般的な M,D(M < D) について考えます。

この場合も、主成分分析 - 分散最大化による定式化 - 導出その1の記事と同様に、
\bf S の固有値のうち小さい方の D−M 個に対応する固有ベクトルを選んだ時に歪み尺度 J の最小値を得ることができます。
よって、主部分空間は \bf S の固有値のうち大きい方の M 個に対応する固有ベクトルを選ぶとよいことが分かります。
これの証明については、PRML演習問題 12.2(標準) をご覧ください。

偉人の名言


他人の芸を見てあいつは下手だなと思ったら　そいつは自分と同じくらい
同じくらいだなと思ったら　かなり上
うまいなあと感じたら　とてつもなく先へ行っている
古今亭志ん生

参考文献

パターン認識と機械学習 下巻

参考リンク

Matrix Calculus
PRML 12.2解答

動画

なし

目次へ戻る