Principal Component Analysis

主成分分析

主成分分析 (PCA) 是一种数据降维方法，可以从两种角度推导——最大化投影方差或最小化重构误差。

首先引入记号。设数据集为 $\{{\mathbf{x}}_n{\}}_{n=1}^N$，其中 ${\mathbf{x}}_n\in {\mathbb{R}}^d$，也可记作矩阵形式： $$\mathbf{X}=\left[\begin{array}{c}{\mathbf{x}}_1^T\\ ⋮\\ {\mathbf{x}}_N^T\end{array}\right]\in {\mathbb{R}}^{N\times d}$$ 不失一般性地，我们假设数据的均值为 $0$，否则可以事先进行中心化。于是有样本协方差矩阵： $$\mathbf{S}=\frac{1}{N}\sum _{n=1}^N{\mathbf{x}}_n{\mathbf{x}}_n^T=\frac{1}{N}{\mathbf{X}}^T\mathbf{X}\in {\mathbb{R}}^{d\times d}$$ 显然 $\mathbf{S}$ 是一个对称阵，即 ${\mathbf{S}}^T=\mathbf{S}$. 我们将看到，PCA 的本质其实就是求解 $\mathbf{S}$ 的特征值与特征向量。

角度一·最大化投影方差

为了降维，我们考虑将数据点投影到一个 $r$ 维子空间中，其中 $r<d$. 降维必然会导致信息损失，为了尽可能少地损失信息，我们希望投影后的数据在各个维度上的方差尽可能大。

首先考虑一维情形。设投影空间的基向量为 ${\mathbf{u}}_1\in {\mathbb{R}}^d$，满足 ${\mathbf{u}}_1^T{\mathbf{u}}_1=1$，则每个 ${\mathbf{x}}_n$ 将被投影为 ${\mathbf{u}}_1^T{\mathbf{x}}_n$. 投影后数据的样本均值仍为 $0$，而样本方差为： $$\frac{1}{N}\sum _{n=1}^N{\left({\mathbf{u}}_1^T{\mathbf{x}}_n\right)}^2={\mathbf{u}}_1^T\mathbf{S}{\mathbf{u}}_1$$ 于是优化问题为： $$\begin{array}{rl}\underset{{\mathbf{u}}_1}{max}& {\mathbf{u}}_1^T\mathbf{S}{\mathbf{u}}_1\\ \text{s.t.}& {\mathbf{u}}_1^T{\mathbf{u}}_1=1\end{array}$$ 引入拉格朗日乘子 ${\lambda }_1$，构建拉格朗日函数： $$L({\mathbf{u}}_1,{\lambda }_1)={\mathbf{u}}_1^T\mathbf{S}{\mathbf{u}}_1+{\lambda }_1(1-{\mathbf{u}}_1^T{\mathbf{u}}_1)$$ 对 ${\mathbf{u}}_1$ 求导并令为零，可得： $$\frac{\partial L}{\partial {\mathbf{u}}_1}=2\mathbf{S}{\mathbf{u}}_1-2{\lambda }_1{\mathbf{u}}_1=\mathbf{0}⟹\mathbf{S}{\mathbf{u}}_1={\lambda }_1{\mathbf{u}}_1$$ 这说明 ${\lambda }_1,{\mathbf{u}}_1$ 正是 $\mathbf{S}$ 的特征值和特征向量。代入优化目标： $${\mathbf{u}}_1^T\mathbf{S}{\mathbf{u}}_1={\lambda }_1{\mathbf{u}}_1^T{\mathbf{u}}_1={\lambda }_1$$ 因此，为了使得优化目标最大，${\lambda }_1$ 应取 $\mathbf{S}$ 的最大特征值，${\mathbf{u}}_1$ 为对应的特征向量，称作第一个主成分。

对于更多维的情形，我们以增量的方式定义下一个主成分，并要求新的主成分与已求得的主成分正交。例如，对于第二个主成分 ${\mathbf{u}}_2$，优化问题写作： $$\begin{array}{rl}\underset{{\mathbf{u}}_2}{max}& {\mathbf{u}}_2^T\mathbf{S}{\mathbf{u}}_2\\ \text{s.t.}& {\mathbf{u}}_1^T{\mathbf{u}}_2=0,{\mathbf{u}}_2^T{\mathbf{u}}_2=1\end{array}$$ 引入拉格朗日乘子 ${\lambda }_2,{\lambda }_{12}$，构建拉格朗日函数： $$L({\mathbf{u}}_2,{\lambda }_2,{\lambda }_{12})={\mathbf{u}}_2^T\mathbf{S}{\mathbf{u}}_2+{\lambda }_2(1-{\mathbf{u}}_2^T{\mathbf{u}}_2)-{\lambda }_{12}{\mathbf{u}}_1^T{\mathbf{u}}_2$$ 对 ${\mathbf{u}}_2$ 求导并令为零，可得： $$\frac{\partial L}{\partial {\mathbf{u}}_2}=2\mathbf{S}{\mathbf{u}}_2-2{\lambda }_2{\mathbf{u}}_2-{\lambda }_{12}{\mathbf{u}}_1=0$$ 上式左乘 ${\mathbf{u}}_1^T$ 得： $$2{\mathbf{u}}_1^T\mathbf{S}{\mathbf{u}}_2-2{\lambda }_2{\mathbf{u}}_1^T{\mathbf{u}}_2-{\lambda }_{12}{\mathbf{u}}_1^T{\mathbf{u}}_1=0-0-{\lambda }_{12}=0$$ 其中第一项等于零是因为 ${\mathbf{u}}_1^T\mathbf{S}{\mathbf{u}}_2=(\mathbf{S}{\mathbf{u}}_1{)}^T{\mathbf{u}}_2={\lambda }_1{\mathbf{u}}_1^T{\mathbf{u}}_2=0$. 将 ${\lambda }_{12}=0$ 代回，我们得到： $$\mathbf{S}{\mathbf{u}}_2={\lambda }_2{\mathbf{u}}_2$$ 这说明 ${\lambda }_2,{\mathbf{u}}_2$ 也是 $\mathbf{S}$ 的特征值和特征向量。代入优化目标： $${\mathbf{u}}_2^T\mathbf{S}{\mathbf{u}}_2={\lambda }_2{\mathbf{u}}_2^T{\mathbf{u}}_2={\lambda }_2$$ 于是，为了让优化目标最大，${\lambda }_2$ 应取 $\mathbf{S}$ 的次大特征值，${\mathbf{u}}_2$ 为对应的特征向量，称作第二个主成分。

以此类推，我们可以得到结论：第 $r$ 个主成分就是 $\mathbf{S}$ 第 $r$ 大的特征值所对应的特征向量。

角度二·最小化重构误差

第二个推导角度的出发点是在一个 $r(r<d)$ 维的线性子空间中近似表示数据，并希望近似的误差最小。具体而言，设 $r$ 维子空间的一组正交基为 $({\mathbf{u}}_1,\dots ,{\mathbf{u}}_r)$，其中 ${\mathbf{u}}_i\in {\mathbb{R}}^d$，则该子空间中的任一点可唯一表示为： $${\tilde{\mathbf{x}}}_n=\sum _{i=1}^r{\gamma }_{ni}{\mathbf{u}}_i$$ 其中 ${\gamma }_{n1},\dots ,{\gamma }_{nr}$ 是表示系数。将这组基扩充为 ${\mathbb{R}}^d$ 中的完备正交基 $({\mathbf{u}}_1,\dots ,{\mathbf{u}}_d)$，那么每个 ${\mathbf{x}}_n$ 在这组基下都有唯一的线性表示： $${\mathbf{x}}_n=\sum _{i=1}^d{\alpha }_{ni}{\mathbf{u}}_i=\sum _{i=1}^d({\mathbf{x}}_n^T{\mathbf{u}}_i){\mathbf{u}}_i$$ 其中 ${\alpha }_{ni}={\mathbf{x}}_n^T{\mathbf{u}}_i$ 是表示系数。于是，重构误差写作： $$J=\frac{1}{N}\sum _{n=1}^N\Vert {\mathbf{x}}_n-{\tilde{\mathbf{x}}}_n{\Vert }^2=\frac{1}{N}\sum _{n=1}^N{\Vert \sum _{i=1}^r({\mathbf{x}}_n^T{\mathbf{u}}_i-{\gamma }_{ni}){\mathbf{u}}_i+\sum _{i=r+1}^d({\mathbf{x}}_n^T{\mathbf{u}}_i){\mathbf{u}}_i\Vert }^2$$ 对 ${\gamma }_{ni}$ 求导并令为零，解得： $${\gamma }_{ni}={\mathbf{x}}_n^T{\mathbf{u}}_i$$ 于是优化目标简化为： $$\begin{array}{rl}J& =\frac{1}{N}\sum _{n=1}^N{\Vert \sum _{i=r+1}^d\left({\mathbf{x}}_n^T{\mathbf{u}}_i\right){\mathbf{u}}_i\Vert }^2\\ & =\frac{1}{N}\sum _{n=1}^N{\left[\sum _{i=r+1}^d\left({\mathbf{x}}_n^T{\mathbf{u}}_i\right){\mathbf{u}}_i\right]}^T\left[\sum _{j=r+1}^d\left({\mathbf{x}}_n^T{\mathbf{u}}_j\right){\mathbf{u}}_j\right]\\ & =\frac{1}{N}\sum _{n=1}^N\sum _{i=r+1}^d{\left({\mathbf{x}}_n^T{\mathbf{u}}_i\right)}^2\\ & =\sum _{i=r+1}^d{\mathbf{u}}_i^T\mathbf{S}{\mathbf{u}}_i\end{array}$$ 至此，我们的优化问题变成了： $$\begin{array}{rl}\underset{\{{\mathbf{u}}_i\}}{min}& \sum _{i=r+1}^d{\mathbf{u}}_i^T\mathbf{S}{\mathbf{u}}_i\\ \text{s.t.}& {\mathbf{u}}_i^T{\mathbf{u}}_i=1\\ & {\mathbf{u}}_i^T{\mathbf{u}}_j=0,i\ne j\end{array}$$ 这与上一节得到的优化问题是类似的，只不过这里是最小化，因此解就是 $\mathbf{S}$ 最小的 $d-r$ 个特征值对应的特征向量。相应地，${\mathbf{u}}_1,\dots ,{\mathbf{u}}_r$ 张成的空间就是 $\mathbf{S}$ 最大的 $r$ 个特征值对应的特征向量张成的空间，因此直接取 $$ 为 $$ 最大的 $$ 个特征值对应的特征向量即可。

计算上的考量

通过上面两小节的推导，我们发现 PCA 就是要求解样本协方差矩阵 $$ 的前 $$ 大的特征值与对应的特征向量。然而众所周知，求解特征值与特征向量并不是一件容易的事，所以我们会有一些计算上的考量。

首先，我们最好保证数据在各个维度上的取值范围差不多，否则 PCA 的解将偏向于取值范围大的维度，因为它们具有更大的方差。因此实践中我们最好对数据进行标准化，而非仅仅中心化。等价地，这相当于我们用相关矩阵、而非协方差矩阵去求解。

其次，在高维度场景下，即 $$ 时，为了节省计算量，我们可以求解 Gram 矩阵 $$ 的特征值与特征向量而非协方差矩阵 $$ 的特征值与特征向量。这是因为矩阵论的知识告诉我们，$$ 与 $$ 有着相同的非零特征值，并且特征向量也有简单的变换关系。具体而言，假设 $$ 的特征值分解为： $$ 其中 $$ 是特征向量构成的矩阵，$$ 是特征值构成的对角阵。那么左乘 $$ 得： $$ 这说明 $$ 的特征值也是 $$，而特征向量构成的矩阵为 $$. 我们将会看到，这种计算方式也让我们能够在 PCA 中用上核技巧。

最后，根据特征值与奇异值的关系，求解 $$ 的特征值与特征向量，其实等价于求解 $$ 的奇异值与右奇异向量。具体而言，设有奇异值分解 $$，那么： $$ 所以我们直接求解 $$ 最大的 $$ 个奇异值对应的右奇异向量即可。

核主成分分析

在 SVM 和 RKHS 中，我们介绍了核技巧及其在 SVM 中的应用。自然地可以想到，核技巧也可以用在 PCA 中。具体而言，设有非线性映射 $$ 将数据点 $$ 映射为特征 $$，其中 $$ 可以是无穷。设核函数为 $$，满足： $$ 考虑在特征空间中实施 PCA，那么这就相当于在数据空间中做了非线性的主成分分析。

我们暂时假设映射后特征的均值依旧是 $$，则特征空间中的样本协方差矩阵为： $$ 不过，为了使用上核技巧，我们需要的是 $$ 而非 $$. 好在根据前文的讨论，求解 $$ 的特征值与特征向量，可以转化为求解 Gram 矩阵的特征值与特征向量： $$ 假设求解出 $$ 的特征向量为 $$，则 $$ 的第 $$ 个特征向量为： $$ 其中 $$ 表示 $$ 的第 $$ 个维度。$$ 模长的平方为： $$ 于是数据点 $$ 在 $$ 上的投影为： $$ 现在还有一个遗留问题——我们假设映射后特征的均值依旧是 $$，但这并不总是正确（即便数据的均值是 $$）。假设中心化后的特征为： $$ 那么相应的 Gram 矩阵 $$ 的第 $$ 行第 $$ 列为： $$ 写作矩阵形式，即： $$ 其中 $$ 表示所有元素均为 $$ 的 $$ 的矩阵。于是我们求解 $$ 的特征值与特征向量即可。

参考资料

1. Bishop, Christopher M., and Nasser M. Nasrabadi. Pattern recognition and machine learning. ↩︎
2. Murphy, Kevin P. Probabilistic Machine Learning: An Introduction. ↩︎
3. Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. ↩︎