2 minute read

合着按着我自己的思路才是最好理解的。PCA 的整个过程其实就是:寻找一个基变换 (change of basis),使得新坐标系内的 axes 的功效可以量化。这个量化的意思是,如果新坐标系内有 x’-axis 和 y’-axis,我可以明确地写出 $\frac{\operatorname{effect}(\text{x’-axis})}{\operatorname{effect}(\text{y’-axis})} = \gamma$ 这么一个比值。那么这个量化是怎么做的呢?用的是原数据集沿该 axis 所保留的 covariance matrix。

\[\newcommand{\icol}[1]{ \bigl[ \begin{smallmatrix} #1 \end{smallmatrix} \bigr] } \newcommand{\irow}[1]{ \begin{smallmatrix}(#1)\end{smallmatrix} }\]

第一步:Centering

假设我有 $m$ 个点,每个都是 $n$ 维,所以 $X_{m \times n} = \begin{bmatrix} – (x^{(1)})^T – \newline – (x^{(2)})^T – \newline \dots \newline – (x^{(m)})^T – \end{bmatrix}$

给 $X$ 做一个 column-wise centering:

  1. $\mu_j = \frac{1}{m} \sum_{i=1}^m { x_j^{(i)} }$ (mean of each column)
  2. $x_j^{(i)} = x_j^{(i)} - \mu_j$ (column 整体减去 mean of column)

做完 column-wise centering 之后,才能有 covariance matrix $\Sigma(X) = \frac{1}{m} X X^{T}$ (因为 column 的 mean 等于 0,所以每个 column 的期望 $E[\cdot]$ 小项就不用考虑了)

第二步:假设一个 change of basis (实际并不需要执行这个 change of basis)

当前的 $n$ 个 bases 是 $\hat i = \begin{bmatrix} 1 \newline 0 \newline \vdots \newline 0 \end{bmatrix}, \hat j = \begin{bmatrix} 0 \newline 1 \newline \vdots \newline 0 \end{bmatrix}, \cdots, \hat z = \begin{bmatrix} 0 \newline 0 \newline \vdots \newline 1 \end{bmatrix}$ (必然都是 $n$ 维)。假设有 $B_{n \times n} = \begin{bmatrix} \vert & \vert & \vert & \vert \newline \hat i & \hat j & \vdots & \hat z \newline \vert & \vert & \vert & \vert \end{bmatrix}$

假设变换后的 $n$ 个 bases 是 $\hat{i’}, \hat{j’}, \dots, \hat{z’}$ 且有 $B_{n \times n}’ = \begin{bmatrix} \vert & \vert & \vert & \vert \newline \hat{i’} & \hat{j’} & \vdots & \hat{z’} \newline \vert & \vert & \vert & \vert \end{bmatrix}$

题外话:如果对 $X$ 做基变换的话:假设变换后的坐标是 $X’$,那么 $X’B’ = XB = X \Rightarrow X’ = XB’^{-1}$

  • 注意 $X$ 的 row 才是 coordinates,所以应该是 $XB$ 而不是 $BX$
  • 另外有一点:基变换是 linear transformation,所以 $X’$ 的每个 column 的 mean 仍然为 0 (沿袭第一步 centering 的效果),所以仍然有 $\Sigma(X’) = \frac{1}{m} X’ {X’}^{T}$

第三步:定量 Effect of axis

那我们现在研究:$X$ 在 $\hat{i’}$ 方向上的 covariance 是多少?根据公式:

\[\begin{align} \mathrm{Cov}(X \hat{i'}, X \hat{i'}) &= \frac{1}{m} (X \hat{i'} - \mu_{X \hat{i'}})^T (X \hat{i'} - \mu_{X \hat{i'}}) \newline &= \frac{1}{m} (X \hat{i'})^T X \hat{i'} \newline &= \frac{1}{m} \hat{i'}^T X^T X \hat{i'} \end{align}\]

这就是我们要找的 effect of axis,令 $\operatorname{effect}(\hat{k’}) = \mathrm{Cov}(X \hat{k’}, X \hat{k’})$,所以对任意两个新的 bases $\hat{i’}$ 和 $\hat{j’}$,有:

\[\frac{\operatorname{effect}(\hat{i'})}{\operatorname{effect}(\hat{j'})} = \frac{\hat{i'}^T X^T X \hat{i'}}{\hat{j'}^T X^T X \hat{j'}}\]

第四步:通过 Eigen-decomposition 确定 change of basis

那为了让这个比值有意义,我们可能会想说:如果 $\hat{i’}$ 和 $\hat{j’}$ 是 $X^T X$ 的 eigenvectors 就好办了,那么:

\[\begin{align} \frac{\operatorname{effect}(\hat{i'})}{\operatorname{effect}(\hat{j'})} & = \frac{\hat{i'}^T (X^T X \hat{i'})}{\hat{j'}^T (X^T X \hat{j'}) } \newline & = \frac{\hat{i'}^T (\lambda_{\hat{i'}} \hat{i'})}{\hat{j'}^T (\lambda_{\hat{j'}} \hat{j'}) } \newline & = \frac {\lambda_{\hat{i'}}} {\lambda_{\hat{j'}}} \end{align}\]

那么我们就直接这样做好了!

直接 eigen-decompose $X^T X$:

  • 因为 $X^T X$ 必定 positive semi-definite,所以 eigenvalues 都是 non-negative
  • 最大的 eigenvalue 对应的 eigenvector 的方向,$X$ 所保留的 covariance 最大
  • 第二大的 eigenvalue 对应的 eigenvector 的方向,$X$ 所保留的 covariance 次之
    • 依此类推

注意很多教程写的是方法是去 SVD $\Sigma(X) = \frac{1}{m} X X^{T}$ 或是直接 SVD $X$ (因为一般情况下都是 $m > n$ 所以 $U_{m \times m}$ 应该也能包含 $n$ 个有效的 eigenvalues),换汤不换药。

Comments