排序算法是信息檢索裡面很重要的一環，例如用戶提交了一個查詢 q，搜索引擎會返回很多相關的文檔，然後需要採用排序算法根據文檔與 q 的相關性對文檔進行排序。可以採用機器學習的方法解決排序的問題，稱為 Learning To Rank (LTR) 。LTR 主要分三類 PointWise，PairWise，ListWise，本文主要介紹一種 PairWise 的算法 RankNet。
1.信息檢索排序
在信息檢索時，系統需要根據用戶的查詢 q，對文檔進行相關性排序。信息檢索中有很多經典的排序算法。
a. 布爾模型(Boolean Model)
將查詢表示成關鍵詞的布爾組合，用 "與"，"或"，"非" 將查詢組合起來，然後計算文檔和查詢的匹配程度。但是布爾模型通常只能檢索出符合條件的文檔，不能進行排序，例如我們有如下三個文檔：
<code>文檔1: a b c d e f
文檔2: a x b y y z
文檔3: a c d e f g/<code>
根據文檔和單詞可以構造出一個單詞-文檔矩陣，表示單詞是否出現在文檔中。
單詞-文檔矩陣
如果用戶要查詢有 a 或者 b，但是一定有 z 的文檔。首先從上述矩陣中找出 a，b，z 對應的向量 a(1, 1, 1)，b(1, 1, 0)，z(0, 1, 0)，然後按照查詢所描述的布爾組合將向量組合在一起。如下所示，只有文檔 2 符合條件。
b. 向量空間模型 Vectos Space Model
將文檔和查詢轉成向量空間中的向量，然後計算查詢向量和文檔向量的內積得到相似度，按相似度進行排序。向量可以用 TF-IDF 向量表示。
c. PageRank
給定一個網頁 u，其影響力等於所有鏈接到 u 的網頁加權影響力之和，如下所示。
PageRank
v 表示所有能夠跳轉到網頁 u 的頁面，L(v) 表示網頁 v 所有跳轉鏈接個數。另外用戶也有可能通過輸入網址訪問頁面而不是通過跳轉鏈接，因此 PageRank 算法還加上了一個因子 d，表示用戶按照跳轉鏈接上網的概率。
PageRank 加阻尼因子
2.Learning To Rank
Learning To Rank 主要是使用機器學習的方法學習出文檔的排序，主要分為三類：
PointWise：給定查詢 q，PointWise 模型的輸入是單個文檔，直接計算出 q 和該文檔的相關性，再根據相關性進行排序。這一類方法沒有考慮文檔之間的相互依賴關係，而且損失函數是不知道排序後文檔的相對位置的。
PairWise：給定查詢 q，PairWise 模型的輸入是文檔對 (即兩個文檔)，然後計算 q 更偏向於哪個文檔。因此模型可以知道文檔之間的相對順序。
ListWise：輸入的是查詢 q 以及一組文檔，輸出為所有文檔的排序結果。
本文主要介紹一種 PairWise 的 LTR 算法，RankNet 是微軟研究院 2005 年提出的，用在搜索引擎 Bing 中，對應的論文是《Learning to Rank Using Gradient Descent》。RankNet 提出了一種概率損失函數，然後使用神經網絡學習排名函數 (ranking function)，最後用使用梯度下降的方法訓練模型。
3.RankNet
RankNet 使用神經網絡對文檔進行打分，f(x1) 表示樣本 x1 的分數，如果 f(x1) > f(x2)，則表示 x1 排名高於 x2 (用 x1->x2 表示)。
我們可以利用函數 f 計算得到樣本 xi 比樣本 xj 排名更高的概率，如下所示。
另外還需要 xi 比 xj 排名更高 (即 xi 比 xj 更加相關) 的真實概率，在數據集中有參數 Sij。如果 xi 相關性比 xj 更高，則 Sij = 1；如果 xi 相關性比 xj 低，則 Sij = -1；如果 xi 相關性和 xj 一樣，則 Sij = 0。我們可以通過下面的公式計算 xi 比 xj 排名更高的真實概率。
RankNet 的損失函數採用了 cross entrophy，根據 損失函數進行梯度下降，優化神經網絡的參數 (即函數 f)，損失函數如下所示。
下圖是不同真實概率下，損失函數取值和 (oi-oj) 的關係。
4.參考文獻
《Learning to Rank using Gradient Descent》
閱讀更多 NLP與人工智能 的文章
