欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

LambdaRank和LambdaMART原理

这部分知识已经有很多地方讲的比较清楚,我这里纯粹是记录一些方便我回忆的要点。

pair-wise error 定义

pair-wise error 表示一个排列中,抽查任意两个item,一共有 \(C_n^2\) 种可能的组合,如果这两个item的之间的相对排序错误,error值加1.

例如,对某个Query,和它相关的文章有两个,记为 \((Q,[D_1,D_2])\)

  1. 如果模型 \(f(\cdot)\) 对此Query返回的n条结果中, \(D_1,D_2\) 分别位于前两位,那么pair-wise error就为0;
  2. 如果模型 \(f(\cdot)\) 对此Query返回的n条结果中, \(D_1,D_2\) 分别位于第1位和第n位,那么pair-wise error为n-2;
  3. 如果模型 \(f(\cdot)\) 对此Query返回的n条结果中, \(D_1,D_2\) 分别位于第2和第3位,那么pair-wise error为2;

通过上面几个例子可以发现,pair-wise error并没有考虑位置的权重,RankNet交叉熵优化的目标和这个类似。所以就可能两轮迭代中出现下图的情况:

QQ20160816-1

第一轮的时候pair-wise error为13,第二轮为 3 + 8 = 11,损失是减少了,但是很多时候我们并不想要这种结果。这种情况就是我们的优化的损失函数和「评价指标」之间不一致导致。

但是评价指标,例如NDCG是一个不连续的函数,没有办法使用,所以LambdaRank就是解决这个不一致的问题。

LambdaRank

LambdaRank的想法是,既然评价指标不连续、不可导,那就直接在梯度上面下功夫,如果梯度的表现和评价指标「接近」即可。具体怎么构造合适的自定义 \(\lambda-function\) 论文也没有说,只是给出了一些指导原则,对这个指导原则的推倒论文有证明。 对于评价指标是NDCG的情况,论文最后通过实验找到了一种比较好的Lambda函数,具体为:

QQ20160816-2

LambdaMART

首先你需要了解MART也就是GBDT,LambdaMART只是在GBDT的过程中做了一个很小的修改。原始GBDT两棵树之间样本的lable是通过「残差」确定,这里相当于不只是用残差,还用到了评价指标的信息:

\(\lambda_{ij}=S_{ij} \begin{vmatrix} \bigtriangleup NDCG \frac{\partial C}{\partial o_{ij}} \end{vmatrix}\)

具体到一个样本上:

\(\lambda_i=\sum_{j \in P}\lambda_{ij}\)

整个流程被修改为(注意第6行):

QQ20160816-3

类似做rank的方法还有GBRank,和传统GBDT的区别也是在「残差」的地方动脑子,有兴趣可以关注。并且xgboost也实现了Rank部分,基于LambdaRank,配合上GBDT也,应该也就变成LambdaMART了,有空可以尝试一下。

 

参考资料

《Learning to Rank with Nonsmooth Cost Functions》

《Adapting Boosting for Information Retrieval Measures》

未经允许不得转载:大数据算法 » LambdaRank和LambdaMART原理

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站