• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

SVD–矩阵奇异值分解

math admin 4年前 (2015-10-07) 3561次浏览 0个评论 扫描二维码

概述

线性代数方法使我们可以将数据分解为很多分量,然后分析其中的主要分量,奇异值分解(SVD)就是其中的一种矩阵分解技术,它是一种有效的代数特征提取方法,深刻揭示了矩阵的内部结构。目前,奇异值分解在信息检索方面的应用主要是隐含语义检索(Latent Semantic Indexing,LSI)。潜在语义索引可以将文档在向量空间模型中的高维表示,投影到低维的潜在语义空间中,这一方面缩小了检索的规模,另一方面也在一定程度上避免了数据的过分稀疏。本文主要根据下文列出的参考文献进行整理,并加入了一些个人理解。

基础概念

SVD 的具体数学定义这里不详细说明了,简单的说一个 mn 的矩阵 A 可以表示为: \[ A=U\Sigma V^T \] 假设 A 是一个 MN 的矩阵,那么得到的 U 是一个 MM 的方阵(里面的向量是正交的,U 里面的向量称为左奇异向量),Σ是一个 MN 的矩阵(除了对角线的元素都是 0,对角线上的元素称为奇异值),\(V^T\)是一个 N * N 的矩阵,里面的向量也是正交的,V 里面的向量称为右奇异向量)。

SVD 的几何意义

我们知道一个矩阵可以看成一个线性变换,因为一个矩阵乘以一个向量后得到的向量,其实就相当于将这个向量进行了线性变换。比如一个二维的对角矩阵: \[ M=\begin{bmatrix} 3 & 0\\ 0 & 1 \end{bmatrix} \] 从几何的角度,平面上的点(x, y)乘以 M 变换成另外一个点(3x, y)。 这种变换的效果如下:平面在水平方向被拉伸了 3 倍,在竖直方向无变化。

此处输入图片的描述

此处输入图片的描述

对角矩阵的变换是有一个很好的特性就是它是解耦的,即它的变换是各个维度相互独立的。如果是一个非对角矩阵,那么它在几何变化方向就不是“正”的 x 和 y 方向了。比如如果 \[ M=\begin{bmatrix} 2 & 1\\ 1 & 2 \end{bmatrix} \] 它的几何变换结果为:

此处输入图片的描述

此处输入图片的描述

很难用简单的语言描述上面图形是如何变换的,因为对于不同的点它的变化方向是不一样的。(x,y)经过变换变为(2x+y,x+2y),点在 x 轴的变化量需要考虑点在 y 轴上的坐标,同理点在 y 轴的变化也要考虑 x 轴的坐标。这种变换 x 和 y 方向是相互耦合的,而在实际问题分析中我们并不希望这种耦合。我们将上面的图片旋转 45 度,得到以下结果:

此处输入图片的描述

此处输入图片的描述

我们发现,现在变换后的图像在 x 轴和 y 轴的变化已经解耦了。

当 A 是方阵时,其奇异值的几何意义是:若 x 是 n 维单位球面上的一点,则 Ax 是一个 n 维椭球面上的点,其中椭球的 n 个半轴长正好是 A 的 n 个奇异值。简单地说,在二维情况下,A 将单位圆变成了椭圆,A 的两个奇异值是椭圆的长半轴和短半轴,如下图(图片来自维基百科):

此处输入图片的描述

此处输入图片的描述

左上表示原来的图像,右上表示经过 M 矩阵变换后的最后图像。这个变换可以分解为 3 步:首先经过 V*矩阵旋转坐标系,然后通过\(\Sigma\)对角矩阵在新的坐标系上进行拉伸(新的坐标系下拉伸方向是解耦的),最后再通过 U 矩阵再进行坐标系旋转,得到最终结果。维基百科对这张图的原文描述如下:

The upper left shows the unit disc in blue together with the two canonical unit vectors. The upper right shows the action of M on the unit disc: it distorts the circle to an ellipse. The SVD decomposes M into three simple transformations: a rotation V*, a scaling Σ along the coordinate axes and a second rotation U. The SVD reveals the lengths σ1 resp. σ2 of the of the semi-major axis resp. semi-minor axis of the ellispe; they are just the singular values which occur as diagonal elements of the scaling Σ. The rotation of the ellipse with respect to the coordinate axes is given by U.

SVD 的意义我觉得可以这么理解:它可以通过对原坐标系进行处理,使得原先相互耦合的变换转换成相互独立维度变换。

SVD 的应用

本小节主要介绍 SVD 在 LSI 的应用。潜在语义索引(LSI),又称为潜在语义分析(LSA),是在信息检索领域提出来的一个概念。主要是在解决两类问题,一类是一词多义,如“bank”一词,可以指银行,也可以指河岸;另一类是一义多词,即同义词问题,如“car”和“automobile”具有相同的含义,如果在检索的过程中,在计算这两类问题的相似性时,依靠余弦相似性的方法将不能很好的处理这样的问题。所以提出了潜在语义索引的方法,利用 SVD 降维的方法将词项和文本映射到一个新的空间。我们用下面的例子进行说明:

此处输入图片的描述

此处输入图片的描述

这就是一个矩阵,不过不太一样的是,这里的一行表示一个词在哪些 title 中出现了,一列表示一个 title 中有哪些词。比如说 T1 这个 title 中就有 guide、investing、market、stock 四个词,各出现了一次。我们将这个矩阵进行 SVD,由于 M 矩阵是 11X9 的矩阵,按照 SVD 分解应该得到一个 11X9 的对角矩阵,即应该有 9 个奇异值。 这 9 个奇异值的能量大小分布如下图:

此处输入图片的描述

此处输入图片的描述

我们发现,大部分能量都集中在前几个奇异值上。这里我们取前 3 个值得到下面的矩阵:

此处输入图片的描述

此处输入图片的描述

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

因此 SVD 可以挖掘出数据中潜在的“重要因素(factor)”。奇异值越大,该 factor 对结果的影响就越大。SVD 可以利用这个特性做用户推荐。反之,如果我们的 M 矩阵是一个杂乱无章的矩阵,我们对该矩阵进行 SVD 分解将会得到相差无几的奇异值,也就无法提取出对结果影响比较大的 factor 了。


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明SVD–矩阵奇异值分解
喜欢 (1)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!