[ML Notes] PCA：最近重构性
如前文所述，主成分分析通过将样本点投影到一个超平面上来实现降维，可以从最大可分性或最近重构性两个角度寻找理想的超平面。
从最近重构性的角度考虑，假设数据集有 $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}
$$
可见这个优化问题与从最大可分性角度得到的问题等价。