Learning to Rank for IR的评价指标—MAP,NDCG,MRR

Map：相关性，1 or 0，计算排序后rank值
NDCG：
设定相关性等级（2^5-1, 2^4-1…）
计算累计增益值（嗯，就累加起来）
计算折算因子log(2)/log(1+rank) （越靠前的，越容易被点击）
归一化到NDCG，为了不同等级上的搜索结果的得分值容易比较
4.1. 首先计算理想list的MaxDCG
4.2 相除即可
MRR：”把标准答案在被评价系统给出结果中的排序取倒数作为它的准确度，再对所有的问题取平均。”
———————————————–
http://www.cnblogs.com/HappyAngel/p/3535919.html

NDCG如何理解？对于搜索引擎，本质是用户搜一个query，引擎返回一个结果列表，那么如何衡量这个结果列表的好坏？我能够想到的是：

我们希望把最相关的结果放到排名最靠前的位置，因为大部分用户都是从上往下阅读的，那么最相关的在前面可以最大程度减少用户的阅读时间；
我们希望整个列表的结果尽可能的和query相关；
第一个条件的满足是首要的，而第二个条件的加入是保证整体结果质量，而这两个条件都体现在了NDCG里面，首先，计算NDCG，需要计算Gain，这个gain即是每条结果的质量的定义，NDCG把所有结果相加最终相加保证，整体质量越高的列表NDCG值越大。同时，Discounted的设计使得越靠前的结果权重越大，这保证了第一条，更相关的排在靠前的结果会有更大的NDCG值。从这两点看，以NDCG为优化目标，保证了搜索引擎在返回结果总体质量好的情况下，把更高质量结果排在更前面。

NDCG提供了一种计算方式，当我们有其他排名类似的需求的时候，NDCG都是值得参考的，其Gain以及Discounted的计算的变化可以产生很多其他有价值的metrics

———————————————–
http://www.cnblogs.com/ywl925/archive/2013/08/16/3262209.html

MAP(Mean Average Precision)：

单个主题的平均准确率是每篇相关文档检索出后的准确率的平均值。主集合的平均准确率(MAP)是每个主题的平均准确率的平均值。MAP 是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank 越高)，MAP就可能越高。如果系统没有返回相关文档，则准确率默认为0。
例如：假设有两个主题，主题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。”

NDCG(Normalized Discounted Cumulative Gain)：
计算相对复杂。对于排在结位置n处的NDCG的计算公式如下图所示：

在MAP中，四个文档和query要么相关，要么不相关，也就是相关度非0即1。NDCG中改进了下，相关度分成从0到r的r+1的等级(r可设定)。当取r=5时，等级设定如下图所示：

(应该还有r=1那一级，原文档有误，不过这里不影响理解)

例如现在有一个query={abc}，返回下图左列的Ranked List(URL)，当假设用户的选择与排序结果无关(即每一级都等概率被选中)，则生成的累计增益值如下图最右列所示：

考虑到一般情况下用户会优先点选排在前面的搜索结果，所以应该引入一个折算因子(discounting factor): log(2)/log(1+rank)。这时将获得DCG值(Discounted Cumulative Gain)如下如所示：

最后，为了使不同等级上的搜索结果的得分值容易比较，需要将DCG值归一化的到NDCG值。操作如下图所示，首先计算理想返回结果List的DCG值：

然后用DCG/MaxDCG就得到NDCG值，如下图所示：

MRR(Mean Reciprocal Rank)：

是把标准答案在被评价系统给出结果中的排序取倒数作为它的准确度，再对所有的问题取平均。相对简单，举个例子：有3个query如下图所示：

(黑体为返回结果中最匹配的一项)

可计算这个系统的MRR值为：(1/3 + 1/2 + 1)/3 = 11/18=0.61。