Learning To Rank 研究與應用

轉載請註明出處：8層會議室-知乎專欄

一：背景介紹

在互聯網搜索誕生之初，檢索模型所依賴的特徵是相對簡單的，這些特徵的設計主要是基於查詢詞與文檔的匹配程度，所用到的信息比如TF-IDF等。在互聯網不斷發展的今天，更多複雜而有效設計的特徵被應用到檢索計算裡面，比如查詢與文檔深層次匹配，網頁pagerank等，人工參數調整已經不能滿足需求，此時機器學習被應用到這項任務中，同時由於互聯網海量數據的特點，比如展現點擊日誌，基於大數據的learning to rank逐漸成為熱門的領域。

二：有監督機器學習排序原理框架

1.

訓練階段：

測試階段：

在訓練階段輸入是n個query對應的doc集合，通常數據來源有兩種，一種是人工標註，即通過對實際系統中用戶query返回的doc集合進行相關性標註，標籤打分可以是三分制（相關，不相關，弱相關），也可以是更細的打分標準。另外一種是點擊日誌中獲取，通過對一段時間內的點擊信息進行處理獲得優質的點擊數據。這些輸入的doc的表示形式是多個維度的特徵向量，特徵的設計也尤其重要，對網頁系統檢索而言，常用的有查詢與文檔匹配特徵，其中細化了很多角度的匹配，比如緊密度匹配，語義匹配，精準匹配等等，還有通過將文檔分為不同域後的各個域的匹配特徵，關鍵詞匹配特徵，bm系列特徵, 以及通過dnn學習得到的端到端的匹配特徵。對各個垂直領域比如圖像搜索而言，在網頁搜索特徵的基礎上，需要利用圖片相關性特徵，圖片標籤等一系列垂直特徵去加強學習效果。

通過排序模型的不斷迭代，當一個用戶輸入一個query之後，排序系統會根據現有模型計算各個doc在當前特徵下的得分，並根據得分進行排序返回給用戶。

1.

排序演算法

常見的LTR學習將學習任務分為三種策略，即pointwise，pairwise，Listwise三類。其中pointwise將其轉化為多類分類或者回歸問題，pairwise將其轉化為pair分類問題，Listwise為對查詢下的一整個候選集作為學習目標，三者的區別在於loss不同。

1)

Pointwise

一種思想是將query與doc之間的相關程度作為標籤，比如標籤有三檔，問題就變為多類分類問題,模型有McRank,svm，最大熵等。另一種思想是將query與doc之間的相關程度作為分數利用回歸模型擬合，經典回歸模型有線性回歸，dnn，mart等。

輸入：doc 的特徵向量

輸出：每個doc的相關性分數

損失函數: 回歸loss，分類loss，有序回歸loss

2)

Pairwise

Pairwise的方法是將文檔組成文檔對，不單考慮單個文檔，而是考慮文檔組對是否合理，比如對於query 1返回的三個文檔 doc1，doc2，doc3, 有三種組對方式，<doc1,doc2>,<doc2,doc3>,<doc1,doc3>。當三個文檔原來的label為3,4,2時，這樣組對之後的三個例子就有了新的分數（表達這種順序是否合理），可以利用這種數據進行分類學習，模型如SVM Rank, 還有RankNet(C. Burges, et al. ICML 2005)， FRank(M.Tsai, T.Liu, et al. SIGIR 2007)，RankBoost(Y. Freund, et al. JMLR 2003)。

Pairwise的一個問題是其對不同分數的doc區分度是一樣的，然而在信息系統裡面用戶更傾向於點擊最前面的結果，所以應該著重將相關性最高的排在前面。並且在現有的各類模型中並非以排序性能作為最終目標，將會導致最終排序效果並不理想。

輸入：doc pair <d1，d2>

輸出: 偏向得分 {-1,+1}

損失函數：pairwise分類loss

3)

ListWise

Pointwise將訓練集里每一個文檔當做一個訓練實例，pairwise方法將同一個査詢的搜索結果里任意兩個文檔對作為一個訓練實例，Listwise方法是將每一個查詢對應的所有搜索結果列表整體作為一個訓練實例，

常見的模型比如ListNet使用正確排序與預測排序的排列概率分布之間的KL距離（交叉熵）作為損失函數，LambdaMART的框架其實就是MART，主要的創新在於中間計算的梯度使用的是Lambda，將類似於NDCG這種無法求導的IR評價指標轉換成可以求導的函數，並且富有了梯度的實際物理意義

輸入：doc 集合{d1,d2….}

輸出：所有doc的打分或者排列順序

損失函數：IR評價機制如NDCG，MAP

LambdaMart由於是基於MART框架，在學習的過程中可以通過特徵採樣和樣本採樣來降低過擬合風險。

3

實際應用

Learning to rank的演算法已經被應用到圖片檢索系統中。訓練數據主要來源於標註數據集，我們把query與圖片的相關性標籤分為三檔，即弱相關，相關與不相關。在query的選擇上，通過對近六個月的query進行統計挖掘，將pv次數少的長尾query作為重點目標，在實際中也是這類的query效果優化需求更高。目前標註數據一共四萬個query，每個query包含30個返回結果，其中，train集,val集以及test集合的比例為4:1:1。特徵的構建一方面基於文本檢索系統本身的特徵，主要是前面所提到的各種文本域的匹配信息，還加入了包括query與站點匹配，query與圖片匹配，圖片與所在網頁文本匹配等基於圖片和站點挖掘的各種信息。

訓練採用5-fold交叉驗證，在實驗中嘗試採樣特徵以及採樣數據來降低過擬合，並且調整樹和葉子節點數目獲得最優參數。下面給出在部分實驗數據上的效果（20000

query）。

這裡僅給出了LambdaMart與Mart的效果對比，同時在LambdaMart與其他LTR演算法的對比實驗中也都是效果更好，這裡就不一一列出了。

上面講了多種LTR演算法，而在實際應用中通常會根據任務目的調整演算法，例如Yahoo在2016年的論文《Ranking Relevance in Yahoo Search》中core ranking 模塊中利用GDBT+logistic

loss，核心思想是對於正樣本，保證梯度一直是正的，而對於負樣本，保證梯度一直是負的.通過這種策略，減少了40%的bad

url，並且在此基礎上調整了響應函數，相當於對於不同的label具有不同的loss權重，稱它為LogisticRank。

下面是論文中提到的幾種排序策略對比的對比：

可以看到logisticRank可以提高最相關的結果的排序，這也符合用戶對於檢索系統的要求。

這種方法在實際中的效果也取決於當前訓練數據，我們利用已有的標註數據基於論文提到的演算法進行實驗,，然後對實際系統中的top k結果進行重排,發現排序效果並沒有比lambdamart更好，原因是這種方法的目的是消除候選doc中的負例，而topk中明顯不好的負例佔比不大，而因此訓練樣本最好是query返回的全量數據，但是這樣標註代價太大，需要數據的長期積累。

4.Risk機制

現在許多改善搜索結果質量的策略被相繼提出，這些技術通過設計高級排序特徵或者利用複雜的學習排序去提升整體平均效果，然而，儘管這些策略相對於基準線來說提升了搜索結果的平均效果，但一個很重要的因素卻被忽略了，那就是穩健性，也就是說雖然在平均整體上有提升，但是許多query上的表現卻大打折扣，這在真實檢索場景中是不適用的。因此，系統有效性和穩健性應該同時作為訓練目標，目的是盡量降低最嚴重的排序失誤，我們需要在兩者之間找到一個平衡。

Lidan Wang ,Paul N. Bennett以及Bekir

Taner Dincer等人在這個方向進行了探索，提出了risk的概念。

下面我們的一個直方圖統計，幫我們更好的理解這個問題。

圖中為query經過LTR模型之後相對於baseline的NDCG變化情況，正值代表相對於baseline效果提升，負值代表相對於baseline效果下降。 其中負值的部分就是所謂的risk，更進一步說就是隨機選擇一個query，可預見模型在此query上的搜索結果質量的下降幅度。正值的含義稱為risk，就是相反的概念。因此整體效果的提升可以用公式表達：

Reward – Risk +Baseline

因此優化Reward和Risk,可以直接改善搜索質量。更好的系統應該是能夠儘可能降低risk，同時又能保證整體搜索質量提升。

上面表格是risk模型在微軟數據集上的表現，a控制模型訓練過程中risk控制程度，可見隨著控制程度加大，loss>20%的query數據顯著下降。

在我們自己的數據集上的實驗效果如下：

因此通過加入risk機制，可以靈活的調節模型在query上的表現。

論文中一共提到了三種優化方法，Urisk，SARO，FARO，後兩種是在第一種的基礎上加入了自適應調節策略，它們三者都是優化中心都是LambdaMART訓練過程中的梯度，也就是傳說中的deltaNDCG。

筆者基於RankLib-2.3實現了以上三種策略，開源代碼地址為 ilovedoudou/Risk-Sensitive-LTR。

5結語

目前LTR不僅被應用到檢索系統中，也應用到所有與排序相關的各種需求中。與此同時，在這方面的研究一直是信息檢索領域的熱點和難點。本文中所提到都是有監督的，但是標註耗費人力物力，並且標註的結果也不一定滿足最終用戶的需求，因此近幾年無監督的Online Learning to Rank for Information

Retrieval 在IR領域越來越被關注，它是基於用戶點擊模型以及交互行為的在線學習排序系統，也是之後我們的研究方向。

5. 參考論文

1) Learning to Rank. Hang Li.

Microsoft Research Asia

2) Learning to Rank for Information Retrieval

.Tie-Yan Liu. Lead ResearcherMicrosoft

Research Asia

3) Learning to Rank with Nonsmooth Cost

Functions

4) Adapting Boosting for Information Retrieval

Measures

5) A Short Introduction to Learning to Rank

6) Yahoo! Learning to Rank Challenge Overview

7) Ranking Relevance in Yahoo Search

8) Learning

Query and Document Relevance from a Web-scale Click Graph

9) Robust Ranking Models via Risk-Sensitive

Optimization

10)

Hypothesis Testing for the Risk-Sensitive Evaluation of Retrieval

Systems

11) Multileave Gradient Descent for Fast Online

Learning to Rank

12) Balancing

Exploration and Exploitation in Listwiseand Pairwise Online

推薦閱讀：