【search】概述搜索排序算法的评价指标MAP,NDCG,MR
【原文地址已失效，故粘贴于此】
By Eletva, eletva.com
我们知道，每个算法都有其评估的手段，借此用以指导当前算法模型的好坏，搜索rank是一个相对而言比较常见又比较特殊的场景，因为最后我们需要评估的是一个序列的好坏，是各个个体的相互关系，而不是大部分机器学习算法那样评估的是每个个体的处理好坏。因此，要深入了解搜索rank的机制，那么首先要知道我们是怎样来评估一种排序算法是好的算法，而另一种是不好的。本文中提到了三种评估的方式，都是有各自的试用场景。
因为搜索的意思形态不一样，可能采取的评估指标也可能会随之变化，以下提到的评估手段都可能是当用或者复用，要适当变之。。。
1. MAP（mean average precision）：
MAP的衡量标准比较单一，q(query，搜索词)与d(doc，检索到的doc)的关系非0即1，核心是利用q对应的相关的d出现的位置来进行排序算法准确性的评估，比如q1对应相关的d排名是1，2，5，7（假设q1有4个相关d），那么对于q1的ap（average precision）的计算就是（1/1+2/2+3/5+4/7）/4=ap1，对于q2的排序结果结果中与之相关的d的排名是2，3，6（假设q2有5个相关d），那么对于q2的ap就是（1/2+2/3+3/6+0+0）/5=ap2，那么这个排序算法的MAP就是（ap1+ap2）/2
MAP 是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank 越高)，MAP就应该越高。如果系统没有返回相关文档，则准确率默认为0。
这里注意的是，在利用MAP的评估的时候，需要知道：1. 每个q有多少个相关的d; 2. 排序结果中这些d的位置 3. 相关的定义
延展：或许这个MAP可以进行部分改进，相关定义的部分可以考虑用0-1之间的系数来确定，而到实际使用中可以用ctr，gmv这些指标进行替换
2. 对于NDCG(Normalized Discounted Cumulative Gain)的理解
N指的是归一化，D指的是衰减率，C指的累加，G指的是熵，其实这个公式的关键就是就是熵，再多了三个形容词：归一化的，带有衰减函数的，再带有累加的熵即是了
仔细看一下上面的公司，停顿两分钟就可以体会其中的含义了
1）公式中最核心的Gain用一个指数函数来表示了，这与一般的信息熵的概念有些不一样，可能指代表着一个信息量的关系的变化，也许这说明熵是可以以任意形式出现的，anyway，这个还要再研究一下
2）那么接下去就是带有衰减因子的G，也就是DG了，用来表示与位置的衰减关系，因为排名越往后，那么说明越被点击的可能越小，因此越往后的衰减因子越小，实际操作中有很多衰减因子的定义函数，比如C*1/log(1+j)，上式子是指C为1的特殊形式， 其中C一般还会取值log2之类的一些经验值，这个都可以根据实际情况来进行变化（不过，我们应该清楚的认识到因为）
3）接着，就是累加，将带有衰减因子的熵进行累加，每个排名处进行累加
4）最后，是归一化，用当前的CDG/MAX，MAX即是理想状态下的CDG，那么就进行了归一化处理
总结：这里的相关性体现在Gain的计算处，r将相关性分成了多个档位，这里可以用实际操作中需要的指标去代替
3. MRR（mean reciprocal rank），倒数排序法
这个是最简单的一个，因为他的评估假设是基于唯一的一个相关结果，比如q1的最相关是排在第3位，q2的最相关是在第4位，那么MRR=(1/3+1/4)/2，MRR方法主要用于寻址类检索（Navigational Search）或问答类检索（Question Answering）
--------------------------------------------------------------------------------------------
另外谈到两个常见的算法指标的一些比较本质的东西，一个是Precision（准确率）与Recall（召回率）的关系，另一个是F-Measure，一个用来衡量P与R的指标
P与R之间的关系有些符合其齐夫定律，召回率和准确率分别反映了检索系统的两个最重要的侧面，而这两个侧面又相互制约。因为大规模数据集合中，如果期望检索到更多相关的文档，必然需要“放宽”检索标准，因此会导致一些不相关结果混进来，从而使准确率受到影响。类似的，期望提高准确率，将不相关文档尽量去除时，务必要执行更“严格”的检索策略，这样也会使一些相关的文档被排除在外，使召回率下降。
F-Measure：公式是基于P与R的调和平均数，1/[（1-lamda）*1/p+lamda*1/r), 一般lamda会取0.5，表示p与r的平衡，这里使用调和平均数而不是通常的几何平均或算术平均，原因是调和平均数强调较小数值的重要性，能敏感的反映小数字的变化，因此更适合用来反映算法效果。因为常常，一个指标比多个指标能够方便快捷的定位好坏。
本文版权属作者@eletva所有，转载需注明出处
