前面七篇文章(從間隔最大化，支持向量開始)系統地推導了適用於二類分類(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類之間的決策邊界。

成對分類方法，one-against-one

對於第 i 類和第 j 類數據，訓練一個binary SVM即求解二次規劃問題：

min_{mathbf w^{ij}, b^{ij}, xi^{ij}}{frac{1}{2} {(mathbf w^{ij})^T mathbf w^{ij}}+Csum_{t}{xi_t^{ij}}} ag{I}\ egin{align} s.t. (mathbf w^{ij})^Tphi(mathbf x_t) +b^{ij}&geq 1 - xi_t^{ij}, { m if} y_t=i\ (mathbf w^{ij})^Tphi(mathbf x_t) +b^{ij}&leq -1 + xi_t^{ij}, { m if} y_t=j\ xi_t^{ij} &geq 0end{align}

其中，上標表示是 i 類和 j 類之間binary SVM的參數；下標 t 表示 i 類和 j 類的並集中樣本的索引； phi 表示輸入空間到特徵空間的非線性映射。

(當然，求解的是 left( m I ight) 的對偶問題。)

索引 i,jin left{ 1,ldots,M ight}, i<j ，一共需訓練 C_M^2=frac{1}{2}M(M-1) 個binary SVMs。平均每個類包含 N/M 個樣本，所以平均每個對偶問題包含 2N/M 個變數。

第 i 類和第 j 類之間binary SVM的決策函數：

y_{new}^{ij} = { m sign}left[ (mathbf w^{ij})^T phi left( mathbf x ight) +b^{ij} ight]= { m sign}left[ sum_{support\vectors}{y_talpha_t^{ij}k(mathbf x_t,mathbf x_{new})+b^{ij}} ight]\ ag{1}

(1)式用於判斷數據是屬於 i 類還是 j 類。

對於新數據，採用voting strategy(投票策略)進行分類：

  • 每個binary SVM根據其決策函數對新數據 mathbf x_{new} 有一個預測(投票)，以 i 類和 j 類之間的binary SVM為例，若對 mathbf x_{new} 的預測為 i 類，則 i 類得票加1；否則 j 類得票加1；
  • 最終得票最多的類別就是對 mathbf x_{new} 的預測(Max Wins, [3])；
  • 若出現平票的情況，(雖然可能不是一個好方法)，簡單地選擇索引較小的那個類別作為對 mathbf x_{new} 的分類。

圖(b)所示為根據上述投票策略畫出的決策邊界(文獻[1])。若新數據位於橙色區域，則其對1類的得票為3票，會被預測為1類；同理，位於藍色和紅色區域的數據會分別被預測為2類和3類。至於中心灰色區域，對三個類的得票均為1票。

11.2 一類對余類，one-against-all，one-against-the-rest

另外一種基於binary SVM的方法是一類對余類方法(文獻[6])，也叫one-against-all(文獻[3])，one-against-the-rest(文獻[4])。

這種方法也好理解：對於每一個類，將其作為+1類，而其餘 M-1 個類的所有樣本作為-1類，構造一個binary SVM。如下圖(a)所示，對於黃點所示的1類，將2類和3類都當成-1類，構造binary SVM，其決策邊界為 d_1 ；對於藍點所示的2類，則將1類和3類都當成-1類，構造binary SVM，其決策邊界為 d_2 ；類似地得到 d_3 。

一類對余類，one-against-all

一般地，構造一個binary SVM將第 i 類與其餘 M-1 類分開，即求解二次規劃問題：

min_{mathbf w^{i}, b^{i}, xi^{i}}{frac{1}{2} {(mathbf w^{i})^T mathbf w^{i}}+Csum_{t=1}^{N}{xi_t^{i}}}\ egin{align} s.t. (mathbf w^{i})^Tphi(mathbf x_t) +b^{i}&geq 1 - xi_t^{i}, { m if} y_t=i\ (mathbf w^{i})^Tphi(mathbf x_t) +b^{i}&leq -1 + xi_t^{i}, { m if} y_t e i\ xi_t^{i} &geq 0end{align}\ ag{II}

其中，下標 t 表示樣本的索引；上標 iin left{ 1,ldots,M ight} ，一共需訓練 M 個binary SVMs，求解 M 個包含 N 個變數的二次規劃問題。

為避免平票，通常去掉決策函數(1)中的符號函數(signum function)，第 i 類的決策函數採用：

d_{new}^{i} = (mathbf w^{i})^T phi left( mathbf x ight) +b^{i}= sum_{support\vectors}{y_talpha_t^{i}k(mathbf x_t,mathbf x_{new})+b^{i}}\ ag{2}

(2)式可看作新數據 mathbf x_{new} 到第 i 條決策邊界的帶符號的函數間隔『。因為在問題 left( m II ight) 中我們把第 i 類當成+1類，所以如果 mathbf x_{new} 屬於第 i 類，那麼一般來說(2)式應該是正的。

對於 mathbf x_{new} ， M 個決策函數一共有 M 個輸出。我們選擇使(2)式最大的類 i 作為對 mathbf x_{new} 的預測(winner-takes-all, [1])，也就是說，採用如下的決策函數來對 mathbf x_{new} 進行分類：

f(mathbf x) = mathop{argmax}_{iin left{ 1,ldots,M ight}}left[ (mathbf w^{i})^T phi left( mathbf x ight) +b^{i} ight] =mathop{argmax}_{iin left{ 1,ldots,M ight}}left[ sum_{support\vectors}{y_talpha_t^{i}k(mathbf x_t,mathbf x_{new})+b^{i}} ight]

圖(b)所示為相應的決策邊界(文獻[1])。若 mathbf x_{new} 位於橙色區域，則 d_{new}^1 最大， mathbf x_{new} 會被預測為1類；同理，位於藍色區域 d_{new}^2 最大，會被預測為2類；位於紅色區域 d_{new}^3 最大，會被預測為3類。

<不平衡數據，unbalanced data(文獻[2])>

在某些情況下，不同類別的樣本數量是不平衡的。如採用一類對余類方法時，-1類樣本的數量可能比+1類樣本多很多。

個人理解：這會使得問題 left( m II ight) 目標函數中的懲罰項主要由-1類樣本的error組成，模型偏向於-1類。

這種情況可以通過對兩類數據設置不同的懲罰參數(penalty parameter)來處理，優化問題變為：

min_{mathbf w, b, xi}{frac{1}{2} {mathbf w^T mathbf w}+C^+sum_{y_i=1}{xi_i}+C^-sum_{y_i=-1}{xi_i}}\ egin{align} s.t. y_ileft[ mathbf w^Tphi(mathbf x_t) +b ight] &geq 1 - xi_i, i=1,ldots,N\ xi_i &geq 0, i=1,ldots,Nend{align}

其中， C^+, C^- 分別表示+1類和-1類的懲罰參數。對於樣本數更少的+1類，採用更大的懲罰參數 C^+ 。

相應的對偶問題為：

egin{align} &min_{mathbf alpha}{frac{1}{2}mathbf{alpha^T Q alpha} -mathbf{1^Talpha}}\ &s.t. 0 leq mathbf alpha_i leq C^+, { m if} y_i=1\ & 0 leq mathbf alpha_i leq C^-, { m if} y_i=-1\ & mathbf {y^T alpha} = 0 \ end{align}

更一般地，可以對每個樣本都設置一個懲罰參數 C_i 。

<參數選擇，parameter selection>

各個binary SVM可以通過交叉驗證(cross-validation)來選擇各自的最優參數(懲罰參數和核參數)；也可對所有binary SVM採用相同的參數。

文獻[7]Section 8比較了這兩種方法在one-against-one的 u- m SVM 上的應用。文獻[8]也有比較研究。這裡就不做介紹了。

11.3 只需求解一個優化問題的多類方法

對於多類分類SVM，還有一種只需求解一個優化問題的方法(文獻[4-5])。這種方法類似於one-against-all，構造 M 個二類的決策函數，其中第 m 個函數 mathbf w_m^Tphi(mathbf x_t) +b_m 將第 m 類和其餘類分開。形成的優化問題如下：

egin{align} &min_{mathbf w, b, xi}{frac{1}{2} sum_{m=1}^{M}{mathbf w_m^T mathbf w_m}+Csum_{t=1}^{N}{sum_{m e y_t}{xi_t^{m}}}}\ s.t. &mathbf w_{y_t}^Tphi(mathbf x_t) +b_{y_t}geq mathbf w_m^Tphi(mathbf x_t) +b_m+2 - xi_t^{m}, ag{3}\ &xi_t^{m} geq 0, t=1,ldots,N, min left{ 1,ldots,M ight}ackslash y_t end{align}\ ag{III}

解這個優化問題得到全部 M 個決策函數。

個人理解：不等式約束(3)表示第 y_t 類數據到第 y_t 個邊界的函數間隔應該比到其餘 M-1 個邊界都要遠。

決策函數為：

f(mathbf x) = mathop{argmax}_{min left{ 1,ldots,M ight}}left[ mathbf w_m^T phi (mathbf x)+b_m ight]

文獻[4-5]推導了問題 left( m III ight) 的對偶問題。

文獻[3]比較了幾種多類分類SVM的方法，並表明one-against-one適合實際應用。

關於支持向量機的學習暫時先到這裡吧。至於 u- m SVM ，sci-kit learn(sklearn)庫的svm模塊等，以後有機會再繼續學習。

參考文獻

[1] Krebel, U. H.-G. 1998. Pairwise classification and support vector machines. In Advances in Kernel Methods – Support Vector Learning, B. Scholkopf, C. J. C. Burges, and A. J. Smola, Eds., MIT Press, Cambridge, MA, 255-268.

[2] C. C. Chang and C. J. Lin. 2001. LIBSVM: a library for support vector machines. csie. ntu.edu.tw/cjlin/libsvm.

[3] C. W. Hsu and C. J. Lin. 2002. A comparison of methods for multi-class support vector machines. IEEE Trans. Neural Netw. 13, 2, 415-425.

[4] J. Weston and C. Watkins. 1998. Multi-class support vector machines. Technical Report CSD-TR-98-04, Department of Computer Science, Royal Holloway, University of London.

[5] J. Weston and C. Watkins. Support vector machines for multi-class pattern recognition. In Proceedings of the Seventh European Symposium on Artificial Neural Networks, April 1999.

[6] 鄧乃揚，田英傑，數據挖掘中的新方法——支持向量機，科學出版社，北京，2004年。

[7] P. H. Chen, C. J. Lin, and B. Scholkopf. 2005. A tutorial on u -support vector machines. Appl. Stochas. Models Bus. Indust. 21, 111-136.

[8] W. C. Kao, K. M. Chung, C. L. Sun, and C. J. Lin. 2004. Decomposition methods for linear support vector machines. Neural Computation, 16:1689-1704.

推薦閱讀：

相关文章