（应用数学专业论文）几类支持向量机变型算法的研究.pdf

摘要 摘要 统计学习理论是一种基于小样本的机器学习理论，经过几十年的发展，目前 已经形成了一套比较完整的理论体系支持向量机是在此理论基础之上提出来的 一种新机器学习方法它根据结构风险最小化原则，通过核函数在一个高维特征 空间中构造最优线性决策函数，避免了维数灾难，且可达到全局最优解，具有较 高的泛化能力由于支持向量机具有良好的性能，已经被广泛地应用于模式分类， 函数逼近和密度估计等问题，日益受到学者们的广泛关注，其理论研究、算法实 现和应用方面都取得了重大进展，成为机器学习领域的热点课题 为了降低标准支持向量机的计算复杂度，提高其学习速度和泛化能力，本文 主要研究几类支持向量机变型算法的理论及其应用，主要内容如下： 一、对目前支持向量机的研究现状做了综述，然后简要地介绍了支持向量机 的相关基本知识 二、研究一类基于核最小平方误差的支持向量机变型算法首先给出最小二 乘支持向量机的分类几何解释；其次将用于分类问题的临近支持向量机推广到回 归问题上，提出临近支持向量回归机，并给出一种基于c h o l e s k y 分解的快速算法， 此外证明了新模型对分类问题和回归问题的模型等价性；然后结合最小二乘支持 向量机和临近支持向量机的优点，提出直接支持向量机，该模型可同时适应于分 类问题和回归问题，且求解更简单，训练速度快，泛化能力也未降低该模型与 最小二乘支持向量机相比，增强了问题的凸性，保证得到的解全局最优；与临近 支持向量机相比，修正了线性与非线性模型不统一的缺点，测试速度更快最后 通过数值实验验证了上述研究的可行性和有效性 三、首先理论上证明了模糊支持向量机模型与多惩罚因子支持向量机的等 价性，提供了将模糊支持向量机隶属度参数作为模型选择参数进行自适应求解的 理论依据；然后针对模糊支持向量机的隶属度设计方法，分别基于支持向量机分 类面与样本的几何分布关系和基于支持向量机分类的本质，提出两种更合理的新 隶属度设计方法，通过数值实验验证了这两种方法的有效性，并与现有一些方法 进行了比较研究 四、研究二次损失函数的模糊支持向量机泛化能力首先给出二次损失函数 模糊支持向量机的数学模型，然后证明其等价于带有新核函数的硬间隔支持向量 机，将模糊隶属度参数转化为新核函数的参数；其次将硬间隔支持向量机的四种 泛化能力估计方法，推广到二次损失函数模糊支持向量机；最后通过理论分析和 i l 几类支持向量机变型算法的研究 数值实验系统地比较它们的估计性能，得到对于二次损失函数的模糊支持向量机 最好的泛化能力估计界，为后期的模型选择奠定基础 五、研究了双惩罚因子的二次损失函数支持向量机的模型选择及其应用将 二次损失函数支持向量机应用于乳腺癌x 线影像病灶点的识别，针对问题中两类数 据的不均衡性，对其采用不同的惩罚因子，然后根据前面的研究结果，通过最小 化泛化错误率上界，给出一种自动确定模型参数的方法最后通过对x 线影像中的 肿块检测和钙化簇检测实验，验证了该方法不但有效，而且可达到更好的泛化精 度 关键词：统计学习理论支持向量机 模糊隶属度函数模型选择 核函数最小平方误差c h o l e s 时分解 b f g s 拟牛顿法肿块检测钙化簇检测 a b s t r a c t a b s t r a c t s t a t i s t i c a ll e a n l i r 喀t l l e o 巧i sat l l e a t r i c a l 仔锄e w o r ko fm a c l l i n el e a r l l i n gf o rs m a l l s 锄p l e s d 面n gt h ep a s td e c a d e s ，i th 嬲b e e nd e v e l o p m e n t i n gt ob ear e l a t i v e l y c o m p 础l e 璐i v es y s t e mo ft l l e o 阱s u p p o r tv e c t o rm a c k n e ( s v m ) c o m e so u ta san e w m a c h i n el e a r i l i n ga l g o r i t l l mb a s e do nt h i st 1 1 e o 够a c c o r d i n gt 0m es n l i c t u r a lr i s k m j l 】j 瑚j z a t i o n ( s r m ) m l e ，i tc a l lg e tt h eg l o b a lo p t i m a ll i l l e a rd e c i s i o nf h n c t i o ni i la 1 1 i g l l e r d i m e l l s i o n a lf e a h e s p a c ev i aak e m e l 向n c t i o n na v o i d s 1 ec u r s eo f d i m e n s i o n a l 时a n di so f9 0 0 dg e n e r a l i z a t i o na b i l i 够s i n c ei t sg o o dp e r f o n i l a n c ei i l p a _ t t e mr e c o g n i t i o n ，如n c t i o na p p r o x i m a t i o n 趾dd e i l s i t ) re s t i m a t i o i l i th 嬲a t 吮l c t e da 昏e a t a l t e n t i o no fr e s e a r c h e s ，a i l d d e v e l o p e dr 乏l p i d l y i n t l l e o r y c o i i 】l p u t i n g a l l d 印p l i c a t i o n s ，锄db e c o m e sah o tt o p i c i i lm a c l l i r l el e a m i i l g i no r d e rt 0i m p r o v et h e 慨n i i 坞s p e e da 疵rg e n e r 2 l l i z a t i o na b i l i t ) ，o f 位l d i t i o n a l s v m ，1 1 1 i sd i s s e 僦i o nm 2 l i i d yf o c u s e so nt h er e s e a r c ho ft l l et 1 1 e o d ra i l da p p l i c a t i o n b a s e do ns o m ev 撕a n t so fs v m n 伦c o n t e n t si 1 1t l i sd i s s en l a t i o na r ed e s c r i b e d 嬲 f o l j o w s 1 ar e v i e wo fc u r r e n ts t a ：t u so fr e l a t i e dr e s e a r c ho fs v mi sg i v e n ，a i l dt h e ni ti s f o l l o 、e db yab r i e fi n 仃o d u c t i o no ft h e 矗l n d a m e n t a l so fs v m 2 a 咖d yo ns e v e r a ls v m v 蜀u r i 锄tb a s e do nk e m e lm i m m u ms q u a r ee 仃0 r ( m s e ) f i r s t l y ，t 1 1 eg e o m e t r i cd e s c r i p t i o no fl e a s ts q u a r es v m ( l s s v m ) c l a s s i f i e ri s d e s c r i b e d ；s e c o n d l y ，t 1 1 ep r o x i m a ls v m ( p s v m ) m o d e lf o rc l a s s i f i c a t i o np r o b l e mi s e x t e n d e dt or e g r e s s i o np r o b l e m ，t l l u sp r o x i m a ls u p p o nv e c t o rr e g r e s s i o nm a c l l i n ei s p r e s e n t e d ，a sw e ha saf a s tc o i n p u t i n gm e m o db a s e do nc h o l e s k yd e c o m p o s i t i o n t h e e q u i v a l e n c eo fc l a s s i f i c a t i o nm o d e la 1 1 dr e g r e s s i o nm o d e l i sa l s op r o v e d 诎i n gt h e a d v a i l t a g e so fl s s v ma i l dp s v m ，a n e wm o d e lc a l l e dd c ts u p p o r tv e c t o rm a c l l i n e ( d s v m ) i sp r o p o s e d 1 1 1 en e wm o d e lc 孤b eu s e db o t l li nc l a s s i f i c a t i o n 觚dr e g r e s s i o n p r o b l e m s ，b u tb em u l hs i m p l e ra r l dh 嬲f 瓠t e r 仃a i l 】l i i l gs p e e da n dm g h e rg e n e r a l i z a t i o n a b i l i 够c o m p a r e dt 0l s s v m ，i te n h a n c e st 1 1 ec o i e x i 够o ft l l ep r o b l e m ，毋l a r a n t e e st 0 g e tt l l eg l o b a jo p t i i i l 呦；c o m p a r e dt 0p s v m ，i to v e r c o m e st h ed i s a d v a i l t a g eo f d i a 色r e n c e so fl i i l e a r 锄dn o i l l i n e 盯c 弱e s ，a n di sl l i g h e rh lt e s t i n gs p e e d i i lt h ee n d ， c o m p r e h e n s i v em m e r i c a le x p e r i m e n t ss h o w l ef e 嬲i b i l i t ) ，a n d 缸r e c t i v i 够o fa l lt l l e s e r e s e a r c b e sa _ b o v e 3 as t u d y0 n 丘亿z ) rs v m ( f s v m ) f i r s t l y m ee q u i v a l e n c eo ff s v ma n ds v m 谢mm u l t i p l e p e n a l t ) r f 砬t o r si s p r 0 v e dt l l e o r e t i c a l l y ，w k c h i st h e 吐i e o l i e t i c a l f o u n d a t i o no fs e n i n gt h em z z ) rm e m b e r s l l i pa d 印t i v e l y 嬲h ) ，p e 印猢e t e r so fm o d e l s 几类支持向量机变型算法的研究 s e c o n d l y ，嬲t l l es 仃a t e g yo fp r e - s e t t i n gt l l em z z ) ，m e m b e r s l l i p ，帆od e s i g l l i r 唱w a y sa r e g i v e i l ，b a s e do nt l l eg e o m e t r i c a ld i s 仃i b u t i o no fc l 雒s i f i c a t i o nh y p e 印l 锄l ea i 】l d d a t a s a l p l e sa i l dt l l en a n 鹏o fc l a s s i f i c a t i o no fs v m ，r e s p e c t i v e l y n 吼l ei 岫e r i c a l e x p e r i m e n t sa r ed o n et 0s h o wn l ee f f e c t i v e n e s so f l e s e 铆om 础o d s ，嬲w e l l 觞 c o m p a r i s o n s 、析t 1 1o t l l e rm e t l l o d sa v a i l a b i e 4 e v a l 啪血1 9m ep e r f o m a i l c eo ff 2 s v m 、i t l ll 2l o s s 胁“o n ( l 2 f s v m ) f i r s t l y ，t l l em o d e lo fl 2 f s v mi sg i v e l l ，a n dt h e ni ti s 位m s f o 册e de q u i v a l e n t l ya sh a r d m a r g i ns v m 、析t han e wk e m e ln m c t i o n ，i i lw m c ht 1 1 en 】z 2 m e m b e r s h i p s 锄er e s t a t e d 硒k e m e lp a r a m e t e r s s e c o n d l y ，f o u rm e t l l o d so fe s t i m a t i i l gt l l eg e n e r a l i z a t i o ne r r o ro f h a r ds v ma r ee x t e n d e dt ob ea p p l i e di i lt h a to fl 2 f s v m i i lt l l ee n d ，v i ac o m p a r a t i v e 锄a l y s i sa n do v e r a l ln 岫e r i c a le x p e r i m e n t s ，t l l eb e s te s t i m a t i o no fg e n e r a t i o ne r r o ro f l 2 - f s v mi sc o n c l u d e d 、) l 柚c hc a nb eu s e d 硒ac r i t 嘶o no fm o d e ls e l e c t i o n 5 r e s e a r c ho nt l ：屺m o d e ls e l e c t i o nm e t l l o do fd u a l 一p e n a j 够- f a c t o rs v m 谢t hl 2 l o s s 劬c t i o na 1 1 di t s 印p l i c a t i o n s i n c e 圮i i i l b a l 勰c eo f b i n a r yc l 嬲so fd a t ai i lt l l e d i g i t a lm a m m o g r a p h y ，s v m 谢ml 2l o s s 劬c t i o n 锄dd i 虢r e n tp e n 址t ) ，t o r sa r e u s e d t h e i l ，a c c o r d i l l gt ot h ep r e v i o u sr e s e a r c hr e s u l t s ，o n em e t l l o do fd e t e m i l l i n g 廿1 e s eh y p e 印a r a m e t e r sa u t o m a t i c a l l yi sp r e s e n t e d ，v i am i l l i i i l i z i n gn l eg e n e r a l i z a t i o n e r r o rb o u n d b y l ee x p e r i m e n t so fd e t e c t i o no fm 髂sa i l d 面c m c a l c i f i c a t i o l l si nt 1 1 e d i g i t a lm 锄m o 伊印h y ，m ee 虢c t i v e n e s so ft h ep r o p o s e dm e t l l o di sd e m o i l s t r a t e d i ti s c o n c l u d e dt 1 1 a tt h i sm 砒o do u t p e r f o m so t h e rs e t t i i 玛w a y so fh y p e 叩踟e t e r si nt e m s o fg e n e r a l i z a t i o na b i l i 够 k 嚼w o r d s ：s t a t i s t i c a l l e a m i n g 也qs u p p o r tv e c t o rm a c h i n e m i n i m u m s q u a 聆e r m rc h o l e s 晦d o m p 鸺i 黼 k i e m e lf u n c t i o n f u z 巧m 锄b e 璐h i p 缸n c t i o nm o d e ls e l e c t i o nb f g sq u 嬲i - n 删t o nm e t h o dm a 姻 d e t e c t i o n 】i c i d c a l c 墒c a t i o n sd e t e c t i o n 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容外，论文中不包 含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期塑! ! ：弓：! 里 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名：生兰垫 导师签名：到三罕旦 日期塑! ：三： 呈 日期捌里：主：翌一一 第一章绪论 第一章绪论 本章首先阐明了所选课题的背景和意义，给出研究工作的宏观定位，然后介 绍了支持向量机的研究现状和所选课题的研究意义，最后对所做工作进行了概述 1 1选题背景和意义 机器学习( m a c l 血l el e 锄i n g ，m l ) 在人工智能( a n i f i c i a l1 1 1 t e l l i g e n c e ，) 的研究 中具有十分重要的地位“如果一个机器不能学习新的事物，获取新的知识，适应 新的环境，这样的机器不能称得上是一个真正的智能机器”1 机器学习是使机器实 现智能的根本途径，其应用遍及人工智能的各个领域，如模式识别、计算机视觉、 专家系统、智能机器人、自动推理、自然语言理解等领域除此之外，机器学习 的方法还被用于大规模数据集的数据挖掘这一领域1 2 】实际上，在任何有经验可以 积累的地方，机器学习方法均可发挥作用机器学习主要使用的推理方法是归纳、 综合而不是演绎，因此不再是只能够证明已存在事实、定理，而是能发现新的定 理、定律和规则等 学习是智能行为的一个非常重要的特征，但至今对学习的机理尚不清楚1 2 j 目 前普遍接受的是h a s i i i l o n 的观点，即学习是系统所作的适应性变化，使得系统在 下一次完成同样或类似的任务时更为有效关于机器学习的具体而精确的定义尚 且没有，因为机器学习这一名词的含义与人工智能一样包含广博的领域知识，甚 至许多是未知的领域但借助于学习的概念，我们可以理解机器学习的研究就是 根据生理学、认知科学等对人类学习机理的了解，建立人类学习过程的计算模型 或认识模型，发展各种学习理论和学习方法，研究通用的学习算法并进行理论上 的分析，建立面向任务的具有特定应用的学习系统这些研究目标相互影响、相 互促进人们把从过去的数据和以往的知识中学习并获取规律的能力称为学习能 力用获得的规律解释已知的实例，而且对未知的现象做出正确的预测和判断的 能力，称为泛化能力( g e n e r a l i z a t i o na b i l i 劝简单地说，我们可以将机器学习理解 为一种优化过程：是对现有知识进行优化，使得提取出来的规律对未来的信息可 以很好地预测 在人工智能的研究中，人们用计算机来模拟这种学习能力的问题常常被称为 基于数据的机器学习问题这里的计算机，指的是电子计算机，但以后还可能是 1 。m a c h i n e sc a n n o tb ec a l l e di n t e l l i g e n tu n t i l t h e ya r ea b l et ol e a mt od on c wt h i n g s 觚dt oa d a p tt on e w s i t u a t i o n s ，r a t h e r t h a ns i m p l yd o i n ga st h e yw e r et o i dt od o ”一一意译自文【l 】中第7 章 2 几类支持向量机变型算法的研究 中子计算机、光子计算机或神经计算机等等基于数据的机器学习的任务就是： 从一组观测数据集出发，得到一些不能通过原理分析而得到的规律，进而利用这 些规律对未来数据或无法观测到的数据进行预测和分析 统计是我们面对数据又缺乏理论模型的最基本的分析手段传统的统计方法 都是参数估计方法【2 捌，在这一方法论中，参数的相关形式是已知的，训练样本用 来估计参数的值，但有很大的局限性首先它需要已知样本的分布知识，这需要 花费很大代价，甚至在现实中是根本无法得到；另外，传统统计学研究的一系列 理论，例如统计学中关于一致性、无偏性和估计方差的界或模式分类问题错分率 的界等结论都是样本数目趋于无穷大时的渐进特性，而实际问题的数据或样本总 是有限的，不满足以上结论的条件，这表现为理论上很优秀的结果在实际问题中 却不尽如人意2 0 世纪后半叶又出现了以人工神经网络( a n i f i c i a ln e u r a ln 娟o r k ， 删为代表的经验非线性方法【3 】，这些方法利用已知样本建立启发式的非线性模 型，克服了传统参数估计方法的困难，有着良好的性能，在很多实际的问题中有 广泛的应用，例如图像识别，语音处理等但这种方法缺乏一种统一的数学理论 而且存在维数灾难( c u r s co fd i i i l e l l s i o n a l i t ) r ) 、局部极小( l o c a lm 越m u m ) 和过拟合 ( o v e r f i n i n g ) 等问题而由vv a p n i k 等人【4 】提出的统计学习理论( s t a t i s t i c a ll e a n l i n g 1 1 1 e o s ，弥补了这些方法的不足，有着良好的理论背景和广泛的实际应用， 成了近年来的研究热点与传统统计学相比，统计学习理论是针对小样本情况下 的机器学习规律，所建立的一套新理论体系，在这种体系下的统计推理规则不仅 考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果 、却1 1 i k 等人从2 0 世纪六、七十年代开始致力于s l t 的研究【5 1 ，到九十年代中期， 随着其理论的不断发展和成剃6 1 ，由于其比砧州等传统方法有着良好的性能，而 备受关注，推动了机器学习理论和技术的发展统计学习理论的一个核心概念就 是v c 维( 、，却f l i k 觚dc h e r v o n e r l l 【i s ) 概念【7 1 ，它是描述函数集或学习机器的复杂性或 者容量( c 印a c 时o f m em a c l l i n e ) 的一个重要指标，在此概念基础上发展出了关于统 计学习的一致性( c o l l s i s t e n c y ) 、收敛速度、泛化能力( g e n e r a j i z a t i o na b i l i t ) r ) 等一系 列的重要结论1 6 ，1 1 】对于s l t 的研究基础则源于6 0 年代的四项研究成果【6 j ： ( a ) t i l l l 【o n o v ，i v 锄o v 和p t l i l l i p s 的关于解决不适定问题的正则化原则； ( b ) p 觚配n ，r o s e n b l 砒和c h e n _ t s o v 的非参数统计学； ( c ) 、，a p i l i k 和c h e r v o n e i 此s 的泛数空间大数定律以及其与学习过程的关系； ( d ) k 0 1 i i l o g o r o v ，s o l o m o n o 卿c h a i 血的算法复杂性理论以及其与归纳推理的 关系 支持向量机( s u p p o r tv e c t o rm a c h i i l e ，s v m ) 是实现s l t 的一个通用机器学习方 第一章绪论 法【8 一，其建立在s l t 的v c 维理论和结构风险最小原理( s 协l 曲l r e 鼬s km i n i m i z a t i o i l s 刚) 基础上，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折 衷，以期获得最好的泛化能力由于其良好的性能而得到了广泛关注，形成近年 来的研究热点【l 睨2 1 s l t 与s v m 虽有着良好的结果，但其仍然处于发展之中，有很多问题亟待解 决例如如何构造预测函数子集的结构到目前仍无一般性理论；对于v c 维只是停 留在理论分析阶段，尚没有通用的计算方法；许多理论目前还只有理论上的意义， 尚不能在实际算法中实现；s v m 中如何自适应地根据具体问题选择适当的核函数； 结构风险最小原理并不能严格保证s v m 具有良好的泛化能力【1 0 1 1 等等 1 2支持向量机的研究现状 s v m 是v | a p m k 等人根据s l t 中结构风险最小化原则提出的与传统方法相比， s v m 有以下几个主要优点 ( 1 ) s v m 是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不 仅仅是样本数趋于无穷大时的最优值这样符合现实中样本数目有限的情况其 最大间隔的要求，克服了过拟合现象，增强学习算法的泛化能力这方面也影响 了学者们使用间隔最大化的思想来设计设计新的学习算法【2 3 瑙】 ( 2 ) s v m 模型最终是转化成为一个凸的二次规划问题，由最优化理论可以保证 其得到的是全局最优点，这解决了在神经网络方法中无法避免的局部极值问题这 一模型引起了最优化理论方面对于大规模二次规划和其他相关算法的研究 【1 4 ，2 7 。2 9 ，5 8 也1 ，以及s v m 变型问题中相应的数学模型的快速求解方面的研究【9 0 。9 6 】 ( 3 ) s v m 使用了核函数( k e m e lf u i l c t i o n ) ，将原问题通过隐形非线性变换转换 到高维的特征空间( f e 砷l r es p a c e ) ，在高维空间中构造线性决策函数来实现原空间 中的非线性决策函数，巧妙地解决了维数问题在s v m 方法中，通过对核函数的 选择，就可实现不同类型的学习算法【9 】对核函数虽然早已有之1 1 6 8 】，砧z e n i l a l l 与 1 9 6 4 年首次引入到机器学习中来【1 6 9 1 ，但未引起广泛关注，而s v m 使其再次备受宠 爱，于是出现了一系列新的核算法核方法是一系列先进非线性数据处理技术的 总称，其共同特征就是这些数据处理方法都使用了核映射从具体的操作过程上 看，核方法首先采用非线性映射将原始数据有数据空间映射到高维特征空间，进 而在特征空间中进行相应的线性操作例如核f c m ( f u z z ) rc m e a n ) p 们，核主成分分析 ( p r i n c i p l ec o m p o n e n ta n a l y s i s ，p c a ) 【3 1 1 ，核l o g i s t i c 回归【3 2 1 ，核独立成分分析 ( i n d e p e n d e nc o m p o n e n t sa n a l y s i s ，i c a ) 吲，核判别分析( d i s c r 眦i i l 锄ta n a l y s i s ) 3 4 1 ， 核岭回归( 础d g er e g r e s s i o n ) 【3 5 娜】以及核偏最小二乘回归( p a r t i a ll e a s ts q u a r e 4 几类支持向量机变型算法的研究 r e g r e s s i o n ，p l s r ) 【3 7 ，3 8 】等 ( 4 ) s v m 的解具有稀疏性，这使得其决策函数很简单，决策速度快对稀疏性 的研究也早而有之，但s v m 启发了人们对于传统方法寻求稀疏的结果，比如t i p p i n g 于2 0 0 1 年提出的基于b a y e s 学习框架下的相关支持向量机( i 沁v a l e n c ev e c t o r m a h c i n e ，r v m ) f 3 9 】近几年在图像处理中兴起的压缩感知( c o m p r e s ss e n s i n g ) 和用 于信号分析、图像分析中的稀疏表示( s p a r s er e p r e s e n t a t i o n ) 川等方面的研究，可以 说是对事物的描述殊途同归，都基于稀疏性研究，事实上s v m 本身就是对所寻求 函数的一种稀疏逼近【4 2 1 这些优点，不仅使得s v m 拥有广泛的应用，而且引起了一系列的对于传统方 法的类似研究和新方法的创新较好的数学理论框架，以及应用中良好的泛化能 力，使得s v m 在模式分类、回归分析和密度函数估计等机器学习问题中有非常好 的效果，引起了大家对s v m 的模型算法研究以及在现实中广泛应用的研究热潮 1 2 1算法研究 机器学习可以分为无监督学习( u n s u p e r v i s e dl e a n l i n g ) ，半监督学习 ( s e i i l i s u p e i s e dl e a r n j n g ) 和监督学习( s u p e r v i s e dl e a n l i n g ) o2 。s v m 最初是针对二 分类问题的监督学习提出来【8 】，后来被推广到回归和多分类，故很多s v m 变型算 法的研究思路大都是从二分类问题开始但s 订在无监督学习方面也有不少成果， 比较典型的是b e n h u r 等人【4 3 】于2 0 0 1 年将最大间隔思想应用聚类问题中，提出支持 向量聚类( s u p p o r tv e c t o rc l u s t e r i n g ) ，后续也有不少工作m 。5 0 】对于半监督学习的 s v m 模型，最早由b e 皿e t t 等人【”j 于1 9 9 9 年提出，而近几年尤其成为了一个非常热 门的课题【5 2 巧9 】，出现了不少关于s v m 及其变型的半监督模型及求解方法相比之 下，目前最多的、主要的研究成果还是在监督学习方面 s v m 的数学模型是一个凸二次规划，而如何实现快速求解，尤其是对于大规 模问题，目前国内外已有很多学者提出了多种算法典型的算法有：最早的有b o s e r 、 g u y o n 和、却l l i k 【5 8 j 提出的块算法( c h 曲l ( i n ga l g o r i t h m ) ，有效地减少了空间复杂度， 但支持向量个数比较多时，优势并不明显后来出现了由o s u i l a 等人【”】提出的分解 算法( d e c o m p o s i t i o na 1 9 0 r i t h m ) ，进一步降低了空间复杂度，但分解算法的关键是 如何确定工作集的替换策略，该策略的好坏直接影响算法的收敛速度后来 j o a c l l i m s 等人【6 0 】对替换策略进行了重要改进，并将其应用在软件s v m h g h t 中【6 1 】，l i l l 等人1 6 2 j 关于分解算法的收敛性给出了理论证明；h s u 和l i n 等人【6 3 】对工作集的选取 做了研究并进行数值实验，指出任何工作集的选择都不是最完美的之后p l 甜提出 了序列最小优化算法( s e q u e n t i a lm i n i i i l a lo p t i m i z a t i o n ，s m o ) 6 4 ，6 5 】，该算法不涉及 第一章绪论 5 大规模矩阵的计算，大大降低了空间复杂度k e e m l i 等人脚j 对s m o 算法做了进一 步的改进；c a o 等人【f 7 】给出了并行计算的s m o 方法；此外也有很多关于s m o 方法 的理论性分析【6 8 7 0 1 目前十分流行的l i b s v m 软件正是基于s m o 方法【7 9 1 s m o 方 法降低了空间复杂度，但迭代次数增加了，故还存在着改进的余地最初这一系 列的算法都是针对分类模型提出的，后来很多学者都将它们推广应用到s v m 的回 归模型【7 3 7 7 】和一些s v m 的变型模型1 0 刀另外这些算法都是基于对偶模型提出的， 此外还有许多学者提出了基于原始空间的求解算法【_ 】和一些基于分类几何意义的 算法【7 2 】国内关于算法的研究相对较少，参见文 1 4 ，1 7 2 2 ，8 1 8 2 】上面这些都是 针对s v m 标准模型的求解方面做的研究，关于s v m 模型在使用时适应于不同需求 的其他方面研究也有不少工作 标准s v m 模型提出后不久，在2 0 0 0 年b s c h 6 l k o p f 等人【8 2 j 根据s i t m 原则提出了 n u s v m 模型该模型比s v m 多一个新的参数，以用于有效地控制支持向量的个 数它也可以应用于分类问题和回归问题，学者们从各方面对其进行了研究，例 如文【8 3 】给出了n u s v m 模型的几何意义，文【8 4 】对其核函数进行了相关研究，文 8 5 】 研究了最优参数的选择问题，文 8 6 】提出了模糊的n u s v m 用于回归问题 等n u s v m 与标准s v m 是对同一问题的不同表示，在一定条件下可以转化峭，但 n u s v m 的对偶模型比较复杂，故而关注度不如s v m 高 标准s v m 是针对二分类问题，关于多分类问题的研究，主要思想是将多分类 转化为多个二分类问题，目前比较流行的有“一对多 ，“一对一和“多对多 原则，但这些都需要多次求解s v m 模型，复杂度高而与l o g i s t i c 回归的思想类似， b a y e s 框架下的关联支持向量机( r v m ) 【3 9 】根据概率输出，可同时适应于二类或者多 类r v m 比s v m 更稀疏，因而决策速度更快，但泛化能力稍低一些；而且r v m 可 以自动选择参数，核函数并不一定要求正定，但是其训练速度比s 要慢，随着 样本数的增加而迅速增加s v m 对多类问题的求解策略理论上可行，但实际中不 能推广的问题在于计算复杂度高，并且每次使用二分类s v m 时，参数( 惩罚因子c 和核参数) 应该是不同的，而目前没有一个完全解决的自适应方法来选择参数，也 就是模型选择( m o d e ls e l e c t i o n ) ，这仍然是一个公开的难题 关于s v m 的模型选择，使用最多的还是网格搜索( 嘶ds e a r c h ) ，这种近乎穷尽 搜索的方法，固然不是解决问题的完美答案目前已有不少新进展瞄帕删，比较流 行的方法是将泛化能力上界看成是这些参数的函数，通过求解一个优化问题而得 到模型的参数这种方法首先要求一个能更好地准确的估计出泛化能力的上界， 退一步讲，需要一个能反映随着参数的变化，s v m 的泛化能力所变化的函数然 而很多时候得到的上界不是光滑的，这对最优化求解也形成了挑战【1 4 2 1 4 4 j 模型选 择问题已形成s v m 完全走向实际生产中应用的一个瓶颈，目前的成果只是对问题 6 几类支持向量机变型算法的研究 简化后的解决，并未彻底解决问题 对于s v m 处理一类当数据不断更新或者模型需要更新的在线学习问题【l 洲，目 前也有一些进展【1 8 5 郴引这些处理方法的主要策略就是根据新来的样本，对已有的 模型对偶问题参数( l a 伊a i l g e 乘子) ，根据最优化理论中的互补松弛条件而选择是否 更新，这是因为非支持向量的加入对于决策函数是没有影响目前这些方法虽有 一定的效果，但没有提供一个完全理想的答案对于这一问题还是值得进行深入 探讨研究 对于一个机器学习算法，我们希望它模型简单、速度快和泛化能力强，但这 两方面往往是不可兼得的为了提高标准s v m 的学习速度，除了寻求快速的二次 规划求解方法外，目前已有许多对模型简化简化变型的算法；而为了提高其泛化 能力，也有不少方法通过对标准s v m 进行模型变型来研究 ( 1 ) 基于线性规划的支持向量机由于线性规划求解要比二次规划简单嗍， z h o u 等人【黯】根据有限维线性赋泛空间中泛数的等价性，提出了线性规划的支持向 量分类机( l p s v m ) 该模型只需求解一个线性规划，加快了训练速度；由于对v c 维的上界进行了松弛，故而在泛化能力上比传统s v m 稍弱一些此外t 0 r i i 给出了 一种快速求解算法【跏 ( 2 ) 二次损失函数的支持向量分类机标准s v m 是基于一次损失函数的，而有 学者对二次损失函数的支持向量分类机进行了研究二次损失函数的s v m 的具有 更简单的二次规划对偶形式，方便求解，且二者的泛化能力基本相卦9 1 】另外通 过合适的核函数变化技巧，可以将不可分的模型转化为标准可分s v m 的模型，故 而可以使用一些用于可分问题的s v m 模型求解算法来求解不可分问题，如f r 觚c 等 人【9 2 】将原用于可分问题的s k 算法用于求解不可分问题，取得了满意的效果但不 足的是二次损失函数的解在稀疏性方面比一次损失函数的差一些，也就是支持向 量个数相对较多【9 l 】二次损失函数支持向量机对于不均衡数据时，分类准确率随 不均衡度的增加而急剧下降，关于这点，本文在第六章做了相关研究关于二次 损失函数的s v m 模型相关研究，还有不少成果p 3 。1 0 1 1 ( 3 ) 无约束支持向量机算法将约束条件等价地带入到s v m 模型的目标函数中 而使得求解模型变为无约束问题，但此时s v m 模型是非光滑的，不易求解l e e 和m 趾g 舔a r i 趾等人【眦】引入s i 舯o i d 光滑函数取代原模型中的不可微项，提出了光 滑支持向量机( s s v m ) 之外有很多学者将一些新的光滑函数被引入，进行研究， 例如袁玉波等人【1 0 3 1 使用分段光滑函数，熊金志等人【1 0 4 1 使用了插值函数的方法，吴 青等人【1 0 5 1 使用了熵函数l e e 等学者【1 响还将光滑化技巧应用到回归问题中，提出 了光滑的s v r 模型为了增加无约束规划的光滑性，这方面的研究经常使用的是 二次损失函数 第一章绪论7 ( 4 ) 最小二乘支持向量机( 1 e a s ts q u a r es u p p o r tv e c t l wm a c l l i n e ，l s s v m ) 通过将 标准s v m 模型的一次损失函数改为二次损失函数，并将不等式约束变为等式约束， 以s u y k e i l s 为代表的研究团队【1 叫提出了用于分类的最小二乘支持向量机，并出版了 专著【12 6 1 和开发了m a t l a b 软件包【1 2 7 1 l s s v m 只需通过求解一个方程组得到问题的 解，避免了求解二次规划而大大降低计算复杂度，而且l s s v m 的泛化能力与s v m 相比下降并不是很多1 1 3 1 ：s u y k e i l s 等人【1 2 5 1 将其在