对SVM多分类问题的一点说明

众所周知，最原始的支持向量机是针对二分类问题的。怎样将原始的支持向量机有效地扩展到多分类问题是在进行研究的问题。对于SVM多分类问题，目前主要有两种思路，一个是构造多个二分类器并组合起来解决多分类问题，另一个是在一个最优化问题中包含所有分类器的参数，一次性解出所有分类器。这种想法看似简单，但由于需要计算复杂度将对于二分类问题实在太大，所以并没有什么优势。

很多博主将第二种思路成为间接法，顾名思义，第一种思路就是直接法了。博主们往往用两三句就把直接法给糊弄过去了，主要是说它计算太复杂，太慢；然后就长篇累牍的对各种间接法的奇技淫巧进行介绍。其实，从理论的创新性和优美性而言，直接法是很值得我们去探究的。作为一只小小小菜鸡的我，就来个抛砖引🐟吧！

这篇文章我主要试图解释直接法的目标函数及约束条件的来源，主要的参考文献是J. Weston, C. Watkins.的经典论文Multi-class Support Vector Machines。多分类问题的具体的目标函数及约束条件如下：
图片说明
其中的 $k$ 代表样本一共有 $k$ 类，而 $l$ 表示样本个数。现在的问题是(6)(7)式是怎么推导出来的呢？论文并没有给出解释，哎，想想李航老师的统计学习方法，说得多么详细，多么清楚呀！那就自立更生吧！下面我们就集中精力把这件事给尽力弄明白，加油！

首先，我们要明白的是直接法构造的 $k$ 个分类器，本质上走得就是间接法中的"one-aginst-all"的路子。既然这样，让我们先来复习一下"one-aginst-all"的目标函数和约束条件，如下：
图片说明
根据上面的式子可知，对第 $i$ 个分类器而言，如果样本 $X_j = (x_j, y_j)$ 的类别 $y_j$ 是 $i$ ,则判别函数在 $X_j$ 的取值为正，否则为负。这里的关键点是，取出一个特定的样本，然后用众多分类器中的一个作用到该样本，看能得出怎样的目标函数和约束条件。根据这个思路，我们开始尝试解释上面的(6)(7)式的来源。

在 $l$ 个样本中我们取出样本 $X_i = (x_i, y_i)$ ，其中 $i=1,\dots,l$ 。同时，我们将所有的 $k$ 个分类器分成两部分：其中之一是判别一个样本是否是 $y_i$ 类，其余的分类器看成一部分，取出个代表吧：判断样本是否是 $m$ 类的，其中 $m\in \{1,\dots,k\}\setminus \{y_i\}$ 。此时不妨假设样本集是线性可分的，则根据上面的"one-aginst-all"我们有下面不等式： $w_{y_i}x_i+b_{y_i}\ge 1 \quad(1)\\ w_{m}x_i+b_m\le -1 \quad(2)$
现在令式(1)和式(2)做减法得： $w_{y_i}x_i+b_{y_i}\ge w_{m}x_i+b_m + 2$ 。对一般情况而言，数据不一定线性可分，所以在上式中加上松弛变量 $\xi_i^m$ 得 $w_{y_i}x_i+b_{y_i}\ge w_{m}x_i+b_m + 2 - \xi_i^m$ ，其中 $\xi_i^m\ge 0$ 。如此我们便得到式(7)中的约束条件。它的一个直观的几何解释是样本 $X_i = (x_i, y_i)$ 到 $y_i$ 类分类器的间隔要大于其他任一分类器。
这样一来，式(6)就很明显了。