信息检索常用的评价指标整理 MAP nDCG ERR F-measure Precision Recall



转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com

AIQ 机器学习大数据 知乎专栏 点击关注

相关文献:

learning to rank : https://en.wikipedia.org/wiki/Learning_to_rank#cite_note-13
MRR: https://en.wikipedia.org/wiki/Mean_reciprocal_rank
Precision and Recall: https://en.wikipedia.org/wiki/Precision_and_recall
chales‘blog : http://charleshm.github.io/2016/03/Model-Performance/

一 查准率与查全率

此处输入图片的描述

Precision(P)

是指检索得到的文档中相关文档所占的比例,公式如下:

这里写图片描述

如果我们只考虑召回的所有结果的 top n 文档的 查准率, 叫做 P@n

Recall: (R)

查全率率是指所有相关文档中被召回到的比例,公式如下:

这里写图片描述

如果我们只考虑召回的所有结果的 top n 文档的 查准率, 叫做 R@n

即使仅仅观察查全率为 100% 也没多大意义, 虽然相关的文档 被全部召回了, 但是往往代价是伴随着更多的不相关文档被召回,导致查准率下降, 所以应该同时考虑两个指标,尽可能的都要高。
##F-measure

一种同时考虑准确率和召回率的指标。公式如下:

$$F = \frac{2 \times precision \times recall}{(precision+recall)}$$

可以看出 F 的取值范围从 0 到 1。另外还有一种 F 的变体如下所示:

943d5bcb114e485d8b18053e106640e5.png

常用的两种设置是 $F2$ 和 $F0.5$,前者中 recall 重要程度是 precision 的两倍,后者则相反,precision 重要程度是 recall 的两倍。

二 Mean average precision(MAP)

准确率和召回率都只能衡量检索性能的一个方面,最理想的情况肯定是准确率和召回率都比较高。当我们想提高召回率的时候,肯定会影响准确率,所以可以把准确率看做是召回率的函数,即:$P=f(R)$,也就是随着召回率从 0 到 1,准确率的变化情况。那么就可以对函数 $P=f(R)$ 在 R 上进行积分,可以求 P 的期望均值。公式如下:

这里写图片描述

微分:

这里写图片描述

其中 k 是召回文档中的某 doc rank 位置, n 是所有召回文档数,$P(k)$ 为 cut-off $k$ in the list 准确率,$\Delta r(k)$ 为 $k-1$ 到 $k$ 的召回率变化量

等价于下面的公式:

这里写图片描述

$rel(k)$ 值为 0 或 1,如果 doc k 是相关文档,$rel(k)$ 为 1,否则为 0,

AvePAveP 的计算方式可以简单的认为是:
$$AveP=\frac{1}{R}\times\sum_{r=1}^R \frac{r}{position(r)}$$

其中 $R$ 表示相关文档的总个数,$position(r)$ 表示,结果列表从前往后看,第 rr 个相关文档在列表中的位置。比如,有三个相关文档,位置分别为 1、3、6,那么 $AveP=\frac{1}{3}\times (\frac{1}{1}+\frac{2}{3}+\frac{3}{6})$。在编程的时候需要注意,位置和第 i 个相关文档,都是从 1 开始的,不是从 0 开始的。
$AveP$ 意义是在召回率从 0 到 1 逐步提高的同时,对每个 R 位置上的 P 进行相加,也即要保证准确率比较高,才能使最后的 $AveP$ 比较大。

最后~,MAP 计算所有 Query 的平均准确率分数:
$$MAP=\frac{\sum_{q=1}^Q AveP(q)}{Q}$$
Q 为 query 数目总量。

三 Mean reciprocal rank(MRR)

$$MRR = \frac{1}{|Q|} \sum_{i=1}^{|Q|}\frac{1}{rank_i}$$
where $rank_i$refers to the rank position of the first relevant document for the i-th query.

第一个正确答案的排名的倒数。MRR 是指多个查询语句的排名倒数的均值
这里写图片描述

四 Expected reciprocal rank (ERR)

一种考虑是,一个文档是否被用户点击和排在它前面的文档有很大的关系,比如排在前面的文档都是不相关文档,那么它被点击的概率就高,如果排它前面的文档都是非常相关的文档,那么它被点击的概率就很低。Cascade Models 假设用户从排名由高到底依次查看文档,一旦文档满足了用户的需求,则停止查看后续的文档。用 RiRi 表示用户只看在位置 ii 上的文档后就不在需要查看其它文档的概率,显然文档的相关度越高,$R_i$ 越大。那么用户在位置 i 停止的概率公式如下:

$$PP_r=\prod_{i=1}^{r-1}(1-R_i)R_r$$

ERR 表示用户的需求被满足时停止的位置的倒数的期望。首先是计算用户在位置 rr 停止的概率 $PP_r$,如下所示:

$$PP_r=\prod_{i=1}^{r-1}(1-R_i)R_r$$

其中 $R_i$ 是关于文档相关度等级的函数,可以选取如下的函数:

54e11137974c4aa78bccbb9db6fe3943.png

那么 ERR 的计算公式如下:
43f7b714dbcc427b9897afd1be4bf027.png

更通用一点,ERR 不一定计算用户需求满足时停止的位置的倒数的期望,可以是其它基于位置的函数 $φ(r)$,只要满足 $φ(0)=1$,且 $φ(r)→0$ 随着 $r→∞$。比如 DCG 中的 $\varphi(r)=\frac{1}{log_2 (r+1)}$
ERR 论文: https://web.archive.org/web/20120224053008/http://research.yahoo.com/files/err.pdf

五 Discounted cumulative gain (DCG)

在 MAP 计算公式中,文档只有相关不相关两种,而在 nDCG 中,文档的相关度可以分多个等级进行打分。

Cumulative Gain (CG)

计算 DCG 之前先进行计算 CG, 公式如下:
$$CG=\sum_{i=1}^p rel_i$$
$rel_i$ 是位置 i 处的相关性,上述公式计算了前 p 个结果的相关性总和
注意到召回结果的 doc 间任意排序,对 CG 函数值是无影响的,比如: 召回的三个文档 rank 依次是 doc1,doc2,doc3,相关性依次是 3,2,0,而如果
rank 顺序为 doc3,doc2,doc1,其 CG 值依然为 5. 而前者排序是最合理的,但 CG 值相同。

Discounted Cumulative Gain(DCG)

所以要引入对位置信息的度量计算,既要考虑文档的相关度等级,也要考虑它所在的位置信息。假设每个位置按照从小到大的排序,
它们的价值依次递减,意味着,相关度越高的如果排序越靠后,那么分数就应该受到惩罚,
可以假设第 i 个位置的价值是 $\frac{1}{log_2(i+1)}$,那么排在第 i 个位置的文档所产生的效益就是 $rel_i \times\frac{1}{log_2 (i+1)}=\frac{rel_i}{log_2 (i+1)}$,公式如下:

e2df7ee9c7894e4887022cdaa6e99530.png

另一种比较常用的,用来增加相关度影响比重的 DCG 计算方式是:

6960fa612da94422b58ad5795517b878.png

Normalized DCG (NDCG)

由于每个查询语句所能检索到的结果文档集合长度不一,p 值的不同会对 DCG 的计算有较大的影响。所以不能对不同查询语句的 DCG
进行求平均,需要进行归一化处理。nDCG 就是用 IDCG 进行归一化处理,表示当前 DCG 比 IDCG 还差多大的距离。公式如下:
$$nDCG_p = \frac{DCG_p}{IDCG_p}$$
IDCG 为理想情况下最大的 DCG 值
$$IDCG_p =\sum_{i=1}{|REL|} \frac{2{rel_i} -1}{log_2 (i+1)}$$

其中 $|REL|$ 表示,文档按照相关性从大到小的顺序排序,取前 p 个文档组成的集合。也就是按照最优的方式对文档进行排序。

如何计算

假如一个 query 召回的文档前 6 个为
$D={d_1, d_2, d_3,d_4,d_5, d_6}$
相关性分值依次为
$3,2,3,0,1,2$
意味着 $d_1$ 的相关性分值为 3,$d_2$ 相关性分值为 2,以此类推。
$CG$ 值为:
此处输入图片的描述
可以看到只是简单的对召回对前 6 个文档分数简单的加和,并没有考虑 doc 所在的位置对排序结果的评分影响。而 $DCG$ 的思想是对 越高相关性的 doc 越往后排会给予一定的更大惩罚项。
$DCG$ 的计算如下
此处输入图片的描述
因为每个 query 召回文档数目不同,DCG 间无法统一比较,所以需要归一化。
先计算 IDCG,我们假设实际上此 query 召回了八个 doc,除了上面 6 个 doc,还有 $doc_7$ 分值为 3,$dooc_8$ 分值为 0,理想 rank 情况下的相关分数顺序为:
$3,3,3,2,2,1,0$
计算 $IDCG@6$:
$IDCG_6= 8.740$
$$nIDCG_6=\frac{DCG_6}{IDCG_6}=\frac{6.861}{8.740}=0.785$$

局限性

  • nDCG 不能惩罚“坏”文档,比如两个 query 返回了两列结果,分值分别为 $1,1,1$, $1,1,10$ 那么两者的 nDCG 是一样的。注意把 $Excellent$,$Fair$,$Bad$ 映射为分值数字最好为 $1,0, -1$, 而不是类似于 $2,1,0$
  • nDCG 不能惩罚“缺失” 的 doc,比如两个 query 返回了两列结果,分值分别为 $1,1,1$,$1,1,1,1,1$. 前者计算 $DCG@3$,后者计算 $DCG@5$ 的话,两个 doc 都可以被认为是好的。解决方法是应该采取固定的 topk 大小来计算 $DCG@k$,并在 doc 不足的 query 召回结果后面补上“最小权重分值”,如 $1,1,1,0,0$,$1,1,1,1,1$ 两者均计算 $nDCG@5$

六 分类模型上 Precision 和 Recall 的含义

混淆矩阵

True Positive(真正, TP):将正类预测为正类数.
True Negative(真负 , TN):将负类预测为负类数.
False Positive(假正, FP):将负类预测为正类数 →→ 误报 (Type I error).
False Negative(假负 , FN):将正类预测为负类数 →→ 漏报 (Type II error).
ef436e252efd4e77a710d2df4662e135.png

精确率 (precision) 定义为:

$$P = \frac{TP}{TP+FP} \tag{1}$$
需要注意的是精确率 (precision) 和准确率 (accuracy) 是不一样的,
$$ACC = \frac{TP + TN}{TP+TN+FP+FN}$$

在正负样本不平衡的情况下,准确率这个评价指标有很大的缺陷。比如在互联网广告里面,点击的数量是很少的,一般只有千分之几,如果用 acc,即使全部预测成负类(不点击)acc 也有 99% 以上,没有意义。

召回率 (recall,sensitivity,true positive rate) 定义为:
$$R = \frac{TP}{TP+FN} \tag{2}$$

此外,还有 F1F1 值,是精确率和召回率的调和均值,

$$
\frac{2}{F_1} = \frac{1}{P} + \frac{1}{R}
$$
$$
F_1 = \frac{2TP}{2TP + FP + FN} \tag{3}
$$
精确率和准确率都高的情况下,F1F1 值也会高。

通俗版本

实际上非常简单,精确率是针对我们预测结果而言的,它表示的是预测为正的样本中有多少是对的。那么预测为正就有两种可能了,一种就是把正类预测为正类 (TP),另一种就是把负类预测为正类 (FP)。
而召回率是针对我们原来的样本而言的,它表示的是样本中的正例有多少被预测正确了。那也有两种可能,一种是把原来的正类预测成正类 (TP),另一种就是把原来的正类预测为负类 (FN)。
fa9c9a963a6e4ddaa959e2af6b1ee093.png


更多高质资源 尽在AIQ 机器学习大数据 知乎专栏 点击关注

转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com