基本思想

降维是机器学习中很常见的一种思维方式，一般来说，可以通过线性投影和非线性映射进行。

PCA是一种简单的线性映射，当考虑降维时，我们一般有两种思路：

• 找到d-维仿射变换子空间，在合适的投影下，新的投影点与原先的投影点就接近。也就是说，在新投影下能最大限度的保持原数据的特征。
• 找到d-位投影，尽可能多的保留数据的变动（方差）。

我们将会从这两个思路分别进行求解，可以看到，这两个目标实际上等价。

定义

首先定义一些常用的量

样本均值

$\mu_n = \frac{1}{n}\sum\limits_{n = 1}^{n}x_i$

样本协方差

$\sum_n = \frac{1}{n-1}\sum\limits_{i=1}^{n}(x_i - \mu_i)(x_i - \mu_i)^T$

其中$x_i$ 为数据样本（列向量），因此可以得到$X = (x_1,...,x_n)$为$p\times n$矩阵，因此，写成矩阵的形式为

$\sum_n = \frac{1}{n-1}(X - \mu_n1)(X - \mu1)^T$

直观理解

首先，让我们用不是很严格的数学公式来直观理解PCA。

我们很常见的思想是使得协方差矩阵的方差尽可能大（保留更多有效信息），而让协方差尽可能的小（防止数据冗余），在协方差矩阵中则表现为对角矩阵$D$。

我们令经过d-维基$V$变换后的新坐标为$y$，因此可得：

$\begin{aligned} D &=y y^{T} \\ &=V x(V x)^{T} \\ &=V x x^{T} V^{T} \\ &=V \sum_{n} V^{T} \end{aligned}$

这个式子有着特殊的含义。其中，$D$是新的协方差矩阵（对角矩阵），而$\sum_n$则是原始数据的协方差矩阵，$V$则是d-维正交基。

因此，这个式子可以理解为：对协方差矩阵$\sum_n$，找一个$V$，使得其转变为对角矩阵。而协方差矩阵是实对称矩阵，一定能够对角化，证明了这一点的完备性。

因此，我们只需要对协方差矩阵进行对角化，然后求出其对应的特征向量，即为新坐标下的正交基$V$。对$y = Vx$进行坐标变换则求到了新坐标下的PCA坐标。

PCA是最佳的仿射变换拟合

我们要对每个近似$x_i$近似（由仿射变换的定义）：

$x_i \approx \mu + \sum\limits_{j= 1}^{d} \beta_i^jv_j$

其中，$V_{p\times d} = (v_1,..,v_d)$为d-维子空间中的标准正交基，$\mu \in R^p$是平移量，$\beta_j$为在基$v_j$下的系数，$\beta_j^i$为$\beta_j$的第$i$个分量那么上式可以写成：

$x_i = \mu + V\beta_i$

由于其中的$V$由标准正交基组成，因此$V^TV = 1$.

用平方误差来衡量拟合效果，即要求出：

$\min\limits_{\mu,V,\beta_i.V^TV=1} \sum\limits_{i=1}^n||x_i - (\mu + V\beta_i)||^2$

求$\mu$的最优值

首先对$\mu$求偏导，可以得到：

$\sum_{i=1}^n(x_i - (\mu + V\beta_i)) = 0 \Rightarrow (\sum_{i=1}^n x_i) - n\mu - V(\sum_{i=1}^n \beta_i) = 0$

由于$\mu$和$\beta$之间没有关系，不失一般性我们可以假设$\sum \beta_i = 0$，因此可以解出：

$\mu^* = \frac{1}{n}\sum_{i=1}^{n}x_i = \mu_n$

因此，$\mu$的最优值就是样本均值$\mu^*$。

这样，我们可以将原始式子化简为：

$\min\limits_{\mu,V,\beta_i.V^TV=1} \sum\limits_{i=1}^n||x_i - (\mu_n + V\beta_i)||^2$

求$\beta_i$的最优值

注意到，$\beta_i$之间是无耦合的影响的最小值，因此，对于原始式子，可以分别解出$\beta_i$：

$\min\limits_{\beta_i}||x_i - \mu_n - V\beta_i||^2 = \min\limits_{\beta_i}||x_i - \mu_n - \sum\limits_{j=1}^d\beta_i^jv_j||^2$

由于$V$是标准正交基，对$\beta_i$求偏导：

$\beta_i^j = v_j^T(x_i - \mu_n)\Rightarrow \beta_i = V^T(x_i - \mu _n)$

因此式子可以化简为：

$\min\limits_{V^TV = 1} \sum\limits_{i= 1 } ^n ||(x_i - \mu_n) - VV^T(x_i - \mu_n)||^2$

求$V$的最优值

由$||x||^2 = <x,x>$和$V^TV = 1$，可以得到：

$\begin{aligned} \left\|\left(x_{i}-\mu_{n}\right)-V V^{T}\left(x_{i}-\mu_{n}\right)\right\|^{2} &=\left[\left(x_{i}-\mu_{n}\right)-V V^{T}\left(x_{i}-\mu_{n}\right)\right]^{T}\left[\left(x_{i}-\mu_{n}\right)-V V^{T}\left(x_{i}-\mu_{n}\right)\right] \\ &=\left(x_{i}-\mu_{n}\right)^{T}\left(x_{i}-\mu_{n}\right)-\left(x_{i}-\mu_{n}\right)^{T} V V^{T}\left(x_{i}-\mu_{n}\right)-\left(x_{i}-\mu_{n}\right)^{T} V V^{T}\left(x_{i}-\mu_{n}\right)+\left(x_{i}-\mu_{n}\right)^{T} V V \\ &=2\left(x_{i}-\mu_{n}\right)^{T}\left(x_{i}-\mu_{n}\right)-2\left(x_{i}-\mu_{n}\right)^{T} V V^{T}\left(x_{i}-\mu_{n}\right) \end{aligned}$

由于$(x_i - \mu_n)^T(x_i - \mu_n)$与$V$无关，因此等价于求：

$\max _{V^{T} V=1} \sum_{i=1}^{n}\left(x_{i}-\mu_{n}\right)^{T} V V^{T}\left(x_{i}-\mu_{n}\right)$ 化简原式可得：

$\sum_{i=1}^{n}\left(x_{i}-\mu_{n}\right)^{T} V V^{T}\left(x_{i}-\mu_{n}\right)=\sum_{i=1}^{n}\left[V^{T}\left(x_{i}-\mu_{n}\right)\right]^{T}\left[V^{T}\left(x_{i}-\mu_{n}\right)\right]$ 由矩阵的迹的性质可得：

$y^Ty = Tr(yy^T)$

因此，将原始化简的式子等价于求：

$\max\limits _{V^TV=1}\sum\limits_{i=1}^n (x_i - \mu_n)^TVV^T(x_i - \mu_n) =\max\limits _{V^TV=1} (n-1)Tr(V^T\sum_nV)$

即：

$\max\limits _{V^TV=1} Tr(V^T\sum_nV)$

即，我们最后要求的标准正交基为使得协方差矩阵的迹最大；这等价于求协方差矩阵的特征值，并按照从大到小排列。

PCA保留最大方差

我们的第二个目标是要保留数据最大变化的d-维投影。可以写出全方差为：

$\text{Total Variance} (X_n) = \frac{1}{n} \sum\limits||x_i- \mu_n||^2 = \frac {1}{n} \sum\limits_{i=1}^n||x_i - \frac{1}{n}\sum\limits_{i=1}^n x_i||^2$

因此，我们要向最大化投影以后的方差，即$V^Tx_i$的方差：

$\max\limits _{V^TV=1}\sum\limits_{i=1}^n ||V^Tx_i - \frac{1}{n}\sum\limits_{i=1}^n V^Tx_i||^2$

根据之前的结论：

$\sum\limits_{i=1}^n ||V^Tx_i - \frac{1}{n}\sum\limits_{i=1}^n V^Tx_i||^2 =\sum\limits_{i=1}^n ||V^T(x_i - \mu_n)||^2= (n-1)Tr(V^T\sum_nV)$

表明主成分$V$可以通过下式解决：

$\max\limits_{V^TV = 1}Tr(V^T\sum_nV)$

这样，两种不同的度量方法就等价求协方差矩阵的前$d$个特征值。

参考资料

• 如何通俗地讲解「仿射变换」这个概念

• 奇异值的物理意义是什么

• Tutorial on Principal Component Analysis