搜索排序

单点法排序学习（Pointwise Learning to Rank）

看做二分分类（Binary Classification）的问题，某一个查询关键字和某一个文档是否配对。

评价指标：“精度”（Precision）和“召回”（Recall），TopK，F1分数。

可以使用多类分类（Multi-Class Classification）的评价方法，把五级相关度当做五种不同的标签，来看分类器的分类准确度。比如，针对某一个查询关键字，我们不再只关心某个文档是否相关，而是给出一个相关程度的打分，从“最相关”、“相关”、“不能确定”到“不相关”、“最不相关”，一共五级定义。

基于五级定义的排序评价方法：NDCG（Normalized Discounted Cumulative Gain）。

NDCG 这个指标的假设是，在一个排序结果里，相关信息要比不相关信息排得更高，而最相关信息需要排在最上面，最不相关信息排在最下面。任何排序结果一旦偏离了这样的假设，就会受到“扣分”或者说是“惩罚”。

配对法排序学习（Pairwise Learning to Rank）

2000 年左右，研究人员开始利用支持向量机（SVM）来训练排序算法，来自康奈尔的索斯藤·乔基姆斯（Thorsten Joachims）就构建了基于特征差值的 RankSVM，一度成为配对法排序学习的经典算法。

2005 年，当时在雅虎任职的研究人员郑朝晖等人，开始尝试用 GBDT（Gradient Boosting Decision Tree，梯度提升决策树）这样的树模型来对文档之间的两两关系进行建模。郑朝晖后来成为一点资讯的联合创始人。

2005 年，微软的学者克里斯·博格斯（Chris Burges）等人，开始使用神经网络训练 RankNet 文档之间两两关系的排序模型。这是最早使用深度学习模型进行工业级应用的尝试。这篇论文在 2015 年获得了 ICML 2015（International Conference on Machine Learning，国际机器学习大会）的 10 年“经典论文奖”。

总体来说，测试的原理和单点法一样，都是要考察测试集上，对于某一个查询关键字来说，某一组文档所组成的排序是否是最优的。

对于一个查询关键字来说，最重要的其实不是针对某一个文档的相关性是否估计得准确，而是要能够正确估计一组文档之间的“相对关系”。只要相对关系估计正确了，那么从排序这个角度来说，最后的结果也就准确了。

RankSVM 从本质上来说其实还是 SVM，也就是支持向量机，只不过建模的对象从单一文档变成了文档的配对。更加复杂的模型，比如 GBRank，就是通过树的聚合模型 GBDT 来对文档之间的关系直接建模，希望通过函数值的差值来表达文档的相关性差异。

需要注意的是，配对法排序学习特别是在测试集预测的时候，可能会有计算复杂度的问题。因为原则上，必须要对所有的两两关系都进行预测。现实中，如果是基于线性特征的差值来进行样本构造的话，那么测试还可以回归到线性复杂度的情况。

列表法排序学习（Listwise Learning to Rank）

列表法排序学习的基本思路是尝试直接优化像 NDCG（Normalized Discounted Cumulative Gain）这样的指标，从而能够学习到最佳排序结果。

这方面的研究工作很多都来自微软研究院。比如 2007 年左右的 AdaRank，就来自微软亚洲研究院的徐君和李航。这篇论文算是较早提出列表法排序观点的研究工作。同一年在国际机器学习大会 ICML 2007（International Conference on Machine Learning）上发表的 ListNet 算是从理论上开启了列表法的大门。这篇论文也来自微软亚洲研究院，是刘铁岩等人的重要工作。

另外一个方向，LambdaRank 出现稍早，而 LambdaMART 则稍微晚一点。这方面的工作是在微软西雅图的研究院开发的。主导人是克里斯托弗·博格斯（Christopher J.C. Burges）。博格斯 2016 年退休，在微软工作了 16 年，可以说，他领导的团队发明了微软的搜索引擎 Bing 的算法。

列表法排序学习有两种基本思路。第一种，就是直接针对 NDCG 这样的指标进行优化。目的简单明了，用什么做衡量标准，就优化什么目标。第二种，则是根据一个已经知道的最优排序，尝试重建这个顺序，然后来衡量这中间的差异。

先来看第一种思路。

第一种方法是，既然直接优化有难度，那就找一个近似 NDCG 的另外一种指标。而这种替代的指标是“连续”和“可微分”的 。只要我们建立这个替代指标和 NDCG 之间的近似关系，那么就能够通过优化这个替代指标达到逼近优化 NDCG 的目的。这类的代表性算法的有 SoftRank 和 AppRank。

第二种方法是，尝试从数学的形式上写出一个 NDCG 等指标的“边界”（Bound），然后优化这个边界。比如，如果推导出一个上界，那就可以通过最小化这个上界来优化 NDCG。这类的代表性算法有 SVM-MAP 和 SVM-NDCG。

第三种方法则是，希望从优化算法上下手，看是否能够设计出复杂的优化算法来达到优化 NDCG 等指标的目的。对于这类算法来说，算法要求的目标函数可以是“非连续”和“非可微分”的。这类的代表性算法有 AdaRank 和 RankGP。

第二种思路。

我们希望缩小预测排序和完美排序之间的差距。值得注意的是，在这种思路的讨论中，优化 NDCG 等排序的指标并不是主要目的。这里面的代表有 ListNet 和 ListMLE。

第三类思路。这类思路的特点是在纯列表法和配对法之间寻求一种中间解法。具体来说，这类思路的核心思想，是从 NDCG 等指标中受到启发，设计出一种替代的目标函数。

找到替代品以后，把直接优化列表的想法退化成优化某种配对。这第二步就更进一步简化了问题。这个方向的代表方法就是微软发明的 LambdaRank 以及后来的 LambdaMART。微软发明的这个系列算法成了微软的搜索引擎 Bing 的核心算法之一。

LambdaRank 这个系列模型的基本思想。

首先，微软的学者们注意到，一个排序算法是否达到最优的情况，简单来看，就是查看当前的排序中，相比于最优的情况，有哪些两两文档的关系搞错了。学习最优排序的问题就被转化成了减小这些两两排错的关系。更进一步，在设计这个优化过程中，我们其实并不需要知道真正的目标函数的形式，而仅仅需要某种形式的梯度（Gradient）。

这里有这样一个洞察，对于绝大多数的优化过程来说，目标函数很多时候仅仅是为了推导梯度而存在的。而如果我们直接就得到了梯度，那自然就不需要目标函数了。最后，通过实验，微软的学者们把这个 NDCG 通过梯度变化的差值再乘以这个梯度，这样就达到了增强效果的目的。

早期的 LambdaRank，特别是 RankNet 是采用了神经网络来进行模型训练，而 LambdaMART 则采用了“集成决策树”的思想，更换到了基于决策树的方法。后来实践证明，基于决策树的方法对于排序问题非常有效果，也就成了很多类似方法的标准配置。

列表法从理论上和研究情况来看，都是比较理想的排序学习方法。因为列表法尝试统一排序学习的测试指标和学习目标。尽管在学术研究中，纯列表法表现优异，但是在实际中，类似于 LambdaRank 这类思路，也就是基于配对法和列表法之间的混合方法更受欢迎。因为从总体上看，列表法的运算复杂度都比较高，而在工业级的实际应用中，真正的优势并不是特别大，因此列表法的主要贡献目前还多是学术价值。