SVM

SVM全称是Support Vector Machines，即支持向量机，是我们用于分类的一种算法。
接下来通过网上一个例子来诠释一下SVM：
首先你的面前出现一堆不同的颜色的球，你需要用跟棍子分开它，如下图情况：

但是当球数变多了，有一颗球站错了阵营

SVM的作用在于把这个用来分类的棍子放在一个合理的位置，达到两个分类个体在棍子的两边都有较大的间隙（如图所示）。

但是现实似乎不可能总是那么容易，一根棍子就解决了。当出现小球是混乱的情况下，是不存在完美的棍子去进行分类的，我们就考虑高级一点的解法了，这个时候你会怎么做呢？你可以翻转桌子，把球扔到空中。然后，你抓住一张纸，并在球之间滑动，也就是把平面化为立体的，而看起来像曲线进行了分类（如下图所示）

在这个例子里面

球→data
棍子 →classifier
最大间隙 →optimization
拍桌子 →kernelling
那张纸 →hyperplane
也就可以解释SVM具体是在做什么的了。
图片来源：(http://bytesizebio.net/2014/02/05/support-vector-machines-explained-well/)

接下来对几种情况做个分析：

A .线性可分

什么是线性可分呢？也就是上面例子中刚开始用棍子解决的小球的分类问题即我们要在一个二维平面上用仅用一条直线去分类。如下图，图a就是需要进行分类的粉球和篮球，图b和图c就行用直线实现了分类。

这个直线就是分界线，虽然图b和图c都实现了分类，但是效果还是有区别的。比如在上面的基础上多加了一颗粉球，图b和图c就出现不同的区别，图c已经实现不了正确的分类

所以我们接下来需要知道的如何求出哪一条直线更适合分类？

从直观上来说，就是分割的间隙越大越好，把两个类别的点分得越开越好。在SVM中，称为Maximum Marginal，是SVM的一个理论基础之一。

下图中被红色和蓝色的线圈出来的点就是所谓的支持向量(support vector)

下图中的Classifier Boundary就是f(x)，红色和蓝色的线（plus plane与minus plane）就是support vector所在的面，红色、蓝色线之间的间隙就是我们要最大化的分类间的间隙。

M要怎么求解呢？根据高中所学的平行直线的距离公式（表示我也是忘了又查了一下....真的是要温故而知新鸭）:d=|c1-c2|/√a²+b²得到

另外支持向量位于wx + b = 1与wx + b = -1的直线上，我们在前面乘上一个该点所属的类别y，就可以得到支持向量的表达式为：y(wx + b) = 1，这样就可以更简单的将支持向量表示出来了。当支持向量确定下来的时候，分割函数就确定下来了，两个问题是等价的。接下来给出优化求解的表达式：

加上限制条件(s.t→subject to）后为：

[说明： ||w||的意思是w的二范数，跟上面的M表达式的分母是一个意思，之前得到，M = 2 / ||w||，最大化这个式子等价于最小化||w||, 另外由于||w||是一个单调函数，我们可以对其加入平方，和前面的系数，这个式子是为了方便求导。]
接下来这个优化问题可以用拉格朗日乘子法去解，使用了KKT条件的理论，这里直接作出这个式子的拉格朗日目标函数