周一我们介绍了基于“二元相关”原理的线下评测指标。可以说，从1950年开始，这种方法就主导了文档检索系统的研发工作。然而，“二元相关”原理从根本上不支持排序的评测，这就成了开发更加准确排序算法的一道障碍。于是，研究人员就开发出了基于“多程度相关”原理的评测标准。今天我就重点来介绍一下这方面的内容。
从“二元相关”出发，自然就是给相关度更加灵活的定义。在一篇发表于NIPS 2007的文章中（参考文献[1]），雅虎的科学家介绍了雅虎基于五分标准的相关评价体系，从最相关到最不相关。而在同一年的SIGIR上，谷歌的科学家也发表了一篇文章（参考文献[2]），介绍了他们的“多程度”相关打分机制。至此之后，基于“多程度相关”原理的评价标准慢慢被各种搜索系统的研发者们所接受。
在这样的趋势下，基于“二元相关”的“精度”（Precision）和“召回”（Recall）都变得不适用了。我们需要新的、基于“多程度相关”的评价指标。
芬兰的科学家在2000年的SIGIR上（参考文献[3]）发表了一种计算相关度评测的方法。这种方法被广泛应用到了“多程度相关”的场景中。那么，芬兰科学家发明的方法是怎样的呢？
这种方法被称作是“折扣化的累积获得”（Discounted Cumulative Gain），简称“DCG”。 在介绍DCG之前，我们首先假定，位置1是排位最高的位置，也就是顶端的文档，而位置数随着排位降低而增高，位置10就是第一页最后的文档。
DCG的思想是这样的。
首先，一个排序的整体相关度，是这个排序的各个位置上的相关度的某种加权。这样用一个数字就描述了整个排序。只要排序的结果不同，这个数字就会有所不同。因此，这就避免了“精度”或“召回”对排序不敏感的问题。
其次，每个位置上面的“获得”（Gain）是和这个文档原本定义的相关度相关的，但是，根据不同的位置，要打不同的“折扣”。位置越低（也就是位置数越大），折扣越大。这就是DCG名字的由来。
在原始的DCG定义中，“折扣”是文档的相关度除以位置的对数转换。这样，既保证了位置越低（位置数大），折扣越大，还表达了，高位置（位置数小）的差别要大于低位置之间的差别。这是什么意思呢？意思就是，如果某一个文档从位置1挪到了位置2，所受的折扣（或者说是损失）要大于从位置9挪到了位置10。在这样的定义下，DCG鼓励把相关的文档尽可能地排到序列的顶部。
事实上，假设我们有5个文档，假定他们的相关度分别是1、2、3、4、5，分别代表“最不相关”、“不相关”、“中性”、“相关”和“最相关”。那么，在DCG的定义下，最佳的排序就应该是把这5个文档按照相关度的顺序，也就是5、4、3、2、1来排定。任何其他的顺序因为根据位置所定义的“折扣获得”的缘故，都会取得相对较小的DCG，因此不是最优。DCG比“精度”和“召回”能够更好地表达对排序的评估。
但直接使用DCG也存在一个问题。如果我们有两个查询关键字，返回的文档数不一样，那么直接比较这两个查询关键字的DCG值是不“公平”的。原因在于DCG的“加和”特性，结果肯定是越加越大，因此不能直接比较两个不同查询关键字的DCG值。
有没有什么办法呢？把DCG加以“归一化”的指标叫做 nDCG （Normalized Discounted Cumulative Gain）。nDCG的思路是下面这样的。
首先，对某一个查询关键字的排序，根据相关信息，来计算一组“理想排序”所对应的DCG值。理想排序往往就是按照相关信息从大到小排序。然后，再按照当前算法排序所产生的DCG值，除以理想的DCG值，就产生了“归一化”后的DCG，也就是我们所说的nDCG值。简单来说，nDCG就是把DCG相对于理想状态进行归一化。经过nDCG归一化以后，我们就可以比较不同查询关键字之间的数值了。
这里需要说明的是，我们上面介绍的是DCG的原始定义。后来微软的学者们在2005年左右发明了另外一个变种的DCG，基本原理没有发生变化，只是分子分母有一些代数变形。这个新的版本后来在工业界得到了更加广泛的应用。如果你感兴趣，可以查看文末的参考文献[4]。
直到今天，nDCG以及DCG依然是评价排序算法以及各种排序结果的标准指标。
不管是我们之前谈到的“精度”和“召回”，还是今天介绍的nDCG，我们都是使用一个“数”来描述了相对于某个查询关键字，一组结果的好坏。当我们有多个查询关键字的时候，我们该如何比较两个不同排序的结果呢？
这里面的一个问题是，相对于两个不同的排序A和B来说，可能结果各有千秋，也许对于某一个关键字A比B的表现要好，但是另外一个关键字B就比A的结果更棒。这怎么办呢？
也许你会想到用平均值来描述A和B的表现。这的确是很好的第一步。于是，我们就计算A和B，两个排序的平均表现。这样对于这两个排序而言，我们就有了两个数值来表达这两个排序的好坏。
然而，很快我们就会遇到问题。假设A的nDCG平均值是0.781，B的nDCG平均值是0.789，我们可以下结论认为B是比A更好的排序算法吗？
答案当然是不一定。这种情况，我们就需要依赖统计工具“假设检验”来评价两个排序的好坏。
我这里就不去复习假设检验的细节了，简单说一个经常使用的工具。
如果我们比较A和B是在同一组查询关键字上的话，那我们常常可以使用“两个样本的配对T检验”（Two Sample Paired T-Test）。这里所谓的“配对”是指A和B的结果是可以一一比较的。这里的“T检验”其实就是说借助“T分布”或者我们通常所说的“学生分布”来进行假设检验。如果我们是在不同查询关键字集合中进行比较的话，还有其他的假设检验工具，这里就不展开了。
值得注意的是，假设检验本身也不是“万灵药”。第一，怎么最有效地在排序结果上进行假设检验还是一个研究话题，包括我们刚说的“两个样本的配对T检验”在内的所有方法都不是“金科玉律”。第二，依靠假设检验得出来的结论，仅仅是统计意义上的“好坏”，和这些系统在用户面前的表现可能依然会有很大差距。因此，对于假设检验的结果也要带有“批判”的眼光。
今天我为你讲了现代搜索技术中如何评价我们构建的系统，特别是如何评价排序系统。
一起来回顾下要点：第一，简要讲解了基于“多程度相关”的评价体系，包括其由来和DCG以及nDCG的概念。第二，详细介绍了如何来比较两个排序的好坏。
最后，给你留一个思考题，如果我们只有“二元”相关信息，能不能用nDCG来评价好坏呢？
欢迎你给我留言，和我一起讨论。
参考文献
Ben Carterette and Rosie Jones. Evaluating search engines by modeling the relationship between relevance and clicks. Proceedings of the 20th International Conference on Neural Information Processing Systems (NIPS’07), J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis (Eds.). Curran Associates Inc., USA, 217-224,2007.
Scott B. Huffman and Michael Hochster. How well does result relevance predict session satisfaction? Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval (SIGIR '07). ACM, New York, NY, USA, 567-574, 2007.
Kalervo Järvelin and Jaana Kekäläinen. IR evaluation methods for retrieving highly relevant documents. Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval (SIGIR '00). ACM, New York, NY, USA, 41-48, 2000.
Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to rank using gradient descent. Proceedings of the 22nd international conference on Machine learning (ICML '05). ACM, New York, NY, USA, 89-96, 2005.
评论