【机器学习基础】第四十一课:[降维与度量学习]核化线性降维

核主成分分析(KPCA)

Posted by x-jeff on November 29, 2022

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的,然而,在不少现实任务中,可能需要非线性映射才能找到恰当的低维嵌入。图10.6给出了一个例子,样本点从二维空间中的矩形区域采样后以S形曲面嵌入到三维空间,若直接使用线性降维方法对三维空间观察到的样本点进行降维,则将丢失原本的低维结构。为了对“原本采样的”低维空间与降维后的低维空间加以区别,我们称前者为“本真”(intrinsic)低维空间。

数据分布不是线性的,当初SVM也遇到了这个问题,其解决办法为把数据映射到高维空间,在高维空间这些数据就是线性的了,然后我们就可以用上只能处理线性分布数据的PCA来进行降维了。这套思路其实就是核主成分分析(Kernelized PCA,简称KPCA)。KPCA是非线性降维的一种常用方法,是基于核技巧对线性降维方法进行“核化”(kernelized)。

假定我们将在高维特征空间中把数据投影到由$\mathbf{W}$确定的超平面上,即PCA欲求解:

\[\left( \sum_{i=1}^m \mathbf{z}_i \mathbf{z}_i^T \right) \mathbf{W} = \lambda \mathbf{W} \tag{1}\]

其中$\mathbf{z}_i$是样本点$\mathbf{x}_i$在高维特征空间中的像。易知:

\[\begin{align} \mathbf{W} &= \frac{1}{\lambda} \left( \sum_{i=1}^m \mathbf{z}_i \mathbf{z}_i^T \right) \mathbf{W} \\&= \sum_{i=1}^m \mathbf{z}_i \frac{\mathbf{z}_i^T \mathbf{W}}{\lambda} \\&= \sum_{i=1}^m \mathbf{z}_i \mathbf{\alpha}_i \end{align} \tag{2}\]

其中$\mathbf{\alpha}_i = \frac{1}{\lambda} \mathbf{z}_i^T \mathbf{W}$。假定$\mathbf{z}_i$是由原始属性空间中的样本点$\mathbf{x}_i$通过映射$\phi$产生,即$\mathbf{z}_i = \phi (\mathbf{x}_i),i=1,2,…,m$。若$\phi$能被显式表达出来,则通过它将样本映射至高维特征空间,再在(高维)特征空间中实施PCA即可。式(1)变换为:

\[\left( \sum_{i=1}^m \phi(\mathbf{x}_i) \phi(\mathbf{x}_i)^T \right) \mathbf{W} = \lambda \mathbf{W} \tag{3}\]

式(2)变换为:

\[\mathbf{W} = \sum_{i=1}^m \phi (\mathbf{x}_i) \mathbf{\alpha_i} \tag{4}\]

一般情形下,我们不清楚$\phi$的具体形式,于是引入核函数

\[\kappa (\mathbf{x}_i, \mathbf{x}_j) = \phi (\mathbf{x}_i)^T \phi (\mathbf{x}_j) \tag{5}\]

将式(4)和(5)代入式(3)后化简。先看式(3)的左侧:

\[\begin{align} \left( \sum_{i=1}^m \phi(\mathbf{x}_i) \phi(\mathbf{x}_i)^T \right) \mathbf{W} &= \left( \sum_{i=1}^m \phi(\mathbf{x}_i) \phi(\mathbf{x}_i)^T \right) \sum_{j=1}^m \phi (\mathbf{x}_j) \mathbf{\alpha_j} \\&= \left(\phi(\mathbf{x}_1) \phi(\mathbf{x}_1)^T + \phi(\mathbf{x}_2) \phi(\mathbf{x}_2)^T + ... + \phi(\mathbf{x}_m) \phi(\mathbf{x}_m)^T \right) \left( \phi(\mathbf{x}_1)\mathbf{\alpha_1} + \phi(\mathbf{x}_2)\mathbf{\alpha_2} + ... + \phi(\mathbf{x}_m)\mathbf{\alpha_m} \right) \\&= \left(\phi(\mathbf{x}_1) \kappa(\mathbf{x}_1,\mathbf{x}_1) + \phi(\mathbf{x}_2) \kappa(\mathbf{x}_2,\mathbf{x}_1) + ... + \phi(\mathbf{x}_m) \kappa(\mathbf{x}_m,\mathbf{x}_1) \right) \mathbf{\alpha}_1 + \\& \quad \left(\phi(\mathbf{x}_1) \kappa(\mathbf{x}_1,\mathbf{x}_2) + \phi(\mathbf{x}_2) \kappa(\mathbf{x}_2,\mathbf{x}_2) + ... + \phi(\mathbf{x}_m) \kappa(\mathbf{x}_m,\mathbf{x}_2) \right) \mathbf{\alpha}_2 + \\& \quad ... \\& \quad \left(\phi(\mathbf{x}_1) \kappa(\mathbf{x}_1,\mathbf{x}_m) + \phi(\mathbf{x}_2) \kappa(\mathbf{x}_2,\mathbf{x}_m) + ... + \phi(\mathbf{x}_m) \kappa(\mathbf{x}_m,\mathbf{x}_m) \right) \mathbf{\alpha}_m \\& = \phi(\mathbf{x}_1) \left( \kappa(\mathbf{x}_1,\mathbf{x}_1) \mathbf{\alpha}_1 + \kappa(\mathbf{x}_1,\mathbf{x}_2) \mathbf{\alpha}_2 + ... + \kappa(\mathbf{x}_1,\mathbf{x}_m) \mathbf{\alpha}_m \right) + \\& \quad \phi(\mathbf{x}_2) \left( \kappa(\mathbf{x}_2,\mathbf{x}_1) \mathbf{\alpha}_1 + \kappa(\mathbf{x}_2,\mathbf{x}_2) \mathbf{\alpha}_2 + ... + \kappa(\mathbf{x}_2,\mathbf{x}_m) \mathbf{\alpha}_m \right) + \\& \quad ... \\& \quad \phi(\mathbf{x}_m) \left( \kappa(\mathbf{x}_m,\mathbf{x}_1) \mathbf{\alpha}_1 + \kappa(\mathbf{x}_m,\mathbf{x}_2) \mathbf{\alpha}_2 + ... + \kappa(\mathbf{x}_m,\mathbf{x}_m) \mathbf{\alpha}_m \right) \\&= \begin{bmatrix} \phi(\mathbf{x}_1) & \phi(\mathbf{x}_2) & \cdots & \phi(\mathbf{x}_m) \end{bmatrix} \begin{bmatrix} \kappa(\mathbf{x}_1,\mathbf{x}_1) & \kappa(\mathbf{x}_1,\mathbf{x}_2) & \cdots & \kappa(\mathbf{x}_1,\mathbf{x}_m) \\ \kappa(\mathbf{x}_2,\mathbf{x}_1) & \kappa(\mathbf{x}_2,\mathbf{x}_2) & \cdots & \kappa(\mathbf{x}_2,\mathbf{x}_m) \\ \vdots & \vdots & \ddots & \vdots \\ \kappa(\mathbf{x}_m,\mathbf{x}_1) & \kappa(\mathbf{x}_m,\mathbf{x}_2) & \cdots & \kappa(\mathbf{x}_m,\mathbf{x}_m) \end{bmatrix} \begin{bmatrix} \mathbf{\alpha}_1 \\ \mathbf{\alpha}_2 \\ \vdots \\ \mathbf{\alpha}_m \end{bmatrix} \\&= \begin{bmatrix} \phi(\mathbf{x}_1) & \phi(\mathbf{x}_2) & \cdots & \phi(\mathbf{x}_m) \end{bmatrix} \mathbf{K} \mathbf{A} \end{align} \tag{6}\]

然后看式(3)的右侧:

\[\begin{align} \lambda \mathbf{W} &= \lambda \sum_{i=1}^m \phi (\mathbf{x}_i) \mathbf{\alpha_i} \\&= \lambda \begin{bmatrix} \phi(\mathbf{x}_1) & \phi(\mathbf{x}_2) & \cdots & \phi(\mathbf{x}_m) \end{bmatrix} \begin{bmatrix} \mathbf{\alpha}_1 \\ \mathbf{\alpha}_2 \\ \vdots \\ \mathbf{\alpha}_m \end{bmatrix} \\&=\begin{bmatrix} \phi(\mathbf{x}_1) & \phi(\mathbf{x}_2) & \cdots & \phi(\mathbf{x}_m) \end{bmatrix} \lambda \mathbf{A} \end{align} \tag{7}\]

由于我们的目标是求出$\mathbf{W}$,即等价于求出$\mathbf{A}$使得式(6)等于式(7),显然,如果满足式(8)的话,那么式(6)肯定是等于式(7)的,因此,问题转化为通过式(8)求解$\mathbf{A}$:

\[\mathbf{KA} = \lambda \mathbf{A} \tag{8}\]

其中,$\mathbf{K}$为核矩阵。很明显,式(8)是特征值分解问题,取$\mathbf{K}$最大的$d’$个特征值对应的特征向量即可。

对新样本$\mathbf{x}$:

\[\begin{align} \mathbf{z}' &= \mathbf{W}^T \phi(\mathbf{x}) \\&= \sum_{i=1}^m \mathbf{\alpha}_i^T \phi (\mathbf{x}_i)^T \phi(\mathbf{x}) \\&= \sum_{i=1}^m \mathbf{\alpha}_i^T \kappa(\mathbf{x}_i,\mathbf{x}) \end{align} \tag{9}\]

从式(9)可以看出,为获得降维后的坐标,KPCA需对所有样本求和,因此它的计算开销较大。

2.参考资料

  1. 核化线性降维(KPCA)的理解