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)}). \]

所以$^{(k)} ^2 = $.

此外，如果\(\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来进行数据压缩。