统计学习方法

PCA

声明：以下默认“主成分”均指总体主成分，而不是样本主成分

你是什么成分？

统计学中，处理的都是一堆随机变量，要从这些随机的东西中看出点什么，就是要把杂乱的关系“解耦”清楚。就像物理中的复杂的多粒子体系，如何处理比较好呢？方法是把它们解耦为好几个模态，每一个模态都是一个简谐振动，这样就分析出了这个体系的几根骨架。

提取主成分的思想也是一样：对原本互相相关的几个随机变量进行（正交）线性变换，得到一系列新的随机变量，使得到的几个随机变量不相关，这些新的随机变量就是解耦出来的骨架

有$m$维随机变量$\vec{x}=(x_1,\dots,x_m)^T$，注意！其每一个分量都是一个随机变量，代表一种特征，拥有不同的量纲。记其均值向量为$\vec{\mu}=(\mu_1,\dots,\mu_m)^T$

其协方差矩阵为：$\Sigma=E[(\vec{x}-\vec{\mu})(\vec{x}-\vec{\mu})^T]$（注意这里的左边是列向量，右边是行向量）

做线性变换为$y_i=\vec{\alpha_i}^T\vec{x}$，这就是要找的新的变量。根据这个变换形式，就有：
$$
\begin{align*}
&E(y_i)=\vec{\alpha_i}^T\vec{\mu}
\newline
\newline
&\text{Var}(y_i)=\vec{\alpha_i}^T\Sigma\vec{\alpha_i}
\newline
\newline
&\text{Cov}(y_i,y_j)=\vec{\alpha_i}^T\Sigma\vec{\alpha_j}
\end{align*}
$$

那什么是主成分？就是形如上面的线性变换$y_i=\vec{\alpha_i}^T\vec{x}$（仍是随机变量，而且是不同量纲的东西线性叠加得到的随机变量），满足：

正交性：$\vec{\alpha_i}^T\vec{\alpha_j}=\delta_{ij}$（克罗内克符号）
得到的新变量互不相关（概率论中概念），即$\text{Cov}(y_i,y_j)=0\quad ,i\neq j$
按方差大小排序：变量$y_1$是所有$y_i$中方差最大的，$y_2$则是所有与$y_1$不相关的$\vec{x}$的线性变换中，方差次大的……

怎么找呢？其实这和特征值有关

核心定理 设$\Sigma$的特征值是$\lambda_1\geq\lambda_2\geq\dots\geq 0$，分别对应特征向量$\vec{\alpha_1},\vec{\alpha_2},\dots,\vec{\alpha_m}$，则，这些$\vec{\alpha_i}$正是就是要找的线性变换！要找的主成分恰好是它们得来的：$y_i=\vec{\alpha_i}^T\vec{x}$

证明：

使用Lagrange乘数法，因为这里有约束条件$\vec{\alpha_i}^T\vec{\alpha_i}=1$以及与之前的成分不相关，在这些约束之下想要方差最大

对于首个主成分，求解的问题是：

$$
\begin{align*}
\max_{\vec{\alpha_1}} \vec{\alpha_1}^T\Sigma\vec{\alpha_1} \\
\text{s.t. } \vec{\alpha_1}^T\vec{\alpha_1}=1
\end{align*}
$$
因此$\mathscr{L}:=\vec{\alpha_1}^T\Sigma\vec{\alpha_1}-\lambda(\vec{\alpha_1}^T\vec{\alpha_1}-1)$
对$\vec{\alpha_1}$的各个分量分别求偏导并使之为零，能得到好几个方程，将这些方程拼起来是一个很好的向量式：
$$
\Sigma\vec{\alpha_1}-\lambda\vec{\alpha_1}=0
$$
神奇地发现这是特征方程的形式，因此目标函数就是$\max\limits_{\vec{\alpha_1}} \vec{\alpha_1}^T\Sigma\vec{\alpha_1} =\max\limits_{\vec{\alpha_1}} \lambda$，取到最大时，$\vec{\alpha_1}$是特征向量，而且是最大的那个特征值$\lambda_1$对应的特征向量

对于第二个分量，仍然类似，只不过约束多了一个“和第一个不相关”，因此Lagrange函数变为：
$$
\mathscr{L}:=\vec{\alpha_2}^T\Sigma\vec{\alpha_2}-\lambda(\vec{\alpha_2}^T\vec{\alpha_2}-1)-\mu\vec{\alpha_2}^T\Sigma\vec{\alpha_1}
$$
注意到已知$\vec{\alpha_1}$是特征向量，那么上式就是：
$$
\mathscr{L}:=\vec{\alpha_2}^T\Sigma\vec{\alpha_2}-\lambda(\vec{\alpha_2}^T\vec{\alpha_2}-1)-\mu\lambda_1\vec{\alpha_2}^T\vec{\alpha_1}
$$
而且根据定义正交性要求，其实尾项就是零，因此该Lagrange函数形式实际和之前的一模一样，仍能得出一个特征方程形式……
取到最大时，$\vec{\alpha_2}$是特征向量，而且是除去$\lambda_1$后最大的那个特征值对应的特征向量……
$\square$

补充：可能会问，凭什么一定存在呢？万一根本不能满足$\Sigma\vec{\alpha_1}-\lambda\vec{\alpha_1}=0$有解怎么办？的确，这里还缺了一小步论证

证明该方程有解，并且在$2,3,\dots,m$的情况下一直有解，等价于证明$\Sigma$有$m$个正交的特征向量。幸运的是，$\Sigma$是协方差矩阵，而协方差矩阵一定是实对称矩阵（因为协方差当然是实数，而且$\text{Cov}(y_i,y_j)=\text{Cov}(y_j,y_i)$也成立），根据谱定理就知道，它有一组特征向量能够组成规范正交基
$\square$
By the way，不仅是实对称，而且其实是半正定的

主成分的性质

下面来看看变换完成，即，找到主成分后，又有怎么样的结果：

主成分$(y_1,y_2\dots,y_m)^T$的协方差矩阵是对角矩阵，对角元素分别为$\lambda_1,\dots,\lambda_m$

原因是，根据主成分定义就可知$y_i$互相之间协方差为零，此外，$y_i$自身的协方差就是方差，自然就是$\text{Var}(y_i)=\vec{\alpha_i}^T\Sigma\vec{\alpha_i}=\lambda_i \vec{\alpha_i}^T\vec{\alpha_i}=\lambda_i$

方差和不变性：总体主成分$\vec{y}=(y_1,\dots,y_m)^T$的方差之和，等于随机变量$\vec{x}=(x_1,\dots,x_m)^T$的方差之和

原因是，之前的$\vec{x}$的方差之和就是$\vec{x}$的协方差矩阵的对角线之和，因此就是$\text{Tr}(\Sigma)$

若记$\alpha_1,\dots,\alpha_m$这些列向量组成的正交矩阵（酉矩阵）为$A$（含义就是这个正交变换，有$\vec{y}=A^T \vec{x}$），那么根据刚才的核心定理，有$\Sigma A=A\Lambda$，亦即$\Sigma=A\Lambda A^T$

代入就有：$\text{Tr}(\Sigma)=\text{Tr}(A\Lambda A^T)=\text{Tr}(\Lambda)$（已经用了迹的换序性质），就是$\lambda_i$之和，而$\text{Var}(y_i)=\lambda_i$，所以等式右侧就是后来的$\vec{y}$的方差之和

$\square$

有何作用？

和SVD一样，目的都是用更更少的数据代替原始数据，实现“压缩”。主成分分析已经把随机变量中的几根骨架找出来了，那么，哪几根骨架权重最大，说明比较重要，就予以保留，哪些权重较小，就说明不大重要，就予以抛弃（这和控制理论中的“仅保留主导极点”一样）

符合“主成分”字面意思的，就是把最主要的成分保留下来，无关紧要的成分抛弃了，实现一种逼近。

那主成分分析是在何种意义下的最优逼近呢？是在方差意义下的：

定理考虑某个正交变换$\vec{y}=B^T\vec{x}$，这里的$B$不是方阵，而是“$m$维降到$q$维”的$B^T\in R^{q\times m}$。下面考察$\vec{y}$的协方差矩阵$\Sigma_y=B^T\Sigma B$，请问$B$取什么时$\text{Tr}(\Sigma_y)$最大？答案就是：可以根据主成分分析得来的$A$构造！$B$由正交矩阵$A$的前$q$列组成时，$\text{Tr}(\Sigma_y)$一定能取到最大（但没说是取到最大的唯一方法）

证明：由于$A$的列向量就是$\alpha_i$们，它们是张成$R^m$的规范正交基，因此，某个$B$的列向量$\beta_k,k\in 1,\dots,q$可以表示为$\sum\limits_{j=1}^m c_{jk}\vec{\alpha_j}$

故可写为：$B=AC$，这样就有：$C^T C=(A^TB)^T(A^TB)=B^T B=I$（最后一步来自$B$是正交变换），因此$\sum_{j=1}^m\sum_{k=1}^q c_{jk}^2=q$（这一步想清楚行和列就懂了）

此外，我们的目标是$\text{Tr}(B^T\Sigma B)$，下面来看它：$B^T\Sigma B=C^T A^T\Sigma AC=C^T\Lambda C$，按外积展开即为：$\sum\limits_{j=1}^m\lambda_j \vec{c_j}\vec{c_j}^T$（其中$c_j^T$是$C$的第$j$行，可见下方说明）因此：
$$
\begin{align*}
\text{Tr}(B^T\Sigma B)&=\sum\limits_{j=1}^m\lambda_j \text{Tr}(\vec{c_j}\vec{c_j}^T)\newline
&=\sum\limits_{j=1}^m\lambda_j \text{Tr}(\vec{c_j}^T\vec{c_j})\newline
&=\sum\limits_{j=1}^m\lambda_j (\sum_{k=1}^q c_{jk}^2)
\end{align*}
$$

下面的任务就是给$\lambda_j$们配上一些系数（$\sum_{k=1}^q c_{jk}^2$），使得上面那个式子的值最大，如何配呢？由于这些系数加起来是$q$，而且每个系数都有上界$1$（见下方的论述），这样，要使得上面式子的值最大，得使最大的$q$个$\lambda_j$的系数都是$1$才行。显然，$C$取单位阵的前$q$列时能够满足这一点，因此，$B$取$A$的前$k$列可以取到最大！
$\square$

补充论证：为什么系数$\sum_{k=1}^q c_{jk}^2$有上界$1$？

因为根据$C^T C=I$这一点，可以把$C$视为一个正交方阵$D$的前$q$列，这样，必然有$D$的行向量模长平方为一，即$\sum_{k=1}^m d_{jk}^2=1$，推出$\sum_{k=1}^q d_{jk}^2\leq 1$，当然由于$C$是$D$的一部分，所以$c_{jk}=d_{jk},k=1,\dots,q$，所以这就是$\sum_{k=1}^q c_{jk}^2\leq 1$

对外积展开的补充：对外积不熟悉，可以先想矩阵的线性性质，比如$C^T C$可以想成：

$C^T$分成某一列仍不变，而其他列都是$0$的矩阵加和，即分成如下三个小矩阵，叫它们左1、中1、右1：
$$
\begin{pmatrix}
c_{11}&0&0\\
c_{21}&0&0\\
c_{31}&0&0\\
\end{pmatrix} +\begin{pmatrix}
0&c_{12}&0\\
0&c_{22}&0\\
0&c_{32}&0\\
\end{pmatrix}+\begin{pmatrix}
0&0&c_{13}\\
0&0&c_{23}\\
0&0&c_{33}\\
\end{pmatrix}
$$
同样，$C$也是如此，分成三个矩阵，叫它们左2，中2，右2:
$$
\begin{pmatrix}
c_{11}&c_{12}&c_{13}\\
0&0&0\\
0&0&0\\
\end{pmatrix} +\begin{pmatrix}
0&0&0\\
c_{21}&c_{22}&c_{23}\\
0&0&0\\
\end{pmatrix}+\begin{pmatrix}
0&0&0\\
0&0&0\\
c_{31}&c_{32}&c_{33}\\
\end{pmatrix}
$$
一个重要观察就是：只有左1乘左2，中1乘中2，右1乘右2才非零，否则，譬如左1乘中2，位置不对应的都会得到结果零。至此，可以理解为何$C^T C$外积展开中只有$\vec{c_{jk}}$自己和自己的转置乘了吧

同样有定理：

定理考虑某个正交变换$\vec{y}=B^T\vec{x}$，$B^T\in R^{p\times m}$。下面考察$\vec{y}$的协方差矩阵$\Sigma_y=B^T\Sigma B$，请问$B$取什么时$\text{Tr}(\Sigma_y)$最小？$B$由正交矩阵$A$的后$p$列组成时，$\text{Tr}(\Sigma_y)$能取到最小

样本主成分以及算法

由于以上只是考虑“总体”的主成分而已，对于实际情况，往往是根据多次观测得到一组样本，然后写出样本的协方差矩阵，再求其特征值，然后结合实际，取最大的几个特征值，它们对应的特征向量就是主成分……

虽之前都基于总体协方差矩阵，但这里替换成样本协方差矩阵也没问题，是因为：样本协方差矩阵是总体协方差矩阵的无偏估计

证明：即证每一个位置都对应：样本的协方差矩阵中的每一个元素，其期望都是总体协方差矩阵中对应元素

记样本拼成的矩阵为$X$，其每一列都是一次观测得到结果，某一行代表某一个属性，样本的协方差矩阵即为$\frac{1}{n-1}\tilde{X}\tilde{X}^T$，这里的$\tilde{X}$代表把原来的样本中每一个属性都均值为零处理后的矩阵，$i$行$j$列的元素就是$X_{ij}-\bar{X}_{i}$

因此样本协方差阵的某一个元素$S_{ij}$可表示为：$\frac{1}{n-1}\sum _ r (X _ {ir}-\bar{X} _ i)(X _ {rj}^T-\bar{X} _ j)=\frac{1}{n-1}\sum _ r (X _ {ir}-\bar{X} _ i)(X _ {rj}-\bar{X} _ j)$，因此：
$$
\begin{align*}
&E[\sum _ r (X _ {ir}-\bar{X} _ i)(X _ {jr}-\bar{X} _ j)]
\newline
=&E[\sum _ r (X _ {ir} X _ {jr}- \bar{X} _ i X _ {jr} - \bar{X} _ jX _ {ir} +\bar{X} _ i\bar{X} _ j)]
\newline
=& nE[X_ {ir} X _ {jr}] - E[ n\bar{X} _ i \bar{X} _ {j} + n\bar{X} _ j\bar{X} _ {i} -n\bar{X} _ i\bar{X} _ j]
\newline
=& nE[X _ {i} X _ {j}] -n E[ \bar{X} _ i \bar{X} _ j]
\newline
=& nE[X _ {i} X _ {j}] -n \left(\text{Cov}(\bar{X} _{i},\bar{X}_j)+E[ \bar{X} _ i]E[ \bar{X} _ j] \right)
\newline
=& nE[X _ {i} X _ {j}] -n \left( \frac{1}{n^2}
\sum_r \text{Cov}({X} _ {ir},{X} _ {jr})+E[ X _ i]E[ X _ j] \right)
\newline
=& nE[X _ {i} X _ {j}] -n \left( \frac{1}{n}\text{Cov}({X} _ {i},{X} _ {j})+E[ X _ i]E[ X _ j] \right)
\newline
=& (n-1)\text{Cov}({X} _ {i},{X} _ {j})
\end{align*}
$$
其中，提取出$\frac{1}{n^2}$一步已经使用了协方差的线性性质
$\square$

Frobenius范数逼近

还有一种理解，那就是取$k$个主成分的主成分分析相当于求解最优化问题：
$$
\min\limits_{Y} \Vert X-Y \Vert_F
\
\text{ s.t. } \text{rank}(Y)\leq k
$$

这个范数是Frobenius范数，某个矩阵的Frobenius范数是指，将其每个元素的平方相加再开根（等价于把$R^{m\times n}$的矩阵铺展成一个$R^{mn}$中的向量，那个向量的范数）

为什么PCA就相当于解该优化问题呢？因为有如下定理：

定理矩阵$X\in R^{m\times n}$，其秩为$r$，而想要在$R^{m\times n}$且秩$\leq k$的矩阵中，找到$Y$，使得$\Vert X-Y\Vert_F $最小，则取到最小时，$\Vert A-\hat{Y}\Vert_F =(\sigma_{k+1}^2+\dots+\sigma_{n}^2)^{1/2}$，其中$\sigma_i$是$X$的从大到小第$i$个奇异值

（证明参见SVD章节）

在PCA这里，考虑的$X$指（样本/总体）协方差矩阵，由于其实对称（且半正定）推知$X$的奇异值就是特征值。根据PCA的论述，取最大的$k$个特征值后，Frobenius距离就恰好是$(\sigma_{k+1}^2+\dots+\sigma_{n}^2)^{1/2}$，那么根据这个定理，的确是取到最小值了，因此就是一个最佳逼近