奇异值分解

奇异值与特征值基础知识

特征值分解和奇异值分解的目的都是一样，就是提取出一个矩阵最重要的特征。

特征值

如果说一个向量$v$是方阵$A$的特征向量，将一定可以表示成下面的形式：

$$Av=\lambda v$$

特征值分解是将一个矩阵分解成下面的形式：

$$A=Q\Sigma Q^{-1}$$

其中$Q$是这个矩阵$A$的特征向量组成的矩阵，$\Sigma$是一个对角阵，每一个对角线上的元素就是一个特征值。首先，要明确的是，一个矩阵其实就是一个线性变换，因为一个矩阵乘以一个向量后得到的向量，其实就相当于将这个向量进行了线性变换。特征值分解可以得到特征值与特征向量，特征值表示的是这个特征到底有多重要，而特征向量表示这个特征是什么，可以将每一个特征向量理解为一个线性的子空间，我们可以利用这些线性的子空间干很多的事情。不过，特征值分解也有很多的局限，比如说变换的矩阵必须是方阵。

奇异值

在现实的世界中，我们看到的大部分矩阵都不是方阵，比如说有N个学生，每个学生有M科成绩，这样形成的一个$N \times M$的矩阵就不可能是方阵，我们怎样才能描述这样普通的矩阵呢的重要特征呢？奇异值分解可以用来干这个事情，奇异值分解是一个能适用于任意的矩阵的一种分解的方法：

$$A=U\Sigma V^T$$

假设A是一个$N \times M$的矩阵，那么得到的U是一个$N \times N$的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），$\Sigma$是一个$N \times M$的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），$V^T$(V的转置)是一个$N \times N$的矩阵，里面的向量也是正交的，V里面的向量称为右奇异向量），从图片来反映几个相乘的矩阵的大小可得下面的图片

那么奇异值和特征值是怎么对应起来的呢？首先，我们求$A^TA$的特征值：$A^TAv_i=\lambda_iv_i$ 这里得到的$v_i$，就是我们上面的右奇异向量。此外我们还可以得到：

$$\sigma_i=\sqrt{\lambda_i} \\ u_i=\frac{1}{\sigma_i}Av_i$$

这里的$σ$就是上面说的奇异值，$u$就是上面说的左奇异向量。奇异值$σ$跟特征值类似，在矩阵$\Sigma$中也是从大到小排列，而且$σ$的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前$r$大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解：

$$A_{m\times n}\approx U_{m\times r}\Sigma_{r\times r}V_{r \times n}^T$$

$r$是一个远小于m、n的数，这样矩阵的乘法看起来像是下面的样子：

右边的三个矩阵相乘的结果将会是一个接近于A的矩阵，在这儿，$r$越接近于$n$，则相乘的结果越接近于A。而这三个矩阵的面积之和（在存储观点来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵A，我们如果想要压缩空间来表示原矩阵A，我们存下这里的三个矩阵：$U、\Sigma、V$就好了。

奇异值的计算

奇异值的计算是一个难题，是一个$O(N^3)$的算法，其实SVD还是可以用并行的方式去实现的，在解大规模的矩阵的时候，一般使用迭代的方法，当矩阵的规模很大（比如说上亿）的时候，迭代的次数也可能会上亿次，如果使用Map-Reduce框架去解，则每次Map-Reduce完成的时候，都会涉及到写文件、读文件的操作。个人猜测Google云计算体系中除了Map-Reduce以外应该还有类似于MPI的计算模型，也就是节点之间是保持通信，数据是常驻在内存中的，这种计算模型比Map-Reduce在解决迭代次数非常多的时候，要快了很多倍。

Lanczos 迭代就是一种解对称方阵部分特征值的方法，是将一个对称的方程化为一个三对角矩阵再进行求解。

奇异值与主成分分析（PCA）

PCA

PCA 的问题其实是一个基的变换，使得变换后的数据有着最大的方差。方差的大小描述的是一个变量的信息量，我们在讲一个东西的稳定性的时候，往往说要减小方差，如果一个模型的方差很大，那就说明模型不稳定了。但是对于我们用于机器学习的数据（主要是训练数据），方差大才有意义，不然输入的数据都是同一个点，那方差就为0了，这样输入的多个数据就等同于一个数据了。以下面这张图为例子：

这个假设是一个摄像机采集一个物体运动得到的图片，上面的点表示物体运动的位置，假如我们想要用一条直线去拟合这些点，那我们会选择什么方向的线呢？当然是图上标有signal的那条线。如果我们把这些点单纯的投影到x轴或者y轴上，最后在x轴与y轴上得到的方差是相似的（因为这些点的趋势是在45度左右的方向，所以投影到x轴或者y轴上都是类似的），如果我们使用原来的xy坐标系去看这些点，不容易看出来这些点真正的方向是什么。但是如果我们进行坐标系的变化，横轴变成了signal的方向，纵轴变成了noise的方向，则就很容易发现什么方向的方差大，什么方向的方差小了。

一般来说，方差大的方向是信号的方向，方差小的方向是噪声的方向，我们在数据挖掘中或者数字信号处理中，往往要提高信号与噪声的比例，也就是信噪比。对上图来说，如果我们只保留signal方向的数据，也可以对原数据进行不错的近似了。

🌠PCA的全部工作简单点说，就是对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间，这样就从一个N维的空间压缩到$r$维的空间了，但是我们选择的$r$个坐标轴能够使得空间的压缩使得数据的损失最小。

还是假设我们矩阵每一行表示一个样本，每一列表示一个feature，用矩阵的语言来表示，将一个$m \times n$的矩阵A的进行坐标轴的变化，P就是一个变换的矩阵从一个N维的空间变换到另一个N维的空间，在空间中就会进行一些类似于旋转、拉伸的变化:

$$A_{m\times n}P_{n\times n}=\widetilde{A}_{m\times n}$$

而将一个$m \times n$的矩阵A变换成一个$m \times r$的矩阵，这样就会使得本来有n个feature的，变成了有r个feature了（r < n)，这r个其实就是对n个feature的一种提炼，我们就把这个称为feature的压缩。用数学语言表示就是：

$$A_{m\times n}P_{n\times r}=\widetilde{A}_{m\times r}$$

PCA与SVD的关系

之前谈到，SVD得出的奇异向量也是从奇异值由大到小排列的，按PCA的观点来看，就是方差最大的坐标轴就是第一个奇异向量，方差次大的坐标轴就是第二个奇异向量…

SVD近似的式子$A_{m\times n}\approx U_{m\times r}\Sigma_{r\times r}V^{T}{}_{r\times n}$，在矩阵的两边同时右乘矩阵V，可以化成后面的式子

$$A_{m\times n}V_{n\times r}\approx U_{m\times r}\Sigma_{r\times r}V^{T}{}_{r\times n}V_{n\times r} \\ \Rightarrow A_{m\times n}V_{n\times r}\approx U_{m\times r}\Sigma_{r\times r}$$

对比可以看出，其实V就是P，也就是一个变化的向量。这里就是对矩阵的列进行压缩，如果我们想对行进行压缩（在PCA的观点下，对行进行压缩可以理解为，将一些相似的sample合并在一起，或者将一些没有太大价值的sample去掉）。同样，我们写出一个类似的通用的行压缩例子：$P_{r\times m}A_{m\times n}=\widetilde{A}_{r\times n}$。

奇异值与潜在语义索引LSI

潜在语义索引（Latent Semantic Indexing）不是实现了SVD就可以直接用的，不过 LSI 也是一个严重依赖于SVD的算法，之前吴军老师在矩阵计算与文本处理中的分类问题中谈到：

“三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章类之间的相关性。因此，我们只要对关联矩阵A进行一次奇异值分解，我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。”

上面这段话就是LSI的精髓内容，我下面举一个例子来说明一下，下面的例子来自LSA tutorial:

这就是一个矩阵，不过不太一样的是，这里的一行表示一个词在哪些title中出现了（一行就是之前说的一维feature），一列表示一个title中有哪些词，（这个矩阵其实是我们之前说的那种一行是一个sample的形式的一种转置，这个会使得我们的左右奇异向量的意义产生变化，但是不会影响我们计算的过程）。比如说T1这个title中就有guide、investing、market、stock四个词，各出现了一次，我们将这个矩阵进行SVD，得到下面的矩阵：

左奇异向量表示词的一些特性，右奇异向量表示文档的一些特性，中间的奇异值矩阵表示左奇异向量的一行与右奇异向量的一列的重要程序，数字越大越重要。

继续看这个矩阵还可以发现一些有意思的东西，首先，左奇异向量的第一列表示每一个词的出现频繁程度，虽然不是线性的，但是可以认为是一个大概的描述，比如book是0.15对应文档中出现的2次，investing是0.74对应了文档中出现了9次，rich是0.36对应文档中出现了3次；

其次，右奇异向量中一的第一行表示每一篇文档中的出现词的个数的近似，比如说，T6是0.49，出现了5个词，T2是0.22，出现了2个词。

然后我们反过头来看，我们可以将左奇异向量和右奇异向量都取后2维（之前是3维的矩阵），投影到一个平面上，可以得到：

在图上，每一个红色的点，都表示一个词，每一个蓝色的点，都表示一篇文档，这样我们可以对这些词和文档进行聚类，比如说stock 和 market可以放在一类，因为他们老是出现在一起，real和estate可以放在一类，dads，guide这种词就看起来有点孤立了，我们就不对他们进行合并了。按这样聚类出现的效果，可以提取文档集合中的近义词，这样当用户检索文档的时候，是用语义级别（近义词集合）去检索了，而不是之前的词的级别。这样一减少我们的检索、存储量，因为这样压缩的文档集合和PCA是异曲同工的，二可以提高我们的用户体验，用户输入一个词，我们可以在这个词的近义词的集合中去找，这是传统的索引无法做到的。

参考资料

1. A Tutorial on Principal Component Analysis, Jonathon Shlens PCA的主要参考资料
2. http://www.ams.org/samplings/feature-column/fcarc-svd 关于svd的一篇概念好文
3. Singular Value Decomposition and Principal Component Analysis, Rasmus Elsborg Madsen, Lars Kai Hansen and Ole Winther, 2004 跟1）比较类似