「14」支持向量机——我话说完，谁支持？谁反对？
今天我们来看一个机器学习中最基础、也是最重要的算法——支持向量机。为什么SVM叫SVM，到底向量是谁？SMO又是哪位话事人？支持不支持，咱们往下瞧。
1. 支持向量
1.1 线性可分
首先我们先来了解下什么是线性可分。
在二维空间上，两类点被一条直线完全分开叫做线性可分。
严格的数学定义是：
1.2 最大间隔超平面
从二维扩展到多维空间中时，将 d0 和 d1 完全正确地划分开的 y = wx + b 就成了一个超平面。
为了使这个超平面更具鲁棒性，我们会去找最佳超平面，以最大间隔把两类样本分开的超平面，也称之为最大间隔超平面。
- 两类样本分别分割在该超平面的两侧；
- 两侧距离超平面最近的样本点到超平面的距离被最大化了。
1.3 支持向量
样本中距离超平面最近的一些点，这些点叫做支持向量。
1.4 SVM 最优化问题
SVM 想要的就是找到各类样本点到超平面的距离最远，也就是找到最大间隔超平面。任意超平面可以用下面这个线性方程来描述：
如图所示，根据支持向量的定义我们知道，支持向量到超平面的距离为 d，其他点到超平面的距离大于 d。
至此我们就可以得到最大间隔超平面的上下两个超平面：
2. 对偶问题
2.1 拉格朗日乘数法
2.1.1 等式约束优化问题
本科高等数学学的拉格朗日程数法是等式约束优化问题：
2.1.2 不等式约束优化问题
而我们现在面对的是不等式优化问题，针对这种情况其主要思想是将不等式约束条件转变为等式约束条件，引入松弛变量，将松弛变量也是为优化变量。
2.2 强对偶性
对偶问题其实就是将：
3. SVM 优化
我们已知 SVM 优化的主问题是：
我们可以看出来这是一个二次规划问题，问题规模正比于训练样本数，我们常用 SMO(Sequential Minimal Optimization) 算法求解。
SMO(Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。我们来看一下 SMO 算法在 SVM 中的应用。
我们刚说了 SMO 算法每次只优化一个参数，但我们的优化目标有约束条件：
没法一次只变动一个参数。所以我们选择了一次选择两个参数。具体步骤为：
4. 软间隔
4.1 解决问题
在实际应用中，完全线性可分的样本是很少的，如果遇到了不能够完全线性可分的样本，我们应该怎么办？比如下面这个：
于是我们就有了软间隔，相比于硬间隔的苛刻条件，我们允许个别样本点出现在间隔带里面，比如：
4.2 优化目标及求解
增加软间隔后我们的优化目标变成了：
5. 核函数
5.1 线性不可分
我们刚刚讨论的硬间隔和软间隔都是在说样本的完全线性可分或者大部分样本点的线性可分。
但我们可能会碰到的一种情况是样本点不是线性可分的，比如：
这种情况的解决方法就是：将二维线性不可分样本映射到高维空间中，让样本点在高维空间线性可分，比如：
5.2 核函数的作用
我们不禁有个疑问：只是做个内积运算，为什么要有核函数的呢？
这是因为低维空间映射到高维空间后维度可能会很大，如果将全部样本的点乘全部计算好，这样的计算量太大了。
然后在进行内积计算，才能与多项式核函数达到相同的效果。
可见核函数的引入一方面减少了我们计算量，另一方面也减少了我们存储数据的内存使用量。
5.3 常见核函数
我们常用核函数有：
6. 优缺点
6.1 优点
- 有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
- 能找出对任务至关重要的关键样本（即：支持向量）；
- 采用核技巧之后，可以处理非线性分类/回归任务；
- 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。
6.2 缺点
- 训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为 O(N^2) ，其中 N 为训练样本的数量；
- 当采用核技巧时，如果需要存储核矩阵，则空间复杂度为 O(N^2) ；
- 模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。
因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。
实战项目
为了加深对SVM的理解，下一篇我们利用python搭建SVM支持向量机，来预测蓝瘦香菇到底有没有毒，大家别忘了敲一敲代码哦。「15」支持向量机Python实战篇——蓝瘦香菇到底有没有毒？
参考文献
- 《机器学习》 周志华
- 最优化问题的KKT条件
- 一文理解拉格朗日对偶和KKT条件
- 支持向量机通俗导论（理解SVM的三层境界）