支持向量機原理詳解(八): 多類分類SVM

06-10

前面七篇文章(從間隔最大化，支持向量開始)系統地推導了適用於二類分類(binary/two-class classification)問題的SVM。在此基礎上可以將SVM推廣到多類分類問題。在理解二類分類SVM後，多類分類SVM也不難理解。

本文對多類分類SVM做簡單介紹，內容如下：

多類分類問題
成對分類方法(one-against-one， pairwise classification)
一類對余類(one-against-all，one-against-the-rest)
只需求解一個優化問題的多類方法

11. 多類分類SVM(multi-class SVM)

11.0 多類分類問題

前文在數據集只有兩類 $left( y_nin left{ -1, 1 ight} ight)$ 的情況下推導了二類分類SVM(為方便起見，以下稱binary SVM)。現在介紹如何將SVM推廣到數據有 $M$ 個類的分類問題。

多類分類問題描述如下(參考文獻[6])：

給定含 $N$ 個樣本的訓練集 $X=left{ (mathbf x_1, y_1),ldots, (mathbf x_N, y_N) ight}$ ，其中 $K$ 維特徵向量 $mathbf x_nin mathbf R^K$ ，類標籤 $y_nin left{ 1, 2,ldots, M ight}$ ， $n=1, ldots, N$ 。訓練集數據共 $M$ 個類。任務是找到決策函數 $y=f(mathbf x)$ (或者說一個規則)用於預測新數據的類別。

11.1 成對分類方法(one-against-one，pairwise classification)

成對分類方法(文獻[6])是基於binary SVM的，也叫one-against-one(文獻[2-3])，pairwise classification(文獻[1]引入)。one-against-one適合實際應用(文獻[3])，也是LIBSVM庫採用的方法(文獻[2])。

設訓練集數據共 $M$ 個類，one-against-one方法是在每兩個類之間都構造一個binary SVM。以下圖(a)為例，共三類(二維)數據，虛線 $d_{12}$ 表示1類和2類數據之間的binary SVM的決策邊界， $d_{13}$ 表示1類和3類之間的決策邊界， $d_{23}$ 則表示2類和3類之間的決策邊界。