本文原作者：汪毅雄，经授权后发布。
导语：本文用一些简单的例子来解释了SVM是什么，然后通过SVM中最大间隔、核函数、软间隔、SMO四个关键部分，依次进行数学推导和解释。
相信了解机器学习的同学都知道，SVM的“完美强迫症”使得其在各大模型中，几乎是一个“统治性”的地位。但是也不是那么绝对啦，SVM比较耗时，因此不适合那些超大样本。
认识SVM
性质：首先一般情况，它主要解决的是分类问题（当然，回归也是可以做）。
解决的2个主要问题：
1、最大间隔问题
先看一组图片 （图片出处）
假设有一堆球，想用一根棍子把它们分开，怎么做？
有人这么做，确实分开了，那就可以下班了吗？显然不行
SVM看到后，强行把棍子扭一扭才舒服，扭完后棍子离两边的球都比较远了。
OK，先给出几个关于SVM的术语：
小球：数据
棍子：超平面
间隔：离超平面最近的那个数据，到超平面距离
如图，假设间隔为f(x)，则SVM做的事就是找的一个棍子（超平面），使得max{ 2f(x) }，也就是找到最大间距对应的那个超平面。
核函数
还是先看一张图
星星和圆分别代表一些样本，这时候需要分开它们怎么处理？
这时候用一个简单的核函数就能处理了，我们令z = x^2 y^2，这样在z轴上就能得到一些数据，如下图。
这个超平面在z轴的值我们随便举说个，比如9，那超平面可以描述为x^2 y^2 = 9
回到第一张图，看这个核函数的超平面就是这样的划分的。
好了，SVM的认识到此，如果只是想了解SVM是什么的，可以就此打住了，后面的是数学的推导。
详解 数学推导
最大间隔问题
我们知道一个平面的方程可以用
来表示。而点x0到面的距离可以这么表示：
好了，开始真正的说SVM了，这里我们沿用经典的SVM推导方式。
如上图（图片来自wiki），我们假设样本是线性可分的，如果采用最大间隔的方法的话，那么它一定可以表示成如上的模型。也就是说对于所有的白点和黑点都满足：
yi用-1和1来区分，方便推导
而他们的间隔则为
那么最大间隔问题模型就转化为求解使得间隔r最大的w和b，即（s.t.表示受限制于）：
为了方便计算，我们把问题转化成：
这个就是最大间隔问题的最初模型。可以看到这个是一个带不等式约束条件的求最小值问题，而目标函数又是一个凸函数，这个问题就转化成一个凸优化问题！
在我的另一篇文章《 怎么理解凸优化及其在SVM中的应用 》中，详细的解释了凸优化及上述问题的推导，这里直接给出结论。
对于带约束条件的极值问题，肯定也是采用拉格朗日乘子法，其函数：
上述问题的等价问题为：
其对偶问题为：
先求min（L），对w和b分别求偏导得：
代回L中即得到minL，手撕一段吧：
上图最后一行就是最大间隔的对偶问题的最终形式，对偶问题和原始问题等价的话，需要满足KKT条件，令
则KKT条件为：
模型最终转化成参数为alpha的函数最大值问题，也就是由w，b两个参数变成一个参数了！
怎么求？显然，梯度下降法绝对是可行的，但是效率太低。
为了提高效率，大牛们提出了很多高效的算法，其中最著名的一个是SMO算法，这个放到文章最后讲！
核函数
核函数不是SVM独有的，只是SVM让它发扬光大了！在最大间隔问题中，我们的分割平面设为：
这就是说，它只能处理线性分割。而要实现非线性分割，则必须使用核函数了。核函数的作用，其实就是把样本映射到更高维的空间，使得原本线性不可分的样本变得在某一个纬度变得线性可分。
在模型上看来就是把
，代入最大间隔模型中就是
其对偶问题为：
核函数即为：
如果已知φ(x)，那核函数肯定就能求出来，但是通常情况
1、我们往往很难求出合适的。
2、纬度太高的话，求内积会非常非常吓人
因此对于核函数，只能定义一些常用的。但是不是随便定义的，由于是做φ(x)的内积，学过矩阵的应该知道，其核矩阵必须是半正定的。
一些常见的核函数有（内容来自wiki）：
而我们最常用的核函数主要是：线性核（φ(x)=x）、高斯核。
软间隔
先看几幅图
如果样本是如上图，那么沿用上述理论划分是没问题的。
要是这样呢？
有一个样本跑到上面去了（脏数据），如果依然采用之前的理论，那么它会这么划分，这显然不是什么更好的结果。
更好的结果是，我们接受一个错误样本，使得其容错性更强。
怎么在数学上体现呢，SVM采用的是引入松弛变量ε，也就是把目标函数改成：
其中ε指的样本的损失程度，如果样本符合最大间隔条件，那么ε=0。
而C指的是人为引入的权值。比如说上图那个突出的黑点，我们人为的干预它，认为它十分重要/它一定是黑色的。那么C可以设为很大，以致如果把它分错了的话，后果相当严重（损失函数值很大，反映出来的也就是误差很大）
对于软间隔同理，我们可以采用相同的计算方式，得到它的对偶问题为：
和不加损失函数一样，只不过
这个约束条件变成
。
其KKT条件也变化为：
当然损失函数不是只有这一种啦，还有一些甚至可以扩展至回归的，有兴趣的同学可以研究一下。
SMO算法
在最大间隔中，提到了一个解对偶问题的算法也就是SMO,这里也介绍下。刚才我们的优化问题最终描述为：
其中y、x和C都是已知数，要解决的是以α为参数的最大值问题，其中α有m个。
通常，我们的优化思路是，这m个参数逐个地优化，比如说，先固定除α1外的其他参数，然后对它求偏导求极值。但是有个问题在于，我们存在一个约束条件：
这就意味着，如果只保留1个参数α1的话，它可以通过下式直接被算出来：
因此，这里SMO采用保留2个参数的方式。
SMO的优化过程是分很多轮的，每一轮都有这么一些步骤：
1、选出两个合适的参数α1、α2，固定其他参数
2、利用约束条件，算出α1和α2关系，代回目标函数中消掉其中一个α1，那么目标的参数就只剩α2了。
3、唯一参数问题，求偏导求极值
这样经过一轮后，目标函数已经在α1、α2两个参数上max了
这样经过n轮后迭代后，可以选出一组符合条件“最”优解（不一定需要到最优才停止）。
那么问题又来了，怎么选参数呢？SMO有这么一些规则
1、只选择不满足KKT条件的，直观来说就是带来误差（错误样本）的α，每次都从中选取带来误差最大的α作为第一个参数，也就是我们要优化的参数，假设为α1。
2、选取第二个参数的时候，我们要选取对待优化参数α1带来积极影响最大的那个参数.怎么算积极影响呢？SMO定义一个指标E：
先算出所有的参数的E值，已知我们优化的参数为α1的话，那么E1如果为正，则取其他参数中负的最大的那个，反之取正的最大的那个，也是使得|E1 - Ei|最大的那个αi.
这样所有环都通畅了，且每次迭代带来的收益都是最高，迭代次数可能会更少。
主要参考文献
机器学习 周志华
知乎 - SVM是什么意思（https://www.zhihu.com/question/21094489/answer/86273196）
Wiki - SVM
等等
更多优质技术文章请关注官方微信公众号：
长按/扫描关注我们更多优质技术文章请关注官方知乎机构号：
https://www.zhihu.com/org/teng-xun-zhi-neng-tai-ji-qi-xue-xi-ping-tai/activities
