支持向量机
“SVM有三宝，间隔对偶核技巧”
首先，支持向量机是一个二分类的模型。
他与感知机算法有很多相似的地方，都是使用超平面分割空间，但是与感知不同的是：
- 支持向量机并不是感知机的错误驱动，而是对于几何间隔的最大化。
- 支持向量机可以解决的问题很多样，线性可分，近似线性，非线性可分。
线性可分问题：
对于线性可分的问题：
支持向量机采用硬间隔最大的方法训练模型。
首先，我们先解释一下，什么是间隔？
间隔，就如我们所想的就是距离，而这里我们要提及的有两种间隔：
- 函数间隔
- 几何间隔
几何间隔
几何间隔，对于两个点来说，就是两个点之间的距离，至于怎么算，我想也不用说了。
但是，在分类训练问题中，往往不是两个点，而是两堆点，那么对于两堆点，什么是几何间隔呢？
就是两堆中离得最近的点到超平面的距离，而在SVM中，我们知道：
我们是通过超平面分割来实现分类的，所以这个几何距离在实际中表示的就是：
将所有点分开的确信度大小
公式就是：
函数间隔
可能学习过感知机的同学，知道函数间隔，当时统计学习方法中李杭老师对函数间隔一笔带过，留到SVM这里。这里，我们就对当时的一些问题一目了然了。
在感知机中，与其说这是函数间隔，我更愿意将他理解为分类错误的判别函数，其实感知机中并没有涉及到距离，所以这也就是，支持向量机与他不同的地方。
为什么支持向量机不采用函数间隔呢？
如果我们相同比例的扩大和
，超平面并没有变，但是函数间隔却变成了原来的n倍。所以，对于支持向量机不能使用函数间隔。
硬间隔最大化
什么是硬间隔呢？
要理解硬间隔，你需要知道什么叫软间隔，而什么是软间隔呢？这个在近似线性可分再说吧。
这里，我们只要知道，硬间隔在这里就是间隔。
所以，我们的整个训练过程，现在就变成了一个约束条件下的最优化问题：
为什么要有约束条件呢？
其实很简单，首先我们要先满足线性可分，才能使用硬间隔最大化。所以，我们得保证所有的训练数据都要有一个间隔，然后在从间隔中取出最大的一个。
其实，我们可以从前面知道：
函数间隔只是用来指示分类是否正确的函数，但是对于距离并没有影响，简单的说，函数间隔只是掌握了方向，真正影响分类确信度的是，也就是
的L2范数。
或者说这样解释：
首先因为数据是线性可分的，所以，所以一定会有两条直线穿过正例和负例的支持向量，如图：
所以两条直线之间的间隔就是我们要比较的间隔，然后我们的约束条件就是：
数据线性可分
如何实现呢？
只要有一条直线能把他们完全分开
合并在一起就是：
所以，我们可以变换为：
然后，要求的最大值，也就是求
的最小值。为了方便求导：
现在有了公式，我们怎么优化他呢？
对于有约束条件的优化问题，我们使用拉格朗日乘子法
但是这里的拉格朗日乘子法和我们高数中学到的不太一样，我们学习到的是最基本的拉格朗日乘子法是等式约束，很明显，我们这里是不等式约束。所以，我们采用的是一种不一样的东西：
上面的优化问题等价于：
证明：
现在，我们来推导一下整个过程：
首先，我们要做的是间隔最大化：
然后，我们使用拉格朗日乘子法（向量化）：
为了减小计算难度，我们这里使用了拉格朗日的强对偶性：
然后，我们开始计算：
分别对求偏导，等于零，再带入到拉格朗日函数中，最终我们就得到了
的值。
最终，我们就得到了：
这样，我们就可以看到，我们把一个不等式约束的问题通过拉格朗日转换成了等式约束问题，从而，我们可以算出这个 ,然后，我们使用KKT条件算出最后的
。
KKT条件：(强对偶性一定满足KKT)
- 主问题可行：
- 对偶问题可行：
- 互补松弛：
根据KKT条件，我们可以求出：
最终，我们就得到了分类决策函数。
对于最后一步最大化，我们将所有数据带入，然后通过偏导等于零，求得最大值
所以，我们解决一个Hard-margin分类问题时，我们需要:
- 构造并解出等式约束最优化问题
- 计算
- 求出分离超平面。
线性不可分问题
显然很多时候，我们的训练数据并不是那么的完美，总是有着各种各样的噪声，所以，我们需要将我们的SVM扩展到线性不可分的情况上去。
这时候，我们就需要引入软间隔最大化
什么是软间隔呢？
我们从头说起：
往往真实情况是我们并不能完美的将所有的数据分开，总有一些特异点在硬间隔最大化的策略下无法分类。那么这时候，我们为所有数据的判断上加入了一个常数松弛变量，使特异点在松弛变量的影响下可以被分开。所以这时候，我们的约束条件就变成了：
同时，对于每个松弛变量，我们需要支付一个代价,目标函数就由原来的
变为了：
这里的C是惩罚参数，表示了对误分类的惩罚力度。
现在，最小化目标函数就有了两层意思：
- 使
尽量小也就是间隔尽量大
- 使误分类点尽可能少
C是调和两者的参数。
现在，线性不可分的线性支持向量机的学习问题就变成了凸二次规划问题：
其他的就和上面的一样了。
