Learning To Rank之LambdaMART的前世今生

         如图 1所示，每个线条表示文档，蓝色表示相关文档，灰色表示不相关文档，RankNet以pairwise error的方式计算cost，左图的cost为13，右图通过把第一个相关文档下调3个位置，第二个文档上条5个位置，将cost降为11，但是像NDCG或者ERR等评价指标只关注top k个结果的排序，在优化过程中下调前面相关文档的位置不是我们想要得到的结果。图 1右图左边黑色的箭头表示RankNet下一轮的调序方向和强度，但我们真正需要的是右边红色箭头代表的方向和强度，即更关注靠前位置的相关文档的排序位置的提升。LambdaRank[11]正是基于这个思想演化而来，其中Lambda指的就是红色箭头，代表下一次迭代优化的方向和强度，也就是梯度。

         受LambdaNet的启发，LambdaRank对 做因式分解，如下：

         其中

         代入上式得

         其中令

         对于 的文档pair，由于 ，因此 ，所以有

         因此，对每个文档 ，其Lambda为 ，即每一个文档下一次调序的方向和强度取决于所有同一query的其他不同label的文档。

         同时LambdaRank还在Lambda中引入评价指标Z （如NDCG、ERR等），把交换两个文档的位置引起的评价指标的变化 作为其中一个因子，实验表明对模型效果有显著的提升：

         可以看出，LambdaRank不是通过显示定义损失函数再求梯度的方式对排序问题进行求解，而是分析排序问题需要的梯度的物理意义，直接定义梯度，可以反向推导出LambdaRank的损失函数为：

         LambdaRank相比RankNet的优势在于分解因式后训练速度变快，同时考虑了评价指标，直接对问题求解，效果更明显。

7.       LambdaMART

         LambdaRank重新定义了梯度，赋予了梯度新的物理意义，因此，所有可以使用梯度下降法求解的模型都可以使用这个梯度，MART就是其中一种，将梯度Lambda和MART结合就是大名鼎鼎的LambdaMART[12]。

         MART[13][14]的原理是直接在函数空间对函数进行求解，模型结果由许多棵树组成，每棵树的拟合目标是损失函数的梯度，在LambdaMART中就是Lambda。LambdaMART的具体算法过程如下：

         可以看出LambdaMART的框架其实就是MART，主要的创新在于中间计算的梯度使用的是Lambda，是pairwise的。MART需要设置的参数包括：树的数量M、叶子节点数L和学习率v，这3个参数可以通过验证集调节获取最优参数。

         MART支持“热启动”，即可以在已经训练好的模型基础上继续训练，在刚开始的时候通过初始化加载进来即可。下面简单介绍LambdaMART每一步的工作：

         1)  每棵树的训练会先遍历所有的训练数据（label不同的文档pair），计算每个pair互换位置导致的指标变化 以及Lambda，即 ，然后计算每个文档的Lambda： ，再计算每个 的导数w_i，用于后面的Newton step求解叶子节点的数值。

         2)  创建回归树拟合第一步生成的 ，划分树节点的标准是Mean Square Error，生成一颗叶子节点数为L的回归树。

         3)  对第二步生成的回归树，计算每个叶子节点的数值，采用Newton step求解，即对落入该叶子节点的文档集，用公式 计算该叶子节点的输出值。

         4)  更新模型，将当前学习到的回归树加入到已有的模型中，用学习率v（也叫shrinkage系数）做regularization。

         LambdaMART具有很多优势：

         1)  适用于排序场景：不是传统的通过分类或者回归的方法求解排序问题，而是直接求解

         2)  损失函数可导：通过损失函数的转换，将类似于NDCG这种无法求导的IR评价指标转换成可以求导的函数，并且富有了梯度的实际物理意义，数学解释非常漂亮

         3)  增量学习：由于每次训练可以在已有的模型上继续训练，因此适合于增量学习

         4)  组合特征：因为采用树模型，因此可以学到不同特征组合情况

         5)  特征选择：因为是基于MART模型，因此也具有MART的优势，可以学到每个特征的重要性，可以做特征选择

         6)  适用于正负样本比例失衡的数据：因为模型的训练对象具有不同label的文档pair，而不是预测每个文档的label，因此对正负样本比例失衡不敏感

8.       Ranklib开源工具包

         Ranklib[15]是一个开源的Learning ToRank工具包，里面实现了很多Learning To Rank算法模型，其中包括LambdaMART，其源码的算法实现流程大致如下：

         该工具包定义的数据格式如下：

label           qid:$id      $feaid:$feavalue      $feaid:$feavalue      …      #description

         每行代表一个样本，相同查询请求的样本的qid相同，label表示该样本和该查询请求的相关程度，description描述该样本属于哪个待排序文档，用于区分不同的文档。

         该工具包是用Java实现的，在空间使用上感觉有些低效，但整体设计还是挺好的，Ranker的接口设计的很好，值得学习借鉴。

         另外还有很多其他的LambdaMART的开源实现，有兴趣的可以参考[16][17][18]

9.      LambdaMART应用

         最后我们以一个实际场景来介绍LambdaMART的应用。现在很多搜索引擎都有一个下拉提示的功能，学术上叫QAC（Query Auto-Completion，query自动补全），主要作用是在用户在搜索引擎输入框输入query的过程中输出一系列跟用户输入query前缀相匹配的query，供用户选择，减少用户的输入，让用户更加便捷的搜索。

         Milad Shokouhi[19]发现有一些query的热度有明显的用户群倾向，例如，当不同用户输入i时，年轻的女性用户倾向于搜instagram，而男性用户则倾向于搜imdb，所以可以对query的下拉提示做个性化排序。

         Milad Shokouhi使用LambdaMART模型作为个性化排序模型，使用了用户的长期历史、短期历史、性别、年龄、所处地域、提示query的原始排序位置等特征，最终效果提升了9%，效果非常明显。

         Milad Shokouhi的工作说明LambdaMART可以应用于个性化排序，且效果非常不错。

10.   总结

         本文在一些相关书籍、paper和开源代码的基础上，简单梳理了LambdaMART的来龙去脉，简单总结：Lambda在RankNet出炉，在LambdaRank升华，在LambdaMART发扬光大，青出于蓝而胜于蓝，模型的数学推导和实际效果都非常漂亮，只要涉及到排序的场景都可以适用，是排序场景的“万金油”。

参考文献：