Multiclass Classification – SVM

by allenlu2007

前文主要都是 focus on binary classification, 因為簡單。現實的問題大多是 multi-class classification, 例如 MNIST, ImageNet, etc.

Rifkin from MIT 整理了一份 multi-class classification report 相當值得參考。

另外林智仁 “A Comparison of Methods for Multi-class SVM” 整理比較非常清晰。

Multi-class 可視為 binary classification 的延伸,基本上可分為兩類:

(1) 直接推導 multi-class classifier.  Binary classifier 變成 special case.  例如 softmax vs. logistic regression(softmax 算嗎? 應該比較像 OVA?).  台大林智仁教授稱為 all-together classifier.

Pro: 一步到位解決 multi-class problem

Con: 通常複雜度遠超過 binary classification.  通常 training and testing 的 procedure 和時間都更久。大多實測的結果都比其他 ad hoc (主要是 multiple binary classification) 方式差。

(2) 使用 multiple binary classifier 造出一個 mega multi-class classifier.  也就是 divide-and-conqure 的概念。乍看之下用了很多的 binary classifier.  不過因為 binary classifier 可以很有效率,因此多個 binary classifier 效果也不錯。這也分為兩類 “One-versus-One” (OVO) 和 “One-versus-All” (OVA) schemes.

Pro: 簡單易於 implement.  實測速度也不錯。

Con: OVO 或 OVA 畢竟是 ad hoc 的解法。理論上可以造出 dataset (training and testing) 用 all-together classifier 解的好,但 OVO/OVA 解的差。但實務上似乎未出現。 (附圖說明)


什麼是或不是 Multi-class Classification

Multi-class classification:  每一個 training/test point 只歸於 N class 中的一個 class.  例如 MNIST.  適合 all-together classifier.

非 Multi-class classification: 每一個 training/test point 可歸於 N class 中多個 class.  例如 ImageNet.  帆船屬於船也屬於交通工具。適合 OVO or OVA classifiers.


 

Multi-class Classification Formulation

A first idea based on pdf, pi(x)

NewImage

實務上不可能知道真正 pdf, 最多只能估計的 parameterized pdf (e.g. Gaussian, Logistic distribution).  

以 binary classification 而言,我們定義 classification function f(x) 可以相當成功的分開兩個 group (y=0 and 1) 而不需要知道 underlining pdf, 例如 SVM, RLSC (Regularized Least Square Classification)。另一類classification 則是根據假設的 parameterized pdf (Gaussian or Logistic Regression).

是否能用同樣的方法在multi-class classification 問題?

 

OVA: One-vs-All Classification

選一種 binary classifier (e.g.  Logistic Regression, SVM, RLSC – Regularized Least-Squares Classification),造 N 個彼此無關的 binary classifiers.  

重點是對第 i 個 binary classifier,  positive datapoints 就是 class i 的 data; negative datapoints 就是非 class i 的 data.  用這種方法可以 train 出第 i 個 binary classifier.  同理可以 train 出 N 個 binary classifiers.  如下圖。

NewImage

 

我們把這些 binary classifiers 稱為 fi(x).  對於 test or predict x, 就會是:

 NewImage

上式有兩種解讀:  

(1) fi(x) 是 hard decision: fi(x)=1 => x in class i;  fi(x)=0 => x not in class i  

(2) fi(x) 是 soft decision:  fi(x)=score 或是 -1 * loss

如果是 hard decision, 可能會發生多個 1 的情況,代表 x 屬於多個 classes; 或是都是 0, 代表無法分類。這在一般定義的 multi-class classification 屬於 invalid 情形。

如果是 soft decision, 就是用最後的 score 來決定。例如 softmax 最後針對每一個 wi 都有 score, 只是再 normalize (partition function).  同樣也可以解決 multiple classes 問題,就用機率表示前三(or 前k)類。常見於 ImageNet demo.

 

OVO: One-vs-One Classification

同樣用 binary classifier, 但在 OVO 是造 N(N-1) 個 classifiers.  針對每一個 (i, j) class pair 都有一個 fij classifier. (為什麼針對 pair?  因為 binary classifier 只能處理 2 classes).  在 train fij 時,忽略其他所有非 class i or class j 的 datapoint, 如下圖。fij = -1 * fji 因此只需要 train N(N-1)/2 classifiers.

NewImage

在 testing or predict 時,計算:

NewImage

注意 fij 同樣可以是 hard decision or soft decision.

(1) fij(x) 是 hard decision:  fij(x)=1  => x in class i instead of j;  fij(x)=0 => x in class j instead of i

     最佳狀況是 sum(fij(x)) = N => 代表 x 必然 in class i.  其他所有的分數都會小於 N since fji = -1.

(2) fij(x) 是 soft decision: fij(x)=score 或是 -1 * loss

 

OVA or OVO or all-together?

OVO 需要 N(N-1)/2 binary classifier, 不過 training 的時間並不會太長 (因為每個 pair 都只 take class i and class j data).  Testing 時的準確度應該也最好。在 N 不大的情況下 (e.g. MNIST), 似乎是首選。如果 N 很大 (> 100?) 可能是問題。

OVA 需要 N binary classifiers. 每次 training 需要完整的 data (class i and 非 class i).  可能適合 N 很大的情況。

All-together 除了一些 known classifiers (e.g. softmax) 外,可能在 training and testing 都更複雜。

 

All Together or Single Machine

第一個 single machine approach by Wenton and Watkins, Vapnik 如下 (primal)

NewImage

 

之後 Crammer and Singer 改成 only one slack variable per data point.

NewImage

可以得到 dual problem 以及 kernel.  以及 dual decomposition algorithm.

 

林智仁的 paper 結果如下。(same as Wenton and Watkins, Vapnik?)

NewImage

其實這和 OVA 的 decision function 是一樣的。k 個 decision boundaries (w1, w2, … wk)

Dual problem 如下:

NewImage 

 

在 binary classification 時解 (5) 可以用很用效率的算法 (e.g. MSO).   但在 multi-classification 問題時則無法divide-and-conquer.  所以效率並不好,雖然可以用一些 tricks to improve. 比 binary SVM 複雜很多。

 

Cramer and Singer 的方法如下:

NewImage

(4) and (16) 最主要的差別是 slack variables 的數量。(4) 有 kl 個 slack variables.  (16) 只有 k 個 slack variables.    ei 主要是簡化 constraints,  在 ei=0 代表 slack variable >= 0

NewImageNewImage 

同樣也類似 OVA.  

NewImage

(17) 是一個 convex optimization problem.  另外可以用有效率的算法來解。這也是 Cramer and Singer 主要的貢獻。


 

 

Advertisements