読者です 読者をやめる 読者になる 読者になる

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

Kernel PCA (Principal Component Analysis) の導出

何の話かというと

Python Machine Learning: Unlock Deeper Insights into Machine Learning With This Vital Guide to Cutting-edge Predictive Analytics

Python Machine Learning: Unlock Deeper Insights into Machine Learning With This Vital Guide to Cutting-edge Predictive Analytics

この本のKernel PCAの説明が相当に計算を端折っていて、これは読者もつらいだろぅ。。。と思って途中の計算を端折らずになるべく正確に導出してみました。

※実対称行列の固有値分解とLagrangeの未定乗数法は前提知識とします。

普通のPCA

はじめに、Kernelを使わない普通のPCAを導出します。

データセット \{{\mathbf x}_n\}_{n=1}^N,\,\,{\mathbf x}_n \in {\mathbf R}^{\rm D} の分散共分散行列を {\mathbf S} とします。この時、{\mathbf S} は正定値の実対称行列より、正(もしくは0)の固有値を持つ、互いに直行する固有ベクトルで固有値分解されます。この点に注意すると、第1主軸(その方向の成分の分散が最大になる方向)を {\mathbf u}_1\,\,(\|{\mathbf u}_1\|=1) とする時、これは、最大固有値を持つ固有ベクトルに一致することが次のように示されます。

次に、第2主軸({\mathbf u_1} に直行する方向で、その方向の成分の分散が最大になる方向){\mathbf u}_2\,\,(\|{\mathbf u}_2\|=1) は、2番目に大きな固有値を持つ固有ベクトル、さらに第3主軸({\mathbf u_1}{\mathbf u_2} の両方に直行する方向で、その方向の成分の分散が最大になる方向){\mathbf u}_3\,\,(\|{\mathbf u}_3\|=1) は、3番目に大きな固有値を持つ固有ベクトル・・・であることが帰納的に証明されます。


Kernel PCA

D次元空間のデータに対して、何らかの非線形関数 {\mathbf \phi}({\mathbf x}) \in {\mathbf R}^M\,\,(M>D) を用いて、M次元空間のデータに変換した後、データセット \{ {\mathbf \phi}({\mathbf x_n})  \}_{n=1}^N に対して、M次元空間上でのPCAを適用します。すると、次のような結論が得られます。(証明は後ほど掲載)

========
k({\mathbf x_n},{\mathbf x_{n'}})={\mathbf \phi}({\mathbf x}_n)^{\rm T}{\mathbf \phi}({\mathbf x}_{n'})\,\,(n,n'=1,\cdots,N) を成分とする対称行列を {\mathbf K}\in {\mathbf R}^N\times{\mathbf R}^N とする時、グラム行列 \tilde{\mathbf K} を次式で定義する。

 \tilde{\mathbf K} = {\mathbf K} - {\mathbf 1}_N{\mathbf K} - {\mathbf K}{\mathbf 1}_N + {\mathbf 1}_N{\mathbf K}{\mathbf 1}_N

ここに、{\mathbf 1}_N は、すべての成分が 1/N という値のN✕N行列である。

\tilde{\mathbf K} の正の固有値について、大きい方から並べたものを \lambda_1,\lambda_2,\cdots 、対応する(大きさ1の)固有ベクトルを {\mathbf u}_1,{\mathbf u}_2,\cdots \in {\mathbf R}^N とする時、第i主軸方向の単位ベクトルは、次式で与えられる。

 {\mathbf v}_i =\frac{1}{\sqrt{\lambda_i N}}  \sum_{n=1}^N u_{in}\left\{{\mathbf \phi}({\mathbf x}_n)-\frac{1}{N}\sum_{n'=1}^N{\mathbf \phi}({\mathbf x}_{n'})\right\}

この時、任意の点 {\mathbf x} について、非線形変換されたM次元空間における第i主軸成分は、次で計算される。

 {\mathbf \phi}({\mathbf x})^{\rm T}{\mathbf v}_i = \frac{1}{\sqrt{\lambda_i N}}  \sum_{n=1}^N u_{in}k({\mathbf x},{\mathbf x}_n)

ここに、k({\mathbf x},{\mathbf x}')={\mathbf \phi}({\mathbf x})^{\rm T}{\mathbf \phi}({\mathbf x}') をカーネル関数と呼ぶ。
========

この結果の重要なポイントして、{\mathbf u}_i の定義、および、最後の計算式を用いれば、非線形変換 {\mathbf \phi}({\mathbf x}) の具体的な形がわからなくても、カーネル関数 k({\mathbf x},{\mathbf x}') が与えられれば、第i主軸成分が計算できることが挙げられます。

たとえば、カーネル関数として、ガウスカーネル k({\mathbf x},{\mathbf x}_n)=\exp \left\{-\gamma(\| {\mathbf x}-{\mathbf x}_n \|^2)\right\} を用いた場合を考えます。これは、u_{in} が大きな値を取る n について、{\mathbf x_n} との距離が近いほど、その主軸成分が大きくなることを意味します。つまり、k近傍法のように「どのデータとの距離が近いかによって、主軸成分の大小が決まる」ことになります。これによって、元の {\mathbf x} 平面上でのデータの配置に関係なく、それぞれのデータとの距離を特徴量として抽出できることを意味します。(ガウスカーネルに対応するような {\mathbf \phi}({\mathbf x}) が存在することは別途証明が必要ですが、その証明はここでは省略します。)

それでは、前述の結論の証明です。





Kernel PCAの適用例

三日月形に並んだデータ群について、第1〜第4主軸成分の等高線を描きます。赤色は値が大きい所(山)で、青色は値が小さい所(谷)を示します。

gist.github.com

第1主軸成分を見ると、2つの三日月のどちらのデータに近いかで成分の大小が決まっていることが分かります。さらに第2主軸成分は、それぞれの三日月を左右に分割しています。高次の主軸成分になるほど、より細かくデータを分割することが観察できます。