支持向量机SVM

点到平面的距离
https://www.cnblogs.com/graphics/archive/2010/07/10/1774809.html
两条直线的距离公式
http://www.gaosan.com/gaokao/262318.html

1 概念

上图中H3作为分类器比较好，首先H1不能把类别分开，这个分类器肯定是不行的；H2可以，但分割线与最近的数据点只有很小的间隔，如果测试数据有一些噪声的话可能就会被H2错误分类(即对噪声敏感、泛化能力弱)。H3以较大间隔将它们分开，这样就能容忍测试数据的一些噪声而正确分类，是一个泛化能力不错的分类器。

对于支持向量机来说，数据点若是p维向量，我们用p-1维的超平面来分开这些点。但是可能有许多超平面可以把数据分类。最佳超平面的一个合理选择就是以最大间隔把两个类分开的超平面。因此，SVM选择能够使离超平面最近的数据点的到超平面距离最大的超平面。

以上介绍的SVM只能解决线性可分的问题，为了解决更加复杂的问题，支持向量机学习方法有一些由简至繁的模型:

• 线性可分SVM

当训练数据线性可分时，通过硬间隔(hard margin，什么是硬、软间隔下面会讲)最大化可以学习得到一个线性分类器，即硬间隔SVM，如上图的的H3。

• 线性SVM

当训练数据不能线性可分但是可以近似线性可分时，通过软间隔(soft margin)最大化也可以学习到一个线性分类器，即软间隔SVM。

• 非线性SVM

当训练数据线性不可分时，通过使用核技巧(kernel trick)和软间隔最大化，可以学习到一个非线性SVM。

线性可分SVM——硬间隔

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

其中是一个含有个元素的列向量, 即;是标量,,时表示属于正类别,时表示属于负类别。
注: 本文中,、、等都是(列)向量，有的文章一般用表示一个向量而用表示所有组成的一个矩阵，注意区分。
回忆一下感知机的目标: 找到一个超平面使其能正确地将每个样本正确分类。感知机使用误分类最小的方法求得超平面，不过此时解有无穷多个(例如图1.1的H2和H3以及它俩的任意线性组合)。而线性可分支持向量机利用间隔最大化求最优分离超平面,这时解是唯一的。

超平面与间隔

一个超平面由法向量和截距决定,其方程为, 可以规定法向量指向的一侧为正类,另一侧为负类。下图画出了三个平行的超平面，法方向取左上方向。
注意: 如果和都是列向量,即会得到和的点积(dot product, 是一个标量),等价于和。

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

间隔最大化

将高数里面求两条平行直线的距离公式推广到高维可求得图中margin的:

两条平行直线距离公式：若两直线分别为Ax+By+C1=0和Ax+By+C2=0，则距离为|C1-C2|/√ (A²+B²)

我们的目标是使最大, 等价于使最大:
上式的是为了后续求导后刚好能消去，没有其他特殊意义。
同时也不要忘了有一些约束条件:
总结一下，间隔最大化问题的数学表达就是
通过求解上式即可得到最优超平面和。具体如何求解见2.4和2.5节。

支持向量

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的数据点称为支持向量(support vector)，支持向量是使中的约束条件取等的点，即满足
的点。也即所有在直线或直线的点。如下图所示:

图 2.2
在决定最佳超平面时只有支持向量起作用，而其他数据点并不起作用(具体推导见2.4节最后)。如果移动非支持向量，甚至删除非支持向量都不会对最优超平面产生任何影响。也即支持向量对模型起着决定性的作用，这也是“支持向量机”名称的由来。

对偶问题

我们称式所述问题为原始问题(primal problem), 可以应用拉格朗日乘子法构造拉格朗日函数(Lagrange function)再通过求解其对偶问题(dual problem)得到原始问题的最优解。转换为对偶问题来求解的原因是:

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

首先构建拉格朗日函数。为此需要引进拉格朗日乘子(Lagrange multiplier)。则拉格朗日函数为（，将不等式右侧变到左侧然后整体乘以拉格朗日乘子）:


引入拉格朗日之后需要最大化L，然后取最大化L中所有值的最小值对应的b和w。
因此，给定一个和, 若不满足式的约束条件，为正，那么有时L最大。
否则，若满足式的约束条件，为负，该项为0能使得最大化L，有
结合式和知，优化问题
与式所述问题是完全等价的。
根据拉格朗日对偶性，式所述问题即原始问题的对偶问题是:
以上具体推导细节可参见书籍《统计学习方法》或者知乎文章拉格朗日对偶性
为了求得对偶问题的解，需要先求得对和的极小再求对的极大。
(1) 求: 对拉格朗日函数求导并令导数为0，有:对w求偏导对b求偏导
将上面两式代入：

所以，

(2) 求对的极大:
等价于式对求极大，也等价于式取负数后对求极小，即
同时满足约束条件:

至此，我们得到了原始最优化问题和对偶最优化问题、。
由slater条件知，因为原始优化问题的目标函数和不等式约束条件都是凸函数，并且该不等式约束是严格可行的(因为数据是线性可分的), 所以存在,,，使得,是原始问题的解，是对偶问题的解。这意味着求解原始最优化问题可以转换为求解对偶最优化问题、。

slater 条件: 原始问题一般性表达为
则其拉格朗日函数为

假设原始问题目标函数和不等式约束条件都是凸函数，原始问题等式约束都是仿射函数，且不等式约束是严格可行的，即存在，对所有都有，则存在,,，使是原始问题的解，,是对偶问题的解。
那么如何求解优化问题、的最优解呢？ 不难发现这是一个二次规划问题，有现成的通用的算法来求解。
事实上通用的求解二次规划问题的算法的复杂度正比于训练数据样本数，所以在实际应用中需要寻求更加高效的算法，例如序列最小优化(Sequential Minimal Optimiation, SMO)算法。
假设我们现在求得了、的最优解，则根据式可求得最优：
因为至少存在一个(若不存在，即全为0，则, 即,显然不行), 再根据KKT条件，即

所以至少存在一个, 使, 即可求得最优:
至此，所以我们就求得了整个线性可分SVM的解。求得的分离超平面为:
则分类的决策函数为
再来分析KKT条件里的互补条件，对于任意样本，总会有或者。则有若，此样本点不是支持向量，对模型没有任何作用；若，此样本点位于最大间隔边界上，是一个支持向量，如下图所示。

图2.3
此外，当样本点是非支持向量时，因为, 所以SVM的解中的求和项中第项就为0，所以SVM的解、可简化为如下形式:
类似的，判别函数也可转换成如下形式:
所以，整个SVM的解只与支持向量SV有关，与非支持向量无关。这也就解释了2.3节的结论，即在决定最佳超平面时只有支持向量起作用，而其他数据点并不起作用。