機械学習基礎理論独習

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

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

PRML演習問題 12.1(標準) www

問題

この演習問題では、帰納法を使って、射影されたデータの分散を最大化するような M 次元部分空間の上への線形写像が、
データ共分散行列 \bf S (定義は (12.3)) の上位 M 個の固有値に属する M 本の固有ベクトルにより定義されることを証明する。
12.1 節では、M=1 に対してこの結果を証明した。
今度は.ある一般的な値 M に対してこの結果が成り立つと仮定して、その下で M+1 次元に対しでも成り立つことを示す。
これを行うため、最初に、射影されたデータの分散の、ベクトル {\bf u}_{M+1} に対する微分0 とおく。
{\bf u}_{M+1} はデータ空間における新しい方向を定義する。
このとき、次の 2 つの制約を同時に満足しなければならない。
ひとつは、{\bf u}_{M+1} がすでに求めたベクトル {\bf u}_1,\ldots,{\bf u}_{M+1} と直交するという制約であり、
もうひとつは単位長さに規格化しておかなければならないという制約である。
この制約を取り込むためにラグランジュ乗数(⇒付録E)を使ってみよ。
そうして、新しいベクトル {\bf u}_{M+1}{\bf S}固有ベクトルであることを示すために、
ベクトル {\bf u}_1,\ldots,{\bf u}_M の正規直交性を利用せよ。
最後に、固有値が大きい順に並べられているときに、その固有ベクトル {\bf u}_{M+1}\lambda_{M+1} に対応する固有ベクトルに選べば、
分散が最大化されることを示せ。

参照

\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{12.3}
\end{eqnarray}

解答

示すべきは
主部分空間の次元がMのときは固有値が大きい方からM個選び、それに対応する固有ベクトルが主部分空間の基底となる・・・(*)
です。
[証明]
帰納法を用います。
M=1の場合は(*)を既に示してあります。
ここで一般的なMに対しても(*)が成り立っていると仮定します。
この仮定の下で、第M+1主成分{\bf u}_{M+1}を求めます。
{\bf u}_{M+1}は次の関係式が成り立ちます。

\begin{eqnarray}
&&{\bf u}_{M+1}^\top{\bf u}_{M+1} = 1\tag{1}\\
&&{\bf u}_{M+1}^\top{\bf u}_i = 0\hspace{20px}(i=1,\ldots,M)\tag{2}
\end{eqnarray}

制約条件 (1),(2) の下で分散を最大化します。
ラグランジュの未定乗数法を用いると、ラグランジュ関数は以下のようになります。

\begin{eqnarray}
L({\bf u}_{M+1},\lambda_{M+1},\eta_1,\ldots,\eta_M)={\bf u}_{M+1}^\top{\bf S}{\bf u}_{M+1}+\lambda_{M+1}(1-{\bf u}_{M+1}^\top{\bf u}_{M+1})+\sum_{i=1}^M\eta_i{\bf u}_{M+1}^\top{\bf u}_i\tag{3}
\end{eqnarray}

L{\bf u}_{M+1}微分して、={\bf 0}とおきます。

\begin{eqnarray}
&&\frac{\partial}{\partial{\bf u}_{M+1}}L({\bf u}_{M+1},\lambda_{M+1},\eta_1,\ldots,\eta_M)={\bf 0}\\
&&\Leftrightarrow\frac{\partial}{\partial{\bf u}_{M+1}}{\bf u}_{M+1}^\top{\bf S}{\bf u}_{M+1}+\frac{\partial}{\partial{\bf u}_{M+1}}\lambda_{M+1}(1-{\bf u}_{M+1}^\top{\bf u}_{M+1})+\sum_{i=1}^M\eta_i\frac{\partial}{\partial{\bf u}_{M+1}}{\bf u}_{M+1}^\top{\bf u}_i={\bf 0}\\
&&\Leftrightarrow 2{\bf S}{\bf u}_{M+1}-2\lambda_{M+1}{\bf u}_{M+1}+\sum_{i=1}^M\eta_i{\bf u}_i={\bf 0}\tag{4}
\end{eqnarray}

(4) の両辺に左から{\bf u}_j^\top\hspace{10px}(j=1,\ldots,M)を掛けます。

\begin{eqnarray}
&&2{\bf u}_j^\top{\bf S}{\bf u}_{M+1}-2\lambda_{M+1}{\bf u}_j^\top{\bf u}_{M+1}+\sum_{i=1}^M\eta_i{\bf u}_j^\top{\bf u}_i={\bf u}_j^\top{\bf 0}\\
&&\Leftrightarrow 2{\bf u}_{M+1}^\top{\bf S}{\bf u}_j+\eta_j=0\\
&&\Leftrightarrow 2{\bf u}_{M+1}^\top\lambda_j{\bf u}_j+\eta_j=0\\
&&\Leftrightarrow \eta_j=0\tag{5}
\end{eqnarray}

(5) を 式 (4) に代入します。

\begin{eqnarray}
&&2{\bf S}{\bf u}_{M+1}-2\lambda_{M+1}{\bf u}_{M+1}+\sum_{i=1}^M 0 {\bf u}_i={\bf 0}\\
&&\Leftrightarrow {\bf S}{\bf u}_{M+1}=\lambda_{M+1}{\bf u}_{M+1}\tag{6}
\end{eqnarray}

この時、射影されたデータの分散は

\begin{eqnarray}
\sum_{i=1}^{M+1}{\bf u}_i^\top{\bf S}{\bf u}_i&=&\sum_{i=1}^{M}{\bf u}_i^\top{\bf S}{\bf u}_i+{\bf u}_{M+1}^\top{\bf S}{\bf u}_{M+1}\\
&=&\sum_{i=1}^{M}\lambda_i+\lambda_{M+1}\tag{7}
\end{eqnarray}

仮定より\lambda_i\hspace{10px}(i=1,\ldots,M)固有値の大きい方M個なので、
分散(式 (7))を最大にするためには、\lambda_{M+1}M+1番目に大きい固有値となります。
よって、{\bf u}_{M+1}M+1番目に大きい固有値に対応するベクトルです。
したがって、Mの場合に(*)が成り立つとき、M+1の場合も(*)が成り立ちます。

以上より、一般的なMの場合に(*)が成り立ちます。
[証明終わり]

目次へ戻る