排序算法是信息檢索里面很重要的一環(huán)，例如用戶提交了一個(gè)查詢 q主守，搜索引擎會(huì)返回很多相關(guān)的文檔禀倔，然后需要采用排序算法根據(jù)文檔與 q 的相關(guān)性對(duì)文檔進(jìn)行排序〔我可以采用機(jī)器學(xué)習(xí)的方法解決排序的問(wèn)題救湖，稱為 Learning To Rank (LTR) 。LTR 主要分三類 PointWise涎才，PairWise鞋既，ListWise，本文主要介紹一種 PairWise 的算法 RankNet耍铜。

1.信息檢索排序

在信息檢索時(shí)邑闺，系統(tǒng)需要根據(jù)用戶的查詢 q，對(duì)文檔進(jìn)行相關(guān)性排序棕兼。信息檢索中有很多經(jīng)典的排序算法陡舅。

布爾模型(Boolean Model)

將查詢表示成關(guān)鍵詞的布爾組合，用 "與"伴挚，"或"靶衍，"非" 將查詢組合起來(lái)灾炭，然后計(jì)算文檔和查詢的匹配程度。但是布爾模型通常只能檢索出符合條件的文檔颅眶，不能進(jìn)行排序蜈出，例如我們有如下三個(gè)文檔：

文檔1: a b c d e f
文檔2: a x b y y z
文檔3: a c d e f g

根據(jù)文檔和單詞可以構(gòu)造出一個(gè)單詞-文檔矩陣，表示單詞是否出現(xiàn)在文檔中帚呼。

布爾模型

如果用戶要查詢有 a 或者 b掏缎，但是一定有 z 的文檔。首先從上述矩陣中找出 a煤杀，b眷蜈，z 對(duì)應(yīng)的向量 a(1, 1, 1)，b(1, 1, 0)沈自，z(0, 1, 0)酌儒，然后按照查詢所描述的布爾組合將向量組合在一起。如下所示枯途，只有文檔 2 符合條件忌怎。

布爾模型檢索

向量空間模型 Vectos Space Model

將文檔和查詢轉(zhuǎn)成向量空間中的向量，然后計(jì)算查詢向量和文檔向量的內(nèi)積得到相似度酪夷，按相似度進(jìn)行排序榴啸。向量可以用 TF-IDF 向量表示。

PageRank

給定一個(gè)網(wǎng)頁(yè) u晚岭，其影響力等于所有鏈接到 u 的網(wǎng)頁(yè)加權(quán)影響力之和鸥印，如下所示。

PageRank

v 表示所有能夠跳轉(zhuǎn)到網(wǎng)頁(yè) u 的頁(yè)面坦报，L(v) 表示網(wǎng)頁(yè) v 所有跳轉(zhuǎn)鏈接個(gè)數(shù)库说。另外用戶也有可能通過(guò)輸入網(wǎng)址訪問(wèn)頁(yè)面而不是通過(guò)跳轉(zhuǎn)鏈接，因此 PageRank 算法還加上了一個(gè)因子 d片择，表示用戶按照跳轉(zhuǎn)鏈接上網(wǎng)的概率潜的。

PageRank

2.Learning To Rank

Learning To Rank 主要是使用機(jī)器學(xué)習(xí)的方法學(xué)習(xí)出文檔的排序，主要分為三類：

PointWise：給定查詢 q字管，PointWise 模型的輸入是單個(gè)文檔啰挪，直接計(jì)算出 q 和該文檔的相關(guān)性，再根據(jù)相關(guān)性進(jìn)行排序嘲叔。這一類方法沒(méi)有考慮文檔之間的相互依賴關(guān)系脐供，而且損失函數(shù)是不知道排序后文檔的相對(duì)位置的。

PairWise：給定查詢 q借跪，PairWise 模型的輸入是文檔對(duì) (即兩個(gè)文檔)，然后計(jì)算 q 更偏向于哪個(gè)文檔酌壕。因此模型可以知道文檔之間的相對(duì)順序掏愁。

ListWise：輸入的是查詢 q 以及一組文檔歇由，輸出為所有文檔的排序結(jié)果。

本文主要介紹一種 PairWise 的 LTR 算法果港，RankNet 是微軟研究院 2005 年提出的沦泌，用在搜索引擎 Bing 中，對(duì)應(yīng)的論文是《Learning to Rank Using Gradient Descent》辛掠。RankNet 提出了一種概率損失函數(shù)谢谦，然后使用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)排名函數(shù) (ranking function)，最后用使用梯度下降的方法訓(xùn)練模型萝衩。

3.RankNet

RankNet 使用神經(jīng)網(wǎng)絡(luò)對(duì)文檔進(jìn)行打分回挽，f(x1) 表示樣本 x1 的分?jǐn)?shù)，如果 f(x1) > f(x2)猩谊，則表示 x1 排名高于 x2 (用 x1->x2 表示)千劈。

我們可以利用函數(shù) f 計(jì)算得到樣本 xi 比樣本 xj 排名更高的概率，如下所示牌捷。

Pij

另外還需要 xi 比 xj 排名更高 (即 xi 比 xj 更加相關(guān)) 的真實(shí)概率墙牌，在數(shù)據(jù)集中有參數(shù) Sij。如果 xi 相關(guān)性比 xj 更高暗甥，則 Sij = 1喜滨；如果 xi 相關(guān)性比 xj 低，則 Sij = -1撤防；如果 xi 相關(guān)性和 xj 一樣虽风，則 Sij = 0。我們可以通過(guò)下面的公式計(jì)算 xi 比 xj 排名更高的真實(shí)概率即碗。

真實(shí)概率

RankNet 的損失函數(shù)采用了 cross entrophy焰情，根據(jù) 損失函數(shù)進(jìn)行梯度下降，優(yōu)化神經(jīng)網(wǎng)絡(luò)的參數(shù) (即函數(shù) f)剥懒，損失函數(shù)如下所示内舟。

損失函數(shù)

下圖是不同真實(shí)概率下，損失函數(shù)取值和 (oi-oj) 的關(guān)系初橘。

4.參考文獻(xiàn)

《Learning to Rank using Gradient Descent》