《lecture7-system-第7讲--完整搜索系统中的评分计算-现代信息检索导论-教学ppt课件》由会员分享，可在线阅读，更多相关《lecture7-system-第7讲--完整搜索系统中的评分计算-现代信息检索导论-教学ppt课件（93页珍藏版）》请在装配图网上搜索。
1、Introduction to Information Retrieval 现代信息检索现代信息检索中科院研究生院2011年秋季课程现代信息检索 更新时间：Modern Information Retrieval授课人：王斌http:/ introduction to Information retrieval”网上公开的课件，地址 http:/nlp.stanford.edu/IR-book/第7讲 完整搜索系统中的评分计算Scores in a complete search system2011/10/091现代信息检索 提纲上一讲回顾上一讲回顾 结果排序的动机结果排序的动机再论余弦相似
2、度再论余弦相似度结果排序的实现结果排序的实现完整的搜索系统完整的搜索系统2现代信息检索 提纲上一讲回顾上一讲回顾 结果排序的动机结果排序的动机再论余弦相似度再论余弦相似度结果排序的实现结果排序的实现完整的搜索系统完整的搜索系统3 现代信息检索词项频率tft 在 d 中的对数词频权重定义如下：文档-词项的匹配得分t qd(1+log tft,d)4 现代信息检索idf权重dft 是出现词项t的文档数目dft 是和词项t的信息量成反比的一个值于是可以定义词项t的idf权重:(其中N 是文档集中文档的数目)idft 是反映词项t的信息量的一个指标5 现代信息检索tf-idf权重计算词项的tf-idf
3、权重是tf权重和idf权重的乘积信息检索中最出名的权重计算方法之一6 现代信息检索查询和文档之间的余弦相似度计算qi 是第i 个词项在查询q中的tf-idf权重di是第i 个词项在文档d中的tf-idf权重 和 分别是 和 的长度上述公式就是 和 的余弦相似度，或者说向量 和 夹角的余弦 7 现代信息检索余弦相似度计算的图示8 现代信息检索tf-idf 计算样例:lnc.ltn最终结果 0+0+1.04+2.04=3.089 现代信息检索本讲内容排序的重要性：从用户的角度来看(Google的用户研究结果)另一种长度归一化:回转(Pivoted)长度归一化排序实现完整的搜索系统10现代信息检索
4、提纲上一讲回顾上一讲回顾 结果排序的动机结果排序的动机再论余弦相似度再论余弦相似度结果排序的实现结果排序的实现完整的搜索系统完整的搜索系统11 现代信息检索排序的重要性上一讲:不排序的问题严重性用户只希望看到一些而不是成千上万的结果很难构造只产生一些结果的查询即使是专家也很难 排序能够将成千上万条结果缩减至几条结果，因此非常重要接下来:将介绍用户的相关行为数据实际上，大部分用户只看1到3条结果12 现代信息检索检索效果的经验性观察方法如何度量排序的重要性？可以在某种受控配置观察下搜索用户的行为对用户行为进行录像让他们放声思考Ask them to“think aloud”访谈眼球跟踪计时记录并
5、对他们的点击计数下面的讲义来自Dan Russell在JCDL会议上的讲话Dan Russell是Google的“ber Tech Lead for Search Quality&User Happiness“13现代信息检索 14用户访谈14现代信息检索 15用户对结果的浏览模式15现代信息检索 16检索中的用户行为模式16现代信息检索 17用户浏览的链接数17现代信息检索 18浏览 vs.点击18现代信息检索 结果显示顺序对行为的影响19 现代信息检索排序的重要性:小结摘要阅读(Viewing abstracts):用户更可能阅读前几页(1,2,3,4)的结果的摘要点击(Clicking)
6、:点击的分布甚至更有偏向性一半情况下，用户点击排名最高的页面即使排名最高的页面不相关，仍然有30%的用户会点击它。正确排序相当重要 排对最高的页面非常重要20现代信息检索 提纲上一讲回顾上一讲回顾 结果排序的动机结果排序的动机再论余弦相似度再论余弦相似度结果排序的实现结果排序的实现完整的搜索系统完整的搜索系统21 现代信息检索距离函数不适合度量相似度尽管查询q和文档d2的内容很相似，但是向量 和 的 欧氏距离缺很大。这也是为什么要进行长度归一化的原因，或者说，我们前面采用余弦相似度的原因。22 现代信息检索课堂练习：余弦相似度的一个问题查询 q:“anti-doping rules Beiji
7、ng 2008 olympics”反兴奋剂计算并比较如下的三篇文档d1:一篇有关”anti-doping rules at 2008 Olympics”的短文档d2:一篇包含d1 以及其他5篇新闻报道的长文档，其中这5篇新闻报道的主题都与Olympics/anti-doping无关d3:一篇有关”anti-doping rules at the 2004 Athens Olympics“的短文档我们期望的结果是什么？如何实现上述结果？23 现代信息检索回转归一化余弦归一化对倾向于短文档，即对短文档产生的归一化因子太大，而平均而言对长文档产生的归一化因子太小于是可以先找到一个支点(pivot，平
8、衡点)，然后通过这个支点对余弦归一化操作进行线性调整。效果：短文档的相似度降低，而长文档的相似度增大这可以去除原来余弦归一化偏向短文档的问题24现代信息检索 25预测相关性概率 vs.真实相关性概率25现代信息检索 26回转归一化(Pivot normalization)26 现代信息检索回转归一化:Amit Singhal的实验结果 结果第一行：返回的相关文档数目 结果第二行：平均正确率 结果第三行：平均正确率的提高百分比27 现代信息检索Amit Singhal 1989年本科毕业于印度IIT(Indian Institute of Technology)Roorkee分校1996年博士毕
9、业于Cornell University，导师是Gerard Salton其论文获得1996年SIGIR Best Student Paper Award2000年加入Google，2001年被授予Google Fellow称号Google 排序团队负责人,被财富杂志(Fortune,2010)誉为世界科技界最聪明的50个人之一28现代信息检索 提纲上一讲回顾上一讲回顾 结果排序的动机结果排序的动机再论余弦相似度再论余弦相似度结果排序的实现结果排序的实现完整的搜索系统完整的搜索系统29 现代信息检索词项频率tf也存入倒排索引中当然也需要位置信息，上面没显示出来30 现代信息检索倒排索引中的词项
10、频率存储每条倒排记录中，除了docIDd 还要存储tft,d通常存储是原始的整数词频，而不是对数词频对应的实数值这是因为实数值不易压缩对tf采用一元码编码效率很高为什么?总体而言，额外存储tf所需要的开销不是很大：采用位编码压缩方式，每条倒排记录增加不到一个字节的存储量或者在可变字节码方式下每条倒排记录额外需要一个字节即可31 现代信息检索余弦相似度计算算法32 现代信息检索例子BrutusBrutusCaesarCaesarCalpurniaCalpurnia123581321 342481632 6412813 16AntonyAntony3481632 64128328881616163
11、23232 现代信息检索精确top K检索及其加速办法目标：从文档集的所有文档中找出K 个离查询最近的文档(一般)步骤：对每个文档评分(余弦相似度)，按照评分高低排序，选出前K个结果如何加速：思路一：加快每个余弦相似度的计算思路二：不对所有文档的评分结果排序而直接选出Top K篇文档思路三：能否不需要计算所有篇文档的得分？现代信息检索精确top K检索加速方法一：快速计算余弦检索排序就是找查询的K近邻一般而言，在高维空间下，计算余弦相似度没有很高效的方法但是如果查询很短，是有一定办法加速计算的，而且普通的索引能够支持这种快速计算 现代信息检索特例 不考虑查询词项的权重查询词项无权重相当于假设每
12、个查询词项都出现1次于是，不需要对查询向量进行归一化于是可以对上一讲给出的余弦相似度计算算法进行轻微的简化Sec.7.136 现代信息检索快速余弦相似度计算:无权重查询 现代信息检索前面的例子BrutusBrutusCaesarCaesarCalpurniaCalpurnia123581321 342481632 6412813 16AntonyAntony3481632 641283288816161632323238 现代信息检索精确top k检索加速方法二：堆法N中选K检索时，通常只需要返回前K条结果可以对所有的文档评分后排序，选出前K个结果，但是这个排序过程可以避免令 J=具有非零余弦
13、相似度值的文档数目从J中选K个最大的 现代信息检索堆方法堆：二叉树的一种，每个节点上的值 子节点上的值(Max Heap)堆构建：需要 2J 次操作选出前K个结果：每个结果需要2log J 步如果 J=1M,K=100,那么代价大概是全部排序代价的10%1.9.3.8.3.1.140 现代信息检索(最大)堆构建样例(筛选shift法-摘自网上课件)7，10，13，15，4，20，19，8（数据个数n=8）。现代信息检索 现代信息检索 现代信息检索利用堆选出Top K(=4)现代信息检索 现代信息检索 现代信息检索 现代信息检索 现代信息检索精确top K检索加速方法三：提前终止计算到目前为止的
14、倒排记录表都按照docID排序接下来将采用与查询无关的另外一种反映结果好坏程度的指标(静态质量)例如:页面d的PageRank g(d),就是度量有多少好页面指向d的一种指标(参考第 21章)于是可以将文档按照PageRank排序 g(d1)g(d2)g(d3).将PageRank和余弦相似度线性组合得到文档的最后得分 net-score(q,d)=g(d)+cos(q,d)49 现代信息检索提前终止计算假设:(i)g 0,1;(ii)检索算法按照d1,d2,，依次计算(为文档为单位的计算，document-at-a-time)，当前处理的文档的 g(d)1.2由于后续文档的得分不可能超过1.
15、1(cos(q,d)1)所以，我们已经得到了top K结果，不需要再进行后续计算50 现代信息检索精确top K检索的问题仍然无法避免大量文档参与计算一个自然而言的问题就是能否尽量减少参与计算文档数目，即使不能完全保证正确性也在所不惜。即采用这种方法得到的top K虽然接近但是并非真正的top K-非精确top K检索51 现代信息检索非精确top K检索的可行性检索是为了得到与查询匹配的结果，该结果要让用户满意余弦相似度是刻画用户满意度的一种方法非精确top K的结果如果和精确top K的结果相似度相差不大，应该也能让用户满意52 现代信息检索一般思路找一个文档集合A，K|A|N，利用A中的
16、top K结果代替整个文档集的top K结果即给定查询后，A是整个文档集上近似剪枝得到的结果上述思路不仅适用于余弦相似度得分，也适用于其他相似度计算方法53 现代信息检索方法一：索引去除(Index elimination)一般检索方法中，通常只考虑至少包含一个查询词项的文档可以进一步拓展这种思路只考虑那些包含高idf查询词项的文档只考虑那些包含多个查询词项的文档(比如达到一定比例，3个词项至少出现2个，4个中至少出现3个等等)现代信息检索仅考虑高idf词项对于查询 catcher in the rye仅考虑包含catcher和rye的文档的得分直觉：文档当中的in 和 the不会显著改变得分
17、因此也不会改变得分顺序优点:低idf词项会对应很多文档，这些文档会排除在集合A之外55 现代信息检索仅考虑包含多个词项的文档Top K的文档至少包含一个查询词项对于多词项查询而言，只需要计算包含其中大部分词项的文档比如，至少4中含3这相当于赋予了一种所谓软合取(soft conjunction)的语义(早期Google使用了这种语义)这种方法很容易在倒排记录表合并算法中实现如何如何实实现现?现代信息检索4中含3BrutusBrutusCaesarCaesarCalpurniaCalpurnia123581321 342481632 6412813 16AntonyAntony3481632 6
18、412832888161616323232仅对文档8、16和 32进行计算 现代信息检索方法二：胜者表(Champion list)对每个词项t，预先计算出其倒排记录表中权重最高的r篇文档，如果采用tfidf机制，即tf最高的r篇这r篇文档称为t的胜者表也称为优胜表(fancy list)或高分文档(top docs)注意：r 比如在索引建立时就已经设定因此，有可能 r g(d2)g(d3).计算文档的某个组合得分 net-score(q,d)=g(d)+cos(q,d)在这种机制下，能够在扫描倒排记录表时提前结束计算76现代信息检索 77以文档为单位(Document-at-a-time)的
19、处理按照docID排序和按照PageRank排序都与词项本身无关(即两者都是文档的固有属性)，因此在全局这种序都是一致的。上述计算余弦相似度的方法可以采用以文档为单位的处理方式。即在开始计算文档di+1 的得分之前，先得到文档di 的得分。另一种方式:以词项为单位(term-at-a-time)的处理77现代信息检索 78以词项为单位(Term-at-a-time)的处理方式最简单的情况：对第一个查询词项，对它的倒排记录表进行完整处理对每个碰到的docID设立一个累加器然后，对第二个查询词项的倒排记录表进行完整处理.如此循环往复78现代信息检索 79以词项为单位(Term-at-a-time)
20、的处理算法79现代信息检索 80余弦得分的计算对于Web来说(200亿页面),在内存中放置包含所有页面的累加器数组是不可能的因此，仅对那些出现在查询词项倒排记录表中的文档建立累加器这相当于，对那些得分为0的文档不设定累加器(即那些不包含任何查询词项的文档)80现代信息检索 81累加器举例查询:Brutus Caesar:仅为文档 1,5,7,13,17,83,87设立累加器不为文档 8,40,85 设立累加器81现代信息检索 82瓶颈的消除可以使用前面讨论的堆/优先队列结构可以进一步将文档限制在那些在包含高idf值的非零得分文档或者强制执行一个与查询(类似Google):在每个查询词项上都要得
21、到非零余弦相似度值例子:为Brutus Caesar仅建立一个累加器这是因为仅有d1 同时包含这两个词82现代信息检索 提纲上一讲回顾上一讲回顾 结果排序的动机结果排序的动机再论余弦相似度再论余弦相似度结果排序的实现结果排序的实现完整的搜索系统完整的搜索系统83现代信息检索 84完整的搜索系统示意图84现代信息检索 85多层次索引基本思路:建立多层索引，每层对应索引词项的重要性查询处理过程中，从最高层索引开始如果最高层索引已经返回至少k(比如,k=100)个结果，那么停止处理并将结果返回给用户如果结果 k 篇文档，那么从下一层继续处理，直至索引用完或者返回至少k 个结果为止例子：两层的系统第1
22、层:所有标题的索引第2层:文档剩余部分的索引标题中包含查询词的页面相对于正文包含查询词的页面而言，排名更应该靠前85现代信息检索 86多层次索引的例子86现代信息检索 87多层次索引大家相信，Google(2000/01)搜索质量显著高于其他竞争者的一个主要原因是使用了多层次索引(当然还有PageRank、锚文本以及邻近限制条件的使用)87现代信息检索 88搜索系统组成部分(已介绍)文档预处理(语言及其他处理)位置信息索引多层次索引拼写校正k-gram索引(针对通配查询和拼写校正)查询处理文档评分以词项为单位的处理方式88现代信息检索 89搜索系统组成部分(未介绍)文档缓存(cache):用它
23、来生成文档摘要(snippet)域索引：按照不同的域进行索引，如文档正文，文档中所有高亮的文本，锚文本、元数据字段中的文本等等基于机器学习的排序函数邻近式排序(如,查询词项彼此靠近的文档的得分应该高于查询词项距离较远的文档)查询分析器89现代信息检索 90向量空间检索与其他方法的融合如何将短语检索和向量空间检索融合在一起？我们不想对每个短语都计算其idf值，为什么？如何将布尔检索和向量空间检索融合在一起？例如:“+”-限制条件和“-”-限制条件后过滤很简单，但是效率低下-没有好的解决办法如何将通配符查询融入到向量空间检索中？同样，没有好的解决方法90现代信息检索 91本讲内容排序的重要性：从用
24、户的角度来看(Google的用户研究结果)另一种长度归一化:回转(Pivoted)长度归一化排序实现完整的搜索系统91现代信息检索 92参考资料信息检索导论第6、7 章http:/ifnlp.org/irHow Google tweaks its ranking functionInterview with Google search guru Udi ManberYahoo Search BOSS:Opens up the search engine to developers.For example,you can rerank search results.Compare Google and Yahoo ranking for a queryHow Google uses eye tracking for improving search92 现代信息检索课后练习习题7-3习题7-5习题7-793
lecture7-system-第7讲--完整搜索系统中的评分计算-现代信息检索导论-教学ppt课件
