Kernel PCA (Principal Component Analysis) の導出

何の話かというと

Python Machine Learning: Unlock deeper insights into Machine Leaning with this vital guide to cutting-edge predictive analytics (English Edition)

作者:Raschka, Sebastian
Packt Publishing

Amazon

この本の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})$ が存在することは別途証明が必要ですが、その証明はここでは省略します。）