Unsupervised Learning: PCA(Ⅰ)

本文将主要介绍PCA算法的数学推导过程

上一篇文章提到，PCA算法认为降维就是一个简单的linear function，它的input x和output z之间是linear transform，即 $z = W x$ ，PCA要做的，就是根据 $x$ 把W给找出来( $z$ 未知)

PCA for 1-D

为了简化问题，这里我们假设z是1维的vector，也就是把x投影到一维空间，此时w是一个row vector

$z_{1} = w^{1} \cdot x$ ，其中 $w^{1}$ 表示 $w$ 的第一个row vector，假设 $w^{1}$ 的长度为1，即 $| | w^{1} | |_{2} = 1$ ，此时 $z_{1}$ 就是 $x$ 在 $w^{1}$ 方向上的投影

那我们到底要找什么样的 $w^{1}$ 呢？

假设我们现在已有的宝可梦样本点分布如下，横坐标代表宝可梦的攻击力，纵坐标代表防御力，我们的任务是把这个二维分布投影到一维空间上

我们希望选这样一个 $w^{1}$ ，它使得 $x$ 经过投影之后得到的 $z_{1}$ 分布越大越好，也就是说，经过这个投影后，不同样本点之间的区别，应该仍然是可以被看得出来的，即：

我们希望找一个projection的方向，它可以让projection后的variance越大越好
我们不希望projection使这些data point通通挤在一起，导致点与点之间的奇异度消失
其中，variance的计算公式： $V a r (z_{1}) = \frac{1}{N} \sum_{z_{1}} (z_{1} - \bar{z_{1}})^{2}, | | w^{1} | |_{2} = 1$ ， $\bar{z_{1}}$ 是 $z_{1}$ 的平均值

下图给出了所有样本点在两个不同的方向上投影之后的variance比较情况

PCA for n-D

当然我们不可能只投影到一维空间，我们还可以投影到更高维的空间

对 $z = W x$ 来说：

$z_{1} = w^{1} \cdot x$ ，表示 $x$ 在 $w^{1}$ 方向上的投影
$z_{2} = w^{2} \cdot x$ ，表示 $x$ 在 $w^{2}$ 方向上的投影
...

$z_{1}, z_{2}, . . .$ 串起来就得到 $z$ ，而 $w^{1}, w^{2}, . . .$ 分别是 $W$ 的第1,2,...个row，需要注意的是，这里的 $w^{i}$ 必须相互正交，此时 $W$ 是正交矩阵(orthogonal matrix)，如果不加以约束，则找到的 $w^{1}, w^{2}, . . .$ 实际上是相同的值

Lagrange multiplier

求解PCA，实际上已经有现成的函数可以调用，此外你也可以把PCA描述成neural network，然后用gradient descent的方法来求解，这里主要介绍用拉格朗日乘数法(Lagrange multiplier)求解PCA的数学推导过程

注： $w^{i}$ 和 $x$ 均为列向量，下文中类似 $w^{i} \cdot x$ 表示的是矢量内积，而 $(w^{i})^{T} \cdot x$ 表示的是矩阵相乘

calculate $w^{1}$

目标：maximize $(w^1)^TSw^1 $，条件：$ (w^1)^Tw^1=1$

首先计算出 $\bar{z_{1}}$ ：
$\begin{aligned} z_{1} = w^{1} \cdot x \\ \bar{z_{1}} = \frac{1}{N} \sum z_{1} = \frac{1}{N} \sum w^{1} \cdot x = w^{1} \cdot \frac{1}{N} \sum x = w^{1} \cdot \bar{x} \end{aligned}$
然后计算maximize的对象 $V a r (z - 1)$ ：
其中 $C o v (x) = \frac{1}{N} \sum (x - \bar{x}) (x - \bar{x})^{T}$
$\begin{aligned} V a r (z_{1}) & = \frac{1}{N} \sum_{z_{1}} (z_{1} - \bar{z_{1}})^{2} \\ = \frac{1}{N} \sum_{x} (w^{1} \cdot x - w^{1} \cdot \bar{x})^{2} \\ = \frac{1}{N} \sum (w^{1} \cdot (x - \bar{x}))^{2} \\ = \frac{1}{N} \sum (w^{1})^{T} (x - \bar{x}) (x - \bar{x})^{T} w^{1} \\ = (w^{1})^{T} \frac{1}{N} \sum (x - \bar{x}) (x - \bar{x})^{T} w^{1} \\ = (w^{1})^{T} C o v (x) w^{1} \end{aligned}$
当然这里想要求 $V a r (z_{1}) = (w^{1})^{T} C o v (x) w^{1}$ 的最大值，还要加上 $| | w^{1} | |_{2} = (w^{1})^{T} w^{1} = 1$ 的约束条件，否则 $w^{1}$ 可以取无穷大
令 $S = C o v (x)$ ，它是：
- 对称的(symmetric)
- 半正定的(positive-semidefine)
- 所有特征值(eigenvalues)非负的(non-negative)
使用拉格朗日乘数法，利用目标和约束条件构造函数：
$g (w^{1}) = (w^{1})^{T} S w^{1} - α ((w^{1})^{T} w^{1} - 1)$
对 $w^{1}$ 这个vector里的每一个element做偏微分：
$\partial g (w^{1}) / \partial w_{1}^{1} = 0 \partial g (w^{1}) / \partial w_{2}^{1} = 0 \partial g (w^{1}) / \partial w_{3}^{1} = 0 . . .$
整理上述推导式，可以得到：
其中， $w^{1}$ 是S的特征向量(eigenvector)
$S w^{1} = α w^{1}$
注意到满足 $(w^{1})^{T} w^{1} = 1$ 的特征向量 $w^{1}$ 有很多，我们要找的是可以maximize $(w^{1})^{T} S w^{1}$ 的那一个，于是利用上一个式子：
$(w^{1})^{T} S w^{1} = (w^{1})^{T} α w^{1} = α (w^{1})^{T} w^{1} = α$
此时maximize $(w^{1})^{T} S w^{1}$ 就变成了maximize $α$ ，也就是当 $S$ 的特征值 $α$ 最大时对应的那个特征向量 $w^{1}$ 就是我们要找的目标
结论： $w^{1}$ 是 $S = C o v (x)$ 这个matrix中的特征向量，对应最大的特征值 $λ_{1}$

calculate $w^{2}$

在推导 $w^{2}$ 时，相较于 $w^{1}$ ，多了一个限制条件： $w^{2}$ 必须与 $w^{1}$ 正交(orthogonal)

目标：maximize $(w^{2})^{T} S w^{2}$ ，条件： $(w^{2})^{T} w^{2} = 1, (w^{2})^{T} w^{1} = 0$

结论： $w^{2}$ 也是 $S = C o v (x)$ 这个matrix中的特征向量，对应第二大的特征值 $λ_{2}$

同样是用拉格朗日乘数法求解，先写一个关于 $w^{2}$ 的function，包含要maximize的对象，以及两个约束条件
$g (w^{2}) = (w^{2})^{T} S w^{2} - α ((w^{2})^{T} w^{2} - 1) - β ((w^{2})^{T} w^{1} - 0)$
对 $w^{2}$ 的每个element做偏微分：
$\partial g (w^{2}) / \partial w_{1}^{2} = 0 \partial g (w^{2}) / \partial w_{2}^{2} = 0 \partial g (w^{2}) / \partial w_{3}^{2} = 0 . . .$
整理后得到：
$S w^{2} - α w^{2} - β w^{1} = 0$
上式两侧同乘 $(w^{1})^{T}$ ，得到：
$(w^{1})^{T} S w^{2} - α (w^{1})^{T} w^{2} - β (w^{1})^{T} w^{1} = 0$
其中 $α (w^{1})^{T} w^{2} = 0, β (w^{1})^{T} w^{1} = β$ ，
而由于 $(w^{1})^{T} S w^{2}$ 是vector×matrix×vector=scalar，因此在外面套一个transpose不会改变其值，因此该部分可以转化为：
注：S是symmetric的，因此 $S^{T} = S$
$\begin{aligned} (w^{1})^{T} S w^{2} & = ((w^{1})^{T} S w^{2})^{T} \\ = (w^{2})^{T} S^{T} w^{1} \\ = (w^{2})^{T} S w^{1} \end{aligned}$
我们已经知道 $w^{1}$ 满足 $S w^{1} = λ_{1} w^{1}$ ，代入上式：
$\begin{aligned} (w^{1})^{T} S w^{2} & = (w^{2})^{T} S w^{1} \\ = λ_{1} (w^{2})^{T} w^{1} \\ = 0 \end{aligned}$
因此有 $(w^{1})^{T} S w^{2} = 0$ ， $α (w^{1})^{T} w^{2} = 0$ ， $β (w^{1})^{T} w^{1} = β$ ，又根据
$(w^{1})^{T} S w^{2} - α (w^{1})^{T} w^{2} - β (w^{1})^{T} w^{1} = 0$
可以推得 $β = 0$
此时 $S w^{2} - α w^{2} - β w^{1} = 0$ 就转变成了 $S w^{2} - α w^{2} = 0$ ，即
$S w^{2} = α w^{2}$
由于 $S$ 是symmetric的，因此在不与 $w_{1}$ 冲突的情况下，这里 $α$ 选取第二大的特征值 $λ_{2}$ 时，可以使 $(w^{2})^{T} S w^{2}$ 最大
结论： $w^{2}$ 也是 $S = C o v (x)$ 这个matrix中的特征向量，对应第二大的特征值 $λ_{2}$

PCA-decorrelation

$z = W \cdot x$

神奇之处在于 $C o v (z) = D$ ，即z的covariance是一个diagonal matrix，推导过程如下图所示

PCA可以让不同dimension之间的covariance变为0，即不同new feature之间是没有correlation的，这样做的好处是，减少feature之间的联系从而减少model所需的参数量

如果你把原来的input data通过PCA之后再给其他model使用，那这些model就可以使用简单的形式，而无需考虑不同dimension之间类似 $x_{1} \cdot x_{2}, x_{3} \cdot x_{5}^{3}, . . .$ 这些交叉项，此时model得到简化，参数量大大降低，相同的data量可以得到更好的训练结果，从而可以避免overfitting的发生

本文主要介绍的是PCA的数学推导，如果你理解起来有点困难，那下一篇文章将会从另一个角度解释PCA算法的原理~

Unsupervised Learning: PCA(Ⅰ) ​

PCA for 1-D ​

PCA for n-D ​

Lagrange multiplier ​

calculate w1 ​

calculate w2 ​

PCA-decorrelation ​