国家科技创新平台规划

1信息获取技术的评估（RetrievalEvaluation）李晓明，北京大学信息科学技术学院2004年12月2日2提要引言常用的评估指标评估的实践（评测）3引言关于IR领域文本技术系统用户（普通，大量）文本语义的丰富性（以及文本集合本身的变化），用户需求的多样性，模型的简单化系统表现的终极评判在于它们所针对的用户群的评价（大量，长时间）对系统的评估常常是基于对所包含各项技术评估基础上的无论是从研究方法还是工程实践的角度，我们都需要能够评估各个单项技术对系统行为可能的贡献更进一步地，若能将设计指标和评价指标结合起来则最好4System=t1+t2+…+tl系统包含若干技术，t某人发明了一个新的t，评价它的方式:用它替换系统中的相应技术，看对总的效果的贡献单独在一个评测环境中评价前者往往代价较高（时间，费用）例如研究搜索引擎排序算法的不一定有机会摆弄真正的，有大规模用户的搜索引擎后者可能和真实系统应用有距离能对这距离有把握也行5评估（技术，系统）用户关心（系统的）：F={f1,f2,…,fn}相关性，新颖性，完整性，速度，…但代价等原因使完整的评估比较困难我们要确定（技术的）：G={g1,g2,…,gm}较小的代价能完成对它们的测试对它们测试的结果和f1,f2,…,fn有很好的对应最好还能有一套设计指标：P={p1,p2,…,pk}能使我们心里有数：它们实现的程度对g1,g2,…,gm贡献的关系（防止“irrelevance”）6汽车用户关心：速度，启动加速度，刹车距离，…发动机测试：转速，扭矩，马力发动机设计：排量，气缸数，点火方式，…汽车工业的实践已经证明了它们之间对应关系的有效性（尽管不是100%）7计算机用户关心：速度性能测试：SPEC设计：主频，CPI，字长，Cache大小，…计算机工业的实践也基本证明它们的对应关系是有效的8大学用户（社会）关心：培养能够为人类社会的进步充分发挥潜能的人测试：政府高级官员的数量，大文豪、大科学家的数量，…设计的具体追求：得奖数，发表论文数（影响因子），博士学位获得者人数，科研经费数，…实践证明如何？9评估不断地对现有的F,G,P（及其相互关系）提出疑问，提出改进，是研究评估的人们应该考虑的基本任务我们需要了解现在的F,G,P是些什么（如何定义的，如何能得到），但仅此不够。事物都是在一个“目的”和“手段”链中发展的，这种链接关系的紧密程度就决定了达到目的的优化程度（效果、效率）10信息获取技术评估的“森林”11以批判的眼光看Pr,Re,F“Precisionandrecallhavebeenusedextensivelytoevaluatetheretrievalperformanceofretrievalalgorithms.However,amorecarefulreflectionrevealsproblemswiththesetwomeasures.”(page81,ModernInformationRetrieval)12先回顾它们的定义和计算要评价技术T，对于给定的查询，q，总体文档集合D记R：D中和q相关文档的集合，|R|：R的大小A：算法T获取的文档集合，|A|：A的大小|Ra|：R和A交集的大小RRacallReARaecisionPr13查准率和召回率基础定义图示CollectionAnswerSet|A|RelevantDocs|R|RelevantDocsinAnswerSet|Ra|14需要考虑的几个问题定义了，不等于能算了如何算得针对（Q,D）的Pr,Re？另外，人们认为在一定的排序意义上考察Pr,Re更有意义。“rankedA”，沿着这个rank，考察“查准率（精度）随召回率变化的情况”符合许多IR系统的实际情况，通常都会在结果集合上定义一个序1516平均精度对recall增加时对应的精度求平均值和“原始定义”的区别？这样的“平均精度”有什么不好？17“针对11点标准召回率的精度”人们建议在一些特殊的点上给出Re和Pr的关系Re=0%,10%,…,100%，对应的Pr于是就能很方便地讲“召回率为20%的时候精度为X”之类的结论也还有“3点标准”的说法：25%,50%,75%如果D中相关文档的个数是10的倍数，且如果算法给出的“RankedA”包含了所有相关文档，得到这些点就会很简单；否则要考虑如何插值的问题18“省事的”例子D={d1,…,d1000}，对查询q，所有相关文档集合（共10个元素）：Rq={d3,d5,d9,d25,d39,d44,d56,d71,d89,d123}查询的返回结果序：d123*，d84，d56*，d6，d8，d9*，d511，d5*，d39*，d129，d187，d25*，d38，d44*，d57，d71*，d48，d250，d113，d3*，d200，d144，d11，d89*，d1Ranking:*^*^^*^**^^*^*^*^^^*^^^*^Recall:.1.1.2.2.2.3.3.4.5.5.5.6.6.7.7.8.8.8.8.9.9.9.911Precisio:1.5.67.5.4.5.43.5.55.5.45.5.46.5.46.5.47.5.42.45.43.41.39.42.41911standardrecalllevelprecision00.20.40.60.811.200.20.40.60.811.2其实只有10个点？？20但实际上经常不是这样得到的结果集合不包含所有的相关元素实践上常常只是返回排序较高的若干元素因此不能得到需要的recall值D中相关元素的个数不是10的倍数于是能直接得到的recall值不一定包含0%,10%,20%,30%,…,100%21例子所有相关文档集合（共10个元素）：Rq={d3,d5,d9,d25,d39,d44,d56,d71,d89,d123}只能得到5个有效的recall值：10%，20%，30%，40%，50%对查询q返回的结果序:1.d123*2.d843.d56*4.d65.d86.d9*7.d5118.d1299.d18710.d25*11.d3812.d4813.d25014.d11315.d3*22Precision00.20.40.60.811.20%20%40%60%80%100%120%Precision00.20.40.60.811.20%20%40%60%80%100%120%23插值（interpolation）目标是在11个标准召回率上都有精度值可以想出各种“合理的”方法（例如将已知的点连起来），不同的方法结果会不一样（因此做比较时要讲清楚）P(rj)=maxP(r),rj≤r≤rj+1取在下一个标准召回率之间的已知召回率对应的最大精度值P(rj)=maxP(r),rj≤r取往后的已知召回率对应的最大的精度值（这得到的是阶梯函数，单调性。如何考虑返回的结果不包括所有相关文档？24我们最终关心对Q的总体情况qNiqiiNrPrP1)()(–ri取标准召回率，Nq是所考察Q的大小。这样得到一个技术（算法）在（Q，D）上精度的宏观表现25F指数用一个量来表示precision和recall的综合效果How？人们定义：为什么不是：RPPRRPRPHF2112),(2),(RPRPAF26A(P,R)和H(P,R)并不一致例如：P1=0.1,R1=0.83:A(P1,R1)=0.42,H(P1,R1)=0.197;P2=0.3,R2=0.3:A(P2,R2)=0.3,H(P2,R2)=0.3也就是说，A(P1,R1)A(P2,R2)，但H(P1,R1)H(P2,R2)（当然也可以举出它们一致的例子）27指标定义的倾向RPPRF2在P+R一定的情况下，希望它们接近。换句话说，这个指标不掩盖P,R一个方面特别的不足28召回不足分子小精度不够分母大29基于P,R,F的评估小结给定包含一个新算法的IR系统（测试），一个测试文档集合D，一个查询集合Q={q}一个事先确定的相关集合的集合G(Q)我们确定这个算法的P-R图和F值30流程对于Q的每一个元素q：得到一个有序结果集s(q)=d1,d2,…dq与G(q)对比，依序计算s(q)中元素的r[i]和p[i]，i=1,2,…,q选择一种合适的插值方式，得到p[i]在r=0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1处的插值如果r[q]1，则令它其后的标准点上的p=0对Q的所有元素，在标准召回点上求p的平均值给出平均值的统计表和P-R图3132还要算F:得出一个数对每一个查询q，得到标准召回点上的F，即Fq(i)=2*p[i]*r(i)/(p(i)+r(i)),i=0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1在查询内求平均（micro-average）Fq=∑Fq(i),i=0,.1,.2,…,.9,1进一步在查询间求平均（macro-average）F=∑Fq,q∈Q33困难与不适有可能D和Q太大，得出G(Q)代价太高“相关”的含义因人而异如此定义的P,R,F适于“批处理”评估，没有体现交互式信息检索过程（现代IR系统的典型特征）如此定义的P,R,F依赖于返回结果的线性序，但有些系统不一定有这样的序什么是评估搜索引擎排序算法最好的方法（如果你没有搜索引擎的话）？34