Evaluation 对于一个新的信息建索算法，我们该如何去判断这个算法的好坏呢？ 宏观上来看，一个好的算法上线以后，用户的反馈会发生变：用户的点击更多，对于电商网站来说，用户花的钱更多，并且用户可能会有重复的点击行为。但是这些反馈很难量化地评估，因为在此期间可能页面的UI发生了变动，导致用户不喜欢这个网站。我们需要一个评估搜索算法好坏的标准。 实际上，搜索算法的评估需要三个元素：

  1. 和大多数机器学习问题一样，搜索算法的评估需要一个数据集，
  2. 测试的query

  3. query和document之间的关联度。 前两者只要从日常的搜索日志中提取即可，但是如何评估一个query和搜索到的document的关联度的呢？

  4. 无排序搜索 无排序搜索将文档视为set，并不关心搜索结果的顺序，只关心搜索结果与query的相关性。对于一个搜索q，准确率 \(precision=\frac{搜索到的相关文档数量}{搜索到的文档数量}\) 召回率 \(recall=\frac{搜索到的相关文档数量}{相关文档数量}\) 更加准确地来说：

relevant nonrelevant retrieved tp(true positive) fp(false positive) Not retrieved tn(true negetive) fn(fase negetive)

\(p =\frac{tp}{tp+fp}\) 对于以上的四种情况来说，很明显tp和fn是准确的搜索结果：相关的都被搜到了，而不相关的都没有被搜到，所以可以很直观地得出一个无排序搜索的评价标准：accuracy \(r=\frac{tp+fn}{tp+fp+fn+tn}\) 对于很多机器学习的二分类问题来说这是一个很好的评价标准:正确的结果的比率，只不过此时的recall不再具有召回的意味。 召回率与查准率是一对相互冲突的指标，通常用F measure作为对两者的trade-off:F measure是两者的调和平均： \(f = \frac{1}{a\frac{1}{p}+(1-a)\frac{1}{r}}\) 然而对于搜索的问题来说，仍然存在一些问题：如果

  1. 有排序搜索 考虑以下实例：对于一个搜索，结果集为 \(D_0, D_1, D_2, D_3, D_4, D_5\) 各结果对应的相关度为 \(3, 2, 3, 0, 1, 2\) 数字越大代表结果与搜索越相关。 CG, DCG和NDCG CG(cumulative gain)中文翻译为累计增益。此处用Gain这个词可能是因为，对于query的每一个结果，其相关度用数字来表示，如5表示非常理想，1表示根本毫无关联。这个相关度即可看作对于一个结果的增益，增益大的结果应当在结果集的上方出现。 顾名思义，CG为所有增益的累计， \(CG_p=\sum_{n=1} ^{p} rel_i\) 对于上面的例子： \(CG_6=3+2+3+0+1+2=11\) 结果集内元素的顺序的调换不会影响CG的大小，所以CG能衡量的内容比较有限。 DCG DCG(Discounted CG)，discount原意为商品打折，此处指gain加权， DCG: \(DCG=\sum_{n=1}^{p} \frac{rel_i}{log_2(i+1)}\) DCG给每一个结果的相关度乘以一个系数，这个系数大小随着位置的增大而减小。因此：更相关的结果排名靠后时，DCG会变小；越相关的结果排名越靠前，则DCG越大。 对于上面的例子， \(DCG_6=6.681\) DCG也有一些变种，但是也都换汤不换药，比如： \(DCG=\sum_{n=1}^{p} \frac{2^{rel_i} -1}{log_2(i+1)}\) DCG可以衡量一个query的结果集的排序的好坏，但是各个query的结果数量不一样，对于有多个query的数据集，DCG无法衡量两者排序的好坏，我们需要一个归一化的DCG NGCG(Normalized DCG) nDCG指归一化的DCG，对于一个query， \(nDCG=\frac{DCG_p}{max(DCG_p)}\) DCG的最大值即排序最理想的情况下的DCG，此时结果的排序与相关度的排序相同。很明显nDCG的取值范围为(0, 1]，可以用于跨query的比较。 使用nDCG的缺陷在于：很难获得完整