Ice Break
線形代数を思い出すために勉強したんで書き留めておきます。
本稿では機械学習のbasicな手法であるPCAを題材に線形代数を復習していきます。
参考にした文献は（Deep learning by Ian Goodfellow ）です。
翻訳が正確じゃないところがあるかもしれないです。
$\newcommand{\argmin}{\mathop{\rm arg~min}\limits}$
$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}$
主成分分析についてざっくり
統計解析を行うにあたって用いるデータの選択は重要です。
たくさんのデータがあれば解析の精度は向上するが一般にメモリ制約を受けます。(ほんまか？)
そのような状況においてデータをなるべく情報を欠落させずに圧縮する手法が主成分分析です。
身近な例としてはBMIがわかりやすくて、身長と体重の２次元データから１次元データに圧縮していますよね。あんな感じで圧縮することで指標としてわかりやすくなったりすることもあります。
主成分分析の導出
概念の整理
$\mathbb{R}^n$空間におけるm個の点について考えます。(1)
\boldsymbol{X} = \{\boldsymbol{x}^{(1)},...,\boldsymbol{x}^{(m)}\}\cdots(1)
このベクトル集合をl次元(n>l)に圧縮することが主成分分析のざっくりした捉え方です。(2)
\boldsymbol{f}:\boldsymbol{x}^{(i)} \in \mathbb{R}^{n}\ \longmapsto \boldsymbol{c}^{(i)} \in \mathbb{R}^{l}\cdots(2)
(2)より主成分分析では$f(\boldsymbol{x})=\boldsymbol{c}$を満たす符号化関数$f$及び、$\boldsymbol{c}\ {\simeq}\ g(f(\boldsymbol{x}))$を満たす復号化関数$g$を探索します。
主成分分析では復号化関数$g$の探索を容易にするために符号$\boldsymbol{c}$を$\mathbb{R}^n$空間に逆写像するアプローチを取ります。このことは以下の式で表現できます。
g(\boldsymbol{c})=\boldsymbol{D}\boldsymbol{c}\ {\simeq}\ \boldsymbol{x} \ where\ \boldsymbol{D}\ \in \mathbb{R}^{n\times l}\cdots(3)
この行列を探索する際、解が一義的に定まらない可能性があるため２つ制約を設けています。（クラピカのあれです）
①$\boldsymbol{D}$の列ベクトルが互いに直交すること
②$\boldsymbol{D}$の列ベクトルが単位ノルムを有すること
符号化関数fと復号関数gの探索
$①入力\boldsymbol{x}$に対する最適な$g(\boldsymbol{c})$の探索
ここまでの説明でなぜ符号化関数$\boldsymbol{f}$から探索しないのか不思議に思う人もいると思いますが天下り的な導出をお許し下さい。さて、今回の導出手法では最適な$\boldsymbol{g}$を探索するために$\boldsymbol{c^*}$を導入します。
{\boldsymbol{c^*} = \argmin_{\boldsymbol{c}} \|\|\boldsymbol{x} - g(\boldsymbol{c})\|\|_{2}\cdots(4)}
またL2ノルムが非負の値を取り、なおかつ同じ$\boldsymbol{c}$において最小化されることを用いて、L2ノルムの二乗を使用します。（式の展開を容易に行うため）
{\boldsymbol{c^*} = \argmin_{\boldsymbol{c}} \|\|\boldsymbol{x} - g(\boldsymbol{c})\|\|_{2}^2\cdots(4)'}
このことより最小化する関数は以下のように単純化されます。
\begin{align}
\|\|\boldsymbol{x} - g(\boldsymbol{c})\|\|_{2}^2 &= (\boldsymbol{x} - g(\boldsymbol{c}))^{\mathrm{T}}(\boldsymbol{x} - g(\boldsymbol{c}))\cdots(5)\\\\
&=\boldsymbol{x}^{\mathrm{T}}\boldsymbol{x}-\boldsymbol{x}^{\mathrm{T}}g(\boldsymbol{c})
-g(\boldsymbol{c})^{\mathrm{T}}\boldsymbol{x}+g(\boldsymbol{c})^{\mathrm{T}}g(\boldsymbol{c})\cdots(6)\\\\
&=\boldsymbol{x}^{\mathrm{T}}\boldsymbol{x}-2\boldsymbol{x}^{\mathrm{T}}g(\boldsymbol{c})
+g(\boldsymbol{c})^{\mathrm{T}}g(\boldsymbol{c})\cdots(7)
\end{align}
式変形に使用した性質
(5)L2ノルムの定義
(6)分配法則
(7)転置後のスカラーが等しいことを利用
$\boldsymbol{c^*}$は$\boldsymbol{c}$に依存する関数であることを思い出して式(4)を少し書き直す。
\boldsymbol{c^*} = \argmin_{\boldsymbol{c}}-2\boldsymbol{x}^{\mathrm{T}}g(\boldsymbol{c})
+g(\boldsymbol{c})^{\mathrm{T}}g(\boldsymbol{c})\cdots(8)
また式(3)の定義を利用して
\begin{align}
\boldsymbol{c^*} &= \argmin_{\boldsymbol{c}}-2\boldsymbol{x}^{\mathrm{T}}\boldsymbol{Dc}
+(\boldsymbol{Dc})^{\mathrm{T}}\boldsymbol{Dc}\cdots(9)\\\\
&=\argmin_{\boldsymbol{c}}-2\boldsymbol{x}^{\mathrm{T}}\boldsymbol{Dc}
+\boldsymbol{c}^{\mathrm{T}}\boldsymbol{D}^{\mathrm{T}}\boldsymbol{Dc}\cdots(10)\\\\
&=\argmin_{\boldsymbol{c}}-2\boldsymbol{x}^{\mathrm{T}}\boldsymbol{Dc}
+\boldsymbol{c}^{\mathrm{T}}\boldsymbol{I_{l}}\boldsymbol{c}\cdots(11)\\\\
&=\argmin_{\boldsymbol{c}}-2\boldsymbol{x}^{\mathrm{T}}\boldsymbol{Dc}
+\boldsymbol{c}^{\mathrm{T}}\boldsymbol{c}\cdots(12)
\end{align}
式変形に使用した性質
(9) 式(3)より$g(\boldsymbol{c})=\boldsymbol{Dc}$
(10)行列の積の転置の定義より$(\boldsymbol{Dc})^{\mathrm{T}}=\boldsymbol{c}^{\mathrm{T}}\boldsymbol{D}^{\mathrm{T}}$
(11)直交性と単位ノルムの制約より
(12)単位行列の性質より
この最小化問題に対してgradientベースの解法が存在しています(機械学習の常套手段)
ざっくり説明すると微分して0になるところって最小値だよねっていう考え方。鋭い人からすれば極小値$\neq$最小値や極大値を示す可能性について議論が必要だと感じるかもしれませんが、また今度やるので一旦このアプローチで進めます。(線形代数で議論しきれないので)
\nabla_{c}(-2\boldsymbol{x}^{\mathrm{T}}\boldsymbol{Dc}
+\boldsymbol{c}^{\mathrm{T}}\boldsymbol{c})= 0\cdots(13)
-2\boldsymbol{D}^{\mathrm{T}}\boldsymbol{x}
+2\boldsymbol{c}= 0\cdots(14)
\boldsymbol{c}= \boldsymbol{D}^{\mathrm{T}}\boldsymbol{x}\cdots(15)
式変形に使用した性質
(13) 最小化問題の典型的アプローチ
(14)$\boldsymbol{c}$で微分した
(15)2で割って移項しただけ
ここがすごい慣性が大きい話になるんですが、最適な復号関数$\boldsymbol{g}$を探索していたら最適な符号化関数$\boldsymbol{f}$が導出されます。
また、このことにより$
\boldsymbol{f(x)}=\boldsymbol{c}
$を$\boldsymbol{f(x)}=\boldsymbol{D}^{\mathrm{T}}\boldsymbol{x}$で表現できます。
また復号関数$g$は式(3)より
\begin{align}
r(\boldsymbol{x})&=g(f(\boldsymbol{x}))\\
&=\boldsymbol{D}\boldsymbol{c}\\
&=\boldsymbol{D}\boldsymbol{D}^{\mathrm{T}}\boldsymbol{x}\cdots(16)
\end{align}
と定義できる。
符号化行列Dの探索
ここでもう一度、入力$\boldsymbol{x}$と$\boldsymbol{c}$のL2を最小化するアプローチをとる。先程と異なる点はすべての$\boldsymbol{x}^{(i)}$に対して同一の$\boldsymbol{D}$を作用させるため、今まで一つの$\boldsymbol{x}$ついて考えてきた誤差の概念をi個の$\boldsymbol{x}$に拡張する必要があるります。そのためフロペニウスノルムを用いて誤差関数を定義し、最小化を試みます。
\boldsymbol{D}^{*}=\argmin_{\boldsymbol{D}}\sqrt{\sum_{i,j}(x_{j}^{(i)}-r(\boldsymbol{x}^{(i)})_j)^{2}}\ subject \ to \ \boldsymbol{D}^{\mathrm{T}}\boldsymbol{D}=\boldsymbol{I}_{l}\cdots(17)
この式(17)に式(16)を代入すると
\boldsymbol{D}^{*}=\argmin_{\boldsymbol{D}}\sqrt{\sum_{i,j}(x_{j}^{(i)}-\boldsymbol{D}\boldsymbol{D}^{\mathrm{T}}(\boldsymbol{x}^{(i)})_j)^{2}}\cdots(17)^{'}
式(17)を最小化するために、まずl = 1 について考えます。
\boldsymbol{d}^{*}=\argmin_{\boldsymbol{d}}\sum_{i,j}||\boldsymbol{x}_{j}^{(i)}-\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{x}^{(i)}||_{2}^{2}\ subject \ to \ ||\boldsymbol{d}||_{2}=1\cdots(18)
ここでスカラーである$\boldsymbol{d}^{\mathrm{T}}(\boldsymbol{x}^{(i)})$がベクトルの右に表記されている、マナー上良くない書き方らしいので以下のように書き直します。
\boldsymbol{d}^{*}=\argmin_{\boldsymbol{d}}\sum_{i,j}||\boldsymbol{x}_{j}^{(i)}-\boldsymbol{d}^{\mathrm{T}}\boldsymbol{x}^{(i)}\boldsymbol{d}||_{2}^{2}\ subject \ to \ ||\boldsymbol{d}||_{2}=1\cdots(18)^{'}
またスカラー部の転置行列の性質を利用して以下のように書き下すことができます。
\boldsymbol{d}^{*}=\argmin_{\boldsymbol{d}}\sum_{i,j}||\boldsymbol{x}_{j}^{(i)}-\boldsymbol{x}^{(i)T}\boldsymbol{d}\boldsymbol{d}||\ subject \ to \ ||\boldsymbol{d}||_{2}=1\cdots(18)^{''}
このように機械学習の論文では行列を含む式を書き下しているときがあるので慣れておくと、ひるまなくて済みます。
そしてここで式を展開しすぎて訳が分からなくなってきたので、一度整理します。
\boldsymbol{X} = \{\boldsymbol{x}^{(1)},...,\boldsymbol{x}^{(m)}\}\ subject\ to \ \ \boldsymbol{x}^{(i)}\in \mathbb{R}^{n}
の関係を思い出して式$(18)^{''}$を$\boldsymbol{X}$を用いて書き直すと
\boldsymbol{d}^{*}=\argmin_{\boldsymbol{d}}||\boldsymbol{X}-\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}||_{F}^{2}\ \ subject \ to \ ||\boldsymbol{d}||_{2}=1\cdots(19)
この式(19)を更に展開していく
\begin{align}
\argmin_{\boldsymbol{d}}||\boldsymbol{X}-\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}||_{F}^{2}
&=\argmin_{\boldsymbol{d}}Tr((\boldsymbol{X}-\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})^{\mathrm{T}}(\boldsymbol{X}-\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}))\cdots(20)\\
&=\argmin_{\boldsymbol{d}}Tr((\boldsymbol{X}^\mathrm{T}\boldsymbol{X}-\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}-\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{X}^\mathrm{T}\boldsymbol{X}+\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})\dots(21)\\
&=\argmin_{\boldsymbol{d}}Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X})-Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})-Tr(\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{X}^\mathrm{T}\boldsymbol{X})+Tr(\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})\dots(22)\\
&=\argmin_{\boldsymbol{d}}-Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})-Tr(\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{X}^\mathrm{T}\boldsymbol{X})+Tr(\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})\dots(23)\\
&=\argmin_{\boldsymbol{d}}-2Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})+Tr(\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})\dots(24)\\
&=\argmin_{\boldsymbol{d}}-2Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})+Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})\dots(25)\\
\end{align}
式変形に使用した性質
(20)フロペニウスノルムの性質 $||\boldsymbol{A}||_{F}=\sqrt{Tr(\boldsymbol{A}\boldsymbol{A}^\mathrm{T})}$
(21)(22)分配法則
(23)$\boldsymbol{d}$に影響しない項を排除
(24)(25)Trace行列の巡回可能な法則を利用
ここで制約条件 $subject\ to\ \boldsymbol{d}^{\mathrm{T}}\boldsymbol{d}=1$ を思い出して式を整理していく
\begin{align}
\argmin_{\boldsymbol{d}}-2Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})+Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})\ subject\ to\ \boldsymbol{d}^{\mathrm{T}}\boldsymbol{d}=1\dots(26)\\
\end{align}
\begin{align}
\argmin_{\boldsymbol{d}}-2Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})+Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})\ subject\ to\ \boldsymbol{d}^{\mathrm{T}}\boldsymbol{d}=1\dots(27)\\
\end{align}
\begin{align}
\argmin_{\boldsymbol{d}}-Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})\ subject\ to\ \boldsymbol{d}^{\mathrm{T}}\boldsymbol{d}=1\dots(28)\\
\end{align}
\begin{align}
\argmax_{\boldsymbol{d}}\ Tr(\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d}\boldsymbol{d}^{\mathrm{T}})\ subject\ to\ \boldsymbol{d}^{\mathrm{T}}\boldsymbol{d}=1\dots(29)\\
\end{align}
\begin{align}
\argmax_{\boldsymbol{d}}\ Tr(\boldsymbol{d}^{\mathrm{T}}\boldsymbol{X}^\mathrm{T}\boldsymbol{X}\boldsymbol{d})\ subject\ to\ \boldsymbol{d}^{\mathrm{T}}\boldsymbol{d} =1\dots(30)\\
\end{align}
式変形に使用した性質
(26)制約条件の追加
(27)制約条件より$\boldsymbol{d}^{\mathrm{T}}\boldsymbol{d}$を１とみなした
(28)加算則
(29)符号を反転させ、最大値問題に転換（よくやる）
(30)固有値問題に落とし込むための並び替え
式(30)は固有値問題として解くことができます。行列$\boldsymbol{X}^\mathrm{T}\boldsymbol{X}$の最大固有値に対応する固有ベクトルが$\boldsymbol{d}$に対応するためです。今回は1次の場合について導出しましたが、行列$\boldsymbol{D}$においても最大固有値に対応するl個のベクトルを格納したものに対応することが知られています。
$\LaTeX$楽しかった