前面七篇文章(从间隔最大化，支持向量开始)系统地推导了适用于二类分类(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.

推荐阅读：

相关文章