Learning to Rank，即排序學習，簡稱為 L2R，它是構建排序模型的機器學習方法，在信息檢索、自然語言處理、數據挖掘等場景中具有重要的作用。其達到的效果是：給定一組文檔，對任意查詢請求給出反映文檔相關性的文檔排序。本文簡單介紹一下 L2R 的基本演算法及評價指標。 背景 隨著互聯網的快速發 ...
Learning to Rank，即排序學習，簡稱為 L2R，它是構建排序模型的機器學習方法，在信息檢索、自然語言處理、數據挖掘等場景中具有重要的作用。其達到的效果是：給定一組文檔，對任意查詢請求給出反映文檔相關性的文檔排序。本文簡單介紹一下 L2R 的基本演算法及評價指標。
背景
隨著互聯網的快速發展，L2R 技術也越來越受到關註，這是機器學習常見的任務之一。信息檢索時，給定一個查詢目標，我們需要算出最符合要求的結果並返回，這裡面涉及一些特征計算、匹配等演算法，對於海量的數據，如果僅靠人工來干預其中的一些參數來進行排序的話，是遠遠不能達到要求的，而 L2R 演算法就是用來解決這種問題的，L2R 將機器學習的技術很好地應用到了排序中，並提出了一些新的理論和方法，有效解決了排序的問題，而且效率上相比人工干預也有了幾個數量級的飛躍。
L2R 演算法
L2R 演算法主要包括三種類別：Pointwise、Pairwise、Listwise，下麵分別進行介紹。
1. Pointwise
Pointwise 將問題轉化為多分類或回歸問題。如果歸結為多分類問題，對於某個 Query，對文檔與此 Query 的相關程度打標簽，標簽分為有限的類別，這樣就將問題轉為多分類問題；如果歸結為回歸問題，對於某個 Query，則對文檔與此 Query 的相關程度計算相關度 Score，這樣就將問題歸結為回歸問題。
模型
應用 Pointwise 模型有 Subset Ranking、OC SVM、McRank、Prank 等。
輸入
特定的 Query，文檔的特征向量。
輸出
文檔與 Query 的標簽類別或相關性分數。
損失函數
回歸 Loss、分類 Loss、有序回歸 Loss。
優缺點
Pointwise 演算法實現簡單，易於理解，但它只對給定 Query 單個文檔的相關度進行建模，僅僅考慮了單個文檔的絕對相關度，Pointwise 只學習到了文檔和 Query 的全局相關性，對排序先後順序有一定的影響。在某一些場景下，排在最前面的幾個文檔對排序結果的影響非常重要，如搜索引擎的第一頁的內容非常重要，而 Pointwise 沒有考慮這方面的影響，不對排序的先後順序優劣做懲罰。
2. Pairwise
上文提到 Pointwise 方法只考慮了單個文檔和 Query 的絕對相關度，Pairwise 考慮的則是兩個文檔之間的相對相關度，比較不同文檔的先後順序。Pairwise 方法是目前比較流行的方法，它將整個排序問題轉為二元分類問題，即構建的是一個二分類器，對一個文檔對 <Doc1, Doc2> 做二分類，一類是 Doc1 排序前於 Doc2，另一類則相反，通過兩兩比較，模型可以學習到不同文檔之間的先後順序。
模型
應用 Pairwise 的模型有 Ranking SVM、RankBoost、RankNet、GBRank、IR SVM 等。
輸入
特定 Query，文檔對 <Doc1, Doc2>。
輸出
文檔對偏向得分，{-1, 1}。
損失函數
Pairwise 分類 Loss。
優缺點
Pairwise 方法通過考慮兩兩文檔之間的相關度來進行排序，有一定進步。但 Pairwise 使用的是兩文檔之間相關相關度的損失函數，而它和真正衡量排序效果的指標之間存在很大不同，甚至可能是負相關的，如可能出現 Pairwise Loss 越來越低，但 NDCG 分數也越來越低的現象。另外此方法只考慮了兩個文檔的先後順序，且沒有考慮文檔在搜索列表中出現的位置，導致最終排序效果並不理想。
3. Listwise
Listwise 演算法相對於 Pointwise 和 Pairwise 方法來說，它不再將排序問題轉化為一個分類問題或者回歸問題，而是直接針對評價指標對文檔的排序結果進行優化，如常用的 MAP、NDCG 等。
模型
應用 Listwise 的模型有 ListNet、ListMLE、SVM MAP、AdaRank、SoftRank、LambdaRank、LambdaMART。其中 LambdaMART（對 RankNet 和 LambdaRank 的改進）在 Yahoo Learning to Rank Challenge 表現出最好的性能。
輸入
特定Query，文檔集合
輸出
所有文檔的打分或者排列順序
損失函數
評價指標如 NDCG、MAP 等。
優缺點
由於此種方法是針對評價指標直接進行優化，所以它往往表現出不錯的效果。
評價指標
L2R 評價指標主要有 NDCG、MAP、WTA、MRR 等，下麵分別簡單介紹一下。
1. NDCG
NDCG，全稱為 Normalized Discounted Cumulative Gain，是一種綜合考慮模型排序結果和真實序列之間的關係的一種指標，也是最常用的衡量排序結果的指標，其計算公式如下：
$$ \mathrm{NDCG@K} = \frac{DCG}{iDCG} $$
NDCG 其實是由 DCG 的值計算出來的，分子為模型計算出的 DCG 值，分母則為理想情況下的 DCG 值，而 DCG 的計算公式如下：
$$ \mathrm{DCG@K} = \sum_{i=1}^{k}{\frac {{2^{r(i)}-1}}{\log_{2}{(i+1)}}} $$
在 DCG 的表達式中，$\sum_{i=1}^{k}$ 是求和累積，${r(i)}$ 表示在模型給出的排序中，排名為 i 的元素的實際分數，這裡通過 ${2^{r(i)}-1}$ 運算放大了其分數的差異，$\log_{2}{(i+1)}$ 是每個元素的折價，由於排序靠前的元素被選取的概率更大，所以這裡可以使得排名前面的元素影響權重更大。
2. MAP
MAP，全稱為 Mean Average Precision，即平均準確率。對於每個真實相關的文檔，考慮其在模型排序結果中的位置 P，統計該位置之前的文檔集合的分類準確率，取所有這些準確率的平均值。
對於一個 Query，原本有 4 個相關結果，查詢時將 4 個結果都查詢出來了，其 rank 分別為 1, 2, 4, 7，則 MAP 為 (1/1 + 2/2 + 3/4 + 4/7)/4 = 0.83。對於另一個 Query，原本有 5 個相關結果，查詢只有 3 個相關結果，其 rank 分別為 1, 3, 5，則 MAP 為 (1/1 + 2/3 + 3/5 + 0 + 0)/5 = 0.45。則 MAP = (0.83 + 0.45)/2 = 0.64。
3. WTA
WTA，全稱 Winners Take All，對於給定的查詢 Query，如果模型返回的結果列表中，第一個文檔是相關的，則 WTA =1， 否則為 0。
如對於一個 Query，本來有 5 個相關結果，查詢結果中如果第一個結果是相關的，那麼 WTA = 1，如果第一個結果是不相關的，則 WTA = 0。
4. MRR
MRR，全稱 Mean Reciprocal Rank，是把相關文檔在結果中的排序倒數作為準確度，然後再取平均。
如對於第一個 Query，查詢結果將正確結果排名 rank 為 3，則其 Reciprocal Rank 為 1/3，對於第二個 Query，查詢結果將正確結果排名 rank 為 2，則其 Reciprocal Rank 為 1/2，對於第三個 Query，查詢結果將正確結果排名 rank 為 1，則其 Reciprocal Rank 為 1，則 MRR = (1/3 + 1/2 + 1)/3 = 11/18 = 0.61。
參考資料
- Learning to Rank, Hang Li
- Learning to Rank for Information Retrieval, Tie-Yan Liu
- Learning to rank基本演算法小結
- Learning to Rank簡介
- 淺談智能搜索和對話式OS
- Learning to Rank 簡介
- NDCG評價標準
