封面圖來源：叔叔的朋友圈
本文是原創文章歡迎轉載
論文: Learning to Rank: From Pairwise Approach to Listwise Approach
當我們做CTR預估建模的時候，如果樣本標籤是點擊和未點擊，那我們正在做的就是pointwise的方法，模型預測的是用戶點擊某一個item的概率得分，基於這個得分進行排序。看起來好像沒有問題，為什麼還會有pairwise和listwise？看完本文可能可以解答一部分疑惑。
摘要
本文涉及learning to rank，即構建排序對象的模型或函數。learning to rank對於文檔檢索、協同過濾和許多其他應用非常有用。有一些將對象pair作為學習實例的learning to rank的方法被提出。本文將它們稱為pairwise方法。儘管pairwise具有優勢，但它忽略了排序是對象列表的預測任務。本文假設，learning to rank應採用listwise方法，其中對象list在學習作為"實例"。本文提出了一種新的方法。具體來說，它引入了兩個概率模型，分別涉及到排列概率然後選出最大的那一個，定義一個listwise損失函數用於學習。然後，在學習方法中使用神經網絡和梯度下降作為模型和算法。在信息檢索的實驗結果表明，listwise方法比pairwise方法效果更好。
1 引言
許多應用的核心問題是排序。包括文檔檢索、協同過濾、專家查找、反Web垃圾郵件、情緒分析和產品打分。本文以文檔檢索為例，討論learning to rank，不失通用性。
learning to rank，當應用於文檔檢索時，是這樣的一個任務。假設有一個文檔集合。在檢索（即排序）中，給定一個查詢，排序函數為每個文檔分配一個分數，並按分數的降序對文檔進行排序。排序順序表示文檔相對於查詢的相對相關性。在學習中，提供了許多查詢;每個查詢都與文檔的完整排序列表關聯;然後使用訓練數據創建排序函數，以便模型可以精確預測訓練數據中的排序列表。
由於其重要性，learning to rank在機器學習社區中越來越受到廣泛關注。基於我們所說的pairwise方法已經開發出來，並成功地應用於文檔檢索。這種方法在學習中以文檔對作為實例，將learning to rank正式化為分類問題。具體來說，在學習中，它從排序列表中收集文檔對，並且對於每個文檔對，它分配一個標籤，表示兩個文檔的相關性。然後用標記數據對分類模型進行建模，並在排序中採用分類模型。使用支持向量機（SVM），Boosting和神經網絡作為分類模型產生對應的方法，Ranking SVM方法（Herbrich 等人，1999 年）、RankBoost（Freund 等人，1998 年），和 RankNet (Burges et al., 2005).
採用pairwise方法有其優點。首先，現有的分類方法可以直接應用。其次，在某些情況下，文檔對的訓練實例很容易獲得（Joachims，2002 年）。但是，這種方法也存在問題。首先，學習的目標被公式化為最大限度地減少文檔對分類中的錯誤，而不是最小化文檔排序中的錯誤。其次，訓練過程的計算成本很高，因為文檔對的數量非常大。第三，生成文檔對的假設也過於強。第四，生成的文檔對的數量因查詢而異，這將導致訓練一個偏向於具有更多文檔pair的查詢的模型（Cao 等人，2006 年）
在這篇論文中，我們提出listwise方法，使用文檔list而不是文檔pairs當做實例。那麼，主要的問題是如何定義一個listwise損失函數，通過排序模型來表示排序列表輸出和給出真實標籤的差別。
我們提出了一種計算listwise損失函數的概率方法。具體來說，我們將排序函數所分配的文檔分數和人所給出的文檔隱式或顯示的標籤轉換為概率分布。然後，我們可以利用概率分布之間的任何指標作為損失。我們考慮使用兩種模型進行轉型;一個稱為排列概率，另一個稱為top one概率。
然後，我們提出了一個learning to rank listwise損失函數，神經網絡作為模型，梯度下降作為算法。我們稱它為 ListNet。
我們應用 ListNet 進行文檔檢索，並比較了它的結果與現有的pairwise方法的結果，包括ranking SVM、RankBoost 和 RankNet。三個數據集的結果表明，我們的方法優於現有方法，這表明在learning to rank時，使用listwise方法比使用pairwise方法更好。
本文的主要貢獻包括：(1)提出了listwise方法，(2)在概率模型的基礎上公式化listwise損失函數，(3)開發ListNet方法，(4)驗證方法的有效性。
論文的其餘部分按如下方式組織。第2節介紹相關工作。第3節對learning to rank的listwise給出了一般性描述。第4節介紹了用於定義listwise損失函數的概率模型，第5節中解釋learning to rank ListNet。第6節報告我們的實驗結果。最後，第7節給出結論。
2 相關工作
2.1 Learning to Rank
Learning to rank是機器學習中一個新的熱門話題。Learning to rank有一種主要的方法，在本文中稱為pairwise。
在pairwise方法中，學習任務被形式化為分類任務，將對象pair分類為兩個類別（正確排序和錯誤排序）。赫布裡希等人（1999年）採用這種方法，利用SVM技術技術建立分類模型。該方法被重新稱為Ranking SVM。Freund等人（1998年）建議以同樣的方式，但通過"Boosting"的方式執行這項任務。Burges等人（2005年）也採用了這種方法，並開發了一種稱為 RankNet 的方法，他們採用交叉熵作為損失函數和梯度下降作為算法來訓練神經網絡模型。
Learning to rank，特別是pairwise方法，已先後應用於信息檢索。Joachims （2002） 應用Ranking SVM到文檔檢索。他開發了一種方法，從用戶的點擊數據中提取用於訓練的文檔對。Burges等人（2005年）將 RankNet 應用於大規模網頁搜索。曹等人（2006年）通過修改損失函數，將Ranking SVM用於為文檔檢索。
2.2 排序的概率模型
在統計學中，提出了表示對象排序列表的概率分布，以及評估分布的方法。例如，在 Luce （1959） 之後，Plackett （1975） 在對象排序列表中定義了概率分布。他進一步介紹了描述概率分布的參數，並開發了一種估計參數的方法。Plackett將模型和方法應用於投票結果的預測。本文利用類似的概率分布。但是，我們模型的基本結構（即參數）和基本用法（即分數向概率分布的轉換）與 Plackett 的不同。
3.1 Listwise方法
在本節中，我們將給出learning to rank通用的描述，以文檔檢索為例。特別地，我們將仔細描述listwise方法。在後續描述中，我們使用上標來指示查詢索引，下標指示特定查詢的文檔索引。
在訓練集中，給定queries的集合
特徵向量
我們接著創建排序函數f；對於每一個特徵向量
其中L是listwise的損失函數。
在排序的時候，當新的query
相比之下，在pairwise方法中，新的訓練數據集
4 概率模型
我們提出使用概率模型計算等式(1) 中的listwise損失函數。具體來說，我們使用本節中描述的一個概率模型將分數列表映射到概率分布，然後將兩個概率分布之間的任何指標作為損失函數。這兩個模型稱為排列概率和top one概率。
4.1 排列概率
假設對象集合需要被排序，標識為數字1，2，...，n。對象上的一個排列
假如這裡有一個排序函數給n個對象打分。我們使用s來代表打分列表
我們假設使用排序函數預測排序列表（排列）存在不確定性。換句話說，假設任何排列都是可能的，但根據排序函數，不同的排列可能有不同的likehood。我們定義排列概率，在給定排序函數下，它具有代表排列可能性（排序列表）理想的屬性。
定義1 假設
其中
讓我們考慮這樣一個有3個對象的例子，{1,2,3}擁有得分s = (s1, s2, s3)。排列的
引理2 排列概率
定理3 給定任意2個排列
定理4 對於n個對象，如果
定理4很容易證明。引理2和定理3的證明在附錄中。
定理3表示，對於基於給定排序函數的任何排序列表，如果我們交換得分較高的對象的位置和得分較低的對象的位置，我們獲得具有較低排列概率的排序列表。定理4表示給定一個排序函數，基於排序函數排序的對象列表具有最高的排列概率，而按相反順序排序的 對象列表的排列概率最低。也就是說，儘管假定所有排列都是可能的，但使用排序函數對他們進行排序。
給定兩個分數列表，我們可以先計算兩個排列的概率分布，然後計算兩個分布之間的距離作為listwise的損失函數。因此排列的數量是n!，因此，計算量可能會太大。為了解決這樣的問題， 我們考慮使用top one概率。
4.2 Top one概率
一個對象的top one概率表示它排在頂部的概率，給定所有對象的得分的情況下。
定義5 對象j的top one概率定義為：
其中
這就是說，對象j的top one概率等於，對象j排在頂部的排列概率的總和。
有人可能會爭辯說， 為了計算n個top one概率， 我們仍然需要計算n!排列概率。定理6表明，我們可以用不同的方式計算top one概率，這種方法是高效的。
定理6 對於一個top one概率
其中sj是對象j的得分，j = 1,2,...,n。
引理7 Top one概率
定理8 給定2個對象j和k，如果
定理6的證明在附錄中。引理7和定理8的證明很容易。
通過使用top one概率，給定兩個分數列表，我們可以使用任何指標來表示兩個分數列表之間的距離（listwise損失函數）。例如，當我們使用交叉熵作為指標時，listwise損失函數變為
5 學習方法：listNet
我們引入一個新的學習方法來優化listwise基於top one概率的損失函數，使用神經網絡和梯度下降。我們稱這個方法為ListNet。
我們以文件檢索為例。我們標記基於神經網絡模型
給定一個query
在交叉熵度量下，對於query
我們可以得到關於參數
等式3使用梯度下降，算法1描述了ListNet的學習算法。
注意ListNet跟RankNet很像。主要的區別在於ListNet使用文檔列表作為樣本，而RankNet使用文檔pair作為樣本。前者使用listwise損失函數而後者使用pairwise損失函數。有趣的是，當每個query只有2個文檔的時候，listwise損失函數變成了pairwise損失函數。
RankNet的時間複雜度是
6 實驗
我們對比了ListNet和3個基準方法的排序準確率：在3個數據集上，對比RankNet，Ranking SVM，RankBoost。這裡ListNet是基於top one概率模型。
為了簡化，在實驗中，我們使用線下神經網絡並且在模型中忽略了b：
其中<.,.>代表內積。
6.1 數據收集
我們在實驗中使用了三個數據集：TREC，一個從TREC2003網絡獲得的數據集(Craswell等人，2003年);OHSUMED，一套用於重新記錄文件的基準數據集(Hersh等人，1994年);和CSearch，一個商業搜尋引擎。
TREC由2002年初從.gov do域名抓取的網頁組成。數據集中共有1053110個頁面和 11164829個超連結。它還包含來自TREC 2003 Web跟蹤主題蒸餾任務的50個查詢。提供了與查詢相關的網頁上的相關性判斷（相關或無關）。從每個查詢文檔pair中提取大約20 個特徵，包括內容特徵和超連結特徵。
OHSUMED（Hersh等人，1994年）是一系列關於醫學的藥學和查詢，包括348566個文檔和106個查詢。總共有16140個query-document pair，根據這些pair進行相關判斷。相關性判斷要麼絕對相關，要麼可能相關，要麼不相關。文檔檢索中的標準功能（Nallapati，2004 年）用於每個查詢文檔對。總共有 30 個特徵。
CSearch是一個來自商業網絡搜索的數據集。它包含大約 25000個查詢，每個查詢都有一千個關聯的文檔。每個查詢文檔對總共有大約600個特徵，包括與查詢相關的特徵和獨立特徵。此數據集提供五個級別的相關性判斷，從 4（"完全匹配"）到0（"不匹配"）。
要為每個查詢獲取基本真實排序列表，我們只需使用實例的 *排序* 創建列表。
在排序性能評估中，採用了2個常用的信息檢索評估指標：NDCG(Normalized Discounted Cumulative Gain)和MAP(Mean Average Precision)。NDCG 旨在評估在有個兩以上相關性判斷時排序的準確性。對於 MAP，假設有兩個級別：相關和不相關的。在計算 OHSUMED 的MAP時，我們將"確定性相關"視為相關級別，其他兩個級別視為不相關。對於 CSearch，我們只使用 NDCG。
6.2 排序準確性
對於TREC和OHSUMED，我們將每個數據集劃分為五個子集，並進行了5 -fold的交叉驗證。在每個試驗中，三個folds用於訓練，一個flod用於驗證，一個fold用於測試。對於 RankNet和ListNet，每個試驗中的驗證集用於確定迭代的次數。對於Ranking SVM，它用於調整係數C，對於 RankBoost，它用於選擇弱學習者的數量。我們在本節中報告的結果是五次試驗的平均結果。
圖 1和表1提供了TREC的結果。我們可以看到 ListNet 的所有指標都優於RankNet、Raning SVM和RankBoost的三種基線方法。特別是對於NDCG@1和NDCG@2，ListNet達到4個點以上的增益，相對提升在10%左右。
圖2和表1顯示了OHSUMED的結果。同樣，ListNet 在所有指標方面都優於RankNet和 RankBoost。此外，ListNet在NDCG@1，NDCG@2和NDCG@4和MAP方面比 Ranking SVM，除了NDCG@3和NDCG@5。
CSearch是一個大型數據集，因此我們沒有進行交叉驗證。相反，我們隨機選擇了三分之一的數據進行訓練，三分之一用於驗證，剩下的三分之一用於測試。圖3顯示了 ListNet、RankNet和RankBoost的結果。同樣， ListNet 在所有指標方面都超過RankNet和RankBoost。由於訓練數據很大，因此無法使用 SVMlight 工具運行Ranking SVM（Joachims，1999 年）。
6.3 討論
我們研究了為什麼listwise方法ListNet可以超過RankNet，ranking SVM 和 RankBoost。
如第1節所述，對於pairwise方法，文檔對的數量因查詢而異。因此，訓練模型可能偏向那些具有更多文檔對的查詢。我們觀察到所有數據集中的傾向。例如，表2顯示了 OHSUMED 中每個查詢中每個查詢的文檔對數的分布。我們可以看到分布是偏斜的：大多數查詢只有少量文檔對（例如少於5000個），而少數查詢具有大量文檔對（例如超過 15000 個）。在listwise方法中，在每個query上定義損失函數，不存在這樣的問題。這似乎是 ListNet 提高性能的原因之一。
pairwise方法實際上採用了pairwise損失函數，該函數可能過於鬆散，作為NDCG和MAP 性能測量的近似值。通過對比，listwise方法中使用的listwise損失函數可以更恰當地表示性能評估。這似乎是ListNet性能超過RankNet 等的另一個原因。為了驗證這種想法，我們進一步研究了兩種方法的優化過程。我們研究了ListNet和RankNet使用的損失函數與 NDCG在學習階段之間的相關性。請注意，兩種方法的主要區別在於loss。使用TREC數據的結果如圖4和圖5所示。從這些數字中，我們可以看到RankNet的pairwise損失與NDCG 沒有反向的相關性。從迭代20到迭代50次，NDCG@5增加，而pairwise RankNet減少。但是，在迭代60次之後，NDCG@5開始下降，儘管pairwise loss仍在減少。相比之下， ListNet的listwise loss與NDCG成反比。更具體地說，從迭代20到迭代50，listwise loss減少，NDCG@5增加。迭代 50 後，listwise的loss達到其極限，同時NDCG@5收斂。此外，pairwise損失收斂比listwise損失收斂得慢，這意味著 RankNet 需要在訓練中運行比 ListNet更多的迭代。根據MAP評估的結果，也觀察到了類似的趨勢。
我們的結論是，對於learning to rank來說，listwise方法比pairwise方法更有效。
7 結論
本文提出了一種新的learning to rank方法，稱為listwise方法。我們認為，在learning to rank方面，採用這種方法比採用傳統的pairwise方法更好。在listwise方法中，我們使用對象列表作為學習的實例，而不是使用對象pairs作為實例。
listwise方法的關鍵想法是定義一個listwise損失函數。本文提出了一種概率方法來解決它。具體來說，我們使用概率模型：排列概率和top one概率，將排序分數轉換為概率分布。然後，我們可以將概率分布之間的任何指標（例如，交叉熵）視為listwise損失函數。
然後，我們開發了一種使用神經網絡和梯度下降的學習方法。三個數據集的實驗結果顯示，該方法比現有的pairwise方法（如 RanNet、ranking SVM 和 RankBoost）效果更好，這表明在learning to rank中採用listwise方法比較好。
未來的工作包括探討除交叉熵以外的其他目標函數的性能，以及其他排序模型取代線性神經網絡模型。我們還將研究listwise損失函數與信息檢索中使用的NDCG和MAP等性能指標之間的關係。
Learning to rank分為三種方法，pointwise，pairwise和listwise。本文系統的描述了learning to rank的listwise方法，從樣本構造，損失函數設計，原理的論證等。在推薦系統中，learning to rank是比較常見的一種算法，在數據量不是很大的業務場景，deep模型效果一般不會太好，可以考慮試試LightGBM和XGBoost的learning to rank方法。
最近身體不太舒服，在這敏感的時候感冒發燒，影響了文章的進度，當然更多還是自己的惰性，後面還是要鞭策自己，持續把點滴時間利用起來，加油。