支持向量机（一）：线性支持向量机

引言

就目前学习过的机器学习算法中，支持向量机（SVM）应该是最复杂和最难上手的的了，其间涉及多种数学变换、巧合的拼凑，刚开始接触SVM可能一脸懵*，接触地多了慢慢会对SVM的思想有一个概括的认识，但如果不从假设到结论一步步推到，估计也很难将SVM讲的清楚，本文尝试从推导的每一步回顾一下SVM，用以加深理解和记忆。（下面可能会大规模照搬李航老师的蓝皮书，不适的同学请及时止步）

关键词

函数间隔 几何间隔 间隔最大化 凸二次规划

支持向量机(Support Vector Machine)是一种重要的分类方法，由Cortes和Vapnik首先提出，开始主要用于二分类，后来扩展到多分类及回归领域。假设所有样本都是高维空间中的点，支持向量机基于间隔最大化原理, 试图找到一个超平面将所有样本分隔开, 并且该超平面具有最大间隔的性质。根据模型的繁简程度不同，支持向量机又可以分为线性可分支持向量机、线性支持向量机和非线性支持向机，本篇介绍前两种。

1 线性可分支持向量机

考虑两类完全线性可分的样本，如图1所示，存在无限条线性边界可以将这些样本分开，我们无法选择哪条分类直线是最优的。在高维度的情况下，分类直线即成了分类超平面，Cortes等提出的支持向量机模型定义了“间隔”的概念，认为最优的超平面应该在正确分离两类数据的基础上，使得两类数据之间的间隔最大，这里即引出了间隔的定义。

图片1援引自文献《Applied Predictive Modeling》，Fig.13.9.

间隔又可分为函数间隔(functional margin)和几何间隔(geometric margin)，假设分离超平面的方程为$w · x + b = 0$，样本的类别标记为$+1$或$−1$，样本$ i $是否被超平面正确分类可以由$w · x_i + b$的符号与类标记是否一致来表示。由此，引出__函数间隔__的定义，假设有待分类数据集T ，对于给定的样本点$(x_i, y_i)$和超平面$(w, b)$，定义超平面$(w, b)$和__样本点__$(x_i, y_i)$之间的函数间隔为

$\hat{\gamma_i}= y_i(w · x_i + b)$

定义超平面$(w, b)$关于__数据集T__的函数间隔为超平面$(w, b)$关于数据集T中所有样本点$(x_i, y_i)$的函数间隔的最小值，即
$\hat{\gamma}= \min \limits_{i=1,2,\cdots,N} \hat{\gamma_i}$

函数间隔可以帮助判别分类是否正确，但在遴选超平面时，由于成比例地改变超平面参数$w$和$b$，会使得函数间隔发生变化，此时超平面却没有改变。由此，想到可以通过样本点到超平面的距离来表示“间隔”，这既可以描述分类的准确性，也可以通过距离的大小定量地表示分类的确信度（其实我觉得更容易想到的是几何间隔，先提出函数间隔的定义是因为后面求解的时候要用到），由此引出了__几何间隔__的定义，假设有待分类数据集T对于给定的样本点和超平面$(w, b)$，定义超平面$(w, b)$和样本$(x_i, y_i)$之间的几何间隔为

$$ \gamma_i = y_i \left( \frac{w}{\Vert{w}\Vert}·x_i + \frac{b}{\Vert{w}\Vert} \right) $$

括号内为样本点到超平面的带符号的距离，类似地，定义超平面$(w, b)$关于数据集T的几何间隔为超平面$(w, b)$关于数据集T中所有样本点$(x_i, y_i)$的几何间隔的最小值，即

$\gamma = \min \limits_{i=1,2,\cdots,N} \gamma_i$

间隔的定义确定以后，就可以明确我们的目标了，即找出最大几何间隔的超平面（也就是开头说的最大间隔性质的超平面），使得该超平面将两类数据样本分开（假定两类样本线性可分），这个目标等价于下列最优化问题：

$\max \limits_{w,b} \quad \gamma$

$$s.t \qquad y_i\left( \frac{w}{\Vert{w}\Vert}·x_i + \frac{b}{\Vert{w}\Vert} \right) \geq \gamma,\quad i=1,2,\cdots,N$$

由函数间隔和几何间隔的定义可知，函数间隔和几何间隔存在如下关系：
$$\gamma_i = \frac{\hat{\gamma_i}}{\Vert{w}\Vert}$$

$\gamma = \frac{\hat{\gamma}}{\Vert{w}\Vert}$

所以最优化问题可以改写为:

$\max \limits_{w,b} \quad \frac{\hat\gamma}{\Vert{w}\Vert}$
$$s.t \qquad y_i(w · x_i + b) \geq \hat{\gamma},\quad i=1,2,\cdots,N$$

为了求得最大的$\hat{\gamma}/\Vert{w}\Vert$，需要使$\hat{\gamma}$最大而$\Vert{w}\Vert$最小，由于函数间隔的特点，当$\hat{\gamma}$增大时，$w$和$b$也会成比例的改变，因此函数间隔的改变不会对上述优化问题的限制条件产生影响，为了处理方便，我们取$\hat{\gamma}= 1$，同时将最大化问题改写为最小化问题(最大化$1/{\Vert{w}\Vert}$和最小化${\Vert{w}\Vert}^2/2$是等价的)，最终得到了如下的凸二次规划(convex quadratic programming)问题(原始问题):

$$\min \limits_{w,b} \quad \frac{1}{2}{\Vert{w}\Vert}^2$$

$$s.t \qquad y_i(w · x_i + b) - 1 \geq 0,\quad, i=1,2,\cdots,N$$

关于该问题的求解，需要使用到拉格朗日对偶性，因此也常常被称为对偶算法，下一篇再细说。

2 线性支持向量机

涉及到线性不可分的问题时，由于上述问题中的假定不再成立，因此解决方法也需要有所调整。

假定待分离数据集为M，可以将M视作上述问题的T再添加了几个不能被超平面分离的特异点（outlier），这些点不再满足函数间隔大于等于1的约束条件，此时我们对每一个样本点$(x_i, y_i)$都引入一个松弛变量$\xi_i\geq 0$，使函数间隔加上松弛变量大于等于1，如下所示：

$$y_i(w · x_i + b) \geq 1-\xi_i$$

同时，对每一个松弛变量$\xi_i$，都支付相应的代价，因此目标函数变成了：

$$\frac{1}{2}{\Vert{w}\Vert}^2 + C \sum \limits_{i=1} {\xi_i}$$

其中，$C>0$为惩罚参数，需要根据具体情况确定，$C$值大时，对误分类项的惩罚增大，$C$值小时，对误分类项的惩罚减小。此时最小化目标函数的含义是使得几何间隔尽量大，而同时保持松弛变量的和尽量小(即使得被误分类的程度尽量小) ，$C$是调和二者的系数。

此时的优化目标，可以表示成如下凸二次规划问题（原始问题）：

$$\min \limits_{w,b,\xi} \quad \frac{1}{2}·{\Vert{w}\Vert}^2 + C \sum \limits_{i=1} {\xi_i}$$

$$s.t \qquad y_i(w · x_i + b) \geq 1-\xi_i$$

$$\qquad \quad \xi_i \geq 0, \quad i=1,2,\cdots,N$$

该问题是一个凸二次规划问题，因此关于$(w,b,\xi)$的解是存在的。可以证明$w$的解是唯一的，但$b$的解不唯一，$b$的解存在于一个区间。该问题同样使用对偶算法求解。