SVM入门SVM的八股简介

支持向量机(Support Vector Machine)是 Cortes 和 Vapnik 于 1995 年首先提出的， 它在解决小样本、 非线性及高维模式识别中表现出许多特有的优势， 并能够推广应用到函数拟合等其他机器学习问题中1.SVM入门(一)SWM的八股简介支持向量机( Support vector machine)是 Cortes和 Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现岀许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中[10]。支持向量机方法是建立在统计学习理论的vC维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度, Accuracy)和学习能力(即无错误地识划任意样本的能力)之间寻求最佳折衷,以期获得最好的推广能力[14](或称泛化能力)。以上是经常被有关SⅦM的学术文献引用的介绍,有点八股,我来逐一分解并解释一下。vapnik是统计机器学习的大牛,这想必都不用说,他出版的《 Statistical learningTheory》是一本完整阐述统计机器学习思想的名著。在该书中详细的论证了统计机器学习之所以区别于传统机器学习的本质,就在于统计机器学习能够精确的给山学习效果,能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比,传统的机器学习基本上属于摸着石头过河,用传统的机器学习方法构造分类系统亢全成了一和技巧,一个人做的结果可能很好,另一个人差不多的方法做出来却很差,缺乏指导和原则。所谓VC维是对函数类的种度量,可以简单的坦解为问题的复杂程度,VC维越晑,个问题就越复杂。正是因为SⅥM关注的是VC维,后面我们可以看到,SM解决问题的时候,和样本的维数是无关的(甚至样本是上万维的都可以,这使得SWM很适合用来解决文本分类的问题,当然,有这样的能力也因为引入了核函数)。结构风险最小听上去文绉绉,其实说的也无非是下面这回事。机器学习本质上就是一种对问题真实模型的逼近(我们选择一个我们认为比较好的近似模型,这个近似模型就叫做个假设),但亳无疑问,真实模型“定是不知道的(如果知道了,我们干吗还要机器学习?直接用真实模型解决问题不就可以了?对吧,哈哈)既然真实模型不知道,那么我们选择的假设与问题真实解之间究竟有多大差距,我们就没法得知。比如说我们认为宇宙诞生于150亿年前的一场大爆炸,这个假改能够描述很多我们观察到的现象,但它与真实的宇宙模型之间还相差多少?谁也说不清,因为我们压根就不知道真实的宇宙模型到底是什么这个与问题真实解之间的误差,就叫做风险(更严格的说,误差的累积叫做风险)。我们选择」一个假设之后(更直观点说,我们得到了一个分类器以后),真实误差无从得知,但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与頁实结果(因为样本是已经标注过的数据,是准确的数据)之间的差值来表示这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的日标,但后来发现很多分类函数能够在样本集上轻易达到100%的正确率,在真实分类时却塌糊涂(即所诮的推广能力差,或泛化能力差)。此时的情况便是选择∫一个足够复杂的分类函数(它的VC维很高),能够精确的记住每一个样本,但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现,此原则适用的大前提是经验风险要确实能够逼近真实风险才行(行话叫一致),但实际上能逼近么?答案是不能,因为样木数相对」现实世界要分类的文本数来说简直九一毛,经验风险最小化原则只在这占很小比例的样本上做到没有误差,当然不能保证在更来例的真实文本上也没有误差。统计学习因此而引入了泛化误差界的概念,就是指真实风险应该由两部分内容刻画是经验风险,代表了分类器在给定样木上的误差;二是置信风险,代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。很显然,第二部分是没有办法精确计算的,因此只能给出·个估计的区间,也使得整个误差只能计算上界,而无法计算准确的值(所以叫做泛化误差界,而不叫泛化误差)。置信风险与两个量有关,一是样木数量,显然给定的样木数量越大,我们的学习结果越有可能正确,此时置信风险越小;二是分类函数的VC维,显然VC维越人,推广能力越差,置信风险会变大。泛化误差界的公式为:R(w)≤Remp(w)+(n/h)公式中R(w)就是真实风险,Remp(w)就是经验风险,Φ(n/h)就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小,即结构风险最小SⅧM正是这样种努力最小化结构风险的算法SWM其他的特点就比较容易理解了。小样本,并不是说样本的绝对数量少(实际上,对任何算法来说,更多的样本几乎总是能带来更好的效果),而是说与问题的复杂度比起来,SⅥM算法要求的样本数是相对比较少非线性,是指SWM擅长应付样木数据线性不可分的情况,主要通过松弛变量(也有人叫惩罚变量)和核函数技术来实现,这一部分是SwM的精髓,以后公详细讨论。多说一句,关于文本分类这个问题究竞是不是线性可分的,尚没有定论,因此不能简单的认为它是线性可分的而作简化处理,在水落石出之前,只好先当它是线性不可分的(反正线性可分也不过是线性不可分的一种特例而已,我们向来不怕方法过于通用)。高维模式识别是指样本维数很高,例如文本的向量表示,如果没有经过另一系列文章(《文本分类入门》)中提到过的降维处理,出现几万维的情况很正常,其他算法基本就没有能力应付了,SWM却可以,主要是因为SWM产生的分类器很简洁,用到的样本信息很少(仅仅用到那些称之为“支持向量”的样本,此为后话),使得即使样本维数很高,也不会给存储和计算带来大麻烦(相对照而言,kN算法在分类时就要用到所有样本,样本数巨大,每个样本维数再一高,这日子就没法过了………)。节开始正式讨论SWM。别嫌我说得太详细哦2.SM入门线性分类器之二&之三21.SⅥM入门(二)线性分类器Part1线性分类器(一定意义上,也可以叫做感知机)是最简单也很有效的分类器形式在一个线性分类器中,可以看到SWM形成的思路,并接触很多SVM的核心概念.用一个二维空间里仅有两类样本的分类问题来举个小例子。如图所示C1和C2是要区分的两个类别,在二维平面中它们的样如上图所示。中间的直线就是一个分类函数,它可以将两类样本完全分开。一般的,如果一个线性函数够将样本完全正确的分开,就称这些数据是线性可分的,否则称为丰线生可分的什么叫线性函数呢?在一维空间里就是一个点,在二维空间里就是一条直线,三维空间里就是个平面,可以如此想象下去,如果不关注空间的维数:这种线性函数还有一个统一的名称一一超平面( Hyper Plane)实际上,一个线性函数是一个实值函数(即函数的值是连续的实数),而我们的分类问题(例如这里的二元分类问题一一回答一个样本属子还是不属于一个类别的问题)需要离散的输出值,例如用1表示某个样本属于类别CL,而用0表示不属于(不属于C1也就意味着属于C2),这时候只需要简单的在实值函数的基础上附加一个阈值即可,通过分类函数执行时得到的值人于还是小于这个阈值来确定类别归属例如我们一个线性函数g()=WX+我们可以取阈值为0,这样当有一个样本xi需要判别的时候,我们就看g(xi)的值。若g(xi)>0,就判别为类别C,若g(xi)<0,则判别为类别C2(等于的时侯我们就拒绝判断,呵呵)。此时也等价于给函数g(x)附加一个符号函数gn(),即r(x)=sg[g(x)]是我们真正的判别函数关于g(x)=Wx+b这个表达式要注意三点:一,式中的x不是二维坐标系中的横轴,而是样本的向量表示,例如个样本点的坐标是(3,8),则xI=(3,8),而不是x=3(一般说向量都是说列向量,因此以行向量形式来表小时,就加上转置)。二,这个形式并不局限于二维的情况,在n维空间中仍然可以使用这个表达式,只是式中的w成为了n维问量(在二绯的这个例了中,w是二维向量,注意这里的w严格的说乜应该是转置的形式,为∫表示起来方便简洁,以下均不区别列向量和它的转置,聪明的读者一看便知);三,g(x)不是中间那条直线的表达式,中间那条直线的表达式是g(x)=0,即wx+b=0,我们也把这个数叫做分类面。实际上很容易看出来,中间那条分界线并不是唯一的,我们把它稍微旋转一下,只要不把两类数据分错,仍然可以达到上面说的效果,稍微平移一下,也可以。此时就牵涉到一个问题,对同一个问题存在多个分类函数的时候,哪个函数更好呢?显然必须要先找一个指标来量化“好”的程度,通常使用的都是叫做“分类间隔”的指标。下一节我们就仔细说说分类间,出补一补相关的数学知识。22SⅥM入门(三)线性分类器Part2上回说到对于文本分类这样的不适定问题(有一个以上解的问题称为不适定叵题),需要有一个指标来衡量解决方案(即我们通过训练建立的分类模型)的好坏,而分关间隔是一个比较好的指标左进行文木分类的时候,我们可以让计算机这样来看待我们提供给它的训练样木,每一个样本由一个向量(就是那些文本征所组成的问量)和一个标记(标示出这个样本属于哪个类別)组成。如下xi就是文本向量(维数很高),yi就是分类标记在二元的线性分类中,这个表示分英的标记只有两个值,1和-1(用来表示属丁还是不属丁这个类)。有了这种表示法,我们就可以定义一个样木点到某个超平面的问隔:8 i=yi(wxi+b)这个公式乍一看没什么袒秘的,也说不出什么道理,只是个定义而己,但我们做做变揆,就能看吕一些有意思的东西首先注意到如果某个样本属于该类别的话,那么wxi+b>0(记得么?这是因为我们所选的g(x)=wx+b就通过大于0还是小于0来判断分类),而yi也大于0;若不属于该类别的活,那么wxi-o<0,而yi也小于0,这意味着yi(wxi+b)总是大于0的,而且它的值就等于wxi+b!(世就是|g(xi))现在把w和b进行一下归一化,即用w/W和b/w分别代替原来的w和b,那么间隔就可以写成1&=Ig(rI这个公式是不是看上去有点眼熟?没错,这不就是解析几何中点xi刭直线g(x)=0的距离公式嘛!(推广一下,是到超平面g(x)=0的距离,g(x)=0就是上节屮提到的分类超平面)小Tips:|W是什么符号?|w|叫做向量w的范数,范数是对向量长度的一种度量。我们常说的向量长度其实指的是它的2-范数,范数最一般的表示形式为p-范数,可以写成如下表达式向量v=(w1,w2,w3,……wn)它的p范数为lo《呵+n2+香看看把p换成2的时候,不就是传统的向量长度么?当我们不指明p的时候,就像|w这样使用时,就意味着我们不关心p的值,用几范数都可以:或者上文已经提到了p的值,为了叙述方便不再重复指明当用归一化的w和b代替原值之后的间隔有一个专门的名称,叫做几何间隔,几何间隔所表示的正是点到超平面的欧氏距离,我们下面就简称几何间隔为“距离”。以上是单个点到某个超平面的距离(就是间隔,后面不再区别这两词)定义,同样可以定义一个点的集合(就是一组样本)到某个超平面的距离为此集合中离超平面最近的点的距离下面这张图更加直观的展示出了几何间隔的玩实含义:margin=2/ w图2线性可分情况下的最优分表线Ⅱl是分类面,而Ⅲ和2是平行于H,且过离H最近的两类样本的直线,H与H,H2与H之间的距离就是几何间隔。之所以如此关心儿何回隔这个东西,是因为儿何间隔与样本的误分次数问存在关系:误分次数≤2A其中的6是样本集合到分类面的间隔,R=max||xi1,,n,即R是所有样本中(xi是以同量表示的第i个样本)向量长度最长的值(也就是说代表样本的分布有多么广)。先不必追究误分次数的具体定义和导过程,只要记得这个误分次数一定程度上代表分类器的误差。而从上式可以看出,误分次数的上界由儿何向隔决定!(当然,是样本已知的时候)至此我们就明白为何要选择几何间隔来作为评价一个解优劣的指标了,原来几何间隔越大的解,它的误差上界越小。因此最大化几何间隔成」我们训练阶段的目标,而且,与二把刀作者所写的不同,最大化分类间混并不是SW的专利,而是早在线性分类时期就已有的思想3.SVM入门线性分类器的求解之四&之五31SVM入门四)线性分类器的求解—问题的描述Part1上节说到我们有了一个线性分类函数,也有了判断解优劣的标准一一即有了优化的目标,这个目标就是最大化几何间隔,但是看过一些关于SWM的论文的人一定记得什么优化的目标是要最小化|w这样的说法,这是怎么回事呢?回头再看看我们对间隔和几何间隔的定义:叫隔:8=y(wx+b)=g(x)Ig(r)几何问隔可以看出8=w8儿何。注意到儿何间隔与|w|是成反比的,因比最大化儿何间隔与最小化|w完全是一回事。而我们常用的方法并不是固定|w的大小而寻求最大几何间隔,而是固定间隔(例如固定为1),寻找最小的w|而凡是求—个函数的最小值(或最大值)的问题都可以称为寻优问题(也叫作一个规划问题),又由丁找最大值的问题总可以通过加一个负号变为找最小值的问题,因此我们下面讨论的时候都针对找最小值的过程来进行。一个寻优问题最重要的部分是目标函数,顺名思义,就是指寻优的目标。例如我们想寻找最小的w这件事,就可以用下面的式子表小:但实际上对于这个目标,我们常需使用另一个完全等价的目标数来代昔,那就是;不难看当w2达到最小时,|w|也达到最小,反之亦然(前提当然是|w|描述的是向量的长度,因而是非负的)。之所以采用这种形式,是因为后面的求解程会对目标函数作一系列变换,而式(1)的形式会使变换后的形式更为简洁(正如聪明的读者所料,添加的系数二分之一和平方,皆是为求导数所需)。接下来我们白然会问釣就是,这个式子是否就述了我们的河题呢?(回想一下,我们的问题是有一堆点,可以被分成两类,我们要找出最好的分类由)如果直接来解这个求最小值问题,很容易看出当|w|-0的时候就得到了目标函数的最小值。但是你也会发现,无论你给什么样的数据,都是这个解!反映在图中,就是H与H两条直线间的距离无限大,这个时侯,所有的样本点(无论正样本还是负样本)都跑到了H和H2屮间,而我们原本的意图是,H右侧的被分为正类,H2左侧的被分为负类位于两类中间的样本则扣绝分类(扣绝分类的另一种珒解是分给哪一类都有道珙,因而分给哪一类也都没有道理)。这下可好,所有样本点都进入了无法分类的灰色地带HIH图2线性可分情况下的最优分类线造成这种结果的原因是在描述问题的时候只考虑了目标,而没有加入约束条件,约束条件就是在求解过程中必缜满足的条件,体现在我们的问题中就是样本点必须在H或H2的某一侧(或者至少在H1和H2上),而不能跑到两者中间。我们前文提到过把间隔固定为1,这是指把所有样本点中间隔最小的那一点的间隔定为1(这也是集合的间隔的定义,有点绕嘴),也就意味着集合中的其他点间隔都不会小亍1,按照间隔的定义,满足这些条件就相当丁让下面的式子总是成立:yi[(w·xi)+b]≥1(i=1,2,…,1)(1是总的样本数)但我们常常习惯让式了的值和0比较,因而经常用变换过的形式i[(w·xi)+b]-1≥0(i=1,2,…,1)(1是总的样本数)因此我们的两类分类问题也被我们转化成了它的数学形式,一个带约束的最小值的问题LILsabject to yI(wr)b-120612.-D0是样本数。下一节我们从最一般的意义上看看一个求最小值的题有何持征,以及如何来解。32SⅥM入门(五)线性分类器的求解一问题的描述Par2从最一般的定义上说,一个求最小值的问题就是一个优化问题(也叫寻优问题,更文绉绉的叫法是规划Programming),它叵样由两部分组成,目标函数和约束条件,可以用下面的式表示:fusubjectto c(x)≤0i=12-Dc, C=0 ip+lp+2式1约束条件用函数c来表示,就是 constrain的意思啦。你可以看出一共有p+q个约束条件,其中p个是不等式约束,q个等式约束。关于这个式子可以这样来理解:式中的x是自变量,但不限定它的维数必须为1(视乎你解决的问题空间维数,对我们的文本分类来说,那可是成干上万啊)。要求f(x)在哪一点上取得最小值(反倒不太关心这个最小值到底是多少,关键是哪一点),但不是在整个空问里找,而是在约束条件所划定的一个有限的空间里找,这个有限的空间就是优化理论里所说的可行域。注意可行域中的每一个点都要求满足所有p+q个条什,而不是满足其中一条或几条就可以(切记,要满足每个约束),同时可行域边界上的点有一个额外好的特性,它们可以使不等式约束取得等号!而边界内的点不行。这对一·般的优化问题可能提供不了什么帮助,但对我们的swM来说,边界上的点有其特殊意义,实际上是它们唯一的决定了分类超平面,这些点(想象他们就是以前的图中恰好落在H和H2上的点,在文本分类问题中,每一个点代表一个文档,因而这个点本身也是一个向量)就被称为支持向量关于可行域还有个概念不得不提,那就是凸集,凸集是指有这么一个点的集合,其中任取两个点连一条直线,这条线上的点仍然在这个集合内部,因此说“凸”是很形象的(一个反例是,二维平血上,一个月牙形的区域就不是凸集,你随便就可以找到两个点违反了刚才的规定)。回头再来看我们线性分类器问题的描述,可以看出更多的东西。subjectto y[)-120612-D是样种(式2)左这个问题中,自变量就是w,而目杯数是w的二次响数,所有的约束条件都是w的线性凶数(哎,千万不要把当成变量,它代表样本,是已知的),这种规划问题有个很有名气的称呼—一一次规划( Quadratic programminGQP),而且可以更进一步的说,由于它的可行域是一个凸集,因此它是一个凸二次规划。下子提了这么多术语,实在不是为了让大家以后能向别人炫耀学识的渊博,这其实是我们继续下去的一个重要前提,因为在动手求一个问题的解之前(女吧,我承认,是动计算机求……),我们必须先间自己:这个问题是不是有解?如果有解,是否能找到?对于·意义上的规划问题,两个问趑的答案都是不一定,但凸二次规划让人喜欢的地方就在于,它有解(教科书里面为了严谨,常常加限定成分,说它有全局最优解,由于我们想找的木来就是全局最优的解,所以不加也罢),而且可以找到!(当然,依据你使用的算法不同,找到这个解的速度,行话叫牧敛速度,会有所不司)对比(式2)和(式1)还可以发现,我们的线性分类器问题只有不等式约束,因此形式上看似乎比一般意义上的规划问题要简单,但解起来却并非如此因为我们实院上并不知道该怎么解一个带约束的优化问题。如果你仔细回忆一下高等数学的知识,会记得我们可以轻松的解一个不带任何约束的优化问题(实际上就是当年背得烂熟的函数求极值嘛,求导冉找0点呗,谁不会啊?笑),我们甚至还会解一个只带等八约東釣忧化问题,也是背得烂熟的,求条件极值,记得么,通过添加拉恪朗日乘子,构造拉格朗日函数,来把这个问题转化为无约束的优化问题云云(如果你一时没想通,我湜龔一卜,构造H的拉格朗日旳数就是转化之后的问题形式,它显然没有带任何条件)