PCA降维

维度劫难

当样本数据的维度较高时，可能会面临维度劫难问题。https://zhuanlan.zhihu.com/p/87389704。概括来说，当数据的维度越高，要找到最优解甚至达到稍低维度时模型的等同 performance，所须要的数据越多，而且是成几何数增长的。
一种无效的解决办法是降维。

样本均值和样本协方差

给定样本数据 $X=(x_1,x_2,\cdots,x_N)^T_{N\times P}$，其中 $N$ 示意样本个数，$P$ 示意样本的维度，$x_i=(x_{i,1},\cdots,x_{i,P})^T$，$x_i \in \mathbb{R}^P,i=1,\cdots,N$。

样本均值为，
$$\begin{equation}\begin{aligned}\overline{x}_{P\times 1}&=\frac{1}{N}\sum_{i=1}^N x_i\\&=\frac{1}{N}\underbrace{(x_1,x_2,\cdots,x_N)}_{X^T}\begin{pmatrix}1 \\1\\\vdots\\1\end{pmatrix}_{N\times 1}\\&=\frac{1}{N}X^T\mathbf{1}_{N}\end{aligned}\tag{1}\end{equation}$$

样本协方差为
$$\begin{equation}\begin{aligned}S_{P\times P}&=\frac{1}{N}\sum_{i=1}^{N}(x_i -\overline{x})(x_i – \overline{x})^T\\&=\frac{1}{N}\underbrace{(x_1-\overline{x},x_2-\overline{x},\cdots,x_N-\overline{x})}_{X^T-\frac{1}{N}X^T\mathbf{1}_N\mathbf{1}_N^T}\begin{pmatrix}(x_1-\overline{x})^T \\(x_2-\overline{x})^T\\\vdots\\(x_N-\overline{x})^T\end{pmatrix}_{N\times P}\\&=\frac{1}{N}X^T\underbrace{(I_N-\frac{1}{N}\mathbf{1}_N\mathbf{1}_N^T)}_{H}\underbrace{(I_N-\frac{1}{N}\mathbf{1}_N\mathbf{1}_N^T)^T}_{H^T}X\\&=\frac{1}{N}X^THH^TX\\&=\frac{1}{N}X^THX\end{aligned}\tag{2}\end{equation}$$
其中，$H$ 称为 centering matrix，易证实 $H^T=H,H^n=H$。

原始特色空间的重构

PCA 将为的次要思维是：对原始特色空间进行重构，具体做法是找到一组线性无关的基（主成分）代替原来的线性相关的基。

角度一：最大投影方差

以二维空间空间为例，将数据投影到 $u_1$ 和 $u_2$ 方向上，显然在 $u_1$ 方向上的投影方差大于在 $u_2$ 方向上的投影方差。如果样本的维度为 $P$，心愿降维到 $Q$ 维，则就是要找到投影方差最大的 $Q$ 个方向（互相正交），也称为主成分。
假如由向量 $\mathbf{a}$ 和方向向量 $\mathbf{b}$，并且 $\mathbf{b}$ 的模为 1，即 $\mathbf{b}^T\mathbf{b}=1$，则 $\mathbf{a}$ 在 $\mathbf{b}$ 上的投影为 $\mathbf{a}^T\mathbf{b}$。
假如心愿找到方向 $u$，使得投影方差最大，则最大化下式
$$\begin{equation}\begin{aligned}J&=\frac{1}{N}\sum_{i=1}^{N}((x_i-\overline{x})^Tu)^2\\&=\sum_{i=1}^N\frac{1}{N}u^T(x_i-\overline{x})(x_i-\overline{x})^Tu\\&=u^T(\sum_{i=1}^N\frac{1}{N}(x_i-\overline{x})(x_i-\overline{x})^T)u\\&=u^T Su\end{aligned}\tag{3}\end{equation}$$
最大化带束缚的指标函数
$$\begin{equation}\begin{cases}\hat{u}=\arg\max_{u}J \\ s.t.u^Tu=1\end{cases}\tag{4}\end{equation}$$
应用拉格朗日乘子法，
$$\begin{equation}\mathscr{L}(u,\lambda)=u^TSu+\lambda(1-u^Tu)\tag{5}\end{equation}$$
对 $u$ 求导，令其等于 0
$$\begin{equation}\frac{\partial \mathscr{L}}{\partial u}=2Su-\lambda\cdot 2u=0\tag{6}\end{equation}$$
即求 u 满足 $Su=\lambda u$，能够看出 $u$ 实际上就是样本协方差矩阵的特征向量，$\lambda$ 是其对应的特征值。将 $Su=\lambda u$ 代入式 (3)，失去 $J=u^T\lambda u=\lambda$，因而如果心愿将原始维度由 $P$ 降到 $Q$，及抉择前 Q 大的特征值对应的特征向量作为主成分，重构原始的数据。
对于原始数据 $x_i$，能够用新失去的线性无关的基示意
$$\begin{equation}x_i=\sum_{k=1}^P((x_i-\overline{x})^Tu_k)u_k\tag{7}\end{equation}$$
假如主成分为 $u1,\cdots,u_Q$，依据主成分重构数据，
$$\begin{equation}\hat{x}_i=\sum_{k=1}^Q((x_i-\overline{x})^Tu_k)u_k\tag{8}\end{equation}$$

角度二：最小重构间隔

应用 PCA 降维后失去的重构数据，要尽量与原始数据类似。
$$\begin{equation}\begin{aligned}J&=\frac{1}{N}\sum_{i=1}^N||x_i-\hat{x}_i||^{2}\\&=\frac{1}{N}\sum_{i=1}^N||\sum_{k=Q+1}^P((x_i-\overline{x})^Tu_k)u_k||^2\\&=\frac{1}{N}\sum_{i=1}^N\sum_{k=Q+1}^P((x_i-\overline{x})^Tu_k)^2\\&=\sum_{k=Q+1}^P\frac{1}{N}\sum_{i=1}^Nu_k^T(x_i-\overline{x})(x_i-\overline{x})^Tu_k\\&=\sum_{k=Q+1}^Pu_k^TSu_k\end{aligned}\tag{9}\end{equation}$$
又因为 u 是线性无关的，因而最小化式 (9) 能够别离对 $u_k^TSu_k,u_k^Tu_k=1,k=Q+1,\cdots,P$ 进行最小化，因而就等价于找到最小的 $P-Q+1$ 个特征值对应的特征向量，残余的 Q 个特征向量作为主成分。

PCA 和 SVD 的关系

实对称矩阵的特征值合成

对于一个 mxm 的实对称矩阵 $A$，能够合成为如下模式，

$$
\begin{equation}A = Q\Sigma Q^T=
Q\left[
\begin{matrix}
\lambda_1 & \cdots & \cdots & \cdots\\
\cdots & \lambda_2 & \cdots & \cdots\\
\cdots & \cdots & \ddots & \cdots\\
\cdots & \cdots & \cdots & \lambda_m\\
\end{matrix}
\right]_{m \times m}Q^T
\tag{10}
\end{equation}
$$

其中 $Q$ 为规范正交阵，即有 $QQ^T=I$，$I$ 为单位阵,$\lambda_i$ 为特征值，$q_i$ 是特色矩阵 $Q$ 的列向量，为特征向量。

奇怪值合成定义

对于一个 $m\times n$ 的实数矩阵 $A$，能够合成为如下模式
$$\begin{equation}A=U\Sigma V^T=U\left[\begin{matrix}\sigma_1 & 0 & 0 & 0 & 0\\0 & \sigma_2 & 0 & 0 & 0\\0 & 0 & \ddots & 0 & 0\\0 & 0 & 0 & \ddots & 0\\\end{matrix}\right]_{m\times n}V^T\tag{11}\end{equation}$$

其中，$U$ 和 $V$ 为单位正交阵，即 $UU^T=I$，$VV^T=I$，$U$ 称为左奇怪矩阵，$V$ 称为右奇怪矩阵，$\Sigma$ 为对角矩阵，主对角线上的值称为奇怪值（主对角线上的元素非负，且不为 0 的个数取决于 A 的秩）。

对 $HX$ 进行奇怪值合成（SVD），
$$\begin{equation}HX=U\Sigma V^T\tag{12}\end{equation}$$
样本协方差矩阵 $S_{P\times P}=X^THX=X^TH^THX$，将式 (12) 代入，失去
$$\begin{equation}S_{P\times P}=(U\Sigma V^T)^T U\Sigma V^T=V\Sigma^2V^T\tag{13}\end{equation}$$
假如 $T=HXX^TH^T$，则代入式 (12)，失去
$$\begin{equation}T_{N\times N}=U\Sigma V^T(U\Sigma V^T)^T =U\Sigma^2U^T\tag{14}\end{equation}$$
能够看出，式 (11) 和(12)是对 $S$ 和 $T$ 的矩阵合成，两者的特征值雷同。$V$ 的列向量为 $S$ 的特征向量，$U$ 的列向量为 $T$ 的特征向量。有上文可知样本协方差矩阵的特征向量形成主成分，且原始数据应用新的基示意的坐标为 $H^TXV=U\Sigma V^TV=U\Sigma$，而 $TU\Sigma=U\Sigma^2U^TU\Sigma=U\Sigma \Sigma^2$，显然 $U\Sigma$ 由 $T$ 的特征向量组成，联合式(12)，坐标能够通过规范正交阵 $U$ 缩放失去。

因而，$S$ 的特色合成间接失去准成分，而后计算 $HXV$ 失去坐标；而 $T$ 的特色合成则能够间接失去坐标。

参考

1. https://www.bilibili.com/vide…
2. https://www.cnblogs.com/endle…
3. https://zhuanlan.zhihu.com/p/…