[ML Notes] PCA：最大可分性
主成分分析（Principal Component Analysis，PCA）通过将样本点投影到一个超平面上来实现降维。理想的超平面应当具有：
- 最大可分性：样本点在这个超平面上的投影能尽可能分开，即最大化投影方差，在投影后保留最多的信息；
- 最近重构性：样本点到这个超平面的距离足够近，即最小化平方误差，通过投影可以最准确地重构出原始样本点。
首先从最大可分性的角度考虑。
给定 $m$ 个样本点 $\boldsymbol d_1, \boldsymbol d_2, \cdots, \boldsymbol d_m$，首先进行中心化，计算 $\boldsymbol \mu_{\boldsymbol d} = \frac{1}{m} \sum\limits_{i=1}^m \boldsymbol d_i$，令 $\boldsymbol x_i = \boldsymbol d_i – \boldsymbol \mu_{\boldsymbol d}$，此时有
$$
\boldsymbol \mu_{\boldsymbol x} = \frac{1}{m} \sum\limits_{i=1}^m \boldsymbol x_i = \boldsymbol 0 \tag{1}
$$
两个向量的内积表示第一个向量在第二个向量方向上的投影长度。对于样本 $\boldsymbol x_i$ 和单位方向向量 $\boldsymbol w$，二者的内积
$$
y_i = \boldsymbol x_i^\mathrm{T} \boldsymbol w \tag{2}
$$
表示 $\boldsymbol x_i$ 在 $\boldsymbol w$ 上的投影坐标，要保持最大可分性，即最大化投影方差，相当于找到一个投影方向 $\boldsymbol w$，使得所有样本 $\boldsymbol x_1, \boldsymbol x_2, \cdots, \boldsymbol x_m$ 在 $\boldsymbol w$ 上投影的方差最大。
由式 $(1)$，可知投影后的均值也为 $0$，即
$$
\mu_y = \frac{1}{m} \sum_{i=1}^m y_i = \frac{1}{m} \sum_{i=1}^m \boldsymbol x_i^\mathrm{T} \boldsymbol w = \bigg( \frac{1}{m} \sum_{i=1}^m \boldsymbol x_i^\mathrm{T} \bigg) \boldsymbol w = 0 \tag{3}
$$
于是投影后的方差为
$$
\begin{aligned}
D(y) &= \frac{1}{m} \sum_{i=1}^m (y_i – \mu_y)^2 = \frac{1}{m} \sum_{i=1}^m y_i^2 = \frac{1}{m} \sum_{i=1}^m (\boldsymbol x_i^\mathrm{T} \boldsymbol w)^2 \\
&= \frac{1}{m} \sum_{i=1}^m (\boldsymbol x_i^\mathrm{T} \boldsymbol w)^\mathrm{T} (\boldsymbol x_i^\mathrm{T} \boldsymbol w) \\
&= \frac{1}{m} \sum_{i=1}^m (\boldsymbol w^\mathrm{T} \boldsymbol x_i \boldsymbol x_i^\mathrm{T} \boldsymbol w) \\
&= \boldsymbol w^\mathrm{T} \bigg( \frac{1}{m} \sum_{i=1}^m \boldsymbol x_i \boldsymbol x_i^\mathrm{T} \bigg) \boldsymbol w
\end{aligned}
$$
注意上式中的 $\frac{1}{m} \sum\limits_{i=1}^m \boldsymbol x_i \boldsymbol x_i^\mathrm{T}$ 是样本的协方差矩阵，记为 $\boldsymbol \Sigma$，则上式可以写为
$$
\boldsymbol D = \boldsymbol w^\mathrm{T} \boldsymbol \Sigma \boldsymbol w \tag{4}
$$
又由 $\boldsymbol w$ 为单位方向向量，有 $\boldsymbol w ^\mathrm{T} \boldsymbol w = 1$，于是最大化投影方差变为一个约束优化问题
$$
\begin{aligned}
\max_{\boldsymbol w} \; & \boldsymbol w^\mathrm{T} \boldsymbol \Sigma \boldsymbol w \\
\text{s.t.} \; & \boldsymbol w ^\mathrm{T} \boldsymbol w = 1
\end{aligned} \tag{5}
$$
对式 $(5)$ 构造拉格朗日函数
$$
L(\boldsymbol{w}, \lambda) = \boldsymbol w^\mathrm{T} \boldsymbol \Sigma \boldsymbol w + \lambda (1 – \boldsymbol w ^\mathrm{T} \boldsymbol w)
$$
令 $\nabla_{\boldsymbol w} L = 0$，可得
$$
\nabla_{\boldsymbol w} (\boldsymbol w^\mathrm{T} \boldsymbol \Sigma \boldsymbol w) = \lambda \nabla_{\boldsymbol w} (\boldsymbol w ^\mathrm{T} \boldsymbol w) \tag{6}
$$
$$
\Sigma \boldsymbol w = \lambda \boldsymbol w \tag{7}
$$
将式 $(7)$ 代入式 $(4)$，得到
$$
\boldsymbol D = \boldsymbol w ^\mathrm{T} \lambda \boldsymbol w = \lambda \tag{8}
$$
式 $(7)$ 表明 $\boldsymbol w$ 和 $\lambda$ 分别是协方差矩阵 $\boldsymbol \Sigma$ 的特征向量和特征值，式 $(8)$ 表明特征值 $\lambda$ 即为投影方差。因此，最大化投影方差就是要找到协方差矩阵 $\Sigma$ 的最大的特征值，此时的投影方向 $\boldsymbol w$ 即为最大特征值对应的特征向量。次佳投影方向位于最佳投影方向的正交空间中，为第二大特征值对应的特征向量，以此类推。
由此得到计算 PCA 的求解方法为，给定样本集 $\{\boldsymbol d_1, \boldsymbol d_2, \cdots, \boldsymbol d_m\}$，低维空间维数 $d$：
- 对所有样本进行中心化：$\boldsymbol x_i = \boldsymbol x_i – \frac{1}{m} \sum\limits_{i=1}^m \boldsymbol d_i$；
- 计算样本的协方差矩阵 $\boldsymbol X \boldsymbol X^\mathrm{T}$；
- 对协方差矩阵 $\boldsymbol X \boldsymbol X^\mathrm{T}$ 进行特征值分解；
- 取最大的 $d$ 个特征值所对应的特征向量 $\boldsymbol w_1, \boldsymbol w_2, \cdots, \boldsymbol w_d$；
由此得到投影矩阵 $\boldsymbol W = (\boldsymbol w_1, \boldsymbol w_2, \cdots, \boldsymbol w_d)$。可以通过如下的计算将单个 $n$ 维样本 $\boldsymbol x$ 映射到 $d$ 维
$$
\boldsymbol z =
\begin{bmatrix}
\boldsymbol w_1^\mathrm{T} \boldsymbol x \\
\boldsymbol w_2^\mathrm{T} \boldsymbol x \\
\vdots \\
\boldsymbol w_d^\mathrm{T} \boldsymbol x
\end{bmatrix}
= \boldsymbol W^\mathrm{T} \boldsymbol x \tag{9}
$$
基于映射得到的 $d$ 维向量 $\boldsymbol z$，可以重构 $n$ 维向量 $\boldsymbol x$
$$
\boldsymbol x’ = \sum_{i=1}^d \boldsymbol z_i \boldsymbol w_i = \boldsymbol W \boldsymbol z\tag{10}
$$