線形分離のできないデータに対して特徴抽出・次元削減を行うとき、特徴量を既存の特徴空間からより高次の特徴空間に写像し、写像先の高次な特徴空間で主成分分析を行う方法が使われている。特徴量をより高次の特徴空間に写像するときに使われる関数を φ とすると、関数 φ は、次のように d 次元の特徴量を受け取り、それを k (<< d) 次元空間に射影するような関数として定義できる。
\[ \phi : \mathbb{R}^{d} \rightarrow \mathbb{R}^{k} \]カーネル主成分分析の固有値と固有ベクトル
分散共分散行列
ここで、入力特徴量を n 行 d 列の行列 X で表す。d 列の特徴量について、それぞれの平均が 0 となるように標準化されているものとする。すると、行列 X の分散共分散行列 Σ は次のようにかける。
\[ \mathbf{\Sigma}_{\mathbf{X}} = \begin{pmatrix} Cov(\mathbf{x}_{1}, \mathbf{x}_{1}) & Cov(\mathbf{x}_{1}, \mathbf{x}_{2}) & \cdots & Cov(\mathbf{x}_{1}, \mathbf{x}_{n}) \\ Cov(\mathbf{x}_{2}, \mathbf{x}_{1}) & Cov(\mathbf{x}_{2}, \mathbf{x}_{2}) & \cdots & Cov(\mathbf{x}_{2}, \mathbf{x}_{n}) \\ \vdots & \vdots & \ddots & \vdots \\ Cov(\mathbf{x}_{n}, \mathbf{x}_{1}) & Cov(\mathbf{x}_{n}, \mathbf{x}_{2}) & \cdots & Cov(\mathbf{x}_{n}, \mathbf{x}_{n}) \end{pmatrix} = \frac{1}{n}\mathbf{X}^{T}\mathbf{X} \]ここで、k 次元に写像された特徴量に着目すると、その分散共分散行列は同様にして次のようにかける。
\[ \mathbf{\Sigma}_{\phi(\mathbf{X})} = \frac{1}{n}\phi(\mathbf{X})^{T}\phi(\mathbf{X}) \]カーネル行列
特徴量 X の分散共分散行列 Σ が与えられたとき、特徴量に対する主成分分析は、固有値問題に帰着される（証明）。
\[ \Sigma \mathbf{w} = \lambda \mathbf{w} \]Σ に k 次元へ写像後の特徴量の分散共分散行列を上式に代入すると、
\[ \frac{1}{n}\phi(\mathbf{X})^{T}\phi(\mathbf{X}) \mathbf{w} = \lambda \mathbf{w} \]これを w について解くと、
\[ \begin{eqnarray} \mathbf{w} &=& \frac{1}{\lambda n} \phi(\mathbf{X})^{T}\phi(\mathbf{X}) \mathbf{w} \\ &=& \lambda \phi(\mathbf{X})^{T} \left( \frac{\phi(\mathbf{X})\mathbf{w}}{\lambda ^{2} n} \right) \\ &=& \lambda \phi(\mathbf{X})^{T} \mathbf{a} \end{eqnarray} \]ここで、改めて \( \Sigma \mathbf{w} = \lambda \mathbf{w} \) に着目する。この式の左辺から w を消すと、
\[ \Sigma \mathbf{w} = \frac{1}{n}\phi(\mathbf{X})^{T}\phi(\mathbf{X}) \mathbf{w} = \frac{1}{n}\phi(\mathbf{X})^{T}\phi(\mathbf{X}) \lambda \phi(\mathbf{X})^{T} \mathbf{a} \]また、右辺から w を消すと、
\[ \lambda \mathbf{w} = \lambda^{2} \phi(\mathbf{X})^{T} \mathbf{a} \]以上により、\( \Sigma \mathbf{w} = \lambda \mathbf{w} \) について w のない形で書くと次のようになる。
\[ \frac{1}{n}\phi(\mathbf{X})^{T}\phi(\mathbf{X}) \lambda \phi(\mathbf{X})^{T} \mathbf{a} = \lambda^{2} \phi(\mathbf{X})^{T} \mathbf{a} \]両辺を λ で割り、左から φ(X) をかけると、次の式を得る。
\[ \frac{1}{n}\phi(\mathbf{X})\phi(\mathbf{X})^{T}\phi(\mathbf{X}) \phi(\mathbf{X})^{T} \mathbf{a} = \lambda \phi(\mathbf{X})\phi(\mathbf{X})^{T} \mathbf{a} \]これを計算すると、
\[ \frac{1}{n}\phi(\mathbf{X})\phi(\mathbf{X})^{T} \mathbf{a} = \lambda \mathbf{a} \]が得られる。新しい行列 K を用いて上式は次のようにかける。
\[ \frac{1}{n} \mathbf{K}\mathbf{a} = \lambda \mathbf{a} \] \[ \mathbf{K} = \phi(\mathbf{X})\phi(\mathbf{X})^{T} = \begin{pmatrix} \phi(\mathbf{x}^{(1)})\phi(\mathbf{x}^{(1)}) & \phi(\mathbf{x}^{(2)})\phi(\mathbf{x}^{(1)}) & \cdots & \phi(\mathbf{x}^{(n)})\phi(\mathbf{x}^{(1)}) \\ \phi(\mathbf{x}^{(1)})\phi(\mathbf{x}^{(2)}) & \phi(\mathbf{x}^{(2)})\phi(\mathbf{x}^{(2)}) & \cdots & \phi(\mathbf{x}^{(n)})\phi(\mathbf{x}^{(2)}) \\ \vdots & \vdots & \ddots & \vdots \\ \phi(\mathbf{x}^{(1)})\phi(\mathbf{x}^{(n)}) & \phi(\mathbf{x}^{(2)})\phi(\mathbf{x}^{(n)}) & \cdots & \phi(\mathbf{x}^{(n)})\phi(\mathbf{x}^{(n)}) \end{pmatrix} \]このとき、行列 K は各サンプルの写像後の特徴量同士の内積として表される。これをカーネル行列という。サンプルサイズが n のとき、カーネル行列 K は n 行 n 列の行列となる。また、カーネル行列の各要素を計算する際に利用するカーネル関数には以下のような関数がある。
| 多項式カーネル | \[ \phi(\mathbf{x}^{(i)})\phi(\mathbf{x}^{(j)}) = \left(\mathbf{x}^{(i)T}\mathbf{x}^{(j)}+c\right)^d \] |
| ガウスカーネル（RBF） | \[ \phi(\mathbf{x}^{(i)})\phi(\mathbf{x}^{(j)}) = \exp\left(-\frac{1}{2\sigma^2}||\mathbf{x}^{(i)}-\mathbf{x}^{(j)}||^2\right) \] |
| 双曲線正接カーネル | \[ \phi(\mathbf{x}^{(i)})\phi(\mathbf{x}^{(j)}) = \tanh\left(\eta \mathbf{x}^{(i)T}\mathbf{x}^{(j)} + c\right) \] |
カーネル主成分分析
カーネル行列の各成分が与えられると、
\[ \frac{1}{n}\mathbf{K} \mathbf{a} = \lambda \mathbf{a} \]これにより、カーネル主成分分析を行うにあたって、以下のような手順で行う。
- カーネル関数およびそのハイパーパラメーターを決めて、カーネル行列を計算する。
- カーネル関数によって写像された後の空間において、各特徴量の組み合わせでできた新しい特徴量の平均が 0 となっている保証がないために、カーネル行列を標準化（中心化）する。 \[\mathbf{K}' = \mathbf{K} - \mathbf{1}_{n}\mathbf{K} - \mathbf{K}\mathbf{1}_{n} + \mathbf{1}_{n}\mathbf{K}\mathbf{1}_{n} \]
- 固有値および固有ベクトルを計算する。この場合、n 個の固有値および固有ベクトルが求められるが、固有値の大きい順に並べて、最初の k の固有値および固有ベクトルを選ぶ。
scikit-learn によるカーネル主成分分析
次の例は、MNIST データに対して kernel PCA を使用して 5 次元まで次元削減を行う例である。
