【SVM】探索支持向量机（二）

vlambda
2020-04-07

【SVM】探索支持向量机（二）

应用之道

存乎一心

从本文开始我们就要正式进入支持向量机的原理介绍，其中涉及到大量的数学推导，因此需要读者具备一定的数理基础（公式有时反而比文字描述更清楚）。很多人表示支持向量机的文章大部分都看不懂，因为其中的公式太多了。对此，笔者只能表示，如果读者不愿意克服数学困难的话，可能也就不太适合在深度学习领域发展了。本文大量内容选取自李航老师的《统计学习方法（第二版）》，由于篇幅限制本文无法进行详尽的展开，欢迎各位阅读李航老师的原作！

线性可分 SVM

回顾超平面与间隔

考虑如下形式的线性可分的训练数据集:

其中 Xi ∈ RN，Yi ∈ {+1, −1}。Xi 为第 i 个特征向量，也称为实例，Yi 为 Xi 的类标记。当 Yi = +1 时，称 Xi 属于正类别。当 yi = −1 时表示 Xi 属于负类别。

支持向量机学习的目标就是在特征空间找到一个分离超平面，能将实例分到不同的类。分离超平面对应于方程 w · x + b = 0，即其由法向量 w 和截距 b 决定，可用（w, b）表示。分离超平面将特征空间划分为两部分，一部分是正类，一部分是负类。法向量指向的一侧是正类，另一侧是负类。

一般地，当训练集线性可分时，存在无穷个分离超平面可以成功地将两类数据正确分类：

而线性可分支持向量机则是利用间隔最大化来求最优分离超平面，此时它的解唯一。

为了找到最大间隔超平面，我们可以先选择分离两类数据的两个平行超平面，使得它们之间的距离尽可能大。在这两个超平面范围内的区域称为间隔（Margin），最大间隔超平面是位于它们正中间的超平面，整个过程如下图所示：

线性可分支持向量机的定义如下：

样例一：函数间隔与几何间隔

下图中有 A、B、C 三个点分别表示 3 个实例，均在分离超平面正类一侧。点 A 距分离超平面比较远，可以比较确信预测是正确的。与之对应的，点 C 距分离超平面较近，则对其预测结果不那么确信。

在超平面 w · x + b = 0 确定的情况下，｜w · x + b｜能够相对的表示点 x 距离超平面的远近。而 w · x + b 的符号与类标记 y 的符号是否一致能够表示分类是否正确，所以可以用 y (w · x + b) 来表示分类的正确性及确信度，这就是函数间隔（Functional Margin）：

但是成比例的改变 w 和 b，例如将它们改为 2w 和 2b，超平面并不会改变。如下图所示，图中箭头代表 w 和 b 的变化，可以发现即使 w 和 b变化，分离超平面依然没有变动：

基于这一事实，我们可以对分离超平面的法向量 w 加上某些约束，比如规范化令 || w || = 1，使得间隔是确定的，这时函数间隔成为几何间隔（Geometric Margin）：

从函数间隔和几何间隔的定义，我们可以得到两者有以下关系：

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的数据点称为支持向量（Support Vector）。硬间隔的支持向量是使 y (w · x + b) = 1的值，如下图所示，处于虚线上的点就是硬间隔的支持向量：

由此可知，在决定分离超平面时，只有支持向量起作用，而其它实例点并不起作用。如果移动非支持向量，甚至删除非支持向量都不会对最优超平面产生任何影响，这也是“支持向量机”名称的由来。支持向量的个数一般比较少，所以支持向量机由很少的“重要”训练样本确定。

间隔最大化

下面考虑如何求得一个几何间隔最大的分离超平面，即最大间隔分离超平面，这个问题可以表示为下面的约束最优化问题：

即表示我们希望超平面（w, b）关于训练集合几何间隔 y 最大化，式中的 s.t. （约束条件）表示超平面关于每个训练样本点的几何间隔至少是 y。事实上，考虑到几何间隔和函数间隔的关系，上式还可以进一步等价：

由于函数间隔 y^ 的取值并不影响最优化问题的解，这样可以取 y^ = 1，并对 1 / || w || 做等价变换（“求使 x 最大的值”与“求使 x ^ 2 最大的值”两个问题等价），我们可以进一步得到线性可分支持向量机学习最优化问题的原始问题（Primal Problem）：

这是一个凸二次规划问题（Convex Quadratic Programming），上式 || w || ^ 2前的1 / 2是为了后续求导后刚好能消去，没有其它特殊意义。

综上所述，就有了下面线性可分支持向量机的学习算法——最大间隔法（Maxinum Margin Method）：

具体方法为：

线性可分 SVM 对偶问题

为了解决线性可分支持向量机学习的原始问题，我们可以应用拉格朗日乘子法构造拉格朗日函数，再通过求解其对偶问题（Dual Problem）得到原始问题的最优解。这样做的优点:

对偶问题更易求解，对偶问题只需优化一个变量且约束条件更简单。
自然引入核函数，进而推广到非线性问题。

这部分具体内容请参考李航老师的《统计学系方法（第二版）》，在此仅列出对偶最优化问题表达式：

对于线性可分训练数据集，我们可以先求得上式对 a 的解 a*，再由 a* 求得原始最优化问题对（w, b）的解 w* , b*。由此可得线性可分支持向量机学习算法：

软间隔最大化与线性 SVM

在前面的讨论中，我们一直假定训练数据是严格线性可分的，即存在一个超平面能“完美”地将两类数据分开。但是在现实任务中，这个假设往往不成立，例如下图所示的数据：

解决该问题的一个办法是允许支持向量机在少量样本上出错，即将之前的硬间隔最大化条件放宽一点，为此引入软间隔（Soft Margin）这一概念。即允许少量样本点（x, y）不满足函数间隔大于等于 1 的约束条件。为此，我们可以对每个样本点（x, y）引入一个松弛变量 ξi >= 0，使得函数间隔加上松弛变量大于等于 1。这样约束条件就变为：