现代信息检索 Chapter 4：检索评价

1 定义

  检索评价针对信息检索系统响应用户查询的返回结果，系统化地给出了一个量化的指标。这个指标应该和检索结果与用户的相关性直接联系。计算这个指标的通常方法是，对于给定的一组查询，比较由系统产生的结果和由人产生的结果。这里的检索评价仅针对检索系统的结果质量，不考虑界面设计、系统性能等因素的影响。

2 检索指标

2.1 精度和召回率

  精度(Precison)是检出文档中相关文档的比例，召回率(Recall)是相关文档集中被检出的比率。将相关文档集记作 $R$ ，系统得出的结果集为 $A$ ，则：

$$精度=p=\frac{|R\cap A|}{|A|}$$ $$召回率=r=\frac{|R\cap A|}{|R|}$$

以横坐标为召回率，纵坐标为精度可绘制精度-召回率曲线，曲线下面积(Area Unser the Curve, AUC)可用于评估不同答案集的质量，面积越大表明质量越好。

  缺点：

• 召回率无法准确估计。
• 精度和召回率是相关联的指标，将二者结合为单一指标会更合适。
• 只能度量批处理状态下对一组查询进行处理的结果。
• 对于只需要弱偏序关系的系统来说，精度和召回率可能不适合。(?)

2.2 单值总结

  (1) 前 $n$ 平均精度 $P@n$ ：大部分搜索不需要高的召回率，绝大部分用户只需要顶部的几篇相关文档，通常计算前5篇或前10篇文档的平均精度(不管是相关还是不相关)， $P@n$ 提供了可靠的指标来评价Web搜索引擎的用户是否在排序的顶部得到了相关文档。

  (2) 平均精度均值(Mean Average Precision, MAP)：通过对每个新观察到的相关文档计算精度并做平均来得到关于排序的总结性的单一指标。查询 $q_i$ 的平均精度定义为：

$$MAP_i=\frac{1}{|R_i|}\sum_{k=1}^{|R_i|}P(R_i[k])$$

其中 $R_i$ 是 $q_i$ 对应的相关文档的集合， $P(R_i[k])$ 是从头遍历结果集的排序队列直到观察到 $R_i$ 中第 $k$ 篇文档时的精度，如果没有观察到就记作0。此外，在一组查询上的平均精度均值定义为：

$$MAP=\frac{1}{|N_q|}\sum_{i=1}^{|N_q|}MAP_i$$

其中 $N_q$ 是查询的总数目。

  (3) $R$ 精度：设当前查询的相关文档集 $R$ 的容量为 $n$ ，取排序队列的前 $n$ 篇文档计算精度，简单粗暴。但是对于一组查询，计算每个查询的 $R$ 精度再取平均效果可能不好。

  (4) 精度直方图：核心思想就是对于一组查询，可以分别比较每个查询在不同算法上的 $R$ 精度，来比较两个算法的检索质量，废话。

  (5) 平均排序倒数：适用于QA系统、特定主页查询等任务，更关注第一个正确的结果，而不是整个排序的结果集。设 $R_i$ 是相对于查询 $q_i$ 的排序， $S_{correct}(R_i)$ 函数返回在 $R_i$ 中第一个正确答案的位置，给定一个排序位置阈值 $S_h$ ， $R_i$ 的排序倒数定义为：

$$\begin{cases} \frac{1}{S_{correct}(R_i)} & S_{correct}(R_i)\leq S_h \\ 0 & otherwise \end{cases}$$

对于由 $N_q$ 个查询组成的集合 $Q$ 来说，平均排序倒数(Mean Reciproach Rank, MRR)是所有排序倒数的均值，即：

$$MRR(Q)=\frac{1}{N_q}\cdot\sum_{i=1}^{N_q}\frac{1}{S_{correct}(R_i)}$$ $$MRR$$ 是倾向于那些第一个正确的结果出现在排序顶部的指标。   (6) E值：结合精度和召回率，公式为： $$E(j)=1-\frac{1+b^2}{\frac{b^2}{r(j)}+\frac{1}{P(j)}}$$

其中 $r(j)$ 是在排序中第 $j$ 个位置的召回率， $P(j)$ 是在排序中第 $j$ 个位置的精度， $b(b\geq 0)$ 是用户定义的参数。

  (7) F值：同样是结合精度和召回率，公式为：

$$F(j)=\frac{2}{\frac{1}{r(j)}+\frac{1}{P(j)}}$$

注意到，当E值的 $b=1$ 时， $F(j)=1-E(j)$ 。

  (8) 摘要统计表：就是把查询数、文档数等统计特征列个表，没什么用。

2.3 面向用户的指标

  在相关文档集 $R$ 和结果集 $A$ 之外，考虑用户的认知范围，即用户已知的文档 $K$ ，如下图：

定义覆盖率为：

$$coverage=\frac{|K\cap R\cap A|}{|K\cap R|}$$

定义新颖率为：

$$novelty=\frac{|(R\cap A)-K|}{|K\cap R|}$$

高覆盖率表明系统找到了用户期望看到的大部分相关文档，高新颖率表明系统向用户展示了许多之前未知的新的相关文档。

2.4 折扣累计增益

  上述基于相关文档集和结果集计算的指标只考虑文档与查询的相关与否，而没有考虑到相关性的强弱。当检查查询的结果时，可以观察到两个重要的现象：

• 在排序的顶部我们更希望是高度相关的文档，而不是轻度相关的文档。
• 出现在排序底部的相关文档的价值不高。

  针对第一个现象，赋予每个相关文档相关性强度，0表示不相关，值越大表示相关性越强，对系统返回的排序列表，增益向量(gain vector) $G$ 定义为其中每个元素的相关性强度组成的向量，如：

$$G=(1,0,1,0,0,3,0,0,0,2,0,0,0,0,3)$$

累计增益(Cumulated Gain) $CG$ 定义为：

$$CG[i]=\begin{cases} G[1] & i=1 \\ G[i]+CG[i-1] & i>1 \end{cases}$$

则对于上面的增益向量：

$$CG=(1,1,2,2,2,5,5,5,5,7,7,7,7,7,10)$$

  针对第二个问题，按照文档在排序列表中的位置进行价值衰减，定义折扣累计增益(Discounted Cumulated Gain) $DCG$ 为：

$$DCG[i]=\begin{cases} G[1] & i=1 \\ \frac{G[i]}{log_2i}+DCG[i-1] & i>1 \end{cases}$$

则对于上面的增益向量：

$$DCG=(1.0,1.0,1.6,1.6,1.6,2.8,2.8,2.8,2.8,3.4,3.4,3.4,3.4,3.4,4.2)$$

同理，对于由多个查询组成的集合，可计算平均累计增益 $\overline{CG}$ 和平均折扣累计增益 $\overline{DCG}$ 。

  由于累计增益没有参照，定义理想 $CG$ 和 $DCG$ 为最优排序列表得到的结果，即文档相关性强度从大到小排列，记作 $ICG$ 和 $IDCG$ 。将原始的 $CG$ 和 $DCG$ 进行归一化：

$$NCG[i]=\frac{\overline{CG[i]}}{\overline{ICG[i]}}$$ $$NDCG[i]=\frac{\overline{DCG[i]}}{\overline{IDCG[i]}}$$

得到了在区间 $[0,1]$ 上的累计增益指标，可用于不同排序算法之间的比较。

2.5 二元偏好

  Todo

2.6 排序相关性测度

  当没有参照或没有评测人员时，很难计算出上述指标，则可以直接度量两个排序函数产生的结果的相关性，若对其中一个排序函数有一定的了解，就可以根据二者的相关性分析另一个排序函数的优劣。

  斯皮尔曼系数(Spearman coefficient)根据相同文档在不同排序中的位置差值计算相关性。设 $s_{1,j}$ 是文档 $d_j$ 在排序 $R_1$ 中的位置， $s_{2,j}$ 是文档 $d_j$ 在排序 $R_2$ 中的位置，则位置差值是 $|s_{1,j}-s_{2,j}|$ ，或计算差值平方和 $(s_{1,j}-s_{2,j})^2$ 。如果有K篇排序文档，对排序差值求平方和，则差值平方和的最大值是 $\frac{K\times(K^2-1)}{3}$ ，即两个排序互为反序。使用该最大值进行差值平方和的归一化，即：

$$\frac{\sum_{j=1}^K(s_{1,j}-s_{2,j})^2}{\frac{K\times(K^2-1)}{3}}$$

将该分式乘2，再用1减去结果，就得到了在区间 $[-1,1]$ 上的斯皮尔曼系数：

$$S(R_1,R_2)=1-\frac{6\times\sum_{j=1}^K(s_{1,j}-s_{2,j})^2}{K\times(K^2-1)}$$

值越大表明相关性越强。然而，通常两个排序文档集的大小和内容是不同的，这时的做法是取并集，将 $R_2$ 中不属于 $R_1$ 的文档添加在 $R_1$ 尾部，同时将 $R_1$ 中不属于 $R_2$ 的文档添加在 $R_2$ 尾部，之后再对这两个增广排序计算斯皮尔曼系数。

  肯德尔系数(Kendall Tau coefficient)比斯皮尔曼系数代数结构简单，有更清楚和直观的解释。给定两篇文档 $d_j$ 和 $d_k$ ，若在两个排序列表 $R_1$ 和 $R_2$ 中， $s_{1,j}-s_{1,k}$ 和 $s_{2,j}-s_{2,k}$ 同号，那么就说文档二元组 $[d_j,d_k]$ 在这两个排序中是协调的，反之则是不协调的。如果有K篇排序文档，则共有 $K(K-1)$ 个文档二元组，肯德尔系数定义为：

$$\tau(R_1,R_2)=1-\frac{2\times\Delta(R_1,R_2)}{K(K-1)}$$

和斯皮尔曼系数的形式是几近相同的，当两个排序文档集不同时，也可以用相同的方式增广排序。