AI内参_38_036_机器学习排序算法列表法排序学习
你好，我是洪亮杰。
今天我和你分享的主题是列表法排序学习。
本周，我们已经分别讨论了最基本的单点法排序学习和配对法排序学习两种思路，单点法排序学习思路简单实用，目的就是要把经典的信息检索问题转化成机器学习问题。
配对法排序学习则是把排序的问题转化成针对某个查询关键字每两个文档之间的相对相关性的建模问题。
不过，这两种思路也都有很明显的问题，需要进一步对算法进行优化，以实现我们需要的最终方法。
今天我就来讲，直接优化排序问题的终极方法。
列表法排序学习相对于尝试学习每个样本是否相关，或者两个文档的相对比较关系。
列表法排序学习的基本思路是尝试直接优化，像NDCG这样的指标，从而能够学习到最佳排序结果。
我先来说说列表法排序学习的历史。
二零零零年后，学术界和工业界都开始研究如何用机器学习来解决最优排序问题。
五六年之后，研究者们才开始尝试直接优化整个排序列表。
这方面的研究工作很多都来自微软研究院。
比如，二零零七年左右的艾达rank,来自微软亚洲研究院的徐军和李航。
这篇论文算是较早提出列表法排序观点的研究工作。
同一年，在国际机器学习大会ICML二零零七上发表的list net算是从理论上开启了列表法的大门。
这篇论文也来自微软亚洲研究院，是刘铁岩等人的重要工作。
类似的研究工作在这一年里如雨后春笋般涌现出来。
另外一个方向，接下来我会提到lambda rank出现较早，而lambd MART则稍微晚一点。
这方面的工作是在微软西雅图的研究院开发的主导人士。
克里斯托弗博格斯博格斯二零一六年退休，在微软工作了十六年，可以说他领导的团队发明了微软的搜索引擎，bean的算法。
下面我来详细讲讲列表法、排序学习。
列表法排序学习有两种基本思路，第一种就是直接针对NDCG这样的指标进行优化，目的简单明了，用什么做衡量标准就优化什么目标。
第二种则是根据一个已经知道的最优排序，尝试重建这个顺序，然后来衡量这中间的差异。
我先来说一下第一大思路，直接针对NDCG这样的指标进行优化。
首先重温一下排序测试集的测试原理。
总体来说，所有的基于排序的指标都要考察测试集上。
对于某一个查询关键字来说，某一组文档所组成的排序是否是最优的？有两种比较通用的做法，第一个方法主要适用于二分的相关信息。
对于某一个查询关键字，针对排序产生的顶部的k格文档进行评估，查看精度、召回等。
第二种方法，利用五级相关信息定义。
在这样的情况下，就可以利用类似于NDCG这样的评价指标。
具体解读。
你可以回到本周前面两期我们讲解过的内容进行复习。
那么直接优化排序指标的难点和核心在什么地方呢？难点在于希望能够优化NDCG指标。
这样的理想很美好，但是现实却很残酷。
Ndcg以及我们之前说过的，基于顶部的k的精度，都是在数学的形式上的非连续和非微分。
那么绝大多数的优化算法都是基于连续和可微分函数的，因此直接优化难度比较大。
针对这种情况，主要有这么几种方法。
第一种方法是，既然直接优化有难度，那么就找一个近似NDCG的另外一个指标。
而这种替代的指标是连续和可微分的。
只要我们建立这个替代指标和NDCG之间的近似关系，那么就能够通过优化这个替代指标，达到逼近优化NDCG的目的。
这类的代表性算法有soft rank和app rank.第二种方法是尝试从数学的形式上写出一个NDCG等指标的边界，然后优化这个边界。
比如，如果推导出一个上界，那就可以通过最小化这个上界来优化NDCG这类的代表性算法有SVM、 map和SVMNDCG.第三种方法则是希望从优化算法上下手看，是否能够设计出复杂的优化算法，来达到优化NDCG等指标的目的。
对于这类算法来说，算法要求的目标函数可以是非连续和非可微分的这类的代表性算法有at rank和rank GP.说完了第一大思路后，我们再来看看第二大思路。
这种思路的主要假设是已经知道了针对某个搜索关键字的完美排序。
那么怎么通过学习算法来逼近这个完美排序呢？我们希望缩小预测排序和完美排序之间的差距。
值得注意的是在这种思路的讨论下，优化NDCG等排序的指标并不是主要目的。
这里面的代表有list net和list MLE.讲了这两大思路以后，最后我再来提一下第三类思路。
这类思路的特点是在纯列表法和配对法之间寻找一种中间解法。
具体来说，这类思路的核心思想是从NDCJ等指标中受到启发，设计出一种替代的目标函数。
这一步还和我刚才介绍的第一大思路中的第一个方向，有异曲同工之妙，都是希望能够找到替代品。
这第三类思路更进一步的则是找到替代品以后，把直接优化列表的想法退化成优化某种配对。
这第二步就更进一步，简化了问题。
这个方向的代表方法就是微软发明的lambda rank,以及后来的lambda MART.微软发明的这个系列算法，成了微软的搜索引擎bean的核心算法之一。
我这里简单提一下lambda rank这个系列模型的基本思想。
首先，微软的学者们注意到一个排序算法是否达到最优的情况。
简单来看，就是查看当前的排序中相比于最优的情况有哪些两两文档的关系搞错了，学习最优排序的问题就被转化成了减小。
这些两两排错的关系更进一步。
在设计这个优化过程中，我们其实并不需要知道真正的目标函数的形式，而仅仅需要某种形式的梯度。
这里有这样一个洞察，对于绝大多数的优化过程来说，目标函数很多时候仅仅是为了推导梯度而存在的。
而如果我们直接就得到了梯度，但自然就不需要目标函数了。
最后，通过实验微软的学者们把这个NDCG通过梯度变化的差值再乘以这个梯度，这样就达到了增强效果的目的。
早期的lambda rank,特别是rank, nenet是采用了神经网络来进行模型训练，而lambda ART则采用了基于决策树的思想更换到了基于决策树的方法。
后来实践证明，基于决策树的方法，对于排序问题非常有效果，也就成了很多类似方法的标准配置。
最后有一点需要你注意哦，我们讨论了不同的列表法、思路、列表法。
从理论上和研究情况来看，都是比较理想的排序。
学习方法。
因为列表法尝试统一排序学习的测试指标和学习目标。
尽管管学学研研究中纯列表法表现优异，但是在实际中类似于lambdrank这类思路，也就是基于配对法和列表法之间的混合方法法，更欢迎迎，因为从总体上列表表的运算复杂度都比较高，而而从工业级的实际应用中，真正的究法不不特价值，因此列表法的主要贡献目前还多是学术价值。
今天我为你讲了列表法排序学习，你可以看到列表法排序有很多种思路。
在二零零零年到二零一零年之间，是一个非常活跃的研究领域，积累了大量的成果。
一起来回顾一下要点，第一，简要介绍了列表法排序学习的历史。
第二，详细介绍了列表法排序学习的三大思路，以及每个思路里的主要细节和方法。
最后给你留一个思考题，列表法，是不是就完全解决了排序算法的问题呢？补充一点，在文末，我列了一些主要的参考文献。
如果你想了解关于排序法的更多细节，可以点击文稿查看，希望对你会有帮助。
欢迎你给我留言，和我一起讨论。