我所理解的SVD与PCA

作者: EternalWang | 来源:发表于2019-01-08 11:30 被阅读0次

Motivation

之所以要写本文，是因为我先在矩阵课上学了SVD，后又在机器学习课上了解到了PCA，当时就觉得两者十分相似，但是一时又难以融会贯通。遂在网上查阅相关资料，然而网上绝大多数文章要么不加思考就转载，要么掺杂着不少谬误。行文语言和逻辑均清晰的更是少有，读完后甚至会更加迷茫。

因而写作此文，期望用较短的篇幅简要说明SVD、PCA以及两者之间的联系，也希望本文能成为讲义级易懂而严谨的文章。

言归正传，首先一句话概括SVD和PCA的联系：对中心化后的样本矩阵做SVD的过程就是PCA。

接下来本文将对SVD与PCA进行简要介绍。

SVD

SVD（Singular Value Decomposition，奇异值分解）就是将任意一矩阵 $A_{n\times m}$ （ $rank(A)>0$ ）分解为三个矩阵相乘的形式，但对这三个矩阵的形式有要求，其过程如下：

（1）求 $A^TA$ 的正特征根： $\lambda _{1},\lambda _{2},...,\lambda _{k}>0$ ,与正交特征向量： $u_{1}\bot u_{2}\bot... \bot u_{k}$

（2）令 $Q=\left(\frac{u_{1}}{\vert u_{1} \vert },\frac{u_{2}}{\vert u_{2} \vert },..., \frac{u_{k}}{\vert u_{k} \vert } \right)_{m\times k}$

（3）令 $P=\left(\frac{Au_{1}}{\vert Au_{1} \vert },\frac{Au_{2}}{\vert Au_{2} \vert },..., \frac{Au_{k}}{\vert Au_{k} \vert } \right)_{n\times k}$

（4）令 $S=\begin{bmatrix} \sqrt{\lambda _{1}} & 0 & \cdots & 0 \\ 0 & \sqrt{\lambda _{2}} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sqrt{\lambda _{k}} \end{bmatrix}_{k\times k}$

对角线元素称为 $A$ 的正奇异值，除此之外， $A$ 还有 $m-k$ 个为0的奇异值。

（5）即得到简奇异值分解： $A=PSQ^T$ 其又称为正奇异值分解

（6）将 $P_{n \times k}$ 扩为正交矩阵（扩充的列应与原有列正交） $W=(P,\tilde{P} )_{n \times n}$

$Q_{m\times k}$ 同样扩为正交矩阵 $V=(Q,\tilde{Q})_{m\times m}$

则得到奇异值分解 $A=W\begin{bmatrix} S & 0 \\ 0 & 0 \end{bmatrix}_{n\times m}V^T$

其实在PCA中，使用到的是简SVD。

PCA

PCA(Principal Component Analysis，主成分分析)顾名思义，就是研究数据所含有的主要成分的方法，常用于矩阵降维。与SVD不同的是，PCA有明确的实际意义，即要尽可能多地保留原数据隐含的信息。其过程如下：

（0）设有 $n$ 条 $m$ 维的数据 $x_{i} \in R^m,i=1,2,...,n$

（1）将这 $n$ 条数据按行组成矩阵 $X_{n\times m}=[x_{1}, x_{2},..., x_{n}]^T$

（2）将 $X$ 进行中心化处理得到 $\hat{X}$ ：即对每一行减去 $\bar{x}^T = \frac{1}{n}{\sum_{i=1}^n{x_{i}^T}}$

（3）求出协方差矩阵 $C_{m\times m} = \frac{1}{n} \hat{X}^T\hat{X}$

这里的因子 $\frac{1}{n}$ 也可省略，并不会影响降维后的结果（因为 $C$ 的特征根虽会等比改变，但特征根的大小关系与其对应的特征向量均不变）。而之所以在这里写出来，是为了和后文PCA的推导部分相对应。

（4）求出 $C$ 的特征根与特征向量

（5）将特征根从大到小排列并取前 $k$ 个 $\lambda _{1}>\lambda _{2}>...>\lambda _{k}$ ，再用这 $k$ 个特征根对应的特征向量组成矩阵 $Q_{m\times k}=\left(\frac{u_{1}}{\vert u_{1} \vert },\frac{u_{2}}{\vert u_{2} \vert },..., \frac{u_{k}}{\vert u_{k} \vert } \right)$ 。

（6） $Y_{n\times k}=XQ$ 的每一行为降到 $k$ 维后的数据

可见，若将SVD中的 $A$ 与PCA当中的 $\hat X$ 对应起来并忽略掉协方差矩阵 $C$ 的因子 $\frac{1}{n}$ ，那么我们就发现了SVD和PCA之间的联系：对中心化后的样本矩阵做SVD的过程就是PCA。

也许读者会有这样的疑惑：为什么协方差矩阵 $C$ 前面有个因子？为什么PCA的计算的过程是上述那样呢？接下来本文将从最小均方误差的角度对PCA的原理进行推导。

最小均方误差指的是：使先降维后升维的新数据与原数据的误差最小。

先定义一组 $m$ 维的标准正交基

$\{u_{i}\},i=1,...,m，u^T_{i}u_{j}=\begin{cases} 1 & \quad \text{if } i=j\\ 0 & \quad \text{if } i\neq j \end{cases}$

每条 $m$ 维的原数据均可以表示为上述基的线性组合

$x_{j}=\sum_{i=1}^m \alpha _{ji}u_{i} \quad (1)$

相当于进行了坐标变换

$\{x_{j1},...,x_{jm}\}\xrightarrow {\{u_{i}\}}\{\alpha _{j1},...,\alpha_{jm}\}$

对 $(1)$ 式等号两侧同左乘 $u_{i}^T$ 易得

$\alpha_{ji}=u_{i}^Tx_{j}=x_{j}^Tu_{i}$

将上式带入 $(1)$ 式得

$x_{j}=\sum_{i=1}^m(x_{j}^Tu_{i})u_{i}$

用 $k$ 个向量近似表示 $x_{j}$ ，即下式的第一个求和部分的权值 $z_{ji}$ 对每个 $x_{j}$ 是不同的，但所有的 $x_{j}$ 共享第二个求和部分的权值 $b_{i}$ 。 $\hat x_{j}$ 就是 $x_{j}$ 先降维后升维得到的新数据。

$x_{j}\approx \hat x_{j}=\sum_{i=1}^k z_{ji}u_{i}+\sum_{i=k+1}^mb_{i}u_{i}$

目标是使失真度（均方误差） $J$ 最小

$\begin{align}J & = \frac{1}{n} \sum_{j=1}^n ||x_{j}- \hat x_{j}||^2\\& =\frac{1}{n} \sum_{j=1}^n (x_{j}- \hat x_{j})^T(x_{j}- \hat x_{j})\\& =\frac{1}{n} \sum_{j=1}^n \left( \sum_{i=1}^k(x^T_{j}u_{i}-z_{ji})^2 + \sum_{i=k+1}^m(x^T_{j}u_{i}-b_{i})^2 \right) \ (2)\end{align}$

$(2)$ 式含有的参数无非是 $u_{i}、z_{ji}、b_{i}$ ，但 $u_{i}$ 和 $z_{ji}、b_{i}$ 的关系可看做“蛋和鸡”的关系：知道了 $u_{i}$ 便能确定权重 $z_{ji}、b_{i}$ ，反之亦然。因而接下来我们不妨先将目标定为通过调整权重 $z_{ji}、b_{i}$ 来求上式的最小值，之后再反过来确定基 $u_{i}$ 。根据多元函数的凸优化理论（本例为2元2次），上式在对各个参数（ $z_{ji}、b_{i}$ ）的导数均为零时取得最小值，因而：

将 $(2)$ 式对参数 $z_{ji}$ 求导,得到如下 $kn$ 个等式

$\frac{\partial J}{\partial z_{ji}}=\frac{2}{n}(z_{ji}-x_{j}^Tu_{i})=0\ (i=1,...,k,\ j=1,...,n)$

易得

$z_{ji}=x_{j}^Tu_{i} \ (i=1,...,k,\ j=1,...,n)$

将 $(2)$ 式对参数 $b_{i}$ 求导，得到如下 $m-k$ 个等式

$\frac{\partial J}{\partial b_{i}}=\frac{2}{n}\sum_{j=1}^n (b_{i}-x_{j}^Tu_{i}) \ (i=k+1,...,m)$

易得

$b_{i}=\frac{1}{n}\sum_{j=1}^nx_{j}^Tu_{i}=\bar {x} ^T u_{i} \ (i=k+1,...,m, \ \bar {x}=\frac {1}{n}\sum_{j=1}^n x_{j})$

因而

$x_{j}-\hat {x}_{j}=\sum_{i=k+1}^m\{(x_{j}-\bar{x} )^Tu_{i}\}u_{i}$

$J = {\frac{1}{n}\sum_{j=1}^n\sum_{i=k+1}^m(x_{j}^Tu_{i}-\bar{x}^Tu_{i})^2} = {\sum_{i=k+1}^m}{u_{i}^T} C u_{i}$

$C$ 为之前出现过的协方差矩阵。由于所求目标为带限制条件（ $u_{i}^Tu_{i}=1$ ）的最优化问题，因而使用拉格朗日乘子法：

$J= {\sum_{i=k+1}^m}{u_{i}^T} C u_{i}+ {\sum_{i=k+1}^m}\lambda_{i}(1-u_{i}^Tu_{i})$

上式为矩阵表达式，其对基向量 $u_{i}$ 求导并化简可得到 $m-k$ 个式子（此处用到了矩阵表达式对向量的求导公式，请读者自行查阅）

$Cu_{i}=\lambda_{i}u_{i}\ (i=k+1,...,m)$

由上式可知， $J$ 的最小值对应协方差矩阵 $C$ 的 $m-k$ 个最小的特征根及其特征向量，对应的失真度为

$J= {\sum_{i=k+1}^m}{u_{i}^T} C u_{i}=\sum_{i=k+1}^m \lambda_{i}$

进一步我们可以得出 $\hat x_{j}=\sum_{i=1}^k z_{ji}u_{i}+\sum_{i=k+1}^mb_{i}u_{i} \ (z_{ji}=x_{j}^Tu_{i}, \ i=1,...,k,\ j=1,...,n)$ 的前 $k$ 个成分 $u_{i}$ 是 $k$ 个最大特征根对应的特征向量，即原数据在最小均方误差目标下的降维后的结果就是 $Y_{n\times k}=XQ\ \left( X_{n\times m}=[x_{1}, x_{2},..., x_{n}]^T,\ Q_{m\times k}=\left(\frac{u_{1}}{\vert u_{1} \vert },\frac{u_{2}}{\vert u_{2} \vert },..., \frac{u_{k}}{\vert u_{k} \vert } \right)\right)$

我所理解的SVD与PCA

Motivation

SVD

PCA

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读