L2R(learning to rank)是指利用机器学习的技术，去完成排序的任务。在模型训练阶段，该算法最终优化的目标是一个更加合理的排序指标。L2R技术已经成功应用在信息检索(IR)、NLP、和数据挖掘(DM)等领域【1】。根据具体优化的目标不同，L2R算法主要分为Pointwise，Pairwise，Listwise三类。本文首先介绍L2R建模的整体框架，然后针对三类方法分别进行介绍。

L2R建模

L2R建模的基本框架如下所示：

图1：L2R基本框架

如图1所示，模型具体分为训练和预测两个解读。

训练阶段： 训练数据包括多个group, 其中每个group由1个query和1组document共同构成。该group中，qi表示第i个query，di,j表示对应第i个query的第j个document, 不仅包含了document的各种属性，也包括了对应document和query之间的相关性标签yi。具体如下所示：

S=[((q1,D1),y1),((q2,D2),y2),…,((qm,Dm),ym)]

Di=[di,1,di,2,…,di,n]

yi=[yi,1,yi,2,…,yi,n]

其中m表示query个数，n表示每个group的document个数（此处假设每个group的document个数相同为n）

在训练阶段，每个pair(qi, di,j) 都提取相关的特征，作为特征向量xi,j。 模型学习的目标是，对每个pair(qi, di,j)，预测其对应的分数f(xi,j), 使得根据这些分数得到的每个qi对应的所有di,j排序尽量接近真实排序。

预测阶段： 输入query qm+1和document集合D=[d1,d2,…,dN], 利用训练得到的model，预测query qm+1和每个document di的相关性分数，并根据预测的分数对document进行排序，输出排序列表。

和分类回归的关系： 传统的分类和回归方法，通过学习相关模型，预测样本的类别或者分数值；而排序模型，则是通过模型，预测样本相关性(或者其它分数)的相对顺序。在分类问题中，有一种问题是序数分类(Ordinal Classification)，序数分类问题和排序问题有点类似，不同之处在于序数分类的目标是预测顺序的类别(ordered-categorization of objects)，而排序问题的目标是预测相对顺序(ordering)。

L2R评估

L2R的评估基于预测的rank list和真实的rank list比较，主要有DCG(Discounted Cumulative Gain)，NDCG(Normalized Discounted Cumulative Gain)，MAP(Mean Average Precision)等评估指标。

对于给定的query, TOP T的返回结果对应的DCG值如下所示：

DCG@T=∑Ti=12li−1log(1+i)

其中i表示预测结果列表中第i个位置，li表示预测结果中第i个位置的document的真实相关性值。分子部分描述了饭回结果的相关性，分母部分针对位置进行加权，排序越靠前，其对应的相关性值权重系数越大。

所有query的平均DCG值作为最终排序系统DCG评估值。

NDCG在DCG指标基础上进行了扩展，通过将DCG值除于DCG最佳排序对应的DCG值，将其归一化到0-1的范围，其定义如下所示：

NDCG@T=DCG@TmaxDCG@T

所有query的平均NDCG值作为最终排序系统DCG评估值。

map是L2R中另一种评估指标，其对应的相关性标签只有0和1。对于给定的query，AP的定义如下所示：
AP=∑ni=1P(i)∗li∑ni=1li

其中i表示预测结果列表中第i个位置，li表示预测结果中第i个位置的document的真实相关性值（在MAP中，相关性值取0或1）。n表示排序列表的长度，P(i)表示从列表第一个位置到第i个位置预测结果的平均准确率，其定义如下：
P(i)=∑ik=1lki

所有query的平均AP值作为最终排序系统MAP评估值。

Pointwise

在Pointwise方法中，排序问题可以转化成分类或回归问题，分类(包括序数分类)或回归的方法都可以使用。由于建模没有使用样本的相对顺序，group也不需要构建。

此处以OC SVM(SVM for Ordinal Classification)【2】为例，说明如何利用分类方法解决排序问题。该方法优化的目标是，对于任何相邻的2个类别，最大化其对应的分类间隔。实现层面，如图2所示，对于类别为l的序数分类问题，引用l−1个分类器 ⟨w,x⟩−br(r=1,···,l−1), 其中b1≤···≤bl−1≤bl=inf。⟨w,x⟩−br=0用于划分第r和r−1个类别，如果⟨w,x⟩+br−1>=0并且⟨w,x⟩+br<0, 则样本标签属于y=r。建模的目标函数如下所示：

minw,b,ξ=12||w||2+C∑l−1r=1∑mri=1(ξr,i+ξ∗r+1,i)

约束如下：

⟨w,xr,i⟩+br<−(1−ξr,i)

⟨w,xr+1,i⟩+br>=1−ξ∗r,i

ξr,i>=0

ξ∗r+1,i>=0

i=1,2,…,mr

r=1,2,…,l−1

m=m1+m2+…+ml

其中 xr,i表示第r个类别的第i个样本，ξr,i和ξ∗r+1,i表示对应的松弛变量，m是样本的个数, mi表示第i类样本的个数。

图2：SVM for Ordinal Classification【2】

Pairwise

基于pairwise的rank方法中，将排序问题转化为pairwise的分类或回归问题进行求解。通常情况下，针对一个query对应的document pair, 利用分类器对pair的order进行判断。常见的pairwise rank方法有RankNet、RankSvm等，此处以RankNet为例进行说明。

RankNet原理及求解

RankNet建模

RankNet使用的打分模型要求对参数可导，训练数据根据query分为多个组，对于1个给定的query，选择2个不同相关性label的document pair，计算相关性分数si=f(xi)和sj=f(xj)，RankNet对其对应的特征向量进行打分。di>dj表示document di的相关性大于dj。

document di的相关性大于document dj的概率如下:

Pij=P(di>dj)=11+e−σ(si−sj)(1)

其中σ是常数，决定sigmoid函数的形状。RankNet采用交叉熵函数训练模型，如下所示。其中P′ij表示真实的di相关性大于dj的概率。

C=−P′ijlogPij−(1−P′ij)log(1−Pij)(2)

RankNet求解

为方便后续描述，针对1个给定的query，我们定义变量Sij：

Sij={1,di比dj更相关−1,dj比di更相关0di和dj相关性相同(3)

在本文中，假定对于每个query，其对应所有document的相关性顺序都是完全确定的。

P′ij=12(1+Sij).(4)

由上述式2和式4可以得出：

C=−P′ijlogPij−(1−P′ij)log(1−Pij)=−12(1+Sij)logPij−(1−12(1+Sij))log(1−Pij)=−12(logPij+log(1−Pij))−12Sij(logPij−log(1−Pij)=−12log(Pij∗(1−Pij))−12SijlogPij1−Pij=−12loge−σ(si−sj)(1+e−σ(si−sj))2−12Sijlogeσ(si−sj)=−12(−σ(si−sj)−2log(1+e−σ(si−sj)))−12Sijσ(si−sj)=12(1−Sij)σ(si−sj)+log(1+e−σ(si−sj)(5)

C={log(1+e−σ(si−sj)),当Sij=1log(1+e−σ(sj−si)),当Sij=−1(6)

C对s求导，结果如下：
φCφsi=σ(12(1−Sij)−11+e−σ(si−sj))=−φCφsj(7)

通过SGD的方式进行求解

wk=wk−η(φCφsiφsiφwk+φCφsjφsjφwk)(8)

其中η>0为学习率。

RankNet求解加速

对于给定的文档对di和dj，

φCφwk=φCφsiφsiwk+φCφsjφsjφwk=σ(12(1−Sij)−11+e−σ(si−sj))(φsiφwk−φsjφwk)=λij(φsiφwk−φsjφwk)(9)

其中λij=φCφsi=σ(12(1−Sij)−11+e−σ(si−sj))（10）

我们定义I为索引对(i,j)的集合(其中doci的相关性大于docj)，汇总来自所有文档对的贡献，

δwk=−η∑(i,j)∈Iλij(φsiφwk−φsjφwk)=−η∑iλiφsiφwk(11)

其中λi=∑j:(i,j)∈Iλij−∑j:(j,i)∈Iλij，每个document对应一个λi，其含义为损失函数对文档di的模型打分si的梯度。方向表示梯度的方向，大小表示梯度的幅度。每个λi的计算都来自该document对应的所有pair。在实际计算时，可以对每个文档计算其对应的λi，然后用于更新模型参数。这种mini-batch的梯度更新方式和问题分解方法，显著提升了RankNet模型训练的效率。

Listwise

基于pairwise的方法(如RankNet)优化的是pairwise误差，而在很多rank相关领域如信息检索，更加关注的是topK的排序结果。

如下图所示，假定当前文档的相关性值只有0和1，灰色线表示和当前query不相关的文档，蓝色线表示和当前query相关文档，对于左图，pairwise误差为13，对于右图，将上面的相关文档下移3个位置，下面的相关文档上移5个位置，pairwise误差减少到11，而对于NDCG等更加关注top k结果的排序指标，误差可能是增加的。右图中的黑色箭头表示RankNet梯度方向，而我们更想要的是红色箭头对应的梯度方向。此时，就需要利用ListRank方法解决。

图3：pairwise和listwise误差比较[3]

我们以LambdaRank方法为例，对Listwise进行说明。

LambdaRank

LambdaRank的建模和求解与RankNet类似。通过直接写出Cost对模型打分的梯度，而不是直接通过计算得到，是LambdaRank的主要思路。采用这样的思路，能绕过NDCG等排序指标对模型打分求导的困难。而lambad值正是代表对模型打分的梯度信息，每篇文档的lambad都从其它所有不同label的文档处获得其对应的更新方向和更新值。

对式10进行更新，乘于交换文档对di和dj在rank列表中的位置后NDCG的变化幅度，能得到不错的结果[3]。

λij=φCφsi=σ(12(1−Sij)−11+e−σ(si−sj))|△NDCG|

由于每个query对应的文档对集合I中，前一个文档的相关性大于后一个，Sij=1，因此，式12可以直接写成：
λij=φCφsi=−σ|△NDCG|1+e−σ(si−sj))(12)

经验表明，式12能直接优化NDCG指标。实际上，如果我们要优化其它指标，如MAP、MRR等，只需要更新NDCG的变化幅度为其它指标的变化幅度[3]。

LambdaMART

LambdaMART算法是LambdaRank和MART算法的组合。MART算法提供了算法的框架，需要用到的梯度相关信息则来自LambdaRank方法的梯度y′i=λi=∑j:(i,j)∈Iλij−∑j:(j,i)∈Iλij

为方便描述，我们引入
∑(i,j)≐Iλij=∑j:(i,j)∈Iλij−∑j:(j,i)∈Iλij

λi相当于如下函数的导数：
C=∑(i,j)≐I|△NDCGij|log(1+e−σ(si−sj))

φCφsi=∑(i,j)≐I−σ|△NDCGij|1+e−σ(si−sj))=∑(i,j)≐I−σ|△NDCGij|ρij(13)
其中ρij=11+e−σ(si−sj)

φ2Cφs2i=∑(i,j)≐Iσ2|△NDCGij|ρij(1−ρij)(14)

对于第m棵树的第k个叶子结点，其对应的值如下：
γkm=∑xi∈RkmφCφsi∑xi∈Rkmφ2Cφs2i=−∑xi∈Rkm∑(i,j)≐I|△NDCGij|ρij∑xi∈Rkm∑(i,j)≐I|△NDCGij|σρij(1−ρij)

LambdaMART算法的流程如下：

图4:lambadMART算法流程[3]

lambdaRank和lambadMART参数更新的不同：

前者对于每个query，计算梯度信息并更新一次参数，每次更新所有的模型参数；后者对每次分裂使用所有落在当前节点的样本及在同一group的样本，只更新当前节点的参数而非所有模型参数。

[1] LI, Hang. “A Short Introduction to Learning to Rank”[J]. IEICE Transactions on Information and Systems, 2011.
[2] A. Shashua and A. Levin, “Ranking with large margin principle: Two approaches” in Advances in Neural Information Processing Systems 15, ed. S.T. S. Becker and K. Ober- mayer, MIT Press.
[3] Christopher J.C. Burges, “From RankNet to LambdaRank to LambdaMART: An Overview”, Microsoft Research Technical Report, 2010