Learning to Rank （LTR）是指一系列基于机器学习的排序算法，最初主要应用于信息检索领域，最典型的是解决搜索引擎对搜索结果的排序问题。除了信息检索以外，Learning to Rank 也被应用到许多其他排序问题上，如商品推荐、计算广告、生物信息学等。目前主流的 Learning to Rank 在排序的过程中通过文档与文档之间的比较，在很多问题上比只基于文档自身特征的分类和回归策略更加有效。当然，Learning to Rank 因此也需要更大的计算量。

Learning to Rank 典型场景

Learning to Rank 典型应用在信息检索问题上，对于一个“给定查询”和“一系列文档”，Learning to Rank 需要构建一个排序策略，给出每个文档的打分，这个打分代表该文档与“给定查询”的相关性，基于打分对文档进行排序，打分越高（或越低）的文档排序越靠前，表示其与“给定查询”的相关性越高（需要说明的是，这里的打分只表示这些文档在“给定查询”下的排序关系，如果查询不同，同一文档的得分很可能不同）。

  • 输入特征
    • 文档自身特征
    • 其他排序模型对该文档的打分
  • 输出
    • 表示每个文档排序关系的打分

Learning to Rank 算法分类及核心思想

按照排序策略的构建方式，Learning to Rank 通常可以分为三类，分别是：Pointwise、Pairwise 和 Listwise。

Pointwise

Pointwise 方法只考虑”给定查询“下，单个文档的绝对相关度，而不考虑其他文档与”给定查询“的相关度。即对于一个给定查询$q$和一系列文档($d_1, d_2, …, d_n$)，每次选择一个文档$d_i$，基于该文档的特征给出打分，表示该文档的与”给定查询$q$“的相关程度。对于损失函数的构建，可以采用多分类、回归、有序回归等，因此，Pointwise可以直接基于排序和回归算法实现。

  • 输入：文档的特征向量
  • 输出：每个文档的相关性分数
  • 损失函数: 回归loss、分类loss、有序回归loss（Ordinal Regression）

Pointwise 方法的相关算法：Pranking (NIPS 2002), OAP-BPM (EMCL 2003), Ranking with Large Margin Principles (NIPS 2002), Constraint Ordinal Regression (ICML 2005)。

Pointwise 方法存在的问题
  • Pointwise 方法仅考虑了单个文档的绝对相关度，没有考虑文档之间的排序影响。
  • 排在最前的几个文档对排序效果的影响更加重要，而 Pointwise 没有考虑这方面的影响。

Pairwise

与 Pointwise 不同，Pairwise 方法考虑”给定查询“下，两个文档的相对相关度。 即对于一个给定查询 $q$ 和一系列文档($d_1, d_2, …, d_n$)，每次选择2个文档$d_i \& d_j$，考虑这两个文档的相对相关度: $d_i>d_j$，或者$d_i<d_j$。每次将2个文档的特征组合成一个特征向量，基于相对相关度给出打分，从而将排序问题转化成了对于文档对的分类或者回归问题，从而可以采用各种分类或者回归算法进行求解，比如SVM、Neural networks、Gradient Boosting Tree 等等。

以基于SVM的 Learning to Rank 方法为例（SVMRank），我们用特征向量$Φ(q,d)$表示文档$d$与给定查询$q$相关程度，由此可以得到一个排序函数列表：

其中$f$是排序函数，$d_i$和$d_j$表示不同的文档，$ω$是在学习期间优化的权重向量。

然后，参考支持向量机分类问题引入松弛变量，可以得到如下优化问题：

最小化：

约束为：

其中$V$是目标函数，$C$是对训练误差的惩罚因子，$\xi$是松弛变量，$k$是约束的下标，$r$是所有可能的文档对集合。

通过调整约束可以得到一个新的优化问题，而这个问题和支持向量机分类问题是等价的：

可以使用解决支持向量机分类的分解算法来求解这个问题。

Pairwise 相关算法有：SVMRank（T. Joachims, KDD 2006）、RankNet(C. Burges, et al. ICML 2005)， FRank(M.Tsai, T.Liu, et al. SIGIR 2007)、RankBoost(Y. Freund, et al. JMLR 2003)、GBRank (Zheng Z, Chen K, Sun G, et al., SIGIR 2007)。

Pairwise 方法存在的问题
  • Pairwise 方法只考虑了两个文档对的相对先后顺序，却没有考虑文档出现在整个搜索列表中的位置，而通常排在前边的文档更为重要。针对这个问题的改进思路是引入代价敏感因素，即每个文档对根据其在列表中的顺序具有不同的权重，越是排在前列的权重越大。
  • 另外一个可能的问题：不同査询，其相关文档数量差异很大，有的查询对能有几百个文档对，而有的查询只有十几个对应的文档对，这会对机器学习系统的效果评价造成困难。例如两个查询，査询$Q_1$对应500个文档对，查询$Q_2$对应10个文档对，假设排序模型对于査询$Q_1$的文档对能够判断正确480个，对于査询 $Q_2$能够判新正确2个文档对，从总的文档对数量来看，这个排序模型的准确率是 $(480+2)/500+10）=0.95$，即 95% 的准确率。但是从査询的角度，两个査询对应的准确率分别为：96% 和 20%，两者平均为58%，与纯粹从文档对判断的准确率相差甚远，这对如何继续调优排序模型会带来困扰。（个人认为这个不是问题，不同查询之间没有直接的可比性，合理的做法就是基于单个查询优化排序模型，而不是整体。）

Listwise

Pointwise 将一个文档当做一个实例，缺少对其他文档的考虑， Pairwise 将两个文档作为一个实例，在一定程度上考虑了其他文档，但是缺少对整体排序的考虑，而 Listwise 则做了进一步改进，对于一个给定查询 $q$ 和一系列文档($d_1, d_2, …, d_n$)，将所有文档的排序结果整体作为一个实例，从而学习整体排序结果上的最优策略。

如前文所述，Pointwise 和 Pairwise 最终的目标函数都和传统的分类和回归方法类似，而 Listwise 方法面临的主要问题是如何定义目标函数，进而获得训练阶段的梯度。 对于排序问题的评价指标一般有 NDCG、ERR、MAP、MRR等，这些指标的特点是不平滑、不连续，无法直接求梯度，因此无法直接用梯度下降法求解。针对整个排序列表定义一个可导的损失函数，从而求得优化模型需要的梯度，或者直接根据排序结果得出梯度，是 Listwise 方法需要解决的问题。

其中一个方案是基于不同排序结果的概率分布定义目标函数，如对于文档A、B、C，其可能出现的排序结果有6种：ABC、ACB、BAC、BCA、CAB和CBA，在文档A、B、C真实得分已知的情况下，可以计算6种排序结果的概率分布，这个概率分布对应的是真实打分下的概率分布$P$，在训练阶段，基于训练得到的模型对文档A、B、C进行打分，可以获得6种排序结果新的概率分布$Q$，计算$Q$与真实打分的概率分布$P$的 KL距离（Kullback-Leibler Divergence），从而获得当前排序结果的误差，进而获得优化模型所需要的梯度。

Listwise 相关算法有：LambdaRank (NIPS 2006)、 AdaRank (SIGIR 2007)、 SVM-MAP (SIGIR 2007)、 SoftRank (LR4IR 2007)、 GPRank (LR4IR 2007)、 CCA (SIGIR 2007), RankCosine (IP&M 2007)、 ListNet (ICML 2007)、 ListMLE (ICML 2008)、LambdaMART [1]。

LambdaMART 算法

LambdaMART [2] 是目前最热门的 Listwise 算法，模型采用的是MART（Multiple Additive Regression Tree），梯度是 Lambda，其物理含义是一个待排序的文档下一次迭代应该排序的方向（向上或者向下）和强度。LambdaMART即Lambda和MART的组合。

LambdaMART 是 LambdaRank 的提升树版本，而 LambdaRank 是基于 RankNet 改进而来的 [1]，因此按照顺序依次介绍 RankNet 、 LambdaRank 、 LambdaMART。

RankNet

RankNet [3] 是一个典型的 Pairwise 方法，对于一个给定查询$q$和一系列文档($d_1, d_2, …, d_n$)，RankNet 把排序问题转换成比较所有两个文档排序概率问题，即比较排在$d_i$ 排在$d_j$前的概率。首先计算每个文档的得分，然后根据得分计算文档对的排序概率。

RankNet 证明了如果知道一个待排序文档的排列中相邻两个文档之间的排序概率，则通过推导可以算出每两个文档之间的排序概率。并且对于一个待排序文档序列，只需计算相邻文档之间的排序概率，不需要计算所有文档对，可以减少计算量。RankNet 采用神经网络模型优化损失函数， 采用梯度下降法求解，而前文所述的 SVMRank 则基于SVM进行求解。

LambdaRank

由于 RankNet 是一个 Pairwise 方法，在训练过程中以 pairwise error 的方式计算损失，缺少对整体排序结果的考虑，而通常我们更关注靠前位置的相关文档的排序位置的提升。 LambdaRank [4] 对此进行了改进，是一个 Listwise 方法。

LambdaRank 的主要贡献在于对梯度（即 Lambda）的提出。如前文所述，在模型训练的阶段，我们最终需要的是优化模型所需要的梯度，甚至可以没有损失函数，因此 LambdaRank 提出了基于整个排序结果的梯度计算方法，具体公式推导可以参考文献[1]，其主要思想是每一个文档下一次调序的方向和强度取决于所有同一查询下其他的文档，同时 LambdaRank 还在 Lambda 中引入评价指标Z（如NDCG、ERR等），把交换两个文档的位置引起的评价指标的变化 作为其中一个因子。 LambdaRank 相比 RankNet 考虑了排序评价指标，直接对排序问题求解，效果更明显。

LambdaMART

LambdaRank 重新定义了梯度，赋予了梯度新的物理意义，因此，所有可以使用梯度下降法求解的模型都可以基于这个梯度学习排序模型，MART（Multiple Additive Regression Tree）就是其中一种模型，将梯度 Lambda 和 MART 结合就是 LambdaMART 。关于 MART 的具体实现可以参考 LambdaMART 不太简短之介绍，这里对其核心思想进行介绍。

MART 是基于 Boosting 思想的多重增量回归树（Multiple Additive Regression Tree），其主要特点是：

  1. 使用多个决策树做迭代预测
  2. 通过加法模型，将每次迭代得到的子模型叠加起来
  3. 每个决策树都比之前的决策树改进一点点，最终拟合到真实结果。

LambdaMART 基于 LambdaRank 所定义的梯度对 MART 模型进行训练，获得最终的排序模型。

XGBoost 中有对 LambdaMART 的实现，可以用于处理各种排序任务。

参考资料

链接

文献

[1]: Burges C J C. From ranknet to lambdarank to lambdamart: An overview[J]. Learning, 2010, 11(23-581): 81.

[2]: Wu Q, Burges C J C, Svore K M, et al. Adapting boosting for information retrieval measures[J]. Information Retrieval, 2010, 13(3): 254-270.

[3]: Burges C, Shaked T, Renshaw E, et al. Learning to rank using gradient descent[C]//Proceedings of the 22nd International Conference on Machine learning (ICML-05). 2005: 89-96.

[4]: Burges C J, Ragno R, Le Q V. Learning to rank with nonsmooth cost functions[C]//Advances in neural information processing systems. 2007: 193-200.

最后更新： 2019年04月21日 22:08

原始链接： http://andersjing.com/2019/04/20/2019-04-20-LearningToRank/

赏
× 请打赏~
打赏二维码