【转】SVD分解

分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词，或者说实词的向量，然后求这两个向量的夹角。当这两个向量夹角为零时，新闻就相关；当它们垂直或者说正交时，新闻则无关。当然，夹角的余弦等同于向量的内积。从理论上讲，这种算法非常好。但是计算时间特别长。通常，我们要处理的文章的数量都很大，至少在百万篇以上，二次回标有非常长，比如说有五十万个词（包括人名地名产品名称等等）。如果想通过对一百万篇文章两篇两篇地成对比较，来找出所有共同主题的文章，就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章，完成这一百万篇文章相关性比较就需要十五年时间。注意，要真正完成文章的分类还要反复重复上述计算。

在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（Singular Value Decomposition，简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先，我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章，每一列对应一个词。

在上面的图中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 个词在第 i 篇文章中出现的加权词频（比如，TF/IDF)。读者可能已经注意到了，这个矩阵非常大，有一百万乘以五十万，即五千亿个元素。

奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X，一个一百乘以一百的矩阵B，和一个一百乘以五十万的矩阵Y。这三个矩阵的元素总数加起来也不过1.5亿，仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数量级以上。

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

现在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中的许多概念，比如矩阵的特征值等等，以及数值分析的各种算法就统统用上了。在很长时间内，奇异值分解都无法并行处理。（虽然 Google 早就有了MapReduce 等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。）最近，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，我认为这是 Google 中国对世界的一个贡献。

 

一个mxn矩阵分解为一个mxm的U，一个mxn的S，一个nxn的V，那么mxn为特征值矩阵，奇异值矩阵是把特征值矩阵扩充了好多0，变成一个方阵。

 

SVD分解（奇异值分解），本应是本科生就掌握的方法，然而却经常被忽视。实际上，SVD分解不但很直观，而且极其有用。SVD分解提供了一种方法将一个矩阵拆分成简单的，并且有意义的几块。它的几何解释可以看做将一个空间进行旋转，尺度拉伸，再旋转三步过程。

首先来看一个对角矩阵，

几何上, 我们将一个矩阵理解为对于点 (x, y)从一个平面到另一个平面的映射:

下图显示了这个映射的效果: 平面被横向拉伸了3倍，纵向没有变化。

对于另一个矩阵

它的效果是

这样一个变化并不是很好描述，然而当我们将坐标系旋转45度后，我们可以看出

这时，我们发现这个新的网格上发生的变化和网格在对角阵下发生变化的效果相似。

这是一个对称矩阵的例子，可以看出，对称矩阵经过旋转后，其作用就和对角阵类似了。数学上，对于一个对称矩阵 M, 我们可以找到一组正交向量 v_i 从而 Mv_i 相当于 v_i上的标量乘积; 也就是

Mv_i = λ_iv_i

λ_i 是标量，也就是对应对角阵中对角线上的元素. 由于这个性质，我们称 v_i 是 M 的特征向量;  λ_i 为特征值. 一个对称矩阵不同特征值对应的特征向量是正交的。

对于更广泛的情况，我们看看是否能从一个正交网格转换到另一个正交网格. 考虑一个非对称矩阵:

这个矩阵的效果形象的称为剃刀（shear）。

这个矩阵将网格在水平方向拉伸了，而垂直方向没有变化。如果我们将网格旋转大约58度，这两个网格就又会都变为正交的了。

 

奇异值分解：

考虑一个 2 *2 矩阵, 我们可以找到两组网格的对应关系。用向量表示，那就是当我们选择合适的单位正交向量 v₁ 和 v₂, Mv₁ 和 Mv₂ 也是正交的.

我们使用 u₁ 和 u₂ 代表 Mv₁ 和 Mv₂的方向.  Mv₁ 和 Mv₂ 的长度表示为 σ₁ 和 σ₂，也就是网格在每个方向的拉伸. 这两个拉伸值叫做M的 奇异值（sigular value）

和前面类似，我们可以 有

Mv₁ = σ₁u₁

Mv₂ = σ₂u₂

我们一直讨论的 v₁ 和 v₂ 是一对正交向量， 对于一般的向量 x，我们有这样的投影关系

x = (v₁x) v₁ + (v₂x) v₂

也就是说

Mx = (v₁x) Mv₁ + (v₂x) Mv₂

Mx = (v₁x) σ₁u₁ + (v₂x) σ₂u

即

Mx = u₁σ₁ v₁^Tx + u₂σ₂ v₂^Tx    --->     M = u₁σ₁ v₁^T + u₂σ₂ v₂^T

这个关系可以写成矩阵形式

M = UΣV^T

U 的列是 u₁ 和 u₂, Σ  σ₁ 和 σ₂构成的对角阵,  V 的列是 v₁ 和 v₂.  即V描述了域中的一组正交基，U描述了相关域的另一组正交基，Σ 表述了U中的向量与V中向量的拉伸关系。

寻找奇异值分解

奇异值分解可以应用于任何矩阵，对于前面的例子，如果我们加上一个圆，那它会映射成一个椭圆，椭圆的长轴和短轴定义了新的域中的正交网格，可以被表示为Mv₁ and Mv₂。

换句话说，单位圆上的函数 |Mx| 在  v₁ 取得最大值，在 v₂取得最小值. 这将单位圆上的函数优化问题简化了。可以证明，这个函数的极值点就出现在M^TM的特征向量上，这个矩阵一定是对称的，所以不同特征值对应的特征向量v_i是正交的.

σ_i = |Mv_i|就是奇异值,  u_i 是 Mv_i方向的单位向量.

Mv_i = σ_iu_iMv_j = σ_ju_j. Mv_i Mv_j = v_i^TM^T Mv_j = v_i M^TMv_j = λ_jv_i v_j = 0.

也就是

Mv_i Mv_j = σ_iσ_j u_i u_j = 0

因此, u_i 和 u_j 也是正交的。所以我们就把一组正交基 v_i 变换到了另一组正交基 u_i.

另一个例子

我们来看一个奇异矩阵（秩为1，或只有一个非零奇异值）

它的效果如下

在这个例子中，第二个奇异值为0，所以 M = u₁σ₁ v₁^T. 也就是说，如果有奇异值为0，那么这个矩阵就有降维的效果。因为0奇异值对应的维度就不会出现在右边。这对于计算机科学中的数据压缩极其有用。例如我们想压缩下面的15 25 像素的黑白图像

我们可以看出这个图像中只有三种列，即

把图像表示成一个15 25 的矩阵，总共有 375 个元素.

然而当我们做了奇异值分解，会发现非零奇异值仅有3个，

σ₁ = 14.72， σ₂ = 5.22， σ₃ = 3.31

 因此，这个矩阵就可以被表示为   M=u₁σ₁ v₁^T + u₂σ₂ v₂^T + u₃σ₃ v₃^T

也就是说我们用三个长度为15的向量v_i，三个长度为25的向量u_i，以及三个奇异值，总共123个数字表示了这个375个元素组成的矩阵。奇异值分解找到了矩阵中的冗余信息实现了降维。

可以看出，奇异值分解捕获了图像中的主要信息。因此，又假设上一个例子里引入了噪声，

当我们用同样的方法做奇异值分解，我们得到如下非零奇异值

σ₁ = 14.15，σ₂ = 4.67，σ₃ = 3.00，σ₄ = 0.21，σ₅ = 0.19，...，σ₁₅ = 0.05

显然，前三个奇异值比其他的大很多，说明其中包括了绝大部分信息。如果我们只要前三个，

M u₁σ₁ v₁^T + u₂σ₂ v₂^T + u₃σ₃ v₃^T

我们就实现了图像的降噪。

Noisy image	Improved image