数学之美 系列十八 － 矩阵运算和文本处理中的分类问题
发表者：Google 研究员，吴军
我 在大学学习线性代数时，实在想不出它除了告诉我们如何解线性方程外，还能有什么别的用途。关于矩阵的许多概念，比如特征值等等，更是脱离日常生活。后来在 数值分析中又学了很多矩阵的近似算法，还是看不到可以应用的地方。当时选这些课，完全是为了混学分的学位。我想，很多同学都多多少少有过类似的经历。直到 后来长期做自然语言处理的研究，我才发现数学家们提出那些矩阵的概念和算法，是有实际应用的意义的。
在自然语言处理中，最常见的两类的分 类问题分别是，将文本按主题归类（比如将所有介绍亚运会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种体育运动的名称个归成一类）。这两种苹果耳机功能 分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决这两个问题的，让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。
分 类的关键是计算相关性。我们首先对两个文本计算出它们的内容词，或者说实词的向量，
然后求这两个向量的夹角。当这两个向量夹角为零时，新闻就相关；当它们 垂直或者说正交时，新闻则无关。当然，夹角的余弦等同于向量的内积。从理论上讲，这种算法非常好。但是计算时间特别长。通常，我们要处理的文章的数量都很 大，至少在百万篇以上，二次回标有非常长，比如说有五十万个词（包括人名地名产品名称等等）。如果想通过对一百万篇文章两篇两篇地成对比较，来找出所有共 同主题的文章，就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章，完成这一百万篇文章相关性比较就需要十五年时间。注意，要真正完成文章 的分类还要反复重复上述计算。
在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（Singular Value Decomposition，简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先，我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文 章，每一列对应一个词。
在上面的图中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 个词在第 i 篇文章中出现的加权词频（比如，TF/IDF)13怎么读英语。读者可能已经注意到了，这个矩阵非常大，有一百万乘以五十万，即五千亿个元素。
奇 异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X，一个一百乘以一百的 矩阵B，和一个一百乘以五十万的矩阵Y。这三个矩阵的元素总数加起来也不过1.5亿，仅仅是原来的
三千分之一。相应的存储量和计算量都会小三个数量级以 上。
三 个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越 相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因此， 我们只要对关联矩阵A进行一次奇异值分解，w 我们就可以同时完成了近义词分类和文章的分类。（同时得到每类
文章和每类词的相关性）。
现 在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中的许多概念，比如矩阵的特征值等等，以及数值分析的各种算法就统统用上了。在很长时 间内，奇异值分解都无法并行处理。（虽然 Google 早就有了MapReduce 等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。）最近，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，我认为这是 Google 中国对世界的一个贡献。
------------------------------------------------------------------------
阵的特征值分解和奇异值分解
2008-04-07 20:17定理:（奇异值分解）设A为m*n阶复矩阵，则存在m阶酉阵U和n阶酉阵V，使得:
A = U*S*V’
其中S=diag(σi,σ2,……,σr)，σi>0
(i=1,…,r)，r=rank(A)。
推论：设A为m*n阶实矩阵，则存在m阶正交阵U和n阶正交阵V，使得
A = U*S*V’
其中S=diag(σi,σ2,……,σr)，σi>0
(i=1,…,r)，夜空中最亮的星星r=rank(A)。
1、奇异值分解非常有用，对于矩阵A(m*n)，存在U(m*m)，V(n*n)，S(m*n)，满足A = U*S*V’。U和V中分别是林花谢了春红A的奇异向量，而S是A的奇异值。AA'的正交单位特征向量组成U，
特征值组成S'S，A'A的正交单位特征向量组成V，特征值（与AA'相同）组成SS'。因此，奇异值分解和特征值问题紧密联系。
2、奇异值分解提供了一些关于A的信息，例如非零奇异值的数目（S的阶数）和A的秩相同，一旦秩r房屋证明模板确定，那么U的前r列构成了A的列向量空间的正交基。
关于奇异值分解中当考虑的对象是实矩阵时: S对角元的平方恰为A'A特征值的说明. (对复矩阵类似可得)
从上面我们知道矩阵的奇异值分解为: A=USV, 其中U,V是正交阵(所谓B为正交阵是指B'=B-1, 即B'B=I), S为对角阵.
A'A=V'S'U'USV=V'S'SV=V-1S2V
上式中, 一方面因为S是对角阵, S'S=S2, 且S2对角元就是酒鬼花生S的对角元的平方. 另一方面注意
到A'A是相似与S2的, 因此与S2有相同特征值.公司点评
其实奇异值可以认为是一种特殊的矩阵范数！参考资料：/bingdao89/blog/item/603640dd0e9f52305982dd93.html
----------------------------------------------------------
注：下面的符号和上面的有差异，注意区分
SVD步骤：
1、求AHA或AAH
2、求AHA或AAH的特征值及特征向量x1,x2,...xr， r个特征值组成
3、 U=(x1,x2,...xr)地
4、V1=AU1Δr-1，取V2与其正交，则V=(V1，V2)
则n阶复方阵U的n个列向量是U空间的一个标准正交基,则U是亲情友情爱情U距阵.
一个简单的充分必要判别准则是 方阵U的转置共扼距阵乘以U 等于单位阵,则U是U距阵
正交向量组的性质
定义1 Euclid空间V的一组两两正交的非零向量叫做V的一个正交向量组．
若正交向量组的每一个向量都是单位向量，这个正交组就叫做一个标准正交向量组．
设V是一个n维Euclid空间．若V中n个向量α1，α2，…，αn构成一个正交组，则由定理9.2.1知道这n个向量构成V的一个基．这样的一个基叫做V的一个正交基．若V的一个正交基还是一个标准正交向量组，则称这个基是V的一个标准正交基．
Singular Value Decomposition
The singular value decomposition for a matrix A writes A as a product (hanger)(stretcher)(aligner).
It's an amazing and uful fact that every m x n matrix has a singular value decompositio
n.
The following theorem goes two-thirds of the way to proving this fact:
Two-thirds Theorem
For an matrix and any orthonormal basis of ,
