使用机器学习排序算法LambdaMART有一段时间了，但一直没有真正弄清楚算法中的所有细节。 学习过程中细读了两篇不错的博文，推荐给大家： 梯度提升树(GBDT)原理小结 徐博From RankNet to LambdaRank to LambdaMART: An Overview 但经过一番搜寻之后发现，目前网上并没有一篇透彻讲解该算法的文章，所以希望这篇文章能够达到此目的。 本文主要参考微软研究院2010年发表的文章From RankNet to LambdaRank to LambdaMART: An Overview1，并结合自己的理解，试图将RankNet、LambdaRank和LambdaMART这三种算法的所有算法细节讲解透彻。 1. 概述 RankNet、LambdaRank和LambdaMART是三个关系非常紧密的机器学习排序算法。简而言之，RankNet是最基础，基于神经网络的排序算法；而LambdaRank在RankNet的基础上修改了梯度的计算方式，也即加入了lambda梯度；LambdaMART结合了lambda梯度和MART（另称为GBDT，梯度提升树）。这三种算法在工业界中应用广泛，在BAT等国内大厂和微软谷歌等世界互联网巨头内部都有大量应用，还曾经赢得“Yahoo！Learning To Rank Challenge(Track 1)"的冠军。本人认为如果评选当今工业界中三种最重要的机器学习算法，以LambdaMART为首的集成学习算法肯定占有一席之地，另外两个分别是支持向量机和深度学习。 2. RankNet 2.1 算法基础定义 RankNet解决如下搜索排序问题：给定query集合，每个query都对应着一个文档集合，如何对每个query返回排序后的文档集合。可以想象这样的场景：某位高考生在得知自己的成绩后，准备报考志愿。听说最近西湖大学办得不错，所以就想到网上搜搜关于西湖大学的资料。他打开一个搜索引擎，输入“西湖大学”四个字，然后点击“搜索”，页面从上到下显示了10条搜索结果，他认为排在上面的肯定比下面的相关，所以就开始从上往下一个个地浏览。所以RankNet的目标就是对所有query，都能将其返回的文档按照相关性进行排序。 RankNet网络将输入query的特征向量x∈Rn映射为一个实数f(x)∈R。RankNet采用pairwise的方法进行模型训练。具体地，给定特定query下的两个文档Ui和Uj，其特征向量分别为xi和xj，经过RankNet进行前向计算得到对应的分数为si=f(xi)和sj=f(xj)。用Ui⊳Uj表示Ui比Uj排序更靠前（如对某个query来说，Ui被标记为“good”，Uj被标记为“bad”）。继而可以用下面的公式来表示Ui应该比Uj排序更靠前的概率： Pij≡P(Ui⊳Uj)≡ 1 1+e−σ(si−sj) 这个概率实际上就是深度学习中经常使用的sigmoid函数，参数σ决定sigmoid函数的形状。对于特定的query，定义Sij∈{0,±1}为文档i和文档j被标记的标签之间的关联，即 Sij={ 1 文档i比文档j更相关 0 文档i和文档j相关性一致 −1 文档j比文档i更相关 定义 ¯ P ij= 1 2 (1+Sij)表示Ui应该比Uj排序更靠前的已知概率，则可以用交叉熵定义优化目标的损失函数： C=− ¯ P ijlogPij−(1− ¯ P ij)log(1−Pij) 如果不太熟悉什么是交叉熵，可以参考宗成庆老师的《统计自然语言处理》2.2节“信息论基本概念”，里面将熵、联合熵、互信息、相对熵、交叉熵和困惑度等概念都讲得相当清楚。 结合以上多个公式，可以改写损失函数C为： C= 1 2 (1−Sij)σ(si−sj)+log(1+e−σ(si−sj)) 对于Sij=1， C=log(1+e−σ(si−sj)) 然而对于Sij=−1， C=log(1+e−σ(sj−si)) 可以看出损失函数C具有对称性，也即交换i和j的位置，损失函数的值不变。 分析损失函数C的趋势发现，如果对文档Ui和Uj的打分可以正确地拟合标记的标签，则C趋向于0，否则C趋向于线性函数。具体地，假如Sij=1，也即Ui应该比Uj排序高，如果si>sj，则拟合的分数可以正确排序文档i和文档j， limsi−sj→∞ C= limsi−sj→∞ log(1+e−σ(si−sj))=log1=0 如果si2）进行评分。NDCG和ERR的另一个优点是更关注排名靠前的文档，在计算分数时会给予排名靠前的文档更高的权重。但是这两种评分方式的缺点是函数不连续，不能进行求导，所以也就不能简单地将这两种评分方式加入到模型的损失函数中去。 3.1 MRR 对于一个查询i来说，ranki表示第一个相关结果的排序位置，所以： MRR(Q)= 1 |Q| |Q| ∑ i=1 1 ranki |Q|表示查询的数量，MRR表示搜索系统在查询集Q下的平均倒数排名值。MRR只能度量检索结果只有一个并且相关性等级只有相关和不相关两种的情况。 举个简单例子： 查询语句 查询结果 正确结果 排序位置 排序倒数 机器学习 快速排序，深度学习，并行计算 深度学习 2 1/2 苹果手机 小米手机，华为手机，iphone 7 iphone 7 3 1/3 小米移动电源 小米移动电源，华为充电器，苹果充电插头 小米移动电源 1 1/1 所以MRR(Q)= 1/2+1/3+1 3 = 11 18 3.2 MAP 假定信息需求qj∈Q对应的所有相关文档集合为d1,...,dmj，Rjk是返回结果中直到遇到dk后其所在位置前（含dk）的所有文档的集合，则定义MAP(Q)2如下： MAP(Q)= 1 |Q| |Q| ∑ j=1 1 mj mj ∑ k=1 Precision(Rjk) 实际上有两种计算MAP的方法或者说有两种MAP(Q)的定义方法。第一种方法是在每篇相关文档所在位置上求正确率然后平均（参考上面的公式）。另一种是在每个召回率水平上计算此时的插值正确率，然后求11点平均正确率，最后在不同查询之间计算平均。前者也称为非插值MAP(Q)。一般提MAP(Q)都指前者，所有这里也只讨论前者。 如果对定义的公式不太理解，可以结合下面的例子进行理解。 查询1：机器学习 查询2：苹果手机 排序位置 是否相关 排序位置 是否相关 1 是 1 否 2 是 2 是 3 否 3 是 4 否 4 否 5 是 5 否 6 否 6 是 7 否 7 是 针对上面检索的结果，可计算出 AP(1)=(1∗1+1∗1+2/3∗0+2/4∗0+3/5∗1+3/6∗0+3/7∗0)/3= 13 15 AP(2)=(0∗0+1/2∗1+2/3∗1+2/4∗0+2/5∗0+3/6∗1+4/7∗1)/4= 47 84 MAP(Q)= AP(1)+AP(2) 2 = 13/15+47/84 2 = 599 420 3.3 NDCG NDCG是基于前k个检索结果进行计算的。设R(j,m)是评价人员给出的文档d对查询j的相关性得分，那么有： NDCG(Q,k)= 1 |Q| |Q| ∑ j=1 Zj,k k ∑ m=1 2R(j,m)−1 log(1+m) 其中 DCGk= k ∑ m=1 2R(j,m)−1 log(1+m) Zj,k为第j个查询的DCG归一化因子，用于保证对于查询j最完美系统的DCGk得分是1。Zj,k也可以用 1 IDCGk 表示。m是返回文档的位置。如果某查询返回的文档数k′t的所有样本落入右子树R中，μL(μR)表示左子树（右子树）所有样例标签值的均值。如果这就是一棵最简单的拥有一个根节点、两个叶子节点的二叉回归树，那么只需要根据最优阈值切分为左右子树，并且分别计算左右子树的值γl,l=1,2即可。如果将划分子树的过程继续进行L−1次即可得到一棵包含L个叶子节点的回归树。 上面公式使用最小二乘法计算拟合误差，所以通过上面方法得到的模型又称为最小二乘回归树。其实不管误差的计算方式如何，我们都可以拟合出相应的回归树，唯一的区别是梯度的计算不同而已。 MART使用线性组合的方式将拟合的树结合起来，作为最后的输出： Fn(x)= N ∑ i=1 αifi(x) fi(x)是单棵回归树函数，αi是第i棵回归树的权重。 在这里我们需要弄清楚为什么拟合残差就能不断减少拟合误差。假设拟合误差C是拟合函数Fn的函数C(Fn)。那么： δC≈ ∂C(Fn) ∂Fn δFn 如果取δFn=−η ∂C ∂Fn ，就可以得到δC<0。其中η是学习率，为正实数。所以只要函数Fn拟合误差函数的负梯度就可以不断降低拟合误差的值。 设标签向量y=[y1,y2,...,ym]T，如果用最小二乘的方式表示拟合误差，则： C= 1 2 (Fn−y)2 那么δFn=−η ∂C ∂Fn =−η(Fn−y)。这其实就是上面提到的残差，所以拟合残差可以不断减少拟合误差。 5.2 逻辑回归+MART进行二分类 了解了MART之后，下面举一个MART实际应用的例子：使用MART和逻辑回归进行二分类。用于分类的样本xi∈Rn，标签yi∈{±1}，拟合函数F(x)。为了简化表示，我们表示条件概率如下： P+≡P(y=1|x) P−≡P(y=−1|x) 用交叉熵表示损失函数： L(y,F)=−ylog(P+)−(1−y)log(P−) 逻辑回归使用对数机率（属于正例概率/属于负例概率）进行建模， Fn(x)= 1 2 log( P+ P− ) P+= 1 1+e−2σFn(x) P−=1−P+= 1 1+e2σFn(x) 将P+和P−带入L(y,F)中，得到： L(y,Fn)=log(1+e−2yσFn) Rjm表示落入第m棵树的第j个叶子节点中的样例集合，可以通过下式对该叶子节点的值进行优化： γjm=arg minγ ∑xi∈Rjm log(1+e−2σyi(Fm−1(xi)+γ)) 上式可以使用Newton-Raphson方法按照下面的公式进行迭代求解： γn+1=γn− g′(γn) g″(γn) 5.3 LambdaMART基本定义 LambdaMART基于MART，优化λ梯度。根据上面的定义，对于任意Ui和Uj，有： λij= ∂C(si−sj) ∂si = −σ|ΔZij| 1+eσ(si−sj) |ΔZij|表示交换Ui和Uj的位置产生的评价指标差值，Z可以是NDCG或者ERR等。对于特定Ui，累加其他所有排序项的影响，得到： λi= ∑j:{i,j}∈I λij− ∑j:{j,i}∈I λij 为了简化表示： ∑{i,j}⇌I = ∑j:{i,j}∈I λij− ∑j:{j,i}∈I λij 于是我们可以更新损失函数： ∂C ∂si = ∑j:{i,j}∈I −σ|ΔZij| 1+eσ(si−sj) = ∑j:{i,j}∈I −σ|ΔZij|ρij 其中，我们定义： ρij= 1 1+eσ(si−sj) = −λij σ|ΔZij| 然后可以得到： ∂2C ∂s 2 i = ∑{i,j}⇌I σ2|ΔZij|ρij(1−ρij) 所以我们可以用下面的公式计算第k棵树的第k个叶子节点上的值： γkm= ∑xi∈Rkm ∂C ∂si ∑xi∈Rkm ∂2C ∂s 2 i = −∑xi∈Rkm∑{i,j}⇌I|ΔZij|ρij ∑xi∈Rkm∑{i,j}⇌I|ΔZij|ρij(1−ρij) 所以总结LambdaMART算法如下： 6. 参考文献 1. Christopher J.C. Burges. From RankNet to LambdaRank to LambdaMART: An Overview. Microsoft Research Technical Report MSR-TR-010-82. 2. Chrisopher D.Manning, Prabhakar Raghavan, Hinrich Schutze著, 王斌译. Introduction to Information Retrieval, 8.4 有序检索结果的评价方法, 2017年10月北京第11次印刷. 3. Olivier Chapelle, Ya Zhang, Pierre Grinspan. Expected Recipocal Rank for Graded Relevance. CIKM 2009.https://www.cnblogs.com/genyuan/p/9788294.html