Learning to rank(簡寫 LTR、L2R) 也叫排序?qū)W習(xí)藤巢，指的是機器學(xué)習(xí)中任何用于排序的技術(shù)。

為什么要用LTR

傳統(tǒng)的檢索模型靠人工擬合排序公式息罗，并通過不斷的實驗確定最佳的參數(shù)組合掂咒，以此來形成相關(guān)性打分。這種方式非常簡單高效迈喉，應(yīng)該范圍也很廣绍刮，比如簡單的博客排序、論壇的QA排序等.但是也同時存在較大的問題:

1. 手動調(diào)參工作量太大
2. 可能會過擬合
3. 如果模型參數(shù)很多挨摸，手動調(diào)參的可用性就很低了~

LTR與此思路不同孩革，最合理的排序公式由機器學(xué)習(xí)算法來確定，而人則需要給機器學(xué)習(xí)提供訓(xùn)練數(shù)據(jù),他的優(yōu)勢有:

1. 可以自動調(diào)節(jié)參數(shù)
2. 可以融合多方面觀點的(evidences)的數(shù)據(jù)
3. 避免過擬合(通過正則項)

LTR基本框架

LTR的核心還是機器學(xué)習(xí)油坝，只是目標不僅僅是簡單的分類或者回歸了嫉戚，最主要的是產(chǎn)出文檔的排序結(jié)果刨裆，它通常的工作框架如下:

image

所描述的步驟為:訓(xùn)練數(shù)據(jù)獲取->特征提取->模型訓(xùn)練->測試數(shù)據(jù)預(yù)測->效果評估

訓(xùn)練數(shù)據(jù)的獲取

人工標注

人工標注的數(shù)據(jù)主要有以下幾大類型:

• 單點標注

  • 對于每個查詢文檔打上絕對標簽

  • 二元標注：相關(guān) vs 不相關(guān)

  • 五級標注：完美(Perfect),出色(Excellent),好(Good),一般(Fair),差(Bad) ，一般后面兩檔屬于不相關(guān)

    好處：標注的量少O(n)
    壞處：難標彬檀。帆啃。。不好統(tǒng)一

• 兩兩標注

  • 對于一個查詢Query,要標注文檔d1比文檔d2是否更加相關(guān) (q,d1)?(q,d2)?

    好處：標注起來比較方便
    壞處：標注量大 估計得有O(n^2)

• 列表標注

  • 對于一個查詢Query窍帝，將人工理想的排序整個兒標好

    好處： 相對于上面兩種努潘，標的效果會很好
    壞處： 這個工作量也太大了…-_-||

日志抽取

當(dāng)搜索引擎搭建起來之后用戶的點擊數(shù)據(jù)就變得非常好使。

比如坤学，結(jié)果ABC分別位于123位疯坤，B比A位置低，但卻得到了更多的點擊深浮，那么B的相關(guān)性可能好于A.

這種點擊數(shù)據(jù)隱含了Query到文檔的相關(guān)性好壞压怠。所以一般會使用點擊倒置的高低位結(jié)果作為訓(xùn)練數(shù)據(jù).

但是他也是存在問題的：

• 用戶總是習(xí)慣于從上到下瀏覽搜索結(jié)果
• 用戶點擊有比較大的噪聲
• 一般頭查詢(head query)才存在用戶點擊

這里的日志提取可以參考Learning to rank在淘寶的應(yīng)用,干貨！７晌菌瘫！

特征提取

檢索系統(tǒng)會使用一系列特征來表示一次查詢，通過模型之后最終決定文檔的排序順序布卡，這里用q來表示查詢,d表示查詢的文檔,occur?term共現(xiàn)的詞雨让，則提取的特征主要有以下三大類:

• occur?term特征
  • 共現(xiàn)在查詢中的出現(xiàn)次數(shù)、比率等
• occur?term的特征
  • 共現(xiàn)在文檔中的出現(xiàn)次數(shù)忿等、比率等
  • 共現(xiàn)詞與文檔的相關(guān)性特征:BM25系列
• 自身特征
  • PageRank值
  • Spam信息
  • Quality質(zhì)量分
  • 行為分,ctr栖忠，停留時間，二跳率等..

模型訓(xùn)練

LTR的模型主要有單文檔方法(Pointwise Approach)贸街、文檔對方法(Pairwise Approach)和列表方法(Listwise Approach)三大類,下面是實現(xiàn)他們的各種算法:

Pointwise Approach

Pointwise的處理對象是單獨的一篇文檔庵寞，將文檔轉(zhuǎn)換為特征向量之后，機器學(xué)習(xí)模型根據(jù)從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)到的分類或者回歸函數(shù)對文檔打分匾浪，打分的結(jié)果就是搜索的結(jié)果.

其實就是將文檔排序轉(zhuǎn)為了文檔的回歸皇帮、分類和有序分類問題，其函數(shù)的框架為:

L(F(X),y)=∑i=1nl(f(xi)?yi)

輸入:

• 單個文檔查詢對:(xi,yi)
• 完全忽略上下文的關(guān)系
• 將標注轉(zhuǎn)為數(shù)字蛋辈，比如Perfect->5, Excellent->4, Good->3, Fair->2, Bad->1

輸出:

• 排序函數(shù),對于給定查詢文檔對,能夠計算出得分(score)

關(guān)于Pointwise下的三個分支，這張圖解釋的很好:

image

其主要區(qū)別就是loss function不同将谊，也就是最后的結(jié)果目標不一樣:

• Classification:輸入的是5檔類別（作為離散）冷溶，最后通過分類模型輸測試數(shù)據(jù)的各個檔位檔位的概率，然后進行加權(quán)成一個實數(shù)值
• Regression:輸入的是5檔或者2檔（作為連續(xù)）尊浓，最后通過回歸模型輸出測試數(shù)據(jù)的一個相關(guān)性實數(shù)(就是回歸)
• Ordinal Classification:輸入的檔位是有序的,比如像上面一樣輸入5檔逞频，但是他們的權(quán)重不一樣，可能權(quán)重最高檔位的分類（二分類）栋齿，再進行次高檔位的分詞苗胀，依次下去(McRank的paper有講)

實現(xiàn)Pointwise方法的主要算法有:

• Classification
  • Discriminative model for IR (SIGIR 2004)
  • McRank (NIPS 2007)
• Regression
  • Least Square Retrieval Function (TOIS 1989)
  • Regression Tree for Ordinal Class Prediction (Fundamenta Informaticae, 2000)
  • Subset Ranking using Regression (COLT 2006)
• Ordinal Classification
  • Pranking (NIPS 2002)
  • OAP-BPM (EMCL 2003)
  • Ranking with Large Margin Principles (NIPS 2002)
  • Constraint Ordinal Regression (ICML 2005)

優(yōu)點:

• 速度快襟诸，復(fù)雜度低.

缺點:

• 效果一般
• 沒有考慮到文檔之間的相對關(guān)系
• 忽略了文檔相關(guān)度與查詢的關(guān)聯(lián)，比如Top Query排在后面的相關(guān)性比Tial Query排在前面的都要高基协，導(dǎo)致訓(xùn)練樣本不一致

Pairwise Approach

對于搜索任務(wù)來說歌亲，系統(tǒng)接收到用戶查詢后，返回相關(guān)文檔列表澜驮，所以問題的關(guān)鍵是確定文檔之間的先后相對順序關(guān)系陷揪，
而Pairwise則將重點轉(zhuǎn)向?qū)ξ臋n關(guān)系是否合理的判斷.

Pairwise主要是講排序問題轉(zhuǎn)為了文檔對順序的判斷
以下圖為例:

image

L(F(x),y)=∑i=1n?1∑j=i+1n(sign(yi?yj),f(xi)?f(xj))

輸入:

• 同一查詢的一對文檔(xi,xj,sign(yi?yj))
• 標注兩個文檔的相對關(guān)系廊蜒，如果文檔xi比xj更加相關(guān)趴拧，則sign(yi?yj))=1
• 分布保留同一查詢下的文檔間關(guān)系

輸出:

• 排序函數(shù)給出文檔對的計算得分

關(guān)于Pairwise最終的算分，其實分類和回歸都可以實現(xiàn):

image

實現(xiàn)Pairwise Approach方法的主要算法有:

• Learning to Retrieve Information (SCC 1995)
• Learning to Order Things (NIPS 1998)
• Ranking SVM (ICANN 1999)
• RankBoost (JMLR 2003)
• LDM (SIGIR 2005)
• RankNet (ICML 2005)
• Frank (SIGIR 2007)
• MHR(SIGIR 2007)
• GBRank (SIGIR 2007)
• QBRank (NIPS 2007)
• MPRank (ICML 2007)
• IRSVM (SIGIR 2006)
• LambdaRank (NIPS 2006)

雖然Pairwise方法對Pointwise方法做了改進劲藐，但是也明顯存在兩個問題:

1. 只考慮了兩個文檔的先后順序八堡，沒有考慮文檔出現(xiàn)在搜索列表中的位置
2. 不同的查詢，其相關(guān)文檔數(shù)量差異很大聘芜，轉(zhuǎn)換為文檔對之后兄渺，有的查詢可能有幾百對文檔，有的可能只有幾十個汰现，最終對機器學(xué)習(xí)的效果評價造成困難

Listwise Approach

與Pointwise和Pairwise不同挂谍，Listwise是將一個查詢對應(yīng)的所有搜索結(jié)果列表作為一個訓(xùn)練實例，因此也稱為文檔列方法.

文檔列方法根據(jù)K個訓(xùn)練實例訓(xùn)練得到最優(yōu)的評分函數(shù)瞎饲，對于一個新的查詢口叙，函數(shù)F對每一個文檔進行打分，之后按照得分順序高低排序嗅战，就是對應(yīng)的搜索結(jié)果.
Listwise主要有兩類:

• Measure specific:損失函數(shù)與評估指標相關(guān),比如:L(F(x),y)=exp(?NDCG)
• Non-measure specific:損失函數(shù)與評估指標不是顯示相關(guān),考慮了信息檢索中的一些獨特性質(zhì)

實現(xiàn)Listwise的算法主要有:

• Measure-specific
  • AdaRank (SIGIR 2007)
  • SVM-MAP (SIGIR 2007)
  • SoftRank (LR4IR 2007)
  • RankGP (LR4IR 2007)
  • LambdaMART (inf.retr 2010)
• Non-measure specific
  • ListNet (ICML 2007)
  • ListMLE (ICML 2008)
  • BoltzRank (ICML 2009)

實驗表明 一般Listwise要好于前兩種排序算法妄田，但是其復(fù)雜度是在太高了

方法對比

評估指標

MAP

MAP(Mean Average Precision)表示文檔在排序中的平均精度均值，是用于衡量個query查詢見過的平均精度值AP,
系統(tǒng)檢索出來的相關(guān)文檔越靠前(rank 越高)驮捍，MAP就可能越高疟呐。如果系統(tǒng)沒有返回相關(guān)文檔，則準確率默認為0东且。

所以對于計算AP的值就是關(guān)鍵了,MAP對文檔只分為兩檔:相關(guān)與不相關(guān)启具，則AP表示為

AP=∑ni:relvancePi/Rin

其中Pi表示所有召回文檔中相關(guān)文檔的相對次序，Ri表示所有被召回的相關(guān)文檔中在所有文檔中的次序

比如在某個query得到的排序中:

image

最終計算的AP=(1/1+2/3+3/4+4/5+5/6+6/10)/6=0.78

NDCG

NDCG表示表示歸一化折損累積增益珊泳，主要是衡量實際相關(guān)性越高的文檔排在越前面鲁冯，它的全稱是Normalized Discounted Cumulative Gain,也正好代表了4個部分的含義:

• Gain:表示增益拷沸，一般相關(guān)性越高，增益值也是越大

Gi=2yi?1

> 其中yi表示文檔相關(guān)性檔位薯演，一般檔位越高撞芍，相關(guān)性越大

• Discounted:一般認為排序位置 帶來的權(quán)重不同，所以會有一個折損因子

DGi=2yi?1log(1+i)

> 其中i為文檔的排序位置涣仿，從1開始

• Cumulative：表示在一次query查詢中所有的增益累加

DCG=∑i=1n2yi?1log(1+i)

• Normalized：為歸一化勤庐，因為在不同的查詢中可能DCG的值波動較大，這里計算各個query最理想的排序的DCG值作為歸一化因子好港，也稱為IDCG

NDCG=1IDCG?∑i=1n2yi?1log(1+i)

NDCG的可使用性更加廣泛了愉镰，但是還是存在以下三點限制:

1. NDCG并沒有對不相關(guān)文檔進行懲罰
2. NDCG對一些缺失的完成結(jié)果也沒有進行懲罰
3. NDCG也不是用檔位大家都相等的情況（比如每頁里面的doc相關(guān)性都是差不多的）

公開數(shù)據(jù)集

1. http://research.microsoft.com/en-us/um/beijing/projects/letor/
2. http://research.microsoft.com/en-us/projects/mslr/
3. http://webscope.sandbox.yahoo.com/

總結(jié)

在玩搜索引擎時敲定特征分的權(quán)重是非常疼的一件事兒，而LTR正好幫你定分钧汹，LTR的三種實現(xiàn)方法其實各有優(yōu)劣：

1. 難點主要在訓(xùn)練樣本的構(gòu)建(人工或者挖日志)丈探，另外就是訓(xùn)練復(fù)雜
2. 雖說Listwise效果最好，但是天下武功唯快不破拔莱，看看這篇文章http://www.cnblogs.com/zjgtan/p/3652689.html體驗下
3. 在工業(yè)界用的比較多的應(yīng)該還是Pairwise碗降，因為他構(gòu)建訓(xùn)練樣本相對方便，并且復(fù)雜度也還可以塘秦，所以Rank SVM就很火啊^_

參考

• 《這就是搜索引擎：核心技術(shù)詳解》 . 第五章
• Learning to Rank小結(jié)
• 機器學(xué)習(xí)及排序?qū)W習(xí)基礎(chǔ)
• Learning to Rank for Information Retrieval
• https://en.wikipedia.org/wiki/Discounted_cumulative_gain
• https://www.kaggle.com/wiki/MeanAveragePrecision