评估排名算法的指标

机器算法验证 算法 排行
2022-01-30 03:14:29

我有兴趣查看几种不同的排名算法指标 - 学习排名维基百科页面上列出了一些指标,包括:

• 平均精度(MAP);

• DCG 和 NDCG;

• Precision@n,NDCG@n,其中“@n”表示仅在前 n 个文档上评估度量;

• 平均倒数等级;

• 肯德尔的 tau

• 斯皮尔曼的 Rho

• 预期倒数排名

• Yandex 的发现

但我不清楚每种算法的优点/缺点是什么,或者何时可以选择一个而不是另一个(或者如果一种算法在 NDGC 上优于另一种算法,但在使用 MAP 评估时更差,这意味着什么)。

我有什么地方可以去了解更多关于这些问题的信息吗?

3个回答

我实际上正在寻找相同的答案,但是我应该至少可以部分回答您的问题。

您提到的所有指标都有不同的特征,不幸的是,您应该选择的指标取决于您实际想要衡量的内容。以下是一些值得牢记的事情:

  • Spearman 的 rho指标惩罚列表顶部的错误,其权重与底部的不匹配相同,因此在大多数情况下,这不是用于评估排名的指标
  • DCG 和 NDCG是考虑到非二进制效用函数的少数指标之一,因此您可以描述记录有用程度,而不是它是否有用。
  • DCG 和 NDCG具有固定的仓位权重,因此给定仓位的单据始终具有相同的收益和折扣,独立于其上方显示的单据
  • 您通常更喜欢NDCG而不是DCG,因为它通过相关文档的数量对值进行规范化
  • MAP应该是这个问题的经典和“首选”指标,它似乎是该领域的标准。
  • (N)DCG应该始终针对固定数量的记录 (@k) 计算,因为它有一个长尾(排名末尾的许多不相关记录高度偏向度量标准)。这不适用于MAP
  • Mean Reciprocal Rank仅标记第一个相关文档的位置,因此如果您关心尽可能多的相关文档以在列表中排名靠前,那么这不应该是您的选择
  • Kendall 的 tau只处理二进制效用函数,它也应该被计算 @k (类似于NDCG

宝贵资源:

无法发布更多链接,因为帐户是新的 :) 如果有人有更多评论或想法,我也很乐意听到!

在许多应用排名算法(例如谷歌搜索、亚马逊产品推荐)的情况下,您会得到成百上千的结果。用户只想在前 20 名左右观看。所以其余的完全无关紧要。

明确地说:只有前个元素是相关的k

如果这对您的应用程序来说是正确的,那么这对指标有直接影响:

  1. 您只需要查看的项目和 ground truth 排名的前项目。kk
  2. 这些潜在的项的顺序可能相关或不相关 - 但可以肯定所有其他项的顺序无关紧要。2k

三个相关指标是 top-k 准确率、precision@k 和recall@k。取决于您的应用程序对于所有这些,对于您评估的排名查询,相关项目的总数应高于kk

排名前 k 的分类准确率

对于基本事实,可能很难定义顺序。而如果你只区分相关/不相关,那么你实际上是在一个分类案例中!

Top-n准确度是分类的指标。请参阅Top-n 准确度的定义是什么?.

top-k accuracy=how often was at least one relevant element within the top-k of a ranking query?ranking queries

所以你让排名算法预测个元素,看看它是否包含至少一个相关项目。k

我非常喜欢这个,因为它很容易解释。来自业务需求(可能是),那么您可以说用户多久会感到高兴。kk[5,20]

这样做的缺点:如果您仍然关心项中的顺序,则必须找到另一个指标。k

精度@k

Precision@k=number of relevant items within the top-kk[0,1], higher is better

它告诉你什么:

  • 如果它很高 -> 您向用户展示的大部分内容都与他们相关
  • 如果它很低 -> 你浪费了你的用户时间。您向他们展示的大部分内容与他们无关

召回@k

Recall@k=number of relevant items within the top-ktotal number of relevant items[0,1], higher is better

这是什么意思:

  • 如果它很高:你展示你所拥有的!你给他们所有相关的项目。
  • 如果低:与相关项的总数相比,k 小/top k 内的相关项小。因此,单独的recall@k 可能没有那么有意义。如果它与高精度@k 相结合,那么增加 k 可能是有意义的。

我最近不得不选择一个指标来评估多标签排名算法并进入这个主题,这真的很有帮助。以下是 stpk 答案的一些补充,有助于做出选择。

  • MAP可以适应多标签问题,但代价是近似值
  • MAP不需要在 k 处计算,但当负类占优势时,多标签版本可能不适用
  • MAP(N)DCG都可以重写为排名相关值的加权平均值

细节

让我们关注平均精度(AP),因为平均精度(MAP)只是几个查询中 AP 的平均值。AP在二进制数据上被正确定义为精确召回曲线下的面积,可以重写为每个正项的精确度平均值。(请参阅MAP 上的维基百科文章)一种可能的近似值是将其定义为每个精度的平均值物品。可悲的是,我们失去了排在列表末尾的负面示例对 AP 值没有影响的好属性。(在评估搜索引擎时,这尤其令人难过,负面示例远多于正面示例。一种可能的解决方法是对负面示例进行二次抽样,但代价是其他缺点,例如,具有更多正面项目的查询将变得平等很少有正面例子的查询很难。)

另一方面,这种近似具有很好的特性,可以很好地推广到多标签情况。实际上,在二进制情况下,位置 k 的精度也可以解释为位置 k 之前的平均相关性,其中正样本的相关性为 1,负样本的相关性为 0。这个定义很自然地扩展到存在两个以上不同级别的相关性的情况。在这种情况下,AP 也可以定义为每个位置的相关性平均值的平均值。

这个表达是stpk 在他们的回答中引用的视频的演讲者选择的表达。他在此视频中展示了 AP 可以重写为相关性的加权平均值,排名中第k

wkAP=1Klog(Kk)

其中是要排名的项目数。现在我们有了这个表达式,我们可以将它与 DCG 进行比较。实际上,DCG 也是排名相关性的加权平均值,权重为:K

wkDCG=1log(k+1)

从这两个表达式中,我们可以推断 - AP 对文档的权重从 1 到 0。 - DCG 独立于文档总数对文档进行加权。

在这两种情况下,如果不相关的例子比相关的例子多得多,那么正面的总权重可以忽略不计。对于 AP,一种解决方法是对负样本进行二次抽样,但我不确定如何选择二次抽样的比例,以及是否使其取决于查询或正文档的数量。对于 DCG,我们可以将其切割为 k,但也会出现同样的问题。

如果有人在这里研究这个主题,我很乐意听到更多关于这个的信息。