美文网首页Paper
LambdaMART笔记

LambdaMART笔记

作者: 天行剑 | 来源:发表于2015-11-02 22:01 被阅读7198次

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,用{Ui,Uj}表示。模型的学习目标是得到一个打分函数f(x),它的输入是某个doc的特征向量x,输出是一个实数,值越高代表该doc的排序位置应该越靠前。也就是说,当f(xi)>f(xj)时,Ui的排序位置应该在Uj之前,用Ui ▷ Uj表示。基于此,我们定义Ui比Uj排序位置更靠前的概率如下,其中,s=f(x).

我们的目标概率(理想情况,预测概率应该尽可能拟合的概率)如下:

为了方便计算,我们令:

这样,根据Ui和Uj的标注得分,就可以计算P‘ij
有了目标概率和模型预测概率,使用交叉熵损失函数(cross entropy loss function)作为概率损失函数,它衡量了预测概率和目标概率在概率分布上的拟合程度:

求上式关于si的偏导,由于对称性可以得到如下结论:

计算C关于模型参数wk的偏导,并应用gradient descent求解:

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

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

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

加速学习算法

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

LambdaRank

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

LambdaMART

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

MART

学习过程

Ranklib

相关文章

  • LambdaMART笔记

    LambdaMART是一种state-of-art的Learning to rank算法,由微软在2010年提出[...

  • LambdaMart

    有用的几个两个tutorialhttp://www.cnblogs.com/wowarsenal/p/390035...

  • LambdaMART之见底之解

    引入 lambdamart是什么呢? 无非是 lamda + mart. lambda 和 mart又是什么呢? ...

  • lambdaMART-1.GBDT

    boosting思想:叠加多个弱模型,渐进的逼近真实情况。问题在于:如何保证拟合方向正确,如何叠加弱模型的结果。 ...

  • 信息检索排序算法 LambdaRank 和 LambdaMART

    排序算法在搜索引擎中非常重要,需要根据用户的查询 q,对一些相关的文档进行排序,尽可能地让用户感兴趣的文档排在前面...

  • 开发笔记目录查看

    笔记一: 笔记二: 笔记三: 笔记四: 笔记五: 笔记六:

  • 目录

    羊皮笔记01 羊皮笔记02 羊皮笔记03 羊皮笔记04 羊皮笔记05 羊皮笔记06 羊皮笔记07

  • 《大江大河》笔记若干(一)

    后续笔记若干…… 后续笔记若干…… 后续笔记若干…… 后续笔记若干…… 后续笔记若干……

  • 记笔记分为闪念笔记、文献笔记和永久笔记

    记笔记分为闪念笔记、文献笔记和永久笔记 7/10 1,记闪念笔记 2,记文献笔记 3,记永久笔记 ——申克•阿伦斯...

  • 卡片笔记上记录什么?

    卡片可以用来记录四种笔记,分别是:闪念笔记、文献笔记、永久笔记、项目笔记。 1、闪念笔记(Fleeting Not...

网友评论

  • wfafa:目标概率搞反了。
  • 小虎牙牙:公式都错了。。。。
  • 27a9a1e82ab0:你好 加速学习算法中的第四个公式的等号右边 lambda的索引ij 是不是应该是ji? 感觉推公式的时候有点不顺。。
    9e207c977b0d:在ranklib的源代码中看,用的好像的确是ji,跟论文中不一致,感觉是不是论文中写错了
    9e207c977b0d:@天哪噜 我也感觉应该是 ji,不过论文里的确写的是 ij,可以描述下推导过程么?
    58d47f3a2ad2:@金橘子 没反,就是从上式推过来的。

本文标题:LambdaMART笔记

本文链接:https://www.haomeiwen.com/subject/ezeqhttx.html