[ML Notes] PCA：最大可分性

Author: nex3z 2020-08-17

  主成分分析（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$：

1. 对所有样本进行中心化：$\boldsymbol x_i = \boldsymbol x_i – \frac{1}{m} \sum\limits_{i=1}^m \boldsymbol d_i$；
2. 计算样本的协方差矩阵 $\boldsymbol X \boldsymbol X^\mathrm{T}$；
3. 对协方差矩阵 $\boldsymbol X \boldsymbol X^\mathrm{T}$ 进行特征值分解；
4. 取最大的 $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}$$