（应用数学专业论文）支持向量机和支持向量域描述的若干问题研究.pdf

摘要 摘要 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是基于统计学习理论提出的一种 新型有监督模式识别方法采用结构风险最小化原则，s v m 在最大化分类间隔 和最小化分类误差之间取得折衷，以控制分类器的泛化能力s v m 较好地解决 了小样本、高维数及非线性等实际问题，具有拟合精度高、选择参数少、推广能 力强和全局最优等特点s v m 成为机器学习领域新的研究热点，并被广泛应用 到模式识别、函数拟合和密度估计等领域本文针对大规模样本集的s 训练 问题、s v m 的集成学习问题、变形s v m 问题、支持向量域描述( s u p p o r tv e c t o r d o m a i nd e s c r i p t i o n ，s v d d ) 的快速训练问题等进行研究，主要研究工作如下： 1 研究了大规模样本集的s v m 训练算法s v m 在训练大规模样本集时面临 着占用内存多、计算代价大的问题，这也成为实际应用的瓶颈问题基于弗行学 习中“分而治之”的理念和“支持向量与全体训练样本等价”的结论，提出一 种同心超球面支持向量机( h y p e r s p h e r es u p p o r tv e c t o rm a c h i n e ，h s v m ) h s v m 以相同层数的两组同心超球面组对正负两类样本进行分割，对分层间隔内的样 本采用s v m 训练，合并所有分层间隔中支持向量的并集以参与最终的s v m 训 练h s v m 既保持了s v m 的分类精度又降低了s v m 的训练时间 2 研究了s v m 的集成学习算法运用集成学习的理念构造了一种空间支 持向量域分类器( s p a c es u p p o r tv e c t o rd o m a i nc l a s s i f i e r ，s s v d c ) 选取支持向 量域分类器( s u p p o r tv e c t o rd o m a i nc l a s s i f i e r ，s v d c ) 和k 近邻( kn e a r e s t n e i g h b o r ，k n n ) 作为子分类器，s s v d c 以选择集成的策略对两者的预测结果 进行集成s s v d c 首先采用s v d d 求得两类样本的最小包围超球，并以超球的 描述边界将训练样本划分为互不相交的几个区域；其次计算待测样本到两个最 小包围超球球心的距离，根据其与两个最小包围超球半径的大小关系判断待测 样本所处区域；最后选择相应的子分类器得到最终的分类结果由于子分类器 均针对样本的某个子集进行训练，s s v d c 具有较短的训练时间由于根据样本 的分布选取相应的子分类器，s s v d c 具有较高的分类精度且其分类精度受核参 数变化的影响不大数值实验验证了s s v d c 的有效性以及对比s v m 和s v d c 的 优越性 西安电子科技大学博士论文 1 1 支持向量机和支持向量域描述的若干问题研究 3 研究了变形s v m 算法通过改变原始优化问题的函数项、变量或系数得 到了一系列变形s v m 算法，这在一定程度拓宽了s v m 的应用范围针对变形s v m 中的二次损失函数s v m ，构造一种光滑对角加权支持向量机( s m o o t hd i a g o n a l w e i g h t e ds u p p o r tv e c t o rm a c h i n e ，s d w s v m ) 在线性空间中，直接运用光滑技 术得到光滑模型，也即采取s i g m o i d i 垂l 数的积分函数来逼近正号函数形式的松 弛在非线性空间中，先分别利用l a g r a n g e 乘子向量来代替分类超平面的权值向 量和原对偶规划隐含的分类超平面的权值向量表达式对原规划的目标函数进行 转换，再利用光滑技术构造光滑模型对线性空问和非线性空间中得到的光滑模 型，均采用n e w t o n 法求解，具有较高的效率 4 提出了一种约简支持向量域描述算法( r e d u c e ds u p p o r tv e c t o rd o m a i n d e s c r i p t i o n ，r s v d d ) s v d d 的训练即为求解一个所含未知数个数等于全体训 练样本个数的凸二次规划为了提高s v d d 的训练速度，r s v d d 对每个样本定 义一种自中心距离比值，定义此值为该样本到中心的距离与所有样本的平均中 心距离的比值，并以此值作为判断该样本成为支持向量的可能性度量r s v d d 选取自中心距离比值较大的部分样本参与s v d d 乇i i 练，从而减少了待解q p 的规 模该算法引入参数少，易于实现且保持了目标类精度 5 提出了一种信赖支持向量域描述算法( c o n f i d e n c es u p p o r tv e c t o rd o m a i n d e s c r i p t i o n ，c s v d d ) 由于支持向量往往分布在s v d d 的描述边界附近，基于 这个几何特性，定义了一种信赖抽样方法以提取部分样本参与s v d d 训练依 次以每个样本为中心，做一个以某定长为半径的超球统计落入该超球中的训 练样本数目，并将该值作为判断中心样本属于支持向量的信赖度量( c o n f i d e n c e m e a s u r e ) 根据信赖度量的值将训练样本升序排列，c s v d d 提取排在前面的部 分样本作为边界向量集参与最终的s v d d i j i i 练，缩短了s v d d 的训练时间并保持 了s v d d 的目标类精度 关键词：统计学习理论支持向量机集成学习变形支持向量机光滑技术 支持向量域描述自中心距离比值信赖度量 西安电子科技大学博士论文 摘要 i i i a b s t r a c t s u p p o r tv e c t o rm a c h i n e ( s v m ) i san e ws u p e r v i s e dp a r e mr e c o g n i t i o nm e t h o d b a s e do ns t a t i s t i c a ll e a r n i n gt h e o r y ( s l t ) s v ma d o p t ss t r u c t u r a lr i s km i n i m i z a t i o n ( s r m ) p r i n c i p l e ；i tm a k e sc o m p r o m i s eb e t w e e nt h em a r g i nm a x i m i z a t i o na n d t h ee r r o r m i n i m i z a t i o n ，s oa st oc o n t r o lt h eg e n e r a l i z a t i o na b i l i t yo ft h eo b t a i n e dc l a s s i f i e r s v m c a nb e t t e rd e a lw i t hp r o b l e m s ，s u c ha ss m a l ls a m p l e ，h i g hd i m e n s i o na n dn o n l i n e a r i t y s v mh a sa d v a n t a g e ss u c ha sh i g hc l a s s i f i c a t i o na c c u r a c i e s ，f e wp a r a m e t e r s ，g l o b a l o p t i m u m sa n ds t r o n gg e n e r a l i z a t i o np e r f o r m a n c e s ；i tb e c o m e sa n e wr e s e a r c ha r e ai n t h ef i e l do fm a c h i n el e a r n i n gr e s e a r c ha n di th a sb e e nw i d e l ya p p l i e di n t ov a r i o u sa r e a s ， s u c ha sp a a e mr e c o g n i t i o n ，f u n c t i o nr e g r e s s i o na n dd e n s i t ye s t i m a t i o n f o c u s i n go nt h e e x i s t i n gp r o b l e m s ，s u c ha s s v mt r a i n i n gf o rl a r g e - s c a l es a m p l e s ，s v me n s e m b l e l e a r n i n g ，r e f o r m a t i o no fs v m ，s u p p o r t v e c t o rd o m a i nd e s c r i p t i o n ( s v d d ) ，e t c ， d e t a i l e ds t u d i e sa r em a d ea n da l lt h er e s e a r c h e sc a nb es u m m a r i z e di n t ot h ef o l l o w i n g f i v e p a r t s ： 1 t h er e s e a r c ho nt h ea l g o r i t h m so fs v mt r a i n i n gf o rl a r g e s c a l es a m p l e s t h e t r a i n i n go fs v mb e c o m e sd i f f i c u l ti np r a c t i c a la p p l i c a t i o n sf o rl a r g e - s c a l es a m p l e s ；i t t a k e su pl a r g em e m o r ya n de n o r m o u sc o m p u t a t i o nt i m e b a s e do nt h ei d e o l o g yo f “d i v i d ea n dc o n q u e r i np a r a l l e ll e a r n i n ga n dt h ec o n c l u s t i o no f “t h ee q u i v a l e n c e b e t w e e ns u p p o r tv e c t o r sa n dt h ew h o l et r a i n i n gs a m p l e s ”，c o n c e n t r i ch y p e r s p h e r e s u p p o r tv e c t o rm a c h i n ei sp r o p o s e da n di sc a l l e dh s v m f o rs h o r t d i v i d i n gt h ep o s i t i v e a n dn e g a t i v es a m p l e su s i n gg r o u p so fc o n c e n t r i ch y p e r s p h e r e sw i t ht h es a m el a y e r s ， h s v mt r a i n st h es a m p l e sb e t w e e nt h em a r g i n su s i n gs v ma n dt a k e st h ec o m b i n a t i o n o ft h eo b t a i n e ds u p p o r tv e c t o r si nc o r r e s p o n d i n gm a r g i n st op a r t i c i p a t ei nt h ef i n a ls v m t r a i n i n g h s v mg u a r a n t e e st h ec l a s s i f i c a t i o na c c u r a c i e so fs v mw h i l ei tr e d u c e st h e t r a i n i n gt i m eo fs v m 2 t h er e s e a r c ho ne n s e m b l el e a r n i n go fs v m e n s e m b l el e a r n i n gi d e o l o g yi su t i l i z e d t oc o n s t r u c tas p a c es u p p o r tv e c t o rd o m a i nc l a s s i f i e r ( s s v b c ) t a k i n gs v d c ( s u p p o r tv e c t o rd o m a i nc l a s s i f i e r ) a n dk n n ( kn e a r e s tn e i g h b o r ) a st h es u b 西安电子科技大学博士论文 i v 支持向量机和支持向量域描述的若干问题研究 c l a s s i f i e r s ，s s v d cu s e ss e l e c t i v ee n s e m b l es t r a t e g yt oo b t a i nt h ef i n a lc l a s s i f i c a t i o n r e s u l t s 。f i r s t l y , s s v d cu s e ss v d d t oo b t a i nt h em i n i m a le n c l o s i n gh y p e r s p h e r e so ft h e p o s i t i v e a n dn e g a t i v e s a m p l e s ，a n dd i v i d e s t h e t r a i n i n gs a m p l e s i n t os e v e r a l d i s c o n n e c t e dr e g i o n su s i n gb o u n d a r i e so ft h et w oh y p e r s p h e r e s ；t h e ns s v d cc a l c u l a t e s t h ed i s t a n c e so fo n et e s ts a m p l et ot h ec e n t e r so ft h et w om i n i m a le n c l o s i n gs p h e r e so f t h ep o s i t i v ea n dn e g a t i v es a m p l e s ，a n ds p e c i f i e st h er e g i o nt h a tt h et e s ts a m p l eb e l o n g s t ob a s e do nt h er e l a t i o n s h i pb e t w e e nt h ed i s t a n c e sa n dt h er a d i u s e so ft h et w om i n i m a l e n c l o s i n gs p h e r e s ；f i n a l l ys s v d ct a k e st h ec o r r e s p o n d i n gs u bc l a s s i f i e rt oj u d g ei t s l a b e l s i n c es u bc l a s s i f i e r sa r ec a r r i e do u to ns u b s e t so ft h ed a t a , s s v d ch a ss h o r t t r a i n i n g t i m e s s i n c ed i f f e r e n ts u bc l a s s i f i e r sa r ee r e c t e db a s e do nt h e s a m p l e d i s t r i b u t i o n ，s s v d ch a sh i g ht a r g e ta c c u r a c i e sw h i c hv a r yl i r l ew i t hk e r n e lp a r a m e t e r s n u m e r i c a le x p e r i m e n t sd e m o n s t r a t et h ee f f e c t i v e n e s so fs s v d ca n dt h es u p e r i o r i t y o v e rs v ma n ds v d c 3 t h er e s e a r c ho nr e f o r m a t i o no fs v m r e f o r m a t i o no fs v mb r o a d e n st h e a p p l i c a t i o na r e a so fs v m ，w h i c hc a nb eo b t a i n e db yc h a n g i n gt h et e r m s ，v a r i a b l e so r c o e f f i c i e n t si nt h eo b j e c t i v ef u n c t i o ni nt h eo r i g i n a lo p t i m i z a t i o np r o b l e m b a s e do n q u a d r a t i cl o s sf u n c t i o ns v m ，s m o o t h i n gt e c h n i q u ei sa d o p t e dt oc o n s t r u c ts m o o t h d i a g o n a lw e i g h t e ds u p p o r tv e c t o rm a c h i n e ( s d w s v m ) i nt h el i n e a rs p a c e ，s m o o t h m o d e li sd i r e c t l yo b t a i n e db yu s i n gs m o o t h i n gt e c h n i q u e ，w h i c ht a k e st h ei n t e g r a l f u n c t i o no fs i g m o i df u n c t i o nt oa p p r o x i m a t et h es l a c ki nt h ep l u sf u n c t i o nf o r m i nt h e k e r n e ls p a c e ，t w om e t h o d sa r eu s e dt ot r a n s f o r mt h eo r i g i n a lo b j e c t i v ef u n c t i o nb e f o r e a p p l y i n gs m o o t h i n gt e c h n i q u e o n eu s e st h em e t h o da d o p t e db yt r a d i t i o n a ls s v m w h i c ht a k e st h el a g r a n g em u l t i p l i e rv e c t o rt os u b s t i t u t et h ew e i g h tv e c t o ro ft h e s e p a r a t i n gh y p e r p l a n e ；t h eo t h e ru s e sd u a lt e c h n i q u eb e t w e e nt h ep r i m a la n dd u a l p r o g r a mt of i n dt h ee x p r e s s i o no ft h ew e i g h tv e c t o ro ft h es e p a r a t i n gh y p e r p l a n e f o r t h eo b t a i n e ds m o o t h m o d e l si nt h el i n e a ra n dk e r n e ls p a c e ，n e w t o nm e t h o di sp r o p o s e d t of i n dt h eg l o b a lo p t i m u m sw h i c hg u a r a n t e e sh i g he f f i c i e n c y 4 r e d u c e ds u p p o r tv e c t o rd o m a i nd e s c r i p t i o n ( r s v d d ) i sp r e s e n t e d t h et r a i n i n g o fs v d di n v o l v e ss o l v i n gac o n v e xq u a d r a t i cp r o g r a m , w h o s en u m b e ro fv a r i a b l e si s e q u a lt ot h en u m b e ro ft r a i n i n gs a m p l e s t oa c c e l e r a t et h et r a i n i n gs p e e d , r s v d d 西安审子科技大学博士论文 a b s t r a c t v d e f i n e sas e l fc e n t r a ld i s t a n c er a t i of o re a c hs a m p l e ，w h i c hi st h er a t i oo ft h ec e n t r a l d i s t a n c ed i v i d e db yt h em e a nc e n t r a ld i s t a n c e ，a n dt a k e si ta sap r o b a b i l i t ym e a s u r et o j u d g ew h e t h e ro n es a m p l ei sas u p p o r tv e c t o ro rn o t r s v d ds e l e c t ss o m es a m p l e sw i t h h i 曲s e l fc e n t r a ld i s t a n c er a t i o st op a r t i c i p a t ei nt h ef i n a ls v d dt r a i n i n g ，t h u sr e d u c i n g t h et r a i n i n gs c a l e r s v d di se a s yt oi m p l e m e n t , h a sf e w p a r a m e t e r sa n dm a i n t a i n sh i i 曲 t a r g e ta c c u r a c i e sa n ds h o r tt r a i n i n gt i m e 。 5 c o n f i d e n c es u p p o r tv e c t o rd o m a i nd e s c r i p t i o n ( c s v d d ) i sp r o p o s e d b a s e do n t h eg e o m e t r yc h a r a c t e r i s t i ct h a ts u p p o r tv e c t o r su s u a l l yd i s t r i b u t ea r o u n dt h ed e s c f i p t i o n b o u n d a r y , ac o n f i d e n c es a m p l i n gs t r a t e g yi sp r o p o s e ds oa st os e l e c ts o m es a m p l e st o p a r t i c i p a t ei nt h es v d dt r a i n i n g c e n t e r e da te a c hs a m p l e as p h e r ew i t h 做e dr a d i u si s d r a w n c o u n t i n gt h en u m b e ro fs a m p l e si nt h eu s e r - d e f i n e ds p h e r e ，c s v d dt a k e st h i s n u m b e ra sac o n f i d e n c em e a s u r et oj u d g ew h e t h e rt h ec e n t e rs a m p l ei so n es u p p o r t v e c t o ro rn o t r a n k i n gt h e g a i n i n gs a m p l e si na s c e n d i n go r d e ra c c o r d i n gt ot h e c o n f i d e n c em e a s u r e ，c s v d de x t r a c t sac e r t a i np o r t i o no ft h o s ef o r m e rr a n k e ds a m p l e s a sb o u n d a r yv e c t o r st op a r t i c i p a t ei nt h es v d dt r a i n i n g t h et r a i n i n gt i m eo f ( 3 s v d d a r es h o r t e rt h a nt h a to fs v d d ，w h i l et h et a r g e ta c c u r a c i e so ft h ef o r m e ra r ei d e n t i c a l w i t ht h o s eo f 也el a t t e r k e y w o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r ys u p p o r tv e c t o rm a c h i n e e n s e m b l e l e a r n i n g r e f o r m a t i o no fs v ms m o o t h i n gt e c h n i q u e s u p p o r tv e c t o rd o m a i n d e s e r i p t i o n s e l fc e n t r a ld i s t a n c er a t i oc o n f i d e n c em e a s u r e 西安电子科技大学博士论文 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：三蝉 闩期圣! 12 全：乏 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权 保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分 内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业 后结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 r 期塑翌2 ：2 ：五 r 期垒啤必 第一章绪论 第一章绪论 本章首先阐明了所选课题的研究背景和意义，从知识发现的角度简要回顾了 机器学习的发展过程；然后对基于统计学习理论的支持向量机方法的产生、主要 研究内容以及国内外的研究现状进行阐述；最后综述了本论文的主要研究工作和 结构安排 1 1 研究背景和意义 人类智慧的一个很重要的方面表现为从过去的数据和以往的知识中学习的能 力通过归纳学习，得到对客观世界的认识和规律，并运用这些规律对未知的现 象做出正确的预测和判断把从过去的数据和以往的知识中学习并获取规律的能 力称为“学习能力用获得的规律不仅可以解释已知的实例，而且能够对未知的 现象做出正确的预测和判断，称这种能力为“推广能力” 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非常 方便地获取和存储大量的数据面对大量的数据，传统的数据分析工具( 如管理信 息系统) 只能进行一些表层的处理( 如查询、统计学) ，而不能获得数据之间的内在 关系和隐含的信息为了摆脱“数据丰富、知识贫乏”的困境，迫切需要一种能 够智能地将数据自动转化为有用信息和知识的技术和工具 用计算机来模拟上述学习能力的问题被称为“基于数据的机器学习问题”，其 任务就是：设计某种方法和模型，通过对已知数据的学习，找到数据内在的相互 依赖关系，从而对未知数据进行预测或判断，使机器具有良好的推广能力 关于机器学习的研究，最早可以追溯到2 0 世纪5 0 年代，其研究和发展历程 可分为如下四个阶段【1 翊： 1 r o s e n b l a t t 感知器( 2 0 世纪6 0 年代) 1 9 6 2 年r o s e n b l a t t 提出第一个学习机器的模型，称为感知器【3 】它在机器学习 领域中有着里程碑的意义，标志着人们对学习过程进行数学研究的真正开 始r o s e n b l a t t 将感知器的模型表示为一个计算程序，并通过试验说明了这个模型 具有一定的泛化能力n o v i k o f f t 4 】证明了感知器的第一个定理：若学习样本能够以 间隔p 被分割开，则感知器至多需要【r 2 p 2 】次修改，就可以将学习样本分隔开该 西安电子科技大学博士论文 2 支持向量机和支持向量域描述的若干问题研究 定理在创建学习理论中起着十分重要的作用 2 学习理论的创立( 2 0 世纪6 0 7 0 年代) 在这段时间里，统计学习理论得到了很大的发展，提出了v c 维和v c 熵的概 念利用这些概念发现了泛函空间的大数定律，并通过研究它与学习过程的联系 得到了关于收敛速率的非渐进界的主要结论；同期还提出了用于解决不适定问题 的正则化理论，这对学习理论的发展产生了深远的影响此外，作为统计学和信 息论中最伟大的思想之一，算法复杂度的思想，也在这一时期萌爿5 们 3 人工神经网络 1 9 8 6 年。l e c 眦【7 】、r u m e l h a r t 、h i t o n 和w i l l i a m s 【8 1 独立地提出了构造感知器所 有神经元的向量系数的后向传播算法( b a c kp r o p a g a t i o n ，b p ) 此方法采用连续的 s i g m o i d 函数修改了感知器的m c c u l l o c h p i r s 神经元模型，使得对于任意固定的输 入都存在对应于所有神经元的所有系数的梯度利用计算出的梯度，人们可以应 用任何基于梯度的方法来构造对预期函数的无限逼近此后，感知器也被称为神 经网络神经网络对于逼近实数值、离散值或向量值的目标函数提供了一种健壮 性很强的方法【9 1 ，并在很多实际问题中取得了惊人的成功由于缺乏统一的数学理 论，人工神经网络容易产生过拟合现象，虽然对训练数据表现良好，但是网络的 泛化能力较低 4 统计学习理论 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 是一种专门研究小样本情况下 机器学习规律的理论 1 0 】；它对小样本统计问题建立了一套新的理论体系在这种 体系下的统计推理规则不仅考虑了对渐进性能的要求，而且追求在现有的有限信 息下的最优结果v a p n i k 等从2 0 世纪6 0 年代开始致力于这方面的研刭1 ，1 1 】到2 0 世纪9 0 年代中期，随s l t 的不断发展和成熟，也由于a n n 等学习算法在理论上 缺乏实质性的进展，s l t 开始受到越来越广泛的重视 s l t 对有限样本情况下模式识别的一些根本性问题进行了系统地研究，它能 将很多现有的方法纳入其中，在很大程度上解决了模型选择和过学习问题、非线 性和维数灾难问题、局部最小值问题等s l t 的一个核心概念就是v c 维【1 0 1 ，它 是描述函数集( 或学习问题) 的复杂性( 或学习能力) 的一个重要指标在v c 维的基 础上发展出一系列关于统计学习的一致性( c o n s i s t e n c y ) 、收敛速度( c o n v e r g e n c e s p e e d ) 、泛化性能( g e n e r a l i z a t i o np e r f o 彻a n c e l 等重要结论【1 2 1 西安电子科技大学博士论文 第一章绪论 3 1 9 9 2 年到1 9 9 5 年期间，v a p n i k 等在s l t 理论的基础上提出了一种新的机器 学习方法支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 3 , 1 4 s v m 方法具有坚实的 理论基础，被视作研究机器学习问题的一个基本框架s v m 根据有限的样本信息 在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力s v m 可以有效地解决高维数据模型的构建问题，并具有泛化能力强、收敛到全局最优 解、维数不敏感等优点；因而s v m 被成功地应用于模式识别、回归估计和概率密 度函数估计等领域 1 4 - 1 6 】 目前，对支持向量机的研究已经成为国际学术的一个研究热点，国内外专家 在此领域也展开了广泛的研究以s c h o l k o p f 为首的研究小组提出的一些关于s v m 的成果代表了目前该领域的最高成就：如快速学习算法、大规模学习算法、半监 督学习算法、主动学习算法等；以m a n g a s a r i a n 为首的团队在光滑s s v m 的学习算 法设计、收敛性分析等方面取得了许多研究成果；t a x 等提出的s v d d 在很多领 域也取得了广泛的应用国内学者也对s v m 开展了广泛的研究，但大多数研究内 容和方法是对国外先进成果的跟踪和吸收，达到国际领先或者具有突破意义的理 论和应用成果仍寥寥无几掌握s l t 和s v m 的相关基础性知识，着重针对其中尚 存在的不成熟、不完善和迫切需要解决的若干问题，投入精力并展开卓有成效的 研究有着重要的意义 1 2 支持向量机的研究现状 相比于神经网络等传统的学习方法，s v m 具有许多优异的性质概括地说， 它的优点主要体现在以下几个方面【i 1 1 1 ： 。1 针对小样本情况提出，其最优解是基于现有的有限样本信息得到，而并非 基于样本数目趋于无穷大时的样本信息得到 2 算法设计为一个凸二次规划，保证了解的全局最优性，解决了传统学习方 法无法避免的局部极小值问题 3 采用结构风险最小化原理，同时考虑了经验风险和置信范围的最小化，保 证了学习机器具有良好的泛化能力 4 采用核函数技术，巧妙地解决了算法复杂度与输入向量维数密切相关的问 题通过一个非线性映射函数，将输入空间中的非线性分类问题映射到一个高维 的特征空间，并在此高维空间中构造线性判别函数由于判别函数仅由样本间的 西安电子科技大学博士论文 4 支持向量机和支持向最域描述的若干问题研究 内积决定，s v m 通过引入核函数而不需要知道非线性映射的具体形式和高维空间 的维数。定义不同的核函数，s v m 可以实现许多其他现有的学习算法 s v m 方法尚处在蓬勃发展的阶段，有很多方面尚不完善也有很多问题亟待解 决比如许多理论尚不能在实际算法中实现；有关s v m 的某些理论解释也并非完 美；对学习机器的v c 维进行分析尚没有通用的方法；实际问题中对于核函数的选 择和构造缺乏理论指导；在计算上存在算法速度慢、算法复杂而且难以实现以及 检测阶段运算量大的问题；分类性能受噪音及孤立点的影响较大；多类分类等问 题对s v m 的研究有待进一步深入和完善 1 2 1 理论研究 近几年涌现的大量理论研究成果完善和发展了s v m 理论，更为其应用研究奠 定了坚实的基础；主要研究成果归结如下 1 模型选择 称求解s v m 的二次规划中惩罚参数、核函数类别与核参数的选择问题为“模 型选择”模型选择是s v m 中一个公开的问题 核参数从某种程度上定义了一个高维特征空间，反映了数据的先验知识核 参数的选取过程也是模型比较的过程如何构造与实际问题相适应的核函数一直 是支持向量机研究的重要课题【1 7 】a m a r i 提出利用实验数据修正已有的核函数，使 之与问题相吻合【1 8 】。文献 1 9 2 1 】分别针对文本分类、图像处理等具体问题构造不 同类型的核函数，获得的泛化性能优于径向基核或多项式核 惩罚参数和核参数中不同参数的组合构成不同的模型，这些参数决定了s v m 的泛化性能简单、准确和有效地估计泛化性能是进行模型选择、参数优化以及 核函数优化的基础最简单的是借助设计者的经验进行手工调整【2 2 1 ，但所得结果 缺乏可靠性更加规范化的方法可分为以下三类 2 3 - 2 7 】： 1 ) 确认集和交叉验证法 确认集法首先定义训练集、确认集和测试集，然后采用不同的参数组合对训 练集的数据进行训练，将训练得到的s v m 在确认集上验证，选出误差最小的s v m 对测试集进行测试交叉验证法【2 3 1 ( c r o s sv a l i d a t i o n ，c v ) 将数据集随机分割成互不 重叠的k 个子集，应用k 1 个子集训练，剩下的一个子集测试整个计算过程重复 k 次，故交叉验证的计算量较大留一法【卅( l e a v eo n eo u t ，l o o ) 是一种极端的 西安电子科技大学博士论文 第一章绪论 交叉验证方法，每次仅保留一个样本用于测试，其余样本用于训练；该方法可以 给出对期望泛化误差的几乎无偏估计 2 ) 基于界的方法 该类方法最小化不同的泛化误差界以求取最佳模型参数b u r g e r s 【1 4 1 提出v c 维界h d 2 1 1w i l 2 + 1 ；当d 2i fw i l 2 + 1 l + 1 时，b u r g h s 取h = ，+ 1 v a p n i k 和c h a p e l l e 指出型导兰竺型竺型! 呈逊，称s 是支持向量跨距并称该式的右边为跨 ll 距边界口5 1 ；v a p n 搬以上d 亳d 2 l lw1 1 2 作为半径间隔界，而c h a p i ，l l e 对该半径 间隔界做出修改l d 0 ，序列r ( q ) 和k ( q ) 依概率p 收敛到同一个极限： l i m p ( 尺( ) 一i n f 尺( 口) ) 占) = 0 ，- + 口a i m p ( ( q ) 一i n f r ( a ) ) 占) ：0 ， o 则e r m 原则对于函数集 q ( z ，口) ，口人) 和概率分布函数f ( x ，y ) 是一致的 ( 2 6 ) ( 2 7 ) 换句话说，如果一个e r m 方法能够提供一个函数序列 q ( z ，) ，= 1 ，2 ， ，使 得期望风险和经验风险都收敛到一个可能的最小风险值，则称这个e r m 方法是一 致的为了保证一致性是所研究的学习方法的性质而不是由于函数集中的个别函 数导致，提出非平凡一致性的概念，即定义式( 2 7 ) 对预测函数集的所有子集都成 立后面说的一致性就是指非平凡一致性 定理2 1 【1 1 3 1 设