svm原理_svm原理详解 - CSDN
精华内容
参与话题
  • SVM 原理详解,通俗易懂

    万次阅读 多人点赞 2018-06-01 11:58:28
    转自:http://www.blogjava.net/zhenandaci/category/31868.html(一)SVM的简介支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的...

    看了该作者的文章,瞬间膜拜了!讲得太好了!

    转自:http://www.blogjava.net/zhenandaci/category/31868.html

    (一)SVM的简介

    支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中[10]。 
    支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度,Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,以期获得最好的推广能力[14](或称泛化能力)。

    以上是经常被有关SVM 的学术文献引用的介绍,我来逐一分解并解释一下。

    Vapnik是统计机器学习的大牛,这想必都不用说,他出版的《Statistical Learning Theory》是一本完整阐述统计机器学习思想的名著。在该书中详细的论证了统计机器学习之所以区别于传统机器学习的本质,就在于统计机器学习能够精确的给出学习效果,能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比,传统的机器学习基本上属于摸着石头过河,用传统的机器学习方法构造分类系统完全成了一种技巧,一个人做的结果可能很好,另一个人差不多的方法做出来却很差,缺乏指导和原则。

    所谓VC维是对函数类的一种度量,可以简单的理解为问题的复杂程度,VC维越高,一个问题就越复杂。正是因为SVM关注的是VC维,后面我们可以看到,SVM解决问题的时候,和样本的维数是无关的(甚至样本是上万维的都可以,这使得SVM很适合用来解决文本分类的问题,当然,有这样的能力也因为引入了核函数)。

    结构风险最小听上去文绉绉,其实说的也无非是下面这回事。

    机器学习本质上就是一种对问题真实模型的逼近(我们选择一个我们认为比较好的近似模型,这个近似模型就叫做一个假设),但毫无疑问,真实模型一定是不知道的(如果知道了,我们干吗还要机器学习?直接用真实模型解决问题不就可以了?对吧,哈哈)既然真实模型不知道,那么我们选择的假设与问题真实解之间究竟有多大差距,我们就没法得知。比如说我们认为宇宙诞生于150亿年前的一场大爆炸,这个假设能够描述很多我们观察到的现象,但它与真实的宇宙模型之间还相差多少?谁也说不清,因为我们压根就不知道真实的宇宙模型到底是什么。

    这个与问题真实解之间的误差,就叫做风险(更严格的说,误差的累积叫做风险)。我们选择了一个假设之后(更直观点说,我们得到了一个分类器以后),真实误差无从得知,但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果(因为样本是已经标注过的数据,是准确的数据)之间的差值来表示。这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标,但后来发现很多分类函数能够在样本集上轻易达到100%的正确率,在真实分类时却一塌糊涂(即所谓的推广能力差,或泛化能力差)。此时的情况便是选择了一个足够复杂的分类函数(它的VC维很高),能够精确的记住每一个样本,但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现,此原则适用的大前提是经验风险要确实能够逼近真实风险才行(行话叫一致),但实际上能逼近么?答案是不能,因为样本数相对于现实世界要分类的文本数来说简直九牛一毛,经验风险最小化原则只在这占很小比例的样本上做到没有误差,当然不能保证在更大比例的真实文本上也没有误差。

    统计学习因此而引入了泛化误差界的概念,就是指真实风险应该由两部分内容刻画,一是经验风险,代表了分类器在给定样本上的误差;二是置信风险,代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。很显然,第二部分是没有办法精确计算的,因此只能给出一个估计的区间,也使得整个误差只能计算上界,而无法计算准确的值(所以叫做泛化误差界,而不叫泛化误差)。

    置信风险与两个量有关,一是样本数量,显然给定的样本数量越大,我们的学习结果越有可能正确,此时置信风险越小;二是分类函数的VC维,显然VC维越大,推广能力越差,置信风险会变大。

    泛化误差界的公式为:

    R(w)≤Remp(w)+Ф(n/h)

    公式中R(w)就是真实风险,Remp(w)就是经验风险,Ф(n/h)就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小,即结构风险最小。

    SVM正是这样一种努力最小化结构风险的算法。

    SVM其他的特点就比较容易理解了。

    小样本,并不是说样本的绝对数量少(实际上,对任何算法来说,更多的样本几乎总是能带来更好的效果),而是说与问题的复杂度比起来,SVM算法要求的样本数是相对比较少的。

    非线性,是指SVM擅长应付样本数据线性不可分的情况,主要通过松弛变量(也有人叫惩罚变量)和核函数技术来实现,这一部分是SVM的精髓,以后会详细讨论。多说一句,关于文本分类这个问题究竟是不是线性可分的,尚没有定论,因此不能简单的认为它是线性可分的而作简化处理,在水落石出之前,只好先当它是线性不可分的(反正线性可分也不过是线性不可分的一种特例而已,我们向来不怕方法过于通用)。

    高维模式识别是指样本维数很高,例如文本的向量表示,如果没有经过另一系列文章(《文本分类入门》)中提到过的降维处理,出现几万维的情况很正常,其他算法基本就没有能力应付了,SVM却可以,主要是因为SVM 产生的分类器很简洁,用到的样本信息很少(仅仅用到那些称之为“支持向量”的样本,此为后话),使得即使样本维数很高,也不会给存储和计算带来大麻烦(相对照而言,kNN算法在分类时就要用到所有样本,样本数巨大,每个样本维数再一高,这日子就没法过了……)。

    下一节开始正式讨论SVM。别嫌我说得太详细哦。

    SVM入门(二)线性分类器Part 1

    线性分类器(一定意义上,也可以叫做感知机) 是最简单也很有效的分类器形式.在一个线性分类器中,可以看到SVM形成的思路,并接触很多SVM的核心概念.

    用一个二维空间里仅有两类样本的分类问题来举个小例子。如图所示

    C1和C2是要区分的两个类别,在二维平面中它们的样本如上图所示。中间的直线就是一个分类函数,它可以将两类样本完全分开。一般的,如果一个线性函数能够将样本完全正确的分开,就称这些数据是线性可分的,否则称为非线性可分的。

    什么叫线性函数呢?在一维空间里就是一个点,在二维空间里就是一条直线,三维空间里就是一个平面,可以如此想象下去,如果不关注空间的维数,这种线性函数还有一个统一的名称——超平面(Hyper Plane)!

    实际上,一个线性函数是一个实值函数(即函数的值是连续的实数),而我们的分类问题(例如这里的二元分类问题——回答一个样本属于还是不属于一个类别的问题)需要离散的输出值,例如用1表示某个样本属于类别C1,而用0表示不属于(不属于C1也就意味着属于C2),这时候只需要简单的在实值函数的基础上附加一个阈值即可,通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。 例如我们有一个线性函数

    g(x)=wx+b

    【看到好多人都在问g(x)=0 和 g(x)的问题,我在这里帮楼主补充一下:g(x)实际是以w为法向量的一簇超平面,在二维空间表示为一簇直线(就是一簇平行线,他们的法向量都是w),而g(x)=0只是这么多平行线中的一条。】

    我们可以取阈值为0,这样当有一个样本xi需要判别的时候,我们就看g(xi)的值。若g(xi)>0,就判别为类别C1,若g(xi)<0,则判别为类别C2(等于的时候我们就拒绝判断,呵呵)。此时也等价于给函数g(x)附加一个符号函数sgn(),即f(x)=sgn [g(x)]是我们真正的判别函数。

    关于g(x)=wx+b这个表达式要注意三点:一,式中的x不是二维坐标系中的横轴,而是样本的向量表示,例如一个样本点的坐标是(3,8),则xT=(3,8) ,而不是x=3(一般说向量都是说列向量,因此以行向量形式来表示时,就加上转置)。二,这个形式并不局限于二维的情况,在n维空间中仍然可以使用这个表达式,只是式中的w成为了n维向量(在二维的这个例子中,w是二维向量,为了表示起来方便简洁,以下均不区别列向量和它的转置,聪明的读者一看便知);三,g(x)不是中间那条直线的表达式,中间那条直线的表达式是g(x)=0,即wx+b=0,我们也把这个函数叫做分类面。

    实际上很容易看出来,中间那条分界线并不是唯一的,我们把它稍微旋转一下,只要不把两类数据分错,仍然可以达到上面说的效果,稍微平移一下,也可以。此时就牵涉到一个问题,对同一个问题存在多个分类函数的时候,哪一个函数更好呢?显然必须要先找一个指标来量化“好”的程度,通常使用的都是叫做“分类间隔”的指标。下一节我们就仔细说说分类间隔,也补一补相关的数学知识。

    SVM入门(三)线性分类器Part 2

    上回说到对于文本分类这样的不适定问题(有一个以上解的问题称为不适定问题),需要有一个指标来衡量解决方案(即我们通过训练建立的分类模型)的好坏,而分类间隔是一个比较好的指标。

    在进行文本分类的时候,我们可以让计算机这样来看待我们提供给它的训练样本,每一个样本由一个向量(就是那些文本特征所组成的向量)和一个标记(标示出这个样本属于哪个类别)组成。如下:

    Di=(xi,yi)

    xi就是文本向量(维数很高),yi就是分类标记。

    在二元的线性分类中,这个表示分类的标记只有两个值,1和-1(用来表示属于还是不属于这个类)。有了这种表示法,我们就可以定义一个样本点到某个超平面的间隔:

    δi=yi(wxi+b)

    这个公式乍一看没什么神秘的,也说不出什么道理,只是个定义而已,但我们做做变换,就能看出一些有意思的东西。

    首先注意到如果某个样本属于该类别的话,那么wxi+b>0(记得么?这是因为我们所选的g(x)=wx+b就通过大于0还是小于0来判断分类),而yi也大于0;若不属于该类别的话,那么wxi+b<0,而yi也小于0,这意味着yi(wxi+b)总是大于0的,而且它的值就等于|wxi+b|!(也就是|g(xi)|)

    现在把w和b进行一下归一化,即用w/||w||和b/||w||分别代替原来的w和b,那么间隔就可以写成

    【点到直线的距离,做解析几何中为:  
    D = (Ax + By + c) /sqrt(A^2+B^2)  
    sqrt(A^2+B^2)就相当于||W||, 其中向量W=[A, B];  
    (Ax + By + c)就相当于g(X), 其中向量X=[x,y]。】

    这个公式是不是看上去有点眼熟?没错,这不就是解析几何中点xi到直线g(x)=0的距离公式嘛!(推广一下,是到超平面g(x)=0的距离, g(x)=0就是上节中提到的分类超平面)

    小Tips:||w||是什么符号?||w||叫做向量w的范数,范数是对向量长度的一种度量。我们常说的向量长度其实指的是它的2-范数,范数最一般的表示形式为p-范数,可以写成如下表达式

        向量w=(w1, w2, w3,…… wn)

    它的p-范数为

    看看把p换成2的时候,不就是传统的向量长度么?当我们不指明p的时候,就像||w||这样使用时,就意味着我们不关心p的值,用几范数都可以;或者上文已经提到了p的值,为了叙述方便不再重复指明。

    当用归一化的w和b代替原值之后的间隔有一个专门的名称,叫做几何间隔,几何间隔所表示的正是点到超平面的欧氏距离,我们下面就简称几何间隔为“距离”。以上是单个点到某个超平面的距离(就是间隔,后面不再区别这两个词)定义,同样可以定义一个点的集合(就是一组样本)到某个超平面的距离为此集合中离超平面最近的点的距离。下面这张图更加直观的展示出了几何间隔的现实含义:

    H是分类面,而H1和H2是平行于H,且过离H最近的两类样本的直线,H1与H,H2与H之间的距离就是几何间隔。

    之所以如此关心几何间隔这个东西,是因为几何间隔与样本的误分次数间存在关系:

    其中的δ是样本集合到分类面的间隔,R=max ||xi||  i=1,...,n,即R是所有样本中(xi是以向量表示的第i个样本)向量长度最长的值(也就是说代表样本的分布有多么广)。先不必追究误分次数的具体定义和推导过程,只要记得这个误分次数一定程度上代表分类器的误差。而从上式可以看出,误分次数的上界由几何间隔决定!(当然,是样本已知的时候)

    至此我们就明白为何要选择几何间隔来作为评价一个解优劣的指标了,原来几何间隔越大的解,它的误差上界越小。因此最大化几何间隔成了我们训练阶段的目标,而且,与二把刀作者所写的不同,最大化分类间隔并不是SVM的专利,而是早在线性分类时期就已有的思想。

    SVM入门(四)线性分类器的求解——问题的描述Part1

    上节说到我们有了一个线性分类函数,也有了判断解优劣的标准——即有了优化的目标,这个目标就是最大化几何间隔,但是看过一些关于SVM的论文的人一定记得什么优化的目标是要最小化||w||这样的说法,这是怎么回事呢?回头再看看我们对间隔和几何间隔的定义:

    间隔:δ=y(wx+b)=|g(x)|

    几何间隔:

    可以看出δ=||w||δ几何。注意到几何间隔与||w||是成反比的,因此最大化几何间隔与最小化||w||完全是一回事。而我们常用的方法并不是固定||w||的大小而寻求最大几何间隔,而是固定间隔(例如固定为1),寻找最小的||w||。

    而凡是求一个函数的最小值(或最大值)的问题都可以称为寻优问题(也叫作一个规划问题),又由于找最大值的问题总可以通过加一个负号变为找最小值的问题,因此我们下面讨论的时候都针对找最小值的过程来进行。一个寻优问题最重要的部分是目标函数,顾名思义,就是指寻优的目标。例如我们想寻找最小的||w||这件事,就可以用下面的式子表示:

    但实际上对于这个目标,我们常常使用另一个完全等价的目标函数来代替,那就是:

    (式1)

    不难看出当||w||2达到最小时,||w||也达到最小,反之亦然(前提当然是||w||描述的是向量的长度,因而是非负的)。之所以采用这种形式,是因为后面的求解过程会对目标函数作一系列变换,而式(1)的形式会使变换后的形式更为简洁(正如聪明的读者所料,添加的系数二分之一和平方,皆是为求导数所需)。

    接下来我们自然会问的就是,这个式子是否就描述了我们的问题呢?(回想一下,我们的问题是有一堆点,可以被分成两类,我们要找出最好的分类面)

    如果直接来解这个求最小值问题,很容易看出当||w||=0的时候就得到了目标函数的最小值。但是你也会发现,无论你给什么样的数据,都是这个解!反映在图中,就是H1与H2两条直线间的距离无限大,这个时候,所有的样本点(无论正样本还是负样本)都跑到了H1和H2中间,而我们原本的意图是,H1右侧的被分为正类,H2 左侧的被分为负类,位于两类中间的样本则拒绝分类(拒绝分类的另一种理解是分给哪一类都有道理,因而分给哪一类也都没有道理)。这下可好,所有样本点都进入了无法分类的灰色地带。

    造成这种结果的原因是在描述问题的时候只考虑了目标,而没有加入约束条件,约束条件就是在求解过程中必须满足的条件,体现在我们的问题中就是样本点必须在H1或H2的某一侧(或者至少在H1和H2上),而不能跑到两者中间。我们前文提到过把间隔固定为1,这是指把所有样本点中间隔最小的那一点的间隔定为1(这也是集合的间隔的定义,有点绕嘴),也就意味着集合中的其他点间隔都不会小于1,按照间隔的定义,满足这些条件就相当于让下面的式子总是成立:

        yi[(w·xi)+b]≥1 (i=1,2,…,l) (l是总的样本数)

    但我们常常习惯让式子的值和0比较,因而经常用变换过的形式:

        yi[(w·xi)+b]-1≥0 (i=1,2,…,l) (l是总的样本数)

    因此我们的两类分类问题也被我们转化成了它的数学形式,一个带约束的最小值的问题:

    下一节我们从最一般的意义上看看一个求最小值的问题有何特征,以及如何来解。

    SVM入门(五)线性分类器的求解——问题的描述Part2

    从最一般的定义上说,一个求最小值的问题就是一个优化问题(也叫寻优问题,更文绉绉的叫法是规划——Programming),它同样由两部分组成,目标函数和约束条件,可以用下面的式子表示:

    (式1)

    约束条件用函数c来表示,就是constrain的意思啦。你可以看出一共有p+q个约束条件,其中p个是不等式约束,q个等式约束。

    关于这个式子可以这样来理解:式中的x是自变量,但不限定它的维数必须为1(视乎你解决的问题空间维数,对我们的文本分类来说,那可是成千上万啊)。要求f(x)在哪一点上取得最小值(反倒不太关心这个最小值到底是多少,关键是哪一点),但不是在整个空间里找,而是在约束条件所划定的一个有限的空间里找,这个有限的空间就是优化理论里所说的可行域。注意可行域中的每一个点都要求满足所有p+q个条件,而不是满足其中一条或几条就可以(切记,要满足每个约束),同时可行域边界上的点有一个额外好的特性,它们可以使不等式约束取得等号!而边界内的点不行。

    关于可行域还有个概念不得不提,那就是凸集,凸集是指有这么一个点的集合,其中任取两个点连一条直线,这条线上的点仍然在这个集合内部,因此说“凸”是很形象的(一个反例是,二维平面上,一个月牙形的区域就不是凸集,你随便就可以找到两个点违反了刚才的规定)。

    回头再来看我们线性分类器问题的描述,可以看出更多的东西。

    (式2)

    在这个问题中,自变量就是w,而目标函数是w的二次函数,所有的约束条件都是w的线性函数(哎,千万不要把xi当成变量,它代表样本,是已知的),这种规划问题有个很有名气的称呼——二次规划(Quadratic Programming,QP),而且可以更进一步的说,由于它的可行域是一个凸集,因此它是一个凸二次规划。

    一下子提了这么多术语,实在不是为了让大家以后能向别人炫耀学识的渊博,这其实是我们继续下去的一个重要前提,因为在动手求一个问题的解之前(好吧,我承认,是动计算机求……),我们必须先问自己:这个问题是不是有解?如果有解,是否能找到?

    对于一般意义上的规划问题,两个问题的答案都是不一定,但凸二次规划让人喜欢的地方就在于,它有解(教科书里面为了严谨,常常加限定成分,说它有全局最优解,由于我们想找的本来就是全局最优的解,所以不加也罢),而且可以找到!(当然,依据你使用的算法不同,找到这个解的速度,行话叫收敛速度,会有所不同)

    对比(式2)和(式1)还可以发现,我们的线性分类器问题只有不等式约束,因此形式上看似乎比一般意义上的规划问题要简单,但解起来却并非如此。

    因为我们实际上并不知道该怎么解一个带约束的优化问题。如果你仔细回忆一下高等数学的知识,会记得我们可以轻松的解一个不带任何约束的优化问题(实际上就是当年背得烂熟的函数求极值嘛,求导再找0点呗,谁不会啊?笑),我们甚至还会解一个只带等式约束的优化问题,也是背得烂熟的,求条件极值,记得么,通过添加拉格朗日乘子,构造拉格朗日函数,来把这个问题转化为无约束的优化问题云云(如果你一时没想通,我提醒一下,构造出的拉格朗日函数就是转化之后的问题形式,它显然没有带任何条件)。

    读者问:如果只带等式约束的问题可以转化为无约束的问题而得以求解,那么可不可以把带不等式约束的问题向只带等式约束的问题转化一下而得以求解呢?

    聪明,可以,实际上我们也正是这么做的。下一节就来说说如何做这个转化,一旦转化完成,求解对任何学过高等数学的人来说,都是小菜一碟啦。

    SVM入门(六)线性分类器的求解——问题的转化,直观角度

    让我再一次比较完整的重复一下我们要解决的问题:我们有属于两个类别的样本点(并不限定这些点在二维空间中)若干,如图,

    圆形的样本点定为正样本(连带着,我们可以把正样本所属的类叫做正类),方形的点定为负例。我们想求得这样一个线性函数(在n维空间中的线性函数):

    g(x)=wx+b

    使得所有属于正类的点+代入以后有g(x+)≥1,而所有属于负类的点x-代入后有g(x-)≤-1(之所以总跟1比较,无论正一还是负一,都是因为我们固定了间隔为1,注意间隔和几何间隔的区别)。代入g(x)后的值如果在1和-1之间,我们就拒绝判断。

    求这样的g(x)的过程就是求w(一个n维向量)和b(一个实数)两个参数的过程(但实际上只需要求w,求得以后找某些样本点代入就可以求得b)。因此在求g(x)的时候,w才是变量。

    你肯定能看出来,一旦求出了w(也就求出了b),那么中间的直线H就知道了(因为它就是wx+b=0嘛,哈哈),那么H1和H2也就知道了(因为三者是平行的,而且相隔的距离还是||w||决定的)。那么w是谁决定的?显然是你给的样本决定的,一旦你在空间中给出了那些个样本点,三条直线的位置实际上就唯一确定了(因为我们求的是最优的那三条,当然是唯一的),我们解优化问题的过程也只不过是把这个确定了的东西算出来而已。

    样本确定了w,用数学的语言描述,就是w可以表示为样本的某种组合:

    w=α1x1+α2x2+…+αnxn

    式子中的αi是一个一个的数(在严格的证明过程中,这些α被称为拉格朗日乘子),而xi是样本点,因而是向量,n就是总样本点的个数。为了方便描述,以下开始严格区别数字与向量的乘积和向量间的乘积,我会用α1x1表示数字和向量的乘积,而用<x1,x2>表示向量x1,x2的内积(也叫点积,注意与向量叉积的区别)。因此g(x)的表达式严格的形式应该是:

    g(x)=<w,x>+b

    但是上面的式子还不够好,你回头看看图中正样本和负样本的位置,想像一下,我不动所有点的位置,而只是把其中一个正样本点定为负样本点(也就是把一个点的形状从圆形变为方形),结果怎么样?三条直线都必须移动(因为对这三条直线的要求是必须把方形和圆形的点正确分开)!这说明w不仅跟样本点的位置有关,还跟样本的类别有关(也就是和样本的“标签”有关)。因此用下面这个式子表示才算完整:

    w=α1y1x1+α2y2x2+…+αnynxn (式1)

    其中的yi就是第i个样本的标签,它等于1或者-1。其实以上式子的那一堆拉格朗日乘子中,只有很少的一部分不等于0(不等于0才对w起决定作用),这部分不等于0的拉格朗日乘子后面所乘的样本点,其实都落在H1和H2上,也正是这部分样本(而不需要全部样本)唯一的确定了分类函数,当然,更严格的说,这些样本的一部分就可以确定,因为例如确定一条直线,只需要两个点就可以,即便有三五个都落在上面,我们也不是全都需要。这部分我们真正需要的样本点,就叫做支持(撑)向量!(名字还挺形象吧,他们“撑”起了分界线)

    式子也可以用求和符号简写一下:

    因此原来的g(x)表达式可以写为:

    注意式子中x才是变量,也就是你要分类哪篇文档,就把该文档的向量表示代入到 x的位置,而所有的xi统统都是已知的样本。还注意到式子中只有xi和x是向量,因此一部分可以从内积符号中拿出来,得到g(x)的式子为:

    发现了什么?w不见啦!从求w变成了求α。

    但肯定有人会说,这并没有把原问题简化呀。嘿嘿,其实简化了,只不过在你看不见的地方,以这样的形式描述问题以后,我们的优化问题少了很大一部分不等式约束(记得这是我们解不了极值问题的万恶之源)。但是接下来先跳过线性分类器求解的部分,来看看 SVM在线性分类器上所做的重大改进——核函数。

    SVM入门(七)为何需要核函数

    生存?还是毁灭?——哈姆雷特

    可分?还是不可分?——支持向量机

    之前一直在讨论的线性分类器,器如其名(汗,这是什么说法啊),只能对线性可分的样本做处理。如果提供的样本线性不可分,结果很简单,线性分类器的求解程序会无限循环,永远也解不出来。这必然使得它的适用范围大大缩小,而它的很多优点我们实在不原意放弃,怎么办呢?是否有某种方法,让线性不可分的数据变得线性可分呢?

    有!其思想说来也简单,来用一个二维平面中的分类问题作例子,你一看就会明白。事先声明,下面这个例子是网络早就有的,我一时找不到原作者的正确信息,在此借用,并加进了我自己的解说而已。

    例子是下面这张图:

    /

    我们把横轴上端点a和b之间红色部分里的所有点定为正类,两边的黑色部分里的点定为负类。试问能找到一个线性函数把两类正确分开么?不能,因为二维空间里的线性函数就是指直线,显然找不到符合条件的直线。

    但我们可以找到一条曲线,例如下面这一条:

    显然通过点在这条曲线的上方还是下方就可以判断点所属的类别(你在横轴上随便找一点,算算这一点的函数值,会发现负类的点函数值一定比0大,而正类的一定比0小)。这条曲线就是我们熟知的二次曲线,它的函数表达式可以写为:

    问题只是它不是一个线性函数,但是,下面要注意看了,新建一个向量y和a:

    这样g(x)就可以转化为f(y)=<a,y>,你可以把y和a分别回带一下,看看等不等于原来的g(x)。用内积的形式写你可能看不太清楚,实际上f(y)的形式就是:

    g(x)=f(y)=ay

    在任意维度的空间中,这种形式的函数都是一个线性函数(只不过其中的a和y都是多维向量罢了),因为自变量y的次数不大于1。

    看出妙在哪了么?原来在二维空间中一个线性不可分的问题,映射到四维空间后,变成了线性可分的!因此这也形成了我们最初想解决线性不可分问题的基本思路——向高维空间转化,使其变得线性可分。

    而转化最关键的部分就在于找到x到y的映射方法。遗憾的是,如何找到这个映射,没有系统性的方法(也就是说,纯靠猜和凑)。具体到我们的文本分类问题,文本被表示为上千维的向量,即使维数已经如此之高,也常常是线性不可分的,还要向更高的空间转化。其中的难度可想而知。

    小Tips:为什么说f(y)=ay是四维空间里的函数?

    大家可能一时没看明白。回想一下我们二维空间里的函数定义 
      g(x)=ax+b 
    变量x是一维的,为什么说它是二维空间里的函数呢?因为还有一个变量我们没写出来,它的完整形式其实是 
      y=g(x)=ax+b 
    即 
      y=ax+b 
    看看,有几个变量?两个。那是几维空间的函数?(作者五岁的弟弟答:五维的。作者:……) 
    再看看 
    f(y)=ay 
    里面的y是三维的变量,那f(y)是几维空间里的函数?(作者五岁的弟弟答:还是五维的。作者:……)

    用一个具体文本分类的例子来看看这种向高维空间映射从而分类的方法如何运作,想象一下,我们文本分类问题的原始空间是1000维的(即每个要被分类的文档被表示为一个1000维的向量),在这个维度上问题是线性不可分的。现在我们有一个2000维空间里的线性函数

    f(x’)=<w’,x’>+b

    注意向量的右上角有个 ’哦。它能够将原问题变得可分。式中的 w’和x’都是2000维的向量,只不过w’是定值,而x’是变量(好吧,严格说来这个函数是2001维的,哈哈),现在我们的输入呢,是一个1000维的向量x,分类的过程是先把x变换为2000维的向量x’,然后求这个变换后的向量x’与向量w’的内积,再把这个内积的值和b相加,就得到了结果,看结果大于阈值还是小于阈值就得到了分类结果。

    你发现了什么?我们其实只关心那个高维空间里内积的值,那个值算出来了,分类结果就算出来了。而从理论上说, x’是经由x变换来的,因此广义上可以把它叫做x的函数(有一个x,就确定了一个x’,对吧,确定不出第二个),而w’是常量,它是一个低维空间里的常量w经过变换得到的,所以给了一个w 和x的值,就有一个确定的f(x’)值与其对应。这让我们幻想,是否能有这样一种函数K(w,x),他接受低维空间的输入值,却能算出高维空间的内积值<w’,x’>?

    如果有这样的函数,那么当给了一个低维空间的输入x以后,

    g(x)=K(w,x)+b

    f(x’)=<w’,x’>+b

    这两个函数的计算结果就完全一样,我们也就用不着费力找那个映射关系,直接拿低维的输入往g(x)里面代就可以了(再次提醒,这回的g(x)就不是线性函数啦,因为你不能保证K(w,x)这个表达式里的x次数不高于1哦)。

    万幸的是,这样的K(w,x)确实存在(发现凡是我们人类能解决的问题,大都是巧得不能再巧,特殊得不能再特殊的问题,总是恰好有些能投机取巧的地方才能解决,由此感到人类的渺小),它被称作核函数(核,kernel),而且还不止一个,事实上,只要是满足了Mercer条件的函数,都可以作为核函数。核函数的基本作用就是接受两个低维空间里的向量,能够计算出经过某个变换后在高维空间里的向量内积值。几个比较常用的核函数,俄,教课书里都列过,我就不敲了(懒!)。

    回想我们上节说的求一个线性分类器,它的形式应该是:

    现在这个就是高维空间里的线性函数(为了区别低维和高维空间里的函数和向量,我改了函数的名字,并且给w和x都加上了 ’),我们就可以用一个低维空间里的函数(再一次的,这个低维空间里的函数就不再是线性的啦)来代替,

    又发现什么了?f(x’) 和g(x)里的α,y,b全都是一样一样的!这就是说,尽管给的问题是线性不可分的,但是我们就硬当它是线性问题来求解,只不过求解过程中,凡是要求内积的时候就用你选定的核函数来算。这样求出来的α再和你选定的核函数一组合,就得到分类器啦!

    明白了以上这些,会自然的问接下来两个问题:

    1. 既然有很多的核函数,针对具体问题该怎么选择?

    2. 如果使用核函数向高维空间映射后,问题仍然是线性不可分的,那怎么办?

    第一个问题现在就可以回答你:对核函数的选择,现在还缺乏指导原则!各种实验的观察结果(不光是文本分类)的确表明,某些问题用某些核函数效果很好,用另一些就很差,但是一般来讲,径向基核函数是不会出太大偏差的一种,首选。(我做文本分类系统的时候,使用径向基核函数,没有参数调优的情况下,绝大部分类别的准确和召回都在85%以上,可见。虽然libSVM的作者林智仁认为文本分类用线性核函数效果更佳,待考证)

    对第二个问题的解决则引出了我们下一节的主题:松弛变量。

    SVM入门(八)松弛变量

    现在我们已经把一个本来线性不可分的文本分类问题,通过映射到高维空间而变成了线性可分的。就像下图这样:

    圆形和方形的点各有成千上万个(毕竟,这就是我们训练集中文档的数量嘛,当然很大了)。现在想象我们有另一个训练集,只比原先这个训练集多了一篇文章,映射到高维空间以后(当然,也使用了相同的核函数),也就多了一个样本点,但是这个样本的位置是这样的:

    就是图中黄色那个点,它是方形的,因而它是负类的一个样本,这单独的一个样本,使得原本线性可分的问题变成了线性不可分的。这样类似的问题(仅有少数点线性不可分)叫做“近似线性可分”的问题。

    以我们人类的常识来判断,说有一万个点都符合某种规律(因而线性可分),有一个点不符合,那这一个点是否就代表了分类规则中我们没有考虑到的方面呢(因而规则应该为它而做出修改)?

    其实我们会觉得,更有可能的是,这个样本点压根就是错误,是噪声,是提供训练集的同学人工分类时一打瞌睡错放进去的。所以我们会简单的忽略这个样本点,仍然使用原来的分类器,其效果丝毫不受影响。

    但这种对噪声的容错性是人的思维带来的,我们的程序可没有。由于我们原本的优化问题的表达式中,确实要考虑所有的样本点(不能忽略某一个,因为程序它怎么知道该忽略哪一个呢?),在此基础上寻找正负类之间的最大几何间隔,而几何间隔本身代表的是距离,是非负的,像上面这种有噪声的情况会使得整个问题无解。这种解法其实也叫做“硬间隔”分类法,因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个值。

    因此由上面的例子中也可以看出,硬间隔的分类法其结果容易受少数点的控制,这是很危险的(尽管有句话说真理总是掌握在少数人手中,但那不过是那一小撮人聊以自慰的词句罢了,咱还是得民主)。

    但解决方法也很明显,就是仿照人的思路,允许一些点到分类平面的距离不满足原先的要求。由于不同的训练集各点的间距尺度不太一样,因此用间隔(而不是几何间隔)来衡量有利于我们表达形式的简洁。我们原先对样本点的要求是:

    意思是说离分类面最近的样本点函数间隔也要比1大。如果要引入容错性,就给1这个硬性的阈值加一个松弛变量,即允许

    因为松弛变量是非负的,因此最终的结果是要求间隔可以比1小。但是当某些点出现这种间隔比1小的情况时(这些点也叫离群点),意味着我们放弃了对这些点的精确分类,而这对我们的分类器来说是种损失。但是放弃这些点也带来了好处,那就是使分类面不必向这些点的方向移动,因而可以得到更大的几何间隔(在低维空间看来,分类边界也更平滑)。显然我们必须权衡这种损失和好处。好处很明显,我们得到的分类间隔越大,好处就越多。回顾我们原始的硬间隔分类对应的优化问题:

    ||w||2就是我们的目标函数(当然系数可有可无),希望它越小越好,因而损失就必然是一个能使之变大的量(能使它变小就不叫损失了,我们本来就希望目标函数值越小越好)。那如何来衡量损失,有两种常用的方式,有人喜欢用

    而有人喜欢用

    其中l都是样本的数目。两种方法没有大的区别。如果选择了第一种,得到的方法的就叫做二阶软间隔分类器,第二种就叫做一阶软间隔分类器。把损失加入到目标函数里的时候,就需要一个惩罚因子(cost,也就是libSVM的诸多参数中的C),原来的优化问题就变成了下面这样:

    这个式子有这么几点要注意:

    一是并非所有的样本点都有一个松弛变量与其对应。实际上只有“离群点”才有,或者也可以这么看,所有没离群的点松弛变量都等于0(对负类来说,离群点就是在前面图中,跑到H2右侧的那些负样本点,对正类来说,就是跑到H1左侧的那些正样本点)。

    【在迭代求w的时候如何样本点非离群点,即分类正确,那么就设它的松弛变量为0了。。。】

    二是松弛变量的值实际上标示出了对应的点到底离群有多远,值越大,点就越远。

    三是惩罚因子C决定了你有多重视离群点带来的损失,显然当所有离群点的松弛变量的和一定时,你定的C越大,对目标函数的损失也越大,此时就暗示着你非常不愿意放弃这些离群点,最极端的情况是你把C定为无限大,这样只要稍有一个点离群,目标函数的值马上变成无限大,马上让问题变成无解,这就退化成了硬间隔问题。

    四是惩罚因子C不是一个变量,整个优化问题在解的时候,C是一个你必须事先指定的值,指定这个值以后,解一下,得到一个分类器,然后用测试数据看看结果怎么样,如果不够好,换一个C的值,再解一次优化问题,得到另一个分类器,再看看效果,如此就是一个参数寻优的过程,但这和优化问题本身决不是一回事,优化问题在解的过程中,C一直是定值,要记住。

    五是尽管加了松弛变量这么一说,但这个优化问题仍然是一个优化问题(汗,这不废话么),解它的过程比起原始的硬间隔问题来说,没有任何更加特殊的地方。

    从大的方面说优化问题解的过程,就是先试着确定一下w,也就是确定了前面图中的三条直线,这时看看间隔有多大,又有多少点离群,把目标函数的值算一算,再换一组三条直线(你可以看到,分类的直线位置如果移动了,有些原来离群的点会变得不再离群,而有的本来不离群的点会变成离群点),再把目标函数的值算一算,如此往复(迭代),直到最终找到目标函数最小时的w。

    啰嗦了这么多,读者一定可以马上自己总结出来,松弛变量也就是个解决线性不可分问题的方法罢了,但是回想一下,核函数的引入不也是为了解决线性不可分的问题么?为什么要为了一个问题使用两种方法呢?

    其实两者还有微妙的不同。一般的过程应该是这样,还以文本分类为例。在原始的低维空间中,样本相当的不可分,无论你怎么找分类平面,总会有大量的离群点,此时用核函数向高维空间映射一下,虽然结果仍然是不可分的,但比原始空间里的要更加接近线性可分的状态(就是达到了近似线性可分的状态),此时再用松弛变量处理那些少数“冥顽不化”的离群点,就简单有效得多啦。

    本节中的(式1)也确实是支持向量机最最常用的形式。至此一个比较完整的支持向量机框架就有了,简单说来,支持向量机就是使用了核函数的软间隔线性分类法。

    下一节会说说松弛变量剩下的一点点东西,顺便搞个读者调查,看看大家还想侃侃SVM的哪些方面。

    SVM入门(九)松弛变量(续)

    接下来要说的东西其实不是松弛变量本身,但由于是为了使用松弛变量才引入的,因此放在这里也算合适,那就是惩罚因子C。回头看一眼引入了松弛变量以后的优化问题:

    注意其中C的位置,也可以回想一下C所起的作用(表征你有多么重视离群点,C越大越重视,越不想丢掉它们)。这个式子是以前做SVM的人写的,大家也就这么用,但没有任何规定说必须对所有的松弛变量都使用同一个惩罚因子,我们完全可以给每一个离群点都使用不同的C,这时就意味着你对每个样本的重视程度都不一样,有些样本丢了也就丢了,错了也就错了,这些就给一个比较小的C;而有些样本很重要,决不能分类错误(比如中央下达的文件啥的,笑),就给一个很大的C。

    当然实际使用的时候并没有这么极端,但一种很常用的变形可以用来解决分类问题中样本的“偏斜”问题。

    先来说说样本的偏斜问题,也叫数据集偏斜(unbalanced),它指的是参与分类的两个类别(也可以指多个类别)样本数量差异很大。比如说正类有10,000个样本,而负类只给了100个,这会引起的问题显而易见,可以看看下面的图:

    方形的点是负类。H,H1,H2是根据给的样本算出来的分类面,由于负类的样本很少很少,所以有一些本来是负类的样本点没有提供,比如图中两个灰色的方形点,如果这两个点有提供的话,那算出来的分类面应该是H’,H2’和H1,他们显然和之前的结果有出入,实际上负类给的样本点越多,就越容易出现在灰色点附近的点,我们算出的结果也就越接近于真实的分类面。但现在由于偏斜的现象存在,使得数量多的正类可以把分类面向负类的方向“推”,因而影响了结果的准确性。

    对付数据集偏斜问题的方法之一就是在惩罚因子上作文章,想必大家也猜到了,那就是给样本数量少的负类更大的惩罚因子,表示我们重视这部分样本(本来数量就少,再抛弃一些,那人家负类还活不活了),因此我们的目标函数中因松弛变量而损失的部分就变成了:

    其中i=1…p都是正样本,j=p+1…p+q都是负样本。libSVM这个算法包在解决偏斜问题的时候用的就是这种方法。

    那C+和C-怎么确定呢?它们的大小是试出来的(参数调优),但是他们的比例可以有些方法来确定。咱们先假定说C+是5这么大,那确定C-的一个很直观的方法就是使用两类样本数的比来算,对应到刚才举的例子,C-就可以定为500这么大(因为10,000:100=100:1嘛)。

    但是这样并不够好,回看刚才的图,你会发现正类之所以可以“欺负”负类,其实并不是因为负类样本少,真实的原因是负类的样本分布的不够广(没扩充到负类本应该有的区域)。说一个具体点的例子,现在想给政治类和体育类的文章做分类,政治类文章很多,而体育类只提供了几篇关于篮球的文章,这时分类会明显偏向于政治类,如果要给体育类文章增加样本,但增加的样本仍然全都是关于篮球的(也就是说,没有足球,排球,赛车,游泳等等),那结果会怎样呢?虽然体育类文章在数量上可以达到与政治类一样多,但过于集中了,结果仍会偏向于政治类!所以给C+和C-确定比例更好的方法应该是衡量他们分布的程度。比如可以算算他们在空间中占据了多大的体积,例如给负类找一个超球——就是高维空间里的球啦——它可以包含所有负类的样本,再给正类找一个,比比两个球的半径,就可以大致确定分布的情况。显然半径大的分布就比较广,就给小一点的惩罚因子。

    但是这样还不够好,因为有的类别样本确实很集中,这不是提供的样本数量多少的问题,这是类别本身的特征(就是某些话题涉及的面很窄,例如计算机类的文章就明显不如文化类的文章那么“天马行空”),这个时候即便超球的半径差异很大,也不应该赋予两个类别不同的惩罚因子。

    看到这里读者一定疯了,因为说来说去,这岂不成了一个解决不了的问题?然而事实如此,完全的方法是没有的,根据需要,选择实现简单又合用的就好(例如libSVM就直接使用样本数量的比)。

    SVM入门(十)将SVM用于多类分类

    从 SVM的那几张图可以看出来,SVM是一种典型的两类分类器,即它只回答属于正类还是负类的问题。而现实中要解决的问题,往往是多类的问题(少部分例外,例如垃圾邮件过滤,就只需要确定“是”还是“不是”垃圾邮件),比如文本分类,比如数字识别。如何由两类分类器得到多类分类器,就是一个值得研究的问题。

    还以文本分类为例,现成的方法有很多,其中一种一劳永逸的方法,就是真的一次性考虑所有样本,并求解一个多目标函数的优化问题,一次性得到多个分类面,就像下图这样:

    多个超平面把空间划分为多个区域,每个区域对应一个类别,给一篇文章,看它落在哪个区域就知道了它的分类。

    看起来很美对不对?只可惜这种算法还基本停留在纸面上,因为一次性求解的方法计算量实在太大,大到无法实用的地步。

    稍稍退一步,我们就会想到所谓“一类对其余”的方法,就是每次仍然解一个两类分类的问题。比如我们有5个类别,第一次就把类别1的样本定为正样本,其余2,3,4,5的样本合起来定为负样本,这样得到一个两类分类器,它能够指出一篇文章是还是不是第1类的;第二次我们把类别2 的样本定为正样本,把1,3,4,5的样本合起来定为负样本,得到一个分类器,如此下去,我们可以得到5个这样的两类分类器(总是和类别的数目一致)。到了有文章需要分类的时候,我们就拿着这篇文章挨个分类器的问:是属于你的么?是属于你的么?哪个分类器点头说是了,文章的类别就确定了。这种方法的好处是每个优化问题的规模比较小,而且分类的时候速度很快(只需要调用5个分类器就知道了结果)。但有时也会出现两种很尴尬的情况,例如拿一篇文章问了一圈,每一个分类器都说它是属于它那一类的,或者每一个分类器都说它不是它那一类的,前者叫分类重叠现象,后者叫不可分类现象。分类重叠倒还好办,随便选一个结果都不至于太离谱,或者看看这篇文章到各个超平面的距离,哪个远就判给哪个。不可分类现象就着实难办了,只能把它分给第6个类别了……更要命的是,本来各个类别的样本数目是差不多的,但“其余”的那一类样本数总是要数倍于正类(因为它是除正类以外其他类别的样本之和嘛),这就人为的造成了上一节所说的“数据集偏斜”问题。

    因此我们还得再退一步,还是解两类分类问题,还是每次选一个类的样本作正类样本,而负类样本则变成只选一个类(称为“一对一单挑”的方法,哦,不对,没有单挑,就是“一对一”的方法,呵呵),这就避免了偏斜。因此过程就是算出这样一些分类器,第一个只回答“是第1类还是第2类”,第二个只回答“是第1类还是第3类”,第三个只回答“是第1类还是第4类”,如此下去,你也可以马上得出,这样的分类器应该有5 X 4/2=10个(通式是,如果有k个类别,则总的两类分类器数目为k(k-1)/2)。虽然分类器的数目多了,但是在训练阶段(也就是算出这些分类器的分类平面时)所用的总时间却比“一类对其余”方法少很多,在真正用来分类的时候,把一篇文章扔给所有分类器,第一个分类器会投票说它是“1”或者“2”,第二个会说它是“1”或者“3”,让每一个都投上自己的一票,最后统计票数,如果类别“1”得票最多,就判这篇文章属于第1类。这种方法显然也会有分类重叠的现象,但不会有不可分类现象,因为总不可能所有类别的票数都是0。看起来够好么?其实不然,想想分类一篇文章,我们调用了多少个分类器?10个,这还是类别数为5的时候,类别数如果是1000,要调用的分类器数目会上升至约500,000个(类别数的平方量级)。这如何是好?

    看来我们必须再退一步,在分类的时候下功夫,我们还是像一对一方法那样来训练,只是在对一篇文章进行分类之前,我们先按照下面图的样子来组织分类器(如你所见,这是一个有向无环图,因此这种方法也叫做DAG SVM)

    这样在分类时,我们就可以先问分类器“1对5”(意思是它能够回答“是第1类还是第5类”),如果它回答5,我们就往左走,再问“2对5”这个分类器,如果它还说是“5”,我们就继续往左走,这样一直问下去,就可以得到分类结果。好处在哪?我们其实只调用了4个分类器(如果类别数是k,则只调用k-1个),分类速度飞快,且没有分类重叠和不可分类现象!缺点在哪?假如最一开始的分类器回答错误(明明是类别1的文章,它说成了5),那么后面的分类器是无论如何也无法纠正它的错误的(因为后面的分类器压根没有出现“1”这个类别标签),其实对下面每一层的分类器都存在这种错误向下累积的现象。。

    不过不要被DAG方法的错误累积吓倒,错误累积在一对其余和一对一方法中也都存在,DAG方法好于它们的地方就在于,累积的上限,不管是大是小,总是有定论的,有理论证明。而一对其余和一对一方法中,尽管每一个两类分类器的泛化误差限是知道的,但是合起来做多类分类的时候,误差上界是多少,没人知道,这意味着准确率低到0也是有可能的,这多让人郁闷。

    而且现在DAG方法根节点的选取(也就是如何选第一个参与分类的分类器),也有一些方法可以改善整体效果,我们总希望根节点少犯错误为好,因此参与第一次分类的两个类别,最好是差别特别特别大,大到以至于不太可能把他们分错;或者我们就总取在两类分类中正确率最高的那个分类器作根节点,或者我们让两类分类器在分类的时候,不光输出类别的标签,还输出一个类似“置信度”的东东,当它对自己的结果不太自信的时候,我们就不光按照它的输出走,把它旁边的那条路也走一走,等等。

    大Tips:SVM的计算复杂度

    使用SVM进行分类的时候,实际上是训练和分类两个完全不同的过程,因而讨论复杂度就不能一概而论,我们这里所说的主要是训练阶段的复杂度,即解那个二次规划问题的复杂度。对这个问题的解,基本上要划分为两大块,解析解和数值解。

    解析解就是理论上的解,它的形式是表达式,因此它是精确的,一个问题只要有解(无解的问题还跟着掺和什么呀,哈哈),那它的解析解是一定存在的。当然存在是一回事,能够解出来,或者可以在可以承受的时间范围内解出来,就是另一回事了。对SVM来说,求得解析解的时间复杂度最坏可以达到O(Nsv3),其中Nsv是支持向量的个数,而虽然没有固定的比例,但支持向量的个数多少也和训练集的大小有关。

    数值解就是可以使用的解,是一个一个的数,往往都是近似解。求数值解的过程非常像穷举法,从一个数开始,试一试它当解效果怎样,不满足一定条件(叫做停机条件,就是满足这个以后就认为解足够精确了,不需要继续算下去了)就试下一个,当然下一个数不是乱选的,也有一定章法可循。有的算法,每次只尝试一个数,有的就尝试多个,而且找下一个数字(或下一组数)的方法也各不相同,停机条件也各不相同,最终得到的解精度也各不相同,可见对求数值解的复杂度的讨论不能脱开具体的算法。

    一个具体的算法,Bunch-Kaufman训练算法,典型的时间复杂度在O(Nsv3+LNsv2+dLNsv)和O(dL2)之间,其中Nsv是支持向量的个数,L是训练集样本的个数,d是每个样本的维数(原始的维数,没有经过向高维空间映射之前的维数)。复杂度会有变化,是因为它不光跟输入问题的规模有关(不光和样本的数量,维数有关),也和问题最终的解有关(即支持向量有关),如果支持向量比较少,过程会快很多,如果支持向量很多,接近于样本的数量,就会产生O(dL2)这个十分糟糕的结果(给10,000个样本,每个样本1000维,基本就不用算了,算不出来,呵呵,而这种输入规模对文本分类来说太正常了)。

    这样再回头看就会明白为什么一对一方法尽管要训练的两类分类器数量多,但总时间实际上比一对其余方法要少了,因为一对其余方法每次训练都考虑了所有样本(只是每次把不同的部分划分为正类或者负类而已),自然慢上很多。

    展开全文
  • SVM原理介绍

    万次阅读 多人点赞 2018-03-11 16:20:40
    一、SVM算法要解决什么问题SVM的全称是Support Vector Machine,即支持向量机,主要用于解决模式识别领域中的数据分类问题,属于有监督学习算法的一种。SVM要解决的问题可以用一个经典的二分类问题加以描述。如图1所...

    一、SVM算法要解决什么问题

    SVM的全称是Support Vector Machine,即支持向量机,主要用于解决模式识别领域中的数据分类问题,属于有监督学习算法的一种。SVM要解决的问题可以用一个经典的二分类问题加以描述。如图1所示,红色和蓝色的二维数据点显然是可以被一条直线分开的,在模式识别领域称为线性可分问题。然而将两类数据点分开的直线显然不止一条。图1(b)和(c)分别给出了A、B两种不同的分类方案,其中黑色实线为分界线,术语称为“决策面”。每个决策面对应了一个线性分类器。虽然在目前的数据上看,这两个分类器的分类结果是一样的,但如果考虑潜在的其他数据,则两者的分类性能是有差别的。


    图1 二分类问题描述


    SVM算法认为图1中的分类器A在性能上优于分类器B,其依据是A的分类间隔比B要大。这里涉及到第一个SVM独有的概念“分类间隔”。在保证决策面方向不变且不会出现错分样本的情况下移动决策面,会在原来的决策面两侧找到两个极限位置(越过该位置就会产生错分现象),如虚线所示。虚线的位置由决策面的方向和距离原决策面最近的几个样本的位置决定。而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的最优决策面。两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔。显然每一个可能把数据集正确分开的方向都有一个最优决策面(有些方向无论如何移动决策面的位置也不可能将两类样本完全分开),而不同方向的最优决策面的分类间隔通常是不同的,那个具有“最大间隔”的决策面就是SVM要寻找的最优解。而这个真正的最优解对应的两侧虚线所穿过的样本点,就是SVM中的支持样本点,称为“支持向量”。对于图1中的数据,A决策面就是SVM寻找的最优解,而相应的三个位于虚线上的样本点在坐标系中对应的向量就叫做支持向量。

    从表面上看,我们优化的对象似乎是这个决策面的方向和位置。但实际上最优决策面的方向和位置完全取决于选择哪些样本作为支持向量。而在经过漫长的公式推导后,你最终会发现,其实与线性决策面的方向和位置直接相关的参数都会被约减掉,最终结果只取决于样本点的选择结果。

    到这里,我们明确了SVM算法要解决的是一个最优分类器的设计问题。既然叫作最优分类器,其本质必然是个最优化问题。所以,接下来我们要讨论的就是如何把SVM变成用数学语言描述的最优化问题模型,这就是我们在第二部分要讲的“线性SVM算法的数学建模”。

    *关于“决策面”,为什么叫决策面,而不是决策线?好吧,在图1里,样本是二维空间中的点,也就是数据的维度是2,因此1维的直线可以分开它们。但是在更加一般的情况下,样本点的维度是n,则将它们分开的决策面的维度就是n-1维的超平面(可以想象一下3维空间中的点集被平面分开),所以叫“决策面”更加具有普适性,或者你可以认为直线是决策面的一个特例。


    二、线性SVM算法的数学建模

    一个最优化问题通常有两个最基本的因素:1)目标函数,也就是你希望什么东西的什么指标达到最好;2)优化对象,你期望通过改变哪些因素来使你的目标函数达到最优。在线性SVM算法中,目标函数显然就是那个“分类间隔”,而优化对象则是决策面。所以要对SVM问题进行数学建模,首先要对上述两个对象(“分类间隔”和“决策面”)进行数学描述。按照一般的思维习惯,我们先描述决策面。

    2.1 决策面方程

    请注意,以下的描述对于线性代数及格的同学可能显得比较啰嗦,但请你们照顾一下用高数课治疗失眠的同学们。

    请你暂时不要纠结于n维空间中的n-1维超平面这种超出正常人想象力的情景。我们就老老实实地看看二维空间中的一根直线,我们从初中就开始学习的直线方程形式很简单。

    y=ax+b (2.1)

    现在我们做个小小的改变,让原来的x轴变成x_1轴,y变成x_2轴,于是公式(2.1)中的直线方程会变成下面的样子

    x_2=ax_1+b (2.2)

    ax_1+(-1)x_2+b=0 (2.3)

    公式(2.3)的向量形式可以写成

    [a,-1]\left[ \begin{array}{c}x_1\\x_2\end{array} \right] +b=0 (2.4)

    考虑到我们在等式两边乘上任何实数都不会改变等式的成立,所以我们可以写出一个更加一般的向量表达形式:

    \boldsymbol{\omega}^T\boldsymbol{x}+\gamma=0 (2.5)

    看到变量\boldsymbol{\omega},\boldsymbol{x}略显粗壮的身体了吗?他们是黑体,表示变量是个向量,\boldsymbol{\omega}=[\omega_1,\omega_2]^T\boldsymbol{x}=[x_1,x_2]^T。一般我们提到向量的时候,都默认他们是个列向量,所以我在方括号[ ]后面加上了上标T,表示转置(我知道我真的很啰嗦,但是关于“零基础”三个字,我是认真的。),它可以帮忙把行向量竖过来变成列向量,所以在公式(2.5)里面\boldsymbol{\omega}后面的转置符号T,会把列向量又转回到行向量。这样一个行向量\boldsymbol{\omega}^T和一个列向量\boldsymbol{x}就可快快乐乐的按照矩阵乘法的方式结合,变成一个标量,然后好跟后面的标量\gamma相加后相互抵消变成0。

    就着公式(2.5),我们再稍稍尝试深入一点。那就是探寻一下向量\boldsymbol{\omega}=[\omega_1,\omega_2]^T和标量\gamma的几何意义是什么。让我们回到公式(2.4),对比公式(2.5),可以发现此时的\boldsymbol{\omega}=[a,-1]^T。然后再去看公式(2.2),还记得那条我们熟悉的直线方程中的a的几何意义吗?对的,那是直线的斜率。如果我们构造一个向量\boldsymbol{\phi} = [1,a]^T,它应该跟我们的公式(2.2)描述的直线平行。然后我们求一下两个向量的点积\boldsymbol{\omega}^T\boldsymbol{\phi},你会惊喜地发现结果是0。我们管这种现象叫作“两个向量相互正交”。通俗点说就是两个向量相互垂直。当然,你也可以在草稿纸上自己画出这两个向量,比如让a=\sqrt{3},你会发现\boldsymbol{\phi} = [1,a]^T在第一象限,与横轴夹角为60°,而\boldsymbol{\omega}=[a,-1]^T在第四象限与横轴夹角为30°,所以很显然他们两者的夹角为90°。

    你现在是不是已经忘了我们讨论正交或者垂直的目的是什么了?那么请把你的思维从坐标系上抽出来,回到决策面方程上来。我是想告诉你向量\boldsymbol{\omega}=[\omega_1,\omega_2]^T跟直线\boldsymbol{\omega}^T\boldsymbol{x}+\gamma=0是相互垂直的,也就是说\boldsymbol{\omega}=[\omega_1,\omega_2]^T控制了直线的方向。另外,还记得小时候我们学过的那个叫做截距的名词吗?对了,\gamma就是截距,它控制了直线的位置。

    然后,在本小节的末尾,我冒昧地提示一下,在n维空间中n-1维的超平面的方程形式也是公式(2.5)的样子,只不过向量\boldsymbol{\omega},\boldsymbol{x}的维度从原来的2维变成了n维。如果你还是想不出来超平面的样子,也很正常。那么就请你始终记住平面上它们的样子也足够了。

    到这里,我们花了很多篇幅描述一个很简单的超平面方程(其实只是个直线方程),这里真正有价值的是这个控制方向的参数\boldsymbol{\omega}。接下来,你会有很长一段时间要思考它到底是个什么东西,对于SVM产生了怎样的影响。

    2.2 分类“间隔”的计算模型

    我们在第一章里介绍过分类间隔的定义及其直观的几何意义。间隔的大小实际上就是支持向量对应的样本点到决策面的距离的二倍,如图2所示。

    图2 分类间隔计算

    所以分类间隔计算似乎相当简单,无非就是点到直线的距离公式。如果你想要回忆高中老师在黑板上推导的过程,可以随便在百度文库里搜索关键词“点到直线距离推导公式”,你会得到至少6、7种推导方法。但这里,请原谅我给出一个简单的公式如下:

    d = \frac{|\boldsymbol{\omega}^T\boldsymbol{x}+\gamma|}{||\boldsymbol{\omega}||} (2.6)

    这里||\boldsymbol{\omega}||是向量\boldsymbol{\omega}的模,表示在空间中向量的长度,\boldsymbol{x}=[x_1,x_2]^T就是支持向量样本点的坐标。\boldsymbol{\omega}, \gamma就是决策面方程的参数。而追求W的最大化也就是寻找d的最大化。看起来我们已经找到了目标函数的数学形式。

    但问题当然不会这么简单,我们还需要面对一连串令人头疼的麻烦。

    2.3 约束条件

    接着2.2节的结尾,我们讨论一下究竟还有哪些麻烦没有解决:

    1)并不是所有的方向都存在能够实现100%正确分类的决策面,我们如何判断一条直线是否能够将所有的样本点都正确分类?

    2)即便找到了正确的决策面方向,还要注意决策面的位置应该在间隔区域的中轴线上,所以用来确定决策面位置的截距\gamma也不能自由的优化,而是受到决策面方向和样本点分布的约束。

    3)即便取到了合适的方向和截距,公式(2.6)里面的\boldsymbol{x}不是随随便便的一个样本点,而是支持向量对应的样本点。对于一个给定的决策面,我们该如何找到对应的支持向量?

    以上三条麻烦的本质是“约束条件”,也就是说我们要优化的变量的取值范围受到了限制和约束。事实上约束条件一直是最优化问题里最让人头疼的东西。但既然我们已经论证了这些约束条件确实存在,就不得不用数学语言对他们进行描述。尽管上面看起来是3条约束,但SVM算法通过一些巧妙的小技巧,将这三条约束条件融合在了一个不等式里面。

    我们首先考虑一个决策面是否能够将所有的样本都正确分类的约束。图2中的样本点分成两类(红色和蓝色),我们为每个样本点\boldsymbol{x}_i加上一个类别标签y_i

    y_i = \left\{\begin{array}{ll}+1 & \textrm{for blue points}\\-1 & \textrm{for red points}\end{array}\right. (2.7)

    如果我们的决策面方程能够完全正确地对图2中的样本点进行分类,就会满足下面的公式

    \left\{\begin{array}{ll} \boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma>0 & \textrm{for~~} y_i=1\\\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma<0 & \textrm{for~~} y_i=-1\end{array}\right. (2.8)

    如果我们要求再高一点,假设决策面正好处于间隔区域的中轴线上,并且相应的支持向量对应的样本点到决策面的距离为d,那么公式(2.8)就可以进一步写成:

    \left\{\begin{array}{ll} (\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma)/||\boldsymbol{\omega}||\geq d & \forall~ y_i=1\\(\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma)/||\boldsymbol{\omega}||\leq -d & \forall~y_i=-1\end{array}\right. (2.9)

    符号\forall是“对于所有满足条件的” 的缩写。我们对公式(2.9)中的两个不等式的左右两边除上d,就可得到:

    \left\{\begin{array}{ll} \boldsymbol{\omega}_d^T\boldsymbol{x}_i+\gamma_d\geq 1 & \textrm{for~~} y_i=1\\\boldsymbol{\omega}_d^T\boldsymbol{x}_i+\gamma_d\leq -1 & \textrm{for~~} y_i=-1\end{array}\right. (2.10)

    其中

    \boldsymbol{\omega}_d = \frac{\boldsymbol{\omega}}{||\boldsymbol{\omega}||d},~~ \gamma_d = \frac{\gamma}{||\boldsymbol{\omega}||d}

    把 \boldsymbol{\omega}_d\gamma_d就当成一条直线的方向矢量和截距。你会发现事情没有发生任何变化,因为直线\boldsymbol{\omega}_d^T\boldsymbol{x}+\gamma_d=0和直线\boldsymbol{\omega}^T\boldsymbol{x}+\gamma=0其实是一条直线。现在,现在让我忘记原来的直线方程参数\boldsymbol{\omega}\gamma,我们可以把参数 \boldsymbol{\omega}_d\gamma_d重新起个名字,就叫它们\boldsymbol{\omega}\gamma。我们可以直接说:“对于存在分类间隔的两类样本点,我们一定可以找到一些决策面,使其对于所有的样本点均满足下面的条件:”



    \left\{\begin{array}{ll} \boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma\geq 1 & \textrm{for~~} y_i=1\\\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma\leq -1 & \textrm{for~~} y_i=-1\end{array}\right. (2.11)

    公式(2.11)可以认为是SVM优化问题的约束条件的基本描述。

    2.4 线性SVM优化问题基本描述
    公式(2.11)里面\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma= 1~~\textrm{or}~~-1的情况什么时候会发生呢,参考一下公式(2.9)就会知道,只有当\boldsymbol{x}_i是决策面\boldsymbol{\omega}^T\boldsymbol{x}+\gamma=0所对应的支持向量样本点时,等于1或-1的情况才会出现。这一点给了我们另一个简化目标函数的启发。回头看看公式(2.6),你会发现等式右边分子部分的绝对值符号内部的表达式正好跟公式(2.11)中不等式左边的表达式完全一致,无论原来这些表达式是1或者-1,其绝对值都是1。所以对于这些支持向量样本点有:

    d = \frac{|\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma|}{||\boldsymbol{\omega}||}=\frac{1}{||\boldsymbol{\omega}||},~~\textrm{if} ~\boldsymbol{x}_i \textrm {is a support vector} (2.12)

    公式(2.12)的几何意义就是,支持向量样本点到决策面方程的距离就是1/||\boldsymbol{\omega}||。我们原来的任务是找到一组参数\boldsymbol{\omega},~\gamma使得分类间隔W=2d最大化,根据公式(2.12)就可以转变为||\boldsymbol{\omega}||的最小化问题,也等效于\frac{1}{2}||\boldsymbol{\omega}||^2的最小化问题。我们之所以要在||\boldsymbol{\omega}||上加上平方和1/2的系数,是为了以后进行最优化的过程中对目标函数求导时比较方便,但这绝不影响最优化问题最后的解。

    另外我们还可以尝试将公式(2.11)给出的约束条件进一步在形式上精练,把类别标签y_i和两个不等式左边相乘,形成统一的表述:

    y_i(\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma)\geq 1~\forall \boldsymbol{x}_i (2.13)

    好了,到这里我们可以给出线性SVM最优化问题的数学描述了:

    \begin{array}{l} \min_{\boldsymbol{\omega},\gamma}\frac{1}{2}||\boldsymbol{\omega}||^2\\ ~\\ \textrm{s. t.}~ ~y_i(\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma)\geq 1,~~i = 1,2,...,m \end{array} (2.14)


    这里m是样本点的总个数,缩写s. t. 表示“Subject to”,是“服从某某条件”的意思。公式(2.14)描述的是一个典型的不等式约束条件下的二次型函数优化问题,同时也是支持向量机的基本数学模型。(此时此刻,你也许会回头看2.3节我们提出的三个约束问题,思考它们在公式2.14的约束条件中是否已经得到了充分的体现。但我不建议你现在就这么做,因为2.14采用了一种比较含蓄的方式表示这些约束条件,所以你即便现在不理解也没关系,后面随着推导的深入,这些问题会一点点露出真容。

    接下来,我们将在第三章讨论大多数同学比较陌生的问题:如何利用最优化技术求解公式(2.14)描述的问题。哪些令人望而生畏的术语,凸二次优化、拉格朗日对偶、KKT条件、鞍点等等,大多出现在这个部分。全面理解和熟练掌握这些概念当然不容易,但如果你的目的主要是了解这些技术如何在SVM问题进行应用的,那么阅读过下面一章后,你有很大的机会可以比较直观地理解这些问题。

    come from future______by Chen

    *一点小建议,读到这里,你可以试着在纸上随便画一些点,然后尝试用SVM的思想手动画线将两类不同的点分开。你会发现大多数情况下,你会先画一条可以成功分开两类样本点的直线,然后你会在你的脑海中想象去旋转这条线,旋转到某个角度,你就会下意识的停下来,因为如果再旋转下去,就找不到能够成功将两类点分开的直线了。这个过程就是对直线方向的优化过程。对于有些问题,你会发现SVM的最优解往往出现在不能再旋转下去的边界位置,这就是约束条件的边界,对比我们提到的等式约束条件,你会对代数公式与几何想象之间的关系得到一些相对直观的印象。

    三、有约束最优化问题的数学模型

    Hi,好久不见)就像我们在第二部分结尾时提到的,SVM问题是一个不等式约束条件下的优化问题。绝大多数模式识别教材在讨论这个问题时都会在附录中加上优化算法的简介,虽然有些写得未免太简略,但看总比不看强,所以这时候如果你手头有一本模式识别教材,不妨翻到后面找找看。结合附录看我下面写的内容,也许会有帮助。

    我们先解释一下我们下面讲解的思路以及重点关注哪些问题:

    1)有约束优化问题的几何意象:闭上眼睛你看到什么?

    2)拉格朗日乘子法:约束条件怎么跑到目标函数里面去了?

    3)KKT条件:约束条件是不等式该怎么办?

    4)拉格朗日对偶:最小化问题怎么变成了最大化问题?

    5)实例演示:拉格朗日对偶函数到底啥样子?

    6)SVM优化算法的实现:数学讲了辣么多,到底要怎么用啊?

    3.1 有约束优化问题的几何意象

    约束条件一般分为等式约束和不等式约束两种,前者表示为g(\boldsymbol{x})=0(注意这里的\boldsymbol{x}跟第二章里面的样本x没有任何关系,只是一种通用的表示);后者表示为g(\boldsymbol{x})\leq0你可能会问为什么不是g(\boldsymbol{x})<0,别着急,到KKT那里你就明白了)。

    假设\boldsymbol{x}\in\mathbb{R}^d就是这个向量一共有d个标量组成),则g(\boldsymbol{x})=0的几何意象就是d维空间中的d-1维曲面,如果函数g(\boldsymbol{x})是线性的,g(\boldsymbol{x})=0则是个d-1维的超平面。那么有约束优化问题就要求在这个d-1维的曲面或者超平面上找到能使得目标函数最小的点,这个d-1维的曲面就是“可行解区域”。


    对于不等式约束条件,g(\boldsymbol{x})\leq0,则可行解区域从d-1维曲面扩展成为d维空间的一个子集。我们可以从d=2的二维空间进行对比理解。等式约束对应的可行解空间就是一条线;不等式约束对应的则是这条线以及线的某一侧对应的区域,就像下面这幅图的样子(图中的目标函数等高线其实就是等值线,在同一条等值线上的点对应的目标函数值相同)。


    图3 有约束优化问题的几何意象图


    3.2 拉格朗日乘子法

    尽管在3.1节我们已经想象出有约束优化问题的几何意象。可是如何利用代数方法找到这个被约束了的最优解呢?这就需要用到拉格朗日乘子法。

    首先定义原始目标函数f(\boldsymbol{x}),拉格朗日乘子法的基本思想是把约束条件转化为新的目标函数L(\boldsymbol{x},\lambda)的一部分(关于\lambda的意义我们一会儿再解释),从而使有约束优化问题变成我们习惯的无约束优化问题。那么该如何去改造原来的目标函数f(\boldsymbol{x})使得新的目标函数L(\boldsymbol{x},\lambda)的最优解恰好就在可行解区域中呢?这需要我们去分析可行解区域中最优解的特点。


    1)最优解的特点分析

    这里比较有代表性的是等式约束条件(不等式约束条件的情况我们在KKT条件里再讲)。我们观察一下图3中的红色虚线(可行解空间)和蓝色虚线(目标函数的等值线),发现这个被约束的最优解恰好在二者相切的位置。这是个偶然吗?我可以负责任地说:“NO!它们温柔的相遇,是三生的宿命。”为了解释这个相遇,我们先介绍梯度的概念。梯度可以直观的认为是函数的变化量,可以描述为包含变化方向和变化幅度的一个向量。然后我们给出一个推论:

    推论1:“在那个宿命的相遇点\boldsymbol{x}^*也就是等式约束条件下的优化问题的最优解),原始目标函数f(\boldsymbol{x})的梯度向量\nabla f(\boldsymbol{x^*})必然与约束条件g(\boldsymbol{x})=0的切线方向垂直。”

    关于推论1的粗浅的论证如下:

    如果梯度矢量\nabla f(\boldsymbol{x}^*)不垂直于g(\boldsymbol{x})=0\boldsymbol{x}^*点的切线方向,就会在g(\boldsymbol{x})=0的切线方向上存在不等于0的分量,也就是说在相遇点\boldsymbol{x}^*附近,f(\boldsymbol{x})还在沿着g(\boldsymbol{x})=0变化。这意味在g(\boldsymbol{x})=0\boldsymbol{x}^*这一点的附近一定有一个点的函数值比f(\boldsymbol{x}^*)更小,那么\boldsymbol{x}^*就不会是那个约束条件下的最优解了。所以,梯度向量\nabla f(\boldsymbol{x}^*)必然与约束条件g(\boldsymbol{x})=0的切线方向垂直。


    推论2:“函数f(\boldsymbol{x})的梯度方向也必然与函数自身等值线切线方向垂直。”

    推论2的粗浅论证:与推论1 的论证基本相同,如果f(\boldsymbol{x})的梯度方向不垂直于该点等值线的切线方向,f(\boldsymbol{x})就会在等值线上有变化,这条线也就不能称之为等值线了。

    根据推论1和推论2,函数f(\boldsymbol{x})的梯度方向在\boldsymbol{x}^*点同时垂直于约束条件g(\boldsymbol{x})=0和自身的等值线的切线方向,也就是说函数f(\boldsymbol{x})的等值线与约束条件曲线g(\boldsymbol{x})=0\boldsymbol{x}^*点具有相同(或相反)的法线方向所以它们在该点也必然相切。


    让我们再进一步,约束条件g(\boldsymbol{x})=0也可以被视为函数g(\boldsymbol{x})的一条等值线。按照推论2中“函数的梯度方向必然与自身的等值线切线方向垂直”的说法,函数g(\boldsymbol{x})\boldsymbol{x}^*点的梯度矢量\nabla g(\boldsymbol{x}^*)也与g(\boldsymbol{x})=0的切线方向垂直。

    到此我们可以将目标函数和约束条件视为两个具有平等地位的函数,并得到推论3:

    推论3:“函数f(\boldsymbol{x})与函数g(\boldsymbol{x})的等值线在最优解点\boldsymbol{x}^*处相切,即两者在\boldsymbol{x}^*点的梯度方向相同或相反”,

    于是我们可以写出公式(3.1),用来描述最优解\boldsymbol{x}^*的一个特性:

    \nabla f(\boldsymbol{x}^*)+\lambda \nabla g(\boldsymbol{x}^*)=0 (3.1)

    这里增加了一个新变量\lambda,用来描述两个梯度矢量的长度比例。那么是不是有了公式(3.1)就能确定\boldsymbol{x}^*的具体数值了呢?显然不行!从代数解方程的角度看,公式(3.1)相当于d个方程(假设\boldsymbol{x}^*是d维向量,函数f(\boldsymbol{x})的梯度就是d个偏导数组成的向量,所以公式(2.15)实际上是1个d维矢量方程,等价于d个标量方程),而未知数除了\boldsymbol{x}^*的d个分量以外,还有1个\lambda。所以相当于用d个方程求解d+1个未知量,应有无穷多组解;从几何角度看,在任意曲线g(\boldsymbol{\omega})=kk为值域范围内的任意实数)上都能至少找到一个满足公式(3.1)的点,也就是可以找到无穷多个这样的相切点。所以我们还需要增加一点限制,使得无穷多个解变成一个解。好在这个限制是现成的,那就是:


    g(\boldsymbol{x}^*)=0 (3.2)

    把公式(3.1)和(3.2)放在一起,我们有d+1个方程,解d+1个未知数,方程有唯一解,这样就能找到这个最优点\boldsymbol{x}^*了。

    2)构造拉格朗日函数

    虽然根据公式(3.1)和(3.2),已经可以求出等式约束条件下的最优解了,但为了在数学上更加便捷和优雅一点,我们按照本节初提到的思想,构造一个拉格朗日函数,将有约束优化问题转为无约束优化问题。拉格朗日函数具体形式如下:

    L(\boldsymbol{x},\lambda)=f(\boldsymbol{x})+\lambda g(\boldsymbol{x}) (3.3)

    新的拉格朗日目标函数有两个自变量\boldsymbol{x},\lambda,根据我们熟悉的求解无约束优化问题的思路,将公式(3.3)分别对\boldsymbol{x},\lambda求导,令结果等于零,就可以建立两个方程。同学们可以自己试一下,很容易就能发现这两个由导数等于0构造出来的方程正好就是公式(3.1)和(3.2)。说明新构造的拉格朗日目标函数的优化问题完全等价于原来的等式约束条件下的优化问题。

    至此,我们说明白了“为什么构造拉格朗日目标函数可以实现等式约束条件下的目标优化问题的求解”。可是,我们回头看一下公式(2.14),也就是我们的SVM优化问题的数学表达。囧,约束条件是不等式啊!怎么办呢?

    3.3 KKT条件

    对于不等式约束条件g(\boldsymbol{x})\leq0的情况,如图4所示,最优解所在的位置\boldsymbol{x}^*有两种可能,或者在边界曲线g(\boldsymbol{x})=0上或者在可行解区域内部满足不等式g(\boldsymbol{x})<0的地方。

    第一种情况:最优解在边界上,就相当于约束条件就是g(\boldsymbol{x})=0。参考图4,注意此时目标函数f(\boldsymbol{x})的最优解在可行解区域外面,所以函数f(\boldsymbol{x})在最优解\boldsymbol{x}^*附近的变化趋势是“在可行解区域内侧较大而在区域外侧较小”,与之对应的是函数g(\boldsymbol{x})在可行解区域内小于0,在区域外大于零,所以在最优解\boldsymbol{x}^*附近的变化趋势是内部较小而外部较大。这意味着目标函数f(\boldsymbol{x})的梯度方向与约束条件函数g(\boldsymbol{x})的梯度方向相反。因此根据公式(3.1),可以推断出参数\lambda>0.



    图4:不等式约束条件下最优解位置分布的两种情况


    第二种情况:如果在区域内,则相当于约束条件没有起作用,因此公式(3.3)的拉格朗日函数中的参数\lambda=0。整合这两种情况,可以写出一个约束条件的统一表达,如公式(3.4)所示。

    \begin{array}{lr} g(\boldsymbol{x})\leq0~ & (1)\\ \lambda\geq0~ & (2)\\ \lambda g(\boldsymbol{x})=0 & (3) \end{array} (3.4)

    其中第一个式子是约束条件本身。第二个式子是对拉格朗日乘子\lambda的描述。第三个式子是第一种情况和第二种情况的整合:在第一种情况里,\lambda>0,~g(\boldsymbol{x})=0;在第二种情况下,\lambda=0,~g(\boldsymbol{x})<0。所以无论哪一种情况都有\lambda g(\boldsymbol{x})=0。公式(3.4)就称为Karush-Kuhn-Tucker条件,简称KKT条件。

    推导除了KKT条件,感觉有点奇怪。因为本来问题的约束条件就是一个g(\boldsymbol{x})\leq0,怎么这个KKT条件又多弄出来两条,这不是让问题变得更复杂了吗?这里我们要适当的解释一下:

    1)KKT条件是对最优解的约束,而原始问题中的约束条件是对可行解的约束。

    2)KKT条件的推导对于后面马上要介绍的拉格朗日对偶问题的推导很重要。


    3.4 拉格朗日对偶

    接下来让我们进入重头戏——拉格朗日对偶。很多教材到这里自然而然的就开始介绍“对偶问题”的概念,这实际上是一种“先知式”的教学方式,对于学生研究问题的思路开拓有害无益。所以,在介绍这个知识点之前,我们先要从宏观的视野上了解一下拉格朗日对偶问题出现的原因和背景

    按照前面等式约束条件下的优化问题的求解思路,构造拉格朗日方程的目的是将约束条件放到目标函数中,从而将有约束优化问题转换为无约束优化问题。我们仍然秉承这一思路去解决不等式约束条件下的优化问题,那么如何针对不等式约束条件下的优化问题构建拉格朗日函数呢?

    因为我们要求解的是最小化问题,所以一个直观的想法是如果我能够构造一个函数,使得该函数在可行解区域内与原目标函数完全一致,而在可行解区域外的数值非常大,甚至是无穷大,那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化是等价的问题。

    拉格朗日对偶问题其实就是沿着这一思路往下走的过程中,为了方便求解而使用的一种技巧。于是在这里出现了三个问题:1)有约束的原始目标函数优化问题;2)新构造的拉格朗日目标函数优化问题;3)拉格朗日对偶函数的优化问题。我们希望的是这三个问题具有完全相同的最优解,而在数学技巧上通常第三个问题——拉格朗日对偶优化问题——最好解决。所以拉格朗日对偶不是必须的,只是一条捷径

    1)原始目标函数(有约束条件)

    为了接下来的讨论,更具有一般性,我们把等式约束条件也放进来,进而有约束的原始目标函数优化问题重新给出统一的描述:

    \begin{array}{lll} \min_{\boldsymbol{x}} & f(\boldsymbol{x}) & ~\\ \textrm{s. t.} & h_i(\boldsymbol{x})=0 & i=1,2,\ldots,m\\ ~ & g_j(\boldsymbol{x})\leq 0 & j = 1,2,\ldots,n\\ \end{array} (3.5)

    公式(3.5)表示m个等式约束条件和n个不等式约束条件下的目标函数f(\boldsymbol{x})的最小化问题。

    2)新构造的目标函数(没有约束条件)

    接下来我们构造一个基于广义拉格朗日函数的新目标函数,记为:

    \theta_P(\boldsymbol{x})=\max_{\boldsymbol{\alpha},~\boldsymbol{\beta};~\beta_j\geq0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) (3.6)

    其中L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})为广义拉格朗日函数,定义为:

    L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})=f(\boldsymbol{x})+\sum_{i=1}^m\alpha_i h_i(\boldsymbol{x})+\sum_{j=1}^n\beta_j g_i(\boldsymbol{x}) (3.7)

    这里,\boldsymbol{\alpha}=[\alpha_1,\alpha_2,\ldots, \alpha_m]^T,~\boldsymbol{\beta}=[\beta_1,\beta_2,\ldots, \beta_n]^T,是我们在构造新目标函数时加入的系数变量,同时也是公式(3.6)中最大化问题的自变量。将公式(3.7)带入公式(3.6)有:

    \theta_P(\boldsymbol{x})=\max_{\boldsymbol{\alpha},~\boldsymbol{\beta};~\beta_j\geq0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})= f(\boldsymbol{x})+\max_{\boldsymbol{\alpha},~\boldsymbol{\beta};~\beta_j\geq0}\left[ \sum_{i=1}^m\alpha_i h_i(\boldsymbol{x})+\sum_{j=1}^n\beta_j g_i(\boldsymbol{x}) \right](3.8)

    我们对比公式(3.5)中的约束条件,将论域范围分为可行解区域和可行解区域外两个部分对公式(3.8)的取值进行分析,将可行解区域记为\Phi,当\beta_j\geq0,j=1,2,\ldots,n时有:


    可行解区域内:由于h_i(\boldsymbol{x})=0~\forall ig_j(\boldsymbol{x})\leq0 且系数\beta_j\geq0,~\forall j, 所以有:


    \max_{\boldsymbol{\alpha},~\boldsymbol{\beta};~\beta_j\geq0}\left[ \sum_{i=1}^m\alpha_i h_i(\boldsymbol{x})+\sum_{j=1}^n\beta_j g_i(\boldsymbol{x}) \right] =0,~\textrm{for}~ \boldsymbol{x}\in\Phi (3.9)

    可行解区域外:代表公式(3.5)中至少有一组约束条件没有得到满足。如果h_i(\boldsymbol{x})\neq0,则调整系数\alpha_i就可以使\alpha_ih_i(\boldsymbol{x})\rightarrow +\infty;如果g_j(\boldsymbol{x})>0,调整系数\beta_j就可以使\beta_jg_j(\boldsymbol{x})\rightarrow +\infty。这意味着,此时有
    \max_{\boldsymbol{\alpha},~\boldsymbol{\beta};~\beta_j\geq0}\left[ \sum_{i=1}^m\alpha_i h_i(\boldsymbol{x})+\sum_{j=1}^n\beta_j g_i(\boldsymbol{x}) \right] =+\infty,~\textrm{for}~ \boldsymbol{x}\notin \Phi (3.10)

    把公式(3.8),(3.9)和(3.10)结合在一起就得到我们新构造的目标函数\theta_P(\boldsymbol{x})的取值分布情况:

    \theta_P(\boldsymbol{x})=\left\{ \begin{array}{ll} f(\boldsymbol{x}) & \boldsymbol{x}\in\Phi\\ +\infty & \textrm{otherwise} \end{array} \right. (3.11)

    此时我们回想最初构造新目标函数的初衷,就是为了建立一个在可行解区域内与原目标函数相同,在可行解区域外函数值趋近于无穷大的新函数。看看公式(3.11),yeah,我们做到了。

    现在约束条件已经没了,接下来我们就可以求解公式(3.12)的问题

    \min_{\boldsymbol{x}}\left[\theta_P(\boldsymbol{x})\right] (3.12)

    这个问题的解就等价于有约束条件下的原始目标函数f(\boldsymbol{x})最小化问题(公式3.5)的解。

    3)对偶问题

    尽管公式(3.12)描述的无约束优化问题看起来很美好,但一旦你尝试着手处理这个问题,就会发现一个麻烦。什么麻烦呢?那就是我们很难建立\theta_P(\boldsymbol{x})的显示表达式。如果再直白一点,我们很难直接从公式(3.8)里面把\boldsymbol{\alpha},\boldsymbol{\beta}这两组参数拿掉,这样我们就没法通过令\partial\theta_P(\boldsymbol{x})/\partial{\boldsymbol{x}}=\boldsymbol{0}的方法求解出最优解\boldsymbol{x}^*

    要解决这个问题,就得用一点数学技巧了,这个技巧就是对偶问题。我们先把公式(3.6)和公式(3.12)放在一起,得到关于新构造的目标函数的无约束优化的一种表达:

    \min_{\boldsymbol{x}}\left[\theta_P(\boldsymbol{x})\right]= \min_{\boldsymbol{x}}\left[ \max_{\boldsymbol{\alpha},\boldsymbol{\beta}:\beta_j\geq0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) \right] (3.13)

    然后我们再构造另一个函数,叫做\theta_D(\boldsymbol{\alpha},\boldsymbol{\beta})=\min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}),然后给出另外一个优化问题的描述:

    \max_{\boldsymbol{\alpha},\boldsymbol{\beta}:\beta_j\geq0}\left[\theta_D(\boldsymbol{\alpha},\boldsymbol{\beta})\right]= \max_{\boldsymbol{\alpha},\boldsymbol{\beta}:\beta_j\geq0} \left[ \min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) \right] (3.14)

    对比公式(3.13)和(3.14),发现两者之间存在一种对称的美感。所以我们就把(3.14)称作是(3.13)的对偶问题。现在我们可以解释一下\theta_P(\boldsymbol{x})中的P是原始问题Primary的缩写,\theta_D(\boldsymbol{\alpha},\boldsymbol{\beta})中的D是对偶问题Dual的缩写。如果我们能够想办法证明(3.14)和(3.13)存在相同的解\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*,那我们就可以在对偶问题中选择比较简单的一个来求解

    4)对偶问题同解的证明


    对偶问题和原始问题到底有没有相同的最优解呢?关于这个问题的根本性证明其实没有在这里给出,而且在几乎我看到的所有有关SVM的资料里都没有给出。但我比较厚道的地方是我至少可以告诉你哪里能找到这个证明。在给出证明的链接地址之前,我们先给一个定理,帮助大家做一点准备,同时也减少一点看那些更简略的资料时的困惑。

    定理一:对于任意\boldsymbol{\alpha},\boldsymbol{\beta}\boldsymbol{x}有:

    d^*=\max_{\boldsymbol{\alpha},\boldsymbol{\beta}:\beta_j\geq0} \left[ \min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) \right] \leq \min_{\boldsymbol{x}}\left[ \max_{\boldsymbol{\alpha},\boldsymbol{\beta}:\beta_j\geq0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) \right]= q^*

    定理一的证明:

    \theta_D(\boldsymbol{\alpha},\boldsymbol{\beta})=\min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) \leq L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) \leq \max_{\boldsymbol{\alpha},~\boldsymbol{\beta};~\beta_j\geq0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) = \theta_P(\boldsymbol{x})

    \theta_D(\boldsymbol{\alpha},\boldsymbol{\beta}) \leq \theta_P(\boldsymbol{x}) ~\forall \boldsymbol{\alpha},\boldsymbol{\beta},\boldsymbol{x}

    所以

    \max_{\boldsymbol{\alpha},\boldsymbol{\beta}:\beta_j\geq0} \theta_D(\boldsymbol{\alpha},\boldsymbol{\beta}) \leq \min_{\boldsymbol{x}} \theta_P(\boldsymbol{x})

    即:

    d^*\leq q^*

    这里的d^*,q^*分别是对偶问题和原始问题的最优值。

    定理一既引入了d^*,q^*的概念,同时也描述了两者之间的关系。我们可以在这个基础上再给一个推论:如果能够找到一组\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*使得\theta_D(\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*) = \theta_P(\boldsymbol{x}^*),那么就应该有:

    \theta_D(\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*) =d^*,~~ \theta_P(\boldsymbol{x}^*)=p^*,~~ d^*=p^*

    这个推论实际上已经涉及了原始问题与对偶问题的“强对偶性”。当d^*\leq q^*时,我们称原始问题与对偶问题之间“弱对偶性”成立;若d^*= q^*,则称“强对偶性”成立。

    如果我们希望能够使用拉格朗日对偶问题替换原始问题进行求解,则需要“强对偶性”作为前提条件。于是我们的问题变成了什么情况下,强对偶性才能够在SVM问题中成立。关于这个问题我们给出定理二:

    定理二:对于原始问题和对偶问题,假设函数f(\boldsymbol{x})和不等式约束条件g_j(\boldsymbol{x}),~\forall j凸函数,等式约束条件中的h_i(\boldsymbol{x})为仿射函数(即由一阶多项式构成的函数,h_i(\boldsymbol{x})=\boldsymbol{a}_i^T\boldsymbol{x}+b_i\boldsymbol{a}_i,\boldsymbol{x}均为列向量,b为标量);并且至少存在一个\boldsymbol{x}使所有不等式约束条件严格成立,即g_j({\boldsymbol{x}})<0,~\forall j,则存在\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*使得\boldsymbol{x}^*是原始问题的最优解,\boldsymbol{\alpha}^*,~\boldsymbol{\beta}^*是对偶问题的最优解且有:d^*=p^*=L(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*),并其充分必要条件如下

    \begin{array}{lr} \nabla_{\boldsymbol{x}}(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)=0 & (1)\\ \nabla_{\boldsymbol{\alpha}}(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)=0 & (2)\\ \nabla_{\boldsymbol{\beta}}(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)=0 & (3)\\ g_j(\boldsymbol{x}^*)\leq0,~j=1,2,\ldots,n & (4)\\ \beta_j^*\geq0,~j=1,2,\ldots,n & (5)\\ \beta_j^*g_j(\boldsymbol{x}^*)=0,~j=1,2,\ldots,n & (6)\\ h_i(\boldsymbol{x}^*)=0,~i=1,2,\ldots,m & (7)\\ \end{array} (3.15)

    再次强调一下,公式(3.15)是使\boldsymbol{x}^*为原始问题的最优解,\boldsymbol{\alpha}^*,~\boldsymbol{\beta}^*为对偶问题的最优解,且d^*=p^*=L(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)的充分必要条件。公式(3.15)中的(1)~(3),是为了求解最优化要求目标函数相对于三个变量\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}的梯度为0;(4)~(6)为KKT条件(见公式3.4(3)),这也是我们为什么要在3.3节先介绍KKT条件的原因;(7)为等式约束条件。

    定理二的证明详见 《Convex Optimization》, by Boyd and Vandenberghe. Page-234, 5.3.2节。stanford.edu/~boyd/cvxb


    关于拉格朗日对偶的一些参考资料:

    1. 简易解说拉格朗日对偶(Lagrange duality),这一篇对对偶问题的来龙去脉说的比较清楚,但是在强对偶性证明方面只给出了定理,没有给出证明过程,同时也缺少几何解释。

    2.优化问题中的对偶性理论,这一篇比较专业,关于对偶理论的概念,条件和证明都比较完整,在数学专业文献里属于容易懂的,但在我们这种科普文中属于不太好懂的,另外就是论述过程基本跟SVM没啥关系。

    3.5 拉格朗日对偶函数示例

    尽管上述介绍在代数层面已经比较浅显了,但是没有可视化案例仍然不容易建立起直观的印象。所以我尽可能的在这里给出一个相对简单但是有代表性的可视化案例。


    图5:有约束条件下的最优化问题可视化案例。

    图5中的优化问题可以写作:

    \begin{array}{ll} \min_{\boldsymbol{x}} & f(\boldsymbol{x})=x_1^2+x_2^2\\ \textrm{s. t.} & h(\boldsymbol{x})=x_1-x_2-2=0\\ ~ & g(\boldsymbol{x}) = (x_1-2)^2+x_2^2 -1\leq 0\\ \end{array} (3.16)

    之所以说这个案例比较典型是因为它与线性SVM的数学模型非常相似,且包含了等式和不等式两种不同的约束条件。更重要的是,这两个约束条件在优化问题中都起到了作用。如图5所示,如果没有任何约束条件,最优解在坐标原点(0, 0)处(青色X);如果只有不等式约束条件 g(\boldsymbol{x})\leq 0 ,最优解在坐标(1,0)处(红色X);如果只有等式约束条件 h(\boldsymbol{x})=0 ,最优解在坐标(1,-1)处(绿色+);如果两个约束条件都有,最优解在 (2-\sqrt{2}/2,-\sqrt{2}/2) 处(黄色O)。

    针对这一问题,我们可以设计拉格朗日函数如下:L(\boldsymbol{x},\alpha,\beta)=(x_1^2+x_2^2)+\alpha(x_1-x_2-2)+\beta\left[(x_1-2)^2+x_2^2-1\right] (3.17)

    根据公式(3.11),函数 \theta_p(\boldsymbol{x}) 只在绿色直线在红色圆圈内的部分——也就是直线 h(\boldsymbol{x})=0 在圆 g(\boldsymbol{x})=0 上的弦——与原目标函数 f(\boldsymbol{x}) 取相同的值,而在其他地方均有 \theta_P(\boldsymbol{x})=+\infty ,如图6所示。


    图6: \theta_P(\boldsymbol{x}) (除了图中绿色虚线部分,其他部分的函数值均为无穷大)。

    (需要注意的是,此处不能使用对 \alpha,\beta 求导等于0的方式消掉 \alpha,\beta ,因为函数 L(\boldsymbol{x},\alpha,\beta)在 \boldsymbol{x} 为确定值时,是 \alpha,\beta 的线性函数,其极大值并不在梯度为0的地方)。由于函数 f(\boldsymbol{x}) 在没有约束条件下的最优解并不在这条弦上,所以显然对 \theta_P(\boldsymbol{x}) 求导等于零的方法是找不到最优解 \boldsymbol{x}^* 的。但是对于这个简单的问题,还是能够从图中看到最优解应该在 :

    [x_1^*,x_2^*]=[2-\sqrt{2}/2,-\sqrt{2}/2]

    由于该最优解是在 h(\boldsymbol{x})=0 和 g(\boldsymbol{x})=0 的交点处,所以可以很容易地理解:当 \boldsymbol{x}=[x_1^*,x_2^*]^T 时,无论 \alpha,\beta 取什么值都可以使函数 L(\boldsymbol{x},\alpha,\beta) 达到最小值。

    然而这个最优解是依靠几何推理的方式找到的,对于复杂的问题,这种方法似乎不具有可推广性。

    那么,我们不妨尝试一下,用拉格朗日对偶的方式看看这个问题。我们将 \alpha,\beta 视为常数,这时 L(\boldsymbol{x},\alpha,\beta) 就只是 \boldsymbol{x} 的函数。我们可以通过求导等于零的方式寻找其最小值,即 \theta_D(\alpha,\beta)=\min_\boldsymbol{x}\left[L(\boldsymbol{x},\alpha,\beta)\right] 。我们对公式(3.17)对 x_1,x_2 分别求偏导,令其等于0,有:

    \left\{\begin{array}{l} \alpha + 2x_1 + \beta (2x_1 - 4)=0\\ 2x_2 - \alpha + 2\beta x_2=0 \end{array}\right. (3.18)

    可以解得:

    \left\{ \begin{array}{l} x_1 = \frac{4\beta-a}{2\beta + 2}\\ x_2 = \frac{\alpha}{2\beta + 2} \end{array}\right. (3.19)

    将(3.19)带入(3.17)可以得到:

    \theta_D(\alpha,\beta)= -\frac{\alpha^2 + 4\, \alpha + 2\, \beta^2 - 6\, \beta}{2\, \left(\beta + 1\right)} (3.20)

    考虑到(3.15)中的条件(5),我们将函数(3.20)在 \beta\geq0 的 \alpha\times\beta 论域画出来,如图7所示。可以通过 \theta_D(\alpha,\beta) 对 \alpha,\beta 求导等于0的方式解出最优解 \alpha^*=-2,~\beta^*=\sqrt{2}-1 ,将其带入公式(3.19)可以得到 \boldsymbol{x}^*=[x_1^*,x_2^*]=[2-\sqrt{2}/2,-\sqrt{2}/2]


    最后通过对比,我们看到拉格朗日原始问题和对偶问题得到了相同的最优解(原始问题的最优解中 \alpha^*,\beta^* 可以是任何值)。

    最后,我来解释一下鞍点的问题。鞍点的概念大家可以去网上找,形态上顾名思义,就是马鞍的中心点,在一个方向上局部极大值,在另一个方向上局部极小值。这件事跟我们的拉格朗日函数有什么关系呢?由于这个例子中的拉格朗日函数包含 x_1,x_2,\alpha,\beta 四个自变量,无法直接显示。为了更好的可视化,我们固定住其中两个变量,令 x_2 = -\sqrt{2}/2,\beta = \sqrt{2}-1。此时拉格朗日函数就变成一个可以可视化的二元函数 L(x_1,\alpha) ,我们把它的曲面画出来。


    图8: L(x_1,\alpha) 可视化效果

    图8(a)中的最优点 (x_1^*,\alpha^*)可以能够两个角度去定义,如图8(b)所示。(为加以区别二维和四维的情况,我们将四维情况对应的 \theta_P,\theta_D 大写的下角标P和D改写为小写的p和d)。

    第一种定义:沿着与 \alpha 轴平行的方向将曲面切成无数条曲线(红色虚线),在每条红色虚线上找到最大值(绿色圆点),即 \theta_p(x_1)=\max_{\alpha}(L(x_1,\alpha)) ,然后在所有的 \theta_p(x_1) 找到最小的那个(蓝色圆点),即 \min_{x_1}\theta_p(x_1) 。

    第二种定义:沿着与 x_1 轴平行的方向将曲面切成无数条曲线(绿色虚线),在每条绿色虚线上找到最小值(红色圆点),即 \theta_d(\alpha) = \min_{x_1}(L(x_1,\alpha)) ,然后在所有的 \theta_d(\alpha) 中找到最大的那个(蓝色圆点),即 \max_{\alpha}\theta_d(\alpha) 。

    从图8的二维情况思考神秘的四维空间中的拉格朗日函数, \theta_p(x_1) 就变成了 \theta_p(\boldsymbol{x}) , \theta_d(\alpha) = \theta_d(\alpha,\beta) ,如图8(b)所示。其实四元函数 L(x_1,x_2,\alpha,\beta) 就是一个定义在4维空间上的鞍形函数,这个从两种思路共同得到的蓝色点就是函数 L(x_1,x_2,\alpha,\beta) 的鞍点,也就是我们要找的最优解。在这个二元化的图中,拉格朗日对偶问题和拉格朗日原始问题的差别就是:原始问题采用第一种定义去求解鞍点,对偶问题采用第二种方法去求解鞍点。

    四、线性SVM优化问题求解

    4.1 基于拉格朗日乘子法的线性SVM优化问题模型

    从第三章开始,我们花了相当长的时间来介绍优化技术。目的是为线性SVM问题的求解打好数学基础。接下来,让我们把目光转回公式(2.14)描述的线性SVM问题的基本模型,为了方便大家阅读,这里重新给出公式(2.14)

    \begin{array}{l} \min_{\boldsymbol{\omega},\gamma}\frac{1}{2}||\boldsymbol{\omega}||^2\\ ~\\ \textrm{s. t.}~ ~y_i(\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma)\geq 1,~~i = 1,2,...,m \end{array} (2.14)

    显然,这是一个具有多个不等式约束条件的优化问题,其拉格朗日函数可以写为:

    L(\boldsymbol{\omega},\gamma,\boldsymbol{\alpha})=\frac{||\boldsymbol{\omega}||^2}{2}+\sum_{i=1}^m\alpha_i(1-y_i(\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma)) (3.21)

    这里 \boldsymbol{\omega}=[\omega_1,\omega_2,\ldots,\omega_d]^T , \boldsymbol{\alpha} = [\alpha_1,\alpha_2,\ldots,\alpha_m]^T 。该拉格朗日函数最优化的原始问题和对偶问题分别为:

    原始问题: \min_{\boldsymbol{\omega},\gamma}\left[ \max_{\boldsymbol{\alpha}:\alpha_j\geq0}L(\boldsymbol{\omega},\gamma,\boldsymbol{\alpha}) \right] (3.22)

    对偶问题: \max_{\boldsymbol{\alpha}:\alpha_j\geq0}\left[ \min_{\boldsymbol{\omega},\gamma}L(\boldsymbol{\omega},\gamma,\boldsymbol{\alpha}) \right] (3.23)

    根据第三章的推导,我们对拉格朗日对偶问题进行求解,根据公式(3.23)首先求解\min_{\boldsymbol{\omega},\gamma}L(\boldsymbol{\omega},\gamma,\boldsymbol{\alpha}) = \min_{\boldsymbol{\omega},\gamma}\left[\frac{1}{2}||\boldsymbol{\omega}||^2+\sum_{i=1}^m{\alpha_i(1-y_i(\boldsymbol{\omega}^T\boldsymbol{x}_i+\gamma))}\right] (3.24)

    为了求拉格朗日函数的极小值,分别令函数 L(\boldsymbol{\omega},\gamma,\boldsymbol{\alpha}) 对 \boldsymbol{\omega},\gamma 求偏导,并使其等于0。

    \frac{\partial{L}}{\partial{\boldsymbol{\omega}}}=0~\Longrightarrow \boldsymbol{\omega}=\sum_{i=1}^m{\alpha_iy_i\boldsymbol{x}_i} (3.25)

    \frac{\partial{L}}{\partial{\gamma}}=0~\Longrightarrow 0=\sum_{i=1}^m{\alpha_iy_i} (3.26)

    (这里介绍一下矢量积求导的基本公式,方便大家理解(3.25)的推导过程。假设f = \boldsymbol{x}^T\boldsymbol{y} , \boldsymbol{x}=[x_1,x_2,\ldots,x_d]^T , \boldsymbol{y}=[y_1,y_2,\ldots,y_d]^T ,则有 \frac{\partial f}{\partial\boldsymbol{x}}=\boldsymbol{y} ,有兴趣大家可以自己推导一下,非常简单!)

    这里要特别提到的是,由于参数向量 \boldsymbol{\omega} 是一个d维矢量,因此公式3.24是一个矢量方程,相当于d个标量方程。将公式(3.25)带入到公式(3.24)可以得到:

    \min_{\boldsymbol{\omega},\gamma}L(\boldsymbol{\omega},\gamma,\alpha)=\frac{1}{2} \left[\sum_{i=1}^m{\alpha_iy_i\boldsymbol{x}_i}\right]^T\left[\sum_{i=1}^m{\alpha_iy_i\boldsymbol{x}_i}\right]+\sum_{i=1}^m\alpha_i-\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j(3.27)

    根据多项式乘法的基本规律(所有项和的积等于所有项积的和),不难明白(注意向量 \boldsymbol{x}_i是列向量):

    \left[\sum_{i=1}^m{\alpha_iy_i\boldsymbol{x}_i}\right]^T\left[\sum_{i=1}^m{\alpha_iy_i\boldsymbol{x}_i}\right] =\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j (3.28)

    所以公式(3.27)可以化简为:

    \min_{\boldsymbol{\omega},\gamma}L(\boldsymbol{\omega},\gamma,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j (3.29)

    将(3.29)带入对偶问题的公式(3.23),同时考虑公式(3.26)给出的约束,可以将SVM的优化问题转变为:

    \begin{array}{l} \max_{\boldsymbol{\alpha}}\left[ \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j \right]\\ \textrm{s.t.}~~ \sum_{i=1}^m{\alpha_iy_i}=0\\ ~~~~~~~~\alpha_j\geq0, i = 1,2,\ldots,m. \end{array} (3.30)


    转自:https://zhuanlan.zhihu.com/p/24638007

    展开全文
  • svm原理详解,看完就懂(一)

    万次阅读 2019-02-15 17:06:39
    (一)SVM的八股简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中[10]...

    (一)SVM的八股简介

    支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中[10]。
    支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度,Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,以期获得最好的推广能力[14](或称泛化能力)。

    以上是经常被有关SVM 的学术文献引用的介绍,有点八股,我来逐一分解并解释一下。

    Vapnik是统计机器学习的大牛,这想必都不用说,他出版的《Statistical Learning Theory》是一本完整阐述统计机器学习思想的名著。在该书中详细的论证了统计机器学习之所以区别于传统机器学习的本质,就在于统计机器学习能够精确的给出学习效果,能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比,传统的机器学习基本上属于摸着石头过河,用传统的机器学习方法构造分类系统完全成了一种技巧,一个人做的结果可能很好,另一个人差不多的方法做出来却很差,缺乏指导和原则。

    所谓VC维是对函数类的一种度量,可以简单的理解为问题的复杂程度,VC维越高,一个问题就越复杂。正是因为SVM关注的是VC维,后面我们可以看到,SVM解决问题的时候,和样本的维数是无关的(甚至样本是上万维的都可以,这使得SVM很适合用来解决文本分类的问题,当然,有这样的能力也因为引入了核函数)。

    结构风险最小听上去文绉绉,其实说的也无非是下面这回事。

    机器学习本质上就是一种对问题真实模型的逼近(我们选择一个我们认为比较好的近似模型,这个近似模型就叫做一个假设),但毫无疑问,真实模型一定是不知道的(如果知道了,我们干吗还要机器学习?直接用真实模型解决问题不就可以了?对吧,哈哈)既然真实模型不知道,那么我们选择的假设与问题真实解之间究竟有多大差距,我们就没法得知。比如说我们认为宇宙诞生于150亿年前的一场大爆炸,这个假设能够描述很多我们观察到的现象,但它与真实的宇宙模型之间还相差多少?谁也说不清,因为我们压根就不知道真实的宇宙模型到底是什么。

    这个与问题真实解之间的误差,就叫做风险(更严格的说,误差的累积叫做风险)。我们选择了一个假设之后(更直观点说,我们得到了一个分类器以后),真实误差无从得知,但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果(因为样本是已经标注过的数据,是准确的数据)之间的差值来表示。这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标,但后来发现很多分类函数能够在样本集上轻易达到100%的正确率,在真实分类时却一塌糊涂(即所谓的推广能力差,或泛化能力差)。此时的情况便是选择了一个足够复杂的分类函数(它的VC维很高),能够精确的记住每一个样本,但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现,此原则适用的大前提是经验风险要确实能够逼近真实风险才行(行话叫一致),但实际上能逼近么?答案是不能,因为样本数相对于现实世界要分类的文本数来说简直九牛一毛,经验风险最小化原则只在这占很小比例的样本上做到没有误差,当然不能保证在更大比例的真实文本上也没有误差。

    统计学习因此而引入了泛化误差界的概念,就是指真实风险应该由两部分内容刻画,一是经验风险,代表了分类器在给定样本上的误差;二是置信风险,代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。很显然,第二部分是没有办法精确计算的,因此只能给出一个估计的区间,也使得整个误差只能计算上界,而无法计算准确的值(所以叫做泛化误差界,而不叫泛化误差)。

    置信风险与两个量有关,一是样本数量,显然给定的样本数量越大,我们的学习结果越有可能正确,此时置信风险越小;二是分类函数的VC维,显然VC维越大,推广能力越差,置信风险会变大。

    泛化误差界的公式为:

    R(w)≤Remp(w)+Ф(n/h)

    公式中R(w)就是真实风险,Remp(w)就是经验风险,Ф(n/h)就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小,即结构风险最小。

    SVM正是这样一种努力最小化结构风险的算法。

    SVM其他的特点就比较容易理解了。

    小样本,并不是说样本的绝对数量少(实际上,对任何算法来说,更多的样本几乎总是能带来更好的效果),而是说与问题的复杂度比起来,SVM算法要求的样本数是相对比较少的。

    非线性,是指SVM擅长应付样本数据线性不可分的情况,主要通过松弛变量(也有人叫惩罚变量)和核函数技术来实现,这一部分是SVM的精髓,以后会详细讨论。多说一句,关于文本分类这个问题究竟是不是线性可分的,尚没有定论,因此不能简单的认为它是线性可分的而作简化处理,在水落石出之前,只好先当它是线性不可分的(反正线性可分也不过是线性不可分的一种特例而已,我们向来不怕方法过于通用)。

    高维模式识别是指样本维数很高,例如文本的向量表示,如果没有经过另一系列文章(《文本分类入门》)中提到过的降维处理,出现几万维的情况很正常,其他算法基本就没有能力应付了,SVM却可以,主要是因为SVM 产生的分类器很简洁,用到的样本信息很少(仅仅用到那些称之为“支持向量”的样本,此为后话),使得即使样本维数很高,也不会给存储和计算带来大麻烦(相对照而言,kNN算法在分类时就要用到所有样本,样本数巨大,每个样本维数再一高,这日子就没法过了……)。

    下一节开始正式讨论SVM。别嫌我说得太详细哦。

     

    SVM入门(二)线性分类器Part 1

    线性分类器(一定意义上,也可以叫做感知机) 是最简单也很有效的分类器形式.在一个线性分类器中,可以看到SVM形成的思路,并接触很多SVM的核心概念.

    用一个二维空间里仅有两类样本的分类问题来举个小例子。如图所示

    clip_image002

    C1和C2是要区分的两个类别,在二维平面中它们的样本如上图所示。中间的直线就是一个分类函数,它可以将两类样本完全分开。一般的,如果一个线性函数能够将样本完全正确的分开,就称这些数据是线性可分的,否则称为非线性可分的。

    什么叫线性函数呢?在一维空间里就是一个点,在二维空间里就是一条直线,三维空间里就是一个平面,可以如此想象下去,如果不关注空间的维数,这种线性函数还有一个统一的名称——超平面(Hyper Plane)!

    实际上,一个线性函数是一个实值函数(即函数的值是连续的实数),而我们的分类问题(例如这里的二元分类问题——回答一个样本属于还是不属于一个类别的问题)需要离散的输出值,例如用1表示某个样本属于类别C1,而用0表示不属于(不属于C1也就意味着属于C2),这时候只需要简单的在实值函数的基础上附加一个阈值即可,通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。 例如我们有一个线性函数

    g(x)=wx+b

    我们可以取阈值为0,这样当有一个样本xi需要判别的时候,我们就看g(xi)的值。若g(xi)>0,就判别为类别C1,若g(xi)<0,则判别为类别C2(等于的时候我们就拒绝判断,呵呵)。此时也等价于给函数g(x)附加一个符号函数sgn(),即f(x)=sgn [g(x)]是我们真正的判别函数。

    关于g(x)=wx+b这个表达式要注意三点:一,式中的x不是二维坐标系中的横轴,而是样本的向量表示,例如一个样本点的坐标是(3,8),则xT=(3,8) ,而不是x=3(一般说向量都是说列向量,因此以行向量形式来表示时,就加上转置)。二,这个形式并不局限于二维的情况,在n维空间中仍然可以使用这个表达式,只是式中的w成为了n维向量(在二维的这个例子中,w是二维向量,为了表示起来方便简洁,以下均不区别列向量和它的转置,聪明的读者一看便知);三,g(x)不是中间那条直线的表达式,中间那条直线的表达式是g(x)=0,即wx+b=0,我们也把这个函数叫做分类面。

    实际上很容易看出来,中间那条分界线并不是唯一的,我们把它稍微旋转一下,只要不把两类数据分错,仍然可以达到上面说的效果,稍微平移一下,也可以。此时就牵涉到一个问题,对同一个问题存在多个分类函数的时候,哪一个函数更好呢?显然必须要先找一个指标来量化“好”的程度,通常使用的都是叫做“分类间隔”的指标。下一节我们就仔细说说分类间隔,也补一补相关的数学知识。

    SVM入门(三)线性分类器Part 2

    上回说到对于文本分类这样的不适定问题(有一个以上解的问题称为不适定问题),需要有一个指标来衡量解决方案(即我们通过训练建立的分类模型)的好坏,而分类间隔是一个比较好的指标。

    在进行文本分类的时候,我们可以让计算机这样来看待我们提供给它的训练样本,每一个样本由一个向量(就是那些文本特征所组成的向量)和一个标记(标示出这个样本属于哪个类别)组成。如下:

    Di=(xi,yi)

    xi就是文本向量(维数很高),yi就是分类标记。

    在二元的线性分类中,这个表示分类的标记只有两个值,1和-1(用来表示属于还是不属于这个类)。有了这种表示法,我们就可以定义一个样本点到某个超平面的间隔:

    δi=yi(wxi+b)

    这个公式乍一看没什么神秘的,也说不出什么道理,只是个定义而已,但我们做做变换,就能看出一些有意思的东西。

    首先注意到如果某个样本属于该类别的话,那么wxi+b>0(记得么?这是因为我们所选的g(x)=wx+b就通过大于0还是小于0来判断分类),而yi也大于0;若不属于该类别的话,那么wxi+b<0,而yi也小于0,这意味着yi(wxi+b)总是大于0的,而且它的值就等于|wxi+b|!(也就是|g(xi)|)

    现在把w和b进行一下归一化,即用w/||w||和b/||w||分别代替原来的w和b,那么间隔就可以写成

    clip_image002[28]

    这个公式是不是看上去有点眼熟?没错,这不就是解析几何中点xi到直线g(x)=0的距离公式嘛!(推广一下,是到超平面g(x)=0的距离, g(x)=0就是上节中提到的分类超平面)

    小Tips:||w||是什么符号?||w||叫做向量w的范数,范数是对向量长度的一种度量。我们常说的向量长度其实指的是它的2-范数,范数最一般的表示形式为p-范数,可以写成如下表达式

        向量w=(w1, w2, w3,…… wn)

    它的p-范数为

    clip_image004[10]

     

    看看把p换成2的时候,不就是传统的向量长度么?当我们不指明p的时候,就像||w||这样使用时,就意味着我们不关心p的值,用几范数都可以;或者上文已经提到了p的值,为了叙述方便不再重复指明。

    当用归一化的w和b代替原值之后的间隔有一个专门的名称,叫做几何间隔,几何间隔所表示的正是点到超平面的欧氏距离,我们下面就简称几何间隔为“距离”。以上是单个点到某个超平面的距离(就是间隔,后面不再区别这两个词)定义,同样可以定义一个点的集合(就是一组样本)到某个超平面的距离为此集合中离超平面最近的点的距离。下面这张图更加直观的展示出了几何间隔的现实含义:

    image

    H是分类面,而H1和H2是平行于H,且过离H最近的两类样本的直线,H1与H,H2与H之间的距离就是几何间隔。

    之所以如此关心几何间隔这个东西,是因为几何间隔与样本的误分次数间存在关系:

    clip_image012

    其中的δ是样本集合到分类面的间隔,R=max ||xi||  i=1,...,n,即R是所有样本中(xi是以向量表示的第i个样本)向量长度最长的值(也就是说代表样本的分布有多么广)。先不必追究误分次数的具体定义和推导过程,只要记得这个误分次数一定程度上代表分类器的误差。而从上式可以看出,误分次数的上界由几何间隔决定!(当然,是样本已知的时候)

    至此我们就明白为何要选择几何间隔来作为评价一个解优劣的指标了,原来几何间隔越大的解,它的误差上界越小。因此最大化几何间隔成了我们训练阶段的目标,而且,与二把刀作者所写的不同,最大化分类间隔并不是SVM的专利,而是早在线性分类时期就已有的思想。

    下一节讲解线性分类器的求解问题

    转载自http://www.blogjava.net/zhenandaci/category/31868.html 

    展开全文
  • SVM原理简介

    2017-01-13 09:44:00
    以下是我通过学习后对SVM原理的理解与总结,记录下来以便自己复习。 1、SVM原理概述 SVM是从线性可分情况下的最优分类面发展而来的,图一中三角形点和圆形点分别代表两类样本,假设: ,i=1,...,n, 我们要寻找...

    SVM是我在做模式识别的时候用得最多的一种分类器。以下是我通过学习后对SVM原理的理解与总结,记录下来以便自己复习。

     

    1、SVM原理概述

    SVM是从线性可分情况下的最优分类面发展而来的,图一中三角形点和圆形点分别代表两类样本,假设:

    ,i=1,...,n,

    我们要寻找一个分类超平面H:,使得:

     假设 分别为过各类中离分类超平面最近的样本并且平行于分类超平面的超平面,它们之间的距离叫做分类间隔。最优分类超平面要求不但能把两类样本正确分开,而且要求分类间隔最大。易知分类间隔为2/||W||,使分类间隔最大,等价于与使||W||最小。所以求最优分类超平面求解下例问题:

    H1,H2上的训练样本点就称作支持向量。

                      图一

    利用Lagrange优化方法可以把上述最优分类面问题转化为其对偶问题:

     

    其中αi为与每个样本对应的Lagrange乘子,容易证明解中有一部分(通常是少部分),若αi不为零,对应的样本就是支持向量。解上述问题后得到的最优分类函数是:

    在线性不可分的情况下,可以增加一个松弛项,使求解最优分类超平面变为下述问题:

    即折衷考虑最少分错样本与最大分类间隔,得到广义最优分类超平面,其中C为惩罚系数。对应的对偶问题变为:

     

    对于非线性问题,可以通过非线性变换转化为某个高维空间中的线性问题,在变换空间求解最优分类面。

    在最优分类面中采用适当的内积函数K(xi,xj)就可以实现某一非线性变换后的线性分类:

    分类函数变为:

     

    这就是支持向量机。

    总结起来,SVM的基本思想如图二所示:

     

                            图二

     

    2、核函数

     目前研究最多的核函数主要有四类:

    通常来讲,RBF核函数可以作为一个SVM模型的最佳选择。RBF核通过非线性映射将样本映射到一个高维空间中,因此,相较于线性核函数,它能很好地处理类别标签与属性之间为非线性关系的情况。而且,线性核可以看做RBF核的一种特殊情况,在某些参数下,线性核具有与RBF核相同的表现。另外,研究显示sigmoid核在某些参数下也与RBF核具有相同表现。选择RBF核的第二个理由是超参数的数量影响着模型选择的复杂性,多项式核的超参数比RBF核更多,因此复杂性也会相应提高。最后,RBF核在数值计算上难度较小。这些都使得RBF核在SVM中有着更好的表现。然而,并非所有情况下RBF核都是最适合的。特别地,当特征维数非常大时,我们可以考虑线性核数。

     

    3、多类分类SVM    

     (1)一对一组合分类  :

     设共有k个类,各类之间两两构造分类函数(共k(k-1)/2个)。预测样本经过每个分类器投票,判定为得票数最多的类。但是如果k过大,k(k-1)/2会非常庞大,使预测过程变慢。libsvm使用的就是这种策略。

    (2)一对余组合分类

    设共有k个类,每一类和余类之间构造分类函数(共k个),取分类函数输出值最大的类别为预测类别。这种方法推广能力比较差,训练时间很长,效率比较低,存在决策盲区。

    还有其他的多类分类法,如决策树。

     

    4、SVM的概率输出

    在分类模型中,P(y|x)是在样本为X的条件下标签为y的概率也就是样本的后验概率。我们知道 ,SVM并不是概率模型 ,无法直接输出样本的后验概率。可以使用sigmoid函数估计样本Xi标签为的后验概率:

    其中,A、B是估计值,是SVM的决策函数值。

    在多类分类问题中,可以使用一对一的策略,构造k(k-1)/2个二类SVM,设之间的二类SVM的后验概率为,则对于一个样本xi,标签为的概率可用下式计算:

     

    参考文献:

    [1]Hsu C W, Chang C C, Lin C J. A Practical Guide to Support Vector Classication[J]. 臺北市:國立臺灣大學資訊工程學系, 2003, 67(5).

    [2]Platt J C. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods[J]. Advances in Large Margin Classifiers, 2000, 10:61--74.

     

    转载于:https://www.cnblogs.com/tacia/p/6281568.html

    展开全文
  • svm基本原理,python代码实现,拉格朗日与KKT算法描述
  • SVM原理及推导过程

    千次阅读 2019-06-17 17:38:51
    SVM核心是最优化方法(带约束条件,拉格朗日乘子法),思想是max(min),即最大化最小间隔(找到最小间隔的点,即支持向量),目标就是求解参数alpha、w、b,确定超平面,然后就能正常的二分类(和逻辑回归类似);...
  • SVM原理

    2018-08-28 23:35:30
    (1)SVM的引入,线性可分(通常,先是看二维)——后在一并假设在高维空间中也能找到一条线性可分的直线;由于直线可旋转,因此满足条件的有很多条,怎么选择最好的那一条,需要引入刻画该线性可分模型的分割,注意...
  • SVM原理篇之手撕SVM

    万次阅读 多人点赞 2018-07-23 16:44:47
    转载请注明作者和出处: https://zhuanlan.zhihu.com/ml-jack 机器学习知乎专栏:https://zhuanlan.zhihu.com/ml-jack CSDN博客专栏:http://blog.csdn.net/column/details/16415.html Github代码获取:h...
  • svm原理详细推导

    千次阅读 2018-10-29 17:50:54
    笔者在查阅了大量资料和阅读大佬的讲解之后,终于对svm有了比较深一点的认识,先将理解的推导过程分享如下: 本文主要从如下五个方面进行介绍:基本推导,松弛因子,核函数,SMO算法,小结五个方面以%%为分隔,同时...
  • SVM原理详解

    千次阅读 2016-07-25 14:53:31
    SVM入门(一)至(三)Refresh 按:之前的文章重新汇编一下,修改了一些错误和不当的说法,一起复习,然后继续SVM之旅. (一)SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先...
  • svm 原理和hog的描述

    2019-01-24 13:01:58
    再次感谢网上大佬们的文章 一、理论 参考网友的博客: (1)【理论】支持向量机1: Maximum Margin Classifier —— 支持向量机简介 (2)【理论】支持向量机2: Support Vector —— 介绍支持向量机目标函数的 dual ...
  • 支持向量机SVM 原理、推导与Matlab实现

    万次阅读 多人点赞 2017-07-13 19:00:15
    2 SVM原理我们前面学过了线性回归和线性分类器。我们来回顾一下。2.1 线性回归线性回归试图找到一条线,让每个点在Y方向上离线越接近越好。就是说,每个数据点做一条垂直的线相较于回归直线,这些线段(图中红色线段...
  • 1.1. SVM介绍1.2. 工作原理 1.2.1. 几何间隔和函数间隔1.2.2. 最大化间隔 1.3. 软间隔1.4. SMO算法1.5. 核函数1.6. 实例 1.1. SVM介绍 SVM(Support Vector Machines)——支持向量机是在所有知名的数据...
  • 一直在犹豫要不要写SVM,因为网上已经有很多详细的SVM原理的解释甚至详细推导,而这东西又庞大复杂,想了解的话直接可以参考。说实话,SVM确实到现在也不是说很懂,感觉最恐怖的是对偶问题后的KKT推导、Mercer定理...
  • 【机器学习】支持向量机SVM原理及推导

    万次阅读 多人点赞 2017-11-02 17:54:03
    SVM原理和推导
  • CSDN地址:https://blog.csdn.net/DP323/article/details/80535863 原地址:http://www.blogjava.net/zhenandaci/category/31868.html
1 2 3 4 5 ... 20
收藏数 26,468
精华内容 10,587
关键字:

svm原理