Learning to rank - from pairwise approach to listwise approach

Learning to rank - from pairwise approach to listwise approach

Summary:
作者使用了一個新的概念來定義ranking的這個問題，本來使用的方法都是用pairwise的方式，例如上次指定的SVR中定義兩個input的feature的差來當作一個classifier的input之類，都是一次處理兩個sample的方式。但是這篇使用了一個使用list的方式來處理，其方法如下。
首先，對應到一個query時，每一個原有的document都會有一個相對關係的答案值(y)，而此時作者定義將一個query和一個document視為一個feature vector x，經過一個ranking function f(.)後，可以得到一個值f(x)，對應到一個query時會列出一堆document而產生一個list of score (x)，而將這個z和原來給定的y透過一個listwise loss function來計算後，就可以算出這個z作ranking的效果了。
而要如何定義這個listwise loss function呢? 作者先定義了一個permutation probability，這一個permutation probability可以計算出一組排列的機率值，由於其定義的方式，使得在score較大要排在較前方，score較小的要排在較後面，如此會得到一個較高的機率值。透過此一function，就可以比較不同排列組合下的好壞之分。但是因為要計算出全部的排列組合數將是一個O(n!)的問題，在實際上是可個不太可行的作法，作者又定義了另外一個function叫作top k probability，只會對排在前面K個順序的object來作計算，而在經過一些計算上的轉換，這個top k probability就可以很有效率的被計算出來。
有了這些function之後，作者就定義listwise loss function為兩個機率分布間的cross entropy，也就是L(y,z)=-ΣPy*log(Pz)。
有了這個listwise loss function，作者便利用neural network作為model，gradient descent當作optimization的方法，來達到learning的效果，並稱此方法為ListNet。有趣的一點是，當每個query對應到的document只有2個的時候，其實這個方法就等同於RankNet了!不過在之後的實驗部分，作者也證明了以listwise的方法去作ranking其實效果會優於pairwise所作出來的效果。

Support vector learning for ordinal regression

Summary:
作者提出了一個distribution independent model來解ordinal regression的問題，而這個方法則是建立在一個針對pair of ranks的loss function上。
其核心的想法如下: 假設給定一組sample( S={(xi,yi)}, i=1,…,l)，也就是共有l個data，每個data對應到一個n-D的feature vector(xi)和一個rank值(yi)。作者想要找到的是一個合適的mapping h，使得empirical risk (Remp(h;S)) 最小化。
透過paper中的定理2，利用一個linear function U(x) = w_T*x可將feature vector投影到一個實數值，且這個實數值一定會落在某個rank投影在此實數空間的區間([Θ(r_i-1), Θ(r_i)])之內。推導至(9)式時，再導入了一個degree of violation constraint(ζ)，而使得margin最大的那個解w，可以轉換成求||w||^2+C*Σζ的解。而這個解w則是透過Lagrangian multiplier轉成了另外一個dual problem(式(10))去解α，之後再透過式(11)經由α回推w之最佳解。此外，透過式(12)還證明了每個rank和rank間的optimal threshold就是兩個rank中距離最近的兩點之中間值。求得了這些rank boundaries，如果有新的data要進來排序時，就可透過U(x)將其對應到一實數值，再看此值落在哪個rank的區間內，就可以得到分類的效果了。
作者提出了一個ordinal regression的問題其實對應到一個unique preference learning problem on pairs of object，如此一來就可將ordinal regression和對pairs of objects的classification problem給連結在一起了。

Critiques:
這篇提出了一個可以利用一小筆的training data，來建立出一個將n維的feature vector投影到一個實數軸上的線性轉換，並盡量保留住原有的分類方式，並透過此一線性轉換來對unseen data也能作ranking的動作，但其實此一方法有一個缺點，如同之前manifold learning相關文獻中所提到的，如果今天data的分布是像三維空間中瑞士捲般的分布，假設瑞士捲越內部的部分其rank越高，但由於本篇採用的是linear function U: X→R，對於非線性分布的資料可能就不會有如同在paper中Fig.1般那麼好的實驗結果。實際上平常在作的許多應用應該都是對一個高維度的非線性分布來作實驗及處理，因此對於非線性分布的ranking問題可能還需要用其他的方法來解決。

Manifold Methods

Nonlinear dimensionality reduction by locally linear embedding

Summary:
作者提出了一個利用locally linear embedding的方式，透過保存local geometry的方式，將data point投影到一個比原來維度D還低的d維度空間上，就可以做到nonlinear dimensionality reduction的效果。
其作法如下:
1. 對於每個data point(Xi)，找出最接近此點的K個nearest point，找出一組係數Wij，使得Σj|Wij| = 1且讓cost function:Σi|Xi - ΣjWijXj |^2極小化。
2. 有了這組linear weights之後，接下來要解如何將D維的Xi投影到d維的Yi上，其cost function為Σi|Yi - ΣjWijYj |^2，可將其視為一個解NxN的eigenvalue problem，就可得到符合cost minimization的解。
作者還用此方法對著臉的照片以及word-document count去作實驗，也證明了此種方法可以將臉的表情變換投影到一個二維的low dimension座標系上的轉換，並且可在轉換路徑上看到表情的逐漸變換；而在文字上作實驗的結果上來看，也可以看出此方法成功的將意義相關的字投影到距離較短的分布上。

Critiques:
這篇提到了利用LLE作nonlinear dimensionality reduction的方法，而最近由於本身研究的關係，看到了一些作spectral clustering的方法，其方法也是類似利用affinity matrix(對graph中每個vertex都有連結或是類似bilateral filter的限制來建立)，再對此一個affinity matrix去求其eigevector的解，而對前幾大的eigenvalue對應到的eigenvector值去作K-means clustering就可做到分群的效果，此一方法也是可以做到manifold dimensionality reduction的效果。此外，在 “Diffusion Maps and Coarse-Graining: A Unified Framework for Dimensionality Reduction, Graph Partitioning, and Data Set Parameterization’’. IEEE Trans. on Pattern Analysis and Machine Intelligence(2006). 中還提到了如何利用diffusion map來作有關分群、降維的動作，有興趣的人可以參考一下。