先看一眼PCA与KPCA的可视化区别:
在PCA算法是怎么跟协方差矩阵/特征值/特征向量勾搭起来的?里已经推导过PCA算法的小半部分原理.
本文假设你已经知道了PCA算法的基本原理和步骤.
从原始输入空间到特征空间
普通PCA算法的输入:
- 训练数据集\(D={x_1, \dots, x_m}\), \(x_i \in R^n\).
- 目标降维维度: \(d\)
- 新的测试数据\(x\)
Kernel PCA则需要在输入中加入一个指定的 kernel function \(\kappa\).
我们已经知道, 每个合法的 kernel function, 即对称和正半定的函数, 都能找到至少一个对应的feature mapping function \(\Phi\). 现在\(\kappa\)是已知的, \(\Phi\)是隐藏的:存在, 但对我们来说未知. 用\(\Phi\)把每个训练样本\(x_i\)映射到一个特征空间\(H\), 得到\(z_i\):
\[
z_i = \Phi(x_i)
\qquad
Z =
\left[
\begin{matrix}
z_1^T \\
z_2^T \\
\vdots \\
z_m^T
\end{matrix}
\right]
\]
均值化处理, 使每个维度的均值为0
均值向量:
\[
\mu = \frac 1m Z^T \left[\begin{matrix}1 \\ 1 \\ \vdots \\1\end{matrix}\right]_{m\times 1} = \frac 1m Z^T \beta
\]
从\(Z\)中每一行都减去\(\mu^T\):
\[
\bar Z = Z - \beta \mu^T = Z - \frac 1m \beta \beta^T Z
\]
协方差矩阵正交对角化
这一步有点绕.
因为协方差矩阵\(C = \bar Z^T \bar Z\)中有未知函数\(\Phi\), 所以没办法直接对角化. 在之前推导kernel svm和kernel linear regression算法的过程中, 我们都使用了kernel matrix:
\[
K =
\left [
\begin{matrix}
\Phi(x_1)^T \Phi(x_1), &\Phi(x_1)^T \Phi(x_2), &\dots &\Phi(x_1)^T \Phi(x_n) \\
\vdots &\dots &\dots &\vdots \\
\Phi(x_n)^T \Phi(x_1), &\Phi(x_n)^T \Phi(x_2), &\dots &\Phi(x_n)^T \Phi(x_n)
\end{matrix}
\right ]
\]
这次也不例外.
先看这个类似于\(K\)的均\(K\)矩阵:
\[
\bar K = \bar Z \bar Z^T
\]
假设\(\bar K\)有一个特征值\(\lambda\),对应的已规范化特征向量为\(u\):
\[
\bar Z \bar Z^T u = \lambda u
\]
两边同时左乘一个\(\bar Z^T\):
\[
\bar Z^T \bar Z \bar Z^T u = \bar Z^T\lambda u
\]
\[
\to C \bar Z^T u =\lambda \bar Z^Tu
\]
这代表\(\bar Z^T u\)是协方差矩阵\(C\)的特征向量, 对应的特征值也是\(\lambda\).
所以, 我们只需要规范正交对角化\(\bar K\), 就能对角化\(C\). 规范正交对角化操作的对象为:
\[
\bar K = \bar Z \bar Z^T = ( Z - \frac 1m \beta \beta^T Z)( Z^T - \frac 1m Z^T \beta \beta^T) = ZZ^T - \frac 1m \beta \beta^T ZZ^T - \frac 1m ZZ^T \beta \beta^T + \frac 1{m^2} \beta \beta^T ZZ^T \beta \beta^T = K - \frac 1m \beta \beta^T K - \frac 1m K\beta \beta^T + \frac 1{m^2} \beta \beta^T K \beta \beta^T
\]
特征向量规范化
由\(\bar K\)的规范化特征向量\(u\), 我们可以得到\(C\)的特征向量\(\bar Z^Tu\), 但它不一定是单位向量, 所以我们还要对它进行规范化处理.
\[
||u||^2 = u^T\bar Z \bar Z^Tu = u^T\lambda u = \lambda
\]
\[
p = \frac {\bar Z^Tu}{||\bar Z^Tu||} = \frac {\bar Z^Tu}{\sqrt \lambda}
\]
注意到了吧, 这里还是有\(\bar Z\)存在, 而\(\bar Z = Z - \frac 1m \beta \beta^T Z\), \(Z\)因为包含未知的\(\Phi\)所以也是未知的. 但是PCA的最终目的是降维, 会有一个输入向量\(x\), 到时又可与\(Z\)配合起来, 构成\(\kappa\).
对向量\(x\)进行降维操作
中间没写出来的步骤, 即特征值降序排列取前\(d\)个对应的特征向量, 与普通的PCA是一样的.
降维操作通过\(x\)在一个基上的投影操作即可说明.
\[
p^T\Phi(x) = \frac {u^T \bar Z \Phi(x)}{\sqrt \lambda} = \frac 1{\sqrt \lambda} u^T ( Z - \frac 1m \beta \beta^T Z) \Phi(x) = \frac 1{\sqrt \lambda} u^T (k - \frac 1m \beta \beta^T k) = \frac 1{\sqrt \lambda} u^T (I_{m \times m} - \frac 1m \beta \beta^T)k
\]
其中, \(\lambda\)与\(u\)分别是\(\bar K\)的特征值和对应的规范化特征向量,
\[
k =
\left [
\begin{matrix}
\kappa(x_1, x) \\
\kappa(x_2, x) \\
\vdots \\
\kappa(x_m, x) \\
\end{matrix}
\right]
\qquad
\beta = \left[\begin{matrix}1 \\ 1 \\ \vdots \\1\end{matrix}\right]_{m\times 1}
\]