理解搜索召回排序算法评价指标

摘要

搜索质量评估是搜索技术研究的基础性工作，也是核心工作之一，评价在搜索技术研发中扮演着重要角色。
搜索结果的好坏与否主要体现在相关性上。相关性的定义包括狭义和广义两方面:

狭义的解释是：检索结果和用户查询的相关程度。
广义的解释是：用户查询的综合满意度。

直观的来看，从用户进入搜索框的那一刻起，到需求获得满足为止，这之间经历的过程越顺畅，越便捷，搜索相关性就越好

搜索与一般应用的区别
搜索 Rank 是一个比较常见但是也相对特殊的场景。
跟大多数的机器学习算法的应用场景不同的是，搜索更多的关注的是检索结果中的排序的质量，用户往往关注的只是搜索结果中 top-k 的返回列表，而其他的大多数场景往往关注的是召回的每个个体的好坏。

常见排序算法评价指标

MAP指标（Mean Average Precision)

MAP 是$\color{red}{平均准确率}$的简称。单个主题的平均准确率是每篇相关文档检索出后的准确率的平均值，主集合的平均准确率(MAP)是每个主题的平均准确率的平均值。（对准确率求了两次平均）

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

1）P（Precision）单query准确率： 返回结果中相关文档占的比例，P=返回结果中相关文档数目/返回结果总数。

2）AP（Average Precision）单query平均准确率：对检索返回的每篇相关文档的准确率求平均，也即对不同召回率点上的正确率求平均。对一个query而言，检索系统返回的结果必然是有序的，而且越相关的文档排的越靠前越好。计算方法如下式:

$\text{AveP}=\frac{\sum_{k=1}^{N}(P(k) \times \operatorname{rel}(k))}{\text {number of relevant documents}}=\frac{\sum_{\mathrm{k}=1}^{N}\left(\frac{k}{r_{k}} \times \operatorname{rel}(k)\right)}{N}$

从上计算AP的式子可见，若某位置上的结果相关，则计算该位置的正确率，若不相关，则正确率置为0。可见AP值是对排序位置敏感的，相关文档排序位置越靠前、返回的相关文档越多，则AP值越大。如果没有返回相关文档，则AP为0。

3）MAP：P、AP都是对单个query而言的，而MAP是对所有（测试样本）query的AP值求算术平均，是反应系统在所有query上的检索效果的单值指标。计算方法如下：

$\mathrm{MAP}=\frac{\sum_{q=1}^{Q} \operatorname{AveP}(\mathrm{q})}{Q}$

可见利用MAP评估时，需要知道：1）每个q有多少个相关的d；2）排序结果中这些d的位置。

MAP计算实例
例如：假设有两个主题，主题1有4个相关网页，主题2有5个相关网页。
某系统对于主题1检索出4个相关网页，其rank分别为1, 2, 4, 7；对于主题2检索出3个相关网页，其rank分别为1, 3, 5。
对于主题1，平均准确率为(1/1+2/2+3/4+4/7)/4=0.83。对于主题2，平均准确率为(1/1+2/3+3/5+0+0)/5=0.45。则MAP= (0.83+0.45)/2=0.64。

MRR指标（Mean Reciprocal Rank）

MRR是$\color{red}{平均倒数排名法}$的简称。计算针对一组查询检索第一相关文档的排名倒数的平均值。

MRR 的核心思想是返回的结果集的优劣，跟第一个用户最满意答案的位置有关，第一个最满意答案越靠前，结果越好。用来评估返回排序的查询答案列表的系统的度量。

1）RR： 是把最符合用户期望（最相关）的结果在被评价系统返回结果列表中的排序位置取倒数；

对于只有一个query，若第一个正确答案排在第n位，则MRR得分就是 1/n

2) MRR: 对所有query（测试样本）的RR求算术平均

$\mathrm{MRR} = \frac 1 {|Q|} \sum_{i=1}^{|Q|} \frac 1 {rank_i}$

其中，$Q$为样本 Query 集合，$rank_i$表示在第$i$个query中，第一个正确答案的排名

MRR计算实例
测试集总共有两个query，如在系统对第一个query返回的检索列表中，用户点选了位置为2的条目，而对于第二个query点选的位置为4的条目，则该系统的MRR=(1/2+1/4)/2=3/8。

NDCG指标（Normalized Discounted Cumulative Gain）

NDCG 翻译为：$\color{red}{归一化折损累计增益}$

通俗理解NDCG

搜索返回的列表中，每一项设置一个相关性的评分值，通常这些评分值是一个非负数。这就是Gain（增益）。此外，对于某些没有用户反馈相关性的项，我们通常设置其增益为0。
把这些相关性分数相加，也就是Cumulative Gain（累积增益）。
为了让排名越靠前的结果越能影响最后的结果，也就是增益越高，因此，在把这些分数相加之前，我们将每项除以一个递增的数（通常是该项位置的对数值），也就是折损值，并得到DCG。
搜索结果随着检索词的不同，返回的数量是不一致的，而DCG是一个累加的值，没法针对两个不同的搜索结果进行比较，因此需要归一化处理，最终得到 NDCG

NDCG计算实例

按照$NDCG$的方法，首先需要对搜索返回列表中（通常是Top-K）的每个条目按照符合用户预期的程度进行评价，我们这里把预期的程度分为以下几个级别：

相关性等级	得分	打分标准
Perfect（完美的）	5	第一眼就会点击
Excellent（极好的）	4	优先点击
Good（挺好的）	3	可能会点击
Fair（还可以）	2	无意中点击
Bad（很差）	1	不会点击

如上表，针对输入参数及接口返回结果的各字段，并结合结果排序，需要人工给每条结果打分（1-5之间，默认为0）。

$CG_{p}=\sum_{i=1}^{p}rel_{i}$

然后使用下式分别计算$DCG@_{10}$和$IDCG@_{10}$：

${DCG}_=\sum_{i=1}^{p} \frac{2^{r e l_{i}}-1}{log _{2}(i+1)}$

其中$IDCG@_{10}$，只是按照打分进行降序排列后的序列打分计算$DCG@_{10}$。
比如对于query“美团”，它的结果列表按照打分降序排列后的打分列表是{5, 4, 3, 3, 3, 2, 2, 2, 1, 1}。通常$IDCG$值会大于$DCG$值，最理想的情况是$DCG$ 和 $IDCG$相同，此时表明结果排序刚好符合用户的预期，按照打分降序排列。
再根据下式计算$NDCG@_{10}$:

${nDCG}_=\frac{DCG_{p}}{IDCG_{p}}$

计算完样本中所有query（总数为$N$个）的$NDCG@_{10}$值后，如下式再对这些$NDCG$值取平均，来评价整个系统的排序质量。

$NDCG_{avg}=\frac{\sum_{i=1}^{N} NDCG_{q_{i}}}{N}$

实际打分标注按照用户的判断进行，如果列表中没有最符合用户预期时，可以没有最高分，比如可以都是低于5分的打分。

MAP 和 NDCG 的区别

MAP认为是二元相关性（一个项是感兴趣的或者不感兴趣的），而NDCG允许以实数形式进行相关性打分

参考这篇文档：信息检索中的评价指标MAP和NDCG

摘要