ps:文章主要轉載自csdn大神hguisu的文章"機器學習排序":
推薦&參考資料:
《learning to rank for information retrieval by:tie-yan liu》
《這就是搜尋引擎 核心技術詳解 著:張俊林》
論文《learning to rank from pairwise approach to listwise approace》
論文《adapting ranking svm to document retrieval by:tie-yan liu》
從使用的資料類型，以及相關的機器學習技術的觀點來看，網際網路搜尋經曆了三代的發展曆程。
第一代技術，将網際網路網頁看作文本，主要采用傳統資訊檢索的方法。
第二代技術，利用網際網路的超文本結構，有效地計算網頁的相關度與重要度，代表的算法有 pagerank 等。
第三代技術，有效利用日志資料與統計學習方法，使網頁相關度與重要度計算的精度有了進一步的提升，代表的方法包括排序學習、網頁重要度學習、比對學習、話題模型學習、查詢語句轉化學習。
這裡主要介紹機器學習排序。
利用機器學習技術來對搜尋結果進行排序，這是最近幾年非常熱門的研究領域。資訊檢索領域已經發展了幾十年，為何将機器學習技術和資訊檢索技術互相結合出現較晚？主要有兩方面的原因。
一方面是因為：在前面幾節所述的基本檢索模型可以看出，用來對査詢和文檔的相關性進行排序，所考慮的因素并不多，主要是利用詞頻、逆文檔頻率和文檔長度這幾個因子來人工拟合排序公式。因為考慮因素不多，由人工進行公式拟合是完全可行的，此時機器學習并不能派上很大用場，因為機器學習更适合采用很多特征來進行公式拟合，此時若指望人工将幾十種考慮因素拟合出排序公式是不太現實的，而機器學習做這種類型的工作則非常合适。随着搜尋引擎的發展，對于某個網頁進行排序需要考慮的因素越來越多，比如網頁的pagerank值、查詢和文檔比對的單詞個數、網頁url連結位址長度等都對網頁排名産生影響，google目前的網頁排序公式考慮200多種因子，此時機器學習的作用即可發揮出來，這是原因之一。
另外一個原因是：對于有監督機器學習來說，首先需要大量的訓練資料，在此基礎上才可能自動學習排序模型，單靠人工标注大量的訓練資料不太現實。對于搜尋引擎來說， 盡管無法靠人工來标注大量訓練資料，但是使用者點選記錄是可以當做機器學習方法訓練資料的一個替代品，比如使用者發出一個查詢，搜尋引擎傳回搜尋結果，使用者會點選其中某些網頁,可以假設使用者點選的網頁是和使用者查詢更加相關的頁面。盡管這種假設很多時候并 不成立，但是實際經驗表明使用這種點選資料來訓練機器學習系統确實是可行的。
ps:簡言之,上面兩個原因論述了為什麼會出現學習排序?
傳統的排序方法是通過構造一個排序函數實作，在information retrieval領域一般按照相關度進行排序。比較典型的是搜尋引擎中一條查詢query，将傳回一個相關的文檔document，然後根據(query,document)之間的相關度進行排序,再傳回給使用者。而随着影響相關度的因素變多，使用傳統排序方法變得困難，人們就想到通過機器學習來解決這一問題，這就導緻了lrt的誕生。
傳統的檢索模型靠人工拟合排序公式，并通過不斷的實驗确定最佳的參數組合，以此來形成相關性打分函數。機器學習排序與此思路不同，最合理的排序公式由機器自動學習獲得，而人則需要給機器學習提供訓練資料。
圖1是利用機器學習進行排序的基本原理圖。 機器學習排序系統由4個步驟組成：人工标注訓練資料、文檔特征抽取、學習分類函數、在實際搜尋系統中采用機器學習模型。
圖1 機器學習排序原理
首先，由人工标注訓練資料。也就是說，對于某個查詢q，人工标出哪些文檔是和這個査詢相關的，同時标出相關程度，相關程度有時候可以用數值序列來表示，比如從1分到5分為3個檔次，1代表微弱相關，5代表最相關，其他數值代表相關性在兩者之間。對于某個查詢，可能相關文檔衆多，同時使用者査詢也五花八門，是以全部靠人工标注有時候 不太可能。此時，可以利用使用者點選記錄來模拟這種人工打分機制。
對于機器學習來說，輸入是使用者查詢和一系列标注好的文檔，機器學習系統需要學習打分函數，然後按照打分函數輸出搜尋結果，但是在其内部，每個文檔由若幹特征構成的，即每個文檔進入機器學習系統之前，首先需要将其轉換我餓滴特征向量，比較常用的特征包括：
·查詢詞在文檔中的詞頻資訊
·查詢詞的idf資訊
·文檔長度
·網頁的傳入連結數量
·網頁的對外連結數量
·網頁的pagerank值
·網頁的url松度
·査詢詞的proximity值：即在文檔中多大的視窗内可以出現所有査詢詞。
以上所列隻是影響排序的一部分特征，實際上還有很多類似的特征可以作為特征向量中的一維加入。在确定了特征數量後，即可将文檔轉換為特征向量x，前面說過每個文檔會人工标出其相關性得分y。這樣每個文檔會轉換為<x,y>的形式，即特征向量及其對應的相關性得分，這樣就形成了一個具體的訓練執行個體。
通過多個調練執行個體，就可以采用機器學習技術來對系統進行訓練，訓練的結果往在是一個分類函數或者回歸函數，在之後的使用者搜尋中，就可以用這個分類函數對文檔進行打分，形成搜尋結果。
從目前的研究方法來說，可以将機器學習排序方法分為以下3種：單文檔方法（pointwise）、文檔對方法(pairwise)和文檔清單方法(listwise)。
ps：ranking學習作為機器學習研究的一個新方向，在資訊檢索、協同濾波、專家發現等領域廣泛應用。ranking學習是指通過使用機器學習技術和有标簽的資料來産生一個ranking模型，它是一種新的學習，一種介于分類和回歸之間的學習。
pointwise和pairwise把排序問題轉換成 回歸 、分類或有序分類問題。listwise把query下整個搜尋結果作為一個訓練的執行個體。3種方法的差別主要展現在損失函數（loss function）上：
•regression: treat relevance degree as real values
•classification: treat relevance degree as categories
•pairwise classification: reduce ranking to classifying the order between each pair of documents.
下面是兩張圖，第一張表示學習排序的過程，第二章是基本的實作算法。
單文檔方法的處理對象是單獨的一篇文檔，将文檔轉換為特征向量後，機器學習系統根據從訓練資料中學習到的分類或者回歸函數對文檔打分，打分結果即是搜尋結果。下面我們用一個簡單的例子說明這種方法。
圖2是人工标注的訓練集合，在這個例子中，我們對于每個文檔采用了3個特征： 査詢與文檔的cosme相似性分值、査詢詞的proximity值及頁面的pagerank數值，而相關性判斷是二進制的，即要麼相關要麼不相關，當然，這裡的相關性判斷完全可以按照相關程度擴充為多元的，本例為了友善說明做了簡化。
圖2 訓練資料
例子中提供了5個訓練執行個體，每個訓練執行個體分别标出來其對應的查詢，3個特征的得分情況及相關性判斷。對于機器學習系統來說，根據訓練資料，需要如下的線性打分函數：
score(q, d)=a x cs+b x pm+cx pr+d
這個公式中，cs代表cosine相似度變徽，pm代表proximity值變量，pr代表pagerank， 而a、b、c、d則是變量對應的參數。
如果得分大于設定閥值，則叫以認為是相關的， 如果小于設定閩值則可以認為不相關。通過訓練執行個體，可以獲得最優的a、b、c、d參數組合，當這些參數确定後，機器學習系統就算學習完畢，之後即可利用這個打分函數進行相關性判斷。對于某個新的查詢q和文檔d，系統首先獲得其文檔d對應的3個特 i特征值，之後利用學習到的參數組合計算兩者得分，當得分大于設定的閩值，即可判斷文檔是相關文檔，否則判斷為不相關文檔。
ps：而微軟給定的資料如下
=============================================================
0 qid:1 1:3 2:0 3:2 4:2 ... 135:0 136:0
2 qid:1 1:3 2:3 3:0 4:0 ... 135:0 136:0
其資料格式： label qid:id feaid:feavalue feaid:feavalue ...
每行表示一個樣本，相同的查詢請求的樣本qid相同，上面就是兩個對qid為“1”的查詢；label表示該樣本和該查詢請求的相關程度，該label等級劃分方式為 {perfect, excellent,good, fair, bad} 共五個類别。
對于搜尋系統來說，系統接收到使用者査詢後，傳回相關文檔清單，是以問題的關鍵是确定文檔之間的先後順序關系。單文檔方法完全從單個文檔的分類得分角度計算，沒有考慮文檔之間的順序關系。文檔對方法則将重點轉向量對文檔順序關系是否合理進行判斷。
之是以被稱為文檔對方法，是因為這種機器學習方法的訓練過程和訓練目标，是判斷任意兩個文檔組成的文檔對<d0c1，d0c2>是否滿足順序關系，即判斷是否d0c1應該排在doc2的前面。圖3展示了一個訓練執行個體：査詢q1對應的搜尋結果清單如何轉換為文檔對的形式，因為從人工标注的相關性得分可以看出，d0c2得分最高，d0c3次之，d0c1得分最低，于是我們可以按照得分大小順序關系得到3個如圖3所示的文檔對，将每個文檔對的文檔轉換為特征向量後，就形成了一個具體的訓練執行個體。
圖3 文檔對的方法訓練執行個體
根據轉換後的訓練執行個體，就可以利用機器學習方法進行分類函數的學習，具體的學習方法有很多，比如svm. boosts、神經網絡等都可以作為具體的學習方法，但是不論具體方法是什麼，其學習目标都是一緻的，即輸入- 個査詢和文檔對<docl，doc2>, 機器學習排序能夠判斷這種順序關系是否成立，如果成立，那麼在搜尋結果中d0c1應該排在d0c2
前面，否則doe2應該摔在docl前面，通過這種方式，就完成搜尋結果的排序任務。
盡管文檔對方法相對單文檔方法做出了改進，但是這種方法也存在兩個明顯的問題：
一個問題是：文檔對方法隻考慮了兩個文檔對的相對先後順序，卻沒有考慮文檔出現在搜尋清單中的位置，排在搜尋站果前列的文檔更為重要，如果前列文檔出現判斷錯誤，代價明顯高于排在後面的文檔。針對這個問題的改進思路是引入代價敏感因素，即每個文檔對根據其在清單中的順序具有不同的權重，越是排在前列的權重越大，即在搜尋清單前列如
果排錯順序的話其付出的代價更高?
另外一個問題是：不同的査詢，其相關文檔數量差異很大，是以轉換為文檔對之後， 有的查詢對能有幾百個對應的文檔對，而有的查詢隻有十幾個對應的文檔對，這對機器學習系統的效果評價造成困難 ?我們設想有兩個查詢，査詢q1對應500個文文檔對，查詢q2 對應10個文檔對，假設學習系統對于査詢ql的文檔對能夠判斷正确480個，對于査詢 q2的義格對能夠判新正确2個，如果從總的文檔對數量來看，這個學習系統的準确率是 (480+2)/（500+10）=0.95.即95%的準确率，但是從査詢的角度，兩個査詢對應的準确率
分别為：96%和20%,兩者平均為58%,與純粹從文檔對判斷的準确率相差甚遠，這對如何繼續調優機器學習系統會帶來困擾。
ps：pairwise方法有很多的實作，比如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)等等。
你通常會看到微軟資料集每個fold檔案夾下有train.txt test.txt vail.text三個檔案，它們分别的作用是什麼呢？
訓練集--用于學習參數，比如可以訓練10個不同階的線性模型，這裡得到每個特征值的權值；驗證集--用來選擇模型，主要考慮的準則是在新的資料上的泛化能力，比如根據各個模型在驗證集上的權值，選擇了3階的模型；測試集--測試模型，測試這個被選中的3階模型的表現。
單文檔方法将訓練集裡每一個文檔當做一個訓練執行個體，文檔對方法将同一個査詢的搜尋結果裡任意兩個文檔對作為一個訓練執行個體，文檔清單方法與上述兩種表示方式不同，是将每一個查詢對應的所有搜尋結果清單整體作為一個訓練執行個體，這也是為何稱之為文檔清單方法的原因。
文檔清單方法根據k個訓練執行個體（一個査詢及其對應的所有搜尋結果評分作為一個實 例）訓練得到最優評分函數f， 對于一個新的使用者査詢，函數f 對每一個文檔打分，之後按照得分順序由高到低排序，就是對應的搜尋結果。 是以關鍵問題是：拿到訓練資料，如何才能訓練得到最優的打分函數？
這裡介紹一種訓練方法，它是基于搜尋結果排列組合的機率分布情況來訓練的，圖4是這種方式訓練過程的圖解示意。
圖4 不同評分函數的kl距離
首先解釋下什麼是搜尋結果排列組合的機率分布，我們知道，對于搜尋 引擎來說，使用者輸入査詢q， 搜尋引擎傳回搜尋結果，我們假設搜尋結果集合包含a. b 和c 3個文檔，搜尋引擎要對搜尋結果排序，而這3個文檔的順序共有6種排列組合方式:
abc, acb, bag, bca, cab和cba,
而每種排列組合都是一種可能的搜尋結果排序方法。
對于某個評分函數f來說，對3個搜尋結果文檔的相關性打分，得到3個不同的相關度得分f(a)、 f(b)和f(c)， 根據這3個得分就可以計算6種排列組合情況各自的機率值。 不同的評分函數，其6種搜尋結果排列組合的機率分布是不一樣的。
了解了什麼是搜尋結果排列組合的機率分布，我們介紹如何根據訓練執行個體找到最優的 評分函數。圖4展示了一個具體的訓練執行個體，即査詢q1及其對應的3個文檔的得分情況，這個得分是由人工打上去的，是以可以看做是标準答案。可以設想存在一個最優的評分函數g，對查詢q1來說，其打分結果是：a文檔得6分，b文檔得4分，c文檔得3分， 因為得分是人工打的，是以具體這個函數g是怎樣的我們不清楚，我們的任務就是找到一 個函數，使得函數對ql的搜尋結果打分順序和人工打分順序盡可能相同。既然人工打分
(虛拟的函數g) 已知，那麼我們可以計算函數g對應的搜尋結果排列組合機率分布，其具體分布情況如圖4中間的機率分布所示。假設存在兩個其他函數h和f，它們的計算方法已知，對應的對3個搜尋結果的打分在圖上可以看到，由打分結果也可以推出每個函數對應的搜尋結果排列組合機率分布，那麼h與f哪個與虛拟的最優評分函數g更接近呢？一般可以用兩個分布機率之間的距離遠近來度量相似性，kl距離就是一種衡量機率分布差異大小的計算工具，通過分别計算h與g的差異大小及f與g的差異大小，可以看出f比h更接近的最優函數g，那麼在這個函數中，我們應該優先選f作為将來搜尋可用的評分函數，訓練過程就是在可能的函數中尋找最接近虛拟最優函數g的那個函數作為訓練結果，将來作為在搜尋時的評分函數。
上述例子隻是描述了對于單個訓練執行個體如何通過訓練找到最優函數，事實上我們有k 個訓練執行個體，雖然如此，其訓練過程與上述說明是類似的，可以認為存在一個虛拟的最優 評分函數g (實際上是人工打分），訓練過程就是在所有訓練執行個體基礎上，探尋所有可能的 候選函數，從中選擇那個kl距離最接近于函數g的，以此作為實際使用的評分函數。 經驗結果表明，基于文檔清單方法的機器學習排序效果要好于前述兩種方法。
聲明：本部落格摘自《這就是搜尋引擎:核心技術詳解》 第五章關于機器學習排序的内容。轉載請說明摘自出處。
最後希望文章對大家有所幫助吧!雖然是我轉載的一篇文章，但是它真心很好，是對learning to rank的基礎入門介紹文章，從為什麼引入學習排序，到介紹三種方法。