1.PCA

主成分分析(Principle Component Analysis，PCA)，是一种多变量统计分析方法，也是数据降维和可视化的常用方法。PCA的原理是将原矩阵投影到一个新的正交坐标系下，且通过依次选择新坐标轴的方向，使得矩阵在新坐标轴上的投影(主成分的样本值)的方差最大

2.证明

输入: $x_i\in {\mathbb{R}}^n,i=1,2,\cdots ,m$

输出: 主成分向量 $z_1,z_2,\cdots ,z_k\in {\mathbb{R}}^n,k\le n$

• 对输入的数据进行归一化：
  $$\tilde{X}=\left[{\tilde{x}}_1,\cdots ,{\tilde{x}}_m\right],{\tilde{x}}_i=x_i-\bar{x},i=1,\cdots ,m\bar{x}=\frac{1}{m}\sum _{i=1}^m{x}_i$$

• PCA就是将这些点投影到方向为$z\in {\mathbb{R}}^n,\Vert z{\Vert }_2=1$上时，保证得到最大的方差，也就是在这个方向上分布地最散：
  $${\alpha }_i={\tilde{x}}_i^{T}z,i=1,\cdots ,m$$

• 投影得到的平均方差为：
  $$\frac{1}{m}\sum _{i=1}^m{\alpha }_i^2=\frac{1}{m}\sum _{i=1}^m{z}^T{\tilde{x}}_i{\tilde{x}}_i^{T}z=\frac{1}{m}{z}^T\tilde{X}{\tilde{X}}^{T}z$$

• 所以，最大化上式：
  $$\underset{z\in R^n}{\max }{z}^T\left(\tilde{X}{\tilde{X}}^T\right)z,\text{ s.t.: }\Vert z{\Vert }_2=1$$

• 根据瑞利熵：
  $${\lambda }_{\min }(A)\le \frac{x^{T}Ax}{x^{T}x}\le {\lambda }_{\max }(A),\forall x\ne 0$$

• 根据谱定理：
  $$A=U\Lambda U^T=\sum _{i=1}^n{\lambda }_i{u}_i{u}_i^T,\Lambda =\mathrm{diag}\left({\lambda }_1,\cdots ,{\lambda }_n\right)$$

• 最后PCA：
  $$H=\tilde{X}{\tilde{X}}^T=U_r{\Sigma }^2{U}_r^T$$

• 第一个主要向量$z_1=u_1,u_1$便是 $U_r$的第一列。

• Perform SVD on $\tilde{X}$:
  $$\tilde{X}=U_r\Sigma V_r^T=\sum _{i=1}{\sigma }_i{u}_i{v}_i^T$$

• 通过减去第一个主要向量的数据得到第二个主要向量$z_2$：
  $$\begin{array}{rl}& {\tilde{x}}_i^{(1)}={\tilde{x}}_i-u_1\left(u_1^T{\tilde{x}}_i\right),i=1,\cdots ,m\\ & {\tilde{X}}^{(1)}=\left[{\tilde{x}}_1^{(1)},\cdots ,{\tilde{x}}_m^{(1)}\right]=\left(I_n-u_1{u}_1^T\right)\tilde{X}\end{array}$$

• 结合上述两个式子可以得到:
  $$\begin{array}{rl}{\tilde{X}}^{(1)}& =\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T-\left(u_1{u}_1^T\right)\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T\\ & =\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T-\sum _{i=1}^r{\sigma }_i{u}_1{u}_1^T{u}_i{v}_i^T\\ & =\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T-{\sigma }_1{u}_1{v}_1^T//\mathrm{U}\text{ is orthogonal }\\ & =\sum _{i=2}^r{\sigma }_i{u}_i{v}_i^T\end{array}$$

• 已经去掉了第一个分量，那么第二个主要向量$z_2$可以通过下式得到：
  $$\begin{array}{c}\underset{z\in R^n}{\max }{z}^T\left({\tilde{X}}^{(1)}{\tilde{X}}^{(1)T}\right)z,\text{ s.t.: }\Vert z{\Vert }_2=1\\ {\tilde{X}}^{(1)}=\sum _{i=2}^r{\sigma }_i{u}_i{v}_i^T\end{array}$$

• 最后的结果 $z_2=u_2,u_2$ 是$U_r$的第二列。

• $z_3,\cdots z_m$ 可以通过相似的去除分量操作进行计算。

3.总结

给定数据 $x_i\in {\mathbb{R}}^n,i=1,2,\cdots m$, 执行PCA的步骤为:

1. 根据中心进行归一化：
   $$\tilde{X}=\left[{\tilde{x}}_1,\cdots ,{\tilde{x}}_m\right],{\tilde{x}}_i=x_i-\bar{x},i=1,\cdots ,m\bar{x}=\frac{1}{m}\sum _{i=1}^m{x}_i$$
2. 计算 SVD:
   $$H=\tilde{X}{\tilde{X}}^T=U_r{\Sigma }^2{U}_r^T$$
3. 主要向量便是$U_r$的列（$X$的特征向量=$H$的特征向量）

4.Kernel PCA

一般来说，主成分分析(Principal Components Analysis, PCA)适用于数据的线性降维。而核主成分分析(Kernel PCA, KPCA)可实现数据的非线性降维，用于处理线性不可分的数据集。

KPCA的大致思路是：对于输入空间(Input space)中的矩阵 $\mathbf{X}$ ，我们先用一个非线性映射把 $\mathbf{X}$ 中的所有样本映射到一个高维甚至是无穷维的空间(称为特征空间，Feature space)，(使其线性可分)，然后在这个高维空间进行PCA降维。

5.证明

输入数据为$x_i\in {\mathbb{R}}^n,i=1,2,\cdots ,N$，假设存在一个非线性变换$\varphi (\cdot )$，可以将数据的维度从${\mathbb{R}}^n\to {\mathbb{R}}^{n_1}$，其中$n<<n_1$，最终会得到升维后的数据$\varphi (X)=[\varphi (x_1),\varphi (x_2),...,\varphi (x_N)]$

在将维度提升至$n_1$后，再采取标准的线性PCA将维度降低到$n_2$维，其中$n<n_2<n_1$:

1. Assume $\varphi \left(x_i\right)$ is already zero-center
   $$\frac{1}{N}\sum _{i=1}^N\varphi \left(x_i\right)=0$$
2. Compute correlation matrix
   $$\tilde{H}=\frac{1}{N}\sum _{i=1}^N\varphi \left(x_i\right){\varphi }^T\left(x_i\right)=\varphi (X){\varphi }^T(X)$$
3. Solve the eigenvectors/eigenvalues by $\tilde{H}\tilde{z}=\tilde{\lambda }\tilde{z}$

此时存在两个问题：

1. $\varphi$将如何定义？
2. 可以避免通过$\varphi$将数据映射到高维这个步骤吗？

我们注意到，特征向量可以表示为特征的线性组合：
$$\tilde{z}=\sum _{j=1}^N{\alpha }_j\varphi \left(x_j\right)=\varphi (X)\alpha$$
注意，此时的$\alpha$变成了一个向量，$\alpha =[{\alpha }_1,{\alpha }_2,...,{\alpha }_N{]}^T$


证明:
$$\tilde{H}\tilde{z}=\tilde{\lambda }\tilde{z}$$

$$\frac{1}{N}\sum _{i=1}^N\varphi \left(x_i\right)\underset{\mathrm{s}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{a}\mathrm{r}}{\underbrace{{\varphi }^T\left(x_i\right)\tilde{z}}}=\tilde{\lambda }\tilde{z}$$

• 将线性组合带入到 $\tilde{H}\tilde{z}=\tilde{\lambda }\tilde{z}$中：
  $$\begin{array}{rl}\frac{1}{N}\varphi (X){\varphi }^T(X)\varphi (X)\alpha & =\tilde{\lambda }\varphi (X)\alpha \end{array}$$

• 定义 kernel 函数为 $k\left(x_i,x_j\right)={\varphi }^T\left(x_i\right)\varphi \left(x_j\right)$， $K={\varphi }^T(X)\varphi (X)\in {\mathbb{R}}^{N\times N}$,$K(i,j)=k\left(x_i,x_j\right)$，$K$是一个对称矩阵：
  $$\frac{1}{N}\varphi (X)K\alpha =\tilde{\lambda }\varphi (X)\alpha$$

• 两边同时乘以 ${\varphi }^T\left(X\right)$：
  $$\frac{1}{N}{\varphi }^T\left(X\right)\varphi (X)K\alpha =\tilde{\lambda }{\varphi }^T\left(X\right)\varphi (X)\alpha$$

• 上述公式还可以写成：
  $$K^2\alpha =N\tilde{\lambda }K\alpha$$

• 两边去掉 $K$ ：
  $$\begin{array}{rl}& K\alpha =N\tilde{\lambda }\alpha \\ & K\alpha =\lambda \alpha \end{array}$$

• 可以得到特征向量 ${\alpha }_r$ 和特征值 ${\lambda }_r,r=1,\cdots ,l$

• 但是，必须保证 $\tilde{z}$ 是单位向量，值得注意的是，我们是在特征空间中解的线性PCA:
  $$\tilde{H}\tilde{z}=\tilde{\lambda }\tilde{z}\tilde{z}=\sum _{j=1}^N{\alpha }_j\varphi \left(x_j\right)=\varphi (X)\alpha$$

• $\tilde{z}$ 归一化流程为：
  $$\begin{array}{rl}1& ={\tilde{z}}_r^T{\tilde{z}}_r\\ 1& =\sum _{i=1}^N\sum _{j=1}^N{\alpha }_{ri}{\alpha }_{rj}{\varphi }^T\left(x_i\right)\varphi \left(x_j\right)={\alpha }_r^T{\varphi }^T\left(X\right)\varphi \left(X\right){\alpha }_r\\ 1& ={\alpha }_r^{T}K{\alpha }_r\end{array}$$

• 注意到 $K\alpha =\lambda \alpha$, 有：
  $${\alpha }_r^T{\lambda }_r{\alpha }_r=1,\forall r$$

• 即, 将 ${\alpha }_r$ 归一化为 $1/{\lambda }_r$，得到归一化后的${\tilde{\alpha }}_r$.

• 现在, 第 $r^{th}$ 主要向量为：
  $${\tilde{z}}_r=\sum _{j=1}^N{\tilde{\alpha }}_{rj}\varphi \left(x_j\right)$$

• 现在，我们已知数据点$x$的映射$\varphi (x)$的主要向量，将$\varphi (x)$映射到${\tilde{z}}_r$的方向上去：
  $${\varphi }^T(x){\tilde{z}}_r=\sum _{j=1}^N{\alpha }_{rj}{\varphi }^T(x)\varphi \left(x_j\right)=\sum _{j=1}^N{\alpha }_{rj}k\left(x,x_j\right)$$

• 但是，还有一件事需要考虑，我们之前是假设$\varphi \left(x_i\right)$是相对于中心归一化的，所以还要通过kernel保证$\varphi \left(x_i\right)$的归一化。

• 将 $\varphi \left(x_i\right)$ 相对于中心点归一化：
  $$\tilde{\varphi }\left(x_i\right)=\varphi \left(x_i\right)-\frac{1}{N}\sum _{j=1}^N\varphi \left(x_j\right)$$

• 为简化表达式，引入$N$维向量$1_{N\times 1}=[1,1,...,1{]}^T$，则
  $$\tilde{\varphi }\left(x_i\right)=\varphi \left(x_i\right)-\frac{1}{N}\varphi (X)1_{N\times 1}$$

• 将矩阵 $\varphi (\mathbf{X})$ 中所有向量中心化得到:
  $$\begin{array}{c}\tilde{\varphi }(\mathbf{X})=\left[\varphi \left({\mathbf{x}}_1\right)-\frac{1}{N}\varphi (\mathbf{X})1_{\mathbf{N}\times 1},\varphi \left({\mathbf{x}}_2\right)-\frac{1}{N}\varphi (\mathbf{X})1_{\mathbf{N}\times 1},\dots ,\varphi \left({\mathbf{x}}_{\mathbf{N}}\right)-\frac{1}{N}\varphi (\mathbf{X})1_{\mathbf{N}\times 1}\right]\\ =\left[\varphi \left({\mathbf{x}}_1\right),\varphi \left({\mathbf{x}}_2\right),\dots ,\varphi \left({\mathbf{x}}_{\mathbf{N}}\right)\right]-\frac{1}{N}\varphi (\mathbf{X})1_{\mathbf{N}\times 1}{1}_{\mathbf{N}\times 1}^T\\ =\varphi (\mathbf{X})-\frac{1}{N}\varphi (\mathbf{X})1_{\mathbf{N}\times 1}{1}_{\mathbf{N}\times 1^T}\end{array}$$

• 为方便表示，我们再次引入矩阵 $1_{\mathbf{N}}=\frac{1}{N}{1}_{\mathbf{N}\times \mathbb{L}}{1}_{\mathrm{N}\times 1}{}^T$ ，表示一个 $N\times N$ 的矩阵，其每 个元素都为 $\frac{1}{N}$ 。则 $\tilde{\varphi }(\mathbf{X})$ 可简记为:
  $$\tilde{\varphi }(\mathbf{X})=\varphi (\mathbf{X})-\varphi (\mathbf{X})1_{\mathbf{N}}$$

• 如前文所说，我们并不需要显式地计算 $\tilde{\varphi }(\mathbf{X})$ ，只需计算中心化后的核矩阵即可:
  $${\tilde{\mathbf{K}}}_{ij}=\tilde{\varphi }{\left({\mathbf{x}}_{\mathbf{i}}\right)}^T\tilde{\varphi }\left({\mathbf{x}}_{\mathbf{j}}\right)={\left[\varphi \left({\mathbf{x}}_{\mathbf{i}}\right)-\frac{1}{N}\varphi (\mathbf{X})1_{\mathbf{N}\times 1}\right]}^T\left[\varphi \left({\mathbf{x}}_{\mathbf{j}}\right)-\frac{1}{N}\varphi (\mathbf{X})1_{\mathbf{N}\times 1}\right]$$

  • 或者，我们可以直接推导中心化整个核矩阵的表达式，更为紧凑:
    $$\begin{array}{c}\tilde{\mathbf{K}}=\tilde{\varphi }(\mathbf{X}{)}^T\tilde{\varphi }(\mathbf{X})={\left[\varphi (\mathbf{X})-\varphi (\mathbf{X})1_{\mathbf{N}}\right]}^T\left[\varphi (\mathbf{X})-\varphi (\mathbf{X})1_{\mathbf{N}}\right]\\ =\varphi (\mathbf{X}{)}^T\varphi (\mathbf{X})-\varphi (\mathbf{X}{)}^T\varphi (\mathbf{X})1_{\mathbf{N}}-1_{\mathbf{N}}^T\varphi (\mathbf{X}{)}^T\varphi (\mathbf{X})+1_{\mathbf{N}}^T\varphi (\mathbf{X}{)}^T\varphi (\mathbf{X})1_{\mathbf{N}}\\ =\mathbf{K}-\mathbf{K}\cdot 1_{\mathbf{N}}-1_{\mathbf{N}}^T\cdot \mathbf{K}+1_{\mathbf{N}}^T\cdot \mathbf{K}\cdot 1_{\mathbf{N}}\end{array}$$

• 由于 $1_{\mathrm{N}}{}^T=1_{\mathrm{N}}$ 为对称矩阵，所以上式又可简化为
  $$\tilde{\mathbf{K}}=\mathbf{K}-\mathbf{K}\cdot 1_{\mathbf{N}}-1_{\mathbf{N}}\cdot \mathbf{K}+1_{\mathbf{N}}\cdot \mathbf{K}\cdot 1_{\mathbf{N}}$$

可选的kernel

• Linear $k\left(x_i,x_j\right)=x_i^T{x}_j$
• Polynomial $k\left(x_i,x_j\right)={\left(1+x_i^T{x}_j\right)}^p$
• Gaussian $k\left(x_i,x_j\right)=e^{-\beta {\Vert x_i-x_j\Vert }_2}$
• Laplacian $k\left(x_i,x_j\right)=e^{-\beta {\Vert x_i-x_j\Vert }_1}$
• Sigmoid

6.总结

• 选择一个核 $k\left(x_i,x_j\right)$, 计算 Gram matrix $K(i,j)=k\left(x_i,x_j\right)$
• 对 $K$进行归一化：
  $$\tilde{\mathbf{K}}=\mathbf{K}-\mathbf{K}\cdot 1_{\mathbf{N}}-1_{\mathbf{N}}\cdot \mathbf{K}+1_{\mathbf{N}}\cdot \mathbf{K}\cdot 1_{\mathbf{N}}$$
• 解出 $\tilde{K}$的特征值和特征向量：
  $$\tilde{K}{\alpha }_r={\lambda }_r{\alpha }_r$$
• 将 ${\alpha }_r$ 归一化为 ${\alpha }_r^T{\alpha }_r=\frac{1}{{\lambda }_r}$
• 对于任意的数据点 $x\in {\mathbb{R}}^n$，计算其到第$r^{th}$个主要向量方向上的投影 $y_r\in \mathbb{R}$：
  $$y_r={\varphi }^T(x){\tilde{z}}_r=\sum _{j=1}^N{\alpha }_{rj}k\left(x,x_j\right)$$

参考文献

[1] https://zhuanlan.zhihu.com/p/59775730 数据降维: 核主成分分析(Kernel PCA)原理解析
[2] https://zhuanlan.zhihu.com/p/59803328 数据降维: 主成分分析(PCA)与NIPALS算法数学原理