1. RankNet
RankNet是2005年微軟提出的一種pairwise的Learning to Rank算法，它從概率的角度來解決排序問題。RankNet的核心是提出了一種概率損失函數(shù)來學(xué)習(xí)Ranking Function，并應(yīng)用Ranking Function對文檔進行排序。這里的Ranking Function可以是任意對參數(shù)可微的模型，也就是說，該概率損失函數(shù)并不依賴于特定的機器學(xué)習(xí)模型，在論文中，RankNet是基于神經(jīng)網(wǎng)絡(luò)實現(xiàn)的。除此之外，GDBT等模型也可以應(yīng)用于該框架。
1.1 相關(guān)性概率
我們先定義兩個概率：預(yù)測相關(guān)性概率、真實相關(guān)性概率。
（1）預(yù)測相關(guān)性概率
對于任意一個doc對(Ui,Uj)，模型輸出的score分別為si和sj，那么根據(jù)模型的預(yù)測，Ui比Uj與Query更相關(guān)的概率為：
由于RankNet使用的模型一般為神經(jīng)網(wǎng)絡(luò)，根據(jù)經(jīng)驗sigmoid函數(shù)能提供一個比較好的概率評估。參數(shù)σ決定sigmoid函數(shù)的形狀，對最終結(jié)果影響不大。
RankNet證明了如果知道一個待排序文檔的排列中相鄰兩個文檔之間的排序概率，則通過推導(dǎo)可以算出每兩個文檔之間的排序概率。因此對于一個待排序文檔序列，只需計算相鄰文檔之間的排序概率，不需要計算所有pair，減少計算量。
（2）真實相關(guān)性概率
對于訓(xùn)練數(shù)據(jù)中的Ui和Uj，它們都包含有一個與Query相關(guān)性的真實label，比如Ui與Query的相關(guān)性label為good，Uj與Query的相關(guān)性label為bad，那么顯然Ui比Uj更相關(guān)。我們定義Ui比Uj更相關(guān)的真實概率為：
如果Ui比Uj更相關(guān)，那么Sij=1；如果Ui不如Uj相關(guān)，那么Sij=?1；如果Ui、Uj與Query的相關(guān)程度相同，那么Sij=0。通常，兩個doc的relative relevance judgment可由人工標注或者從搜索日志中獲取得到（見http://www.cnblogs.com/bentuwuying/p/6681943.html）。
1.2 損失函數(shù)
對于一個排序，RankNet從各個doc的相對關(guān)系來評價排序結(jié)果的好壞，排序的效果越好，那么有錯誤相對關(guān)系的pair就越少。所謂錯誤的相對關(guān)系即如果根據(jù)模型輸出Ui排在Uj前面，但真實label為Ui的相關(guān)性小于Uj，那么就記一個錯誤pair，RankNet本質(zhì)上就是以錯誤的pair最少為優(yōu)化目標。而在抽象成cost function時，RankNet實際上是引入了概率的思想：不是直接判斷Ui排在Uj前面，而是說Ui以一定的概率P排在Uj前面，即是以預(yù)測概率與真實概率的差距最小作為優(yōu)化目標。最后，RankNet使用Cross Entropy作為cost function，來衡量
的擬合程度：
化簡后，有：
當Sij=1，有：
當Sij=-1，有：
下面展示了當Sij分別取1，0，-1的時候cost function以si-sj為變量的示意圖：
可以看到當Sij=1時，模型預(yù)測的si比sj越大，其代價越??；Sij=?1時，si比sj越小，代價越小；Sij=0時，代價的最小值在si與sj相等處取得。
該損失函數(shù)有以下幾個特點：
當兩個相關(guān)性不同的文檔算出來的模型分數(shù)相同時，損失函數(shù)的值大于0，仍會對這對pair做懲罰，使他們的排序位置區(qū)分開。
損失函數(shù)是一個類線性函數(shù)，可以有效減少異常樣本數(shù)據(jù)對模型的影響，因此具有魯棒性。
總代價為：
其中，I表示所有在同一query下，且具有不同relevance judgment的doc pair，每個pair有且僅有一次。
1.3 合并概率
上述的模型Pij需要保持一致性，即如果Ui的相關(guān)性高于Uj，Uj的相關(guān)性高于Uk，則Ui的相關(guān)性也一定要高于Uk。否則，如果不能保持一致性，那么上面的理論就不好使了。
我們使用Ui vs Uj的真實概率 和 Uj vs Uk 的真實概率，計算Ui vs Uk的真實概率：
，則有下圖所示：
1.4 Gradient Descent
我們獲得了一個可微的代價函數(shù)，下面我們就可以用隨機梯度下降法來迭代更新模型參數(shù)wk了，即
η為步長，代價C沿負梯度方向變化。
這表明沿負梯度方向更新參數(shù)確實可以降低總代價。
1.5 加速RankNet訓(xùn)練過程
上面的是對于每一對pair都會進行一次權(quán)重的更新，其實是可以對同一個query下的所有文檔pair全部帶入神經(jīng)網(wǎng)絡(luò)進行前向預(yù)測，然后計算總差分并進行誤差后向反饋，這樣將大大減少誤差反向傳播的次數(shù)。
即，我們可以轉(zhuǎn)而利用批處理的梯度下降法：
其中，
我們令：
有：
下面我們來看看這個λi是什么。前面講過集合I中只包含label不同的doc的集合，且每個pair僅包含一次，即(Ui,Uj)與(Uj,Ui)等價。為方便起見，我們假設(shè)I中只包含(Ui,Uj)表示Ui相關(guān)性大于Uj的pair，即I中的pair均滿足Sij=1，那么
這個寫法是Burges的paper上的寫法。下面我們用一個實際的例子來看：有三個doc，其真實相關(guān)性滿足U1>U2>U3，那么集合I中就包含{(1,2), (1,3), (2,3)}共三個pair
顯然λ1=λ12+λ13，λ2=λ23?λ12，λ3=?λ13?λ23，因此我所理解的λi應(yīng)為
λi決定著第i個doc在迭代中的移動方向和幅度，真實的排在Ui前面的doc越少，排在Ui后面的doc越多，那么文檔Ui向前移動的幅度就越大(實際λi負的越多越向前移動)。這表明每個f下次調(diào)序的方向和強度取決于同一Query下可以與其組成relative relevance judgment的“pair對”的其他不同label的文檔。
同時，這樣的改造相當于是mini-batch learning?？梢约铀賀ankNet的學(xué)習(xí)過程。
原先使用神經(jīng)網(wǎng)絡(luò)模型，通過Stochastic gradient descent計算的時候，是對每一個pair對都會進行一次權(quán)重的更新。而通過因式分解重新改造后，現(xiàn)在的mini-batch learning的方式，是對同一個query下的所有doc進行一次權(quán)重的更新。時間消耗從O(n2)降到了O(n)。這對訓(xùn)練過程的影響是很大的，因為使用的是神經(jīng)網(wǎng)絡(luò)模型，每次權(quán)重的更新迭代都需要先進行前向預(yù)測，再進行誤差的后向反饋。
2. Information Retrieval的評價指標
Information Retrieval的評價指標包括：MRR，MAP，ERR，NDCG等。之前的博客中有詳細介紹過NDCG和MAP：http://www.cnblogs.com/bentuwuying/p/6681943.html，這里就不再重復(fù)介紹了。NDCG和ERR指標的優(yōu)勢在于，它們對doc的相關(guān)性劃分多個（>2）等級，而MRR和MAP只會對doc的相關(guān)性劃分2個等級（相關(guān)和不相關(guān)）。并且，這些指標都包含了doc位置信息（給予靠前位置的doc以較高的權(quán)重），這很適合于web search。然而，這些指標的缺點是不平滑、不連續(xù)，無法求梯度，如果將這些指標直接作為模型評分的函數(shù)的話，是無法直接用梯度下降法進行求解的。
這里簡單介紹下ERR（Expected Reciprocal Rank）。ERR是受到cascade model的啟發(fā)，即一個用戶從上到下依次瀏覽doc，直至他找到一個滿意的結(jié)果，ERR可以定義為：
表示第i位的doc的相關(guān)性概率：
其中，lm表示相關(guān)性評分最高的一檔。
