模式识别-支持向量机.docx

该【模式识别-支持向量机 】是由【飞行的笑笑】上传分享，文档一共【24】页，该文档可以免费在线阅读，需要了解更多关于【模式识别-支持向量机 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
计算机模式鉴识报告
支持向量机
一、

SVM的介绍
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
支持向量机(SupportVectorMachine,SVM)是CorinnaCortes
nik[8]等于1995年第一提出的,它在解决小样本、非线性及高维模式鉴识

和

Vap
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
中表现出好多特有的优势,并能够实行应用到函数拟合等其他机器学习问
题中。
支持向量机方法是建立在统计学习理论的VC维理论和构造风险最小
原理基础上的,依据有限的样本信息在模型的复杂性(即对特定训练样本
的学习精度)和学习能力(即无错误地鉴识任意样本的能力)之间追求最
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
佳折衷,以期获取最好的实行能力
。
我们平时希望分类的过程是一个机器学习的过程。这些数据点是
n维
实空间中的点。我们希望能够把这些点经过一个
n-1
维的超平面分开。通
常这个被称为线性分类器。有好多分类器都吻合这个要求。但是我们还希
望找到分类最正确的平面,即使得属于两个不相同类的数据点间隔最大的那个
面,该面亦称为最大间隔超平面。若是我们能够找到这个面,那么这个分
类器就称为最大间隔分类器。
支持向量机将向量照射到一个更高维的空间里,在这个空间里建立有
一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超
平面。建立方向合适的分开超平面使两个与之平行的超平面间的距离最大
化。其假设为,平行超平面间的距离或差距越大,分类器的总误差越小。
《模式鉴识支持向量机指南》。
所谓支持向量是指那些在间隔区边缘的训练样本点。
这里的“机(ma
chine,机器)”实际上是一个算法。在机器学习领域,常把一些算法看做
是一个机器。
支持向量机(Supportvectormachines
,SVM)与神经网络近似,都是
学习型的体系,但与神经网络不相同的是
SVM使用的是数学方法和优化技术。
支持向量机是由Vapnik领导的AT&TBell实验室研究小组在1963
年提
出的一种新的特别有潜力的分类技术,
SVM是一种基于统计学习理论的模式
鉴识方法,主要应用于模式鉴识领域。由于当时这些研究尚不十分完满,
在解决模式鉴识问题中经常趋于保守,且数学上比较艰涩,这些研究素来
没有获取充分的重视。直到
90年代,统计学习理论
(StatisticalLearni
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
ngTheory,SLT)的实现和由于神经网络等较新兴的机器学习方法的研究碰到一些重要的困难,比方怎样确定网络构造的问题、过学习与欠学习问题、局部极小点问题等,使得SVM迅速发展和完满,在解决小样本、非线性及高维模式鉴识问题中表现出好多特有的优势,并能够实行应用到函数拟合等其他机器学习问题中。今后迅速的发展起来,现在已经在好多领域(生物学,文本和手写鉴识等)都获取了成功的应用。
SVM的要点在于核函数。低维空间向量集平时难于划分,解决的方法是将它们照射到高维空间。但这个方法带来的困难就是计算复杂度的增加,而核函数正好巧妙地解决了这个问题。也就是说,只要采用合适的核函数,
就可以获取高维空间的分类函数。在SVM理论中,采用不相同的核函数将以致不相同的SVM算法。
二、基于统计学习理论的支持向量机算法研究的理论背景
基于数据的机器学习是现代智能技术中的重要方面,研究从察看数据(样本)出发搜寻规律,利用这些规律对未来数据或无法察看的数据进行展望。迄今为止,关于机器学习还没有一种被共同接受的理论框架,关于其实现方法大体能够分为三种:
第一种是经典的(参数)统计估计方法。包括模式鉴识、神经网络等在内,现有机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的,在这种方法中,参数的相关形式是已知的,训练样本用来估计参数的值。这种方法有很大的限制性,第一,它需要已知样本分布形式,这需要开销很大代价,还有,传统统计学研究的是样本数目趋于无量大时的渐近理论,现有学习方法也多是基于此假设。但在本责问题中,样本数经常是有限的,因此一些理论上很优秀的学习方法实质中表现却可能不尽人意。
第二种方法是经验非线性方法,如人工神经网络(ANN)。这种方法利用已知样本建立非线性模型,战胜了传统参数估计方法的困难。但是,这种方法缺乏一种一致的数学理论。
与传统统计学对照,统计学习理论(StatisticalLearningTheory或SLT)是一种特地研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论系统,在这种系统下的统计推理规则不但考虑了对渐近性能的要求,而且追求在现有有限信息的条件下获取最优结果。、七十年代开始致力于此方面研究[1],到九十年代中期,随着其理论的不断发展和成熟,也由于神经网络等学习方法在理论上缺乏实质性进展,统计学习理论开始碰到越来越广泛的重视。
统计学习理论的一其中心看法就是VC维(VCDimension)看法,它是描述函数集或学习机器的复杂性也许说是学习能力(Capacityofthemachine)的一个重要指
标,在此看法基础上发展出了一系列关于统计学习的一致性(Consistency)、收敛速度、实行性能(GeneralizationPerformance)等的重要结论。
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
统计学习理论是建立在一套较牢固的理论基础之上的,为解决有限样本学习问题供应了一个一致的框架。它能将好多现有方法纳入其中,有望帮助解决好多原来难以解决的问题(比方神经网络构造选择问题、局部极小点问题等);同时,
这一理论基础上发展了一种新的通用学习方法──支持向量机(SupportVectorMachine或SVM),已初步表现出好多优于已有方法的性能。一些学者认为,SLT
和SVM正在成为继神经网络研究此后新的研究热点,并将推动机器学习理论和技术有重要的发展。
支持向量机方法是建立在统计学习理论的VC维理论和构造风险最小原理基础上的,依据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度,
Accuracy)和学习能力(即无错误地鉴识任意样本的能力)之间追求最正确折衷,以期获取最好的实行能力(GeneralizatinAbility)。支持向量机方法的几个主要优点有:
它是特地针对有限样本情况的,其目标是获取现有信息下的最优解而不行是是样本数趋于无量大时的最优值;
算法最后将转变为为一个二次型寻优问题,从理论上说,获取的将是全局
最优点,解决了在神经网络方法中无法防备的局部极值问题;
(FeatureSpace),在高维空间中构造线性鉴识函数来实现原空间中的非线性鉴识函数,特别
性质能保证机器有较好的实行能力,同时它巧妙地解决了维数问题,其算法复杂度与样本维数没关;
,计算的复杂性取决于
支持向量的数目,而不是样本空间的维数,这在某种意义上防备了“维数灾祸”。
少许支持向量决定了最后结果,这不仅好够帮助我们抓住要点样本、“剔除”大量冗余样本,而且注定了该方法不仅算法简单,而且拥有较好的“鲁
棒”性。这种“鲁棒”性主要表现在:①增、删非支持向量样本对模型没有影响;②支持向量样本集拥有必然的鲁棒性;③有些成功的应用中,SVM方法对核的采用不敏感。
SVM是一种有牢固理论基础的奇特的小样本学习方法。它基本上不涉及
概率测度及大数定律等,因此不相同于现有的统计方法。从实质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预告样本的“转
导推理”(transductiveinference),大大简化了平时的分类和回归等问题。
在SVM方法中,只要定义不相同的内积函数,就可以实现多项式逼近、贝叶斯分类器、径向基函数(RadialBasicFunction或RBF)方法、多层感知器网络等好多现有学习算法。
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
统计学习理论从七十年代末出生,到九十年代从前都处在初级研究和理论准备阶段,近几年才逐渐获取重视,其自己也趋向完满,并产生了支持向量机这一
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
将这种理论付诸实现的有效的机器学习方法。当前,
SVM算法在模式鉴识、回
归估计、概率密度函数估计等方面都有应用。比方,在模式鉴识方面,关于手写
数字鉴识、语音鉴识、人脸图像鉴识、文章分类等问题,
SVM算法在精度上已
经高出传统的学习算法或与之伯仲之间。
当前,国际上对这一理论的谈论和进一步研究逐渐广泛,而我国国内还没有在
此领域睁开研究,因此我们需要及时学习掌握相关理论,睁开有效的研究工作,
使我们在这一有重视要意义的领域中能够赶忙追上。
由于SLT理论
和SVM方法尚处在发展阶段,好多方面尚不完满,比方:好多理论当前还只有
理论上的意义,尚不能够在实质算法中实现;而相关
SVM算法某些理论讲解也并
非圆满(在[2]中就曾提到构造风险最小原理其实不能够严格证明
SVM为什
么有好的实行能力);其他,关于一个实质的学习机器的
VC维的解析尚没有通用
的方法;SVM方法中怎样依照详尽问题选择合适的内积函数也没有理论依照。
因此,在这方面我们可做的事情是好多的。
三、方法介绍
SVM是从线性可分情况下的最优分类面发展而来的,基本思想可用图1的
两维情况说明。图中,实心点和空心点代表两类样本,H为分类线,H1、H2分别
为过各样中离分类线近来的样本且平行于分类线的直线,它们之间的距离叫做分
类间隔(margin)。所谓最优分类线就是要求分类线不仅好将两类正确分开(训
练错误率为0),而且使分类间隔最大。分类线方程为xwb0,我们能够对
它进行归一化,使得对线性可分的样本集(xi,yi),i1,...,n,xRd,y{1,1},
满足
yi[(wxi)b]10,i1,,n
(1)
此时分类间隔等于2/||w||,使间隔最大等价于使||w||2最小。满足条件(1)且使
1
2
上的训练样本点就称作支持向量。
w最小的分类面就叫做最优分类面,H1、H2
2
利用Lagrange优化方法能够把上述最优分类面问题转变为其对偶问题
[2],
即:在拘束条件
n
yii0,
(2a)
i1
和
i0
i=1,n
(2b)
下对i求解以下函数的最大值:
Q( )
n
1n
i
ijyiyj(xixj)
i
1
2i,j1
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
(3)
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
i为原问题中与每个拘束条件(1)对应的Lagrange乘子。这是一个不等式拘束下二次函数寻优的问题,存在唯一解。简单证明,解中将只有一部分(平时是少部分)i不为零,对应的样本就是支持向量。解上述问题后获取的最优分类函数
是
n
f(x)sgn{(wx)b}sgn
i*yi(xix)b*,
(4)
i
1
式中的求和实质上只对支持向量进行。b*是分类阈值,能够用任一个支持向量(满
足(1)中的等号)求得,或经过两类中任意一对支持向量取中值求得。
对非线性问题,能够经过非线性变换转变为某个高维空间中的线性问题,在变换空间求最优分类面。这种变换可能比较复杂,因此这种思路在一般情况下不易实现。但是注意到,在上面的对偶问题中,不论是寻优目标函数(3)还是分类函数(4)都只涉及训练样本之间的
内积运算(xi
xj
)。设有非线性照射Φ:
最优分类面
图1
Rd将输入空间的样本照射到高维
(可能是无量维)的特点空间中。当在特点空间H中构造最优超平面时,训练算法仅使用空间中的点积,即Φ(xi).Φ(xj),而没有单独的Φ(xi)出现。因此,若是能
够找到一个函数K使得K(xi,xj)=Φ(xi).Φ(xj),这样,在高维空间实质上只要进行
内积运算,而这种内积运算是能够用原空间中的函数实现的,我们甚至没有必要知道变换Φ的形式。依照泛函的相关理论,只要一种核函数K(xi,xj)满足Mercer条件,它就对应某一变换空间中的内积。
因此,在最优分类面中采用合适的内积函数K(xi,xj)就可以实现某一非线性
变换后的线性分类,而计算复杂度却没有增加,此时目标函数(3)变为:
Q( )
n
1n
(5)
i
ijyiyjK(xi,xj),
i
1
2i,j1
而相应的分类函数也变为
n
f(x)sgn(
i*yiK(xi,x)b*),
(6)
i1
这就是支持向量机。
这一特点供应认识决算法可能以致的“维数灾祸”问题的方法:在构造鉴识
函数时,不是对输入空间的样本作非线性变换,尔后在特点空间中求解;而是先在输入空间比较向量(比方求点积或是某种距离),对结果再作非线性变换[9]。这
样,大的工作量将在输入空间而不是在高维特点空间中完成。SVM分类函数形式上近似于一个神经网络,输出是s中间节点的线性组合,每其中间节点对应一
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
个支持向量,如图2所示。
函数K称为点积的卷积核函数,依照公式,它能够看作在样本之间定义的一种距离。
y
输出(决策规则):
s
ysgn(iyiK(xi,x)b)
i1
1y1
2y2sys
权值
iyi
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
K(x1,x)
K(x2,x)
x1x2

K(xs,x)
基于s个支持向量x1,x2,...,xs的非
线性变换(内积
xd输入向量x(x1,x2,...,xd)
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
图2支持向量机表示图
显然,上面的方法在保证训练样本所有被正确分类,即经验风险Remp为0
的前提下,经过最大化分类间隔来获取最好的实行性能。若是希望在经验风险和实行性能之间求得某种均衡,能够经过引入正的废弛因子ξi来赞同错分样本的存在。这时,拘束(1)变为
yi[(wxi)
b]
1
i0,i1,,n
(7)
21
2
n
而在目标——最小化
w
——中加入处分项C
i1i,这样,Wolf对偶问题可
以写成:
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
n
1
Maximize:
Q( )
i
i1
2

n
ijyiyjK(xi,xj)
i,j1
(8)
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
n
.
yii
0
(9a)
i
1
0
i
C
i=1,n
(9b)
这就是SVM方法的最一般的表述。为了方便后边的陈述,这里我们对对偶问题
的最优解做一些推导。
定义
(
)
iyi
(xi)
(10)
i
Fi
( )
(xi)
yi
jyjK(xi,xj)yi
(11)
j
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
对偶问题的Lagrange函数能够写成:
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
L
1
i(iC)
iyi
(12)
( )( )
ii
2
i
i
i
i
KKT条件为
L
)yi
i0
(13a)
(Fi
i
i
ii0
且
i
0
(13b)
i(i
C)=0
i
(13c)
由此,我们能够推导出以下关系式:
若i=0
则i0
i=0
(Fi
i)yi
0
(14a)
若0<i<C
则i=0
i=0
(Fii)yi=0
(14b)
若i=C
则i=0
i0
(Fi
i)yi
0
(14c)
由于KKT条件是最优解应满足的充要条件(6),因此当前提出的一些算法几乎都是以可否违反KKT条件作为迭代策略的准则。

由于SVM方法较好的理论基础和它在一些领域的应用中表现出来的优秀的
实行性能,近来几年来,好多关于SVM方法的研究,包括算法自己的改进和算法的实质应用,都陆续提了出来。尽管SVM算法的性能在好多本责问题的应用中获取了考据,但是该算法在计算上存在着一些问题,包括训练算法速度慢、算法复杂而难以实现以及检测阶段运算量大等等。
传统的利用标准二次型优化技术解决对偶问题的方法可能是训练算法慢的
主要原因:第一,SVM方法需要计算和储藏核函数矩阵,当样本点数目较大时,
需要很大的内存,比方,当样本点数目高出4000时,储藏核函数矩阵需要多达
兆内存;其次,SVM在二次型寻优过程中要进行大量的矩阵运算,多数情况下,寻优算法是占用算法时间的主要部分。
SVM方法的训练运算速度是限制它的应用的主要方面,近来几年来人们针对方法自己的特点提出了好多算法来解决对偶寻优问题。大多数算法的一个共同的思想就是循环迭代:将原问题分解成为若干子问题,依照某种迭代策略,经过屡次求解子问题,最后使结果收敛到原问题的最优解。依照子问题的划分和迭代策略的不相同,又能够大体分为两类。
第一类是所谓的“块算法”(chunkingalgorithm)。“块算法”基于的是这样一个事实,即去掉Lagrange乘子等于零的训练样本不会影响原问题的解。关于给定的训练样本集,若是其中的支持向量是已知的,寻优算法就可以消除非支持向量,只要对支持向量计算权值(即Lagrange乘子)即可。实质上支持向量是未
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
知的,因此“块算法”的目标就是经过某种迭代方式逐渐消除非支持向量。详尽的作法是,选择一部分样本构成工作样本集进行训练,剔除其中的非支持向量,
并用训练结果对节余样本进行检验,将不吻合训练结果(一般是指违反KKT条件)的样本(或其中的一部分)与本次结果的支持向量合并成为一个新的工作样本集,尔后重新训练。这样重复下去直到获取最优结果。
当支持向量的数目远远小于训练样本数目时,“块算法”显然能够大大提高运算速度。但是,若是支持向量的数目自己就比很多,随着算法迭代次数的增加,工作样本集也会越来越大,算法仍旧会变得十分复杂。因此第二类方法把问题分解成为固定样本数的子问题:工作样本集的大小固定在算法速度能够容忍的限度内,迭代过程中可是将节余样本中部分“情况最糟的样本”与工作样本集中的样
本进行等量交换,即使支持向量的个数高出工作样本集的大小,也不改变工作样本集的规模,而只对支持向量中的一部分进行优化。
固定工作样本集的方法和块算法的主要差异在于:块算法的目标函数中仅包
含当前工作样本集中的样本,而固定工作样本集方法诚然优化变量仅包括工作样
本,其目标函数却包括整个训练样本集,即工作样本集之外的样本的Lagrange
乘子固定为前一次迭代的结果,而不是像块算法中那样设为0。而且固定工作样
本集方法还涉及到一个确定换出样本的问题(由于换出的样本可能是支持向量)。
这样,这一类算法的要点就在于找到一种合适的迭代策略使得算法最后能收敛并
且较快地收敛到最优结果。
。在书中,Edgar
Osunal等人介绍了一种详尽的算法并对人脸鉴识问题进行了实验。将样本集分为
两个会集B和N,会集B作为子问题工作样本集进行SVM训练,会集N中所有
样本的Lagrange乘子均置为零。显然,若是把会集B中对应Lagrange乘子为零
的样本i(即i=0,iB)与会集N中的样本j(即i=0,jN)交换,不会改变
子问题与原问题的可行性(即仍旧满足拘束条件);而且,当且仅当样本满足条
件(Fii
)y
i
(
)时,代替后的子问题的最优解不变。于是能够依照以下步
0
14a
骤迭代求解:,构造子问题;
i,
i
B
及,并置
b
j
=0,j
N;,jN找出其中不满足条件(F
i
)y
i
0(14a)的样本
j
i
j,与B中满足i
=0的样本i交换,构成新的子问题。证了然这种迭代算法的收
敛性,并给出了两阶多项式分类器在人脸鉴识问题中的应用结果。
需要说明的是,文中没有说明会集
B的大小可否改变。作者希望的是支持向
量的数目特别少,自然能够固定B的大小,作者的妄图正是这样。但是为此需要选择一个较大的B会集,这样看来,其效率可能还不如块算法。而且若是若是集
合B不足以包括所有的支持向量,该算法没有提出改变B的大小的策略,有可
能得不到结果。
前面提到,固定工作样本集方法的要点在于选择一种合适的换入换出策略。
Joachims指出若是采用某种启示式的迭代策略将会提高算法的收敛速度。近来
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机
(SequentialMinimalOptimization或SMO)算法。
将工作样本集的规模减到最小——两个样本。之因此需要两个样本是由于等式线性拘束的存在使得同时最少有两个Lagrange乘子发生变化。由于只有两个变量,而且应用等式拘束能够将其中一个用另一个表示出来,因此迭代过程中每一步的
子问题的最优解能够直接用解析的方法求出来。这样,算法避开了复杂的数值求解优化问题的过程;其他,Platt还设计了一个两层嵌套循环分别选择进入工作样本集的样本,这种启示式策略大大加快了算法的收敛速度。标准样本集的实验结果证明,SMO表现出在速度方面的优秀性能。
子问题的规模和迭代的次数是一对矛盾,SMO将工作样本集的规模减少到2,一个直接的结果就是迭代次数的增加。因此SMO实际上是将求解子问题的耗费转嫁到迭代上,尔后在迭代上追求迅速算法。但是,SMO迭代策略的思想是能够用到其他迭代算法中的,可见,SMO还有改进的余地。
SMO在实质应用中获取了较好的收效,但它也存在着一些问题。SMO算法每次迭代都要更新值,但是该值有可能是无法确定的(比方不存在0<i<C的样
本,尽管这种情况很少出现),这时SMO采用的方法是确定出的上下界尔后取
平均值;别的,每一次迭代过程中的值仅取决于前一次迭代结果的两个变量的最优值,用这个值判断样本可否满足迭代结果,这即可能存在某些达到最优值的样本殊不满足KKT条件的情况,从而影响了该算法的效率[6]。
解决算法速度问题的另一个路子是采用序列优化的思想。这种方法主要目的
是研究当出现新的单个样本时,它与原有样本集或其子集,或是原有样本集训练
结果的关系,比方,它的加入对原有样本集的支持向量集有什么样的影响,怎样迅速地确定它对新的分类器函数的贡献等等。书中提出了一种用卡尔曼滤波器求解的方法。
四、研究方向
应该说,块算法和固定工作样本集算法是各有优缺点的。毫无疑问,固定工
作样本集的算法解决了占用内存的问题,而且限制了子问题规模的无量增大;但是,从这个意义上来说,固定工作样本集的算法把解标准二次型的寻优问题的时
间转嫁到循环迭代上了,它的迭代次数一般会比“块算法”多。特别是SMO,若是没有一个好的启示式迭代策略,该算法就是一种盲目爬山法。
基于此,我们提出一种算法思想,希望能够综合两类算法的特点。我们仍旧
从最后目标中抽取子问题,借用某种迭代策略使算法收敛,要点的,我们希望一
方面子问题规模不会太小,省得迭代次数太多,另一方面能借鉴SMO的思想,利用二次问题的特点,找到子问题的解析解法,也许是近似解,从而不用对每一个子问题都调用寻优算法。
其他,由于SVM方法的性能与实现上的巨大差异,我们在求解子问题时不用然要获取精确解(解的精确度能够由迭代来保证),甚至还可以够考虑对最后目标
模式辨别-支持向量机
模式辨别-支持向量机
模式辨别-支持向量机