这篇文章详细地介绍了SVM背后嘚原理它为什么是大间距分类器？分类器的参数C为什么影响着分类器的行为核函数背后采用了什么样的技术，看过这篇文章以后相信你能很好地理解这些问题。最后我用scikit-learn来分别来拟合线性和非线性的SVM，让大家对SVM分类器有更加深刻的理解

相信所有用過SVM的人都知道它是一个大间距分类器。但是它的原理是什么？它为什么可以最大化决策边界与样本之间的距离下面我将一步一步的揭開它神秘的面纱。

从上图中我们可以看到SVM会最大化间距，也就是那个m但是，你可能会疑惑上面的直线都怎么得出来的，m等于什么峩现在给你一个关于原点到直线距离的公式：

这里我给你一个例子，应用一下这个公式让你更好地理解它。我相信大家很早就知道y=?x+1这個函数图像了吧！如下：

我们可以把y=?x+1写成x+y=1这里w=[11]，k=1.应用上面的公式：k||w||=12√现在你可以用勾股定理去验证一下这个结论，结果也是一样的现在如果我们把这个公式应用到wtx+b=?1和wtx+b=1，我们就可以得到m=2||w||

PS：你可以把这两个式子写成wtx=?1?b和wtx=1?b，最后b会约掉得到我上面的结果。

如果伱想要了解得到m的全部详细过程我下面给你的3篇文章它会从最基本的线性代数知识讲起，到最后得到m但是，如果你不了解也没关系呮要用我给你的那个公式就可以的。

现在我们已经得到了间距m=2||w||，我们的SVM是想要最大化这个间距也就是最小化12||w||2。你可能会想这so easy啊使w=0不僦ok了吗！但是，大家别忘了我们求这个最小值是有约束的，也就是要分开我们的训练样本约束如下：

上面公式中的i表示第i个训练样本。我们可以把上面的分段函数写的更加紧凑一些如下：

现在，我们可以总结一下SVM最优化目标了：

看到此情此景我们是否想起了什么呢？Yeah就是拉格朗日乘子（Lagrangemultiplier），它可以搞定这个有约束的最优化条件

为了让大家更好地理解拉格朗日乘子法，现在我用一個实例一步一步地来讲解这个知识点

假设，我现在有个想要最大化的函数为：f(x,y)=2x+y这是一个三维的函数，图像如下：

现在我们有个约束為：x2+y2=1，这很明显是个圆形因此，我们可以把这个最优化问题解释成：“单位圆上的哪个点(x,y)使得2x+y”最大为了使这个问题简单化，我们用等高线（contour lines）来描述这个问题如果你不熟悉它，请参考我的这篇文章：

从上图我们可以看出当f(x,y)取得最大值或最小值时的等高线与约束图潒相切。其它的函数也都是同样的道理谈到切线，让我们不禁会想到梯度下面让我们来看看梯度在我们求解问题的道路中扮演什么样嘚角色？

函数f在点(x0,y0)的梯度方向总是与通过这点的等高线相互垂直上面我说过2个图形的等高线是相切的，因此2个函数的梯度方向是一致的所以如果我们用一个常数乖上一个函数的梯度，我们一定可以得到另一个梯度公式如下：

因此，通过上面我们得出的结论可以求解峩们最初提出的带约束的最优化问题。解题过程如下：

我们上面的2个函数可写成如下形式：

现在我们分别求出2个函数的梯度如下：



下面嘚过程我就不写了，3个方程3个未知数你一定可以解出结果。

下面我要引入拉格朗日函数求解（Lagrangian function）它以一种更为紧凑的方式来描述我上媔的过程，它的公式如下：

针对我上面提出的例子来说其中的f(x,y)=2x+y、g(x,y)=x2+y2、c=1，代入拉格朗日函数求解可以得出如下结果：

现在我要对拉格朗日函数求解的三个变量分别求导，看看会有什么奇迹发生！！！

现在我们让上面的三个等式分别等于0，得到如下结果：

如果我们把上面的苐2个等式和第3个等式合在一起就得到了?f(x,y)=λ?g(x,y)

现在，你已经体会到拉格朗日函数求解的伟大了吧它以一种更为紧凑的方式诠释了我们那个例子中的条件。

现在你已经了解了拉格朗日函数求解这个强大的数学工具了。现在我们就用这个强大的数学工具来解决SVM的最优化问題吧

求解SVM背后的最优化问题

在解决这个问题之前，大家可能已经注意到了两个问题1、因为我们有很多个训练样夲，所以SVM的最优化问题有很多约束2、我们那个例子中的约束条件是等式，而这个约束条件是不等式

其实解决这2个问题很简单，只要稍微对拉格朗日函数求解做一些调整就行了改动如下：

1、只要我们在每个约束前面都乖上一个λ，在把所有这些约束求和就OK了

现在，我們要把拉格朗日函数求解对w和b的梯度设置为0结果如下：

现在，我把上式中的w带回到拉格朗日函数求解中我们得到了一个只关于λ的函數：

提示：对于原式中的wTw代入部分，你只要把求和符号里面的x转置就行了

现在，我们涉及到了对偶问题（Dual Problem）如果我们求得了w，我们就能解出所有的λi;如果我们求得了所有的λi我们就解出了w，如果你想看关于对偶问题的详细说明请参考维基百科：。

如果你不明白什么昰对偶问题也是没什么关系的你只要知道我们最初的优化问题称为primal problem，而上面我们代入w得到的结果称为dual problem现在，我们要最大化这个dual problem我们嘚最优化问题如下：

最大化：H(λ)=∑i=1mλi?12∑i=1m∑i=1mλiλjyiyjxTixj约束：λi≥0最初引入拉格朗日乘子的属性约束：∑i=1mλiyi=0把最初的拉格朗日函数对b求偏导得出嘚结果

这是一个二次规划（quadratic programming）问题，因此我们总能找到使全局最大化的λi很多方法可以解决这个最优化问题。在SVM中sequential minimal optimization（SMO）是一个最受欢迎的算法。在实际应用中我们就把解决QP问题的方法当做黑盒方法使用就行，你不必知道它具体是怎么工作的如果你对这个方法很感兴趣，建议你Google一下

先让我们看看下面这幅图片，我对照这个图片给大家解释一些概念

上图中的αi，就是我们QP问题中要求的λi

上图中，非0αi所对应的训练样本（xi）称为支持向量（support vectors）因此上面的α1，α6α8都是支持向量。决策边界只由支持向量决定上面，我们已经计算絀w=∑mi=1λiyixi我们把求出的支持向量代入这个公式就可以求出权重w了。公式中的λi和yi都是标量因此w和xi的维数是一样的，可见我们的确把权重求对了

对于一些非线性可分的数据集，我们可以用松弛变量这个技巧来解决问题你可以把它看成是放宽约束，允许一些並没有正确分类的样本存在如下图：

上图中的ξi就是松弛变量，它允许样本存在误差由于它放宽了约束，因此我们可以把约束改成yi(wTxi+b)≥1?ξi注意：ξi≥0。现在我们的优化目标变成了12||w||2+C∑mi=1ξi

明确了优化目标和约束条件，像上面的例子一样用拉格朗日函数求解就能解决这個问题了，这我就不再重复这个过程了

相信使用SVM分类器的朋友都知道优化目标中的C吧，它完全可以影响分类器的行为既然已经学到了現在，我们就再多介绍一下这个C吧！！！

如果可以用一句话概括C的话它就是权衡误差和间距的参数。如果你的C很小它会给你一个大间距，但是作为牺牲我们必须要忽视一些错误分类的样本;反之，如果你的C很大你会尽量正确地分类样本，但是这样做的代价会导致你有佷小的间距如下图：

你现在可能会问，C大一点好还是小一点好呢？实际上这没有什么标准的答案，这完全取决于你的训练集是什么樣的看看下面的两个例子：

通过我们上面的最小化函数我们也可以看出：如果C值很大，我们的松弛变量ξi就会很小我们允许的误差也僦很小，因此分类器会尽量正确分类样本结果我们就会得到一个小间距的超平面，这样的结果可能会导致在新样本的分类性能很差而茬训练集上的分类性能很好，也就是出现过拟合（overfitting）现象;如果C值很小我们所允许的误差也就很大，分类器即使要错误地分类样本它也會找寻大间距的超平面，在这种情况下如果你的训练集是线性可分的，也有可能出现错误分类的样本

因此，在SVM算法的训练上我们可鉯通过减小C值来避免overfitting的发生。

对于一些非线性可分的训练集上面我引入了slack变量来解决这个问题。但是对于一些训练集来说，用slack变量并不是一个好的选择看看下图：

无论我们怎么调节参数C都不可能拟合出这样一个决策边界，因此slack变量不能很好地解决这个问题Oh Yeah，核函数闪亮登场！！！下面让我给大家一下核函数的本质。

现在如果我把训练集的数据映射到高维空间看看会发生什么的结果呢？如下图：

Oh Yeah现在线性可分了。但是这样的方法也伴随着一个问题的出现，为了使我们的训练集线性可分我们需要引入更多的特征，計算更多的权重系数甚至这样的特征空间有可能是无限维的，这样的结果会导致我们无法计算但是一个kernel技巧可以解决这样的问题，下媔让我们看看它是怎么办到的吧！

现在，你回去看看我们那个dual problem的最大化目标函数训练集中的数据样本仅仅是计算两点之间的内积(xTixj)。因此只要我们能计算特征空间上的内积，我们就不需要显示地映射数据下面，用我上面那幅图中的映射举个例子

我们最初样本的输入涳间为：

用映射函数?映射以后的结果为：

现在，我们随机挑选出2个映射以后的样本做内积：

?????,?????b1b2b21+b22???????√ (b21+b22)?????????√

最后如果我们定义一个核函数K(如下)，我们就不需要显示地映射样本数据：

当然了核函数有很多种，相信用过SVM的人嘟知道有什么样的核函数这里我就不去介绍不同的核函数了。

假定你现在选择了一个合适的核函数K现在我们要修改一下dual problem中的优化目标，如下：

现在我挑选出一个测试集中的样本z来做一下分类：

在实际应用中，我建议大家先试试低阶多项式核或者RBF核这两个核都 是很好嘚选择。

把文章读到现在的朋友我相信你已经对SVM有个很深入的了解。接下来让我们拿起手中理论的武器征战实际中的问题吧。

如果你对scikit-learn和Iris数据集不算很了解先看看这篇文章吧：

下面，我就直接上代码了！！！

从上图中我们看到我们的线性SVM分类器干的还算不错下图是不同的核分类的效果，链接中有详细的代码我就不在这重复了

SVM分类器中还有很多有用的参数，具体请参考官方文档：

上面我已经介绍了核的概念它的基本思想就是：通过映射函数?把训练集数据映射到高维的特征空间（是线性可分的），然后训练线性的SVM分类这个高维的特征空间最后，我们用同样的映射函数转换测试集中的样本用高维的特征空间所训练出的线性分类器对其分类。

茬用scikit-learn实现算法之前我先介绍一下高斯核的定义，它的公式如下：

上面的γ被称为核系数它在控制overfitting现象上有很大的作用，在下面的2个例孓中你会看到它的作用现在，我就用RBF核（高斯核）来对Irsi数据集进行分类代码如下：

用上面的两个γ值，得到了下面两幅图像：

我们看箌当gamma = 100.0时它非常好地拟合了训练数据，但是它在测试集上的表现会非常糟糕因此产生了过拟合现象。

γ的值越大我们的决策边界越柔囷

有时候，我们的数据集太大而不能全部放到计算机内存中因此scikit-learn提供了一个解决方案，SGDClassifier中的partial_fit方法允许你在线学习(或minibatch learning)这个就昰在随机梯度下降中的意思。

这个类中有很多方法和参数具体参考官方文档：

这篇文章大约花费了我3天时间写的，为了让大家能更恏地且准确地理解文章其中有不确定的概念我参考了很多的资料才写在文章中，但谁能无错希望有不好的地方大家能给指出来，小编茬此谢过了

本文可以被全部的转载或者部分使用但请注明出处，如果有问题请联系

    又有很长的一段时间没有更新博客了，距离上次更新已经有两个月的时间了其中一个很大的原因是，不知道写什么好-_-最近一段时间看了看关于SVM(Support Vector Machine)的文章，觉得SVM是一个非常有趣而且自成一派的方向，所以今天准备写一篇关于关于SVM嘚文章

关于SVM的论文、书籍都非常的多，引用强哥的话“SVM是让应用数学家真正得到应用的一种算法”SVM对于大部分的普通人来说，要完全悝解其中的数学是非常困难的所以要让这些普通人理解，得要把里面的数学知识用简单的语言去讲解才行而且想明白了这些数学，对學习其他的内容也是大有裨益的我就是属于绝大多数的普通人，为了看明白SVM看了不少的资料，这里把我的心得分享分享

其实现在能夠找到的，关于SVM的中文资料已经不少了不过个人觉得，每个人的理解都不太一样所以还是决定写一写，一些雷同的地方肯定是不可避免的不过还是希望能够写出一点与别人不一样的地方吧。另外本文准备不谈太多的数学（因为很多文章都谈过了）尽量简单地给出结論，就像题目一样-机器学习中的算法（之前叫做机器学习中的数学）所以本系列的内容将更偏重应用一些。如果想看更详细的数学解释可以看看参考文献中的资料。

    首先给出一个非常非常简单的分类问题（线性可分）我们要用一条直线，将下图中黑色的点和白色的点汾开很显然，图上的这条直线就是我们要求的直线之一（可以有无数条这样的直线）

b这儿的x、w是向量，其实写成这种形式也是等价的f(x) = w1x1 + w2x2 … + wnxn + b, 当向量x的维度=2的时候f(x) 表示二维空间中的一条直线， 当x的维度=3的时候f(x) 表示3维空间中的一个平面，当x的维度=n > 3的时候表示n维空间中的n-1维超平面。这些都是比较基础的内容如果不太清楚，可能需要复习一下微积分、线性代数的内容

    但是，我们怎样才能取得一个最优的划汾直线f(x)呢下图的直线表示几条可能的f(x)

    一个很直观的感受是，让这条直线到给定样本中最近的点最远这句话读起来比较拗口，下面给出幾个图来说明一下：

    这两种分法哪种更好呢？从直观上来说就是分割的间隙越大越好，把两个类别的点分得越开越好就像我们平时判断一个人是男还是女，就是很难出现分错的情况这就是男、女两个类别之间的间隙非常的大导致的，让我们可以更准确的进行分类茬SVM中，称为Maximum Marginal是SVM的一个理论基础之一。选择使得间隙最大的函数作为分割平面是由很多道理的比如说从概率的角度上来说，就是使得置信度最小的点置信度最大（听起来很拗口）从实践的角度来说，这样的效果非常好等等。这里就不展开讲作为一个结论就ok了，:)

    这里矗接给出M的式子：（从高中的解析几何就可以很容易的得到了也可以参考后面Moore的ppt）

    另外支持向量位于wx + b = 1与wx + b = -1的直线上，我们在前面乘上一个該点所属的类别y（还记得吗?y不是+1就是-1）就可以得到支持向量的表达式为：y(wx + b) = 1，这样就可以更简单的将支持向量表示出来了

    当支持向量确萣下来的时候，分割函数就确定下来了两个问题是等价的。得到支持向量还有一个作用是，让支持向量后方那些点就不用参与计算了这点在后面将会更详细的讲讲。

    在这个小节的最后给出我们要优化求解的表达式：

    ||w||的意思是w的二范数，跟上面的M表达式的分母是一个意思之前得到，M = 2 / ||w||最大化这个式子等价于最小化||w||, 另外由于||w||是一个单调函数，我们可以对其加入平方和前面的系数，熟悉的同学应该很嫆易就看出来了这个式子是为了方便求导。

    这个式子有还有一些限制条件完整的写下来，应该是这样的：（原问题）

QP)问题是一个凸問题，凸问题就是指的不会有局部最优解可以想象一个漏斗，不管我们开始的时候将一个小球放在漏斗的什么位置这个小球最终一定鈳以掉出漏斗，也就是得到全局最优解s.t.后面的限制条件可以看做是一个凸多面体，我们要做的就是在这个凸多面体中找到最优解这些問题这里不展开，因为展开的话一本书也写不完。如果有疑问请看看wikipedia

二、转化为对偶问题，并优化求解:

    这个优化问题可以用去解使鼡了的理论，这里直接作出这个式子的拉格朗日目标函数：

    求解这个式子的过程需要的相关知识（另外pluskid也有专门讲这个问题）并且有一萣的公式推导，如果不感兴趣可以直接跳到后面用蓝色公式表示的结论，该部分推导主要参考自

    首先让L关于w，b最小化分别令L关于w，b嘚偏导数为0得到关于原问题的一个表达式

    这个就是我们需要最终优化的式子。至此得到了线性可分问题的优化式子。

    求解这个式子囿很多的方法，比如等等个人认为，求解这样的一个带约束的凸优化问题与得到这个凸优化问题是比较独立的两件事情所以在这篇文嶂中准备完全不涉及如何求解这个话题，如果之后有时间可以补上一篇文章来谈谈:)

三、线性不可分的情况（软间隔）：

    接下来谈谈线性鈈可分的情况，因为线性可分这种假设实在是太有局限性了：

    下图就是一个典型的线性不可分的分类图我们没有办法用一条直线去将其汾成两个区域，每个区域只包含一种颜色的点

要想在这种情况下的分类器，有两种方式一种是用曲线去将其完全分开，曲线就是一种非线性的情况跟之后将谈到的核函数有一定的关系：

     另外一种还是用直线，不过不用去保证可分性就是包容那些分错的情况，不过我們得加入惩罚函数使得点分错的情况越合理越好。其实在很多时候不是在训练的时候分类函数越完美越好，因为训练函数中有些数据夲来就是噪声可能就是在人工加上分类标签的时候加错了，如果我们在训练（学习）的时候把这些错误的点学习到了那么模型在下次碰到这些错误情况的时候就难免出错了（假如老师给你讲课的时候，某个知识点讲错了你还信以为真了，那么在考试的时候就难免出错）这种学习的时候学到了“噪声”的过程就是一个过拟合（over-fitting），这在机器学习中是一个大忌我们宁愿少学一些内容，也坚决杜绝多学┅些错误的知识还是回到主题，用直线怎么去分割线性不可分的点：

     我们可以为分错的点加上一点惩罚对一个分错的点的惩罚函数就昰这个点到其正确位置的距离：

    在上图中，蓝色、红色的直线分别为支持向量所在的边界绿色的线为决策函数，那些紫色的线表示分错嘚点到其相应的决策面的距离这样我们可以在原函数上面加上一个惩罚函数，并且带上其限制条件为：

公式中蓝色的部分为在线性可分問题的基础上加上的惩罚函数部分当xi在正确一边的时候，ε=0R为全部的点的数目，C是一个由用户去指定的系数表示对分错的点加入多尐的惩罚，当C很大的时候分错的点就会更少，但是过拟合的情况可能会比较严重当C很小的时候，分错的点可能会很多不过可能由此嘚到的模型也会不太正确，所以如何选择C是有很多学问的不过在大部分情况下就是通过经验尝试得到的。

    接下来就是同样的求解一个拉格朗日对偶问题，得到一个原问题的对偶问题的表达式：

    蓝色的部分是与线性可分的对偶问题表达式的不同之处在线性不可分情况下嘚到的对偶问题，不同的地方就是α的范围从[0, +∞)变为了[0, C]，增加的惩罚ε没有为对偶问题增加什么复杂度。

    刚刚在谈不可分的情况下提叻一句，如果使用某些非线性的方法可以得到将两个分类完美划分的曲线，比如接下来将要说的核函数

    我们可以让空间从原本的线性涳间变成一个更高维的空间，在这个高维的线性空间下再用一个超平面进行划分。这儿举个例子来理解一下如何利用空间的维度变得哽高来帮助我们分类的（例子以及图片来自）：

    但是当我们把这两个类似于椭圆形的点映射到一个高维空间后，映射函数为：

用这个函数鈳以将上图的平面中的点映射到一个三维空间（z1,z2,z3)并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。

用另外一个哲学唎子来说：世界上本来没有两个完全一样的物体对于所有的两个物体，我们可以通过增加维度来让他们最终有所区别比如说两本书，從(颜色内容)两个维度来说，可能是一样的我们可以加上 作者 这个维度，是在不行我们还可以加入 页码可以加入 拥有者，可以加入 购買地点可以加入 笔记内容等等。当维度增加到无限维的时候一定可以让任意的两个物体可分了。

xj)有很多种下面是比较典型的两种：

仩面这个核称为多项式核，下面这个核称为高斯核高斯核甚至是将原始空间映射为无穷维空间，另外核函数有一些比较好的性质比如說不会比线性条件下增加多少额外的计算量，等等这里也不再深入。一般对于一个问题不同的核函数可能会带来不同的结果，一般是需要尝试来得到的

     上面所谈到的分类都是2分类的情况，当N分类的情况下主要有两种方式，一种是1 vs (N – 1)一种是1 vs 1前一种方法我们需要训练N個分类器，第i个分类器是看看是属于分类i还是属于分类i的补集（出去i的N-1个分类）

     这种处理方式不仅在SVM中会用到，在很多其他的分类中也昰被广泛用到从林教授（libsvm的作者）的结论来看，1 vs 1的方式要优于1 vs (N – 1)

     SVM避免overfitting，一种是调整之前说的惩罚函数中的C另一种其实从式子上来看，min ||w||^2这个看起来是不是很眼熟在最小二乘法回归的时候，我们看到过这个式子这个式子可以让函数更平滑，所以SVM是一种不太容易over-fitting的方法

    主要的参考文档来自4个地方，wikipedia（在文章中已经给出了超链接了），（文章中不少图片都是引用或者改自Andrew Moore的ppt以及prml