支持向量机及其算法研究概要.docx
- 文档编号:17937077
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:11
- 大小:23.83KB
支持向量机及其算法研究概要.docx
《支持向量机及其算法研究概要.docx》由会员分享,可在线阅读,更多相关《支持向量机及其算法研究概要.docx(11页珍藏版)》请在冰点文库上搜索。
支持向量机及其算法研究概要
支持向量机及其算法研究
SupportVectorMachinesandApplicationResearchOverview
杜晓东3 李岐强DUXiao2dong LIQi2qiang
摘 要
本文首先概要介绍了支持向量机的理论背景,然后结合目前一些主要的SVM训练方法以及它们之间的联系,比较了各种算法的优缺点。
重点阐述了其中最有代表性的序贯最小优化(SMO算法及其多种改进方案。
最后指出了SVM及其算法进一步研究和亟待解决的一些问题。
关键词
支持向量机 统计学习理论 SMO
Abstract ThepaperfirstreviewstheprinciplesofSVM,thenintroducessomeimportantandnewestlearningalgo2
rithm.Allthekindsofalgorithm’advantagesanddisadvantageswereanalyzed.Sequentialminimaloptimization(SMOandit’simprovedversionswasdiscussedindetail.SomeimportantissuesaboutSVMandSMOareproposedtobein2vestigatedandthedirectionsofresearchhavebeenpointedoutalso.
Keywords Supportvectormachine Statisticallearningtheory SMO
3山东大学(南校区控制学院模式识别与系统工程研究所 250061
1 引言
支持向量机(SupportVectorMachine,SVM[122]是近年来在模式识别与机器学习领域中出现的新工具,其核心内容从
1992年才开始提出,1995年Vapnik的《TheNatureofStatisticalLearningTheory》一书的出版,标志着统计学习理论体系已走
向成熟。
SVM以统计学习理论为基础,有效地避免经典学习方法中过学习、维数灾难、局部极小等传统分类存在的问题,在小样本条件下仍然具有良好的范化能力,因此受到了广泛的关注,而且成功应用到了人脸识别[3,4]
文本分类
[5]
基因
分析
[6]
手写体识别
[7]
语音识别
[8]
等多种领域。
SVM的训练问题实质上是一个二次规划(QP问题。
在
最优化理论中已有多种成熟算法来解决此问题,如内点法,共轭梯度法。
但是传统算法在每一步迭代都涉及到核函数矩阵的运算,而核函数矩阵占用的内存随样本数呈平方增长,如计算4000个样本的核函数矩阵就需要128M内存
[2]
。
而且由于迭代误差的积累,也会导致算法精度难以接受。
因此设计适用于针对大量样本的算法就成为近年来SVM研究的重要内容。
支持向量机有效实现算法的出现也极大的推动了这一理论的应用。
该文在简要介绍支持向量机理论背景的基础上,对其算法进行综述,最后指出了进一步研究和亟待解决的问题。
2 支持向量机的理论背景
2.1 统计学习理论
统计学习理论(StatisticalLearningTheory[1]是Vapnik等人在20世纪70年代末提出并在20世纪90年代逐渐完善的一种针对小样本的机器学习理论。
它的核心问题是寻找一种归纳原则以实现最小化风险泛函,从而实现最佳的推广能力。
Vapnik提出了VC维的概念来标志函数集的复杂程度,
并用这个概念给出了与分布无关的学习机器推广能力的界。
这个界由两部分构成:
经验风险和置信范围(以VC维为参数。
学习机器能力过强(VC维很大,虽然能取得小的经验风险,但置信范围会很大;VC维太小又会导致大的经验风险。
一个好的归纳原则必须在二者之间作出权衡。
结构风险最小化原则(SRM正是这样一种归纳原则。
SRM原则定义了在对给定数据的逼近精度和逼近函数的复杂性之间的一种折衷。
2.2 SVM的基本原理
SVM是统计学习理论的重要成果。
假定训练数据(x1,yi,...,(xl,yl,x∈Rn,y∈{+1,21}可以被一个超平面(w・x-b=0没有错误地分开,与两类样本点距离最大(称为边缘最大的分类超平面会获得最佳的推广能力。
最优超平面将由离它最近的少数样本点(称为支持向量决定,而与其它样本无关。
我们用如下形式描述与
信息技术与信息化
信号处理与模式识别
37
样本间隔为Δ的分类超平面:
(w・x-b,‖w‖=1y=1,若(w・x-bΕΔy=21,若(w・x-bΦ-Δ
Vapnik给出了一个关于Δ-间隔分类超平面VC维上界
的定理:
如果向量x属于一个半径为R的球中,那么Δ-间隔分类超平面集合的VC维h有下面的界:
hΦmin
Δ2
n+1
这样,SVM首先保证了一个小的经验风险(在训练样本可分时就是零,并通过选择边缘最大的超平面的方式控制了函数集的VC维,这正是SRM原则所要求的。
3 支持向量机的数学模型
3.1 线性支持向量机
支持向量机的原理是用分类超平面将空间中两类样本点正确分离,并得到最大的分类间隔,我们将SVM的最优化问题中的分类超平面归一化:
令Δ=1,而w和b可以按比例缩放。
离超平面最近的样本(支持向量满足
(w・xi-b=1,若y=1(w・xi-b=-1,若y=21
支持向量到超平面的距离为1Π‖w‖。
原问题就转换成一个有约束非线性规划问题:
Minimize
Φ(w,b=2
‖w‖2
s.t. yi(xi・w+b-1Ε0 i=1,2,…,1
目标函数是严格上凹的二次型,约束函数是下凹的,这是一个严格凸规划。
按照最优化理论中凸二次规划的解法,我们把它转化为Wolfe对偶问题来求解:
构造Lagrange函数:
L(w,α,b=
2
‖w‖2
-∑1
i=1αiyi(xi・w+b+∑1
i=1αi,αiΕ0,i=1,2,…,1(其中αi是Lagrange乘子。
它应满足条件wL(w,α,b=0,9bL(w,
α,b=0,(Kuhn2Tucker条件,即w=∑i
αjyixi和∑i
αjyi=0。
将两式代回Lagrange函数中,消去w和b,经运算得到原最优化问题的Wolfe对偶问题:
Maxmize w(α=∑1
i=1αi
-2∑1i,jαiαjyiyjxi・xj
s.t ∑1
i=1
αiyi=0
αiΕ0
i=1,…,1其解是原最优化问题的整体最优解。
解出αi后利用∑i
αiyixi确定最优超平面,注意到只有支持向量所对应的Lagrange乘
子αi才不是0。
利用Wolfe对偶问题,不但使问题更好处理,而且使样本在新问题中仅以向量点积的形式出现,正是这一重要特点,使支持向量机法能推广到非线性情况。
3.2 非线性支持向量机
把寻找最优超平面最终归结为其Wolfe对偶问题克服了
“维数灾难”:
利用核函数K:
(Rn,Rn
→R使得K(xi,xj就等
于xi,xj在高维特征空间中的映射之点积,用K(xi,xj代替
Wolfe对偶问题中xi和xj的点积即可,计算量将会大大减少。
这样只需在输入空间中计算卷积核函数,而不必知道非线性映射的形式,也不必在高维特征空间中进行计算。
此时输入空间中的判别函数是:
f(x=sign
∑支持向量
yiαi
3
K(xi,xj-b其中:
选择一个小于C的正分量αj
3,并据此计算b3
=yi2∑支持向量
yiαi
3
K(xi,xj如果支持向量很多的话,决策阶段的
计算量也将是较大的。
3.3 线性不可分情况的处理
为了使SVM算法能应用于不可分情况,Cortes和Vapnik在1995年引入了软边缘最优超平面的概念,引入非负变量
ξi
将约束条件放松为:
yi(xi・w+b-1Ε1-ξi,
i=1,2,…,1同时对目标函数引入惩罚项:
Φ(w,ξ=2
‖w‖2
+∑1
i=1ξi求解这个二次规划问题,推导所得的Wolfe对偶问题为:
Maxmize w(α=∑1
i=1αi-2∑1
i,jαiαjyiyjxi・xj
s.t ∑1
i=1
αiyi=0
CΕαiΕ0
i=1,…,1唯一的区别在于对αi加了一个上限限制。
SVM是一种基于SRM原则的以样本间的某种距离作为
划分依据的模式识别方法,它可以在高维空间中构造较低
VC维的函数集,从而获得好的推广能力,它的数学模型中样
本仅以点积形式出现,使得这种方法很容易推广到非线性。
4 SVM的训练算法
注意到支持向量机中凸二次规划这一特殊的最优化问题具有一些良好的特性,如解的稀疏性和最优化问题的凸性,这使得可能构造使用较少存储的快速专用算法。
即将大
规模的原问题分解成若干小规模的子问题,按照某种迭代策略,反复求解子问题,得到原问题的近似解,并能逐渐收敛到
信号处理与模式识别
信息技术与信息化
38
原问题的最优解。
根据子问题的选取和迭代策略的不同,算法大体分为选块算法,分解算法和序列最小优化方法。
4.1 选块算法
由于问题的解只是依赖与支持向量对应的样本点,因此可以事先选择那些支持向量,保留其对应的样本点,并删除其他的样本点,可以建立相同的决策函数。
块算法最早是由Boser等人提出来的,其目标就是通过某种迭代方式逐步排除非支持向量。
其具体做法是首先从训练样本集中选择任意一个子集,利用标准的优化算法求解对偶问题,保留其中的支持向量对应的样本,舍去其它的样本点,然后利用新得到的决策函数检验剩余的训练样本,将其中M(事先确定个违背KKT条件最严重的样本点加到新块中去求解,直到满足某一个停机的准则。
每个二次规划子问题都采用上一个二次规划子问题的结果作为初始值。
显然,这种方法可以减少问题的规模,尤其对于支持向量数目远远小于训练样本数目的情况,但是如果支持向量的数目比较多,算法又需要处理较大的黑塞矩阵,使得算法变得缓慢而失效。
4.2 分解算法
如上所述当支持向量较多时,块算法可能会失效,这时可以利用另一种方法———分解。
Osuna等人最早提出分解算法,其思想是每次只是更新若干个Lagrange乘子,而其它的乘子不变,迭代过程中只是将剩余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换,即使支持向量的个数超过工作样本集的大小也不改变工作样本集的规模,而只对支持向量中的一部分进行优化。
对于分解算法,关键是对样本点换入换出策略的选择上,Joachims提出了一些启发式的迭代策略有助于提高算法的收敛速度,并在软件包SVMlight中具体实现,其基本改进思想是在工作样本集的选择上,SVMlight中是沿着最速下降可行方向d,d仅含q个非零元素,由非零元素对应的q个优化变量构成工作样本集。
已经证明了只要最速下降可行方向d存在,则用相应子集构成的子问题可以进一步优化,而子问题的可行解也是原问题的可行解。
而且该算法采用连续收缩和对常用的参数进行缓存的方法,提高训练速度,适合求解大型支持向量机中优化问题。
张学工提出了CSVM算法,其原理是把每类训练样本集进行聚类分成若干子集,用子集中心组成新训练样本集训练SVM,该算法在提高算法速度的同时,减少了野点对结果的影响。
但是牺牲了解的稀疏性。
对于分解算法,Osuna等证明了一个关键定理:
如果存在不满足Kohn2Tucker条件的样本,那么在把它加入到上一个子问题的集合中后,重新优化这个子问题,则可行点依然满足约束条件,且性能严格地改进。
因此,如果每一步至少加入一个不满足Kohn2Tucker条件的样本,一系列的二次规划子问题可保证最后单调收敛。
这对于下面的序列最小优化算法提供了理论依据。
Lin证明在一定条件下采用可行方向策略的分解算法,其{ακ}的任意聚点是对偶优化问题的全局最优解。
当q=2时,Lin证明无须该条件,还证明在一定条件下,采用可行方向策略的分解算法具有线性收敛速度。
4.3 序列最小优化算法(SequentialMinimalOptimization2SMO
SMO方法可以看作是分解算法的一个特例,它将子问题的规模减少到了最小。
它由微软研究院的JohnC.Platt等人提出并做了多次改进。
根据分解算法的原理,在优化过程中换入换出样本点但保持非工作集的Lagrange乘子不变,SMO方法将工作样本集的规模减到了最小———两个样本,这样就满足分解算法的原理,即满足等式线性约束的存在使得同时至少有两个Lagrange乘数发生变化。
由于子问题的优化只涉及两个变量,而且应用等式约束可以将其中一个变量用另一个变量线性表示出来,所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来,而不用在算法的迭代中求解二次规划问题。
它在每一步迭代只是选择两个变量进行调整,同时固定其他变量,通过求解最优化问题,得到这两个变量的最优值,来更新相应的Lagrange乘子。
虽然我们可以按顺序遍历抽取两个Lagrange乘数的所有组合,也可以使Lagrange乘数优化,但是为了提高算法,还需要一定的原则来设计更快的寻找样本点的方法,根据上述算法原理,Platt设计了一个两层嵌套循环:
外层循环首先遍历非边界样本,因为非边界样本最需要调整,确定哪些样本违反了KKT条件来进行调整,当所有的非边界样本都满足KKT条件后,再在整个样本空间循环一遍,来检验所有的样本是否都满足KKT条件,如果还有不满足的就再次遍历非边界样本,这样循环进行,直到所有的样本点都满足KKT条件。
而内层循环是针对以上违反KKT条件的样本来选择另一个样本与它配对优化,其选择的准则是使选择的一对样本能够对决策函数得到最大的优化步长。
SMO算法速度的瓶颈是在最优条件的判断和在非线性情况下误差的重置方面,本质原因是由于对所有的向量逐个地计算核函数,而核函数本身计算就比较复杂。
所以近来对于SMO算法的改进集中在这两个方面。
其中,Keerhti对Platt的SMO算法进行了改进,在迭代过程中的判优条件和循环策略上做了一定的修改,保证了算法的收敛,并减少了迭代的次数,加快了算法的速度。
并于此后提出了GeneralizedSMO(GSMO算法,利用violatingpair的概念确定工作集,并证信息技术与信息化信号处理与模式识别39
明Πτ>0,以τ2violatingpair为工作集则GSMO算法有限终止。
Ginny在其博士论文中详细阐述了SMO的工作机理,并在算法优化Lagrange乘数方面做出改进,尤其给出了详细的软件实现过程。
对于算法结构,文献[5]做了有益的尝试,算法结合分块和分解算法的优点,利用一些策略避免了删除支持向量的可能,并分析了分块大小的影响,指出算法在支持向量较少的情况下可以取得较好的效果。
文献[6]提出一种高效的计算决策函数的缓存策略,该策略充分利用了SVM训练过程中到达上界的拉格朗日乘子变化平稳的特性,有效地降低了计算决策函数的代价,采用该缓存策略的SMO算法在运算速度上得到了显著的提高,而且缓存策略很容易推广到其他分解算法中。
文献[7]给出了一种可行方向解释,在综合考虑与工作集相关的目标函数的下降量和计算代价的情况下,提出了一种收益代价平衡的工作集选择方法,提高了缓存的效率,试验证明该方法特别适用于样本较多,支持向量较多的情况。
值得注意的是Jain2Xiong依据分解的方法提出一种改进的SVM训练算法。
实验表明该算法在不牺牲推广能力的情况下比改进的SMO算法速度提高约9倍。
5 结束语
SVM本质上是一种基于统计与PAC学习的非参数机器学习方法,寻找更好的理论模型来改进SVM正成为该领域的研究难点,同时对于SVM的求解算法的改进也方兴未艾。
但是SVM仍然存在很多的重点和难点:
511 核函数构造问题
核函数的构造虽然有定理限制,但是对于实际的问题其构造多依赖经验,如何根据经验知识和实际问题,选择和构造核函数至今还缺乏相应的理论指导。
512 处理大规模数据的问题
现在虽然对于SVM产生了一些有效的解法,如SMO及其改进方法,但是如何更好的解决算法的速度和数据集的大小之间的矛盾仍是待研究的问题。
513 对于多类问题
SVM是针对两类问题提出的,在推广到多类问题时的有效算法还有待研究,而且理论证明还不完善。
514 SVM是实现结构风险最小化的成果,但是具体如何实现及其一些关键性的数学证明还没有完备的理论。
此外,SVM方法虽然在实际的应用中已经取得了很大的成功,但是其应用范围仍然没有神经网络广泛,所以应用领域的拓展和如何更有效地应用该理论方法给众多研究者提出了机遇和挑战。
参考文献:
[1] VapnikV.统计学习理论的本质[M].张学工.北京:
清华大学出版社,2000.VapnikV.TheNatureofStatisti2calLearningTheory[M].HANGXuegong.Beijing:
TsinghuaUniversityPress,2000.(inChinese
[2] BurgesC.Atutorialonsupportvectormachinesforpatternrecognition[J].DataMiningandKnowledgeDiscovery,1998,2(2:
143.
[3] OsunaE,FreundR,GirosiF.Improvedtrainingalgorithmforsupportvectormachines[C].In:
7thIEEEworkshoponNeuralNetworksforSignalProcessing,NNSP97,IEEE,1997:
276~285.
[4] BerndHeiseleetal.Hierarchicalclassificationandfeaturere2ductionforfastfacedetectionwithsupportvectormachines[J].PatternRecognition,2003:
36:
2007~2017.
[5] 吴翔,谭李,陆文凯,张学工.提高超大规模SVM训练计算速度的研究.模式识别与人工智能.2003,16(1:
46~49.
[6] 孙剑,郑南宁,张志华.一种训练支撑向量机的改进贯序最小优化算法.软件学报.2002,13(10:
2007~2013.[7] 李建民,张钹,林福宗.序贯最小优化的改进算法.软件学报.2003,14(5919~925.
[8] Jain2XiongDong,ChingYS,AdamK.AFastSVMTrainingAlgorithm[J].InternationalJouranlofPatternRecognitionandArtificialIntelligence,2003,17(3:
367~384
[作者简介] 杜晓东(1981.22,男,汉族,山东聊城,系统工程专业,山东大学硕士研究生,研究方向:
数据挖掘与模式识别。
(收稿日期:
2004212210
信号处理与模式识别信息技术与信息化40
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 支持 向量 及其 算法 研究 概要