Learning to rank 基本算法小结

 

“ 本文主要介绍了 Learning To Rank(LTR) 中的一些基本方法，评价指标和相关算法模型 (LambdaMART,RankNet,LambdaRank&FTRL)！”

作者：felix
来源：知乎专栏 有意思的数据挖掘。

最近工作中需要调研一下搜索排序相关的方法，这里写一篇总结，总结记录一下几天的调研成果。包括

1. Learning to rank 基本方法

2. Learning to rank 指标介绍

3. LambdaMART 模型原理

4. FTRL 模型原理

Learning to rank

排序学习是推荐、搜索、广告的核心方法。排序结果的好坏很大程度影响用户体验、广告收入等。
排序学习可以理解为机器学习中用户排序的方法，这里首先推荐一本微软亚洲研究院刘铁岩老师关于 LTR 的著作，Learning to Rank for Information Retrieval，书中对排序学习的各种方法做了很好的阐述和总结。我这里是一个超级精简版。

排序学习是一个有监督的机器学习过程，对每一个给定的查询－文档对，抽取特征，通过日志挖掘或者人工标注的方法获得真实数据标注。然后通过排序模型，使得输入能够和实际的数据相似。
常用的排序学习分为三种类型：PointWise，PairWise 和 ListWise。

PointWise

单文档方法的处理对象是单独的一篇文档，将文档转换为特征向量后，机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分，打分结果即是搜索结果

PointWise 方法很好理解，即使用传统的机器学习方法对给定查询下的文档的相关度进行学习，比如 CTR 就可以采用 PointWise 的方法学习，但是有时候排序的先后顺序是很重要的，而 PointWise 方法学习到全局的相关性，并不对先后顺序的优劣做惩罚。

PairWise

对于搜索系统来说，系统接收到用户査询后，返回相关文档列表，所以问题的关键是确定文档之间的先后顺序关系。单文档方法完全从单个文档的分类得分角度计算，没有考虑文档之间的顺序关系。文档对方法将排序问题转化为多个 pair 的排序问题，比较不同文章的先后顺序。

但是文档对方法也存在如下问题：
1. 文档对方法考虑了两个文档对的相对先后顺序，却没有考虑文档出现在搜索列表中的位置，排在搜索结果前面的文档更为重要，如果靠前的文档出现判断错误，代价明显高于排在后面的文档。
2. 同时不同的査询，其相关文档数量差异很大，所以转换为文档对之后， 有的查询对能有几百个对应的文档对，而有的查询只有十几个对应的文档对，这对机器学习系统的效果评价造成困难

常用 PairWise 实现：

1. SVM Rank

2. RankNet(2007)

3. RankBoost(2003)

ListWise:

单文档方法将训练集里每一个文档当做一个训练实例，文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例，文档列表方法与上述两种方法都不同，ListWise 方法直接考虑整体序列，针对 Ranking 评价指标进行优化。比如常用的 MAP, NDCG。常用的 ListWise 方法有：

1. LambdaRank

2. AdaRank

3. SoftRank

4. LambdaMART

Learning to rank 指标介绍

MAP(Mean Average Precision):

假设有两个主题，主题 1 有 4 个相关网页，主题 2 有 5 个相关网页。某系统对于主题 1 检索出 4 个相关网页，其 rank 分别为 1, 2, 4, 7；对于主题 2 检索出 3 个相关网页，其 rank 分别为 1,3,5。对于主题 1，平均准确率为 (1/1+2/2+3/4+4/7)/4=0.83。对于主题 2，平均准确率为 (1/1+2/3+3/5+0+0)/5=0.45。则 MAP= (0.83+0.45)/2=0.64。

** NDCG(Normalized Discounted Cumulative Gain):**

NDCG 把相关度分为 r 个等级，如果 r＝5，等级设定分别文 2^5-1，24-1 等等

• 本文地址：http://www.6aiq.com/article/1576078092816
• 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出
• 知乎专栏 点击关注

那么加入现在有一个 query 为 abc， 返回如下图所示的列表，假设用户选择和排序结果无关，则累积增益值如右列所示：

考虑到靠前的位置点击概率越大，那么靠下的位置需要加上衰减因子

log2/log(1+j)，求和就可以得到 DCG 的值，最后为了使得不同不搜索结果可以比较，用 DCG/MaxDCG 就可以得到 NDCG 的值了。
MaxDCG 就是当前情况下最佳排序的 DCG 值。如图所示 MaxDCG 就是 1、3、4、5、2 的排序情况下的 DCG 的值 (rank 2 的 gain 较低，应该排到后面）

NDCG 值

• MRR(Mean Reciprocal Rank)
  给定查询 q，q 在相关文档的位置是 r，那么 MRR(q) 就是 1/R

LambdaMART 算法：

LambdaMART 是 Learning to rank 其中的一个算法，在 Yahoo! Learning to Rank Challenge 比赛中夺冠队伍用的就是这个模型。

LambdaMART 模型从名字上可以拆分成 Lambda 和 MART 两部分，训练模型采用的是 MART 也就是 GBDT，lambda 是 MART 求解使用的梯度，其物理含义是一个待排序文档下一次迭代应该排序的方向。

但 Lambda 最初并不是诞生于 LambdaMART，而是在 LambdaRank 模型中被提出，而 LambdaRank 模型又是在 RankNet 模型的基础上改进而来。所以了解 LambdaRank 需要从 RankNet 开始说起。

论文：
From RankNet to LambdaRank to LambdaMART: AnOverview(https://www.researchgate.net/publication/228936665_From_ranknet_to_lambdarank_to_lambdamart_An_overview)

RankNet

RankNet 是一个 pairwise 模型，上文介绍在 pairwise 模型中，将排序问题转化为多个 pair 的排序问题，比较文档 di 排在文档 dj 之前的概率。如下图所示

最终的输出的 sigmoid 函数，RankNet 采用神经网络模型优化损失函数，故称为 RankNet。

可是这样有什么问题呢？排序指标如 NDCG、MAP 和 MRR 都不是平滑的函数，RankNet 的方法采用优化损失函数来间接优化排序指标。

LambdaRank

如图所示，蓝色表示相关的文档，灰色表示不相关的文档。RankNet 以 pairwise 计算 cost 左边为 13，右图将第一个文档下调 3 个位置，将第二个文档下调 5 个位置，cost 就降为 11。如此以来，虽然 RankNet 的损失函数得到优化，但是 NDCG 和 ERR 等指标却下降了。
RankNet 优化的方向是黑色箭头，而我们想要的其实是红色的箭头。LambdaRank 就是基于这个，其中 lambda 表示红色箭头。

LambdaRank 不是通过显示定义损失函数再求梯度的方式对排序问题进行求解，而是分析排序问题需要的梯度的物理意义，直接定义梯度，Lambda 梯度由两部分相乘得到：(1)RankNet 中交叉熵概率损失函数的梯度；(2) 交换 Ui，Uj 位置后 IR 评价指标 Z 的差值。具体如下：

lambdaMART

我们知道 GBDT 算法每一次迭代中， 需要学习上一次结果和真实结果的残差。在 lambdaMART 中，每次迭代用的并不是残差，lambda 在这里充当替代残差的计算方法。

• LambdaMART 算法流程

• GBDT 算法流程

对比 lambdaMART 和 GBDT 算法流程，主要框架是相同的，只不过 LambdaMART 模型用 lambda 梯度代替了 GBDT 的残差。

FTRL 算法（Follow the regularized Leader Proximal）

论文：Ad click prediction: a view from the trenches(https://www.researchgate.net/publication/262412214_Ad_click_prediction_a_view_from_the_trenches)

点击率预估问题（CTR）是搜索、广告和推荐中一个非常重要的模块。在 CTR 计算的过程中，常常采用 LR 模型。

FTRL 属于在线算法，和 SGD 等常用的在线优化方法对比，可以产生较好的稀疏性，非常适合 ID 特征较多，维度较高的特征。

google 的论文中已经给出了很详细的工程化实现的说明，该方法也已经广泛的应用。

• 参数优化

第一项：保证参数不偏移历史参数
第二项：保证 w 不会变化太大
第三项：代表 L1 正则，获得稀疏解

• 算法流程：

 

时间:2019-12-14 23:34  来源:    转发量:次