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 的結果研究

Support Vector Learning for Ordinal Regression

Support Vector Learning for Ordinal Regression

Ralf Herbrich, Thore Graepel, Klaus Obermayer
ICANN, 1999
================================================

這篇提出了一種regression的問題，簡單來說就是在做classification的時候
不僅僅只用 '+' '-' 來作區隔，'+'的部分可以'+' 很多， '-' 的部分同理
用的是Support Vector Learning 的方法，但效果卻比之前的
Support Vector Classification 跟 Support Vector Regression來得好 

這篇說這種Ordinal Regression的問題可以看成
i. classification & ii. regression 的結合
因為在number及分類有限的情況下就像 i.
如果沒有限制 '+'跟'-' 的上限，就比較像 ii.
問題主要就是在怎樣maximize boundary
然後如何對同一個classifier 作 Rank 來表示

在2. 的部分先把問題定義出來，要怎樣表達這種排序的觀念
以及所要求的目標，其實這個部分就是regression
然後定義要怎樣判斷哪種結果比較好

求解的部分用了一般SVM的解法：
1. 加上cost function : minimize the squared norm
2. Lagrangian Multipliers: QP-problem

實驗的部分跟SVM classification 及SVR來作比較
================================================
優點：
1. 提出一個新的regression方式，不僅如此還將這個問題refer 到其他問題上
增加這個方法的實用性，同時也延伸了問題的解法
2. 跟兩種常用的baseline作比較，增加說服力
3. 用之前的解法(cost function, QP-problem)延伸來求解

缺點：
1. 文章的變數好多，整篇看下來我能理解的部分很有限，閱讀很困難
這有可能是因為我對machine learning的領域不熟，不過明明上學期才剛修了一門...
2. 實驗放的圖說明沒有很清楚，看了很久才懂
3. 參數的調整對SVM的影響很大，paper裡沒對這部分多加著墨就用了一組數字

Nonlinear Dimensionality Reduction by Locally Linear Embedding

Nonlinear Dimensionality Reduction by Locally Linear Embedding


Sam T. Roweis and Lawrence K. Saul
SCIENCE   VOL 290   22 DECEMBER 2000
======================================================

這篇paper提出一個方法可以在做dimension reduction 的時候
還能夠保有原先相近的neighbors

因為做完dimension reduction 原先很遠的point 有可能變到很近
這樣就會造成distance distortion
這篇的方法就是把每個 point 利用neighbor 來表示
主要可以分為以下三個步驟：

1. K nearest neighbor
2. 找出這些neighbor的weight
3. 組成 low dimension embedding vector

1. K nearest neighbor:
這部分在很多相關的paper都有提到
這篇沒有特別詳述
不過這裡要找的是each point 的 exactly K nearest
不是 K-centroid 或是 K nearest-approximate

2. 找出這些neighbor的weight:
K neighbors 用 linear 的方式組起來，總和為1
這些weight求解是least sqaure problem 
paper裡還有提到這樣的解法可以invariant to rotation, scaling, translation

3. 組成 low dimension embedding vector
最後假設要降成 d dimension
列出跟 2. 一樣的embedding cost function
這裡的解法是 NxN eigenvalue problem

paper裡提到以上的步驟裡唯一的變數是 K
一旦K決定了之後，剩下的東西都可以按照optimize 來求解
(d應該是User自己決定要用多少，但對每個point來說  K有可能不同
每個point 要用怎樣的K 才是問題，因此才是唯一的變數)

paper裡也提到很多algorithm
(ex: neural networks, self-organizing maps, latent variable models)
幾乎都有很多要set 的變數
而且也不能保証會 global convergence
這篇paper 提出的LLE 可以保証 global convergence
也就是不用set 變數  求出來的解會一致

實驗的部分 有提供兩個實驗
1. 用sequential face 表情變換 project 到2d 圖上，
然後找出它們的transfer path
這樣就可以証明相似的neighbor 會在附近 不會亂跳

2. 把term word project 到 2d semantic meaning map上
意思相近的term 就會在附近
這個map 的意義比較抽象

======================================================

優點：
1. paper 寫得很簡潔，一看就懂，figure 2 一張圖就可以把全部過程表達清楚
2. 方法很簡單，也很make sense，可以應用的地方很多
3. problem solving 都有對應的解法，解出來的答案會converge
4. 變數幾乎沒有(只要找每個K)，不用一些ad-hoc 的setting
5. 兩個實驗都很有創意，比起一般的perfomance showing 來得有意思

缺點：
1. KNN 那裡要找每個point 的 K neighbor，這裡會很耗時間
2. 第二個實驗的結果好像有些部分不是很好，但paper裡沒解釋