[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的基礎知識可能會比較容易讀。