[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$:

  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}
$$