支持向量机（SVM）的理解与推导（一）

SVM是一种传统的学习算法，多用于二分类问题。根据SVM处理的问题样本是否线性可分可以将SVM分为三种类型。如果存在一个划分超平面可以完美的分隔开所有样本，那么这种SVM叫“线性可分SVM”，通过“硬间隔最大化”学习得到模型；如果存在一个划分超平面可以分隔开绝大部分样本，只有少量样本不能正确划分，则可以通过“软间隔最大化”学习得到模型，这种SVM叫“线性SVM”；还有一种情况，上面两种情况均无法满足，比如“异或问题”，这样的SVM称为“非线性SVM”，需要引入核函数，再按照“软间隔最大化”的方法训练模型。

总之，SVM学习策略的核心是“间隔最大化”。本文用于推导的公式是基于线性可分SVM的，也就是讨论“硬间隔最大化”的数学原理。那么什么是“间隔”，什么又是“支持向量”，先来看一张图片。

SVM对分割训练集样本有多种划分超平面

假设样本数据集 $D=\left\{ (x_{1} ,y_{1} ),(x_{2} ,y_{2} ),...,(x_{m} ,y_{m} ) \right\}$ ，其中 $y_{i} \epsilon \left\{ -1,+1 \right\}$ ，上图中的“+”“-”表示正样本和负样本，可以看出，五条线表示五种超平面的划分方法，那么哪个才是最合适的呢？直观地理解，加粗的线是一种最佳的划分超平面，因为它不仅可以正确分开所有样本点，还处于最“中间”的位置。这会使得超平面划分的泛化能力更强（如果给样本加入噪声或扰动，更不易分类错）。换言之，此分类器的鲁棒性更强，对未知的数据的分类错误率更低。

下面，我们逐步引出“间隔”的概念。在样本空间中，划分超平面的方程为 $\omega ^Tx+b=0$ （可从二维平面的角度理解），样本中任意点到划分平面的距离 $r$ 就是 $r=\frac{\vert\omega ^Tx+b\vert}{\vert\vert\omega \vert\vert}$ 。还是看上面的图，样本被完全正确的分类，也就是说如果样本为正，则 $\omega ^Tx+b＞0$ ，如果样本为负，则 $\omega ^Tx+b<0$ 。

我们观察到，即使是离平面最近的样本，也是与平面有一定距离的，离划分超平面最近的那几个向量，就是“支持向量”。由此可以看出SVM的一个特性，超平面的选择只与支持向量的值有关，如果更改甚至删掉其他的部分样本，模型不会受到影响。这就是“支持向量机”。支持向量机的个数一般很少，所以支持向量机是由少数“重要的”样本决定的。

我们这样描述所有样本，令

$\omega ^Tx_{i} +b\geq +1, y_{i} =+1;\\\omega ^Tx_{i} +b\leq -1, y_{i} =-1;$

其中， $i$ 表示样本编号。这里解释一下，为什么可以令表达式 $\geq +1$ 而不是严格 $>0$ 。前面提到，离划分平面最近的样本点与平面是有一定的距离的，我们看划分超平面的方程 $\omega ^Tx+b=0$ ， $\omega$ 和 $b$ 是可以同时扩大、缩小相同倍数而不改变原方程的，那么在正样本的原方程可以写为 $\omega ^Tx+b\geq r_{最近}$ ，除了自变量之外的三个参数可以同时扩大或缩小就成了上面的方程。那什么时候等号成立呢？自然就是当样本为“支持向量”的时候。这时两个异类的支持向量到平面的距离之和为：

$\gamma =\frac{2}{\vert \vert \omega \vert \vert} \\$ ;

这就是“间隔”的定义。不难看出，我们的目标应该是找到间隔最大的超平面，也就是

$max_{\omega ,b} \frac{2}{\vert \vert \omega \vert \vert } ;\\s.t. y_{i} (\omega ^T x_{i} +b)\geq 1,i=1...m;$

我们将其改写为最小值函数：

$min_{\omega ,b} \frac{1}{2} \vert \vert \omega \vert \vert ^2 ;\\s.t. y_{i} (\omega ^T x_{i} +b)\geq 1,i=1...m;$

上式被称为SVM的基本型（后文统一称作“原问题方程”）。那如何求解这个问题呢？我们对其对偶问题进行求解，这样做有两个原因，一是对偶问题只涉及到一个参数，更易求解，二是自然引出核函数，核函数也是SVM的核心之一。对上式使用拉格朗日乘子法即可得到对偶问题：

$L(\omega ,b,\alpha )=\frac{1}{2} \vert \vert \omega \vert \vert ^2+\sum_{i=1}^m \alpha _{i} (1-y_{i} (\omega ^T x_{i} +b))\\$

我们最终要求解的问题时极大极小问题，即 $max_{\alpha _{i} } min_{\omega ,b} L(\omega ,b,\alpha )$ ，首先计算极小的部分，根据大学数学的基本知识，令 $L(\omega ,b,\alpha )$ 对 $\omega$ 和 $b$ 求偏导：

$\omega =\sum_{i=1}^m \alpha _{i} x_{i} y_{i} ;\\0=\sum_{i=1}^m \alpha _{i} y_{i} ;$

代入原式，得：

$\\L(\omega ,b,\alpha )=\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha _{i} \alpha _{j} x_{i} x_{j} y_{i} y_{j} +\sum_{i=1}^m \alpha _{i} -\sum_{i=1}^m \alpha _{i} x _{i} y_{i} \sum_{j=1}^m \alpha _{j} x _{j} y_{j} \\=\sum_{i=1}^m \alpha _{i}-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha _{i} \alpha _{j} x_{i} x_{j} y_{i} y_{j}$

所以对偶问题要解的方程是：

$\\max_{\alpha _{i} } L(\omega ,b,\alpha )=max_{\alpha _{i} }(\sum_{i=1}^m \alpha _{i}-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha _{i} \alpha _{j} x_{i} x_{j} y_{i} y_{j} )$

$s.t.\sum_{i=1}^m \alpha _{i} y_{i} =0; \\\alpha _{i} \geq 0,i=1...m;$

只需要解出来一个向量 $\alpha$ 即可。这里现成的、高效的算法是SMO算法。

SMO的基本思路是先固定 $\alpha _{i}$ 之外的所有参数，求 $\alpha _{i}$ 上的极值。每次SMO会选择两个变量 $\alpha _{i}, \alpha _{j}$ ，并固定其他参数。

在每次迭代时，选择一对需要更新的变量 $\alpha _{i} ,\alpha _{j}$ ，固定其他变量，也就是：

$\alpha _{i} y_{i} +\alpha _{j} y_{j}=c;\\c=-\sum_{k\neq i,j}\alpha _{k} y_{k};$

这样， $\alpha _{j}$ 可以表示为 $\alpha _{i}$ 的函数，对偶问题要解的极大值方程为单变量二次规划问题，易于求解。求解出 $\alpha$ 之后，再求解 $\omega ,b$ ，有如下定理：

若 $\alpha =(\alpha _{1} ,\alpha _{2} ,...,\alpha _{n} )^T$ 是对偶问题的解，那么存在 $\alpha _{j} >0$ ，且原问题方程的解为：

$\omega =\sum_{i=1}^m\alpha _{i} y _{i} x _{i} ;\\b=y _{i} -\sum_{i=1}^m\alpha _{i} y _{i}( x _{i}\bullet x _{j});$

最后模型表示为：

$f(x)=\omega ^Tx+b=\sum_{i=1}^m \alpha _{i} y_{i} x_{i} ^Tx+b;\\$

另外，由于原问题方程满足KKT条件，即

$\alpha _{i} \geq 0;\\y_{i} f(x_{i})-1 \geq 0;\\\alpha _{i}(y_{i} f(x_{i})-1)=0;$

可以看出，对任意训练样本，要么 $\alpha _{i} =0$ ,要么 $y_{i} f(x_{i})=1$ ，如果是前者，那么不影响模型的结果，如果是后者，可以看出样本在间隔边界上，是一个支持向量。这也呼应了前文“模型只与支持向量有关”的结论。