Learning From Data——Kernel PCA

Posted on Edited on In

上次说了几个PCA的局限性，其中有一个是它只找各个特征之间的线性关系。如何拓展线性关系到非线性，似乎有点思路，因为之前SVM中说过，可以通过kernel将SVM拓展到非线性的分类。同样通过kernel，我们也可以找到特征之间的非线性关系，从而利用PCA进行数据压缩等操作。

对于线性的PCA的扩展，就是将PCA映射到更高维度的空间,使其在更高维度的空间有线性关系：$\phi:\mathbb{R}^n \rightarrow \mathbb{R}^d,d\ge n$.而如何映射，通过一个kernel函数来定义：$k(X_i,X_j) = \phi(X_i)^T\phi(X_j)$或者kernel矩阵$K \in \mathbb{R}^{m \times m}$. 映射完成后，我们就可以在更高维度的空间再使用标准的PCA算法了。不过这个想法是naive的，比如高斯核函数，是映射到无限维度，如果用原来的PCA去求，是不现实的。而且，从下面的分析可以看到，直接求也用不到kernel函数的方便之处。

映射后的数据的协方差矩阵如下：
$$
\Sigma = \frac 1 m \sum_{i=1}^m \phi(X_i) \phi(X_i)^T \in \mathbb{R}^{d\times d}
$$

假如$(\lambda_k,v_k),k=1,…,d$为$\sigma$的特征分解，则：
$$
\Sigma v_k = \lambda_k v_k
$$

则原来$X_l$的在第k个主要成分的投影为：$\phi(X_l)^Tv_k$.

到目前位置，我们都没有用到kernel。$\phi(X_i)$是难以计算的，而kernel是容易计算的。因此如何避免$\phi_(X_i)$的计算？

首先我们知道：
$$
\begin{align}
\Sigma v_k = \left (\sum_{i=1}^m \phi(X_i) \phi(X_i)^T \right ) v_k = \lambda _k v_k
\end{align}
$$

实际上，我们可以将$v_k$写成$\phi(X_i)^T$的组合（这个很像是之前的kernel logistic regression用的trick），这里就不证明为什么一定可以写成这个组合了，我觉得应该会用到线性代数的秩的知识。
$$
v_k = \sum_{i = 1} ^m \alpha_i^{(k)} \phi(X_i)
$$

那么，之前提到的投影可以将上式带入：
$$
\begin{aligned}
\phi(X_l)^Tv_k &= \phi(X_l)^T \sum_{i = 1} ^m \alpha_i^{(k)} \phi(X_i)\
&= \sum_{i=1} ^m \alpha_i^{(k)} \phi(X_l)^T\phi(X_i)\
&= \sum_{i=1} ^m \alpha_i^{(k)} k(X_l,X_i)
\end{aligned}
$$

这又引入了一个问题：如何得到$\alpha_i^{(k)}$?

将$v_k = \sum_{i = 1} ^m \alpha_i^{(k)} \phi(X_i)$带入(1)式,我们得到：
$$
\left[\sum_{i=1}^m \phi(X_i) \phi(X_i)^T \right] \left(\sum_{i=1}^m \alpha_i^{(k)} \phi(X_i) \right) = \lambda_k m \left(\sum_{i=1}^m \alpha_i^{(k)} \phi(X_i) \right)\
\Phi(X)^T \Phi(X) \Phi(X)^T \alpha^{(k)} = \lambda_k m \Phi(X)^T \alpha^{(k)}\
\Phi(X) \Phi(X)^T \alpha^{(k)} = \lambda_k m \alpha^{(k)}\
K \alpha^{(k)} = \lambda_k m \alpha_k,
$$
上式中：
$$
\alpha ^{(k)} = \begin{bmatrix}
a_1^{(k)}\
\vdots\
a_m^{(k)}
\end{bmatrix};\Phi(X) = \begin{bmatrix}
\phi(X_1)^T\
\vdots\
\phi(X_m)^T
\end{bmatrix} \
K = \begin{bmatrix}
k(X_1,X_1)&k(X_1,X_2)&\cdots&k(X_1,X_m)\
k(X_2,X_1)&k(X_2,X_2)&\cdots&k(X_2,X_m)\
\vdots&\vdots\ &\ddots&\vdots\
k(X_m,X_1)&k(X_m,X_2)&\cdots&k(X_m,X_m)
\end{bmatrix}
$$

上式中$\alpha^{(k)}$可以通过求解K的特征向量得到，而K是kernel矩阵。

我们希望正交化$\alpha^{(k)}$，使得$v_k^Tv_k = 1$（与之前的标准PCA一致）.
$$
v_k^T v_k = (\alpha^{(k)})^T \Phi(X) \Phi(X)^T \alpha^{(k)} = \lambda_k m ((\alpha^{(k)})^T \alpha^{(k)}).
$$

所以$\Vert \alpha^{(k)} \Vert^2 = \frac{1}{\lambda_k m} $.

此外，如果$\mathbb{E}(\phi(X)) \ne 0$，我们还需要中心化$\phi(X)$:
$$
\tilde{\phi}(X_i) = \phi(X_i) - \frac 1 m \sum_{l=1}^m \phi(X_i)
$$

而中心化以后的kernel矩阵为：
$$
\tilde{k}(i,j) = \tilde{\phi}(X_i)^T \tilde{\phi}(X_j)
$$

写成矩阵就是：
$$
\tilde{K} = K -1_m K - K 1_m + 1_mK1_m
$$

其中：
$$
1_m = \begin{bmatrix}
\frac 1 m & \cdots &\frac 1 m\
\vdots & \ddots & \vdots\
\frac 1 m & \cdots &\frac 1 m
\end{bmatrix} \in \mathbb{R}^{m\times m}
$$

我们从前面已经推导出来，计算kernel PCA的$v_k$最终需要的是kernel矩阵，因此使用$\tilde{K}$去计算PCA即可。

２个问题：

  1. 之前的X不光是中心化的，而且还是Stdev(X) = 1,在kernel PCA中没有考虑这一点吗？

对于kernel PCA的标准协方差分析是非常困难的。不过协方差的意义在于使得数据范围不会变动过大（如身高ｍ为单位，变化程度可能是１以内，而体重以斤为单位，变化范围为几十），因此如果对原数据进行协方差变0的操作后，假设kernel是对称的，它们的变化范围不会差得过多。

  1. $ａ^{(k)}$算出来有ｍ个，但是我们不一定把它映射到ｍ维度的空间了。不像原来的PCA，ｎ维有ｎ个特征向量？

一般来说我们升维时候都会升到无限维度，很少有比ｍ小的。这时候它的特征向量个数就受到了数据个数的限制。如果维度比ｍ小，则特征向量不会真正达到ｍ个。

总结以下，kernel PCA的步骤：

  1. 求出Ｋ

  2. 求出$\tilde{K}$

  3. 求出上面的特征值和特征向量，并且根据使得特征向量的长度等于$\frac {1}{\sqrt{\lambda_k m} }$，其中$\lambda_km$也就是对应的特征值。

  4. 根据求得的特征向量，求得$v_k$.

Kernel PCA的例子：

kernel PCA经常用于聚类，异常检测等等。它需要找到$m \times m$的特征向量来代替$n \times n$。通过投影到k维主子空间进行降维通常是不可能的，也就是一般不用kernel PCA来进行数据压缩。