Kernel PCA

机器学习

---

算法原理

部分数据在低维度线性不可分，但映射到高维度时就可以实现线性划分。通过使用核的技巧就可以实现映射$x_i \rightarrow \phi_{x_i}$，并在映射得到的新的特征空间进行主成分分析。

推导方法1[1]

推导建立在PCA的基础上的。需要先掌握PCA。

假设在特征空间数据的均值为：

$$\mu = \frac{1}{n} \sum _{i=1} ^n \phi(x_i)= 0$$

有方差：

$$C = \frac{1}{n} \sum _{i=1} ^n \phi(x_i) \phi(x_i)^ T$$

和PCA相类似， 特征向量为：

$$\begin{align} Cv = \lambda v \end{align}$$

因为不知道$\phi$的形式是怎么样的，并不能直接通过特征分解求$v$。

可以证明$v$可以表示成高维特征的线性组合

$$v_j = \sum _{i=1} ^n \alpha _{ji} \phi(x_i)$$

所以求特征向量等价于求因子$\alpha_{ji}$

通过将$C, v$的表达式代入(1)中可以得到：

$$\begin{align}K \alpha_j = n \lambda_j \alpha_j \end{align}$$

其中$K$是一个核函数，$k(x_i, x_j) = \phi (x_i)^T \phi (x_i), K \neq C$对于特定的数据，可认为是已知的。由(2) $\alpha _j$是$K$的特征向量， 下面求其约束。注意这里并不是要求其长度为1。 特征向量$v_j$是一个单位向量,
由

$$v_j^T v_j = 1$$

代入$v_j$有

$$\sum _{k=1} ^n \sum _{l=1} ^n \alpha _{jl} \alpha _{jk} \phi(x_l)^T \phi(x_k)= 1$$

即

$$\alpha _j ^T K \alpha _j = 1$$

代入(2)得到

$$\lambda _j n \alpha _j ^T \alpha _j = 1 , \forall j$$

以上就是其长度约束。

对于新的数据x，它在主成分的投影坐标为

$$\phi (x)^T v_j = \sum _{i=1} ^n \alpha _{ji} \phi (x)^T \phi (x_i) = \sum _{i=1} ^n \alpha _{ji}K(x, x_j)$$

由以上投影坐标可以求。

---

一般情况下，特征空间的均值不是0。可以将特征中心化。

$$\hat \phi (x_i) = \phi(x_i) - \frac{1}{n} \sum _{k=1} ^n \phi(x_k)$$

相应的核也变成了

$$\hat K(x_i, x_j) = K(x_i, x_j) - \frac{1}{n} \sum _{k=1} ^n K(x_i, x_k) - \frac{1}{n} \sum _{k=1} ^n K(x_j, x_k)+ \frac{1}{n^2} \sum _{l= 1, k=1} ^n K(x_l, x_k)$$

矩阵形式：

$$\hat K (x_i , x_j) = K - 2 1_{1/n}K + 1 _{1/n }K 1_{1/n}$$

$1_{1/n}$表示所有元素为1的矩阵。

---

KPCA的算法流程
1. 选择一个核
2. 由(3)建立一个归一化核矩阵
3. 求特征值分解

$$\hat K \alpha _i = \lambda _i \alpha _i$$
4. 对于新的数据点在主成分的投影为
$$y_i = \sum _{i=1} ^n \alpha _{ji}K(x, x_i), j = 1, ···d$$

推导方法2[2]

假设数据均值为0时，有协方差矩阵，

$$C = \frac{1}{n}X^T X = \frac{1}{N} \begin{bmatrix} \phi(x_1),...\phi(x_n) \end{bmatrix} \begin{bmatrix} \phi(x_1)^T \\ \vdots \\ \phi(x_n)^T \end{bmatrix}$$

$X$认为是数据在特征空间的表示。因为不知道$\phi$的形式，所以希望转换成可以用kernel K表示形式

$$K = X X^T = \begin{bmatrix} \phi(x_1)^T \phi(x_1) & \dots & \phi(x_1)^T \phi(x_n)\\ \vdots & \dots & \vdots\\ \phi(x_n)^T\phi(x_1) & \dots & \phi(x_n)^T \phi(x_n)\end{bmatrix} \\= \begin{bmatrix} \kappa(x_1, x_1) & \dots & \kappa(x_1, x_n) \\ \vdots & \dots & \vdots\\ \kappa(x_n, x_1) & \dots & \kappa(x_n, x_n) \end{bmatrix}$$

从kernel矩阵的特征方程(逆向推理)出发：

$$X X^T u = \lambda u$$

两边左乘$X^T$，整理得到

$$X^T X (X^T u) = \lambda (X^T u)$$

可以看出$X^T u$是$C$的特征向量，因为其受到其为单位向量的约束，有：

$$v = \frac{1}{||X^T u||}X^T u = \frac{1}{\sqrt{u ^T X X^T u}}X^T u \\ =\frac{1}{\sqrt{u^T \lambda u}}X^T u = \frac{1}{\sqrt{ \lambda}}X^T u$$

这里令$u$也是单位向量。特征向量还是和$X$直接相关，仍然是未知的。

直接考虑在特征空间投影之后的坐标(高中向量知识)：

$$v ^T \phi(x') = (\frac{1}{\sqrt{ \lambda}}X^T u)^T \phi(x') = \frac{1}{\sqrt{ \lambda}}u^T X \phi(x') \\ = \frac{1}{\sqrt{ \lambda}}u^T \begin{bmatrix} \phi(x_1)^T \\ \vdots \\ \phi(x_n)^T \end{bmatrix} \phi(x') = \frac{1}{\sqrt{ \lambda}}u^T \begin{bmatrix} \kappa(x_1, x') \\ \vdots \\ \kappa(x_n, x') \end{bmatrix}$$

最想要知道的正好是可以计算的。

---

题外话
特征空间的向量$v$可以用特征空间的数据线性表示。因为

$$v=\frac{1}{\sqrt{ \lambda}}X^T u = \frac{1}{\sqrt{ \lambda}}\begin{bmatrix} \phi(x_1),...\phi(x_n) \end{bmatrix} u \\ = \frac{1}{\sqrt{ \lambda}} \sum _{i=1} ^n u_i \phi(x_i) = \sum_{i=1} ^n \alpha_i \phi(x_i)$$

---

KPCA的算法流程
1. 选择一个核
2. 建立一个归一化核矩阵
3. 求特征值分解

$$K u = \lambda u$$
4. 对于新的数据点在主成分的投影为
$$v= \frac{1}{\sqrt{ \lambda}}u^T \begin{bmatrix} \kappa(x_1, x') \\ \vdots \\ \kappa(x_n, x') \end{bmatrix}$$

参考文献

[1]. http://www.cs.haifa.ac.il/~rita/uml_course/lectures/KPCA.pdf
[2]. https://www.youtube.com/watch?v=G2NRnh7W4NQ