Aubergineのブログ

カーネル主成分分析というもの

Python機械学習プログラミング達人データサイエンティストによる理論と実践 (impress top gear)で勉強していたところ，カーネル主成分分析（以下，Kernel PCA）の導出の筋が理解できませんでした．そこで本書で学習される方の一助になれば幸い思いと思い，別の導出方法を記します．カーネル法のイメージと価値については，英語の質問ページを和訳なさったこちらのページの説明が簡潔でわかりやすかったです．

Kernal PCAはPCAの名を冠しているし，データを特徴空間へ写像した後の手順はPCAと同様だろうと高をくくっていましたが，そんなことはありませんでした．

Kernel PCAは，PCAにおける共分散行列の固有値問題を，共分散行列ではなくグラム行列により表現することで，ベクトルの無限次元空間への写像$\phi$を扱えるようになっています．グラム行列に着目した点はKernel PCAの肝として強調されるべきだと思います．

$\phi$による写像の（陽な）計算はkernel関数を考えることで省略されています（所謂カーネルトリック）が，この省略により無限次元の行列積の計算をする必要をなくしています．美しいです．

導出の話

本題です．書籍における非線形関数$\boldsymbol{\phi}$からカーネル関数$K$に至る別の道のりを示します．

本稿では行列$X$のとり方を書籍と変更し，列ベクトル$x_i(i=1, 2, \cdots, n)$を列方向に並べた（横に並べた）行列を$X$とします．すなわち，

$$
\boldsymbol{x_i} = \left[ \begin{array}{c}
\vdots \\\
\vdots \\\
\vdots \\\
\end{array}
\right] \in \mathbb{R}^d \ \ (i=1,2, \dotsc, n)
,\ \ \boldsymbol{X} = \left[ \begin{array}{cccc}
\ & \ & \ & \ \\
\boldsymbol{x}_1 & \boldsymbol{x}_2 & \cdots & \boldsymbol{x}_n \\\
\ & \ & \ & \ \\
\end{array}
\right] \ \in \mathbb{R}^{d \times n}
$$

となります．$\boldsymbol{\phi} (\mathbb{R}^d \mapsto \mathbb{R}^k)$は入力ベクトル$x$をより高次元のベクトルに写像する関数です．ここで$d < k$です．

（書籍では$x$を列ベクトルとしているので，$X$はこの置き方が自然と思うのですが，分野によって流儀が異なるのでしょうか．ご意見がございましたらよろしくお願いいたします．）

書籍ではグラム行列$\boldsymbol{\Sigma}$は式(5.3.9)で総和記号を使わずに表現しています．

$$
\Sigma = \frac{1}{n} \sum_{i=1}^n \boldsymbol{\phi} (\boldsymbol{x}^{(i)}) \boldsymbol{\phi} (\boldsymbol{x}^{(i)})^T
$$

そして，グラム行列$\boldsymbol{\Sigma}$の固有値・固有ベクトルを求めます．

すなわち，

$$
\boldsymbol{\Sigma} \boldsymbol{u}_i = \lambda_i \boldsymbol{u}_i
$$

を満たす固有対$(\lambda_i , \boldsymbol{u}_i)$を求めます．

ここで関数$\Phi (\mathbb{R}^{d \times n} \mapsto \mathbb{R}^{k \times n})$を行列$\boldsymbol{A} = \left[ \boldsymbol{a}_1 \ \boldsymbol{a}_2 \ \cdots \ \boldsymbol{a}_n \right] \in \mathbb{R}^{d \times n}$を入力とする関数として

$$
\boldsymbol{\Phi} (\boldsymbol{A}) \equiv
\boldsymbol{\Phi} ( \left[ \boldsymbol{a}_1 \ \boldsymbol{a}_2 \ \cdots \ \boldsymbol{a}_n \right]) = \left[\begin{array}{cccc}
\ & \ & \ & \ \\\
\boldsymbol{\phi(\boldsymbol{a}_1)} & \boldsymbol{\phi(\boldsymbol{a}_2)} & \cdots & \boldsymbol{\phi(\boldsymbol{a}_n)} \\\
\end{array}
\right]
$$

と定義すれば，

$$
\sum_{i=1}^n \boldsymbol{\phi} \left( \boldsymbol{x}^{(i)} \right) \boldsymbol{\phi} \left( \boldsymbol{x}^{(i)} \right) ^T = \boldsymbol{\Phi} (\boldsymbol{X}) \boldsymbol{\Phi} (\boldsymbol{X})^T
$$

が成立します．この関係式は行列のスペクトル分解と呼ばれるものですね．スペクトル分解の説明は後ほど．

ところで$\boldsymbol{\Phi} (\boldsymbol{X}) \boldsymbol{\Phi} (\boldsymbol{X})^T$は半正定値行列（非負定値行列）であるため，固有値は全て0以上となることが保証されています．証明は後ほど．

実は上式の形で表現されていなくとも，半正定値行列は上式の形で表現できることも証明できます．この証明がなされた時点で，$K$が知れているなら，$\phi$の形を明らかにする必要なくなったわけです．

スペクトル分解

行列$X$が
$$
\boldsymbol{X} = \left[ \begin{array}{cccc}
\ & \ & \ & \ \\\
\boldsymbol{x}_1 & \boldsymbol{x}_2 & \cdots & \boldsymbol{x}_n \\\
\end{array}
\right]
$$

と表される時，

$$
XX^T = \sum_{i=1}^{n} \boldsymbol{x}_i \boldsymbol{x}_i^T
$$

が成立する．というもの．
いま適切な次元の列ベクトル$\boldsymbol{b}$を用意して，

$$
\begin{align}
XX^T\boldsymbol{b} &= \left[ \begin{array}{cccc}
\ & \ & \ & \ \\\
\boldsymbol{x}_1 & \boldsymbol{x}_2 & \cdots & \boldsymbol{x}_n \\\
\ & \ & \ & \ \\\
\end{array}
\right]
\left[ \begin{array}{ccc}
\ & \boldsymbol{x}_1^T & \ \\\
\ & \boldsymbol{x}_2^T & \ \\\
\ & \vdots & \ \\\
\ & \boldsymbol{x}_n^T & \ \\\
\end{array}
\right]
\boldsymbol{b}\\

&= \left[ \begin{array}{cccc}
\ & \ & \ & \ \\\
\boldsymbol{x}_1 & \boldsymbol{x}_2 & \cdots & \boldsymbol{x}_n \\\
\ & \ & \ & \ \\\
\end{array}
\right]
\left[ \begin{array}{ccc}
\boldsymbol{x}_1^T \boldsymbol{b}\\\
\boldsymbol{x}_2^T \boldsymbol{b}\\\
\vdots\\\
\boldsymbol{x}_n^T \boldsymbol{b}\\\
\end{array}
\right] \\

&= \boldsymbol{x}_1 \boldsymbol{x}_1^T \boldsymbol{b} +\boldsymbol{x}_2 \boldsymbol{x}_2^T \boldsymbol{b} + \cdots+ \boldsymbol{x}_n \boldsymbol{x}_n^T \boldsymbol{b} \\

&= \left( \sum_{i=1}^{n} \boldsymbol{x}_i \boldsymbol{x}_i^T \right) \boldsymbol{b}

\end{align}
$$

従って
$$
\begin{align}
& XX^T\boldsymbol{b} = \left( \sum_{i=1}^{n} \boldsymbol{x}_i \boldsymbol{x}_i^T \right) \boldsymbol{b} \\
\Leftrightarrow & \left(XX^T - \sum_{i=1}^{n} \boldsymbol{x}_i \boldsymbol{x}_i^T \right) \boldsymbol{b} = \boldsymbol{0} \\
& (\because ２つの行列XX^T，\sum_{i=1}^{n} \boldsymbol{x}_i \boldsymbol{x}_i^T は同じサイズ)
\end{align}
$$

を得ますが，最後に得た等式が任意の$\boldsymbol{b}$について成立することから $XX^T - \sum_{i=1}^{n} \boldsymbol{x}_i \boldsymbol{x}_i^T$が零行列であることが示され，ここから
$$
XX^T = \sum_{i=1}^{n} \boldsymbol{x}_i \boldsymbol{x}_i^T
$$
が得られます．

半正定値行列であることの説明

$\boldsymbol{\Phi} (\boldsymbol{X}) \boldsymbol{\Phi} (\boldsymbol{X})^T$の二次形式が非負であることを直接示します．$\boldsymbol{y} $を0でないベクトルとします．

$$
\begin{align}
\boldsymbol{y}^{T} \boldsymbol{\Phi} (\boldsymbol{X}) \boldsymbol{\Phi} (\boldsymbol{X})^T \boldsymbol{y}
&= \left( \boldsymbol{\Phi} (\boldsymbol{X}) ^{T} \boldsymbol{y} \right) ^{T} \left( \boldsymbol{\Phi} (\boldsymbol{X}) ^{T} \boldsymbol{y} \right) \\
& = \| \boldsymbol{\Phi} (\boldsymbol{X}) ^{T} \boldsymbol{y} \| ^2 \\
& \geq 0
\end{align}
$$