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裡沒解釋

Latent Dirichlet Allocation

Latent Dirichlet Allocation

David M. Blei
Andrew Y. Ng
Michael I. Jordan (這個人的名字頗出名)
Journal of Machine Learning Research 3 (2003) 993-1022
===============================================================

這篇說的LDA跟上一篇pLSA的應用面其實很相近
LDA是想要找出document裡面 term所對應到的 class
所以一個document裡面會包含各種class 的 term

可能是因為journal的關係，這篇在比較的方面寫得相當地詳細
跟最原本的tf-idf然後再跟pLSA作了比較，當然也列出了它們的一些性質及缺點

LSI 是因為 dimension reduction 而出現的觀念
pLSA 就是 improve LSI 的結果
但是pLSA也有下列兩個缺點：
a. corpus增加的時候變數也會等比例增加，會造成overfitting
b. training set 以外的就會沒辦法處理 (有點類似沒有background model)
所以這篇提出的LDA 算是pLSA的改進，用的方法當然也有不同
建model的條件就是不只對該doc的機率要高，對同類的doc也要高

LDA的主要觀念就是每個document可能會含有很多不同的latent class
而每種class的機率就是靠著每個term的機率來算
所以用的跟pLSA一樣是bayessian probability然後一樣用EM 來找出比較好的參數
然後LDA有個假設是說每個term或每個topic 彼此的次序是independent (exchangable)
這跟最原本的language model 可以說是完全不同

中間就說明了
uni-gram -> mixture of uni-gram -> pLSI -> LDA 這些model的演進

實驗的部分當然就做了上述四種方法的比較
不論在perplexity及Accuracy ，LDA 的表現都比其他三者要好

結論的部分提到說 LDA 一樣有 dimension reduction的效果
且比起pLSA 更多了modularity 和 extensibility
===============================================================

優點：
1. 這篇的比較相當完善，每個方法都有說明清楚
2. 數學推導結果
3. 對提出的假設(exchangable) 有說明原因

缺點：
1. 實驗在做accuracy 的時候就沒有用上述的其他方法作比較，而用word feature當baseline
2. 在training 數量很大的時候 跟word feature相比 improve 其實沒有說的這麼凸出

Probabilistic Latent Semantic Indexing

Probabilistic Latent Semantic Indexing

Thomas Hofmann
International Computer Science Institute, Berkeley, CA &
EECS Department, CS Division, UC Berkeley
hofmann@cs.b   erkeley.edu

CVPR' 1999
=======================================================

這個方法是用在text search 的 indexing system上

傳統的text search作法就是利用literal term matching
也就是每個字去比對
但這樣的缺點是因為text 的表示很有可能not precise
e.g. query term 出現在很多class 裡
因此就有人提出了LSA的概念
想要找出latent term 再用這些term去search
這篇paper提出的方法就是去improve LSA   兩者主要的差異在於：
a. short vector   V.S   long vector
b. TEM   V.S   SVD

tempered EM 跟原本EM的方法只差在多乘上一個weight
這樣在做EM converge的時候可以調整去避免 overfitting

後面search的方法也是用 vector-space model(VSM)
1. transformation function:  TF
2. term weighting scheme: IDF
3. similarity measure: cosine sim
簡單地說就是用tf-idf 然後算cosine similarity，這些現在來看就是標準程序

實驗的部分
列出不同class 找出的 latent term 和它們彼此的關係
比較傳統(tf-idf)、LSI、pLSI 三者的precision and recall
從結果來看  pLSI 在各dataset的表現都勝過 LSI
=======================================================

優點：
1. latent term 的觀念 (不過最早提出的不是這篇)
2. 詳細的數學式推導
3. result 跟之前的state-of-art作比較，一目了然

缺點：
1. 標準的踩在巨人肩膀上，其實觀念就是LSA，不過找到更好的方法去improve
2. 找出的latent term 好像沒有考慮出現在class的機率(出現在越少class越好)
3. 同一class的latent term 應該要越diverse越好
(2跟3的觀念在image search 裡就常常被強調，不過這篇好像都沒考慮)

Lost in Binarization: Query-Adaptive Ranking for Similar Image Search with Compact Codes

Lost in Binarization: Query-Adaptive Ranking for Similar
Image Search with Compact Codes






ICMR'2011
Yu-Gang Jiang  , Jun Wang  , Shih-Fu Chang
Columbia University, New York, NY 10027, USA
IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA
========================================================

這篇paper講的是在large-scale image search上的improve
他在state-of-art 的 scheme上  用hamming distance的時候可以作re-ranking

這篇就是標準的踩在巨人肩膀上
甚至在hamming distance re-ranking的概念都是別人提出來的
不過裡面的related work 寫得很清楚
把過程及一些方法的優缺點都寫出來了

目前很多paper提出的state-of-art作法
1. 取BoW(Bag-of-words) feature
    用SIFT 再quantize 成 visual words
2. binary embedding (hashing)
3. reranking (Hamming distance)
   這篇paper主要的improve是在這裡，他提出一種reranking 是可以根據query
   給不同的weight 去作 reranking

在 related work 有作 2. 的比較，目前比較efficient image search有三種方法
a. inverted index:
    缺點是 image 不像 text 在 query的時候會用關鍵字，image的 word很多
    所以return 的 candidate images 也就會很多
b. tree-based index:
   目前大多是用KD-tree，但對high dimension的效果不好
c. binary embedding:
   很多人用Locality Sensitive Hashing(LSH)
   但在hamming distance相同下有很多不同的意義
   這篇主要是用這個方法然後improve reranking的結果
   最近也有很多paper在研究如何reranking
   但這篇最大的不同點是會因query改變weight

方法在概念上是在query 後，先找出一些比較相似的class
然後利用這些class算出hamming code 每個dimension 的weight
再用這個weight 去 內積原本的hamming distance
最後用這個score 去作re-ranking

這篇 實驗的部分就是show出用提出的方法 MAP可以提升多少
========================================================

優點：
1. 對於 state-of-art 各步驟的一些方法，在related work裡有作說明及比較
2. Adaptive weights 用數學式去推導，而且可以用 quadratic programming來算
3. improve the state-of-art

缺點：
1. 方法建立在state-of-art上，改進某一個部分，而且想法別人也提出過
這部分的創意點比較不夠
2. 用adaptive weight 變成要有一定數量的class，但在實驗裡這部分沒有詳細討論
不過在future work裡有說之後可以improve # class
3. 我覺得這個方法應該可以考慮 diversity 的問題，但paper對這部分沒有多作著墨

Aggregating local descriptors into a compact image representation

Aggregating local descriptors into a compact image representation

Herv´e J´egou INRIA Rennes
Matthijs Douze INRIA Grenoble
Cordelia Schmid INRIA Grenoble
Patrick P´erez Technicolor
========================================================

這篇paper主要的目的是要做一個large-scale image search
著力點在三方面：
1. accuracy
2. efficiency
3. memory usage
所以這個系統不但要結果好，同時在空間及時間運用上都要有效率

paper裡提到很多篇related work
上面所提到的三個目的在很多paper 裡都有研究
但通常都是只針對其中的某一項
這篇的作者比較像是集大成然後再統整
所以方法也是用之前別人用過的，然後再加以修改
步驟跟目的也有說明很清楚，主要可以分為三個
1. aggregate local descriptors
2. dimensionality reduction
3. indexing system
以下將對每項作說明：

1. aggregate local descriptors:
這步就是取feature然後作fusion，最後會形成一個high-dimension vector
這裡用的方法是BOF跟Fisher kernel，然後再aggregate成SIFT descriptors
作者把最後的結果vector 稱為VLAD
再用 K-means 作quantization 然後把每個word跟centroid difference 存起來

2. dimensionality reduction:
在1. 作完之後，每張image都有一個high dimension vector可以代表
這步的目的就是要做降維，用兩個方法 a. projection(PCA), b. quantization
這裡找 nearest neighbor用的方法是 product quantization-based approximate search method
先找出重要的 centroids 再把之前的結果 quantize 成這些 codes
再用PCA去找出最具代表性的dimensions
這裡在paper裡用比較多的數學來說明他們的結果可以work及運算方法

3. indexing system:
有了2. 的codes後，就可以把每張image都用這些codes來表示
然後用IR的方法去作inverted indexing
利用這樣去加速搜尋的結果，而不能用pair-wise comparison
paper裡最後用20 bytes 來代表一張圖

實驗的部分
作者有作了一些實驗去找出適合的 K 和 D 的值
然後去算出他的方法mAP
接著再跟 miniBOF(state-of-art)方法比較
他提出的方法用的byte較少，mAP也比較高
最後再用large-scale data 上去算 mAP 效果也能夠維持
有提到用inverted file ADC 只要 46 ms 就可以，等於是可以real-time
========================================================

這篇paper的條理很清楚
一步一步依序寫下來，用的字也很淺顯易懂
大概是對image search 比較有概念，所以都能理解他做這些步驟的目的跟想法

優點：
1. 這篇算是集大成，求好、求快、求效率，全部都有考慮到
2. 方法論述很清楚，都會說明這個步驟的目的，而不是單純寫作法
3. 相關的related work 優缺點都有提出，並且說明哪個方法為什麼不用，哪裡要改進
4. 實驗有提供state-of-art的結果，更加有說服力

缺點：
1. K 跟 D 的值像是用trial-and-error的方法去找，沒有比較有說服力的決定方法
但這個部分是trade-off 因為 K 跟 D 愈大，搜尋花的時間就愈高
2. 最後用的real-time方法 IVFADC or ADC 對 mAP的犧牲都很大，從圖上可以看到
跟baseline(BOF)至少下降0.1  等於是變差至少30%，但paper裡對這個部分說明沒有很清楚
只有強調花的時間很少
3. state-of-art 只是針對accuracy，並不是跟large-scale system的state-of-art做比較(除非沒有)
而且這篇的方法是去improve state-of-art 因此在不考慮時間效率下，應該就是要比較好