Learning to Rank: From Pairwise Approach to Listwise Approach

Learning to Rank: From Pairwise Approach to Listwise Approach

ICML 2007
Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, Hang Li
==================================================

這篇的目的是要改進以前用的pairwise ranking的方法
利用listwise learning method 然後搭配適合的 model 跟 training method

主要可分為以下三個階段：
1. Listwise Approach
2. Probability Models:
     a. Permutation Probability
     b. Top One Probability
3. Learning Method: ListNet
下面將分別詳述：

1.  Listwise Approach
簡單地說就是在training 的時候，要餵給一個list
要告訴它說這個list裡每個object的分數，愈前面愈高分
相較於以往的方法，以前用的是pairwise
所以之前是會分是或不是  也就是 +1 or -1
現在則是要有類似ranking的分數在list裡

2. Probability Models:
    a. Permutation Probability
因為input是list，所以排的順序也變得很重要
如何去算出這樣順序的好壞或是分數要用到permutation
所以這裡定了這樣的方法

    b. Top One Probability
為了有別於以往的pairwise，上述listwise的方法是可以直接拿整個list來算score
這裡就用了一些推導証明出可以只用Top One的就好
因此就不用像以前pairwise算的次數那麼頻繁
另外這篇paper用來算distance的方法是 Cross Entropy (不過為什麼不用DL-divergence?)

3. Learning Method: ListNet
搭配上面的model，利用GD (Gradient Descent) 來作optimization
找到最佳的weight之後，後面丟進來的query就可以利用這些weight來算score
然後做完ranking 排出好的結果
另外paper裡也提到這部分與RankNet大致上相同
唯一的差異是在RankNet是pairwise，這裡改成listwise
也因為這個改進，時間複雜度下降了一個O(n), n = #doc
==================================================

實驗的部分用了TREC跟OHSUMED這兩個dataset
然後拿另外的RankBoost, RankSVM, RankNet 來當baseline
其中RankNet還是當時的 state-of-art
實驗的結果在accuracy跟NDCG的結果幾乎都比較好
此外我很好奇他們怎麼evaluate ranking的結果
他們用CSearch的dataset，裡面對每個query都有1000筆結果
然後有分別給出0~4分，不過這個dataset似乎是要付費的

在Discussion裡有說明他們的方法為什麼會比RankNet來得好
因為training data取的部分很有可能會biased
然後在作pairwise similarity的時候可能就會當成negative class
因此就算不到它的weight
而在listwise就沒有這個問題，因此表現也較RankNet來得好
==================================================

優點：
1. 數學算式推導及lemma儘管用得不少，但條理很清楚，非常容易看懂!!
2. baseline的方法用了三種，其中有一種還是state-of-art，無論是速度或效果都比較好
3. 整套的方法從listwise input, model, 到training method 都有做好調整，且寫得很清楚

缺點：(Nothing to complain!!)
在introduction裡面，有寫到ranking對很多問題(領域)都有幫助 ex: sentiment analysis
但沒有真的去做application 的結果研究