機器學習排序算法：列表法排序學習

基本的單點法排序學習（Pointwise Learning to Rank）和配對法排序學習（Pairwise Learning to Rank）兩種思路，單點法排序學習思路簡單實用，目的就是把經典的信息檢索問題轉化成機器學習問題，配對法排序學習則是把排序的問題轉化成針對某個查詢關鍵字每兩個文檔之間的相對相關性的建模問題，不過，這兩種思路也都有很明顯的問題，需要進一步對算法進行優化，以實現需要的最終目標

而針對優化排序問題的「終極方法」：列表法排序學習（Listwise Learning to Rank） ，相對於嘗試學習每一個樣本是否相關或者兩個文檔的相對比較關係，列表法排序學習的基本思路是嘗試直接優化像 NDCG（Normalized Discounted Cumulative Gain）這樣的指標，從而能夠學習到最佳排序結果

列表法排序學習的歷史
2000 年後，學術界和工業界都開始研究如何用機器學習來解決最優排序問題，五六年之後，研究者們才開始嘗試直接優化整個排序列表，

這方面的研究工作很多都來自微軟研究院，比如 2007 年左右的 AdaRank，就來自微軟亞洲研究院的徐君和李航，這篇論文算是較早提出列表法排序觀點的研究工作，同一年在國際機器學習大會 ICML 2007（International Conference on Machine Learning）上發表的 ListNet 算是從理論上開啓了列表法的大門，這篇論文也來自微軟亞洲研究院，是劉鐵岩等人的重要工作，類似的研究工作在這一年里如雨後春筍般湧現

另外一個方向，接下來我會提到，LambdaRank 出現稍早，而 LambdaMART 則稍微晚一點，這方面的工作是在微軟西雅圖的研究院開發的，主導人是克里斯托弗·博格斯（Christopher J.C. Burges），博格斯 2016 年退休，在微軟工作了 16 年，可以說，他領導的團隊發明瞭微軟的搜索引擎 Bing 的算法

列表法排序學習詳解
列表法排序學習有兩種基本思路，第一種，就是直接針對 NDCG 這樣的指標進行優化，目的簡單明瞭，用什麼做衡量標準，就優化什麼目標，第二種，則是根據一個已經知道的最優排序，嘗試重建這個順序，然後來衡量這中間的差異

先來說一下第一大思路，直接針對 NDCG 這樣的指標進行優化

首先，重溫一下排序測試集的測試原理，總體來說，所有的基於排序的指標都要考察測試集上，對於某一個查詢關鍵字來說，某一組文檔所組成的排序是否是最優的，有兩種比較通用的做法，第一個方法主要適用於二分的相關信息，對於某一個查詢關鍵字，針對排序產生的「頂部的 K」個文檔進行評估，查看精度（Precision）、召回（Recall）等，第二種方法，利用五級相關信息定義，在這樣的情況下，就可以利用類似於 NDCG 這樣的評價指標

那麼，直接優化排序指標的難點和核心在什麼地方呢？

難點在於，希望能夠優化 NDCG 指標這樣的「理想」很美好，但是現實卻很殘酷，NDCG 以及基於「頂部的 K」的精度，都是在數學的形式上的「非連續」（Non-Continuous ）和「非可微分」（Non-Differentiable），而絕大多數的優化算法都是基於「連續」（Continuous ）和「可微分」 （Differentiable）函數的，因此，直接優化難度比較大

針對這種情況，主要有這麼幾種方法

第一種方法是，既然直接優化有難度，那就找一個近似 NDCG 的另外一種指標，而這種替代的指標是「連續」和「可微分」的 ，只要建立這個替代指標和 NDCG 之間的近似關係，那麼就能夠通過優化這個替代指標達到逼近優化 NDCG 的目的，這類的代表性算法的有 SoftRank 和 AppRank

第二種方法是，嘗試從數學的形式上寫出一個 NDCG 等指標的「邊界」（Bound），然後優化這個邊界，比如，如果推導出一個上界，那就可以通過最小化這個上界來優化 NDCG，這類的代表性算法有 SVM-MAP 和 SVM-NDCG

第三種方法則是，希望從優化算法上下手，看是否能夠設計出複雜的優化算法來達到優化 NDCG 等指標的目的，對於這類算法來說，算法要求的目標函數可以是「非連續」和「非可微分」的，這類的代表性算法有 AdaRank 和 RankGP

說完了第一大思路後，再來看看第二大思路，這種思路的主要假設是，已經知道了針對某個搜索關鍵字的完美排序，那麼怎麼通過學習算法來逼近這個完美排序，希望縮小預測排序和完美排序之間的差距，值得注意的是，在這種思路的討論中，優化 NDCG 等排序的指標並不是主要目的，這裡面的代表有 ListNet 和 ListMLE

講了這兩大思路以後，最後再來提一下第三類思路，這類思路的特點是在純列表法和配對法之間尋求一種中間解法，具體來說，這類思路的核心思想，是從 NDCG 等指標中受到啓發，設計出一種替代的目標函數，這一步還和剛才介紹的第一大思路中的第一個方向有異曲同工之妙，都是希望能夠找到替代品

這第三類思路更進一步的則是找到替代品以後，把直接優化列表的想法退化成優化某種配對，這第二步就更進一步簡化了問題，這個方向的代表方法就是微軟發明的 LambdaRank 以及後來的 LambdaMART，微軟發明的這個系列算法成了微軟的搜索引擎 Bing 的核心算法之一

這裡簡單提一下 LambdaRank 這個系列模型的基本思想

首先，微軟的學者們注意到，一個排序算法是否達到最優的情況，簡單來看，就是查看當前的排序中，相比於最優的情況，有哪些兩兩文檔的關係搞錯了，學習最優排序的問題就被轉化成了減小這些兩兩排錯的關係，更進一步，在設計這個優化過程中，其實並不需要知道真正的目標函數的形式，而僅僅需要某種形式的梯度（Gradient）

這裡有這樣一個洞察，對於絕大多數的優化過程來說，目標函數很多時候僅僅是為了推導梯度而存在的，而如果直接就得到了梯度，那自然就不需要目標函數了。最後，通過實驗，微軟的學者們把這個 NDCG 通過梯度變化的差值再乘以這個梯度，這樣就達到了增強效果的目的

早期的 LambdaRank，特別是 RankNet 是採用了神經網絡來進行模型訓練，而 LambdaMART 則採用了「集成決策樹」的思想，更換到了基於決策樹的方法，後來實踐證明，基於決策樹的方法對於排序問題非常有效果，也就成了很多類似方法的標準配置

最後，有一點需要你注意，討論了不同的列表法思路，列表法從理論上和研究情況來看，都是比較理想的排序學習方法，因為列表法嘗試統一排序學習的測試指標和學習目標

儘管在學術研究中，純列表法表現優異，但是在實際中，類似於 LambdaRank 這類思路，也就是基於配對法和列表法之間的混合方法更受歡迎，因為從總體上看，列表法的運算複雜度都比較高，而在工業級的實際應用中，真正的優勢並不是特別大，因此列表法的主要貢獻目前還多是學術價值

今天講了列表法排序學習，可以看到，列表法排序有很多種思路，在 2000 年到 2010 年之間是一個非常活躍的研究領域，積累了大量的成果

一起來回顧下要點：

第一，簡要介紹了列表法排序學習的歷史

第二，詳細介紹了列表法排序學習的三大思路以及每個思路里的主要細節和方法

最後，留下了一個思考題，列表法是不是就完全解決了排序算法的問題呢？

參考文獻

Jun Xu and Hang Li. AdaRank: a boosting algorithm for information retrieval. Proceedings of the 30th annual international ACM SIGIR conference on research and development in information retrieval, 391-398，2007.

Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, Hang Li. Learning to rank: from pairwise approach to listwise approach. ICML, 129-136, 2017.

Q. Wu, C.J.C. Burges, K. Svore and J. Gao. Adapting boosting for information retrieval measures. Journal of Information Retrieval, 2007.

C.J.C. Burges, R. Ragno and Q.V. Le. Learning to rank with non-smooth cost functions. Advances in Neural Information Processing Systems, 2006.

C.J.C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton and G. Hullender. Learning to rank using gradient descent. Proceedings of the twenty second international conference on machine learning, 2005.

F. Xia, T.-Y. Liu, J. Wang, W. Zhang, and H. Li. Listwise approach to learning to rank — Theorem and algorithm. ICML, 1192–1199, 2008.

S. Chakrabarti, R. Khanna, U. Sawant, and C. Bhattacharyya. Structured learning for non-smooth ranking losses. SIGKDD, 88–96, 2008.

T. Qin, T.-Y. Liu, and H. Li. A general approximation framework for direct optimization of information retrieval measures.Technical Report, Microsoft Research, MSR-TR-2008-164, 2008.

M. Taylor, J. Guiver, S. Robertson, and T. Minka. SoftRank: Optimising non-smooth rank metrics. WSDM, 77–86, 2008.

J.-Y. Yeh and J.-Y. Lin, and etc. Learning to rank for information retrieval using genetic programming. SIGIR 2007 Workshop in Learning to Rank for Information Retrieval, 2007.

Y. Yue, T. Finley, F. Radlinski, and T. Joachims. A support vector method for optimizing average precision. SIGIR, 271–278, 2007.