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

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

一、使用多类SVM损失函数

在原始的二分类SVM算法中，模型可看做对Hinge损失函数的L2正则化，即：
$\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(wx_i+b)$yi​(wxi​+b)可视为点$(x_i,y_i)$(xi​,yi​)距分隔面$w,b$w,b的函数距离。
不妨令在$m$m分类问题中，有$m$m个这样的超平面$(w^{(j)},b^{(j)})$(w(j),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)$(xi​,yi​)的真实分类为$k$k，定义如下的多类SVM损失函数：$\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 \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类作为正样本，剩下的所有类作为负样本训练出$m$m个二分类模型。

其缺点显而易见：
1）样本的不均衡。若原始样本中各子类的样本数量相当，但经过1VR之后，每个正样本的数量的远小于负样本（尤其当类别较多时），这会造成严重的样本不均衡，影响二分类模型的判断。
2）会导致分类不清的现象。由于样本的不均衡，可能$m$m个二分类模型结果都倾向于负样本，因此无法得到其最终的分类结果。另一方面，若这$m$m个二分类模型中，有若干个都认为样本属于正样本，那到底最终的结果该判定为哪个？

三、1V1策略

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

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

四、层次SVM策略

本质上是对1V1策略的一种简化，运用“贪婪算法”思想，将$C_m^2$Cm2​个二分类模型构造出一个有向无环图结构，进行逐层对比和筛选，因此也叫DAG SVM算法。
在训练阶段，同样需要训练所有的$C_m^2$Cm2​组子二分类模型。但在预测阶段，通过DAG的方法，能够快速进行预测值的判断。