写在前面

介绍核主成分分析算法(Kernel Principal Component Analysis)^[1]

主成分分析

给定\(N\)个样本\(x_i \in \mathbb{R}^p\)，假设\(\sum_i x_i =0\)，样本的协方差矩阵为\(\Sigma=\frac{1}{N}\sum_i x_i x_i^T \in \mathbb{R}^{p \times p}\)，对其作特征值分解：

\[ \Sigma = U \Lambda U^T = \sum_k \lambda_k u_k u_k^T, UU^T = I_p \] 得到降维投影映射\(y_i = U_k^T x_i\)，其中\(U_k\in \mathbb{R}^{p\times k}\)为前\(k\)个特征列向量构成的子矩阵，显然

\[ \frac{1}{N}\sum_i y_i y_i^T = \frac{1}{N} \sum_i U_k^T x_i x_i^T U_k = U_k^T \Sigma U_k = U_k^T U \Lambda U^T U_k^T =\Lambda_k \] 其中\(\Lambda_k \in \mathbb{R}^{k \times k}\)为前\(k\)个最大的特征值构成的对角矩阵。记样本矩阵\(X=[x_1,x_2,\dots,x_N]\in \mathbb{R}^{p \times N}\)，以上问题可以用如下优化问题来概述

\[ \begin{aligned} &\min\limits_{U_k U_k^T = I_k} \sum_i \|x_i-{\mathcal{P}}_k(x_i)\|^2 \\ & = \min tr(X-{\mathcal{P}}_k(X))^T(X-{\mathcal{P}}_k(X))\\ & = \min tr(X^T(I-{\mathcal{P}}_k)^T(I-{\mathcal{P}}_k)Y)\\ & = \min tr(XX^T(I-{\mathcal{P}}_k)^2)\\ & = \min tr(XX^T(I-{\mathcal{P}}_k))\\ & = \min tr(XX^T) - tr(XX^T U_k U_k^T)\\ & = \max tr(U_k^T XX^T U_k)\\ & = \max tr(U_k^T \Sigma U_k) \\ & =\max tr(\Sigma_k)= \sum_{i=1}^k \lambda_k \end{aligned} \] 其中\({\mathcal{P}}_k = U_k U_k^T\)是到子空间的投影映射。此时\(U_k\)的最优解为前\(k\)个特征向量构成的列酉阵。

线性到非线性

核主成分分析

向量内积\(\langle a, b\rangle = a^T b\)，求解协方差矩阵的特征方程

\[ \lambda u = \Sigma u = (\frac{1}{N}\sum_i x_i x_i^T) u = \frac{1}{N}\sum_i \langle x_i, u \rangle x_i \]

• \[ \lambda \langle x_i, u\rangle = \langle x_i, \Sigma u\rangle \]

• \[ u = \sum_i \frac{\langle x_i,u \rangle}{\lambda N} x_i = \sum_i \alpha_i x_i \]

引入非线性映射\(\Phi :{\mathbb{R}^p \to F, x\mapsto X}\)，假设\(\sum_i \Phi(x_i)=0\)成立，否则可进行中心化处理\(\Phi(x_i)=\Phi(x_i)-\frac{1}{N}\sum_j \Phi(x_j)\)。对应协方差矩阵为

\[ \bar{\Sigma} = \frac{1}{N}\sum_i \Phi(x_i)\Phi(x_i)^T \] 对应特征值方程为\(\lambda U = \bar{\Sigma} U\)，表明特征向量位于\(\Phi(x_1),\cdots,\Phi(x_N)\)所张成的空间内，可得以下两个结论：

• \[ \lambda \langle \Phi(x_i), U\rangle = \langle\Phi(x_i), \bar{\Sigma} U\rangle \]

• \[ U = \sum_j \alpha_j \Phi(x_j) \]

可得

\[ \lambda \sum_j \alpha_j \langle \Phi(x_i), \Phi(x_j)\rangle = \frac{1}{N}\sum_{j,k} \alpha_j\langle\Phi(x_i), \Phi(x_k)\rangle \langle\Phi(x_k), \Phi(x_j)\rangle \] 令\(K_{ij} = \langle\Phi(x_i), \Phi(x_j)\rangle, \tilde{\lambda} = N \lambda\)，

\[ K \alpha = \tilde{\lambda}\alpha \] 由于特征向量的单位化，即\(U^T U = 1\)，可得

\[ \sum_{i,j} \alpha_i \alpha_j \langle\Phi(x_i), \Phi(x_j)\rangle = \alpha^T K \alpha = \tilde{\lambda} \alpha^T \alpha =1 \] 对于新的样本点\(t\)，特征空间对应点\(\Phi(t)\)的投影可表示为

\[ \langle U, \Phi(t)\rangle = \sum_j \alpha_j \langle \Phi(x_j), \Phi(t)\rangle = \sum_j \alpha_j K(x_j,t) \] ### 计算步骤

1. 计算矩阵\(K\)
2. 计算特征向量并归一化
3. 计算新的样本点对应的特征向量

核函数

不同核函数具有不同的意义，后面会专门写一个核方法、核技巧的总结。

Kernel PCA性质(继承于PCA)

• 前\(q\)个主成分比其他任意\(q\)个主成分表示的方差是最大的
• 前\(q\)个主成分比其他任意\(q\)个主成分表示的均方误差是最小的
• 主成分具有无关性
• 前\(q\)个主成分比其他任意\(q\)个主成分表示的互信息最多

参考文献

1. Scholkopf B, Smola A J, Muller K, et al. Nonlinear component analysis as a kernel eigenvalue problem[J]. Neural Computation, 1998, 10(5): 1299-1319. ↩︎