搜索排序一直是信息检索的研究重点,搜索排序的流程主要分为:召回层、粗排层、精排层、重排层,重排层主要考虑的是相关业务诉求和多样性要求,偏业务规则,此处我们只关注精排模型。 本文主要介绍搜索排序的质量评测。通过质量评测,可根据评测结果不断的进行改进和研究,也可以验证搜索引擎在真实环境中运行时的实际效果。
准确率、精确率、召回率
准确率和召回率广泛用于信息检索和统计学分类领域的两个度量值,用于评价结果的质量。其中准确率是检索出相关文档数与检索出的文档总数的比率,衡量的是检索系统的查准率;召回率是指检索出的相关文档数和文档库中所有的相关文档数的比率,衡量的是检索系统的查全率。
公式如下:
精确率(Precision)= 相关文档总数 / 返回的结果总数 = TP / (TP + FP)
召回率(Recall)= 相关文档总数 / 所有文档总数 = TP / (TP + FN)
准确率(precision)= (TP + TN) / 总样本个数(预测为正例中,有多少预测正确)
F值 = 精确率 * 召回率 * 2 / (精确率 + 召回率)(F值即为精确率和召回率的调和平均值)
真阳率(TPR)= TP / (TP + FN)
假阳率(FPR)= FP / (FP + TN)
AUC
ROC 曲线就是以 FPR 为横轴,TPR 为纵轴绘制的曲线。曲线如何绘制呢?给出一系列预测值,给定不同的阈值将预测得到不同的正负样本,对不同阈值分别计算(TPR,FPR),连接这些点将得到 ROC 曲线,ROC曲线下面的面积就是AUC。 公式计算: 方法一:假设样本集里面总共有 M 个正样本,N 个负样本,那么将得到 MN 个正负样本对,这 MN 个正负样本对里面,正样本预测概率 > 负样本预测概率个数的比例就是 AUC 的值。 方法二:和方法一的本质是一样的,但是计算复杂度减少了,将预测结果从小到大排序,score 最高的 rank 为 n,第二高位 n-1,以此类推,将所有正样本的 rank 求和再减去 M-1 种两两正样本的组合,就是所有正负样本对中正样本概率大于负样本概率的个数,然后除以 M*N。
AUC 的理解分析
- 物理含义:随机抽取一个正负样本对,使用模型对正负样本分别打分,预测得到正样本score > 负样本score 的概率。
- 为什么适合作为排序指标:相比于模型常用的准确率accuracy、精确率precision等指标的计算,他们依靠score的绝对值大小,取不同的阈值会计算出不同的值,而AUC是使用的score相对大小,不会因为阈值变化,auc就发生改变;后面提到的 MAP 和 NDCG也是这也。
- AUC 计算的不足:AUC 是一种全局计算,可能会考虑一些无效的点击正样本与未点击负样本,比如user1的点击正样本排序高于user2的未点击负样本。针对不足可以考虑计算Group-AUC(Group 可以是一个user,一次请求queryid,一个session等维度)做平均。
P@10指标
此指标更关注搜索结果排名最靠前结果的质量,用于评估最终排序top10个文档中有多大比例是相关的。公式如下: P@10 = 相关文档个数 / 10 * 100 % 这种方法比较暴力,并且只追求top10的结果不够全面,对于电商搜索来讲,此种方法基本无效。
MAP
1. Average precision(AveP)
准确率和召回率都只能衡量检索性能的一个方面,最理想的情况肯定是准确率和召回率都比较高。当我们想提高召回率的时候,肯定会影响准确率,所以可以把准确率看做是召回率的函数,即:P = f ( R ),也就是随着召回率从0到1,准确率的变化情况。那么就可以对函数P = f ( R )在R上进行积分,可以求P的期望均值。公式如下:
其中rel(k)表示第k个文档是否相关,若相关则为1,否则为0,P(k)表示前k个文档的准确率。 AveP的计算方式可以简单的认为是:
其中R表示相关文档的总个数,position( r )表示,结果列表从前往后看,第r个相关文档在列表中的位置。比如,有三个相关文档,位置分别为1、3、6,那么AveP=13×(11+23+36)。在编程的时候需要注意,位置和第i个相关文档,都是从1开始的,不是从0开始的。
AveP意义是在召回率从0到1逐步提高的同时,对每个R位置上的P进行相加,也即要保证准确率比较高,才能使最后的AveP比较大。
2. Mean average precision(MAP)
通常会用多个查询语句来衡量检索系统的性能,所以应该对多个查询语句的AveP求均值(the mean of average precision scores),即公式:
- 单个主题的平均准确率是每篇相关文档检索出后的准确率的平均值。
- 主集合的平均准确率(MAP)是每个主题的平均准确率的平均值。
- MAP 是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank 越高),MAP就应该越高。如果系统没有返回相关文档,则准确率默认为0。
- MAP的衡量标准比较单一,q(query,搜索词)与d(doc,检索到的doc)的关系非0即1,核心是利用q对应的相关的d出现的位置来进行排序算法准确性的评估。 例如:假设有两个主题,主题1有4个相关网页(假设q1有4个相关d),主题2有5个相关网页(假设q2有5个相关d)。某系统对于主题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。
- 需要注意:在利用MAP的评估的时候,需要知道:1. 每个q有多少个相关的d; 2. 排序结果中这些d的位置 3. 相关的定义。
NDCG
NDCG(normalized discounted cumulative gain,归一化折损累计增益)是一种近年来逐渐被采用的指标,尤其是在基于机器学习的排序方法中。NDCG是针对连续值的指标,它考虑单次请求,单个query的排序效果。
CG(Cumulative Gain) 累积增益:
其中,p为item在结果中的排序位置,rel_i为处在该位置的item相关度得分,CG就是标注序列的得分之和。
DCG(Discounted Cumulative Gain)折损累积增益:考虑CG没有考虑位置信息,DCG引入位置折损,越靠前的item相关度对整体排序质量影响越大。
另一种比较常用的,用来增加相关度影响比重的DCG计算方式是:
NDCG(Normalized DCG) 归一化折损累积增益:考虑到不同的请求,DCG 差异很大导致不可比,所以提出归一化的折损累积增益。通过对当前排序结合设置一个理想的排序顺序,得到的DCG值就是IDCG(ideal DCG)。