approach和基于神經網絡的listnet算法及java實作.包括：
1.基于列的學習排序(listwise)介紹
2.listnet算法介紹
3.listnet算法java實作
ltr中單文檔方法是将訓練集裡每一個文檔當做一個訓練執行個體,文檔對方法是将同一個查詢的搜尋結果裡任意兩個文檔對作為一個訓練執行個體,文檔列方法是将一個查詢裡的所有搜尋結果清單作為一個訓練執行個體.
listwise方法将一個查詢對應的所有搜尋結果評分作為一個執行個體,訓練得到一個最優的評分函數.在給出如下資料集中：(資料集介紹詳見上一篇文章)
===============================================================================
0 qid:10 1:0.000000 2:0.000000 3:0.000000 ... 45:0.000000 46:0.000000 #docid =
1 qid:10 1:0.031310 2:0.666667 3:0.500000 ... 45:0.448276 46:0.000000 #docid =
1 qid:10 1:0.078682 2:0.166667 3:0.500000 ... 45:1.000000 46:0.000000 #docid =
0 qid:50 1:0.044248 2:0.400000 3:0.333333 ... 45:0.622951 46:0.000000 #docid =
2 qid:50 1:0.764381 2:0.200000 3:0.000000 ... 45:0.252874 46:0.000000 #docid =
1 qid:50 1:0.693584 2:0.000000 3:0.000000 ... 45:0.275862 46:0.000000 #docid =
基于列的學習排序(listwise approach)是将qid=10對應的所有查詢文檔作為一個執行個體進行訓練,即一個查詢及其對應的所有搜尋結果評分作為一個執行個體進行訓練;訓練得到一個最後評分函數f後,test測試集中一個新的查詢,函數f對每一個文檔進行打分,之後按照得分順序由高到低排序即是對應搜尋的結果.
下面介紹一種基于搜尋結果排序組合的機率分布情況來訓練.如下圖：
參考《這就是搜尋引擎：核心技術詳解 by:張俊林》第5章
使用者輸入查詢q1,假設傳回的搜尋結果集合裡包含a、b和c三個文檔,搜尋引擎要對搜尋結果排序,而3個文檔順序共有6種排列組合方式:abc、acb、bac、bca、cab和cba,每種排列組合都是一種可能的搜尋結果排序方法.
我們可以把函數g設想成最優評分函數(人工打分),對查詢q1來說：文檔a得6分,文檔b得4分,文檔c得3分;我們的任務是找到一個函數,使得其對q1的搜尋結果打分順序盡可能的接近标準函數g.其中函數f和h就是實際的評分函數,通過比較兩個機率之間的kl距離,發現f比h更接近假想的最優函數g.故選擇函數f為搜尋的評分函數.
listwise主要的算法包括：adarank、svm-map、listnet、lambdamart等.
pointwise學習排序是将訓練集中的每個文檔看作一個樣本擷取rank函數,主要解決辦法是把分類問題轉換為單個文檔的分類和回歸問題,如prank.
pairwise學習排序(下篇介紹)是将同一個查詢中不同的相關标注的兩個文檔看作一個樣本,主要解決思想是把rank問題轉換為二值分類問題,如ranknet.
listwise學習排序是将整個文檔序列看作一個樣本,主要是通過直接優化資訊檢索的評價方法和定義損失函數兩種方法實作.listnet算法将luce模型引入到了排序學習方法中來表示文檔序列,同時大多數基于神經網絡的排序學習算法都是基于luce模型(luce模型就是将序列的任意一種排序方式表示成一個機率值)來表示序列的排序方式的.
listnet算法參考：
通過該算法步驟解釋如下:
1.首先輸入訓練集train.txt資料.{x,y}表示查詢号對應的樣本文檔,包括标注等級label=y(46維微軟資料集共3個等級:0-不相關,1-部分相關,2-全部相關),x表示對應的特征和特征值,需要注意的是x(m)表示m個qid數,每個x(m)中有多個樣本文檔.
2.初始化操作.疊代次數t(設定為30次)和learning rate(ita可以為0.003、0.001、0.03、0.01等),同時初始化權重w.
3.兩層循環操作.第一層是循環疊代次數：for t = 1 to t do;第二層循環是疊代查詢總數(qid總數)：for i = 1 to m do.
4.計算該行分數用目前權重w.注意權重w[46]是一維數組,分别對應46個特征值,同時f(w) = w * x.
5.計算梯度向量delta_w(46個次元).其中計算公式如下：
其中n(i)表示查詢号qid=i對應的總文檔數,j表示qid=i的目前文檔.x的右上方下标表示對應的qid數,右下方下标表示對應的文檔标号.而p是計算機率的函數,如下：
它表示s1排第一、s2排第二且s3排第三的機率值.這就是使用luce模型使一個序列的排序方式表示成一個單一的機率值.實際過程中,我們通過使用exp()函數來表示fai.主要保證其值為正、遞增.
但n!的時間複雜度很顯然效率很低,是以提出了top-k機率來解決,即用前k項的排列機率來近似原有的整個序列的機率,通過降低精準度來換取運作時間.
top-k機率公式如下：
在下面的java代碼實作中我采用的是top-1,即擷取目前行文檔排第一的機率值.
6.循環更新權重w.
7.最後輸出w[46]權重,訓練過程結束.通過該模型可以進行測試預測排序,test.txt通過該權重進行w*x打分,再進行從高到低排序即可.
ps:這僅僅是我結合兩篇論文後的個人了解,如果有錯誤或不足之處,歡迎探讨!同時感謝我的同學xp和mt,我們一起探讨和分享才了解了一些listnet算法及代碼.
(ps:該部分代碼非常感謝我的組長xp和mt,他們在整個程式設計路上對我幫助是一生的.同時自己也希望以後工作中能找到更多的老師和摯友指導我前行~)
代碼中有詳細的注釋,按照每個步驟完成.左圖是主函數,它主要包括：讀取檔案并解析資料、寫資料、學習排序模型和打分預測,右圖是學習排序的核心算法.
代碼如下：
上面的代碼我更希望你關注的是listnet在訓練模型過程中的代碼,也就是通過train.txt擷取得到46維的權重的模型.通過該模型你可以對test.txt進行打分(權重*特征值)排序,而上面的代碼僅是對train.txt進行了簡單的打分操作,那時因為我們的作業是基于hadoop或spark分布式處理基礎上的.是以該部分由其他同學完成.
同時你也可以通過開源的ranklib或羅磊同學的listnet算法進行學習,位址如下:
最後我們使用開源的map和ndcg@r簡單對該算法進行了性能評估,同時附上hadoop上的運作截圖(mapreduce隻找到了prank的一張截圖).
希望文章對大家有所幫助,同時我是根據論文寫出的java代碼,如果有錯誤或不足之處,還請海涵~同時歡迎提出問題,我對機器學習和算法的了解還是初學,但是會盡力答複.同時發現該部分的代碼真的很少,是以才寫了這樣一些文章,後面還準備寫寫pairwise和map\ndcg評價.