奇异值分解的一些特性以及应用小案例

1、第一部分:预备知识1.1 矩阵的F-范数与矩阵迹的关系引理:设m nA R,令(ij m n A a =,则2211|(m nT T Fiji j A atr AA tr A A =;其中,(tr 定义如下:令方阵111212122212r r r r rr m m m m m m M m m m =,则11221(r rr iii tr M m m m m =+= ,即矩阵M 的迹。注意,(tr 只能作用于方阵。那么,下面来看下为什么有2211|(m nT T Fiji j A atr AA tr A A =?首先,2211|m nFiji j A a=这个等式是矩阵F-范数的定义,即一个矩

2、阵的F-范数等于矩阵中每个元素的平方和。其次,因111212122212(n n ij m nm m mn a a a a a a A a a a a = ,则112111222212m m T n n mn a a a a a a A a a a =,易得2211(|mnT TijF i j tr AA tr A A aA =。(T AA 或TA A 的第r 个对角元素等于第r行或列元素的平方和,所有对角元素之和就是矩阵每个元素的平方和,即有上式成立。此过程如图1和图2所示。111211121121222122221212n m n m T m m mn n n mn a a a a a a

3、 a a a a a a AA a a a a a a =图1. T AA 方阵迹的形成过程112111112112222212221212m n m n T n n mn m m mn a a a a a a a a a a a a A A a a a a a a =图2. T A A 方阵迹的形成过程1.2 矩阵AB 的迹等于矩阵BA 的迹设m nA R ,n mB R,令(ij m nA a =,(ij n mB b =,则(tr AB tr BA =。分析如下:111212122212(n n ij m nm m mn a a a a a a A a a a a =1112121222

4、12(m m ij n mn n nm b b b b b b B b b b b =图3. 11(mnijjii j tr AB a b=111212122212(m m ij n mn n nm b b b b b b B b b b b =111212122212(n n ij m nm m mn a a a a a a A a a a a =图4. 11(nmji ijj i tr BA b a =第二部分:奇异值分解本部分主要在矩阵奇异值分解(Singular Value Decomposition U SVD =的基础之上,从理论上分析降维之后信息到底损失了多少,以及为什么要选取奇

5、异值最大的那部分矩阵块;紧接着,举个例子来展示取不同奇异值的情况下,信息损失了多少,让大家进一步直观地理解其中的机理。2.1 矩阵U 的奇异值分解:U SVD =设矩阵m nU R(m n >,奇异值分解为:U SVD =;其中,m m S R ,m nV R ,n n D R ,如下式所示:111121111121111212212222212222122212121200000000m m n m m n nn n n mn m m mm n n nn v u u u s s s d d d v u u u s s s d d d v u u u s s s d d d =其中,矩阵

6、S 和D 都是正交矩阵,即T m S S I =,T m SS I =,T n DD I =,T n D D I =,矩阵S和D的行之间相互正交,列之间也相互正交,且行向量为单位向量,列向量也为单位向量。奇异值分解过程如图5所示。 图5. U=SVD矩阵U奇异值分解之后,矩阵V可以分成两块,一个n阶的对角矩阵(对角元素为U的n个奇异值和一个全零矩阵;这样的话,通过矩阵分块理论,可以把奇异值分解简化,如图6所示。 图6. 矩阵分块简化奇异值分解注意,在这里,矩阵U 的奇异值分解我并没有强调V 矩阵的对角元素非要按照从大到小排列,可以是随意的。因此,进一步对矩阵进行分块,将矩阵V 分解成两块对角矩

7、阵,矩阵S 和D 作相应的分块,如图7所示。数学形式如下:111222,V O D U S S O V D =111211222,D S V S O S O S V D =+111222,D S V S V D =111222S V D S V D =+ 图7. 矩阵分块变换奇异值分解形式因1S 和2S 的列向量相互正交,且为单位向量,故有(1,2Ti i S S I i =;同理,1D 和2D 的行向量相互正交,且为单位向量,故有(1,2T i i D D I i =。2.2矩阵U 的近似奇异值分解:111U S V D 在实际应用中,往往通过矩阵的近似分解来达到降维的目的,从而可以进行数据

8、压缩。这样,一方面节省了存储空间,另一方面也将节省计算资源;最重要的一点,在某些应用(如信息检索,文本分类聚类中,可以挖掘数据中潜在的语义结构,继而更深一步探讨事物的本质是什么。但是,矩阵的近似分解会丢失掉一部分信息,怎样分解才能使得信息量丢失的最少同时又有降维的目的呢?定量层面上又丢失多少呢?下面我们来从理论上分析下这些问题。上面已经给出了矩阵U 的奇异值分解形式以及分块后的变形形式(如图7所示。假设将其降到r 维空间下,则有:111U S V D 如图7所示,矩阵U 近似成左边三个矩阵1S ,1V 和1D 的乘积了,具体如图8所示。 图8. 111U S V D 这样的话,就损失了最右边的

9、三个矩阵乘积部分,即222S V D 。那么损失的信息量怎么计算呢?一般可以用矩阵的F-范数来表示。因此,111U S V D 之后损失的信息量为2222|F S V D 。2222222222|(T F S V D tr S V D S V D =222222(T T T tr S V D D V S =2222(T T tr S V V S =2222(T T tr S S V V =22(T tr V V =22211r r n +=+因此,可以看到,损失的信息量即为被“抛弃的奇异值的平方和”!我们知道,奇异值分解后,矩阵V 就是奇异值的“对角矩阵”;如果我们按照奇异值从大到小排列,取前

10、r 个奇异值以及对应的S 和D 矩阵,那么我们就能最大程度上保留原来的信息量,从而减少了信息的损失量。这就是为什么以前总是提“按照奇异值从大到小排列,取前r 个,这样得到的矩阵近似分解信息损失的最小”的说法了,在这里得到了分析和验证。下面我们在看看矩阵原始的信息量是多少?如果猜想一下的话,对,就是所有的奇异值的平方和就是总的信息量!22|(T F F U SVD tr SVD SVD =(T T T tr SVDD V S =(T T tr SVV S =(T T tr S SVV =(T tr VV =22211n =+因此,111U S V D 的信息损失量为22211r r n + ,占

11、总信息量的2221122211r r n n + 。 2.3 例子演示此部分主要是随机举个例子来展示下奇异值分解的结果,以及取不同奇异值的情况下信息的损失情况,看看是不是和理论上推导的结论相一致?理论与例子相结合,进一步加深大家对奇异值分解及其近似的理解。下面随机举个数据矩阵(12,9data ,12行9列,如下所示:100100000101000000110000000011010000011200000010010000010010000001100000010000001000001110000000111000000011data =Matlab 中奇异值分解命令:S,V,D=svd(

12、data 奇异值分解简化命令:S,V,D=svd(data,0 下面通过Matlab代码来展示每当“抛弃”一个奇异值后,其损失量是多少? Matlab代码:svd_sample.m% 清屏及变量clc;clear;% 数据data= 1 0 0 1 0 0 0 0 01 0 1 0 0 0 0 0 01 1 0 0 0 0 0 0 00 1 1 0 1 0 0 0 00 1 1 2 0 0 0 0 00 1 0 0 1 0 0 0 00 1 0 0 1 0 0 0 00 0 1 1 0 0 0 0 00 1 0 0 0 0 0 0 10 0 0 0 0 1 1 1 00 0 0 0 0 0 1

13、 1 10 0 0 0 0 0 0 1 1;% 数据大小m,n=size(data% 奇异值分解S,V,D=svd(data,0% 矩阵分解近似优化len=min(m,n% 损失信息量记录loss=% 对应的奇异值的平方compare=% 奇异值对角化namda=diag(Vfori=1:lenloss=loss,trace(S(:,i*D(i,:*D(i,:'*S(:,i'*namda(i2; compare=compare,namda(i2;end% 输出信息量损失loss% 输出奇异值平方compare% 判断信息损失量是否等于奇异值的平方norm(loss-compar

14、e,2运行结果:loss =11.1615 6.4602 5.5411 2.7045 2.2645 1.7066 0.71560.3138 0.1323compare =11.1615 6.4602 5.5411 2.7045 2.2645 1.7066 0.71560.3138 0.1323ans =8.9841e-015显然,理论分析的结论在例子中得到了验证。第三部分:潜在语义分析模型Latent Semantic Analysis 此部分主要是举个奇异值分解在实际应用中的例子,来展示下矩阵近似分解在降维以及挖掘语义结构方面上的神奇功能。1.1 问题背景传统向量空间模型使用精确的词匹配,即

15、精确匹配用户输入的词与向量空间中存在的词。由于一词多义(polysemy和一义多词(synonymy的存在,使得该模型无法提供给用户语义层面的检索。比如用户搜索“automobile”,即汽车,传统向量空间模型仅仅会返回包含“automobile”单词的页面,而实际上包含“car”单词的页面也可能是用户所需要的。LSA(latent semantic analysis潜在语义分析,也被称为LSI(latent semantic index,是Scott Deerwester, Susan T. Dumais等人在1990年提出来的一种索引和检索方法。该方法主要是用矩阵的奇异值分解来挖掘文档的潜

16、在语义,和传统向量空间模型(vector space model一样使用向量来表示词(terms和文档(documents,并通过向量间的关系(如夹角余弦值来判断词及文档间的关系;而不同的是,LSA将词和文档映射到潜在语义空间,从而去除了原始向量空间中的一些“噪音”,提高了信息检索的精确度。下面是LSA原始Paper里举的一个例子: 图9 文本语料库的观测矩阵:Document-Term Matrix上图是一个Term-Document矩阵,X代表该单词出现在对应的文件里,星号表示该词出现在查询(Query中,当用户输入查询“IDF in computer-based information

17、look up”时,用户是希望查找与信息检索中IDF(文档频率相关的网页,按照精确词匹配的话,文档2和3分别包含查询中的两个词,因此应该被返回,而文档1不包含任何查询中的词,因此不会被返回。但我们仔细看看会发现,文档1中的access, retrieval, indexing, database这些词都是和查询相似度十分高的,其中retrieval和look up是同义词。显然,从用户的角度看,文档1应该是相关文档,应该被返回。再来看文档2:computer information theory,虽然包含查询中的一次词information,但文档2和IDF或信息检索无关,不是用户需要的文档,

18、不应该被返回。从以上分析可以看出,在本次检索中,和查询相关的文档1并未返回给用户,而与查询无关的文档2却返回给了用户。这就是同义词和多义词如何导致传统向量空间模型检索精确度的下降。LSA潜在语义分析的目的,就是要找出词(terms在文档和查询中真正的含义,也就是潜在语义,从而解决上节所描述的问题。具体说来就是对一个大型的文档集合使用一个合理的维度建模,并将词和文档都表示到该空间,比如有2000个文档,包含7000个索引词,LSA使用一个维度为100的向量空间将文档和词表示到该空间,进而在该空间进行信息检索。而将文档表示到此空间的过程就是SVD奇异值分解和降维的过程。降维是LSA分析中最重要的一

19、步,通过降维,去除了文档中的“噪音”,也就是无关信息(比如词的误用或不相关的词偶尔出现在一起,语义结构逐渐呈现。相比传统向量空间,潜在语义空间的维度更小,语义关系更明确。1.2 实例分析假设文档集合如下:c1: Human machine interface for ABC computer applicationsc2: A survey of user opinion of computer system response timec3: the EPS user interface management systemc4: System and human system engineer

20、ing testing of EPSc5: Relation of user perceived response time to error measurement m1: The generation of random, binary, ordered treesm2: The intersection graph of paths in treesm3: Graph minors IV: Widths of trees and well-quasi-orderingm4: Graph minors: A Survey统计的Term-Document矩阵如下: 对其进行奇异值分解: 然后

21、对分解后的矩阵降维,这里保留S的最大两个奇异值,相应的WP矩阵如上图阴影部分,注意P在公式中需要转置。到了这一步后,我们试着将降维后的三个矩阵再乘起来,重新构建X矩阵,看看会有什么效果? 观察X矩阵和矩阵 矩阵可以发现:X中human-C2值为0,因为C2中并不包含human 单词,但是 中human-C2为0.40,表明human 和C2有一定的关系,为什么呢?因为C2:”A survey of user opinion of computer system response time”中包含user 单词,和human 是近似词,因此human-C2的值被提高了。同理还可以分析其他在 中数

22、值改变了的词。第四部分:小结本文档主要在奇异值分解的基础上从理论上分析了矩阵近似降维过程中信息是如何损失的,以及损失了多少,为什么按照奇异值从大到小来选择降维;紧接着,举例来说明理论上分析的结论;最后给出了一个简单的应用案例。X XXé1 1 ù ú A=ê ê1 1 ú ê ë0 0 ú û V = AT A é1 1 ù é1 1 0 ù ê ú = é2 2ù A A=ê 1 1 ú 

23、50; ê ú ê ë1 1 0 û ê0 0 ú ë 2 2 û ë û T | l I - AT A |= l (l - 4 = 0 l1 = 4, l2 = 0 AT Av1 = l1v1 v1 = -1/ 2, -1/ 2T é ê- V = v1 , v2 = ê ê - ê ë 1 2 1 2 - 1 ù 2ú T ú U U = I , VV T = I 1 ú 2 ú û é 1 ù ê- 2 ú ê ú ê 1 ú é 1 A = ê- 2 - 2ú ê 2 ê ú ë ê 0 ú ê ú ë û é -1/ 2 ù ê ú u1 = Av1 / d1 = ê -1/ 2 ú ê 0