lecture9queryexpansion信息检索导论王斌.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,中科院研究生院2011年度秋季课程,#,现代信息检索,第,9,讲 相关反馈及查询扩展,Relevance Feedback&Query Expansion,1,2011/10/11,提纲,2,上一讲回顾,动机,相关反馈基础,相关反馈详细介绍,查询扩展,提纲,3,上一讲回顾,动机,相关反馈基础,相关反馈详细介绍,查询扩展,上一讲回顾,信息检索的评价方法,不考虑序的评价方法,(,即基于集合,),：,P,、,R,、,F,考虑序的评价方法：,P/R,曲线、,MAP,、,NDCG,信息检索评测语料及会议,检索结果的摘要,4,5,正确率,(,Precision),和召回率,(,Recall,),正确率,(,Precision,，简写为,P,),是返回文档中真正相关的比率,召回率,(,Recall,R,),是返回结果中的相关文档占所有相关文档,(,包含返回的相关文档和未返回的相关文档,),的比率,5,6,正确率,vs.,召回率,P,=,TP,/,(,TP,+,FP,),R,=,TP,/(,TP,+,FN,),6,7,F,允许正确率和召回率的折中,where,0,1,，,b,2,0,常用参数,:,balanced,F,，,b,=1 or,=0.5,实际上是正确率和召回率的调和平均数（,harmonic mean,）,7,正确率和召回率相结合的指标：,F,值,8,正确率,-,召回率曲线,每个点对应,top k,上的结果,(,k,=1,2,3,4,.).,插值,(,红色,):,将来所有点上的最高结果,插值的原理：如果正确率和召回率都升高，那么用户可能愿意浏览更多的结果,8,9,平均的,11-,点正确率,/,召回率曲线,计算每个召回率点,(,0.0,0.1,0.2,.,),上的插值正确率,对每个查询都计算一遍,在查询上求平均,该曲线也是评测上常用的指标之一,9,MAP,平均正确率,(Average Precision,AP),：对不同召回率点上的正确率进行平均,未插值的,AP:,某个查询,Q,共有,6,个相关结果，某系统排序返回了,5,篇相关文档，其位置分别是第,1,，第,2,，第,5,，第,10,，第,20,位，则,AP=(1/1+2/2+3/5+4/10+5/20+,0,)/6,多个查询的,AP,的平均值称为系统的,MAP(Mean AP),MAP,是,IR,领域使用最广泛的指标之一,10,11,NDCG,BV(Best Vector),：假定,m,个,3,，,l,个,2,，,k,个,1,，其他都是,0,12,NDCG,Normalized(D)CG,另一种,NDCG,的计算方法,加大相关度本身的权重，原来是线性变化，现在是指数变化，相关度,3,、,2,、,1,在计算时用,2,3,、,2,2,、,2,1,据说搜索引擎公司常用这个公式,13,14,标准的评价会议,:TREC,TREC=Text Retrieval Conference(TREC),美国标准技术研究所,(NIST),组织,TREC,实际上包含了对多个任务的评测,最出名的任务,:TREC Ad Hoc,任务，,1992,到,1999,年前,8,届会议中的标准任务,TREC disk,包含,189,百万篇文档，主要是新闻报道，有,450,个信息需求,由于人工标注的代价太大，所有没有完整的相关性判定,然而，,NIST,采用了一种所谓结果缓冲,(pooling),的办法来进行人工标注，首先将所有参测系统的前,k,个结果放到一个缓冲池,(pool),，然后仅对缓冲池的文档进行标注，并认为所有的相关文档均来自该缓冲池中。,14,15,动态摘要,给出一个或者多个,“,窗口,”,内的结果,(snippet),，这些窗口包含了查询词项的多次出现,出现查询短语的,snippet,优先,在一个小窗口内出现查询词项的,snippet,优先,最终将所有,snippet,都显示出来作为摘要,15,16,一个动态摘要的例子,查询,:“new guinea economic development”Snippets(,加黑标识,),that were extracted from a document:.,In recent years,Papua,New Guinea has faced severe economic difficulties and,economic growth has slowed,partly as a result of weak governance,and civil war,and partly as a result of external factors such as the,Bougainville civil war which led to the closure in 1989 of the,Panguna mine(at that time the most important foreign exchange,earner and contributor to Government finances),the Asian,financial crisis,a decline in the prices of gold and copper,and a fall,in the production of oil.,PNGs economic development record,over the past few years is evidence that,governance issues,underly many of the countrys problems.Good governance,which,may be defined as the transparent and accountable management of,human,natural,economic and financial resources for the purposes,of equitable and sustainable development,flows from proper public,sector management,efficient fiscal and accounting mechanisms,and a willingness to make service delivery a priority in practice.,16,17,本讲内容,交互式相关反馈,(,Interactive relevance feedback):,在初始检索结果的基础上，通过用户交互指定哪些文档相关或不相关，然后改进检索的结果,最著名的相关反馈方法：,Rocchio,相关反馈,查询扩展,(,Query expansion):,通过在查询中加入同义或者相关的词项来提高检索结果,相关词项的来源,:,人工编辑的同义词词典、自动构造的同义词词典、查询日志等等。,17,提纲,18,上一讲回顾,动机,相关反馈基础,相关反馈详细介绍,查询扩展,19,搜索中提高召回率的方法,本讲的主题：两种提高召回率的方法,相关反馈及查询扩展,考虑查询,q,:aircraft.,某篇文档,d,包含,“plane”,但是不包含,“aircraft”,显然对于查询,q,，一个简单的,IR,系统不会返回文档,d,，,即使,d,是和,q,最相关的文档,我们试图改变这种做法：,也就是说，我们会返回不包含查询词项的相关文档。,19,20,关于召回率,Recall,本讲当中会放松召回率的定义，即,(,在前几页,),给用户返回更多的相关文档,这可能实际上会降低召回率，比如，将,jaguar,扩展为,jaguar(,美洲虎；一种汽车品牌,)+panthera(,豹属,),可能会去掉一些相关的文档，但是可能增加前几页返回给用户的相关文档数,20,21,提高召回率的方法,局部,(local),方法,:,对用户查询进行局部的即时的分析,主要的局部方法,:,相关反馈,(,relevance feedback),第一部分,全局,(Global),方法,:,进行一次性的全局分析,(,比如分析整个文档集,),来产生同,/,近义词词典,(,thesaurus,利用该词典进行查询扩展,第二部分,21,提纲,22,上一讲回顾,动机,相关反馈基础,相关反馈详细介绍,查询扩展,23,相关反馈的基本思想,用户提交一个,(,简短的,),查询,搜索引擎返回一系列文档,用户将部分返回文档标记为相关的，将部分文档标记为不相关的,搜索引擎根据标记结果计算得到信息需求的一个新查询表示。当然我们希望该表示好于初始的查询表示,搜索引擎对新查询进行处理，返回新结果,新结果可望（理想上说）有更高的召回率,23,相关反馈分类,用户相关反馈或显式相关反馈,(User Feedback or Explicit Feedback):,用户显式参加交互过程,隐式相关反馈,(Implicit Feedback),：系统跟踪用户的行为来推测返回文档的相关性，从而进行反馈。,伪相关反馈或盲相关反馈,(Pseudo Feedback or Blind Feedback),：没有用户参与，系统直接假设返回文档的前,k,篇是相关的，然后进行反馈。,24,25,相关反馈,相关反馈可以循环若干次,下面将使用术语,ad hoc retrieval,来表示那种无相关反馈的常规检索,将介绍三个不同的,(,用户,),相关反馈的例子,25,26,例,1,26,27,初始查询的结果,27,28,用户反馈,:,选择相关结果,28,29,相关反馈后再次检索的结果,29,30,向量空间的例子,:,查询,“canine”(1),Source:,Fernando D,az,30,31,文档和查询,“canine”,的相似度,Source:,Fernando D,az,31,32,用户反馈,:,选择相关文档,Source:,Fernando D,az,32,33,相关反馈后的检索结果,Source:,Fernando D,az,33,例,3:,一个实际的例子,34,初始查询,:,new space satellite applications,初始查询的检索结果,:(,r,=rank),r,+1 0.539 NASA Hasnt Scrapped Imaging Spectrometer,+2 0.533 NASA Scratches Environment Gear From Satellite Plan,3 0.528 Science Panel Backs NASA Satellite Plan,But Urges Launches,of Smaller Probes,4 0.526 A NASA Satellite Project Accomplishes Incredible Feat:Staying,Within Budget,5 0.525 Scientist Who Exposed Global Warming Proposes Satellites for,Climate Research,6 0.524 Report Provides Support for the Critics Of Using Big Satellites,to Study Climate,7 0.516 Arianespace Receives Satellite Launch Pact From Telesat,Canada,+8 0.509 Telecommunications Tale of Two Companies,用户将一些文档标记为相关,“+”.,35,基于相关反馈进行扩展后的查询,查询,:new space satellite applications,35,2.074,new,15.106,space,30.816,satellite,5.660,application,5.991,nasa,5.196,eos,4.196,launch,3.972,aster,3.516,instrument,3.446,arianespace,3.004,bundespost,2.806,ss,2.790,rocket,2.053,scientist,2.003,broadcast,1.172,earth,0.836,oil,0.646,measure,基于扩展查询的检索结果,36,r,*1 0.513 NASA Scratches Environment Gear From Satellite Plan,*2 0.500 NASA Hasnt Scrapped Imaging Spectrometer,3 0.493 When the Pentagon Launches a Secret Satellite,Space Sleuths Do Some Spy Work of Their Own,4 0.493 NASA Uses Warm Superconductors For Fast Circuit,*5 0.492 Telecommunications Tale of Two Companies,6 0.491 Soviets May Adapt Parts of SS-20 Missile For Commercial,Use,7 0.490 Gaping Gap:Pentagon Lags in Race To Match the,Soviets In Rocket Launchers,8 0.490 Rescue of Satellite By Space Agency To Cost$90,Million,提纲,37,上一讲回顾,动机,相关反馈基础,相关反馈详细介绍,查询扩展,38,相关反馈中的核心概念：质心,质心是的是一系列点的中心,前面我们将文档表示成高维空间中的点,因此，我们可以采用如下方式计算文档的质心,其中,D,是一个文档集合，是文档,d,的的向量表示,38,39,质心的例子,39,40,Rocchio,算法是向量空间模型中相关反馈的实现方式,Rocchio,算法选择使下式最大的查询,D,r,:,相关文档集,;,D,nr,:,不相关文档集,上述公式的意图是 是将相关文档和不相关文档分得最开的向量。,加入一些额外的假设，可以将上式改写为,:,40,Rocchio,算法,41,Rocchio,算法,41,最优查询向量为：,即将相关文档的质心移动一个量，该量为相关文档质心和不相关文档的差异量,42,课堂练习,:,计算,Rocchio,向量,圆形点,:,相关文档,叉叉点,:,不相关文档,42,43,Rocchio,算法图示,:,相关文档的质心,43,44,Rocchio,算法图示,不能将相关,/,不相关文档分开,44,45,Rocchio,算法图示,不相关文档的质心,45,46,Rocchio,算法图示,46,47,Rocchio,算法图示,-,差异向量,47,48,Rocchio,算法图示,加上差异向量,48,49,Rocchio,算法图示,得到,49,50,Rocchio,算法图示,能够将相关,/,不相关文档完美地分开,50,51,Rocchio,算法图示,能够将相关,/,不相关文档完美地分开,51,52,Rocchio 1971,算法,(SMART,系统使用,),q,m,:,修改后的查询,;,q,0,:,原始查询,;,D,r,、,D,nr,:,已知的相关和不相关文档集合,:,权重,新查询向相关文档靠拢而远离非相关文档,vs.,/,设置中的折中,:,如果判定的文档数目很多，那么,/,可以考虑设置得大一些,一旦计算后出现负权重，那么将负权重都设为,0,在向量空间模型中，权重为负是没有意义的。,52,实际中使用的公式,:,53,正,(Positive),反馈,vs.,负,(Negative),反馈,正反馈价值往往大于负反馈,比如，可以通过设置,=0.75,=0.25,来给正反馈更大的权重,很多系统甚至只允许正反馈，即,=,0,53,54,相关反馈中的假设,什么时候相关反馈能否提高召回率？,假设,A1:,对于某初始查询，用户知道在文档集中使用哪些词项来表达,假设,A2:,相关文档中出现的词项类似,(,因此，可以基于相关反馈，从一篇相关文档跳到另一篇相关文档,),或者,:,所有文档都紧密聚集在某个,prototype,周围,或者,:,有多个不同的,prototype,但是它们之间的用词具有显著的重合率,相关文档和不相关文档之间的相似度很低,54,55,假设,A1,不成立的情况,假设,A1:,对于某初始查询，用户知道在文档集中使用哪些词项来表达,不成立的情况：用户的词汇表和文档集的词汇表不匹配,例子：,cosmonaut/astronaut,55,56,假设,A2,不成立的情况,假设,A2:,相关文档中出现的词项类似,假设不成立的查询例子：,contradictory government policies,互相矛盾的政府政策,一些相关的文档集合，但是文档集合彼此之间并不相似,文档集合,1,：烟草种植者的补贴,vs.,禁烟运动,文档集合,2,：对发展中国家的帮助,vs.,发展中国家进口商品的高关税,有关烟草文档的相关反馈并不会对发展中国家的文档有所帮助,56,57,相关反馈的评价,选择上一讲中的某个评价指标，比如,P,10,计算原始查询,q,0,检索结果的,P,10,指标,for original query,计算修改后查询,q,1,检索结果的,P,10,指标,大部分情况下,q,1,的检索结果精度会显著高于,q,0,!,上述评价过程是否公平？,57,58,相关反馈的评价,公平的评价过程一定要基于存留文档集,(,residual collection):,用户没有判断的文档集,研究表明采用，采用这种方式进行评价，相关反馈是比较成功的一种方法,经验而言，一轮相关反馈往往非常有用，相对一轮相关反馈，两轮相关反馈效果的提高有限。,58,59,有关评价的提醒,相关反馈有效性的正确评价，,必须要和其他需要花费同样时间的方法,相关反馈的一种替代方法,:,用户修改并重新提交新的查询,用户更倾向于修改和重新提交查询而不是判断文档的相关性,并没有清晰的证据表明，相关反馈是用户时间使用的最佳方法,59,60,课堂练习,搜索引擎是否使用相关反馈,?,为什么,?,60,61,相关反馈存在的问题,相关反馈开销很大,相关反馈生成的新查询往往很长,长查询的处理开销很大,用户不愿意提供显式的相关反馈,很难理解，为什么会返回,(,应用相关反馈之后,),某篇特定文档,Excite,搜索引擎曾经提供完整的相关反馈功能，但是后来废弃了这一功能,61,62,隐式相关反馈,通过观察用户,对当前检索结果采取的行为,来给出对检索结果的相关性判定。,判定不一定很准确，但是省却了用户的显式参与过程。,对用户,非当前,检索行为或,非检索,相关行为的分析也可以用于提高检索的效果，这些是个性化信息检索,(Personalized IR),的主要研究内容，并非本节的主要内容。,63,用户行为种类,鼠标键盘动作：,点击链接、加入收藏夹、拷贝粘贴、停留、翻页等等,用户眼球动作,Eye tracking,可以跟踪用户的眼球动作,拉近、拉远、瞟、凝视、往某个方向转,64,点击行为,(Click through behavior),FIELD,VALUE,User ID,1162742023015,Time stamp,06/Nov/2006:00:01:35,Query terms,嫁给警察的理由,URL,number,1,Rank,7,Anchor text,姑娘们，你们愿意,嫁给警察,吗？,慈溪社区,65,眼球动作,(,通过鼠标轨迹模拟,),66,关于,Eye tracking,67,隐式相关反馈小,结,优点：,不需要用户显式参与，减轻用户负担,用户行为某种程度上反映用户的兴趣，具有可行性,缺点：,对行为分析有较高要求,准确度不一定能保证,某些情况下需要增加额外设备,68,伪相关反馈,(,Pseudo-relevance feedback),伪相关反馈对于真实相关反馈的人工部分进行自动化,伪相关反馈算法,对于用户查询返回有序的检索结果,假定前,k,篇文档是相关的,进行相关反馈,(,如,Rocchio),平均上效果不错,但是对于某些查询而言可能结果很差,几次循环之后可能会导致查询漂移,(,query drift,),68,69,TREC4,上的伪相关反馈实验,比较了两种长度归一化机制,(L vs.l),以及反馈不反馈后的结果,(PsRF).,实验中的伪相关反馈方法对查询只增加了,20,个词项,(Rocchio,将增加更多的词项,),上述结果表明，伪相关反馈在平均意义上说是有效的方法,69,检索方法,相关文档数目,lnc.ltc,3210,lnc.ltc-PsRF,3634,Lnu.ltu,3709,Lnu.ltu-PsRF,4350,使用,Cornell,大学的,SMART,系统,50,个查询，每个查询基于前,100,个结果进行反馈,(,因此所有的反馈文档数目是,5000),：,70,伪相关反馈小,结,优点：,不用考虑用户的因素，处理简单,很多实验也取得了较好效果,缺点：,没有通过用户判断，所以准确率难以保证,不是所有的查询都会提高效果,提纲,71,上一讲回顾,动机,相关反馈基础,相关反馈详细介绍,查询扩展,72,查询扩展,(,Query expansion),查询扩展是另一种提高召回率的方法,我们使用,“,全局查询扩展,”,来指那些,“,查询重构,(query reformulation),的全局方法,”,在全局查询扩展中，查询基于一些全局的资源进行修改，这些资源是与查询无关的,主要使用的信息,:,同义词或近义词,同义词或近义词词典,(,thesaurus,),两种同,(,近,),义词词典构建方法：人工构建和自动构建,72,73,查询扩展的例子,73,74,用户反馈的类型,用户对文档提供反馈,在相关反馈中更普遍,用户对词或短语提供反馈,在查询扩展中更普遍,74,75,查询扩展的类型,人工构建的同,(,近,),义词词典,(,人工编辑人员维护的词典，如,PubMed),自动导出的,同,(,近,),义词词典,(,比如，基于词语的共现统计信息,),基于查询日志挖掘出的查询等价类,(,Web,上很普遍，比如上面的,“palm”,例子,),75,76,基于同,(,近,),义词词典的查询扩展,对查询中的每个词项,t,将词典中与,t,语义相关的词扩充到查询中,例子,:,HOSPITAL MEDICAL,通常会提高召回率,可能会显著降低正确率，特别是对那些有歧义的词项,INTEREST RATE INTEREST RATE FASCINATE,广泛应用于特定领域,(,如科学、工程领域,),的搜索引擎中,创建并持续维护人工词典的开销非常大,人工词典和基于受控词汇表,(,controlled vocabulary,),的标记的效果大体相当,76,77,基于人工词典的扩展样例,:PubMed,77,78,同,(,近,),义词词典的自动构建,通过分析文档集中的词项分布来自动生成同,(,近,),义词词典,基本的想法是计算词语之间的相似度,定义,1:,如果两个词各自的上下文共现词类似，那么它们类似,“car”“motorcycle”,，因为它们都与,“road”,、,“gas”,及,“license”,之类的词共现，因此它们类似,定义,2:,两个词，如果它们同某些一样的词具有某种给定的语法关系的话，那么它们类似,可以,harvest,peel,eat,prepare apples,和,pears,因此,apples,和,pears,肯定彼此类似,共现关系更加鲁棒，而语法关系更加精确,78,基于共现的词典构造,最简单的方法就是通过词典,-,文档矩阵,A,计算词项,-,词项的相似度,C=AA,T,w,i,j,=,(,t,i,d,j,),的,(,归一化,),权重,对每个,t,i,选择,C,中高权重的词项进行扩展,t,i,d,j,N,M,如果矩阵,A,是,0/1,矩阵，那么,C,的每一项是什么？,d,j,N,80,基于共现关系的同,(,近,),义词词典样例,WordSpace demo on web,80,词语,同,(,近,),义词,absolutely,bottomed,captivating,doghouse,makeup,mediating,keeping,lithographs,pathogens,senses,absurd whatsoever totally exactly nothing,dip copper drops topped slide trimmed,shimmer stunningly superbly plucky witty,dog porch crawling beside downstairs,repellent lotion glossy sunscreen skin gel,reconciliation negotiate case conciliation,hoping bring wiping could some would,drawings Picasso Dali sculptures Gauguin,toxins bacteria organisms bacterial parasite,grasp psyche truly clumsy naive innate,81,搜索引擎中的查询扩展,搜索引擎进行查询扩展主要依赖的资源：查询日志,(,query log),例,1:,提交查询,herbs(,草药,),后，用户常常搜索,herbal remedies,(,草本疗法,),“herbal remedies”,是,“herb”,的潜在扩展查询,例,2:,用户搜索,flower pix,时常常点击,URL,clipart,常常点击同样的,URL,“flower clipart”,和,“flower pix”,可能互为扩展查询,81,82,本讲小结,交互式相关反馈,(,Interactive relevance feedback):,在初始检索结果的基础上，通过用户交互指定哪些文档相关或不相关，然后改进检索的结果,最著名的相关反馈方法：,Rocchio,相关反馈,查询扩展,(,Query expansion):,通过在查询中加入同义或者相关的词项来提高检索结果,相关词项的来源,:,人工编辑的同义词词典、自动构造的同义词词典、查询日志等等。,82,83,参考资料,信息检索导论,第,9,章,ifnlp.org/ir,Salton and Buckley 1990(,原始的相关反馈论文,),Spink,Jansen,Ozmultu 2000:Relevance feedback at Excite,Sch,tze 1998:Automatic word sense discrimination(,接扫了一个简单的同义词自动构造方法,),83,课后练习,习题,9-3,习题,9-4,习题,9-7,84,