SVM算法（八）将SVM推广到多分类问题

SVM算法本质上是基于正、负样本推导得到的二分类模型。通过一些手段，可将其推广到多分类问题中：

一、使用多类SVM损失函数

在原始的二分类SVM算法中，模型可看做对Hinge损失函数的L2正则化，即：

min ⁡ λ N w 2 + ∑ i = 0 N m a x ( 0 , 1 − y i ( w x i + b ) ) \min \frac{\lambda}{N} w^2+\sum_{i=0}^Nmax(0, 1-y_i(wx_i+b)) minNλ​w2+i=0∑N​max(0,1−yi​(wxi​+b))其中的 y i ( w x i + b ) y_i(wx_i+b) yi​(wxi​+b)可视为点 ( x i , y i ) (x_i,y_i) (xi​,yi​)距分隔面 w , b w,b w,b的函数距离。

不妨令在 m m m分类问题中，有 m m m个这样的超平面 ( w ( j ) , b ( j ) ) (w^{(j)},b^{(j)}) (w(j),b(j))，该点距各分隔面的函数距离分别为 s i ( j ) = y i ( w ( j ) x i + b ( j ) ) s_i^{(j)}=y_i(w^{(j)}x_i+b^{(j)}) si(j)​=yi​(w(j)xi​+b(j))。

假设点 ( x i , y i ) (x_i,y_i) (xi​,yi​)的真实分类为 k k k，定义如下的多类SVM损失函数： max ⁡ ( 0 , 1 − ( s i ( k ) − ∑ j = 1 , j ≠ k m s i ( j ) ) ) \max(0,1-(s_i^{(k)}-\sum_{j=1,j\ne k}^ms_i^{(j)})) max(0,1−(si(k)​−j=1,j​=k∑m​si(j)​))其意义为点该距正确分隔面的函数距离，与其余所有函数距离之和的差，必须大于1，才不需惩罚。

因此，完整的基于多类SVM损失函数的L2正则化目标函数可写为： min ⁡ λ N ∑ j = 1 m w j 2 + ∑ i = 1 N max ⁡ ( 0 , 1 − ( s i ( k ) − ∑ j = 1 , j ≠ k m s i ( j ) ) ) \min \frac{\lambda}{N} \sum_{j=1}^mw_j^2+\sum_{i=1}^N\max(0,1-(s_i^{(k)}-\sum_{j=1,j\ne k}^ms_i^{(j)})) minNλ​j=1∑m​wj2​+i=1∑N​max(0,1−(si(k)​−j=1,j​=k∑m​si(j)​))

二、1VR策略

这是个经典的从二分类模型推广到多分类模型的策略，即每次选取第 j j j类作为正样本，剩下的所有类作为负样本训练出 m m m个二分类模型。

其缺点显而易见：

1）样本的不均衡。若原始样本中各子类的样本数量相当，但经过1VR之后，每个正样本的数量的远小于负样本（尤其当类别较多时），这会造成严重的样本不均衡，影响二分类模型的判断。

2）会导致分类不清的现象。由于样本的不均衡，可能 m m m个二分类模型结果都倾向于负样本，因此无法得到其最终的分类结果。另一方面，若这 m m m个二分类模型中，有若干个都认为样本属于正样本，那到底最终的结果该判定为哪个？

三、1V1策略

构造 C m 2 C_m^2 Cm2​个二分类模型，但每次只判断某两个类别。然后选择判断类别次数最多或概率最大的类别作为样本的最终类别。

这种策略有效的避免了样本不均衡的问题，而且不会产生分类不清楚的结果。但其缺点是子分类器数量较多，尤其在类别较多时，运算量很大，当然可以通过并行运算的方式改善速度。

四、层次SVM策略

本质上是对1V1策略的一种简化，运用“贪婪算法”思想，将 C m 2 C_m^2 Cm2​个二分类模型构造出一个有向无环图结构，进行逐层对比和筛选，因此也叫DAG SVM算法。

在训练阶段，同样需要训练所有的 C m 2 C_m^2 Cm2​组子二分类模型。但在预测阶段，通过DAG的方法，能够快速进行预测值的判断。