《信息检索的评价 - 苏州大学智能信息处理及应用研究所.ppt》由会员分享，可在线阅读，更多相关《信息检索的评价 - 苏州大学智能信息处理及应用研究所.ppt（78页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Introduction to Information Retrieval 信息检索导论信息检索导论 Introduction to Information Retrieval授课人：赵朋朋http:/ 检索评价&结果摘要Evaluation&Snippets12011/10/11提纲2 上一讲回顾 有关检索评价 评价指标 相关评测 结果摘要提纲3 上一讲回顾 有关检索评价 评价指标 相关评测 结果摘要信息检索 4快速返回top K结果的启发式方法以文档为单位(Document-at-a-time）的处理 计算查询-文档相似度时，先计算完文档 di 的得分，再开始文档 di+1的计算文档在所有
2、倒排记录表中的顺序应该保持一致以词项为单位(Term-at-a-time)的处理计算查询-文档相似度时，先处理完词项 ti 的倒排记录表，再处理词项ti+1的倒排记录表需要对每个未处理完的文档建立一个累加器4堆结构5信息检索 6分层索引6 信息检索本讲内容信息检索的评价指标不考虑序的检索评价指标(即基于集合)考虑序的评价指标信息检索评测语料及会议检索结果的摘要7提纲8 上一讲回顾 有关检索评价 评价指标 相关评测 结果摘要 信息检索从竞技体育谈起(曾经的一说)世界记录 vs.世界最好成绩110米栏世界记录：罗伯斯，古巴，1287男子马拉松世界最好成绩：保罗 特尔加特，肯尼亚，2小时4分55秒评
3、价要公平！环境要基本一致：天气、风速、跑道等等比赛过程要一样：竞走中的犯规指标要一样：速度、耐力9 信息检索为什么要评估IR？通过评估可以评价不同技术的优劣，不同因素对系统的影响，从而促进本领域研究水平的不断提高类比：110米栏各项技术-起跑、途中跑、跨栏、步频、冲刺等等信息检索系统的目标是较少消耗情况下尽快、全面返回准确的结果。10 信息检索IR中评价什么？效率(Efficiency)可以采用通常的评价方法时间开销空间开销响应速度效果(Effectiveness)返回的文档中有多少相关文档所有相关文档中返回了多少返回得靠不靠前其他指标覆盖率(Coverage)访问量数据更新速度11 信息检索
4、如何评价效果？相同的文档集合，相同的查询主题集合，相同的评价指标，不同的检索系统进行比较。The Cranfield Experiments,Cyril W.Cleverdon,1957 1968(上百篇文档集合)SMART System,Gerald Salton,1964-1988(数千篇文档集合)TREC(Text REtrieval Conference),Donna Harman,美国标准技术研究所,1992-(上百万篇文档)，信息检索的“奥运会”12信息检索 评价任务的例子两个系统，一批查询，对每个查询每个系统分别得到一些结果。目标：哪个系统好？系统&查询1234系统1，查询1d3
5、d6d8d10系统1，查询2d1d4d7d11系统2，查询1d6d7d3d9系统2，查询2d1d2d4d1313提纲14 上一讲回顾 有关检索评价 评价指标 相关评测 结果摘要 信息检索评价指标分类对单个查询进行评估的指标在单个查询上检索系统的得分对多个查询进行评估的指标在多个查询上检索系统的得分15 信息检索评价指标分类对单个查询进行评估的指标在单个查询上检索系统的得分对多个查询进行评估的指标在多个查询上检索系统的得分16信息检索 回到例子系统&查询1234系统1，查询1d3d6d8d10系统1，查询2d1d4d7d11系统2，查询1d6d7d2 d9系统2，查询2d1d2d4d1317对于
6、查询1的标准答案集合 d3,d4,d6,d9 信息检索评价指标召回率召回率(Recall):RR/(RR+NR)，返回的相关结果数占实际相关结果总数的比率，也称为查全全率率，R 0,1正确率正确率(Precision):RR/(RR+RN)，返回的结果中真正相关结果的比率，也称为查准率准率，P 0,1两个指标分别度量检索效果的某个方面，忽略任何一个方面都有失偏颇。两个极端情况：返回有把握的1篇，P=100%，但R极低；全部文档都返回，R1，但P极低18信息检索 四种关系的矩阵表示RRRNNRNN19真正相关文档 RR+NR真正不相关文档系统判定相关 RR+RN(检索出)系统判定不相关(未检索出
7、)RecallPrecisionAns=RR+NRRet=RR+RN 信息检索基于集合的图表示20RR标准答案Ans返回结果RetRNNRPrecisionRecall信息检索 回到例子系统&查询12345系统1，查询1d3d6d8d10d11系统1，查询2d1d4d7d11d13系统2，查询1d6d7d2 d9系统2，查询2d1d2d4d13d1421对于查询1的标准答案集合 d3,d4,d6,d9对于系统1，查询1，正确率2/5，召回率2/4对于系统2，查询1，正确率2/4，召回率2/4 信息检索课堂提问：另一个计算例子一个例子：查询Q，本应该有100篇相关文档，某个系统返回200篇文档，
8、其中80篇是真正相关的文档Recall=80/100=0.8Precision=80/200=0.4结论：召回率较高，但是正确率较低22 信息检索正确率和召回率的应用领域拼写校对中文分词文本分类人脸识别23 信息检索关于正确率和召回率的讨论(1)“宁可错杀一千，不可放过一人”偏重召回率，忽视正确率。冤杀太多。判断是否有罪：如果没有证据证明你无罪，那么判定你有罪。召回率高，有些人受冤枉如果没有证据证明你有罪，那么判定你无罪。召回率低，有些人逍遥法外24 信息检索关于正确率和召回率的讨论(2)虽然Precision和Recall都很重要，但是不同的应用、不用的用户可能会对两者的要求不一样。因此，实
9、际应用中应该考虑这点。垃圾邮件过滤：宁愿漏掉一些垃圾邮件，但是尽量少将正常邮件判定成垃圾邮件。有些用户希望返回的结果全一点，他有时间挑选；有些用户希望返回结果准一点，他不需要结果很全就能完成任务。25 信息检索课堂提问：正确率和召回率的定义或者计算有什么问题或不足？26系统&查询12345系统1，查询1d3d6d8d10d11系统1，查询2d1d4d7d11d13系统2，查询1d6d7d2 d9系统2，查询2d1d2d4d13d14对于查询1的标准答案集合 d3,d4,d6,d9对于系统1，查询1，正确率2/5，召回率2/4对于系统2，查询1，正确率2/4，召回率2/4 信息检索正确率和召回率
10、的问题召回率难以计算解决方法：Pooling方法，或者不考虑召回率两个指标分别衡量了系统的某个方面，但是也为比较带来了难度，究竟哪个系统好？大学最终排名也只有一个指标。解决方法：单一指标，将两个指标融成一个指标两个指标都是基于(无序)集合进行计算，并没有考虑序的作用举例：两个系统，对某个查询，返回的相关文档数目一样都是10，但是第一个系统是前10条结果，后一个系统是最后10条结果。显然，第一个系统优。但是根据上面基于集合的计算，显然两者指标一样。解决方法：引入序的作用27 信息检索关于召回率的计算对于大规模语料集合，列举每个查询的所有相关文档是不可能的事情，因此，不可能准确地计算召回率缓冲池(
11、Pooling)方法：对多个检索系统的Top N个结果组成的集合进行人工标注，标注出的相关文档集合作为整个相关文档集合。这种做法被验证是可行的(可以比较不同系统的相对效果)，在TREC会议中被广泛采用。28 信息检索4个系统的Pooling29系统1 TOP N系统2 TOP N系统3 TOP N系统4 TOP N全部文档Pool 信息检索课堂提问(某个系统的某个查询)通过Pooling计算出的召回率、正确率和真正的召回率、正确率的大小之间有什么关系？情况1(常见情况)：如果只有部分结果进行了Pooling操作，那么显然在计算正确率时有 RRP=0)倍，1更重视召回率，1更重视正确率31信息检
12、索 32为什么使用调和平均计算F值为什么不使用其他平均来计算F，比如算术平均如果采用算术平均计算F值，那么一个返回全部文档的搜索引擎的F值就不低于50%，这有些过高。做法：不管是P还是R，如果十分低，那么结果应该表现出来，即这样的情形下最终的F值应该有所惩罚采用P和R中的最小值可能达到上述目的但是最小值方法不平滑而且不易加权基于调和平均计算出的F 值可以看成是平滑的最小值函数32 信息检索引入序的作用(1)R-Precision：检索结果中，在所有相关文档总数位置上的准确率，如某个查询的相关文档总数为80，则计算检索结果中在前80篇文档的正确率。33系统1，查询1d3d6 d8d10d11系统
13、2，查询1d6 d7d2 d10 d9 对于查询1的标准答案集合 d3,d4,d6,d9R-P1=2/4 R-P2=1/4 信息检索引入序的作用(2)正确率-召回率 曲线(precision versus recall curve)检索结果以排序方式排列，用户不可能马上看到全部文档，因此，在用户观察的过程中，正确率和召回率在不断变化(vary)。可以求出在召回率分别为0%,10%,20%,30%,90%,100%上对应的正确率，然后描出图像在上面的曲线对应的系统结果更好34信息检索 P-R曲线的例子某个查询q的标准答案集合为：Rq=d3,d5,d9,d25,d39,d44,d56,d71,d8
14、9,d123某个IR系统对q的检索结果如下：1.d123 R=0.1,P=16.d9 R=0.3,P=0.511.d382.d847.d51112.d483.d56 R=0.2,P=0.678.d12913.d2504.d69.d18714.d1135.d810.d25 R=0.4,P=0.415.d3 R=0.5,P=0.3335 信息检索P-R曲线36 信息检索P-R 曲线的插值问题对于前面的例子，假设Rq=d3,d56,d1293.d56 R=0.33,P=0.33;8.d129 R=0.66,P=0.25;15.d3 R=1,P=0.2不存在10%,20%,90%的召回率点，而只存在
15、33.3%,66.7%,100%三个召回率点在这种情况下，需要利用存在的召回率点对不存在的召回率点进行插值(interpolate)对于t%，如果不存在该召回率点，则定义t%为从t%到(t+10)%中最大的正确率值。对于上例，0%,10%,20%,30%上正确率为0.33，40%60%对应0.25，70%以上对应0.237 信息检索P-R曲线图38 信息检索P-R的优缺点优点：简单直观既考虑了检索结果的覆盖度，又考虑了检索结果的排序情况缺点：单个查询的P-R曲线虽然直观，但是难以明确表示两个查询的检索结果的优劣39 信息检索基于P-R曲线的单一指标Break Point：P-R曲线上 P=R的
16、那个点这样可以直接进行单值比较11点平均正确率(11 point average precision)：在召回率分别为0,0.1,0.2,1.0的十一个点上的正确率求平均，等价于插值的AP40 信息检索P-R曲线中的break point41y=xBreak point信息检索 引入序的作用(3)平均正确率(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:在召回率分别为0,0
17、.1,0.2,1.0的十一个点上的正确率求平均，等价于11点平均只对返回的相关文档进行计算的AP,AP=(1/1+2/2+3/5+4/10+5/20)/5，倾向那些快速返回结果的系统，没有考虑召回率42 信息检索不考虑召回率PrecisionN：在第N个位置上的正确率，对于搜索引擎，大量统计数据表明，大部分搜索引擎用户只关注前一、两页的结果，因此，P10,P20对大规模搜索引擎来说是很好的评价指标43信息检索 回到例子系统&查询12345系统1，查询1d3 d6 d8d10d11系统1，查询2d1 d4d7d11d13 系统2，查询1d6 d7d2 d9 系统2，查询2d1 d2 d4d13
18、d1444查询1及查询2的标准答案集合分别为 d3,d4,d6,d9d1,d2,d13系统1查询1:P2=1,P5=2/5;系统1查询2:P2=1/2,P5=2/5;系统1查询1:P2=1/2,P5=2/5;系统1查询1:P2=1,P5=3/5 信息检索评价指标分类对单个查询进行评估的指标对单个查询得到一个结果对多个查询进行评估的指标在多个查询上检索系统的得分求平均45 信息检索评价指标(9)平均的求法：宏平均(Macro Average):对每个查询求出某个指标，然后对这些指标进行算术平均微平均(Micro Average):将所有查询视为一个查询，将各种情况的文档总数求和，然后进行指标的计
19、算如：Micro Precision=(对所有查询检出的相关文档总数)/(对所有查询检出的文档总数)宏平均对所有查询一视同仁，微平均受返回相关文档数目比较大的查询影响MAP(Mean AP)：对所有查询的AP求宏平均46信息检索 回到例子系统&查询12345系统1，查询1d3 d6 d8d10d11系统1，查询2d1 d4d7d11d13 系统2，查询1d6 d7d2 d9 系统2，查询2d1 d2 d4d13 d1447查询1及查询2的标准答案集合分别为 d3,d4,d6,d9d1,d2,d13系统1查询1:P=2/5,R=2/4,F=4/9,AP=1/2;系统1查询2:P=2/5,R=2/
20、3,F=1/2,AP=7/15;系统2查询1:P=2/4,R=2/4,F=1/2,AP=3/8;系统2查询2:P=3/5,R=3/3.F=3/4,AP=11/12;系统1的MacroP=2/5,MacroR=7/12,MacroF=17/36,MAP=29/60,MicroP=4/10,MicroR=4/7,MicroF=8/17系统2的MacroP=11/20,MacroR=3/4,MacroF=5/8,MAP=31/48,MicroP=4/9,MicroR=5/7,MicroF=40/73 信息检索课堂提问：两个查询q1、q2的标准答案数目分别为100个和50个，某系统对q1检索出80个结
21、果，其中正确数目为40，系统对q2检索出30个结果，其中正确数目为24，求MacroP/MacroR/MicroP/MicroR：48P1=40/80=0.5,R1=40/100=0.4P2=24/30=0.8,R2=24/50=0.48MacroP=(P1+P2)/2=0.65,MacroR=(R1+R2)/2=0.44MicroP=(40+24)/(80+30)=0.58MicroR=(40+24)/(100+50)=0.43 信息检索整个IR系统的P-R曲线在每个召回率点上，对所有的查询在此点上的正确率进行算术平均，得到系统在该点上的正确率的平均值。两个检索系统可以通过P-R曲线进行比较
22、。位置在上面的曲线代表的系统性能占优。49 信息检索几个IR系统的P-R曲线比较50 信息检索面向用户的评价指标前面的指标都没有考虑用户因素。而相关不相关由用户判定。假定用户已知的相关文档集合为U，检索结果和U的交集为Ru，则可以定义覆盖率覆盖率(Coverage)C=|Ru|/|U|，表示系统找到的用户已知的相关文档比例。假定检索结果中返回一些用户以前未知的相关文档Rk，则可以定义出新率出新率(Novelty Ratio)N=|Rk|/(|Ru|+|Rk|)，表示系统返回的新相关文档的比例。51 信息检索其他评价指标不同的信息检索应用或者任务还会采用不同的评价指标MRR(Mean Recip
23、rocal Rank):对于某些IR系统(如问答系统或主页发现系统)，只关心第一个标准答案返回的位置(Rank)，越前越好，这个位置的倒数称为RR，对问题集合求平均，则得到MRR例子：两个问题，系统对第一个问题返回的标准答案的Rank是2，对第二个问题返回的标准答案的Rank是4，则系统的MRR为(1/2+1/4)/2=3/852提纲53 上一讲回顾 有关检索评价 评价指标 相关评测 结果摘要 信息检索TREC 概况The Text REtrieval Conference,TREC,http:/trec.nist.gov由NIST(the National Institute of Stan
24、dards and Technology)和DARPA(the Defense Advanced Research Projects Agency)联合举办1992年举办第一届会议，每年11月举行，至2006年已有15届，可以看成信息检索的“奥运会”54 信息检索TREC的目标(1)总目标：支持在信息检索领域的基础研究，提供对大规模文本检索方法的评估办法1.鼓励对基于大测试集合的信息检索方法的研究2.提供一个可以用来交流研究思想的论坛，增进工业界、学术界和政府部门之间的互相了解；55 信息检索TREC的目标(2)3.示范信息检索理论在解决实际问题方面的重大进步，提高信息检索技术从理论走向商业应
25、用的速度；4.为工业界和学术界提高评估技术的可用性，并开发新的更为适用的评估技术。56 信息检索TREC的运行方式(1)TREC由一个程序委员会管理。这个委员会包括来自政府、工业界和学术界的代表。TREC以年度为周期运行。过程为：确定任务参加者报名参加者运行任务返回运行结果结果评估大会交流一开始仅仅面向文本，后来逐渐加入语音、图像、视频方面的评测57 信息检索TREC的运行方式(2)确定任务：NIST提供测试数据和测试问题报名：参加者根据自己的兴趣选择任务运行任务：参加者用自己的检索系统运行测试问题，给出结果返回结果：参加者向NIST返回他们的运行结果，以便评估58 信息检索TREC的运行方式
26、(3)结果评估：NIST使用一套固定的方法和软件对参加者的运行结果给出评测结果大会交流：每年的11月召开会议，由当年的参加者们交流彼此的经验59 信息检索TREC的运行方式(4)60 信息检索测试数据和测试软件由LDC(Linguistic Data Consortium)或者其他单位免费提供，但有些数据需要缴纳费用，一般都必须签订协议每年使用的数据可以是新的，也可以是上一年度已经使用过的TREC使用的评估软件是开放的，任何组织和个人都可以用它对自己的系统进行评测61信息检索 62大型搜索引擎的评价Web下召回率难以计算搜索引擎常使用top k的正确率来度量,比如,k=10.或者使用一个考虑返
27、回结果所在位置的指标，比如正确答案在第一个返回会比第十个返回的系统给予更大的指标搜索引擎也往往使用非相关度指标比如：第一个结果的点击率仅仅基于单个点击使得该指标不太可靠(比如你可能被检索结果的摘要所误导，等点进去一看，实际上是不相关的).当然，如果考虑点击历史的整体情况会相当可靠比如：一些基于用户行为的指标 比如:A/B 测试62信息检索 63A/B 测试目标:测试某个独立的创新点先决条件：大型的搜索引擎已经在上线运行很多用户使用老系统将一小部分(如 1%)流量导向包含了创新点的新系统对新旧系统进行自动评价，并得到某个评价指标，比如第一个结果的点击率于是，可以通过新旧系统的指标对比来判断创新点
28、的效果这也可能是大型搜索引擎最信赖的方法63提纲64 上一讲回顾 有关检索评价 评价指标 相关评测 结果摘要信息检索 65结果的呈现最常见的就是列表方式，也称为“10 blue links”怎样描述该列表中的每篇文档？该描述很关键用户往往根据该描述来判断结果的相关性而不需要按次序点击所有文档65信息检索 66文档描述方式最常见的方式:文档标题、url以及一些元数据.以及一个摘要如何计算摘要？66信息检索 67摘要两种基本类型:(i)静态(ii)动态不论输入什么查询，文档的静态摘要都是不变的而动态摘要依赖于查询，它试图解释当前文档返回的原因67信息检索 68静态摘要一般系统中静态摘要是文档的一个
29、子集最简单的启发式方法：返回文档的前50个左右的单词作为摘要更复杂的方法：从文档中返回一些重要句子组成摘要可以采用简单的NLP启发式方法来对每个句子打分将得分较高的句子组成摘要也可以采用机器学习方法，参考第13章最复杂的方法：通过复杂的NLP方法合成或者生成摘要对大部分IR应用来说，最复杂的方法还不够成熟68信息检索 69动态摘要给出一个或者多个“窗口”内的结果(snippet)，这些窗口包含了查询词项的多次出现出现查询短语的snippet优先在一个小窗口内出现查询词项的snippet优先最终将所有snippet都显示出来作为摘要69信息检索 70一个动态摘要的例子查询:“new guinea
30、 economic development”Snippets(加黑标识)that were extracted from a document:.In recent years,PapuaNew Guinea has faced severe economic difficulties andeconomic growth has slowed,partly as a result of weak governanceand civil war,and partly as a result of external factors such as theBougainville civil wa
31、r which led to the closure in 1989 of thePanguna mine(at that time the most important foreign exchangeearner and contributor to Government finances),the Asianfinancial crisis,a decline in the prices of gold and copper,and a fallin the production of oil.PNGs economic development recordover the past f
32、ew years is evidence that governance issuesunderly many of the countrys problems.Good governance,whichmay be defined as the transparent and accountable management ofhuman,natural,economic and financial resources for the purposesof equitable and sustainable development,flows from proper publicsector
33、management,efficient fiscal and accounting mechanisms,and a willingness to make service delivery a priority in practice.70信息检索 71Google中的动态摘要71信息检索 72动态摘要的生成基于位置索引来构建动态摘要不太合适，至少效率上很低需要对文档进行缓存通过位置位置索引会知道查询词项在文档中的出现位置文档的缓存版本可能会过时不缓存非常长的文档，对这些文档只需要缓存其一个短前缀文档72信息检索 73动态摘要搜索结果页面的空间是有限的，snippet必须要短但是另一方面要
34、使snippet有意义，它们又要足够长通过Snippet应该能够判断文档的相关性理想情况：语言上良构的snippet理想情况：snippet就能回答查询而不需要继续浏览文档动态摘要对于用户满意度相当重要用户可以快速浏览这些snippet从而确定是否需要点击很多情况下，我们根本不需要点击就可以获得答案，从而可以节省时间73 信息检索本讲小结信息检索的评价方法不考虑序检索评价指标(即基于集合)：P、R、F考虑序的评价指标：P/R曲线、MAP、NDCG信息检索评测语料及会议检索结果的摘要74信息检索 75参考资料信息检索导论第8章http:/ifnlp.org/irTREC主页：http:/trec
35、.nist.govF-measure:Keith van Rijsbergen更多有关 A/B 测试的文章Too much A/B testing at Google?Tombros&Sanderson 1998:动态摘要的最早的几篇文章之一Google VP of Engineering on search quality evaluation at Google75 信息检索苏州大学计算机学院 赵朋朋课后练习题两个系统A,B，两个查询q1,q2,它们的标准答案分别是 Rq1=d1,d4,d28,d39,d56,Rq2=d3,d7,d16,d45,d86,d97 A、B 检索的结果分别如下表所示。试计算出每个系统对每个查询的P、R、F、P-R曲线、P10、AP等指标，并利用MAP指标对两个系统进行比较。请写出计算过程和结果。其中AP计算采用未插值方法。信息检索苏州大学计算机学院 赵朋朋课后练习对于下列例子，用书上公式tf*idf计算权重，夹角余弦计算相似度，写出计算过程，并判断哪篇文档和查询q更相关。查询q：2006 世界杯 举办地文档d1：2006 世界杯 在 德国 举行，本届 世界杯 的 冠军 是 意大利 队。文档d2：2002 世界杯 在 韩国 和 日本 举行，最后 的 冠军 得主 是 巴西 队。文档d3：信息 检索 信息检索课后练习习题8-8习题8-1078