[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。

[aMMAI] Paper Summary: Support Vector Learning for Ordinal Regression

Title: Support Vector Learning for Ordinal Regression

Author: Ralf Herbrich, Thore Graepel, Klaus Obermayer

Publication: ICANN, 1999

這篇paper提出一個解決ordinal regression的方法。

Regression有兩種形式:

(i)一種是分兩類，通常是用”+”，”-“或是”0”，”1”來分類，如果套在retrieval上，可以表示文件是相關還是不相關。偏向classification。

(ii)另一種除了分類外，還有看他的比重，分在”+”裡面後還要看正多少，分在負裡面後還要看負多少，依此作排序。這稱為ordinal regression。

技術的部分主要兩部分:

1. A Risk Formulation for Ordinal Regression

這邊主要用到的方式有Empirical Risk Minimization(ERM)、Pair-wise Training。

給定一個set S = {(x,y)}，x: feature vector, y: rank。

從S中要學出一個h，給定x可以預測出相對應的y，h(x)->y。

以Pair-wise的方式來比(x1,y1)、(x2,y2)這邊利用ERM來達到最佳化。

為了讓訓練更有效，他將原本的S轉成S’形式，S’ = {(x1,x2),diff(y1,y2)}

一樣利用ERM來找出Risk Formulation

2. SVM for Ordinal Regression

從圖來看，他會將步驟二rank出來的每個sample透過一個U做降維，並且在降維過程中還能保留原有的rank條件。

θ(r)就是高維中的平面，可以將不同rank間的點切開，類似在做分類的問題，利用SVM去做分類。為了讓切開的平面能達到margin最大，導入了一個非負的值，利用Lagrange multiplier、QP-problem來解。

最後這篇paper與一些方式(multi-class SVM、SV regression)做比較，以及提出應用在IR上的效果。

結論:

這篇paper提出的方法結合了classification與regression的問題。

將高維降到剩純量還可以保有原本的rank，還蠻難想像的。

裡面有用到很多專有名詞，有machine learning的基礎知識可能會比較容易讀。

[aMMAI] Paper Summary: Nonlinear dimensionality reduction by locally linear embedding

Title: Nonlinear dimensionality reduction by locally linear embedding

Author: Roweis & Saul

Publication:  Science, 2000

在描述真實世界中的物件時，通常都是使用高維的向量來表示。

維度越高，處理起來會有很多問題，因此就會想要做降維。

在原本物件的結構上，比較相近的點會有一些關聯性(例如:影像中相鄰的像素不會差太多)。

這邊paper提出一個unsupervised learning algorithm的非線性降維方法，稱做locally linear embedding (LLE)，降維的過程中，空間上每一點保留與原本鄰近點的相關性，這些鄰近點不會因為位移或旋轉而改變，如下圖所示。

圖B中所表示的是在三維空間中的點，我們希望將他降維乘如圖A所表示的二維空間形式，其中圖上顏色越相近的表示他們是越相近的點。

LLE的降維方式不同於PCA或是傳統的MDS，會在降維過程中將原本相近的點map到不同的平面上，如下圖，有些顏色不相似的點混在一起。

LLE降維過程主要有三個步驟，如下圖所示。

假設空間中有N個點，每個點都有D個維度，用向量X_i表示。

Step 1:

先找出原本空間中每個點的鄰居。

Step 2:

藉由該點四周圍的鄰居重建出這一點。

重建的過程中，需要最小化cost function (1)。

X_i表示原本的點，總合W_ijX_j表示由j個點重建出來的X_i。

這個cost function需要滿足兩個限制:

1. 每個點只有用那一點的鄰居來重建，如果W_ij等於零，表示j點不是i點的鄰居。

2. Weight matrix總和必須等於零。

Step 3:

要將原本高維的向量X對應到低維向量Y中，首先要先建立出Y的向量空間。

我們利用前面的weight W來建立出Y的向量空間，藉由最小化cost function (2)來達到。

由於weight已經固定，利用解eigenvalue，取eigenvalue最小的d個eignevector做為Y向量空間的orthogonal coordinates。

LLE的優點是，只需要評估K(鄰居數量)這個參數，沒有很多參數須要做調整。

LLE可以應用在很多方面上，paper中舉了人臉與文字語意的例子，下面是該例子的例圖

PCA與LLE降維步驟這兩張圖來自這份投影片:

http://slp.csie.ntnu.edu.tw/ppt/20100509_ytlo_LLE.pptx