《《隐性语义索引》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《隐性语义索引》PPT课件.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、现代信息检索 第18讲 隐性语义索引Latent Semantic Indexing2011/11/271现代信息检索 提纲上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用2现代信息检索 提纲上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用3现代信息检索 4层次聚类层次聚类的目标是生成类似于前面提到的Reuters目录的一个层次结构：这个层次结构是自动创建的，可以通过自顶向下或自底向上的方法来实现。最著名的自底向上的方法是层次凝聚式聚类(hierarchical agglomerative clustering，HAC)。4现代信息检索 5 单连接:最大相似度(最短距离)5
2、现代信息检索 6 全连接:最小相似度6现代信息检索 7质心法7现代信息检索 8组平均8现代信息检索 9四种HAC算法的比较方法结合相似度时间复杂度是否最优?注释单连接簇间文档的最大相似度(N2)yes链化效应全连接簇间文档的最小相似度(N2 log N)no对离群点敏感组平均所有文档相似度的平均值(N2 log N)no大部分应用中的最佳选择质心法所有簇间相似度的平均值(N2 log N)no相似度颠倒9现代信息检索 10 簇标签生成的例子文档数目 簇标签生成方法质心互信息标题4622oil plant mexico production crude power000 refinery gas
3、 bpdplant oil productionbarrels crude bpd mexico dolly capacity petroleumMEXICO:HurricaneDolly heads for Mexico coast91017police security russianpeople military peace killed told grozny courtpolice killed militarysecurity peace told troops forces rebels peopleRUSSIA:RussiasLebed meets rebelchief in
4、Chechnya10125900 000 tonnes tradersfutures wheat pricescents september tonnedelivery traders futurestonne tonnes desk wheat prices 000 00USA:Export Business-Grain/oilseeds complex三种方法：选择质心向量中的突出词项，使用MI的差别式标签，使用离质心最近的文档的标题三种方法的结果都不错10现代信息检索 11本讲内容矩阵SVD分解隐性语义索引LSI(Latent Semantic Indexing)LSI在IR中的应用11
5、现代信息检索 提纲上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用12现代信息检索 13回顾一下词项-文档矩阵该矩阵是计算文档和查询相似度的基础，接下来我们要介绍，能否通过对该矩阵进行转换来获得文档和查询之间的一个更好的相似度计算方法？Anthony and CleopatraJulius CaesarTheTempestHamlet OthelloMacbethanthony5.253.180.00.00.00.35brutus1.216.100.01.00.00.0caesar8.59 2.540.01.510.250.0calpurnia0.01.540.00.00.00.0c
6、leopatra2.850.00.00.0 0.00.0mercy1.510.01.900.125.250.88worser1.370.00.114.150.251.95.13现代信息检索 14隐性语义索引LSI简介我们将词项-文档矩阵转换成多个矩阵的乘积这里我们使用的是一个特定的分解方法：奇异值分解(singular value decomposition，简称SVD)SVD:C=UV T(其中 C=词项-文档矩阵)利用SVD分解的结果我们来构造一个新的、改进的词项-文档矩阵 C通过C 我们可以得到一个更好的相似度计算方法(相对于 C而言)为了这种目的使用SVD被称为隐性语义索引(laten
7、t semantic indexing)或者简称 LSI。14现代信息检索 15例子C=UVT:矩阵C 上面给出了一个标准的词项-文档矩阵，为简单起见，这里使用了布尔矩阵。15现代信息检索 16例子 C=UVT:矩阵U 每个词项对应一行，每个min(M,N)对应一列，其中M为词项的数目，N是文档的数目。这是个正交矩阵：(i)列向量都是单位向量；(ii)任意两个列向量之间都是互相正交的。可以想象这些列向量分别代表不同的“语义”维度，比如政治、体育、经济等主题。矩阵元素 uij 给出的是词项i和第j个“语义”维度之间的关系强弱程度。16现代信息检索 17例子 C=UVT:矩阵 这是个min(M,N
8、)min(M,N)的对角方阵。对角线上是矩阵C的奇异值。奇异值的大小度量的是相应“语义”维度的重要性。我们可以通过忽略较小的值来忽略对应的“语义”维度17现代信息检索 18例子C=UVT:矩阵VT每篇文档对应一列，每 min(M,N)对应一行。同样，这也是一个正交矩阵：(i)每个行向量都是单位向量；(ii)任意两个行向量之间都是正交的；同样每个行向量代表的是一个语义维度，矩阵元素vij 代表的是文档 i 和语义维度j的关系强弱程度18现代信息检索 19例子 C=UVT:所有的四个矩阵19现代信息检索 20LSI:小结词项-文档矩阵可以分解成3个矩阵的乘积词项矩阵 U 每个词项对应其中的一个行向
9、量文档矩阵 VT 每篇文档对应其中的一个列向量奇异值矩阵 对角方阵，对角线上的奇异值代表的是每个“语义”维度的重要性接下来我们要介绍这样做的原因。20现代信息检索 提纲上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用21现代信息检索 22为什么在LSI中使用SVD分解最关键的性质：每个奇异值对应的是每个“语义”维度的权重将不太重要的权重置为0，可以保留重要的信息，去掉一些信息“枝节”这些“枝节”可能是：噪音 这种情况下，简化的LSI 噪音更少，是一种更好的表示方法枝节信息可能会使本来应该相似的对象不相似，同样简化的LSI 由于其能更好地表达相似度，因而是一种更优的表示方式“细节越少越
10、好”的一个类比鲜红色花朵的图像红黑花朵的图像如果忽略颜色，将更容易看到两者的相似性22现代信息检索 23将空间维度降为 2实际上，我们只需将矩阵中相应的维度置为0即可。此时，相当于矩阵U 和V T 的相应维度被忽略，然后计算C2=U2V T.23现代信息检索 24维度降为 224现代信息检索 25回顾原始未分解的矩阵 C=UVT25现代信息检索 26原始矩阵 C vs.简化的矩阵 C2=U2VTC2 可以看成矩阵C的一个二维表示。我们将表示的维度缩减至2维。26现代信息检索 27为什么新的低维空间更好？在原始空间中，d2 和d3的相似度为0；但是在新空间下，d2 和 d3的相似度为：0.52*
11、0.28+0.36*0.16+0.72*0.36+0.12*0.20+-0.39*-0.08 0.5227现代信息检索 28为什么新的低维空间更好？“boat”和“ship”语义上相似。低维空间能够反映出这一点。SVD的什么性质会导致相似度计算有所提高？28现代信息检索 提纲上一讲回顾隐性语义索引 空间降维处理LSI 在IR中的应用29现代信息检索 30LSI在IR中使用的原因LSI 能够发现文档的语义上的关联.但是在原始向量空间中这些文档相似度不大(因为它们使用不同的词语).于是通过LSI可以将它们映射到新的低维向量空间中.在新的空间下，两者相似度较高因此，LSI能够解决一义多词(synon
12、ymy)和语义关联问题在标准向量空间下，同义词对文档相似度计算没有任何贡献LSI所期望的效果：同义词对文档相似度贡献很大30现代信息检索 31LSI是如何解决一义多词和语义关联问题的降维迫使我们忽略大量“细节”我们将原始空间下不同的词映射到低维空间的同一维中将同义词映射到同一维的“开销”远小于无关词的聚集SVD选择开销最小的映射方法因此，SVD会将同义词映射到同一维但是，它同时能避免将无关词映射到同一维31现代信息检索 32LSI与其它方法的比较如果查询和文档没有公共词项时，前面我们介绍的相关反馈和查询扩展可以用于提高IR的召回率LSI会提高召回率但是损害正确率因此，它和相关反馈查询扩展解决的
13、是同一问题.同样它们的缺点也一致32现代信息检索 33 LSI实现对词项-文档矩阵进行SVD分解计算在新的低维空间下的文档表示将查询映射到低维空间中上述公式来自：计算 q2 和V2中的所有文档表示的相似度像以往一样按照相似度高低输出文档结果课堂练习：上述做法的最基本问题是什么？33现代信息检索 34 最优性SVD 在下面的意义上说是最优的：保留 k 个最大的奇异值并将其他奇异值置为0，这种做法得到是原始矩阵C的最佳逼近(参考Eckart-Young 定理)最优性：不存在其它同秩的矩阵能够更加逼近C逼近的度量指标F范数(Frobenius norm):于是，LSI 得到最可能的矩阵警告：F范数和文档的余弦相似度之间关系不大。34现代信息检索 35 参考资料信息检索导论第 18 章http:/ifnlp.org/irDeerwester等人写的第一篇LSI的文章Thomas Hofmann提出的概率LSI(PLSI)利用LSI来得到此空间35现代信息检索 36 课后练习习题18-5习题18-1136