学习笔记|线性可分支持向量机学习的间隔最大算法
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分分离超平面有无穷多个（等价于感知机，可参见学习笔记|感知机（二）），但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化（与将要讨论的训练数据集近似线性可分时的软间隔最大化相对应）。
间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。
1. 求解最大间隔分离超平面
下面考虑如何求得一个几何间隔最大的分离超平面，即最大间隔分离超平面。具体地，这个问题可以表示为下面的约束最优化问题：
即我们希望最大化超平面(ω,b)关于训练数据集的几何间隔γ，约束条件表示的是超平面(ω,b)关于每个训练样本点的几何间隔至少是γ。
考虑几何间隔和函数间隔的关系式（参见学习笔记|线性可分支持向量机的函数间隔和几何间隔），可将这个问题改写为
函数间隔的取值并不影响最优化问题的解。事实上，假设将ω和b按比例改变为λω和λb，这时函数间隔成为。函数间隔的这一改变对上面最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，也就是说，它产生一个等价的最优化问题。这样，就可以取=1。将=1代入上面的最优化问题，注意到最大化和最小化是等价的，于是就得到下面的线性可分支持向量机学习的最优化问题：
这是一个凸二次规划问题。
凸优化问题是指约束最优化问题
其中，目标函数f(ω)和约束函数是仿射函数时，上述凸最优化问题成为凸二次规划问题。
如果求出了约束最优化问题的解，那么就可以得到最大间隔分离超平面及分类决策函数，即线性可分支持向量机模型。
综上所述，就有下面的线性可分支持向量机的学习算法——最大间隔法。
线性可分支持向量机学习最大间隔法：
输入：线性可分训练数据集，其中，，，i=1,2,...,N；
输出：最大间隔分离超平面和分类决策函数。
（1）构造并求解约束最优化问题：
求得最优解。
（2）由此得到分离超平面：
分类决策函数
2. 支持向量和间隔边界
在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。支持向量是使约束条件式等号成立的点，即
对的正例点，支持向量在超平面
上，对的负例点，支持向量在超平面
上。如下图所示，在和上的点就是支持向量。
和平行，并且没有实例点落在它们中间。在与之间形成一条长带，分离超平面与它们平行且位于它们中央。长带的宽度，即与之间的距离称为间隔。间隔依赖于分离超平面的法向量ω，等于。和称为间隔边界。
在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解；但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。由于支持向量在确定分离超平面中起着决定性作用，所以将这种分类模型称为支持向量机。支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。
参考文献
【1】统计学习方法（第2版），李航著，清华大学出版社