员外带你读论文：From RankNet to LambdaRank to LambdaMART: An Overview

严格来说，这并不是一篇论文，只是一个 ，里面系统的介绍了三个比较著名的排序模型 ，链接 Rank^[1]

本篇博文将分析总结下这三个排序模型。其参考的代码RankNet、LambdaRank^[2],LambdaMart^[3]。

需要说明的是，本篇博文在主要总结论文和实现代码同时，也小部分的参考了这篇文章Learning to Rank 算法介绍：RankNet，LambdaRank，LambdaMart^[4]

RankNet

这是基于 方法的排序模型。

数据集由 分开。

24 [[-1.0, 0.85, 0.35], [1.0, 0.66, 1.0], [-1.0, 0.42, 0.18], [-1.0, 0.46, 0.1]]
25 [[-1.0, 0.51, 0.6], [-1.0, 0.35, 0.61], [1.0, 0.75, 1.0], [-1.0, 0.58, 0.23]]
26 [[-1.0, 0.55, 0.63], [-1.0, 0.62, 0.74], [-1.0, 0.01, 0.8], [1.0, 0.63, 0.35]]
27 [[1.0, 0.97, 0.27], [-1.0, 0.89, 0.42], [-1.0, 0.56, 0.06], [-1.0, 0.49, 1.0]]
20 [[-1.0, 0.37, 1.0], [-1.0, 0.0, 0.88], [-1.0, 0.0, 0.92], [1.0, 0.97, 0.65]]
21 [[1.0, 0.76, 1.0], [-1.0, 0.52, 0.11], [-1.0, 0.74, 0.6], [-1.0, 0.02, 0.54]]
22 [[1.0, 0.76, 1.0], [-1.0, 0.21, 1.0], [-1.0, 0.0, 0.52], [-1.0, 0.8, 0.31]]
23 [[-1.0, 0.96, 0.02], [-1.0, 0.91, 0.35], [-1.0, 0.59, 1.0], [1.0, 0.87, 0.99]]
28 [[-1.0, 0.35, 0.79], [-1.0, 0.26, 0.39], [-1.0, 0.18, 1.0], [1.0, 0.79, 0.03]]
29 [[-1.0, 0.64, 0.52], [-1.0, 0.56, 0.16], [1.0, 0.83, 1.0], [-1.0, 0.12, 0.55]]
0 [[1.0, 0.85, 0.62], [-1.0, 0.77, 0.13], [-1.0, 0.22, 0.88], [-1.0, 0.79, 0.27]]
4 [[1.0, 0.97, 0.29], [-1.0, 0.0, 0.09], [-1.0, 0.43, 0.72], [-1.0, 0.52, 0.52]]

上面字典数据集是实现代码中生成的，为 ， 为一个列表，表示与该  可能相关的所有文档集，每个子列表的第一个数表示该文档与 是否相关，第二、第三个数表示该文档的特征。

对于一个给定的 而言，与其可能相关的文档集合中（假设大小为），不同 的两两文档形成一个文档对(  )，模型 可以对这两个文档进行打分分别得到 ，可以理解为相关性得分，那么 应该排在 前面的概率为：

注意：这里面的 是个常数，决定了 函数的形状。上面公式中的 为两两文档打分的差，显然结果应该是一个矩阵。根据公式可知， 越大于 ，其的 越大，符合逻辑。那么在实做时如何实现这一步呢？

代码中定义了一个三层的神经网络作为排序模型，给输入的一个 下的每个文档进行打分。

def compute_graph(X):"""Build compute graphdefine a function for computing ds_i/dw_k respectively,┆   as the tf.gradient() computes sum_{k} dy_k/dx_i w.r.t x_iArgs:┆   X: the input feature vector tensor shaped [None, x_i]Returns:┆   y: the output predict tensor shaped [None, y_i]"""if config.USE_HIDDEN_LAYER == True:┆   with tf.name_scope("hidden_layer"):┆   ┆   layer_h1 = tf.add(tf.matmul(X, weights["hidden"]), biases["hidden"])┆   ┆   layer_h1 = tf.nn.relu(layer_h1)┆   with tf.name_scope("out_layer"):┆   ┆   y = tf.add(tf.matmul(layer_h1, weights["out"]), biases["out"])else:┆   with tf.name_scope("linear_layer"):┆   ┆   y = tf.add(tf.matmul(X, weights["linear"]), biases["linear"])return y

这样我们就可以给文档打分了，并且计算两两文档之间的打分差：

y = compute_graph(X)
sigma_ij = y - tf.transpose(y)##广播操作

得到  大小的 矩阵。

 是指预测的分数分布，那么真实的得分分布呢？论文中是这样定义的：

其中，为  时，表示文档  比  与 更相关，反正为  ，相关性相等时则为  。

那么损失函数就可想而知了，论文中用 来衡量这两种分布的距离：

那么代码中如何实现这一步呢？

Sij_ = Y - tf.transpose(Y)## Y 为真实得分
Sij = tf.minimum(1.0, tf.maximum(-1.0, Sij_))##将其取值控制在0,1,-1
Pij_hat = 1.0 / 2.0 * (1 + Sij)
Cij = tf.nn.sigmoid_cross_entropy_with_logits(┆   logits=sigma_ij, labels=Pij_hat)

这样就得到了损失函数了，直接利用 来 。

loss = tf.reduce_mean(Cij)
train_op = tf.train.GradientDescentOptimizer(┆   ┆   config.LEARNING_RATE).minimize(loss)

 实现起来很简单？不对啊，论文中还有大量的梯度推导的公式啊，对， 把参数更新的过程都自动化的实现了，无需我们自己实现这些麻烦的过程。

LambdaRank

 以错误 最少为优化目标的算法，然而许多时候仅以错误 数来评价排序的好坏是不够的，像  或者 等评价指标就只关注 个结果的排序，当我们采用 算法时，往往无法以这些指标为优化目标进行迭代，所以 的优化目标和  评价指标之间存在不一致的地方。然而这些指标的缺点是不平滑、不连续，无法求梯度，如果将这些指标直接作为模型评分的函数的话，是无法直接用梯度下降法进行求解的。

由上面的分析，我们必须要重新定义 函数，并且 函数需要考虑指标的优化。这就要我们仔细的推导了。下面我们仔细推导下 参数更新的过程

上面 的交叉商损失函数为：

可以计算得：

再用梯度下降法可以更新参数：

加速训练过程

由上面的推导，我们可以再进行简单的化简：

如此，论文中这样定义 ：

在代码中如何实现这一步呢？

# pairwise lambda matrix
# lambda_ij = dCij/ds_i = 1/2 * (1 - Sij) * dsigma(s_i - s_j)/d(s_i - s_j) * 1
#    - (dsigma(s_i - s_j)/d(s_i - s_j) * 1) / (1 + e^(sigma_ij))
# here we assign sigma = Identity, thus dsigma/d(si - sj) = 1
# thus lambda_ij = 1.0 / 2.0 * (1 - Sij) - 1.0 / (1 + tf.exp(sigma_ij))
# but tf.exp may have numerical precision issue
# comforming to sigma_ij + sigma_ji = 0, lambda_ij + lambda_ji = 0
# use the reformulation exp(-x) = exp(log(1 + exp(-|x|)) - min(0, x)) - 1
lambda_ij = 1.0 / 2.0 * (1 - Sij) - 1.0 / \tf.exp(tf.log(1 + tf.exp(-tf.abs(-sigma_ij))) - tf.minimum(0.0, -sigma_ij))

论文中进一步提到，在 中不需要对每个文档进行，只需要知道两两文档之间的相对关系即可。

由上面的 的计算可知：

在求得 后，我们就可以利用梯度下降法 批量的加速反向更新过程。

应该如何理解上面的  呢？论文中是这样说的， 是针对预测排序后的第 个文档而言，我们假设 和 ，有：

这一步不太好理解，举例来说：假设有三个文档，其中有，则集合 中就包含 共三个文档对，则按照上面损失函数对参数 求偏导的公式来说有：

合并相同的，可知，，。

论文中提到，这个 正负号指的就是文档 下一次的移动方向，其大小指的是移动距离。

如上图所示，每个线条表示文档，蓝色表示相关文档，灰色表示不相关文档， 以 的方式计算，左图的 为，右图通过把第一个相关文档下调 3 个位置，第二个文档上条 5 个位置，将 降为 11，但是像  或者 等评价指标只关注 个结果的排序，在优化过程中下调前面相关文档的位置不是我们想要得到的结果。虽然较小的下调前面文档的位置和较大的提升后面文档位置，得到的 可能会变小，但是实际上指标值却下降了。右图左边黑色的箭头表示 下一轮的调序方向和强度，但我们真正需要的是右边红色箭头代表的方向和强度，即更关注靠前位置的相关文档的排序位置的提升。 正是基于这个思想演化而来，其中 指的就是红色箭头，代表下一次迭代优化的方向和强度，也就是梯度。

那么在代码中如何求得  呢？

# dC/dw_k = \sum{lambda_ij * (ds_i/dw_k - ds_j/dw_k)}
#    = \sum{lambda_i * ds_i/dw_k}
# lambda_i is the coefficiency of dC/dw_k
# which is factorized as lambda_i = \sum_{if Sij = 1}{lambda_ij} -
#    \sum_{if Sji = 1}{lambda_ji}
ij_positive_label_mat = tf.maximum(Sij, 0) #Mij = 1 if (i, j) \in P
ij_positive_mat = ij_positive_label_mat * lambda_ij## 论文中提到在Sij=1的情况下
ij_sum = tf.reduce_sum(ij_positive_mat, [1])
ji_sum = tf.reduce_sum(ij_positive_mat, [0])
lambda_i = ij_sum - ji_sum #lambda_i for \sum_{i}dCij/dsi - \sum_{i}dCji/dsj

这样就求出了 了。

因为 优化目标与评价指标不一致，所以在 的损失函数中，我们需要考虑评价指标的因素，例如。

在论文中，其实就是在上面 基础上引入评价指标  ，把交换两个文档的位置引起的评价指标的变化作为其中一个因子，此时要优化的 变为：

那么这个 如何求呢？显然这应该是个矩阵。代码中是这样实现的：

relevance = tf.maximum(Y, 0) # negative label normalize to 0
##pdb.set_trace()
Y_r = tf.squeeze(Y)
Y_sort_r = tf.nn.top_k(Y_r, k=tf.shape(Y_r)[0]).values
Y_sort = tf.expand_dims(Y_sort_r, [1])
relevance_sort = tf.maximum(Y_sort, 0) # ideal result sequence
ranks_sort_r = tf.cast(tf.range(1, tf.shape(Y)[0] + 1, 1), dtype=tf.float32) # [1, 2, ..]
ranks_sort = tf.expand_dims(ranks_sort_r, [1]) # column vectory_r = tf.squeeze(y) # row vector (1-D tensor)
# y_indices_sort[i] = j means doc j ranks i
y_indices_sort = tf.nn.top_k(y_r, k=tf.shape(y_r)[0]).indices
def gen_mask_tensor(x):"""Generate mask tensorArgs:┆   x: location 1-D tensorReturn:┆   1-D tensor [0, 0, .. ,1, .., 0] with index x set to 1"""return tf.gather(identity_mat, tf.squeeze(x))
idx_to_rank_mat = tf.map_fn(gen_mask_tensor, tf.expand_dims(y_indices_sort, [1]))
# ranks_compute[i] = j means the document ranks i is doc j
# i.e. reverse mapping of y_indices_sort
ranks_compute_r = tf.reduce_sum(ranks_sort * tf.cast(idx_to_rank_mat, dtype=tf.float32), axis=[0])
ranks_compute = tf.expand_dims(ranks_compute_r, [1])# DCG(t) = \sum^(t)_{1}
def log2(x):"""Compute log(x)/log(2)"""return tf.log(x)/tf.log(tf.constant(2.0))
# current DCG
dcg_each = (2 ** relevance - 1) / log2(ranks_compute + 1)
dcg = tf.reduce_sum(dcg_each)
# ideal DCG
max_dcg_each =(2 ** relevance_sort - 1) / log2(ranks_sort + 1)
max_dcg = tf.reduce_sum(max_dcg_each)
# |\Delta NDCG| matrix by swapping each i, j rank position pair
# denoted li = relavance of i, ri = rank of i, lirj = 2^(li)/lg2(rj + 1)
# [l1r1 l1r1 l1r1
#  l2r2 l2r2 l2r2
#  l3r3 l3r3 l3r3]
dcg_each_col_tile = tf.tile(dcg_each, [1, tf.shape(y)[0]])
# [l1r1 l2r2 l3r3
#  l1r1 l2r2 l3r3
#  l1r1 l2r2 l3r3]
dcg_each_row_tile = tf.tile(tf.transpose(dcg_each), [tf.shape(y)[0], 1])
# [l1r1 l1r2 l1r3
#  l2r1 l2r2 l2r3
#  l3r1 l3r2 l3r3]
dcg_swap_col = (2 ** relevance - 1) / log2(tf.transpose(ranks_compute) + 1)
# [l1r1 l2r1 l3r1
#  l1r2 l2r2 l3r2
#  l1r3 l2r3 l3r3]
dcg_swap_row = tf.transpose(dcg_swap_col)
delta_dcg = 0 - dcg_each_col_tile - dcg_each_row_tile + dcg_swap_col + dcg_swap_row
delta_ndcg = delta_dcg / max_dcg

这十几步代码其实挺难理解的，我仔细的推了一遍，是正确的。其中最后得出的矩阵，其  即表示第 个文档和第 个文档互换位置后的 差值。，拆分开就是 （把第 个文档放在排序为 的位置的 值和原本第 个文档就在第 个位置的 的差值）和  （同理）

要特别说明的是，这里一定要注意 是如何做的，不是我们想当然的，这样理解是错误的，应该是：

由此可以得到需要新的 和新的：

lambda_ij_objective = lambda_ij * tf.abs(delta_ndcg)## 这句代码揭示了RankNet的不同。# lambda_i becomes
ij_positive_label_mat = tf.maximum(Sij, 0) # Mij = 1 if (i, j) \in P
ij_positive_mat_objective = ij_positive_label_mat * lambda_ij_objective
ij_sum_objective = tf.reduce_sum(ij_positive_mat_objective, [1])
ji_sum_objective = tf.reduce_sum(ij_positive_mat_objective, [0])
lambda_i_objective = ij_sum_objective - ji_sum_objective

在求得新的  后，我们利用梯度上升法来更新参数：

因此相比，  只是在 的基础上引入了评价指标的因素。

损失函数的梯度代表了文档下一次迭代优化的方向和强度，由于引入了 评价指标， 梯度更关注位置靠前的优质文档的排序位置的提升。有效的避免了下调位置靠前优质文档的位置这种情况的发生。 相比  的优势在于分解因式后训练速度变快，同时考虑了评价指标，直接对问题求解，效果更明显。

LambdaMart

在之前的博文已经详细总结过 的推导，其实一句话就可以总结：每次生成的树都是在拟合之前所有已经生成的树的残差，也就是在梯度下降的方向来生成这课树。

那么在上面的 方法中我们已经得到了梯度的计算方式，是否可以用集成学习的方式来学习呢？

在论文中提到  的计算方式

注意这里面的 可能是 或者其他任何一个评价指标，当互换 的位置引起的变化，具体计算上面已经详细讲到。

论文中以  为梯度重新定义了损失函数：

后面就是求损失函数的二阶梯度，再利用牛顿法去优化损失函数，得到当前生成的树。

我感觉上面这种讲法有点不太好理解，下面我直接以 的套路讲下个人想法：

我们已经知道残差的计算方式为 ，那么直接去拟合每一步的残差去生成树不就可以了吗，都不需要知道损失函数。在实作时也是这样做的。

model_output = np.zeros(len(features))##初始化
for i in range(n_trees):##预先设定的树的个数print " Iteration: " + str(i + 1)# Compute psedo responces (lambdas)# witch act as training label for documentstart = time.clock()print "  --generating labels"##计算之前所有生成的树的预测结果所得lambda值。其就是计算残差，都不需要定义损失函数，因为残差已经定义好了。##在获取每一步模型打分后，根据真实相关，计算NDCG变化值。lambdas = compute_lambdas(model_output, scores, queries, k)print zip(lambdas, scores)#lambdas = mart_responces(model_output, scores)print "  --done", str(time.clock() - start) + " sec"# create tree and append it to the modelprint "  --fitting tree"start = time.clock()tree = DecisionTreeRegressor(max_depth=6)##新建一棵树# print "Distinct lambdas", set(lambdas)tree.fit(features, lambdas)##拟合残差print "  ---done", str(time.clock() - start) + " sec"print "  --adding tree to ensemble"ensemble.add(tree)# update model scoreprint "  --generating step prediction"prediction = tree.predict(features)##当前生成的这课树的预测结果。# print "Distinct answers", set(prediction)print "  --updating full model output"##这句是重点：将当前这颗树的预测结果累加到之前的预测结果去，作为新预测结果。model_output += learning_rate * prediction# print set(model_output)# train_scorestart = time.clock()print "  --scoring on train"##获取当前集成树的NDCG值。train_score = score(model_output, scores, queries, 10)

 计算过程：

def query_lambdas(page, k=10):true_page, model_page = page##真实打分，模型预测打分worst_order = np.argsort(true_page)true_page = true_page[worst_order]model_page = model_page[worst_order]model_order = np.argsort(model_page)idcg = dcg(np.sort(true_page)[-10:][::-1])size = len(true_page)position_score = np.zeros((size, size))for i in xrange(size):┆   for j in xrange(size):┆   ┆   position_score[model_order[i], model_order[j]] = \┆   ┆   ┆   point_dcg((model_order[j], true_page[model_order[i]]))lambdas = np.zeros(size)for i in xrange(size):┆   for j in xrange(size):┆   ┆   ┆   if true_page[i] > true_page[j]:┆   ┆   ┆   ┆   delta_dcg  = position_score[i][j] - position_score[i][i]┆   ┆   ┆   ┆   delta_dcg += position_score[j][i] - position_score[j][j]┆   ┆   ┆   ┆   delta_ndcg = abs(delta_dcg / idcg)┆   ┆   ┆   ┆   rho = 1 / (1 + math.exp(model_page[i] - model_page[j]))┆   ┆   ┆   ┆   lam = rho * delta_ndcg┆   ┆   ┆   ┆   lambdas[j] -= lam┆   ┆   ┆   ┆   lambdas[i] += lamreturn lambdas

总结

 在推导的时候只用了 比 的相关性高还是低，没用上包含位置信息的评估指标（如），就推出了梯度，在 的 的基础上加入评价指标因素。所以 的，就强硬的在 的上乘上了评估指标的变化（因为评估指标不连续导致目标函数难以推导）。注意 到 的目标函数，从代价函数变成了效用函数，所以从使用负梯度变成了正梯度。感觉加上评价指标的因素这一做法有点像强化学习的反馈机制。

参考资料

[1]

Rank: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.180.634&rep=rep1&type=pdf

RankNet、LambdaRank: https://github.com/Njust-taoye/lambdarank/tree/master/src

LambdaMart: https://github.com/Njust-taoye/LambdaMart

Learning to Rank算法介绍：RankNet，LambdaRank，LambdaMart: http://www.cnblogs.com/bentuwuying/p/6690836.html

关于本站

“机器学习初学者”公众号由是黄海广博士创建，黄博个人知乎粉丝23000+，github排名全球前100名（33000+）。本公众号致力于人工智能方向的科普性文章，为初学者提供学习路线和基础资料。原创作品有：吴恩达机器学习个人笔记、吴恩达深度学习笔记等。

往期精彩回顾

• 那些年做的学术公益-你不是一个人在战斗

• 适合初学者入门人工智能的路线及资料下载

• 吴恩达机器学习课程笔记及资源（github标星12000+，提供百度云镜像）
  

• 吴恩达深度学习笔记及视频等资源（github标星8500+，提供百度云镜像）

• 《统计学习方法》的python代码实现（github标星7200+）

• 机器学习的数学精华（在线阅读版）
  

备注：加入本站微信群或者qq群，请回复“加群”

加入知识星球（4300+用户，ID：92416895），请回复“知识星球”

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！