怎样量化评价搜索引擎的结果质量

 

 

怎样量化评价搜索引擎的结果质量

　　来源：InfoQ
　　作者：陈运文

　　前言

 

 

　　搜索质量评估 是搜索技术研究的基础性工作，也是核心工作之一。评价（Metrics） 在搜索技术研发中扮演着重要角色，以至于任何一种新方法与他们的评价方式是融为一体的。

　　搜索引擎结果的好坏 与否，体现在业界所称的在相关性（Relevance） 上。相关性的定义包括狭义 和广义 两方面，狭义的解释是：检索结果和用户查询的相关程度 。而从广义的层面，相关性可以理解为为用户查询的综合满意度 。直观的来看，从用户进入搜索框的那一刻起，到需求获得满足为止，这之间经历的过程越顺畅，越便捷，搜索相关性就越好。本文总结业界常用的相关性评价指标 和量化评价方法 。供对此感兴趣的朋友参考。

　　Cranfield评价体系

　　A Cranfield-like approach 这个名称来源于英国Cranfield University ，因为在二十世纪五十年代 该大学首先提出了这样一套评价系统 ：由查询样例集、正确答案集、评测指标构成的完整评测方案 ，并从此确立了“评价”在信息检索研究中的核心地位。

　　Cranfield评价体系 由三个环节组成：

 

1. 抽取代表性的查询词 ，组成一个规模适当的集合
2. 针对查询样例集合，从检索系统的语料库中寻找对应的结果 ，进行标注（通常人工进行）
3. 将查询词和带有标注信息的语料库输入检索系统，对系统反馈的检索结果，使用预定义好的评价计算公式，用数值化的方法来评价检索系统结果和标注的理想结果的接近程度

　　查询词集合的选取

　　Cranfield评价系统 在各大搜索引擎公司 内有广泛的应用。具体应用时，首先需要解决的问题是构造一个测试用查询词集合。

　　按照Andrei Broder （曾在AltaVista/IBM/Yahoo任职）的研究，查询词可分为3类 ：寻址类查询（Navigational）、信息类查询(Informational)、事务类查询(Transactional) 。对应的比例分别为

 

• Navigational ： 12.3%
• Informational ： 62.0%
• Transactional ： 25.7%

　　为了使得评估符合线上实际情况，通常查询词集合 也会按比例 进行选取。通常从线上用户的Query Log文 件 中自动抽取 。

　　另外查询集合的构造时，除了上述查询类型 外，还可以考虑Query的频次 ，对热门Query（高频查询）、长尾query（中低频） 分别占特定的比例 。

　　另外，在抽取Query时，往往 Query的长短 也是一个待考虑的因素。因为短query（单term的查询）和长Query（多Term的查询）排序算法往往会有一些不同。

　　构成查询集合后，使用这些查询词，在不同系统（例如对比百度和Google）或不同技术间（新旧两套Ranking算法的环境）进行搜索，并对结果进行评分，以决定优劣。

　　附图：对同一Query：“社会保险法 ”，各大搜索引擎的结果示意图。下面具体谈谈评分的方法。

 

　　

　　Precision-recall（准确率-召回率方法）

 

　　计算方法

　　信息检索领域 最广为人知的评价指标 为Precision-Recall（准确率-召回率） 方法 。该方法从提出至今已经历半个世纪，至今在很多搜索引擎公司的效果评估中使用。

　　顾名思义，这个方法由准确率 和召回率 这两个相互关联的统计量构成：召回率（Recall） 衡量一个查询搜索到所有相关文档的能力 ，而准确率（Precision） 衡量搜索系统排除不相关文档的能力 。（通俗的解释一下：准确率就是算一算你查询得到的结果中有多少是靠谱的；而召回率表示所有靠谱的结果中，有多少被你给找回来了）。这两项是评价搜索效果的最基础指标，其具体的计算方法如下。

　　Precision-recall方法 假定对一个给定的查询，对应一个被检索的文档集合和一个不相关的文档集合。这里相关性被假设为二元的，用数学形式化方法来描述，则是：

　　A表示相关文档集合

　　A 表示不相关集合

　　B表示被检索到的文档集合

　　B 表示未被检索到的文档集合

　　则单次查询的准确率和召回率 可以用下述公式来表达：

 

   

　　

　　　　　　　　　　　　　　（运算符∩表示两个集合的交集。|x|符号表示集合x中的元素数量）

　　从上面的定义不难看出，召回率 和准确率 的取值范围 均在[0,1] 之间。那么不难想象，如果这个系统找回的相关越多，那么召回率越高，如果相关结果全部都给召回了，那么recall此时就等于1.0。

 

　　

　　Precision-Recall曲线

　　召回率 和准确率 分别反映了检索系统的两个最重要的侧面 ，而这两个侧面又相互制约 。因为大规模数据集合中，如果期望检索到更多相关的文档，必然需要“放宽”检索标准，因此会导致一些不相关结果混进来，从而使准确率受到影响。类似的，期望提高准确率，将不相关文档尽量去除时，务必要执行更“严格”的检索策略，这样也会使一些相关的文档被排除在外，使召回率下降。

　　所以为了更清晰的描述两者间的关系，通常我们将Precison-Recall 用曲线的方式绘制出来，可以简称为P-R diagram 。常见的形式如下图所示。（通常曲线是一个逐步向下的走势，即随着Recall的提高，Precision逐步降低）

 

　　

　　P-R的其它形态

　　一些特定搜索应用，会更关注搜索结果中错误的结果 。例如，搜索引擎的反作　弊系统（Anti-Spam System） 会更关注检索结果中混入了多少条作　弊结果。学术界把这些错误结果称作假阳性（False Positive） 结果，对这些应用，通常选择用虚报率（Fallout） 来统计：

 

　　

 

　　Fallout和Presion本质是完全相同的。只是分别从正反两方面来计算。实际上是P-R的一个变种。

　　再回到上图，Presion-Recall是一个曲线，用来比较两个方法的效果往往不够直观，能不能对两者进行综合，直接反映到一个数值上呢？为此IR学术界提出了F值度量（F -Measure） 的方法。F-Measure通过Precision和Recall的调和平均数 来计算，公式为：

 

　　

　　其中参数λε(0,1)调节系统对Precision和Recall的平衡程度。

 

　　通常取λ=0.5，此时

 

　　

　　这里使用调和平均数 而不是通常的几何平均 或算术平均 ，原因是调和平均数 强调较小数值的重要性 ，能敏感的反映小数字的变化 ，因此更适合用来反映检索效果。

　　使用F Measure的好处是只需要一个单一的数字就可以总结系统的检索效果，便于比较不同搜索系统的整体效果。

　　P@N 方法

 

　　点击因素

　　传统的Precision-Recall 并不完全适用对搜索引擎的评估，原因是搜索引擎用户的点击方式有其特殊性，包括：

　　A、60-65%的查询点击了名列搜索结果前10条的网页；
　　B、20-25%的人会考虑点击名列11到20的网页；
　　C、仅有3-4%的会点击名列搜索结果中列第21到第30名的网页

　　也就是说，绝大部分用户是不愿意翻页去看搜索引擎给出的后面的结果 。

　　而即使在搜索结果的首页（通常列出的是前10条结果），用户的点击行为 也很有意思，我们通过下面的Google点击热图（Heat Map） 来观察（这个热图在二维搜索结果页上通过光谱来形象的表达不同位置用户的点击热度。颜色约靠近红色 表示点击强度越高 ）：

 

　　

 

　　从图中可以看出，搜索结果的前3条吸引了大量的点击 ，属于热度最高的部分。也就是说，对搜索引擎来说，最前的几条结果是最关键的，决定了用户的满意程度。

 

　　

 

　　康乃尔大学 的研究人员通过 eye tracking实验 获得了更为精确的Google搜索结果的用户行为分析图 。从这张图中可以看出，第一条结果获得了56.38%的搜索流量 ，第二条和第三条结果的排名依次降低 ，但远低于排名第一的结果 。前三条结果的点击比例大约为11:3:2 。而前三条结果的总点击几乎分流了搜索流量的80% 。

　　另外的一些有趣的结论是，点击量并不是按照顺序依次递减的 。排名第七位获得的点击是最少的 ，原因可能在于用户在浏览过程中下拉页面到底部 ，这时候就只显示最后三位排名网站，第七名便容易被忽略 。而首屏最后一个结果获得的注意力（2.55）是大于倒数第二位的(1.45)，原因是用户在翻页前，对最后一条结果印象相对较深。搜索结果页面第二页排名第一的网页（即总排名11位的结果）所获得的点击只有首页排名第十网站的40%，与首页的第一条结果相比，更是只有其1/60至1/100的点击量 。

　　因此在量化评估搜索引擎的效果时，往往需要根据以上搜索用户的行为特点，进行针对性的设计。

 

　　 P@N 的计算方法

　　P@N 本身是Precision@N 的简称，指的是对特定的查询，考虑位置因素，检测前N条结果的准确率 。例如对单次搜索的结果中前5篇，如果有4篇为相关文档，则P@5 = 4/5 = 0.8 。

　　测试通常会使用一个查询集合（按照前文所述方法构造），包含若干条不同的查询词，在实际使用P@N 进行评估时，通常使用所有查询的P@N 数据，计算算术平均值，用来评判该系统的整体搜索结果质量。

　　N的选取

　　对用户来说，通常只关注搜索结果最前若干条结果，因此通常搜索引擎的效果评估只关注前5、或者前3结果 ，所以我们常用的N取值为P@3 或P@5 等。

　　对一些特定类型的查询应用，如寻址类的查询（Navigational Search），由于目标结果极为明确，因此在评估时，会选择N=1（即使用 P@1 ） 。举个例子来说，搜索“新浪网”、或“新浪首页”，如果首条结果不是新浪网（url：www.sina.com.cn ），则直接判该次查询精度不满足需求，即P@1=0

　　MRR

　　上述的P@N 方法，易于计算和理解。但细心的读者一定会发现问题，就是在前N结果中，排序第1位和第N位的结果，对准确率的影响是一样的。但实际情况是，搜索引擎的评价是和排序位置极为相关的。即排第一的结果错误，和第10位的结果错误，其严重程度有天壤之别。因此在评价系统中，需要引入位置这个因素。

　　MRR 是平均排序倒数（Mean Reciprocal Rank） 的简称，MRR方法主要用于寻址类检索（Navigational Search）或问答类检索（Question Answering） ，这些检索方法只需要一个相关文档，对召回率不敏感 ，而是更关注搜索引擎检索到的相关文档是否排在结果列表的前面 。MRR方法首先计算每一个查询的第一个相关文档位置的倒数 ，然后将所有倒数值求平均。例如一个包含三个查询词的测试集 ，前5结果分别为：

　　查询一结果：1.AN 2.AR 3.AN 4.AN 5.AR
　　查询二结果：1.AN 2.AR 3.AR 4.AR 5.AN
　　查询三结果：1.AR 2.AN 3.AN 4.AN 5.AR

　　其中AN表示不相关结果，AR表示相关结果 。那么第一个查询的排序倒数（Reciprocal Rank）RR1 = 1/2=0.5 ；第二个结果RR2 = 1/2 = 0.5 ；注意倒数的值不变，即使查询二获得的相关结果更多。同理，RR3= 1/1 = 1。对于这个测试集合，最终MRR=（RR1+RR2+RR3）/ 3 = 0.67

　　然而对大部分检索应用来说，只有一条结果无法满足需求，对这种情况，需要更合适的方法来计算效果，其中最常用的是下述MAP方法。

　　MAP

　　MAP方法 是Mean Average Precison ，即平均准确率法 的简称。其定义是求每个相关文档检索出后的准确率的平均值（即Average Precision）的算术平均值（Mean） 。这里对准确率求了两次平均，因此称为Mean Average Precision 。（注：没叫Average Average Precision一是因为难听，二是因为无法区分两次平均的意义）

　　MAP 是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank 越高)，MAP就应该越高。如果系统没有返回相关文档，则准确率默认为0 。

　　例如：假设有两个主题：

　　主题1有4个相关网页，主题2有5个相关网页。

　　某系统对于主题1检索出4个相关网页，其rank分别为1, 2, 4, 7；

　　对于主题2检索出3个相关网页，其rank分别为1,3,5。

　　对于主题1，平均准确率MAP计算公式为：

　　(1/1+2/2+3/4+4/7)/4=0.83。

　　对于主题2，平均准确率MAP计算公式为：

　　(1/1+2/3+3/5+0+0)/5=0.45。

　　则MAP= (0.83+0.45)/2=0.64。

　　DCG方法

　　DCG 是英文Discounted cumulative gain 的简称，中文可翻译为“折扣增益值 ”。DCG方法的基本思想是：

 

1. 每条结果的相关性分等级来衡量
2. 考虑结果所在的位置，位置越靠前的则重要程度越高
3. 等级高（即好结果）的结果位置越靠前则值应该越高，否则给予惩罚

　　我们首先来看第一条：相关性分级。这里比计算Precision时简单统计“准确”或“不准确”要更为精细。我们可以将结果细分为多个等级。比如常用的3级 ：Good（好）、Fair（一般）、Bad（差） 。对应的分值rel为：Good:3 / Fair:2 / Bad:1 。一些更为细致的评估使用5级分类法 ：Very Good（明显好）、Good（好）、Fair（一般）、Bad（差）、Very Bad（明显差），可以将对应分值rel设置为：Very Good:2 / Good:1 / Fair:0 / Bad:-1 / Very Bad: -2

　　评判结果的标准可以根据具体的应用来确定，Very Good通常是指结果的主题完全相关，并且网页内容丰富、质量很高。而具体到每条

 

　　

 
　　DCG的计算公式并不唯一 ，理论上只要求对数折扣因子的平滑性。我个人认为下面的DCG公式更合理，强调了相关性，第1、2条结果的折扣系数也更合理：

 

　　

  


　　此时DCG前4个位置上结果的折扣因子（Discount factor） 数值为：

 

　　

　　取以2为底的log值也来自于经验公式，并不存在理论上的依据。实际上，Log的基数可以根据平滑的需求进行修改，当加大数值时（例如使用log5 代替log2），折扣因子降低更为迅速，此时强调了前面结果的权重。

　　为了便于不同类型的query结果之间横向比较，以DCG为基础，一些评价系统还对DCG进行了归一，这些方法统称为nDCG（即 normalize DCG）。最常用的计算方法是通过除以每一个查询的理想值iDCG（ideal DCG）来进行归一，公式为：

 

　　


 

　　求nDCG需要标定出理想情况的iDCG，实际操作的时候是异常困难的，因为每个人对“最好的结果”理解往往各不相同，从海量数据里选出最优结果是很困难的任务，但是比较两组结果哪个更好通常更容易，所以实践应用中，通常选择结果对比的方法进行评估。

　　怎样实现自动化的评估？

　　以上所介绍的搜索引擎量化评估指标，在Cranfield评估框架（Cranfield Evaluation Framework） 中被广泛使用。业界知名的TREC（文本信息检索会议） 就一直基于此类方法组织信息检索评测和技术交流。除了TREC外，一些针对不同应用设计的Cranfield评测论坛 也在进行（如 NTCIR、IREX等）。

　　但Cranfield评估框架存在的问题 是查询样例集合的标注 上。利用手工标注答案 的方式进行网络信息检索的评价是一个既耗费人力、又耗费时间的过程 ，只有少数大公司能够使用。并且由于搜索引擎算法改进、运营维护的需要，检索效果评价反馈的时间需要尽量缩短，因此自动化的评测方法 对提高评估效率十分重要。最常用的自动评估方法是A/B testing系统 。

　　A/B Testing

 

 

　　


 
 
　　　　　　　　　　　　　　　　　　A/B Testing系统

　　A/B testing系统在用户搜索时，由系统来自动决定用户的分组号（Bucket id），通过自动抽取流量导入不同分支，使得相应分组的用户看到的是不同产品版本（或不同搜索引擎）提供的结果。用户在不同版本产品下的行为将被记录下来，这些行为数据通过数据分析形成一系列指标，而通过这些指标的比较，最后就形成了各版本之间孰优孰劣的结论。

　　在指标计算 时，又可细分为两种方法，一种是基于专家评分的方法 ；一种是基于点击统计的方法 。

　　专家评分的方法通常由搜索核心技术研发和产品人员来进行，根据预先设定的标准对A、B两套环境的结果给予评分，获取每个Query的结果对比，并根据nDCG 等方法计算整体质量。

　　点击评分 有更高的自动化程度 ，这里使用了一个假设 ：同样的排序位置，点击数量多的结果质量优于点击数量少的结果 。（即A2表示A测试环境第2条结果，如果A2 > B2，则表示A2质量更好）。通俗的说，相信群众（因为群众的眼睛是雪亮的 ）。在这个假设前提下，我们可以将A/B环境前N条结果的点击率自动映射为评分 ，通过统计大量的Query点击结果，可以获得可靠的评分对比。

　　Interleaving Testing

　　另外2003年 由Thorsten Joachims 等人提出的Interleaving testing 方法也被广泛使用。该方法设计了一个元搜索引擎 ，用户输入查询词后，将查询词在几个著名搜索引擎中的查询结果随机混合反馈给用户，并收集随后用户的结果点击行为信息．根据用户不同的点击倾向性，就可以判断搜索引擎返回结果的优劣 ，

　　如下图所示，将算法A和B的结果交叉放置，并分流量进行测试，记录用户点击信息。根据点击分布来判断A和B环境的优劣。

 

 

　　

 
　　　　　Interleaving Testing评估方法

　　Joachims 同时证明了Interleaving Testing评价方法 与传统Cranfield评价方法 的结果具有较高的相关性。由于记录用户选择检索结果的行为是一个不耗费人力的过程，因此可以便捷的实现自动化的搜索效果评估。

　　总结

　　没有评估就没有进步 ——对搜索效果的量化评测，目的是准确的找出现有搜索系统的不足（没有哪个搜索系统是完美的），进而一步一个脚印对算法、系统进行改进。本文为大家总结了常用的评价框架和评价指标。这些技术像一把把尺子，度量着搜索技术每一次前进的距离。

 

评论

1 楼 bluky999 2014-08-20  

@Mark