原理就是这么简单 机器学习算法 - SVM中篇（算法解析））

Date: 02/21/2018

读完上篇文章，相信各位大家已经对SVM的数学理论基石有了一个完整的理解（如果还没理解SVM数学理论基础的可以参看上篇），那现在恭喜你，这篇文章所讲解的SVM的原理和实践你会觉得非常轻松。
话不多说，先用一个案例来介绍SVM到底是什么，以及它能解决什么问题。

案例

2018年维米天使正在选拔谁能登上维米的舞台！

原理就是这么简单 机器学习算法 - SVM中篇（算法解析））
这天来了很多出色的模特。
但是这次选拔的标准有两个颜值（满分10分） 和 身高。
有一天小明来代班当面试官，并决定哪些模特可以登上维米的舞台。
小明看到这么多的美丽的模特心想“这不是在鸡蛋里挑骨头吗”？
但是小明又不能让所有来应征的模特都登上舞台，那么小明该怎么办呢？

小明突然想到2017年同样举办过一场非常成功的维米天使，这时候他想通过17年天使的颜值，身高数据来评选18年的天使。
这真是个好主意，首先把17年天使的各个数据输入到计算机里来看一看，如下图：

model.PNG

图中有100个维米天使的数据对应着100个点，其中横轴为身高，纵轴为颜值。
蓝色的代表是去年登上舞台的选手，棕色的代表没有被选上的选手。

这时候可以想到的很好的办法是在图中画条线来区分两块数据。可以这么画：

2.PNG

还可以这么画：

3.PNG

可是图中红色的线和蓝色的线都能很好的分开这两批天使，那到底改用哪个呢？

如果可以画一条线能够把两边的数据尽可能的分开，那不就是说明这条线画的更好嘛。有可能如下图：

3.PNG

嗯哼！这条线小明感觉到很满意，一看就是维米资深面试官画的线，运用于2018年的维米选拔效果肯定不错。

在这个案例中，能用画线的方式来区分两批天使数据，称之为线性可分， 而这条线被称为超平面，
而如何从众多可以区分两批模特的线中找到最中间或者最优的这条线的算法，被称为SVM算法。
SVM 算法有如下两个重点：

判断数据是否线性可分
找到最优超平面

接下来，我们具体看看SVM到底用数学语言是怎么表述并解决的吧

SVM原理

刚才为了找那条最优的超平面，我们有个原则，就是能够把两边的数据尽可能的分开，用数学语言来定义的话就是让这条线离两边的数据的最小距离都尽可能的大。

请看下面这张图：
灰色的是超平面，黑点和红点是一个正样本点和一个负样本点。

4.PNG

此图中点到超平面的距离是

5.png

（数学公式，直接使用就可以了，证明略）
但是公式这里有个绝对值，这让我们计算的时候总是不那么方便，如何去掉这个绝对值呢？
因为当分子部分没有绝对值的话，是有正负号的，当样本属于正样本（e.g. 黑点）那么：

6.PNG

反之（e.g.红点）

7.PNG

然而yi的取值为（正例+1，负例-1），所以yi与上式相乘总是一个大于等于0的数字，如下：

8.PNG

这个比较通用的距离公式被称为几何间隔(Geometric margin)

这样原问题就被转化为了找到 w,b 使得最小的几何间隔最大化 ，又因为最小的几何间隔和 1/ ||w|| 无关所以放到min的外面如下：

9.PNG

简化目标函数

这个目标函数还是有点复杂，因为式子中min的部分对于不同的超平面 xi,yi 都是不定的量，这会让我们的优化变得繁琐，所以我们要想办法进行简化。
在简化之前 我们先来看看这个式子：

10.PNG

这个式子所代表的含义被称为函数间隔(Function margin)
首先我们知道函数间隔永远都是大于0的，这其实就是一个约束。
而对同一个超平面，我们可以通过比例缩放w和b，函数间隔也会同比例变化。举个例子，对于一个成功划分正负实例的超平面（并非最优），如果该平面固定，但是通过缩放w和b， 可以让函数间隔取到任意大的值。对一个超平面，函数间隔与∥w∥的比值保持不变，也就是说几何间隔在同一个超平面下是固定的。而我们优化的目标是最大化几何间隔去找相应的超平面，所以我们可以缩放w,b使得距离最近的点的函数间隔为1（其他的点当然大于等于1），然后最小化∥w∥（与最大化1/||w||等价）达到最大化几何间隔的目的。

这样我们就清晰的看到其实SVM是一个有约束的优化问题，它的基本型为：

svm.PNG

有了基本型，我们可以利用上篇文章中的对偶方式进行求解，很多人之所以不理解SVM其实就是不理解这些数学概念

求解SVM

求解SVM自然利用对偶问题的知识

SVM对偶问题

• 拉格朗日函数：

  
  11.PNG

• 对偶问题

  
  12.PNG

令L（w,b,入）对w,b的偏导等于0，可得：
其中* 代表最优解

13.PNG 14.PNG

代入原拉格朗日函数可得对偶问题为：

15.PNG

根据KKT条件可得：

16.PNG

所以带入w* 可得b*

18.PNG

现在我们就将整个SVM的求解过程解释清楚了。
但是为什么我们非要用对偶来解决原来的问题呢，因为在数学家的研究下已经研究出来了一种名叫SMO的算法可以非常高效率的解决这样的问题，可能在高维多数据的情况下也有着最佳的性能。有兴趣的小伙伴可以去查阅wiki 关于SMO算法的求解过程。

但是作为理解SVM的算法到这里就已经足够了。
接下来我会用SVM算法来实现一些数据线性可分的案例，以及处理线性不可分的案例和它的拓展理论。请看下篇文章。