·绪论

这篇是我学习机器学习过程中写的一篇笔记，篇幅较长，特意单独作为一篇提取出来。支持向量机涉及到大量统计学的数学理论知识等，网上的教程大多晦涩难懂，让人看得头晕。支持向量机是属于机器学习中的一个难点，我觉得有必要专门写一篇总结，希望用通俗简单的语言说明白支持向量机是如何运作的。经过长时间的学习摸索后，我写下本文，希望能化繁为简，从一个不一样的角度写明白支持向量机的工作原理。

本文从一个实际问题出发，――二维点坐标线性可分问题的求解，一步步顺着SVM的思路推导，最终是把实现二维线性可分问题的求解完全梳理和推导了一遍。但是奈何精力有限，更复杂的问题（例如多维线性不可分问题）本文就不作详细推导了，因为那还涉及到超平面、核函数等知识，详细推导下来太复杂了。不过，本文会推荐许多写得不错的博文链接，感兴趣的读者可以去深究一下。

 

------------------下面是正文-----------------

 

【目标】

   在一个二维平面中，存在两类点（蓝点和黑点），它们线性可分，现需要找到一条直线，使得这两类点分别位于直线的两侧，且这条直线到两侧点的最短距离尽可能远。

 

【建模】

1)目标函数

    我们假设目标直线方程y=ax+b ，我们用向量来表示，就是：，把向量（a，-1）用向量符号w来表示，维数向量（x，y用向量符号x来表示。那么直线方程就变成了w・x+b=0。

目标是要求点到直线的距离，回顾一下点到直线的距离公式：直线（一般式）：Ax＋By＋C＝0,另外一个点的坐标(x0, y0)。那么这点到这直线的距离就是：

d=

    现在把它换到向量方程中去，对于直线w・x+b=0，有d=,

    把向量换成二范数的形式，即是：

d=

  所以二维线性可分问题的目标函数就能够抽象成以下的数学表达式：

    但是，这样的目标函数有些复杂，我们可以进行简化。

    如下图，我们作两条直线，和分类直线平行。让这两条直线分别经过以下蓝色和黑色集合的边界，那么这两条直线到中间分类直线的距离相等，于是，我们能够假定这两条直线方程各自是w・x+b=c, w・x+b=-c。

    回顾两条平行直线的距离计算公式d=，那么两类点到分类直线的最近距离都是d==

对于一条直线，w・x+b=c，我们对应的成比例的缩小他们的系数，如变成・x+= ,这条直线和原来的直线还是同一条直线。如今把它变成・x+==1，新的直线还是和曾经直线是同一条直线。也就是说，对于直线w・x+b=c，我们总能够找到另外的一条新的 w1=w/c, b1=b/c。使w1・x+b1=1, 并且这两条直线事实上表达的是同一条直线，这样的话，上面的图就能够变成如下的图：

这样，我们所要寻找的最优分类直线――到两类点集合的距离最大的直线，就能够抽象成如下的目标函数：（w1与w同为待求变量，故依然用w表示，b1也用b表示）

=

 

2)目标函数的约束条件

    对蓝色样本点而言，不在w1・x+b1=1直线上的点。一定是在直线上面的点，它们满足w1・x+b1>1，所以对全部的蓝色样本点而言，它们都满足w1・x+b1>=1。同理，对全部黑色的样本点，都是满足w1・x+b1<=-1。

这两个条件是我们求解的限制条件，也就是我们寻找上面的目标函数的时候，必须满足上面的两个不等式约束。

      满足约束：

    我们可以把上式的两个不等式条件表达式合并成一个式子。对于上面蓝色点相应的不等式，我们在不等式两边同时乘以一个y=1；同理，黑色点相应的不等式在式子两边同乘以一个y=-1。 那么上面的两个式子能够变成：

    而这儿的y值之所以能够取不同的值，是因为，y其实是来自训练样本点的另一个已知的类别标记量label值,也就是说，对蓝色点的label值我们人为将其定义为1，而对黑色点的label值我们定义为-1这样子。

    到此，我们的目标函数就写成了：

 s.t.  y・(w・x+b)>=1

（s.t.即为subject to,表示受限于）

 

【求解】

    我们接下来就开始正式求解上面的带不等式条件的优化问题了！

 

1）    把原始问题化成对偶问题

首先考虑之前得到的目标函数：

   s.t.  y・(w・x+b)>=1

由于求的最大值相当于求最小值，所以上述目标函数等价于：

    s.t.  y・(w・x+b)>=1

为什么要这样转化呢？其实是一种技巧，因为求最值一般会求偏导数，而求导的结果就是x，会让结果式子比较好看。

因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。由于这个问题的特殊结构，可以通过拉格朗日对偶性变换到对偶变量的优化问题（其实就是把原始问题进一步转化）。

我们先来了解一下拉格朗日函数：通过给每一个约束条件加上一个拉格朗日乘子a，整合到原始式当中，便形成了拉格朗日函数，它只用一个表达式便清楚完整地表达出我们的问题，所以令：

   然后令       

θ(w)=

   容易验证，当某个约束条件不满足时，例如<1，那么显然有θ(w)=∞（只要令即可）。而当所有约束条件都满足时，则最优值为θ(w)=，亦即最初要最小化的量，这便是使用拉格朗日函数的目的！

    因此，在要求约束条件得到满足的情况下最小化，实际上等价于直接最小化θ(w)。具体写出来，目标函数变成了：

    如果对上式直接求解，那么一上来便得面对w和b两个参数，而又是不等式约束，这个求解过程不好做，于是我们可以把最小和最大的位置交换一下，变成：

   交换以后的新问题是原始问题的对偶问题，在凸二次线性规划问题下，它与原问题是等价的(满足强对偶下的KKT条件)，证明过程大致说一下（因为我不懂~~）：

    KKT条件的成立要满足constraint qualifications，而constraint qualifications之一就是Slater条件。所谓Slater 条件，即指：凸优化问题，如果存在一个点x，使得所有等式约束都成立，并且所有不等式约束都严格成立（即取严格不等号，而非等号），则满足Slater 条件。对于此处，Slater 条件成立。

 

这样我们便将原始问题化成了优化问题：

求。

 

2）    对偶问题的求解

已知 

    因为求极值，我们分别令：

=0 , =0

有：         （1）

                  （2）

   其中，对于求导的结果是w而不是||w||，是因为：假如w=（w1,w2,w3），那么，分别对w1，w2，w3求导就是（w1，w2，w3）=w。

   将（1）（2）式带入到L中，有：（因为计算过程太复杂，word打字麻烦，我用手写的推导式）

    最后我们得到：

    由此可见，此时的拉格朗日函数只包含了一个变量，那就是，下面我们求的极大值，即：

(

s.t.    ≥0，i=1,2,……n

   我们在接下来将会用SMO算法求解这一极值{PS：SMO算法看起来真的是极其复杂，但是抽离掉它表象繁复的数学公式，去领会它的核心数学思想，会发现这其实是一种高级的迭代算法。。我尽可能用通俗的语言把它的算法给说明白。。}

    把上述拉格朗日函数再转化一下，即原问题等价于：

(

s.t.    ≥0，i=1,2,……n

    加入一些松弛变量(目的是扩大求解可行域)后，原模型修改为：

    s.t.  y・(w・x+b)>=1-

0≤≤C ，i

    从而最终我们的问题变为：

(

s.t.    0≤≤C，i=1,2,……n

 

    上述表达式中K（）函数是一个核函数方法，它是一种在特征空间中直接计算内积的方法。原理是做一个映射，把二维向量的计算转移到三维甚至更高维去，使得其像在原始输入点的函数中一样能直接求解。比如在这里，

K（）=<>,其中是从x到内积特征空间F的映射。但核函数实在是太复杂了，它涉及到超平面知识，等我有精力了再去好好学学。。在这儿我们先把的内积标记为K（）吧。

下面我们要解决的问题是：在上求上述目标函数的最小值.接下来我尽可能清楚地阐述一下SMO算法求解的核心思路，这是解决上述二维线性可分问题最重要的部分：

    每次从a中任意抽取两个乘子，例如和，然后固定和以外的其它乘子，使得目标函数只是关于和的函数。为了求出最好的和，把当前找到的和记为和，通过迭代算法（后文会具体给出）去寻找更好的和去替代和。这样，不断的从一堆乘子中任意抽取两个求解，并不断的迭代求解子问题，最终达到求解原问题的目的。

   因此，原对偶问题子问题的目标函数，我们就可以把只含的式子记为常数，剩下的就只是关于和的函数：

ψ=

    其中

= K（） ,

    上式ψ的结果推导我大致手写一下：

 

    为了解决这个子问题，首要问题便是每次如何选取和。

    根据KKT条件（即约束条件）可以得出目标函数中取值的意义：

    这个意义很好理解:表明是正常分类，在间隔边界外部（我们知道正确分类的点）；表明是支持向量，在间隔边界上；表明在两条间隔边界线之间。

    而最优解需要满足KKT条件，即上述3个条件都满足，所以以下几种情况出现将会出现不满足：

• <=1但是<C，则是不满足的，而原本=C
• >=1但是>0，则是不满足的，而原本=0
• =1但是=0或者=C则是不满足的，而原本应该是0<<C

也就是说，如果存在不满足KKT条件的，那么需要更新这些，这是第一个约束条件。此外，更新的同时还要受到第二个约束条件的限制，即

因此，如果假设选择的两个乘子和，它们在更新之前分别是、，更新之后分别是、，那么更新前后的值需要满足以下等式才能保证和为0的约束：

    其中，是常数，因为从i=3开始就视为常数。

    两个因子不好同时求解，所以可先求第二个乘子的解，得到的解之后，再用的解表示的解。

为了求解，得先确定的取值范围。假设它的上下边界分别为H和L，那么有：

L≤≤H

    接下来，综合0≤≤C，i=1,2,……n和这两个约束条件，求取的取值范围。

当 != 时，根据可得，所以有L=max(0,)，H=min(C,C)（因为且0≤≤C）。如下图所示：

当 = 时，同样根据可得，所以有L=max(0,)，H=min(C,)，如下图所示：

    如此，根据和异号或同号，可得出的上下界分别为：

    回顾下第二个约束条件，令其两边乘以，可得：

其中w=- ，这是因为，而w=。

因此可以用表示，，从而把子问题的目标函数转换为只含的问题：

ψ=

对求导，可得

=

化简下：

=s(

然后将s=,和 代入上式,手写计算如下：

   （其实在的计算中我感觉是有些问题的，求大神指教。。）

    所以有()()=

令（表示预测值与真实值之差），, 然后上式两边同时除以，得到一个关于单变量的解：

    这个解没有考虑其约束条件0≤≤C，即是未经剪辑时的解。

然后考虑约束0≤≤C可得到经过剪辑后的的解为：

求出了后，便可以求出,得。那么如何选择一开始的乘子和呢？

• 对于，即第一个乘子，可以通过刚刚说的那3种不满足KKT的条件来找；
• 而对于第二个乘子可以寻找满足条件：max||的乘子。

而b在满足下述条件：

下更新b：

=

=

    且每次更新完两个乘子的优化后，都需要再重新计算b，及对应的值。

最后更新所有，y和b，这样模型就出来了，从而即可求出咱们开头提出的分类函数：

其中。

 

【总结】

    花了五天时间，终于把支持向量机解决二维线性可分问题的数学算法从头至尾过了一遍，写一篇总结是极有必要的，毕竟算法中蕴含的数学思维很值得被提取。

其实支持向量机的建模过程并不是很难理解，本质上就是规划问题的数学抽象，即建立一个数学公式表示出待求的目的函数（如最大距离的最小值），然后加上约束条件，便完成了建模。

接下来便是将目的函数进行优化，优化有好多好多种，在上文的算法中，我们可以看到，首先是减变量优化，比如点到间隔界线的距离c直接换成1不影响最后求解结果；还有把约束条件两边同乘以y就能将两个约束条件化为一个；再后来目的问题的转化也是关键，比如求的最大值等价于求的最小值，从而转化为一个凸二次规划问题的求解，以及min(max(f))转化为对偶问题max(min(f))等，这些手段都是为了能更好的求解。

最后便是最重要的求解过程。对于规划问题的求解，拉格朗日算法是极其实用的，它通过建立一个拉格朗日函数便将所有的规划条件和求解目的囊括在了一个式子中。而在本例中我们采用了SMO算法去求解这个拉格朗日函数。其实就我的理解来说，SMO算法更是一个计算机算法而不是一个数学算法，因为它不是用一个数学公式直接给出解，而是通过大量的迭代计算去一步步“逼近”最佳解，这一工作量只有计算机才能去完成。但是SMO巧妙的部分在于，它每次都假定只取两个变量，其他变量视为常数，不断地去找到更好的变量去取代原有的两个变量，这样每迭代一次我们找出的曲线就一定会有“进步”，最后当这一曲线逼近一条恒定的分界线时，我们就可以停止迭代，找到目标分界线了。值得一提的是，为什么SMO每次只取两个变量而不是三个或四个呢？从理论上来说，我们取三个或四个变量不断地迭代逼近最佳曲线也能求解出最终解，但是，线性分类器中的数学关系和逻辑，在两个变量中是最好找的，这个在本文的数学推导中已经非常清晰明了，相反，如果是选择三个甚至更多变量，想去判定如何才能满足“更优的解”就不是这么容易了。

这次对支持向量机的初步学习的所得就是上述这么多了，希望以后有时间和精力时再去把多维非线性的问题好好学习理解下，还是挺有意思的。