机器学习中的数学(5)——强大的矩阵奇异值分解及其应用，一是通过奇异值分解实现。上一篇是基于特征值分解的解释。在大多数人的印象中，特征值和奇异值往往停留在纯数学计算上。而且，在线性代数或矩阵论中，很少有与特征值和奇异值相关的应用背景。奇异值分解是一种具有明显物理意义的方法。它可以通过将几个更小更简单的子矩阵相乘来表达一个更复杂的矩阵。这些小矩阵描述了矩阵的重要特征。.就像描述一个人一样。向别人形容此人浓眉大眼方脸留胡子戴黑框眼镜。就这么几个特点，让别人的脑海里有了更加生动的形象。清楚认识，其实人脸上有无数种特征。之所以可以这样描述，是因为人天生具有非常好的提取重要特征的能力，从而机器可以学习提取重要特征。SVD是一种重要的方法。在机器学习领域，有相当多的应用可以和奇异值相关，比如特征约简的PCA，数据压缩的算法（以图像压缩为代表），搜索引擎语义层次检索的LSI（LatentSemantic）Indexing)另外，我想在这里吐槽一下。之前百度搜SVD，结果是俄罗斯狙击步枪（AK47同时代），因为穿越火线游戏里有一把叫SVD的狙击步枪。谷歌搜索的时候，奇异值分解全出来了（主要是英文资料）。想玩战争游戏，玩COD不是很好吗？玩盗版CS真的很有意思。国内网页的话语权也被这些没有多少营养的帖子给占了。真心希望国内的气氛能浓一点。搞游戏的很喜欢做游戏，搞数据挖掘的很喜欢挖数据。他们不只是为了吃。谈论超越别人是有道理的。中文文章里，能踏踏实实谈技术的太少了。要改变这种状况，还是从我自己做起吧。前面说了这么多，本文主要针对奇异值的一些特点，也稍微提到了奇异值的计算，但本文不打算过多展开奇异值的计算。另外，本文中还有一些线性代数的知识不是太深。如果你完全忘记了线性代数，可能很难阅读这篇文章。1、奇异值和特征值的基础知识：特征值分解和奇异值分解都是机器学习领域中随处可见的方法。两人关系非常密切。接下来我会讲到。特征值分解和奇异值分解的目的是一样的，都是提取矩阵最重要的特征。先说特征值分解：1）特征值：如果一个向量v是方阵A的特征向量，则必须表示为如下形式：此时，λ称为特征向量v对应的特征值，A矩阵的特征向量集是一组正交向量。特征值分解就是把一个矩阵分解成如下形式：其中Q是这个矩阵A的特征向量组成的矩阵，Σ是对角矩阵，每个对角线元素是一个特征值。我在这里引用一些参考资料来说明。首先要明确一点，一个矩阵其实就是一个线性变换，因为一个矩阵乘以一个向量得到的向量其实就相当于对这个向量进行了一次线性变换。比如下面这个矩阵：它对应的线性变换是下面的形式：因为这个矩阵M乘以一个向量（x,y）的结果是：上面的矩阵是对称的，所以这个变换是一对x,y轴方向的拉伸变换（对角线上的每个元素都会拉伸变换一个维度，值>1时拉长，值<1时缩短），当矩阵不对称时，如果矩阵如下：它所描述的变换如下：这实际上是在平面上的一个轴上的拉伸变换（如蓝色箭头所示），在图中，蓝色的箭头是最重要的变化方向（变化方向可能不止一个）。如果我们想很好地描述一个变换，那么我们可以描述这个变换的主要变化方向。回头看前面的特征值分解公式，分解后的Σ矩阵是一个对角矩阵，里面的特征值是从大到小排列的。这些特征值对应的特征向量描述了这个矩阵的变化方向。（从大变化到小变化排列）当矩阵是高维的时候，那么这个矩阵就是在高维空间中的线性变换。这种线性变化可能无法用图片来表示，但是可以想象，这种Transformation也有很多变换方向。通过特征值分解得到的前N个特征向量对应于该矩阵最重要的N个变换方向。我们可以通过使用前N个变化方向来近似这个矩阵（变换）。也就是我之前说的：提取这个矩阵最重要的特征。综上所述，特征值分解可以得到特征值和特征向量。特征值表示特征的重要程度，特征向量表示特征是什么。每个特征向量都可以理解为一个线性子空间。我们可以利用这些线性子空间来做很多事情。但是特征值分解也有很多局限性，比如变换后的矩阵必须是方阵。（说了这么多特征值变换，不知道讲清楚了没有，请大家多多指教。）2）奇异值：说说奇异值分解。特征值分解是一种很好的提取矩阵特征的方法，但它只适用于方阵。在现实世界中，我们看到的大多数矩阵都不是方阵。比如有N个学生，每个学生有M个科目的成绩，那么这样组成的一个N*M的矩阵不可能是方阵。我们如何描述这样一个普通矩阵的重要特征？可以使用奇异值分解来做到这一点。奇异值分解是一种可以应用于任何矩阵的分解方法：假设A是一个N*M的矩阵，那么得到的U就是一个N*N的方阵（里面的向量是正交的，U里面的向量叫做左奇异向量），Σ是一个N*M矩阵（除了对角线上的元素全为0，对角线上的元素称为奇异值），V'（V的转置）是一个N*N矩阵，里面的向量也是正交的，V里面的向量叫做右奇异向量），从图中反映出几个相乘矩阵的大小可以得到下图中奇异值和特征值是怎么对应的？首先，我们转置一个矩阵A*A，我们将得到一个方阵。我们可以用这个方阵来求特征值：这里得到的v就是我们上面的右奇异向量。此外，我们还可以得到：这里σ是上面提到的奇异值，u是上面提到的左奇异向量。奇异值σ类似于特征值。也是在矩阵Σ中从大到小排列，σ的减小特别快。很多时候，前10%甚至1%的奇异值之和就占了所有的奇异值。总和的99%以上。也就是说，我们也可以用第r个的奇异值来近似描述矩阵。这里我们定义了奇异值分解的一部分：r是一个远小于m和n的数，这样矩阵的乘法看起来像这样：右边三个矩阵相乘的结果将是一个接近于A、这里r越接近n，乘法结果越接近A、这三个矩阵的面积之和（从存储的角度来说，矩阵面积越小，存储容量越小）比原来的矩阵A小很多，如果我们要压缩空间来表示原来的矩阵A，我们就把这里的三个矩阵：U，Σ，V存起来就可以了。2.奇异值的计算：奇异值的计算是一个难题，是一个O(N^3)的算法。当然，在单机的情况下是没有问题的。Matlab可以在一秒内计算出一个1000*1000的矩阵的所有奇异值，但是当矩阵的尺寸变大时，计算的复杂度增加到3次方，这就涉及到了并行计算的需要。谷歌的吴军先生在数学之美系列中谈到SVD时，提到谷歌实现了SVD的并行化算法，说这是对人类的贡献，但他没有给出具体的计算规模，也没有说明提供太多有价值的信息。其实SVD还是可以并行实现的。在求解大规模矩阵时，一般采用迭代法。当矩阵规模很大时（比如上亿），迭代次数也可能上亿。第二，如果使用Map-Reduce框架来解决，每完成一次Map-Reduce，都会涉及到写入和读取文件的操作。个人猜测，除了Map-Reduce，Google云计算系统中应该还有类似MPI的计算模型，即保持节点间通信，数据常驻内存。这种计算模型在解决迭代次数非常多的时候比Map-Reduce快很多倍。Lanczos迭代是一种求解对称方阵的一些特征值的方法（前面说过，求解A'*A得到的对称方阵的特征值是求解A的右奇异向量），就是将a转化为对称方程转化为一个三对角矩阵，然后求解。根据网上的一些文献，谷歌应该是用这种方法来做奇异值分解的。请参阅维基百科上的一些引用论文。如果您了解这些论文，您“几乎”可以制作SVD。由于奇异值的计算是一个非常枯燥的纯数学过程，而之前的研究成果（论文中）几乎已经给出了整个程序的流程图。关于奇异值计算的更多内容会在后面的参考资料中给出，这里就不深入了，还是着重介绍奇异值的应用。3.奇异值和主成分分析（PCA）：上一节也讨论了主成分分析。这里主要讲一下如何用SVD来解决PCA的问题。PCA的问题其实就是对基进行变换，使得变换后的数据方差最大。方差的大小描述了变量的信息量。当我们谈论某事的稳定性时，我们经常说方差应该减少。如果一个模型的方差很大，说明这个模型是不稳定的。但是对于我们用于机器学习的数据（主要是训练数据）来说，具有较大的方差是有意义的。否则，输入数据为同一个点，方差为0，所以多个输入数据等价于一个数据。向上。以下图为例：假设是一个相机拍摄了一张运动中物体的图片，上面的点代表了运动中物体的位置。如果我们要用一条直线去拟合这些点，我们会选择什么方向呢？线路呢？当然是图中标有线的信号。如果我们简单地将这些点投影到x轴或y轴上，最终在x轴和y轴上得到的方差是相似的（因为这些点的趋势是在大约45度的方向上，所以投影到x轴或y轴类似），如果我们用原来的xy坐标系来看这些点，很容易看不出这些点的真正方向是什么。但是如果我们换个坐标系，横轴变成信号的方向，纵轴变成噪声的方向，那么就很容易发现哪个方向方差大，哪个方向方差小。一般来说，方差大的方向是信号方向，方差小的方向是噪声方向。在数据挖掘或数字信号处理中，我们常常需要提高信噪比，即信噪比。对于上图，如果我们只保留信号方向的数据，也可以很好地逼近原始数据。简单来说，PCA的全部工作就是在原空间中依次寻找一组相互正交的坐标轴。第一个轴最大化方差，第二个轴与第一个轴正交。方差在平面内最大，第三轴在与第一轴和第二轴正交的平面内方差最大，所以假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r来逼近这个空间，使得它从一个N维空间压缩到一个r维空间，但是我们选择的r个坐标轴可以让空间压缩最小化数据的损失。仍然假设我们矩阵的每一行代表一个样本，每一列代表一个特征，用矩阵的语言来表达。在坐标轴上变换一个m*n的矩阵A，P是从N维空间变换而来的矩阵。变换到另一个N维空间，会在空间中进行一些类似旋转和拉伸的变化。而将一个m*n的矩阵A转化为一个m*r的矩阵，这会让原来的n个特征变成r个特征（r
