机器学习之SVM原理

相信了解机器学习的同学都知道，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

等等