SVM详解(一)

SVM(Support Vector Machine),即支持向量机,号称最优秀的分类算法之一,以其简单的理论构造了复杂的算法,又以其简单的用法实现了复杂的问题。
本文旨在介绍SVM的理论基础如基本思想、用到的数学知识等,是我综合了看到的相关书籍和博客的一个总结,数学推导绝大部分都是手写的,字写的不好请见谅。
之后会再写一篇文章介绍SVM用Python的简单实现、SVM如何进行非线性分类、SVM如何进行多分类。

数学基础

拉格朗日乘数法

先来看这样一个问题:

很显然,我们只需要分别求出f对x1,x2,x3的偏导数,然后令他们都等于0,解出x1,x2,x3即可。
如果我们增加两个约束条件,使得题目变成下面这个样子呢?

对于这样一个带约束条件的极值问题,我们就要用到所谓的拉格朗日乘数法了:

上图是《张宇高等数学18讲》中关于拉格朗日乘数法的定义,即把约束条件都乘上一个各自的系数加到目标函数中去,这样就相当于既考虑了原目标函数,也考虑了约束条件。所以上面这道题的解法为:

KKT条件

上面关于拉格朗日乘数法的讨论中只出现了等式约束条件,但实际问题中约束条件可能为等式约束,也可能为大于号约束、小于号约束,而这三种情况通过变形最终都能转化为两类:约束方程等于0和约束方程小于0.我们来看下面的这个问题:

首先把约束条件转化为等于0或者是小于0的式子,然后将其各自乘以一个系数加到目标函数中去:

对于这样的一个优化问题,我们引入KKT条件:

如果一个优化问题在转变完后变成:

其中g是不等式约束,h是等式约束(像上面那个只有不等式约束,也可能有等式约束)。那么KKT条件就是函数的最优值必定满足下面条件:

  1. L对各个x求导为零;

  2. h(x)=0;

  3. ∑αigi(x)=0,αi≥0

这三个式子前两个好理解,重点是第三个式子不好理解,因为我们知道在约束条件变完后,所有的g(x)<=0,且αi≥0,然后求和还要为0,无非就是告诉你,要么某个不等式gi(x)=0,要么其对应的αi=0。

于是运用KKT条件,则上面那个具体的例子可以得到如下式子:

根据KKT条件,上式中要么g=0,要么α=0,这里两个g两个α,这样我们就需要讨论四种情况:

  1. α1=α2=0,那么看上面的关系可以得到x1=1,x2=−1,再把两个x带到不等式约束,发现第一个就是需要满足(10-1+20=29<0)显然不行,29>0的。舍弃。

  2. g1(x)=g2(x)=0,带进去解得,x1=110/101;x2=90/101,再带回去求解α1,α2,发现α1=58/101,α2=4/101,它们满足大于0的条件,那么显然这组解是可以的。

  3. 其他两种情况再去讨论发现是不行的。

于是我们最后得出这个具体问题的答案是x1=110/101,x2=90/101。
可能你会说,这个问题属于约束条件少的情况,那么如果有10个约束条件,这样就有10个g和10个α,你去给我讨论?多少种组合,不知道,但是换个思路,我们非得去10个一起去讨论?机智的学者想到一种方法,考虑到∑αigi(x)=0这个条件,那么我两个两个讨论不就可以了,比如现在我就讨论α7,α8,让其他的α不变,为什么选或者至少选两个讨论呢,因为这个式子求和为0,改变一个显然是不行的,那就改变两个,你增我就减,这样和可以为0。再问为什么不讨论3个呢?也可以,这不是麻烦嘛,一个俗语怎么说来着,三个和尚没水喝,假设你改变了一个,另外两个你说谁去减或者加使得和为0,还是两个都变化一点呢?不好说吧,自然界都是成双成对的才和谐,没有成三成四的(有的话也少)。

SVM理论基础

现在假设我们有这样一个如图所示的二分类问题:

我们希望找到一个决策面使得两类分开,决策面的表达式为WX+b=0,其中W为系数,b为常数项。那么如何才能找到对应的W和b使得分割的效果最好呢?答案有很多种,比如逻辑回归、牛顿法等,二我们现在所讨论的SVM便是这些方法中的一种。
现在我们反过来思考一下,如果我们已经得到了结果即下图所示的决策面:

那么我们会看到,在这两个类里面,总能各自找到离这个决策面最近的点。现在定义一下离这个决策面最近的点到这个决策面(线)的距离分别为d1,d2,令D=d1+d2。那么SVM找最优权值的策略就是,先找到最边上的点,再找到这两个距离之和D,然后求解D的最大值,想想如果按照这个策略是不是可以实现最优分类,是的。
再深入一点思考我们会发现,我们可以令d1=d2,因为决策面在两个最近的点间上下移动对分类结果是不会产生影响的。假设两个离分界面最近的点所在的与分界面平行的面(线)分别为WX+b1=0、WX+b2=0,我们可以假设这两个面(线)恰好是分界面上下平移一个单位所形成的,如果不是,那么我们可以将WX+b1=0、WX+b2=0两边同时除以k,使得|b1-b|和|b2-b|恰好都等于1.这样做对决策面的影响无非就是W变化到w1,b变到b1,我再让w=w1,b=b1,不是又回到了起点吗,也就是说,这个中间无非是一个倍数关系。
那么现在决策面上下两个离得最近的点到决策面的距离之和的表达式为:

根据前面所说的SVM的基本思想,我们现在要求的就是D的最大值,等价于求0.5WTW的最小值(WT为W的转置),乘上一个系数0.5是为了后面计算方便。最终我们得到的带约束条件的需要优化的问题便是:

约束条件是由前面假设得出的,其中yi表示样本点是正类还是反类,正类的yi=1,反类的yi=-1,即在决策面上方的样本点yi=1,在决策面下方的样本点yi=-1(这也是为什么SVM在使用之前为什么要把两类标签设置为+1,-1,而不是0,1等等之类的了)。把约束条件换成小于等于0的形式并引入拉格朗日乘数法,:

松弛变量

前面的推导都是在正负两类完全线性可分的基础上进行的,但如果出现以下情况:

正负两类的最远点没有明显的分解面,搞不好正类的最远点反而会跑到负类里面去了,负类最远点跑到正类里面去了,要是这样的话,你的分界面都找不到,因为你不可能找到将它们完全分开的分界面。在实际情况中这种情形是有的,就是一些离群点或者噪声点,因为这一些点导致整个系统用不了。当然如果不做任何处理确实用不了,但是我们处理一下就可以用了。SVM考虑到这种情况,所以在上下分界面上加入松弛变量ϵi,认为如果正类中有点到上界面的距离小于ϵi,那么认为他是正常的点,哪怕它在上界面稍微偏下一点的位置,同理下界面。还是以上面的情况,我们目测下的是理想的分解面应该是下面这种情况:

如果按照这种分会发现4个离群点,他们到自己对应分界面的距离表示如上,理论上讲,我们给每一个点都给一个自己的松弛变量ϵi,如果一个分界面求出来了,那么比较这个点到自己对应的界面(上、下界面)的距离是不是小于这个值,要是小于这个值,就认为这个界面分的可以,比如上面的ϵ3这个点,虽然看到明显偏离了正轨,但是计算发现它的距离d小于等于我们给的ϵ3,那么我们说这个分界面可以接受。你可能会说那像上面的ϵ10,距离那么远了,他肯定是大于预设给这个点的ϵi了对吧,确实是这样的,但是我们还发现什么?这个点是分对了的点呀,所以你管他大不大于预设值,反正不用调整分界面。需要调整分界面的情况是只有当类似ϵ3这样的点的距离大于了ϵ3的时候。
因为松弛变量的加入,导致每个点的约束条件就变化了点,我们在原来的需要优化的变量和新的约束条件的基础上重新进行如下推导:

分享