嚴格來說，這并不是一篇論文，只是一個?，里面系統的介紹了三個比較著名的排序模型?，鏈接 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

[2]

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

[3]

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

[4]

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），請回復“知識星球”

總結

以上是生活随笔為你收集整理的员外带你读论文：From RankNet to LambdaRank to LambdaMART: An Overview的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。