[aMMAI] Paper Summary: Paper Summary: Learning to Rank: From Pairwise Approach to Listwise Approach

Title: Learning to Rank: From Pairwise Approach to Listwise Approach

Author: Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, Hang Li

Publication:  ICML, 2007

Learning to rank: 利用machine learning的方法，來幫助排序。

常用的方法有Pointwise、Pairwise、與這篇論文提出的Listwise，主要是跟Pairwise做比較。

Pointwise:

單看文件與query之間的關係，利用訓練的方式，找出可以算出query與文件之間分數(相關性)有多少的模型。

Pairwise:

除了看query與文件之間的關係外，現在還要兩兩pair去比較，根據其相關性的大小給與不同的類別(+1, -1)。

Pairwise有一些缺點:

1. 兩兩去看文件相關性而不是去看一整串文件間的相關性

2. 一些評估的方法(MAP、NDCG)都是著重在rank的前幾名上(實際上，使用者在使用時通常也只看前幾個搜尋結果)，pair並沒有針對前面的部分做細分。

Listwiae:

對所有文件取出所有的排列可能，每個排列都有一個機率在。

作者定義了一個機率函式來計算每個排列的機率，如下。

但是因為排列的可能性太多了，複雜度會達到O(n!)。

所以後面提出只對前k個文件做排列，複雜度降到O(P_n^k)

用cross-entropy做為loss function。y:正確排序、z:預測排序。

最後用gradient decent的方法來做learning，訓練出一個線性的模型。

作者稱這個方式為ListNet。