Tag Archives: Evaluation

IR笔记(7) – Evaluation

一个IR系统是好是坏,总要有个量化的打分的,下面说一下对IR系统的估价。

首先有一点是,我们说一条文档是相关还是不相关,针对的是用户的Information Need,而不是具体输入的Query。一般来讲Information Need是比较复杂而难以描述的,并不一定能用输入的Query精确表示出。比如我想知道我们学校都有什么样的美女,我在Google里输入“天大 美女”,结果得到的全是“一张美女图背后的惊天大秘密”,而如果我输入“天津大学 美女”,结果就好得多。再比如,用户输入Python,他可能是想关注那个脚本语言,也可能是想了解一下蟒蛇这种动物。当然,要求IR系统从Query中猜出用户的真实意图有点勉为其难,但这确实是我们始终绕不开的最终目标,所谓的Feedback Relevance, Query Expansion等等也都是为此而做的努力。

要做出Evaluation需要三类数据,一系列Information Need(用自然语言或是Query描述),大量的文档集,以及每篇文档与每个Need的相关度(通常是0,1二值,也有多值的,下面以二值为例)。评估的两个重要指标precision(以下称作P)和recall(以下称作R)在前面已经说过了,详细来说的话,对每个Query我们可以统计出四个值:

tp: 相关,且被检索出
fp: 不相关,但被检索出
fn: 相关,未被检出
tn: 不相关,未被检出

那么,P = tp/(tp+fp),R = tp/(tp+fn)。这里可能有一个疑问,就是看上去(tp+tn)/(tp+fp+fn+tn)似乎是一个更合适的选择,它可以表示出IR系统所做出的正确判断的比例。理论上确实是这样的,但实际上,针对每个Query的相关文档数相对整个文档集来说总是很小很小一部分(比如0.1%),如果我们的系统追求(tp+tn)/(tp+fp+fn+tn)最大化,它就会倾向于不检出任何文档,这样就可以得到一个相当高的得分。比如相关文档只占0.1%,那么这个啥活都不干的系统就得到了满分的99.9%,这显然是一个很囧的结果。

然而,用P和R两个值有时候确实不方便,有时候人们会采用一个F-Measure,它是P和R的加权调和平均数,也就是

$$F=frac{1}{alpha frac{1}{p} + (1- alpha) frac{1}{R} }$$

这里的$$alpha$$可以根据不同系统对P和R的不同侧重而调节。

最后说一下对返回结果有序的IR系统的评估,也就是说,我们关心的是系统返回的前k条结果的质量。首先注意一点,随着返回结果数目k的增大,R值一定单调不减,而对于比较正常的系统来说,P值整体来看应该是递减。这样的话,我们就可以在二维坐标上把针对不同k值的(P,R)都画出来并连线,就会得到一个类似下图的东西(图片来自Introduction to Information Retrieval):

Precision-Recall Graph

其中竖直往下的线表示随k增大,暂时没有检到新的相关文档,所以R不变,P降低;往斜上的线表示新的相关文档被检出。在实际中常常取11个典型Recall值(0.0, 0.1, 0.2…1.0)所对应的Precision作为指标。

最近又出现其他的评估方法,比如Mean Average Precision(MAP),这个是指,对于每个Query Q,设与它相关的文档为{d1,d2,…dk},我们用Rk表示随着返回文档数增加最终把dk包含起来时的集合,每个这样的集合对应一个P值,最后求对所有Query所有集合Rk的平均值:

$$MAP(Q) = frac{1}{|Q|} sum_{j=1}^{|Q|} frac{1}{m_j} sum_{k=1}^{m_j} Precision(R_{jk})$$

这里Q表示Query集合,$$m_j$$表示与Query j相关的文档数。