? 排序一直是信息檢索的核心問題之一，Learning to Rank(簡稱LTR)用機器學習的思想來解決排序問題。LTR有三種主要的方法：PointWise，PairWise，ListWise。ListNet算法就是ListWise方法的一種，由劉鐵巖，李航等人在ICML2007的論文Learning to Rank:From Pairwise approach to Listwise Approach中提出。

? Pairwise方法的實際上是把排序問題轉換成分類問題，以最小化文檔對的分類錯誤為目標。但是評估排序結果的好壞通常采用MAP或NDCG等考慮文檔排序的方法，所以Pairwise方法的損失函數并不是非常合適。 ListNet算法定義了一種Listwise的損失函數，該損失函數表示由我們的模型計算得來的文檔排序和真正的文檔排序之間的差異，ListNet最小化該損失函數以達到排序的目的。

? ListNet首先把文檔的排序列表轉換成概率分布，然后選取交叉熵來衡量由模型訓練出的文檔排序和真正的文檔排序之間的差異，最小化這個差異值來完成排序。下面我們從如何把文檔列表轉換成概率，如何計算概率分布之間的差異值，如何優化差異值三個部分來介紹ListNet算法。

? 1. 組合概率和Top-K概率。

? (1) 組合概率.

? 假設我們需要對n篇文檔進行排序，我們用 π=< π(1),π(2),...,π(n) >表示一種排列組合，其中π(i)表示排列在第i個位置的文檔。設Φ(.)是一個遞增和恒大于0的函數， Φ(x)可以是線性函數Φ(x)=αx或者指數函數Φ(x)=exp(x),則排列組合π的概率為：

? ? ? ? ? ? ?

? 其中S _π(j) 表示排列在第j個位置的文檔的得分。組合概率的計算復雜度為O(n!)，當文檔的數量較多時，計算量太大，所以ListNet選用了另外一種概率:Top-K概率。

? (2) Top-K概率.

? 序列(j ₁ ,j ₂ ,...,j _k )的Top-K概率表示這些文檔排在n個文檔中前K個的概率。在定義Top-K概率之前，需要首先定義前K個文檔為(j ₁ ,j ₂ ,...,j _k )的文檔排序的Top-K Subgroup：

而G _k 代表所有的Top-K Subgroup集合：

??G _k 中總共有N!/(N-k)!種不同的組合，大大低于組合概率的N!種組合。

? n個文檔中(j ₁ ,j ₂ ,...,j _k )排在前k個的概率，亦即(j ₁ ,j ₂ ,...,j _k )的Top-K概率為：

??

? (j ₁ ,j ₂ ,...,j _k )的Top-K概率的計算方法為：

? 2. 計算概率分布的差異值

? 在得到利用模型訓練出的文檔排序和真正的文檔排序的概率分布之后，我們可以使用多種方法來計算兩個概率分布之間的差異值作為損失函數，ListNet采用交叉熵來計算兩個概率分布之間的差異。

? 兩個概率分布p和q之間的交叉熵定義為：

??

? 在ListNet中，假設P _{y ⁽ⁱ⁾} (g)表示實際的文檔排序g的概率，而P _{z ⁽ⁱ⁾} (g)表示模型計算得來的文檔排序g的概率，則兩個文檔排序概率分布之間的交叉熵為：

??

? 3. 優化損失函數

? ListNet使用神經網絡來計算文檔的得分值，選取Φ(x)=exp(x)，然后使用梯度下降(Gradient Descent)的方法來不斷更新神經網絡的參數ω, 最小化損失函數,?ω的迭代公式如下:

?

? 參考文獻:

? [1]. Learning to Rank: From Pairwise Approach to Listwise Approach . Zhe Cao, Tao Qin, Tie-yan Liu, Ming-Feng Tsai, Hang Li. ICML 2007

? [2]. Learning to Rank for Information Retrieval and Natural Language Processing. Hang Li

ListNet 算法簡介