PCA
通常被用来做维度缩减，即将数据从高维空间投影到低维空间，同时尽可能完整地保留原有的信息，可以由一个例子来看。假设在二维空间中存在一个单位向量\(q\)，即\(|\!|q|\!| = 1\)，对于同一空间中的其它向量\(x_i\)，该向量在\(q\)上的投影对应的向量为\(d\cdot \frac{q}{|\!|q|\!|} = dq\)（假设长度为\(d\)）。设\(x_i\)与\(q\)的夹角为\(\theta\)，则\(d = |\!|x_i|\!|\cos \theta\)。又\(\cos \theta = \frac{q^\mathsf{T}x_i}{|\!|q|\!||\!|x_i|\!|}\)，因此 \[ d = |\!|x_i|\!|\cos\theta = |\!|x_i|\!|\cdot \frac{q^\mathsf{T}x_i}{|\!|q|\!||\!|x_i|\!|} = q^\mathsf{T}x_i \] 即\(x_i\)在\(q\)上投影对应的向量为\((q^\mathsf{T}x_i)q\)。这样，二维向量\(x_i\)的信息被降为了一维的\(q^\mathsf{T}x_i\)来保存，维度减小，但是信息没有丢失。最好的\(q\)满足平方近似误差最小，即 \[ \begin{align*} q &= {\rm arg}\min_q \sum_{i=1}^n |\!|x_i - qq^\mathsf{T}x_i|\!|^2\ \ \ {\rm subject\ to}\ q^\mathsf{T}q = 1 \\ &= {\rm arg}\min_q \sum_{i=1}^n x_i^\mathsf{T}x_i - q^\mathsf{T}\underbrace{\left(\sum_{i=1}^n x_ix_i^\mathsf{T}\right)}_{=XX^\mathsf{T}}q \end{align*} \] 由于第一项与\(q\)无关，第二项带负号，因此上述问题等价于 \[ q = {\rm arg}\max_q q^\mathsf{T}(XX^\mathsf{T})q\ \ \ {\rm subject\ to}\ q^\mathsf{T}q = 1 \] 这里变化为特征值分解的问题。\(q\)是\(XX^\mathsf{T}\)的第一个特征向量，\(\lambda = q^\mathsf{T}(XX^\mathsf{T})q\)是第一个特征值 具体解释如下：对上述优化问题引入Lagrange乘子，则优化问题转化为 \[ \begin{align*} \mathcal{L} &= q^\mathsf{T}(XX^\mathsf{T})q + \lambda (1-q^\mathsf{T}q) \\ \nabla \mathcal{L}_q &= 2XX^\mathsf{T}q - 2q\lambda \end{align*} \] 令\(\nabla \mathcal{L}=0\)可以得到\(XX^\mathsf{T}q =\lambda q\)，这里也是特征值与特征向量的定义。而由于 \[ \begin{align*} q^\mathsf{T}(XX^\mathsf{T})q &= q^\mathsf{T}\lambda q\ \ (\because (XX^\mathsf{T})q = \lambda q)\\ &= \lambda q^\mathsf{T}q \\ &= \lambda\ \ (\because q^\mathsf{T}q = 1) \end{align*} \] 因此求最大的\(q^\mathsf{T}(XX^\mathsf{T})q\)等于求最大\(\lambda\)，即最大的特征值
上述表示可以推广到将数据降维到\(K\)维的情况，即 \[ \begin{align*} q &= {\rm arg}\min_q \sum_{q=1}^n \left|\!\left|x_i - \underbrace{\sum_{k=1}^K(x_i^\mathsf{T}q_k)q_k}_{ {\rm approximates\ } x}\right|\!\right|^2\ \ \ {\rm s.t.}\ q_k^\mathsf{T}q_k' = \begin{cases}1, & k = k' \\ 0, & k \not= k'\end{cases} \\ &= {\rm arg}\min_q \sum_{i=1}^n x_i^\mathsf{T}x_i - \sum_{k=1}^K q_k^\mathsf{T} \underbrace{\left(\sum_{i=1}^n x_ix_i^\mathsf{T} \right)}_{=XX^\mathsf{T}}q_k \end{align*} \]
因此投影为 \[ x_{\rm proj} = \left[\begin{array}{c} q_1^\mathsf{T}x \\ \vdots \\ q^\mathsf{T}_K x \end{array}\right],\ \ x \approx \sum_{k=1}^K (q_k^\mathsf{T}x)q_k = Qx_{\rm proj} \]
使用SVD分解，可以得到\(X=USV^\mathsf{T}\)。我们有\(XX^\mathsf{T} = US^2U^\mathsf{T}\)，可以推出\(Q=U, \lambda_i = (S^2)_{ii} \ge 0\)，即\(XX^\mathsf{T}\)是半正定矩阵，因此特征值有\(r = \min\{d, n\}\)个，且 \[ \lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_r > 0 \]
PCA之前一般要做一个预处理，把\(x\)的每个维度减去该列的均值
概率PCA
使用SVD分解，有\(X=USV^\mathsf{T}\)。如果我们用矩阵\(W\)和\(Z\)近似，即\(X\approx WZ\)，其中
- \(W\)是一个\(d \times K\)矩阵，类似特征向量组成的集合，但是并不需要正交
- \(Z\)的第\(i\)列\(z_i \in \mathbb{R}^K\)是\(x_i\)在低维空间的表示
则概率PCA的生成过程为 \[ x_i \sim N(Wz_i, \sigma^2I),\ \ z_i \sim N(0,I) \]
目标是在边缘分布下（即积分掉\(z_i\)以后）找出\(W\)的最大似然估计，即 \[ W_{\rm ML} = {\rm arg}\max_W \ln p(x_1, \ldots, x_n|W) = {\rm arg}\max_W \sum_{i=1}^n \ln p(x_i|W) \] 由于\(p(x_i|W) = N(x_i |0, \sigma^2I + WW^\mathsf{T})\) \[ N(x_i |0, \sigma^2I + WW^\mathsf{T}) = \frac{1}{(2\pi)^{\frac{d}{2}}\left|\sigma^2 I + WW^\mathsf{T}\right|^{\frac{1}{2}}}e^{-\frac{1}{2}x^\mathsf{T}(\sigma^2I + WW^\mathsf{T})^{-1}x} \] 可以借助\(z_1, \ldots, z_n\)来使用EM算法求解
概率PCA的EM算法 输入：数据\(x_{1:n}, x_i \in \mathbb{R}^d\)，模型\(x_i \sim N(W_{z_i}, \sigma^2), z_i \sim N(0,I), z\in \mathbb{R}^K\) 输出：\(W\)的点估计和\(z_i\)的后验分布 E步：令每个\(q(z_i) = p(z_i|x_i, W) = N(z_i|\mu_i, \Sigma_i)\)，其中 \[ \Sigma_i = (I + W^\mathsf{T}W/\sigma^2)^{-1},\ \ \mu_i = \Sigma_iW^\mathsf{T}x_i / \sigma^2 \] M步：最大化E步的目标函数\(\mathcal{L}\)，更新\(W\) \[ W = \left[\sum_{i=1}^n x_i\mu_i^\mathsf{T}\right]\left[\sigma^2I + \sum_{i=1}^n (\mu_i\mu_i^\mathsf{T}+\Sigma_i)\right]^{-1} \]
核PCA
在原始的PCA中，\(\sum_{i=1}^n x_ix_i^\mathsf{T}\)可以写作\(XX^\mathsf{T}\)。如果我们使用\(\phi(x)\)把特征从\(\mathbb{R}^d\)映射到\(\mathbb{R}^D\)，即做特征值分解 \[ \left[\sum_{i=1}^n \phi(x_i)\phi(x_i)^\mathsf{T}\right]q_k = \lambda_kq_k \] 同时又不真正在高维空间中做计算，即，如何不显式使用\(\phi(\cdot)\)和\(q\)，直接做PCA？
由于由前式有 \[ \sum_{i=1}^n \phi(x_i)\underbrace{(\phi(x_i)^\mathsf{T}q_k)/\lambda_k}_{=a_{ki}} = q_k \] 因此\(q_k\)可以写为 \[ q_k = \sum_{i=1}^n a_{ki}\phi(x_i) \] 其中\(\mathbf{a}_k \in \mathbb{R}^n\)
因此我们可以不学习\(q_k\)，直接学习\(\mathbf{a}_k\)。把上面\(q_k\)的式子代回原始公式，有 \[ \sum_{i=1}^n \phi(x_i) \sum_{j=1}^n a_{kj}\underbrace{\phi(x_i)^\mathsf{T}\phi(x_j)}_{K(x_i, x_j)} = \lambda_k \sum_{i=1}^n a_{ki}\phi(x_i) \] 对于赏识，左右两边再乘以\(\phi(x_l)^\mathsf{T}\)，\(l \in \{1,\ldots, n\}\)，可以得到 \[ K^2\mathbf{a}_k = \lambda_k K \mathbf{a}_k \Leftrightarrow K\mathbf{a}_k = \lambda_k \mathbf{a}_k \] 其中\(K\)是在数据上构建的\(n\times n\)核矩阵
核PCA 输入：数据\(x_1, \ldots, x_n, x\in \mathbb{R}^d\)，以及核函数\(K(x_i, x_j)\) 构造数据上的核矩阵，例如 \[ K_{ij} = b\exp\left\{-\frac{|\!|x_i - x_j|\!|^2}{c}\right\} \] 对核矩阵做特征值分解，得到前\(r <\!\!< n\)个特征值/特征向量 \((\lambda_1, \mathbf{a}_1) , \ldots, (\lambda_r, \mathbf{a}_r)\) 输出：\(x_i\)的低维表示，先将\(x_i\)映射到\(\phi(x_i)\)，然后投影为\(q_k^\mathsf{T}\phi(x_i)\) \[ x_i \mathop{\rightarrow}^{\rm proj} \left[\begin{matrix} \lambda_1a_{1i} \\ \vdots \\ \lambda_ra_{ri} \end{matrix}\right] \] 其中\(a_{ki}\)是第\(k\)个特征向量\(\mathbf{a}_k\)的第\(i\)维
对新数据也可以做类似的kernel trick，只不过有 \[ \begin{align*} x_0 &\mathop{\rightarrow}^{\rm proj} \left[\begin{matrix} \phi(x_0)^\mathsf{T}q_1 \\ \vdots \\ \phi(x_0)^\mathsf{T}q_r \end{matrix}\right] \\ \phi(x_0)^\mathsf{T}q_k &= \sum_{i=1}^n a_{ki}\phi(x_0)^\mathsf{T}\phi(x_i) = \sum_{i=1}^n a_{ki}K(x_0, x_i) \end{align*} \]
