LambdaMART笔记

LambdaMART是一种state-of-art的Learning to rank算法，由微软在2010年提出[1]。在工业界，它也被大量运用在各类ranking场景中。LambdaMART可以看做GDBT版本的LambdaRank，而后者又是基于RankNet发展而来的。RankNet最重要的贡献是提出了一种pairwise的用于排序的概率损失函数，而LambdaRank又在损失函数中巧妙的引入了NDCG等ranking metrics来优化排序效果。LambdaMART则是集大成者，它结合了上述两篇文章中提出的Lambda函数以及GDBT这个效果经过实践证明的ensemble算法，在各种排序问题中均能取得不错的效果。下面是目前的一些开源实现：

1. Ranklib
2. Xgboost

RankNet

RankNet是2005年微软提出的一种pairwise的Learning to rank算法，它从概率的角度来解决排序问题。RankNet提出了一种pairwise的概率损失函数，并可以应用于任意对参数可导的学习算法。在论文中，RankNet基于神经网络实现，除此之外，GDBT等模型也可以应用该损失函数。
RankNet是一个pairwise的算法，它首先将训练数据中同一Query下的doc两两组成pair，用{U_i，U_j}表示。模型的学习目标是得到一个打分函数f(x)，它的输入是某个doc的特征向量x，输出是一个实数，值越高代表该doc的排序位置应该越靠前。也就是说，当f(x_i)>f(x_j)时，U_i的排序位置应该在U_j之前，用U_i ▷ U_j表示。基于此，我们定义U_i比U_j排序位置更靠前的概率如下，其中，s=f(x).

我们的目标概率（理想情况，预测概率应该尽可能拟合的概率）如下：

为了方便计算，我们令：

这样，根据U_i和U_j的标注得分，就可以计算P‘_ij。
有了目标概率和模型预测概率，使用交叉熵损失函数（cross entropy loss function）作为概率损失函数，它衡量了预测概率和目标概率在概率分布上的拟合程度：

求上式关于s_i的偏导，由于对称性可以得到如下结论：

计算C关于模型参数w_k的偏导，并应用gradient descent求解：

总的来说，RankNet从概率角度定义了排序问题的loss function，并通过梯度下降法求解。所以RankNet依赖的模型必须是平滑的，保证梯度是可以计算的。在paper中，作者选择一个两层的神经网络作为排序模型。除此之外，选择GBDT也可以取得不错的效果。

交叉熵
设随机变量X服从的概率分布为p(x)，往往p(x)是未知的，我们通过统计方法得到X的近似分布q(x)，则随机变量X的交叉熵为：

它衡量了q(x)和p(x)的拟合程度

加速学习算法

在上述的学习过程中，每一对样本{U_i，U_j}都会更新一次参数w，如果采用BP神经网络模型，每一次更新都需要先前向预测，再误差后向反馈，训练过程非常慢。因此，有了下面的加速算法；
对于给定的样本对U_i，U_j，我们有如下推导：
![][07]
这里我们定义：
![][08]
梯度下降量的求解如下：
![][09]
其中，为了计算简便，我们令{i,j}满足U_i>U_j，所以有
![][10]
上两式合并有：
![][12]
其中：
![][11]
这样，我们将每更新一次w，计算一个样本对{U_i，U_j}
改为了计算U_i所能组成的所有样本对。加速算法可以看成是一种mini-batch的梯度下降算法。

LambdaRank

在RankNet中，我们使用了交叉熵概率损失函数，并作为最优化的目标。但对于IR问题，通常选择NDCG、ERR作为评价指标，这两者间存在一定的mismatch。另一方面，NDCG、ERR是非平滑、不连续的，无法求梯度，不能直接运用梯度下降法求解，将其直接作为优化目标是比较困难的。因此，LambdaRank选择了直接定义cost function的梯度来解决上述问题。
LambdaRank是一个经验算法，它直接定义的了损失函数的梯度λ，也就是Lambda梯度。Lambda梯度由两部分相乘得到：(1)RankNet中交叉熵概率损失函数的梯度；(2)交换U_i，U_j位置后IR评价指标Z的差值。具体如下：
![][15]
Z可以是NDCG、ERR、MRR、MAP等IR评价指标
损失函数的梯度代表了文档下一次迭代优化的方向和强度，由于引入了IR评价指标，Lambda梯度更关注位置靠前的优质文档的排序位置的提升。有效的避免了下调位置靠前优质文档的位置这种情况的发生。
LambdaRank相比RankNet的优势在于考虑了评价指标，直接对问题求解，所以效果更好。

LambdaMART

LambdaRank中重新定义了损失函数的梯度，而这个Lambda梯度可以应用于任何使用梯度下降法求解的模型。自然，我们想到了将Lambda梯度和MART结合，这就是LambdaMART。

MART

学习过程

Ranklib