奇异值分解（We Recommend a Singular Value Decomposition）
http://www.flickering.cn/nlp/2015/01/%E5%A5%87%E5%BC%82%E5%80%BC%E5%88%86%E8%A7%A3%EF%BC%88we-recommend-a-singular-value-decomposition%EF%BC%89/#jtss-tsina奇异值分解（We Recommend a Singular Value Decomposition） [url=http://www.flickering.cn/nlp/2015/01/%e5%a5%87%e5%bc%82%e5%80%bc%e5%88%86%e8%a7%a3%ef%bc%88we-recommend-a-singular-value-decomposition%ef%bc%89/]2015/01/04[/url][url=http://www.flickering.cn/category/%e6%90%9c%e7%b4%a2%e6%8a%80%e6%9c%af/]搜索技术[/url]、[url=http://www.flickering.cn/category/machine_learning/]机器学习[/url]、[url=http://www.flickering.cn/category/nlp/]自然语言处理[/url][url=http://www.flickering.cn/author/richardsun/]richardsun[/url]
原文作者：[color=#000000]David Austin
原文链接： [url=http://www.ams.org/samplings/feature-column/fcarc-svd]http://www.ams.org/samplings/feature-column/fcarc-svd[/url][/color]
译者：richardsun(孙振龙)
在这篇文章中，我们以几何的视角去观察矩阵奇异值分解的过程，并且列举一些奇异值分解的应用。
[b]介绍[/b]
矩阵奇异值分解是本科数学课程中的必学部分，但往往被大家忽略。这个分解除了很直观，更重要的是非常具有实用价值。譬如，Netflix（在线电影租赁公司）对能够提高其电影推荐系统准确率10%的人提供100万美元的丰厚奖金。令人惊奇的是，这个看似简单的问题却非常具有挑战性，相关的团队正在使用非常复杂的技术解决之，而这些技术的本质都是奇异值分解。
奇异值分解简单来讲，就是以一种方便快捷的方式将我们感兴趣的矩阵分解成更简单且有直观意义的矩阵的乘积。本文以几何的视角去观察奇异值分解的过程，并且列举一些奇异值分解的应用。
[b]线性变换的几何解释[/b]
首先，我们来看一个只有两行两列的简单矩阵。第一个例子是对角矩阵
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image001.gif[/img][/align]从几何的角度，矩阵可以描述为一个变换：用矩阵乘法将平面上的点（x, y）变换成另外一个点（3x, y）：
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image003.gif[/img][/align]这种变换的效果如下：平面在水平方向被拉伸了3倍，在竖直方向无变化。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image005.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image007.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image009.gif[/img][/align]
再看下这个矩阵
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image011.gif[/img][/align]它会产生如下的效果
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image005.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image007.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image015.gif[/img][/align]不过这张图貌似也并没有能够简洁、清晰的描述出上述矩阵变换的几何效果。然而，如果我们把网格旋转45度，再观察一下。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image017.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image007.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image019.gif[/img][/align]
啊哈！我们看到现在这个新的网格被转换的方式与原始的网格被对角矩阵转换的方式是完全一致的：网格在某一方向上被拉伸了3倍。
当然这是一种特殊的结果，因为矩阵[i]M[/i]是对称的，换句话说，[i]M[/i]的转置（通过互换矩阵的对角项得到）还等于[i]M[/i]。如果我们有一个2*2的对称矩阵，可以证明，我们总是可以通过在平面上旋转网格，使得矩阵变换的效果恰好是在两个垂直的方向上对网格的拉伸或镜面反射。换句话说，对称矩阵表现得像对角矩阵一样。
说的更数学化一些，给定一个对称矩阵[i]M[/i]，我们可以找到一组正交向量[b]vi[/b]使得[i]M[/i][b]vi[/b]等于[b]vi[/b]和标量的乘积；那就是
[align=center][i]M[/i][b]vi[/b] = λi[b]vi[/b][/align]
这里λi是标量。从几何意义上讲，这意味着当[b]vi[/b]乘上矩阵[i]M[/i]时被简单地拉伸或者反射了。因为这个性质，我们称[b]vi[/b]是[i]M[/i]的特征向量；标量λi被称为特征值。一个可以被证明的重要的事实是：对称矩阵不同的特征值对应的特征向量是正交的。如果我们把对称矩阵的特征向量和网格对齐，那么矩阵对网格的拉伸或反射的方式，与矩阵对特征向量的拉伸或反射的方式，两者是完全一致的。
上述线性变换的几何解释非常简单：网格在某个方向上被简单地拉伸了。对于更一般的矩阵，我们将要问的问题是： 能否能找到某个正交网格，在矩阵变换之下，变成另一个正交网格？ 让我们最后来考虑一个非对称矩阵的例子：
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image021.gif[/img][/align]这个矩阵产生的几何效果是切变（shear）。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/024.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image008.jpg[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image025.gif[/img][/align]
很容易找到一族沿水平轴的特征向量。但是从上图可以看出，这些特征向量无法把某个正交网格变换到另外一个正交网格。尽管如此，我们先尝试将网格旋转30度，然后看看发生了什么，
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image027.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image008.jpg[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image029.gif[/img][/align]
注意右侧红色平行四边形在原点形成的夹角已经增加。（译者注：这暗示了，如果我们增加旋转角度，平行四边形在原点形成的夹角可能增加到90度，从而变成正交网格。) 接下来将左侧网格旋转到60度：
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image031.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image008.jpg[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image033.gif[/img][/align]
右侧的网格现在几乎是正交的。事实上，如果将左侧网格旋转58.28度，左右两个网格就都是正交的了。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image035.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image008.jpg[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image037.gif[/img][/align]
[b]奇异值分解[/b]
2*2矩阵奇异值分解的几何实质是：对于任意2*2矩阵，总能找到某个正交网格到另一个正交网格的转换与矩阵变换相对应。
用向量解释这个现象：选择适当的正交的单位向量[b]v1[/b]和[b]v2[/b]，向量[i]M[/i][b]v1[/b]和[i]M[/i][b]v2[/b]也是正交的。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/shear.svd.basis.2.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image008.jpg[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/shear.svd.range.basis.2.gif[/img][/align]
用[b]u1[/b]和[b]u2[/b]来表示[i]M[/i][b]v1[/b]和[i]M[/i][b]v2[/b]方向上的单位向量。[i]M[/i][b]v1[/b]和[i]M[/i][b]v2[/b]的长度用σ1 和 σ2来表示——量化了网格在特定方向上被拉伸的效果。σ1 和 σ2被称为[i]M[/i]的奇异值。（在本例中，奇异值就是黄金比例及其倒数，但它在此不是很重要。）
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image039.gif[/img][/align]由此，我们有
[align=center][i]M[/i][b]v1[/b] = σ1[b]u1[/b]
[i]M[/i][b]v2[/b] = σ2[b]u2[/b][/align]
现在给出矩阵[i]M[/i]作用于向量[b]x[/b]的简单描述。因为向量[b]v1[/b]和[b]v2[/b]是正交的单位向量，我们有
[align=center][b]x[/b] = ([b]v1 · [/b][b]x[/b]) [b]v1[/b] + ([b]v2 · [/b][b]x[/b]) [b]v2[/b][/align]
这意味着
[align=center][i]M[/i][b]x[/b] = ([b]v1 · [/b][b]x[/b]) [i]M[/i][b]v1[/b] + ([b]v2 · [/b][b]x[/b]) [i]M[/i][b]v2[/b]
[i]M[/i][b]x[/b] = ([b]v1 · [/b][b]x[/b]) σ1[b]u1[/b] + ([b]v2 · [/b][b]x[/b]) σ2[b]u2[/b][/align]
注意点积可以用向量的转置来计算
[align=center][b]v · x[/b] = [b]v[/b]T[b]x[/b][/align]
我们有
[align=center][i]M[/i][b]x[/b] = [b]u1[/b]σ1 [b]v1[/b]T[b]x[/b] + [b]u2[/b]σ2 [b]v2[/b]T[b]x[/b]
[i]M[/i] = [b]u1[/b]σ1 [b]v1[/b]T + [b]u2[/b]σ2 [b]v2[/b]T[/align]
通常表述成
[align=center]M = [i]U[/i]Σ[i]V[/i]T[/align]
这里[i]U[/i]是列向量[b]u1[/b]和[b]u2[/b]组成的矩阵，Σ是非零项为σ1 和 σ2的对角矩阵，[i]V[/i]是列向量[b]v1[/b]和[b]v2[/b]组成的矩阵。带有上标T的矩阵[i]V[/i]是矩阵[i]V[/i]的转置。
上面描述了怎样将矩阵[i]M[/i]分解成三个矩阵的乘积：[i]V[/i]描述了原始空间中的正交基，[i]U[/i]描述了相关空间的正交基，Σ描述了[i]V[/i]中的向量变成[i]U[/i]中的向量时被拉伸的倍数。
[b]怎样做奇异值分解？[/b]
奇异值分解的魅力在于任何矩阵都可以找到奇异值。怎么做？让我们来看下先前的例子，这回在空间中加入单位圆。在变换后的空间中，单位圆变成了椭圆，其长轴和短轴定义了正交网格。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image042.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image008.jpg[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image044.gif[/img][/align]
注意长轴和短轴用[i]M[/i][b]v1[/b]和[i]M[/i][b]v2[/b]定义。这两个向量因此成为单位圆里的所有向量中最长的和最短的向量。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image046.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image008.jpg[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image048.gif[/img][/align]
换句话讲，单位圆上的向量函数|[i]M[/i][b]x[/b]|在[b]v1[/b]上有最大值而在[b]v2[/b]上有最小值。这就把原始问题简化为了一个标准的微积分问题：我们在单位圆上去优化一个函数的极值。而这个函数的极值点正好恰恰是矩阵[i]MTM[/i]的特征向量。由于该矩阵是对称的，其不同的特征值对应的特征向量之间是正交的。这就产生了向量族[b]vi[/b]。
奇异值通过σi = |[i]M[/i][b]vi[/b]|得到，[b]ui[/b]是[i]M[/i][b]vi[/b]方向上的单位向量。但是[b]ui[/b]之间为什么是正交的呢？
为了解释这个问题，我们假设σi和σj是不同的奇异值。我们有
[align=center][i]M[/i][b]vi[/b] = σi[b]ui[/b]
[i]M[/i][b]vj[/b] = σj[b]uj[/b][/align]
让我们从表达式[i]M[/i][b]vi[/b][i]M[/i][b]vj[/b]开始，为了方便，假定奇异值是非零的。一方面，[i]M[/i][b]vi[/b][i]M[/i][b]vj[/b]是零，因为作为矩阵[i]MTM[/i]的特征向量[b]vi[/b]之间是正交的：
[align=center][i]M[/i][b]vi[/b] · [i]M[/i][b]vj[/b] = [b]vi[/b]T[i]M[/i]T [i]M[/i][b]vj[/b] = [b]vi[/b] · [i]M[/i]T[i]M[/i][b]vj[/b] = λj[b]vi ·[/b] [b]vj[/b] = 0[/align]
另一方面，我们有
[align=center][i]M[/i][b]vi ·[/b] [i]M[/i][b]vj[/b] = σiσj [b]ui ·[/b] [b]uj[/b] = 0[/align]
因此[b]ui[/b]和[b]uj[/b]是正交的，所以我们已经找到能够转换成某个正交向量集[b]ui[/b]的正交向量集[b]vi[/b]。奇异值描述了在不同方向上拉伸的倍数。
在实践中，这不是获得矩阵奇异值分解的步骤，因为这个方法不是特别高效，或者在数值计算中的表现也不够好。
[b]另外一个例子[/b]
让我们看一个奇异矩阵
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image050.gif[/img][/align]矩阵的几何效果如下：
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image052.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image054.jpg[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/image055.gif[/img][/align]在这个例子中，第二个奇异值是零，所以我们可以这样写：
[align=center]M = [b]u1[/b]σ1 [b]v1[/b]T[/align]
换句话讲，如果一些奇异值为零，相应的项将不会出现在[i]M[/i]的分解中。因此，矩阵[i]M[/i]的秩（即线性独立的行或列的个数）等于非零奇异值的个数。
[b]数据压缩[/b]
奇异值分解可以高效的表示数据。例如，假设我们想传送下列图片，包含15*25个黑色或者白色的像素阵列。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image057.gif[/img][/align]因为在图像中只有三种类型的列（如下），它可以以更紧凑的形式被表示。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image058.gif[/img] [img]http://7te9ta.com1.z0.glb.clouddn.com/image059.gif[/img] [img]http://7te9ta.com1.z0.glb.clouddn.com/image060.gif[/img][/align]我们用15*25的矩阵来表示这个图像，其中每个元素非0即1，0表示黑色像素，1表示白色像素。如下所示，共有375个元素。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image061.gif[/img][/align]如果对M进行奇异值分解的话，我们只会得到三个非零的奇异值。
[align=center]σ1 = 14.72
σ2 = 5.22
σ3 = 3.31[/align]
因此，矩阵可以如下表示
[align=center][i]M[/i]=[b]u1[/b]σ1 [b]v1[/b]T + [b]u2[/b]σ2 [b]v2[/b]T + [b]u3[/b]σ3 [b]v3[/b]T[/align]
我们有三个包含15个元素的向量[b]vi[/b]，三个包含25个元素的向量[b]ui[/b]，以及三个奇异值σi。这意味着我们可以只用123个数字就能表示这个矩阵而不是出现在矩阵中的375个元素。在这种方式下，我们看到在矩阵中有3个线性独立的列，也就是说矩阵的秩是3。
[b]降噪[/b]
从之前的例子看出我们利用了矩阵中有很多奇异值为0的特殊性。通常来说，越大的奇异值对应的信息越令人感兴趣。例如，想象我们用扫描仪将上面的图片输入到我们的计算机。但是，我们的扫描机会在图片上产生一些缺陷（通常称作“噪声”）。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image063.gif[/img][/align]我们以同样的方式处理：用15*25矩阵来表示图像，然后进行奇异值分解。我们得到以下奇异值：
[align=center]σ1 = 14.15
σ2 = 4.67
σ3 = 3.00
σ4 = 0.21
σ5 = 0.19
…
σ15 = 0.05[/align]
很明显，头三个奇异值是最重要的，所以我们假定其他的都是图像上的噪声，并假设假设
[align=center][i]M≈[/i][b]u1[/b]σ1 [b]v1[/b]T + [b]u2[/b]σ2 [b]v2[/b]T + [b]u3[/b]σ3 [b]v3[/b]T[/align]
这就产生了如下的优化后的图片
[align=center]Noisy image Improved image[/align]
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image065.gif[/img][img]http://7te9ta.com1.z0.glb.clouddn.com/improve.gif[/img]
[/align][b]数据分析[/b]
我们在收集数据的时候经常会遇到噪声：无论工具多好，总有一些误差在测量过程中。如果我们记得大的奇异值指向矩阵中重要的特征，很自然地想到用奇异值分解去研究被收集的数据。
例如，我们收集了一些数据如下：
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image066.gif[/img][/align]如下是我们获得的数据，将其放入矩阵中：
[table][tr][td]-1.03[/td][td]0.74[/td][td]-0.02[/td][td]0.51[/td][td]-1.31[/td][td]0.99[/td][td]0.69[/td][td]-0.12[/td][td]-0.72[/td][td]1.11[/td][/tr][tr][td]-2.23[/td][td]1.61[/td][td]-0.02[/td][td]0.88[/td][td]-2.39[/td][td]2.02[/td][td]1.62[/td][td]-0.35[/td][td]-1.67[/td][td]2.46[/td][/tr][/table]然后进行奇异值分解。我们得到奇异值
[align=center]σ1 = 6.04
σ2 = 0.22[/align]
其中第一个奇异值远远大于另外一个，很安全的假设小的奇异值σ2是数据中的噪声并且可以理想地认为是0。这个例子中的矩阵的秩是1，意味着所有数据都位于[b]ui[/b]定义的线上。
[align=center][img]http://7te9ta.com1.z0.glb.clouddn.com/image068.gif[/img][/align]这个简短的例子引出了主成分分析领域，展示了一系列用奇异值分解来检测数据依赖和冗余的技术。
同样地，奇异值分解可以用来检测数据中的簇，这就解释了奇异值分解可以用来尝试优化Netflix的电影推荐系统。程序会根据你看过的电影来对与你看过的电影相似的未看过的电影进行排序。推荐系统会挑选出你未看过的电影集合中预估分高的电影。
[b]总结[/b]
如文章的开头所述，奇异值分解应该是本科数学专业线性代数课程的核心部分。除了拥有无比简单的几何解释，奇异值分解提供了将线性代数想法应用于现实的极其有效的技术。然而大家对本科线性代数课程的通常都缺乏足够的重视。
本文可能有点印象派的风格：我的目的是为奇异值分解背后的中心思想提供直观的解释，并通过具体的例子来说明怎么将奇异值分解的思想付诸实践。
[b]References:[/b]
[list][*]Gilbert Strang, [b] Linear Algebra and Its Applications[/b]. Brooks Cole.Strang’s book is something of a classic though some may find it to be a little too formal.[/list][list][*]William H. Press [i]et al[/i], [b]Numercial Recipes in C: The Art of Scientific Computing[/b]. Cambridge University Press.Authoritative, yet highly readable. Older versions [url=http://www.nr.com/oldverswitcher.html]are available online.[/url][/list][list][*]Dan Kalman, [url=http://www.math.umn.edu/%7Elerman/math5467/svd.pdf]A Singularly Valuable Decomposition: The SVD of a Matrix,[/url] [i]The College Mathematics Journal[/i] [b] 27[/b] (1996), 2-23.Kalman’s article, like this one, aims to improve the profile of the singular value decomposition. It also a description of how least-squares computations are facilitated by the decomposition.[/list][list][*][url=http://www.nytimes.com/2008/11/23/magazine/23Netflix-t.html][i]If You Liked This, You’re Sure to Love That[/i][/url], [i]The New York Times[/i], November 21, 2008.This article describes Netflix’s prize competition as well as some of the challenges associated with it.[/list]
页:
[1]