LTR 算法通常有三種手段芍瑞，分別是：Pointwise课竣、Pairwise 和 Listwise朦促。Pointwise 和 Pairwise 類(lèi)型的LTR算法童太，將排序問(wèn)題轉(zhuǎn)化為回歸米辐、分類(lèi)或者有序分類(lèi)問(wèn)題。Listwise 類(lèi)型的 LTR 算法則另辟蹊徑书释，將用戶(hù)查詢(xún)（Query）所得的結(jié)果作為整體翘贮，作為訓(xùn)練用的實(shí)例（Instance）。
Pointwise
Pointwis方法的主要思想是將排序問(wèn)題轉(zhuǎn)化為多類(lèi)分類(lèi)問(wèn)題或者回歸問(wèn)題爆惧。假設(shè)對(duì)于查詢(xún)query狸页，與其相關(guān)的文檔集合為：{d1, d2, …, dn}。那么:
- 多類(lèi)分類(lèi)：將query與di之間的相關(guān)度的程度作為label扯再，一般的label等級(jí)劃分方式為：｛Perfect, Excellent, Good, Fair, Bad｝芍耘，一共五個(gè)類(lèi)別。于是熄阻，對(duì)于一個(gè)查詢(xún)及其文檔集斋竞，可以形成n個(gè)訓(xùn)練實(shí)例。有了訓(xùn)練實(shí)例秃殉，我們可以使用任一種多類(lèi)分類(lèi)器進(jìn)行學(xué)習(xí)坝初，比如最大熵，SVM复濒。
- 回歸：將query與di之間的相關(guān)度作為value，利用regression model來(lái)得到一個(gè)query與document之間相關(guān)度的預(yù)測(cè)乒省。
缺點(diǎn) ： Pointwise完全從單文檔的分類(lèi)角度計(jì)算巧颈，沒(méi)有考慮文檔之間的相對(duì)順序。而且它假設(shè)相關(guān)度是查詢(xún)無(wú)關(guān)的袖扛，只要（query砸泛，di）的相關(guān)度相同，那么他們就被劃分到同一個(gè)級(jí)別中蛆封，屬于同一類(lèi)唇礁。然而實(shí)際上，相關(guān)度的相對(duì)性是和查詢(xún)相關(guān)的惨篱，比如一個(gè)常見(jiàn)的查詢(xún)它會(huì)有很多相關(guān)的文檔盏筐，該查詢(xún)和它相關(guān)性相對(duì)靠后的文檔的label標(biāo)注級(jí)別時(shí)可能會(huì)比一個(gè)稀有的查詢(xún)和它為數(shù)不多的高度相關(guān)文檔的label標(biāo)準(zhǔn)級(jí)別更高。這樣就導(dǎo)致訓(xùn)練樣本的不一致砸讳，并且對(duì)于預(yù)測(cè)為同一label級(jí)別的文檔之間也無(wú)法相對(duì)排序琢融。
Pairwise
Pairwise方法是目前比較流行的方法界牡，效果也非常不錯(cuò)。它的主要思想是將Ranking問(wèn)題形式化為二元分類(lèi)問(wèn)題漾抬。常用的機(jī)器學(xué)習(xí)的方法比較多宿亡，比如Boost、SVM纳令、神經(jīng)網(wǎng)絡(luò)等挽荠。
- 對(duì)于同一query的相關(guān)文檔集中，對(duì)任何兩個(gè)不同label的文檔平绩，都可以得到一個(gè)訓(xùn)練實(shí)例（di,dj）圈匆，如果di>dj則賦值+1，反之-1馒过，于是我們就得到了二元分類(lèi)器訓(xùn)練所需的訓(xùn)練樣本了臭脓，如下圖所示。
-
測(cè)試時(shí)腹忽，只要對(duì)所有pair進(jìn)行分類(lèi)就可以得到所有文檔的一個(gè)偏序關(guān)系来累，從而實(shí)現(xiàn)排序。
Pairwise
缺點(diǎn) ： 盡管Pairwise對(duì)Pointwise做了改進(jìn)窘奏，但該方法還是存在明顯的問(wèn)題
- 只考慮了兩篇文檔的相對(duì)順序嘹锁，沒(méi)有考慮他們出現(xiàn)在搜索結(jié)果列表中的位置。排在前面的文檔更為重要着裹，如果出現(xiàn)在前面的文檔判斷錯(cuò)誤领猾，懲罰函數(shù)要明顯高于排在后面判斷錯(cuò)誤。因此需要引入位置因素骇扇，每個(gè)文檔對(duì)根據(jù)其在結(jié)果列表中的位置具有不同的權(quán)重摔竿，越排在前面權(quán)重越大，如果排錯(cuò)順序其受到的懲罰也越大少孝。
- 對(duì)于不同的查詢(xún)相關(guān)文檔集的數(shù)量差異很大继低，轉(zhuǎn)換為文檔對(duì)后，有的查詢(xún)可能只有十幾個(gè)文檔對(duì)稍走，而有的查詢(xún)可能會(huì)有數(shù)百個(gè)對(duì)應(yīng)的文檔對(duì)袁翁，這對(duì)學(xué)習(xí)系統(tǒng)的效果評(píng)價(jià)帶來(lái)了偏置。假設(shè)查詢(xún)1對(duì)應(yīng)500個(gè)文檔對(duì)婿脸，查詢(xún)2對(duì)應(yīng)10個(gè)文檔對(duì)粱胜，假設(shè)機(jī)器學(xué)習(xí)系統(tǒng)對(duì)應(yīng)查詢(xún)1能夠判斷正確480個(gè)文檔對(duì)，對(duì)應(yīng)查詢(xún)2能夠判斷正確2個(gè)狐树。對(duì)于總的文檔對(duì)該系統(tǒng)準(zhǔn)確率是（480+2）/（500+10）=95%焙压，但從查詢(xún)的角度，兩個(gè)查詢(xún)對(duì)應(yīng)的準(zhǔn)確率分別為：96%和20%，平均為58%冗恨，與總的文檔對(duì)判斷準(zhǔn)確率相差巨大答憔，這將使得模型偏向于相關(guān)文檔集大的查詢(xún)。
Pairwise有很多的實(shí)現(xiàn)掀抹，比如Ranking SVM虐拓，RankNet，F(xiàn)rank傲武，RankBoost等蓉驹。
Listwise
Listwise與上述兩種方法不同，它是將每個(gè)查詢(xún)對(duì)應(yīng)的所有搜索結(jié)果列表作為一個(gè)訓(xùn)練樣例揪利。Listwise根據(jù)訓(xùn)練樣例訓(xùn)練得到最優(yōu)評(píng)分函數(shù)F态兴，對(duì)應(yīng)新的查詢(xún)，評(píng)分F對(duì)每個(gè)文檔打分疟位，然后根據(jù)得分由高到低排序瞻润，即為最終的排序結(jié)果。
目前主要有兩種優(yōu)化方法：
- 直接針對(duì)Ranking評(píng)價(jià)指標(biāo)進(jìn)行優(yōu)化甜刻。比如常用的MAP, NDCG（下面介紹）绍撞。這個(gè)想法非常自然，但是往往難以實(shí)現(xiàn)得院，因?yàn)镸AP傻铣、NDCG這樣的評(píng)價(jià)指標(biāo)通常是非平滑（連續(xù)）的，而通用的目標(biāo)函數(shù)優(yōu)化方法針對(duì)的都是連續(xù)函數(shù)祥绞。
- 優(yōu)化損失函數(shù) loss function非洲。比如LambdaRank、LambdaMART蜕径。
- - - - - - - - - - - - - - - --- 華麗分割線 --- - - - - - - - - - - - - - - -
From RankNet to LambdaRank to LambdaMART
LambdaMART 是一種 Listwise 類(lèi)型的 LTR 算法两踏，它基于 LambdaRank 算法和 MART (Multiple Additive Regression Tree) 算法，將搜索引擎結(jié)果排序問(wèn)題轉(zhuǎn)化為回歸決策樹(shù)問(wèn)題兜喻。MART 實(shí)際就是梯度提升決策樹(shù)（GBDT, Gradient Boosting Decision Tree）算法梦染。GBDT 的核心思想是在不斷的迭代中，新一輪迭代產(chǎn)生的回歸決策樹(shù)模型擬合損失函數(shù)的梯度虹统，最終將所有的回歸決策樹(shù)疊加得到最終的模型弓坞。LambdaMART 使用一個(gè)特殊的 Lambda 值來(lái)代替上述梯度隧甚，也就是將 LambdaRank 算法與 MART 算法加和起來(lái)车荔。
考慮到 LambdaRank 是基于 RankNet 算法的，所以在搞清楚 LambdaMART 算法之前戚扳，我們首先需要了解 MART忧便、RankNet 和 LambdaRank 是怎么回事。
RankNet
RankNet是2005年微軟提出的一種pairwise的Learning to rank算法，它從概率的角度來(lái)解決排序問(wèn)題珠增。RankNet提出了一種概率損失函數(shù)來(lái)學(xué)習(xí)Ranking Function超歌，并應(yīng)用Ranking Function對(duì)文檔進(jìn)行排序。這里的Ranking Function可以是任意對(duì)參數(shù)可導(dǎo)的模型蒂教，也就是說(shuō)巍举，該概率損失函數(shù)并不依賴(lài)于特定的機(jī)器學(xué)習(xí)模型，在論文中凝垛，RankNet是基于神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)的懊悯。除此之外，GDBT等模型也可以應(yīng)用于該框架梦皮。
學(xué)習(xí)過(guò)程
變量定義：
A排序在B之前的目標(biāo)概率：
(a_i)
$
$\overline{P_(ij)}$
\overline{P_(ij)}
\begin{equation}
a_i
\end{equation}
＼[J\alpha(x) = \sum{m=0}^\infty \frac{(-1)^m}{m! \Gamma (m + \alpha + 1)} {\left({ \frac{x}{2} }\right)}^{2m + \alpha}＼]
A排序在B之前的模型概率：$$P_{ij}$$
映射函數(shù)：$$f(x_i)$$
值：$$o_i = f(x_i)$$
值：$$o_{ij} = f(x_i)-f(x_j)$$
交叉熵?fù)p失函數(shù)：$$C_{ij}$$
$$C_{ij} = C(o_{ij}) = -\overline{P_{ij}}logP_{ij}$$
