排序算法在搜索引擎中非常重要，需要根據用戶的查詢 q，對一些相關的文檔進行排序，儘可能地讓用戶感興趣的文檔排在前面。之前的文章介紹了一種 Learning to rank 的算法 RankNet，現在介紹另外兩種比較經典的排序模型 LambdaRank 和 lambdaMART。
1.RankNet 的問題
信息檢索排序問題常用的評價指標有 NDCG、ERR 等，不熟悉的童鞋可以看下之前的文章《 》，這些評價指標是不平滑不連續的，無法直接用於梯度下降。 算法將排序問題轉成一個概率問題，使用神經網絡計算出一篇文章排在另一篇文章之前的概率，使用交叉熵作為損失函數，最後用梯度下降進行求解。
RankNet 的損失函數如下所示，本質上是計算樣本的 pairwise error，即減少排序出錯的樣本數量，注意下式中 σ 是一個參數。
由於 RankNet 優化的是 pairwise error，因此會存在一些問題，我們先看下圖。
RankNet 的問題
在上圖中包含 16 個文檔，其中藍色表示相關的文檔，灰色表示不相關的文檔。左圖中 pairwise error 的個數為 13 (即第二個藍色文檔前有 13 個不相關文檔)，而右圖 pairwise error 的個數為 11。RankNet 在優化時關注於文檔對的錯誤，可能會出現有圖的結果，但是很多時候這並不是理想的。
很多評價指標，例如 NDCG 和 ERR 等更加關注的時 top k 個結果的排序，因此優化過程中把相關文檔往下調並不合適。
另外一點，右邊的圖中的黑色箭頭表示 RankNet 下一次優化時調整的方向和梯度大小 (箭頭越長梯度越大)。但是我們真正需要的是右邊的紅色箭頭，即排名越靠前的文檔梯度應該越大。因此微軟提出了 LambdaRank。
2.LambdaRank
LambdaRank 是在 RankNet 基礎上修改的，首先對 RankNet 的損失函數進行分解，得到其中的梯度。分解公式如下所示，wk 表示神經網絡模型的參數。
lambda 可以表示梯度的強度，lambda 可以進一步化簡，假設對於訓練集裡面的文檔對 (i, j)，都有文檔 i 排在文檔 j 之前，即 Sij = 1，則 lambda 可以如下簡化。
LambdaRank 主要創新點在於不直接定義模型的損失函數再求梯度，而是通過分析 RankNet 排序損失函數的梯度再直接對梯度 lambda 進行修改。
考慮到 NDCG、ERR 等指標不能直接求梯度，因此 LambdaRank 直接修改梯度 lambda，從而引入評價指標的信息，使梯度能夠接近評價指標的表現。論文中的做法是交換兩個文檔 i,j 的位置，然後計算評價指標的變化情況 |ΔZ|，把 |ΔZ| 做為 lambda 的因子。Z 可以是 NDCG 等評價指標。
通過梯度 lambda 也可以反推出 LambdaRank 的損失函數，如下。
3.LambdaMART
LambdaMART 是一種結合了 LambdaRank 和 MART 的算法。MART 算法是一種集成學習算法，全稱是 Multiple Additive Regression Tree，也稱為梯度提升樹 GBDT。MART 算法中每一棵樹都是串聯的關係，每棵樹優化的是上一次分類器的殘差。
3.1 MART 分類
對於樣本 x，MART 預測的結果為 F(x)，另 P+ 和 P- 分別表示模型預測正例和負例的概率，I+ 和 I- 表示真實的類標，如果 I+ = 1 (I- = 0)，則表示正例；如果 I+ = 0 (I- = 1)，則表示負例。可以定義交叉熵損失函數。
MART 每棵樹擬合的是當前的負梯度，如下：
Rjm 表示第 m 棵樹的第 j 個葉子節點包含的所有樣本，則該葉子節點的取值可以如下計算，最小化對應的損失函數。對應的 gamma 值就是葉子節點的取值。
最終葉子節點的取值可以用牛頓迭代法求解，公式如下，具體推導過程可以參考論文《From RankNet to LambdaRank to LambdaMART: An Overview》。
3.2 LambdaMART
LambdaMART 結合了 LambdaRank 和 MART，LambdaRank 中推導出 lambda 的公式
對應的損失函數如下。
可以求出損失函數的一階導數和二階導數
第 m 棵樹的第 k 個葉子節點的取值用下面的公式進行計算。
算法的偽代碼如下圖所示
4.參考文獻
《From RankNet to LambdaRank to LambdaMART: An Overview》
《Adapting Boosting for Information Retrieval Measures》
《Learning to Rank with Nonsmooth Cost Functions》
閱讀更多 NLP與人工智能 的文章
