《隐性语义索引》PPT课件.ppt
1,第18讲 隐性语义索引Latent Semantic Indexing,2011/11/27,2,提纲,上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用,3,提纲,上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用,4,4,层次聚类,层次聚类的目标是生成类似于前面提到的Reuters目录的一个层次结构：这个层次结构是自动创建的，可以通过自顶向下或自底向上的方法来实现。最著名的自底向上的方法是层次凝聚式聚类(hierarchical agglomerative clustering，HAC)。,5,5,单连接:最大相似度(最短距离),6,6,全连接:最小相似度,7,7,质心法,8,8,组平均,9,9,四种HAC算法的比较,10,10,簇标签生成的例子,三种方法：选择质心向量中的突出词项，使用MI的差别式标签，使用离质心最近的文档的标题三种方法的结果都不错,11,11,本讲内容,矩阵SVD分解隐性语义索引LSI(Latent Semantic Indexing)LSI在IR中的应用,12,提纲,上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用,13,13,回顾一下词项-文档矩阵,该矩阵是计算文档和查询相似度的基础，接下来我们要介绍，能否通过对该矩阵进行转换来获得文档和查询之间的一个更好的相似度计算方法？,14,14,隐性语义索引LSI简介,我们将词项-文档矩阵转换成多个矩阵的乘积这里我们使用的是一个特定的分解方法：奇异值分解(singular value decomposition，简称SVD)SVD:C=UV T(其中 C=词项-文档矩阵)利用SVD分解的结果我们来构造一个新的、改进的词项-文档矩阵 C通过C 我们可以得到一个更好的相似度计算方法(相对于 C而言)为了这种目的使用SVD被称为隐性语义索引(latent semantic indexing)或者简称 LSI。,15,15,例子C=UVT:矩阵C,上面给出了一个标准的词项-文档矩阵，为简单起见，这里使用了布尔矩阵。,16,16,例子 C=UVT:矩阵U,每个词项对应一行，每个min(M,N)对应一列，其中M为词项的数目，N是文档的数目。这是个正交矩阵：列向量都是单位向量；任意两个列向量之间都是互相正交的。可以想象这些列向量分别代表不同的“语义”维度，比如政治、体育、经济等主题。矩阵元素 uij 给出的是词项i和第j个“语义”维度之间的关系强弱程度。,17,17,例子 C=UVT:矩阵,这是个min(M,N)min(M,N)的对角方阵。对角线上是矩阵C的奇异值。奇异值的大小度量的是相应“语义”维度的重要性。我们可以通过忽略较小的值来忽略对应的“语义”维度,18,18,例子C=UVT:矩阵VT,每篇文档对应一列，每 min(M,N)对应一行。同样，这也是一个正交矩阵：(i)每个行向量都是单位向量；(ii)任意两个行向量之间都是正交的；同样每个行向量代表的是一个语义维度，矩阵元素vij 代表的是文档 i 和语义维度j的关系强弱程度,19,19,例子 C=UVT:所有的四个矩阵,20,20,LSI:小结,词项-文档矩阵可以分解成3个矩阵的乘积词项矩阵 U 每个词项对应其中的一个行向量文档矩阵 VT 每篇文档对应其中的一个列向量奇异值矩阵 对角方阵，对角线上的奇异值代表的是每个“语义”维度的重要性接下来我们要介绍这样做的原因。,21,提纲,上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用,22,22,为什么在LSI中使用SVD分解,最关键的性质：每个奇异值对应的是每个“语义”维度的权重将不太重要的权重置为0，可以保留重要的信息，去掉一些信息“枝节”这些“枝节”可能是：噪音 这种情况下，简化的LSI 噪音更少，是一种更好的表示方法枝节信息可能会使本来应该相似的对象不相似，同样简化的LSI 由于其能更好地表达相似度，因而是一种更优的表示方式“细节越少越好”的一个类比鲜红色花朵的图像红黑花朵的图像如果忽略颜色，将更容易看到两者的相似性,23,23,将空间维度降为 2,实际上，我们只需将矩阵中相应的维度置为0即可。此时，相当于矩阵U 和V T 的相应维度被忽略，然后计算C2=U2V T.,24,24,维度降为 2,25,25,回顾原始未分解的矩阵 C=UVT,26,26,原始矩阵 C vs.简化的矩阵 C2=U2VT,C2 可以看成矩阵C的一个二维表示。我们将表示的维度缩减至2维。,27,27,为什么新的低维空间更好？,在原始空间中，d2 和d3的相似度为0；但是在新空间下，d2 和 d3的相似度为：0.52*0.28+0.36*0.16+0.72*0.36+0.12*0.20+-0.39*-0.08 0.52,28,28,为什么新的低维空间更好？,“boat”和“ship”语义上相似。低维空间能够反映出这一点。SVD的什么性质会导致相似度计算有所提高？,29,提纲,上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用,30,30,LSI在IR中使用的原因,LSI 能够发现文档的语义上的关联.但是在原始向量空间中这些文档相似度不大(因为它们使用不同的词语).于是通过LSI可以将它们映射到新的低维向量空间中.在新的空间下，两者相似度较高因此，LSI能够解决一义多词(synonymy)和语义关联问题在标准向量空间下，同义词对文档相似度计算没有任何贡献LSI所期望的效果：同义词对文档相似度贡献很大,31,31,LSI是如何解决一义多词和语义关联问题的,降维迫使我们忽略大量“细节”我们将原始空间下不同的词映射到低维空间的同一维中将同义词映射到同一维的“开销”远小于无关词的聚集SVD选择开销最小的映射方法因此，SVD会将同义词映射到同一维但是，它同时能避免将无关词映射到同一维,32,32,LSI与其它方法的比较,如果查询和文档没有公共词项时，前面我们介绍的相关反馈和查询扩展可以用于提高IR的召回率LSI会提高召回率但是损害正确率因此，它和相关反馈查询扩展解决的是同一问题.同样它们的缺点也一致,33,33,LSI实现,对词项-文档矩阵进行SVD分解计算在新的低维空间下的文档表示将查询映射到低维空间中上述公式来自：计算 q2 和V2中的所有文档表示的相似度像以往一样按照相似度高低输出文档结果课堂练习：上述做法的最基本问题是什么？,34,34,最优性,SVD 在下面的意义上说是最优的：保留 k 个最大的奇异值并将其他奇异值置为0，这种做法得到是原始矩阵C的最佳逼近(参考Eckart-Young 定理)最优性：不存在其它同秩的矩阵能够更加逼近C逼近的度量指标F范数(Frobenius norm):于是，LSI 得到最可能的矩阵警告：F范数和文档的余弦相似度之间关系不大。,35,35,参考资料,信息检索导论第 18 章http:/ifnlp.org/irDeerwester等人写的第一篇LSI的文章Thomas Hofmann提出的概率LSI(PLSI)利用LSI来得到此空间,36,36,课后练习,习题18-5习题18-11,
