[ML Notes] PCA：最近重构性

Author: nex3z 2020-08-19

  如前文所述，主成分分析通过将样本点投影到一个超平面上来实现降维，可以从最大可分性或最近重构性两个角度寻找理想的超平面。

  从最近重构性的角度考虑，假设数据集有 $m$ 个 $n$ 维的样本点 $\boldsymbol x_1, \boldsymbol x_2, \dots, \boldsymbol x_m$，要将它们投影到 $d$ 维的超平面 $D$ 上。记 $\boldsymbol x_k$ 在 $D$ 上的投影为 $\hat{\boldsymbol x}_k$，则样本点到超平面的距离为

$$\mathrm{distance}(\boldsymbol x_k, D) = ||\boldsymbol x_k – \hat{\boldsymbol x}_k||_2 \tag{1}$$

  记 $W = (\boldsymbol w_1, \boldsymbol w_2, \dots, \boldsymbol w_d)$ 为超平面 $D$ 的标准正交基，则 $\hat{\boldsymbol x}_k$ 可以由这组基的线性组合表示

$$\hat{\boldsymbol x}_k = \sum_{i=1}^d (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) \boldsymbol w_i \tag{2}$$

  要保证最近重构性，即最小化平方误差，优化目标为

$$\begin{aligned} \min \; & \sum_{k=1}^m ||\boldsymbol x_k – \hat{\boldsymbol x}_k||_2^2 \\ \text{s.t.} \; & \underset{\forall i, j}{\boldsymbol w_i^\mathrm{T} \boldsymbol w_j} = \delta_{i,j} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases} \end{aligned} \tag{3}$$

  式 $(3)$ 中的距离可以展开为

$$\begin{aligned} ||\boldsymbol x_k – \hat{\boldsymbol x}_k||_2^2 &= (\boldsymbol x_k – \hat{\boldsymbol x}_k)^\mathrm{T} (\boldsymbol x_k – \hat{\boldsymbol x}_k) \\ &= \boldsymbol x_k^\mathrm{T} \boldsymbol x_k – 2 \boldsymbol x_k^\mathrm{T} \hat{\boldsymbol x}_k + \hat{\boldsymbol x}_k^\mathrm{T} \hat{\boldsymbol x}_k \end{aligned} \tag{4}$$

式 $(4)$ 中的第一项 $\boldsymbol x_k^\mathrm{T} \boldsymbol x_k$ 与 $\boldsymbol W$ 无关的常数。式 $(4)$ 中的第二项可以进一步展开为

$$\begin{aligned} \boldsymbol x_k^\mathrm{T} \hat{\boldsymbol x}_k &= \boldsymbol x_k^\mathrm{T} \sum_{i=1}^d (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) \boldsymbol w_i & （由式 (2)） \\ &= \sum_{i=1}^d (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) \boldsymbol x_k^\mathrm{T} \boldsymbol w_i &（括号内的值为标量）\\ &= \sum_{i=1}^d \boldsymbol w_i^\mathrm{T} \boldsymbol x_k \boldsymbol x_k^\mathrm{T} \boldsymbol w_i \end{aligned} \tag{5}$$

式 $(4)$ 中的第三项可以进一步展开为

$$\begin{aligned} \hat{\boldsymbol x}_k^\mathrm{T} \hat{\boldsymbol x}_k &= \bigg(\sum_{i=1}^d (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) \boldsymbol w_i\bigg)^\mathrm{T} \bigg(\sum_{j=1}^d (\boldsymbol w_j^\mathrm{T} \boldsymbol x_k) \boldsymbol w_j\bigg) \\ &= \sum_{i=1}^d \sum_{j=1}^d \big((\boldsymbol w_i^\mathrm{T} \boldsymbol x_k)\boldsymbol w_i\big)^\mathrm{T} \big((\boldsymbol w_j^\mathrm{T} \boldsymbol x_k)\boldsymbol w_j\big) \end{aligned}$$

上式中 $\boldsymbol w_i^\mathrm{T} \boldsymbol x_k$ 和 $\boldsymbol w_j^\mathrm{T} \boldsymbol x_k$ 都是标量，$\boldsymbol w_i^\mathrm{T} \boldsymbol w_j$ 仅在 $i = j$ 时为 $1$，在 $i \neq j$ 时为 $0$，故上式可以化简为

$$\begin{aligned} \hat{\boldsymbol x}_k^\mathrm{T} \hat{\boldsymbol x}_k &= \sum_{i=1}^d \sum_{j=1}^d (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) (\boldsymbol w_j^\mathrm{T} \boldsymbol x_k) \boldsymbol w_i^\mathrm{T} \boldsymbol w_j \\ &= \sum_{i=1}^d (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) \boldsymbol w_i^\mathrm{T} \boldsymbol w_i \\ &= \sum_{i=1}^d (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) \\ &= \sum_{i=1}^d (\boldsymbol w_i^\mathrm{T} \boldsymbol x_k) (\boldsymbol x_k^\mathrm{T} \boldsymbol w_i) \\ &= \sum_{i=1}^d \boldsymbol w_i^\mathrm{T} \boldsymbol x_k \boldsymbol x_k^\mathrm{T} \boldsymbol w_i \end{aligned} \tag{6}$$

  将式 $(5)$、式 $(6)$ 代入式 $(4)$，可得

$$\begin{aligned} ||\boldsymbol x_k – \hat{\boldsymbol x}_k||_2^2 &= \boldsymbol x_k^\mathrm{T} \boldsymbol x_k – 2 \boldsymbol x_k^\mathrm{T} \hat{\boldsymbol x}_k + \hat{\boldsymbol x}_k^\mathrm{T} \hat{\boldsymbol x}_k \\ &= \boldsymbol x_k^\mathrm{T} \boldsymbol x_k + \sum_{i=1}^d \boldsymbol w_i^\mathrm{T} \boldsymbol x_k \boldsymbol x_k^\mathrm{T} \boldsymbol w_i – 2\sum_{i=1}^d \boldsymbol w_i^\mathrm{T} \boldsymbol x_k \boldsymbol x_k^\mathrm{T} \boldsymbol w_i \\ &= \boldsymbol x_k^\mathrm{T} \boldsymbol x_k – \sum_{i=1}^d \boldsymbol w_i^\mathrm{T} \boldsymbol x_k \boldsymbol x_k^\mathrm{T} \boldsymbol w_i \end{aligned}$$

上式中的 $\sum\limits_{j=1}^d \boldsymbol w_i^\mathrm{T} \boldsymbol x_k \boldsymbol x_k^\mathrm{T} \boldsymbol w_i$ 是 $\boldsymbol W^\mathrm{T} \boldsymbol x_k \boldsymbol x_k^\mathrm{T} \boldsymbol W$ 的迹，$\boldsymbol x_k^\mathrm{T} \boldsymbol x_k$ 是一个常数（记为 $C_k$），有

$$||\boldsymbol x_k – \hat{\boldsymbol x}_k||_2^2 = – \mathrm{tr}(\boldsymbol W^\mathrm{T} \boldsymbol x_k \boldsymbol x_k^\mathrm{T} \boldsymbol W) + C_k \tag{7}$$

于是式 $(3)$ 中最小化的目标

$$\begin{aligned} \sum_{k=1}^m ||\boldsymbol x_k – \hat{\boldsymbol x}_k||_2^2 = – \sum_{k=1}^m \mathrm{tr}(\boldsymbol W^\mathrm{T} \boldsymbol x_k \boldsymbol x_k^\mathrm{T} \boldsymbol W) + \sum_{k=1}^m C_k \end{aligned}$$

其中 $\sum\limits_{i=1}^m C_k$ 仍是常数，又由 $\sum\limits_k \boldsymbol x_k \boldsymbol x_k^\mathrm{T} = \boldsymbol X \boldsymbol X^\mathrm{T}$，式 $(3)$ 的优化问题变为

$$\begin{aligned} \max \; & \mathrm{tr}(\boldsymbol W^\mathrm{T} \boldsymbol X \boldsymbol X^\mathrm{T} \boldsymbol W) \\ \text{s.t.} \; & \boldsymbol W^\mathrm{T} \boldsymbol W = I \end{aligned} \tag{8}$$

  $W$ 中包含 $d$ 个基 $\boldsymbol w_1, \boldsymbol w_2, \dots, \boldsymbol w_d$，对这些基依次求解，对于一个基向量 $\boldsymbol w$，式 $(8)$ 变为

$$\begin{aligned} \max \; & \mathrm{tr}(\boldsymbol w^\mathrm{T} \boldsymbol X \boldsymbol X^\mathrm{T} \boldsymbol w) \\ \text{s.t.} \; & \boldsymbol w^\mathrm{T} \boldsymbol w = 1 \end{aligned} \tag{9}$$

可见这个优化问题与从最大可分性角度得到的问题等价。