支持向量机
支持向量机
1基本情况
Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起,然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去,这种分类器被称为支持向量机(Support Vector Machine,简称SVM)。支持向量机的提出有很深的理论背景
支持向量机方法是在近年来提出的一种新方法。
SVM的主要思想可以概括为两点:
⑴它是针对线性可分情况进行分析,对于线性不可分的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能;
⑵它基于结构风险最小化理论之上在特征空间中建构最优分割超平面,
使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。
例子
如图:
将1维的“线性不可分”上升到2维后就成为线性可分了。
在学习这种方法时,首先要弄清楚这种方法考虑问题的特点,这就要从线性可分的最简单情况讨论起,在没有弄懂其原理之前,不要急于学习线性不可分等较复杂的情况,支持向量机在设计时,需要用到条件极值问题的求解,因此需用拉格朗日乘子理论。
2一般特征
⑴SVM学习问题可以表示为凸优化问题,因此可以利用已知的有效算法发现目标函数
的全局最小值。而其他分类方法(如基于规则的分类器和人工神经网络)都采用一种基于贪心学习的策略来搜索假设空间,这种方法一般只能获得局部最优解。
⑵SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此,用户必须提供其他参数,如使用核函数类型和引入松弛变量等。
⑶通过对数据中每个分类属性引入一个哑变量,SVM可以应用于分类数据。
⑷SVM一般只能用在二类问题,对于多类问题效果不好。
3原理简介
SVM方法是通过一个非线性映射p,把样本空间映射到一个高维乃至无穷维的特征空间中(Hilbert空间),使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题.简单地说,就是升维和线性化.升维,就是把样本向高维空间做映射,一般情况下这会增加计算的复杂性,甚至会引起“维数灾难”,因而人们很少问津.但是作为分类、回归等问题来说,很可能在低维样本空间无法线性处理的样本集,在高维特征空间中却可以通过一个线性超平面实现线性划分(或回归).一般的升维都会带来计算的复杂化,SVM方法巧妙地解决了这个难题:应用核函数的展开定理,就不需要知道非线性映射的显式表达式;由于是在高维特征空间中建立线性学习机,所以与线性模型相比,不但几乎不增加计算的复杂性,而且在某种程度上避免了“维数灾难”.这一切要归功于核函数的展开和计算理论.
选择不同的核函数,可以生成不同的SVM,常用的核函数有以下4种:
⑴线性核函数K(x,y)=x·y;
⑵多项式核函数K(x,y)=[(x·y)+1]^d;
⑶径向基函数K(x,y)=exp(-|x-y|^2/d^2)
⑷二层神经网络核函数K(x,y)=tanh(a(x·y)+b).
最优分类面:最优超平面
SVM是从线性可分情况下的最优分类面发展而来的,基本思想可用图2的两维情况说明。
如图:方形点和圆形点代表两类样本,H为分类线,H1,H2分别为过各类中离分类线最近的样本且平行于分类线的直线,他们之间的距离叫分类间隔。
最优分类线就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。
推广到高维空间,最优分类线就变为最优分类面。
设线性可分的样本集(xi,yi),i=1,…,n,x∈Rd,y∈{+1,-1}。d维空间中的线性判别函数:g(x)=wx-b,分类面方程为:wx-b=0。
我们可以对它进行归一化,使得所有样本都满足| g(x)|>=1,即分类面最近的样本满足g(x)=1,这样分类间隔就等于2/||W||,因此要求分类间隔最大,就是要求||W||或||W||2最小。而要求分类面对所有样本正确分类,就是要求满足:
yi[wxi+b]-1>=0, i=1,…,n,(1)
因此,满足上面公式且使||W||2最小的分类面就是最优分类面。过两类样本中离分类面最近的点且平行于最优分类面的超平面H1,H2上的训练样本,就是使上式等号成立的样本称作支持向量。
定义:
支持向量机(Support Vector Machine,SVM),是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中。在地球物理反演当中解决非线性反演也有显著成效,例如(支持向量机在预测地下水涌水量问题等)。已知该算法被应用的主要有:石油测井中利用测井资料预测地层孔隙度及粘粒含量、天气预报工作等。
支持向量机方法建立在统计学习理论的VC维理论和结构风险最小原理基础上,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折中,以求获得最好的推广能力(或称泛化能力) 。
所谓VC维是对函数类的一种度量,可以简单的理解为问题的复杂程度,VC维越高,一个问题就越复杂。正是因为SVM关注的是VC维,后面我们可以看到,SVM解决问题的时候,和样本的维数是无关的(甚至样本是上万维的都可以,这使得SVM很适合用来解决文本分类的问题,当然,有这样的能力也因为引入了核函数)。
我们通常希望分类的过程是一个机器学习的过程。这些数据点是n维实空间中的点。我们希望能够把这些点通过一个n-1维的超平面分开。通常这个被称为线性分类器。有很多分类器都符合这个要求。但是我们还希望找到分类最佳的平面,即使得属于两个不同类的数据点间隔最大的那个面,该面亦称为最大间隔超平面。如果我们能够找到这个面,那么这个分类器就称为最大间隔分类器。
支持向量机属于一般化线性分类器。他们也可以认为是提克洛夫规则化(Tikhonov Regularization)方法的一个特例。这种分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区。因此支持向量机也被称为最大边缘区分类器。
支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。建立方向合适的分隔超平面使两个与之平行的超平面间的距离最大化。其假定为,平行超平面间的距离或差距越大,分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。 支持向量机特点
支持向量机中的一大亮点:在传统的最优化问题中提出了对偶理论,主要有最大最小
对偶及拉格朗日对偶。
(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射;
(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心;
(3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。
(4)SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题。
(5)SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。
(6)少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:
①增、删非支持向量样本对模型没有影响;
②支持向量样本集具有一定的鲁棒性;
③有些成功的应用中,SVM 方法对核的选取不敏感
支持向量机不足
(1) SVM算法对大规模训练样本难以实施
由于SVM是借助二次规划来求解支持向量,而求解二次规划将涉及m阶矩阵的计算(m为样本的个数),当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法
(2) 用SVM解决多分类问题存在困难
经典的支持向量机算法只给出了二类分类的算法,而在数据挖掘的实际应用中,一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树;再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点,结合其他算法的优势,解决多类问题的分类精度。如:与粗集理论结合,形成一种优势互补的多类问题的组合分类器。
支持向量机的优势:
可用于分类、回归和异常检验 可以发现全局最优解 可以用参数来控制过度拟合问题
SVM的关键在于核函数。低维空间向量集通常难于划分,于是将它们映射到高维空间。但这个办法带来的困难就是计算复杂度的增加,而核函数正好巧妙地解决了这个问题。只要选用适当的核函数,就可以得到高维空间的分类函数。采用不同的核函数将导致不同的SVM算法。
支持向量机分类器
理解SVM有四个关键名词:分离超平面、最大边缘超平面、软边缘、核函数。
分离超平面(separating hyperplane):处理分类问题的时候需要一个决策边界,好
象楚河汉界一样,在界这边我们判别A,在界那边我们判别B。这种决策边界将两类事物相分离,而线性的决策边界就是分离超平面。
最大边缘超平面(Maximal Margin Hyperplane):分离超平面可以有很多个,怎么找
最好的那个呢,SVM的作法是找一个“最中间”的。换句话说,就是这个平面要尽量和两边保持距离,以留足余量,减小泛化误差,保证稳健性。或者用中国人的话讲叫做“执中”。以江河为国界的时候,就是以航道中心线为界,这个就是最大边缘超平面的体现。在数学上找到这个最大边缘超平面的方法是一个二次规划问题。
软边缘(Soft Margin):但世界上没这么美的事,很多情况下都是“你中有我,我中有你”的混杂状态。不大可能用一个平面完美的分离两个类别。在线性不可分情况下就要考虑软边缘了。软边缘可以破例允许个别样本跑到其它类别的地盘上去。但要使用参数来权衡两端,一个是要保持最大边缘的分离,另一个要使这种破例不能太离谱。这种参数就是对错误分类的惩罚程度C。
核函数(Kernel Function),为了解决完美分离的问题,SVM还提出一种思路,就是将
原始数据映射到高维空间中去,直觉上可以感觉高维空间中的数据变的稀疏,有利于“分清敌我”。那么映射的方法就是使用“核函数”。如果这种“核技术”选择得当,高维空间中的数据就变得容易线性分离了。而且可以证明,总是存在一种核函数能将数据集映射成可分离的高维数据。看到这里各位不要过于兴奋,映射到高维空间中并非是有百利而无一害的。维数过高的害处就是会出现过度拟合。 所以选择合适的核函数以及软边缘参数C就是训练SVM的重要因素。一般来讲,核函数越复杂,模型越偏向于拟合过度。在参数C方面,它可以看作是LASSO算法中的lambda的倒数,C越大模型越偏向于拟合过度,反之则拟合不足。实际问题中怎么选呢?用人类最古老的办法,试错。
常用的核函数有如下种类:
Linear:使用它的话就成为线性向量机,效果基本等价于Logistic回归。但它可以处理变量极多的情况,例如文本挖掘。 polynomial:多项式核函数,适用于图像处理问题。 Radial basis,高斯核函数,最流行易用的选择。参数包括了sigma,其值若设置过小,会有过度拟合出现。 sigmoid:反曲核函数,多用于神经网络的激活函数。
关键得在R里面出手。R语言中可以用e1071包中的svm函数建模,而另一个kernlab包中则包括了更多的核方法函数,本例用其中的ksvm函数,来说明参数C的作用和核函数的选择。我们先人为构造一个线性不可分的数据,先用线性核函数来建模,其参数C取值为1。然后我们用图形来观察建模结果,下图是根据线性SVM得到各样本的判别值等高线图(判别值decision value相当于Logistic回归中的X,X取0时为决策边
界)。可以清楚的看到决策边界为线性,中间的决策边缘显示为白色区域,有相当多的样本落入此区域。
为了更好的拟合,加大了C的取值,可以预料到,当加大惩罚参数后决策边缘缩窄,也使训练误差减少,但仍有个别样本未被正确的分类。 最后我们换用高斯核函数,这样得到的非线性决策边界。所有的样本都得到了正确的分类。
1.1、分类标准的起源:Logistic
理解SVM,先清楚:线性分类器。 回归
给定一些数据点,它们分别属于两个不同的类,现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点,用y表示类别(y可以取1或者-1,分别代表两个不同的类),一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面(hyper plane),这个超平面的方程可以表示为( wT中的T代表转置):
这个1或-1的分类标准起源于logistic回归。
Logistic回归目的是从特征学习出一个0/1分类模型,而这个模型是将特性的线性组合作为自变量,由于自变量的取值范围是负无穷到正无穷。因此,使用logistic函数(或称作sigmoid函数)将自变量映射到(0,1)上,映射后的值被认为是属于y=1的概率。
假设函数
其中x是n维特征向量,函数g就是logistic函数。
而的图像是
可以看到,将无穷映射到了(0,1)。
而假设函数就是特征属于y=1的概率。
从而,当我们要判别一个新来的特征属于哪个类时,只需求
就是y=1的类,反之属于y=0类。
此外,只和有关,
。再者,当>0,那么时,,而g(z)只是用来映射,真实的类=1,反之=0。如果我们只从
,而是y=0的特征出。即可,若大于0.5别决定权还是在于发,希望模型达到的目标就是让训练数据中y=1的特征
Logistic回归就是要学习得到,使得正例的特征远大于0,负例的特征远小于0,而且要在全部训练实例上达到这个目标。
形式化的表示:
接下来,尝试把logistic回归做个变形。首先,将使用的结果标签y = 0和y = 1替换为y = -1,y = 1,然后将
将后面的替换为()中的(即替换为b,最后)。如此,则有了
。也就是说除了y由y=0变为y=-1外,线性分类函数跟logistic回归的形式
化表示没区别。
进一步,可以将假设函数
y=-1和y=1上。映射关系如下: 中的g(z)做一个简化,将其简单映射到
1.2、线性分类的一个例子
现在有一个二维平面,平面上有两种不同的数据,分别用圈和叉表示。由于这些数据是线性可分的,所以可以用一条直线将这两类数据分开,这条直线就相当于一个超平面,超平面一边的数据点所对应的y全是 -1 ,另一边所对应的y全是1。
这个超平面可以用分类函数表示,当f(x) 等于0的时候,x便是位于超平面上的点,而f(x)大于
0的点对应 y=1 的数据点,f(x)小于0的点对应y=-1的点,如下图所示:
注:有的资料
上定义特征到结果的输
出函数
实质是一样
的,因为无论是,与这里定义
的,还是
,不影响最终优
化结果。当我们转化到优化
的时候,为了求解
方便,会把yf(x)令为1,即yf(x)是y(w^x + b),还是y(w^x - b),对我们要优化的式子max1/||w||已无影响。
有些时候,或者说大部分时候数据并不是线性可分的,这个时候满足这样条件的超平面就根本不存在,假设数据都是线性可分的,亦即这样的超平面是存在的。
换言之,在进行分类的时候,遇到一个新的数据点x,将x代入f(x) 中,如果f(x)小于0则
将x的类别赋为-1,如果f(x)大于0则将x的类别赋为1。
如何确定这个超平面呢?从直观上而言,这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以,得寻找有着最大间隔的超平面。
1.3、函数间隔Functional margin与几何间隔Geometrical margin
在超平面w*x+b=0确定的情况下,|w*x+b|能够表示点x到距离超平面的远近,而通过观察w*x+b的符号与类标记y的符号是否一致可判断分类是否正确,所以,可以用(y*(w*x+b))的正负性来判定或表示分类的正确性。于此,我们便引出了函数间隔(functional margin)的概念。
定义函数间隔(用表示)为:
而超平面(w,b)关于T中所有样本点(xi,yi)的函数间隔最小值(其中,x是特征,y是结果标签,i表示第i个样本),便为超平面(w, b)关于训练数据集T的函数间隔: = mini (i=1,...n)
但这样定义的函数间隔有问题,即如果成比例的改变w和b(如将它们改成2w和2b),则函数间隔的值f(x)却变成了原来的2倍(虽然此时超平面没有改变),所以只有函数间隔还远远不够。
事实上,我们可以对法向量w加些约束条件,从而引出真正定义点到超平面的距离--几何间隔(geometrical margin)的概念。
假定对于一个点 x ,令其垂直投影到超平面上的对应点为 x0 ,w 是垂直于超平面的一个向量,为样本x到分类间隔的距离,如下图所示:
有,其中||w||表示的是范数。
又由于 x0 是超平面上的点,满足 f(x0)=0 ,代入超平面的方程
算出: 即可
γ
其中,||w||为w的二阶泛数)为了得到
何间隔(用表示)的定义: 的绝对值,令乘上对应的类别 y,即可得出几
从上述函数间隔和几何间隔的定义可以看出:几何间隔就是函数间隔除以||w||,而且函数间隔y*(wx+b) = y*f(x)实际上就是|f(x)|,只是人为定义的一个间隔度量,而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。
1.4、最大间隔分类器Maximum Margin Classifier的定义
对一个数据点进行分类,当超平面离数据点的“间隔”越大,分类的确信度(confidence)也越大。所以,为了使得分类的确信度尽量高,需要让所选择的超平面能够最大化这个“间隔”值。这个间隔如下图中的gap / 2所示。
通过由前面的分析可知:函数间隔不适合用来最大化间隔值,因为在超平面固定以后,可以等比例地缩放w的长度和b的值,这样可以使得
函数间隔的值任意大,亦即,可以在超平面保持不变的情况下被取得任意大。但几何间隔因为除上了
使得在缩放w和b的时候几何间隔的值是不会改变的,它只随着超平面的变动而变动,因此,这是更加合适的一个间隔。所以,这里要找的最大间隔分类超平面中的“间隔”指的是几何间隔。
于是最大间隔分类器(maximum margin classifier)的目标函数可以定义为:
同时需满足一些条件,根据间隔的定义,有
其中,s.t.,即subject to的意思,它导出的是约束条件。
回顾下几何间隔的定义
令可知:如果令函数间隔等于1(之所以等于1,是为了方便推导和优化,且这样做对目标函数的优化没有影响,至于为什么,请见本文评论下第42楼回复),则有 = 1 / ||w||且,从而上述目标函数转化成了
这个目标函数便是在相应的约束条件
化这个1/||w||值,而1/||w||便是几何间隔。 下,最大
如下图所示,中间的实线便是寻找到的最优超平面(Optimal Hyper Plane),其到两条虚线的距离相等,这个距离便是几何间隔,两条虚线之间的距离等于2,而虚线上的点则是支持向量。由于这些支持向量刚好在边界上,所以它们满足(还记得我们把 functional margin 定为 1 了吗?上节中:处于方便推导和优化的目的,我们可以令=1),而对于所有不是支持向量的点,则显然有。
2.2、核函数Kernel
2.2.1、特征空间的隐式映射:核函数
咱们首先给出核函数的来头:在上文中,我们已经了解到了SVM处理线性可分的情况,而对于非线性的情况,SVM 的处理方法是选择一个核函数 κ(⋅,⋅) ,通过将数据映射到高维空间,来解决在原始空间中线性不可分的问题。
此外,因为训练样例一般是不会独立出现的,它们总是以成对样例的内积形式出现,而用对偶形式表示学习器的优势在为在该表示中可调参数的个数不依赖输入属性的个数,通过使用恰当的核函数来替代内积,可以隐式得将非线性的训练数据映射到高维空间,而不增加可调参数的个数(当然,前提是核函数能够计算对应着两个输入特征向量的内积)。
在线性不可分的情况下,支持向量机首先在低维空间中完成计算,然后通过核函数将输
入空间映射到高维特征空间,最终在高维特征空间中构造出最优分离超平面,从而把平面上本身不好分的非线性数据分开。如图7-7所示,一堆数据在二维空间无法划分,从而映射到三维空间里划分:
而在我们遇到核函数之前,如果用原始的方法,那么在用线性学习器学习一个非线性关系,需要选择一个非线性特征集,并且将数据写成新的表达形式,这等价于应用一个固定的非线性映射,将数据映射到特征空间,在特征空间中使用线性学习器,因此,考虑的假设集是这种类型的函数:
这里
两步:
1. 首先使用一个非线性映射将数据变换到一个特征空间F,
2. 然后在特征空间使用线性学习器分类。
而由于对偶形式就是线性学习器的一个重要性质,这意味着假设可以表达为训练点的线性组合,因此决策规则可以用测试点和训练点的内积来表示: ϕ:X->F是从输入空间到某个特征空间的映射,这意味着建立非线性学习器分为
如果有一种方式可以在特征空间中直接计算内积〈φ
(xi · φ(x)〉,就像在原始输入点的函数中一样,就有可能将两个步骤融合到一起建立一个非线性的学习器,这样直接计算法的方法称为核函数方法:
核是一个函数K,对所有x,z(-X,满足
是从X到内积特征空间F的映射。 ,这里
φ
2.2.2、核函数:如何处理非线性数据
来看个核函数的例子。如下图所示的两类数据,分别分布为两个圆圈的形状,这样的数据本身就是线性不可分的,此时咱们该如何把这两类数据分开呢(下文将会有一个相应的三维空间图)?
事实上,上图所述的这个数据集,是用两个半径不同的圆圈加上了少量的噪音生成得到的,所以,一个理想的分界应该是一个“圆圈”而不是一条线(超平面)。如果用 X1 和 X2 来表示这个二维平面的两个坐标的话,我们知道一条二次曲线(圆圈是二次曲线的一种特殊情况)的方程可以写作这样的形式:
注意上面的形式,如果我们构造另外一个五维的空间,其中五个坐标的值分别为 Z1=X1, Z2=X21, Z3=X2, Z4=X22, Z5=X1X2,那么显然,上面的方程在新的坐标系下可以写作:
关于新的坐标 Z ,这正是一个 hyper plane 的方程!也就是说,如果我们做一个映射 ϕ:R2→R5 ,将 X 按照上面的规则映射为 Z ,那么在新的空间中原来的数据将变成线性可分的,从而使用之前我们推导的线性分类算法就可以进行处理了。这正是 Kernel 方法处理非线性问题的基本思想。
再进一步描述 Kernel 的细节之前,不妨再来看看这个例子映射过后的直观例子。
当然,你我可能无法把 5 维空间画出来,不过由于我这里生成数据的时候就是用了特殊的情形,具体来说,我这里的超平面实际的方程是这个样子(圆心在
X2 轴上的一个正圆):
因此我只需要把它映射到 Z1=X21, Z2=X22, Z3=X2 这样一个三维空间中即可,下图即是映射之后的结果,将坐标轴经过适当的旋转,就可以很明显地看出,数据是可以通过一个平面来分开的
核函数相当于把原来的分类函数:
映射成:
而其中的可以通过求解如下 dual 问题而得到的:
这样一来问题就解决了吗?似乎是的:拿到非线性数据,就找一个映射 ,然后一股脑把原来的数据映射到新空间中,再做线性 SVM 即可。不过事实上没有这么简单!其实刚才的方法稍想一下就会发现有问题:在最初的例子里,我们对一个二维空间做映射,选择的新空间是原始空间的所有一阶和二阶的组合,得到了五个维度;如果原始空间是三维,那么我们会得到 19 维的新空间,这个数目是呈爆炸性增长的,这给 的计算带来了非常大的困难,而且如果遇到无穷维的情况,就根本无从计算了。所以就需要 Kernel 出马了。 不妨还是从最开始的简单例子出发,设两个向量
,而和即是到前面说的五维空间的映射,因此映射过后的内积为:
(公式说明:上面的这两个推导过程中,所说的前面的五维空间的映射,这里说的前面便是文中2.2.1节的所述的映射方式,回顾下之前的映射规则,再看那第一个推导,其实就是计算x1,x2各自的内积,然后相乘相加即可,第二个推导则是直接平方,去掉括号,也很容易推出来)
另外,我们又注意到:
二者有很多相似的地方,实际上,我们只要把某几个维度线性缩放一下,然后再加上一个常数维度,具体来说,上面这个式子的计算结果实际上和映射
之后的内积的结果是相等的,那么区别在于什么地方呢?
1. 一个是映射到高维空间中,然后再根据内积的公式进行计算;
2. 而另一个则直接在原来的低维空间中进行计算,而不需要显式地写出映射后的结果。 (公式说明:上面之中,最后的两个式子,第一个算式,是带内积的完全平方式,可以拆开,然后,通过凑一个得到,第二个算式,也是根据第一个算式凑出来的)
回忆刚才提到的映射的维度爆炸,在前一种方法已经无法计算的情况下,后一种方法却依旧能从容处理,甚至是无穷维度的情况也没有问题。
我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 (Kernel Function) ,例如,在刚才的例子中,我们的核函数为:
核函数能简化映射空间中的内积运算——刚好“碰巧”的是,在我们的 SVM 里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们上面写出来的式子,现在我们的分类函数为:
其中 由如下 dual 问题计算而得:
这样一来计算的问题就算解决了,避开了直接在高维空间中进行计算,而结果却是等价的!当然,因为我们这里的例子非常简单,所以我可以手工构造出对应于
来,如果对于任意一个映射,想要构造出对应的核函数就很困难了。
2.2.4、核函数的本质
1. 实际中,我们会经常遇到线性不可分的样例,此时,我们的常用做法是把样例特征
映射到高维空间中去(如上文2.2节最开始的那幅图所示,映射到高维空间后,相关特征便被分开了,也就达到了分类的目的);
2. 但进一步,如果凡是遇到线性不可分的样例,一律映射到高维空间,那么这个维度
大小是会高到可怕的(如上文中19维乃至无穷维的例子)。那咋办呢? 的核函数出
3. 此时,核函数就隆重登场了,核函数的价值在于它虽然也是讲特征进行从低维到高
维的转换,但核函数绝就绝在它事先在低维上进行计算,而将实质上的分类效果表现在了高维上,也就如上文所说的避免了直接在高维空间中的复杂计算。
最后引用这里的一个例子举例说明下核函数解决非线性问题的直观效果。
假设现在你是一个农场主,圈养了一批羊群,但为预防狼群袭击羊群,你需要搭建一个篱笆来把羊群围起来。但是篱笆应该建在哪里呢?你很可能需要依据牛群和狼群的位置建立一个“分类器”,比较下图这几种不同的分类器,我们可以看到SVM完成了一个很完美的解决方案。
这个例子从侧面简单说明了SVM使用非线性分类器的优势,而逻辑模式以及决策树模式都是使用了直线方法。
第三层、证明SVM
3.1、线性学习器
3.1.1、感知机算法
这个感知机算法是1956年提出的,年代久远,依然影响着当今,当然,可以肯定的是,此算法亦非最优,后续会有更详尽阐述。不过,有一点,你必须清楚,这个算法是为了干嘛的:不断的训练试错以期寻找一个合适的超平面(是的,就这么简单)。
下面,举个例子。如下图所示,凭我们的直觉可以看出,图中的红线是最优超平面,蓝线则是根据感知机算法在不断的训练中,最终,若蓝线能通过不断的训练移动到红线位置上,则代表训练成功。
既然需要通过不断的训练以让蓝线最终成为最优分类超平面,那么,到底需要训练多少次呢?Novikoff定理告诉我们当间隔是正的时候感知机算法会在有限次数的迭代中收敛,也就是说Novikoff定理证明了感知机算法的收敛性,即能得到一个界,不至于无穷循环下去。
Novikoff定理:如果分类超平面存在,
仅需在序列
错误次数下就可以找到分类超平面,算法停止。
上迭代几次,
在界为的
这里,为扩充间隔。根据误分次数公式可知, 迭代次数与对应于扩充(包括偏置)权重的训练集的间隔有关。
顺便再解释下这个所谓的扩充间隔,即为样本到分类间隔的距离,即从引出的最大分类间隔。OK,还记得上文第1.3.2节开头的内容么?如下:“
在给出几何间隔的定义之前,咱们首先来看下,如上图所示,对于一个点 x ,令其垂直投影到超平面上的对应的为 x0 ,由于 w 是垂直于超平面的一个向量,为样本x到分类间隔的距离,我们有 ”
然后后续怎么推导出最大分类间隔请回到本文第一、二部分,此处不重复板书。
同时有一点得注意:感知机算法虽然可以通过简单迭代对线性可分数据生成正确分类的超平面,但不是最优效果,那怎样才能得到最优效果呢,就是上文中第一部分所讲的寻找最大分类间隔超平面。
3.5、SMO算法
在上文中,我们提到了求解对偶问题的序列最小最优化SMO算法,但并未提到其具体解法。首先看下最后悬而未决的问题:
等价于求解:
针对上述问题的解法:SMO算法,它很快便成为最快的二次规划优化算法,特别是在针对线性SVM和数据稀疏时性能更优。
接下来,咱们便参考John C. PlattSMO
的解法是怎样的。
3.5.2、SMO算法的步骤
SMO的主要步骤:
1. 第一步选取一对和,选取方法使用启发式方法; 2. 第二步,固定除和之外的其他参数,确定W极值条件下的
,由表示。
假定在某一次迭代中,需要更新
模的二次规划问题写为: ,对应的拉格朗日乘子,,那么这个小规
那么在每次迭代中,如何更新乘子呢?
知道了如何更新乘子,那么选取哪些乘子进行更新呢?具体选择方法有以下两个步骤:
1. 步骤1:先“扫描”所有乘子,把第一个违反KKT条件的作为更新对象,令为a2;
2. 步骤2:在所有不违反KKT条件的乘子中,选择使|E1 −E2|最大的a1进行更新,
使得能最大限度增大目标函数的值(类似于梯度下降。此外,而
,求出来的E代表函数ui对输入xi的预测值与真实输出类标记
yi之差)。 最后,每次更新完两个乘子的优化后,都需要再重新计算b,及对应的Ei值。
SMO算法的基本思想是将Vapnik在1982年提出的Chunking方法推到极致,SMO算法每次迭代只选出两个分量ai和aj进行调整,其它分量则保持固定不变,在得到解ai和aj之后,再用ai和aj改进其它分量。与通常的分解算法比较,尽管它可能需要更多的迭代次数,但每次迭代的计算量比较小,所以该算法表现出整理的快速收敛性,且不需要存储核矩阵,也没有矩阵运算。