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

? Pairwise方法的實(shí)際上是把排序問(wèn)題轉(zhuǎn)換成分類問(wèn)題，以最小化文檔對(duì)的分類錯(cuò)誤為目標(biāo)。但是評(píng)估排序結(jié)果的好壞通常采用MAP或NDCG等考慮文檔排序的方法，所以Pairwise方法的損失函數(shù)并不是非常合適。 ListNet算法定義了一種Listwise的損失函數(shù)，該損失函數(shù)表示由我們的模型計(jì)算得來(lái)的文檔排序和真正的文檔排序之間的差異，ListNet最小化該損失函數(shù)以達(dá)到排序的目的。

? ListNet首先把文檔的排序列表轉(zhuǎn)換成概率分布，然后選取交叉熵來(lái)衡量由模型訓(xùn)練出的文檔排序和真正的文檔排序之間的差異，最小化這個(gè)差異值來(lái)完成排序。下面我們從如何把文檔列表轉(zhuǎn)換成概率，如何計(jì)算概率分布之間的差異值，如何優(yōu)化差異值三個(gè)部分來(lái)介紹ListNet算法。

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

? (1) 組合概率.

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

? ? ? ? ? ? ?

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

? (2) Top-K概率.

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

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

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

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

??

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

? 2. 計(jì)算概率分布的差異值

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

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

??

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

??

? 3. 優(yōu)化損失函數(shù)

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

?

? 參考文獻(xiàn):

? [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 算法簡(jiǎn)介