2012年12月1日星期六

从奇异值分解(SVD)看潜在语义索引(LSI)


从奇异值分解(SVD)看潜在语义索引(LSI)

 上篇文章简单形象地介绍了LSI 以及LSI 的用途。从中可以看到LSI 的核心运算在于SVD(Singular Value Decomposition),本文希望通过介绍SVD以及LSI对SVD的用法,补充分析 LSI 的本质及对不同问题的适用性。(不过限于本人数学修养有限,并没有对“本质”一挖到底。不过文章末尾的附注留下了足够的向导信息,希望继续探寻数学本质的同学可以依之展开学习)

   1. SVD 简介
    SVD中文称为“奇异值分解”,是一种矩阵分解方法。其公式如下:
    定理:设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 矩阵是我们初始的特征矩阵,在文本挖掘中:A就是 t (term) 行 d (document) 列的矩阵,每列是一篇文章,每行是一个单词,每个单元格的当前单词在当前文章里的出现次数。 U 是一个 t 行 r 列 的矩阵, V 是一个 r 行 d 列 的矩阵, S 是一个 r 行 r 列的对角矩阵。这里 r 的大小是 A的秩。那么U和V中分别是A的奇异向量,而S是A的奇异值。AA'的正交单位特征向量组成U,特征值组成S'S,A'A的正交单位特征向量组成V,特征值(与AA'相同)组成SS'。( 关于秩是什么,特征值是什么,这个分解是怎么得到的,可以暂不去管)
      注意,这个公式是等号,也就是等号左边完全等价于等号右边。换句话说我们只是把原来的A换了一种表示形式而已,并没有丢失任何信息。就好像 24 = 2 * 3 * 4 一样。 也正是因此,如果 LSI 直接使用 SVD 的话,不仅 r 是不可控的,而且 r 很可能很大以至于起不到降维效果,事实上这样做不仅没降维而且耗费了大量的运算时间。而 SVD 作为一种矩阵分解方法,也并非仅仅用在 LSI 中。Matlab中有直接的svd函数可以使用:[U,S,V] = svd(A) 

   2. LSI 对 SVD 的使用
   LSI 对 SVD 做了一点改变,就是对 S 的 r 个对角线元素进行了排序,并只保留前 k 个值 ( k < r ), 后 r - k 个置零。此时,可以证明等式右边是在最小二乘意义下对等式左边的最佳近似。事实上这个过程是把数据集的特征值(在SVD中用奇异值表征)按照重要性排列,降维的过程就是舍弃不重要的特征向量的过程,而剩下的特征向量张成空间为降维后的空间。
   看到这里,我们能得到最重要的启发就是,LSI 是通过舍弃不重要的特征向量来达到降维效果的,而又由于特征向量是根据矩阵运算得出的,因此 LSI 在降维的过程中不仅丢失了信息,而且还改变了信息。降维后的数据集仅仅是对原数据集的一种近似而非等价形式。且降维幅度越大,与原信息的偏离就越大。

  3. LSI 的适用性
  1) 特征降维
   LSI 本质上是把每个特征映射到了一个更低维的子空间(sub space),所以用来做降维可以说是天造地设。在降维这块土地上还有另一位辛勤的耕耘者那就是TFIDF,TFIDF通过一个简单的公式(两个整数相乘)得到不同单词的重要程度,并取前k个最重要的单词,而丢弃其它单词,这里只有信息的丢失,并没有信息的改变。从执行效率上 TFIDF 远远高于 LSI,不过从效果上(至少在学术界)LSI 要优于TFIDF。
   不过必须提醒的是,无论是上述哪一种降维方法,都会造成信息的偏差,进而影响后续分类/聚类的准确率。 降维是希望以可接受的效果损失下,大大提高运行效率和节省内存空间。然而能不降维的时候还是不要降维(比如你只有几千篇文档要处理,那样真的没有必要降维)

  2)单词相关度计算
   LSI 的结果通过简单变换就能得到不同单词之间的相关度( 0 ~ 1 之间的一个实数),相关度非常高的单词往往拥有相同的含义。不过不要被“潜在语义”的名称所迷惑,所谓的潜在语义只不过是统计意义上的相似,如果想得到同义词还是使用同义词词典靠谱。LSI 得到的近义词的特点是它们不一定是同义词(甚至词性都可能不同),但它们往往出现在同类情景下(比如“魔兽” 和 “dota”)。不过事实上直接使用LSI做单词相关度计算的并不多,一方面在于现在有一些灰常好用的同义词词典,另外相对无监督的学习大家还是更信任有监督的学习(分类)得到的结果。

    3)聚类
    直接用 LSI 聚类的情景我还没有见过,但使用该系列算法的后续变种 PLSI, LDA 进行聚类的的确有一些。其中LDA聚类还有些道理(因为它本身就假设了潜在topic的联合概率分布),用 LSI 进行聚类其实并不合适。本质上 LSI 在找特征子空间,而聚类方法要找的是实例分组。 LSI 虽然能得到看起来貌似是聚类的结果,但其意义不见得是聚类所想得到的。一个明显的例子就是,对于分布不平均的样本集(比如新闻类的文章有1000篇,而文学类的文章只有10篇), LSI/PLSI 得到的往往是相对平均的结果(A类500篇,B类600篇),这种情况下根本无法得到好的聚类结果。相对传统聚类方法k-means, LSI 系列算法不仅存在信息的偏差(丢失和改变),而且不能处理分布不均的样本集。
    对于 LSI/PLSI 来说,聚类的意义不在于文档,而在于单词。所以对于聚类的一种变型用法是,当 k 设的足够大时,LSI/PLSI 能够给出落在不同子空间的单词序列,基本上这些单词之间拥有较为紧密的语义联系。其实这种用法本质上还是在利用降维做单词相关度计算。

附注:
本文部分信息来自百度百科。对数学知识感兴趣的同学可以参照以下链接展开阅读:奇异值分解矩阵特征值行列式
Tip: 行列式是一切问题的渊源,如果下图行列式的公式大家看不懂的话,就可以考虑赞不深入探索了:

没有评论:

发表评论