（运筹学与控制论专业论文）支持向量机研究及其应用.pdf

电子科技大学顺= l 学位论文 支持向量机研究及其应用 摘要 支持向量机( s v m ) 是九十年代中期发展起来的新的机器学习技术，与 传统的神经网络( n n ) 技术不同，s v m 是以统计学习理论( s l t ) 为基础， n n 是以传统统计学理论为基础。传统统计学的前提条件是要有足够多 的样本，而统计学习理论是着重研究小样本条件下的统计规律和学习方 法的，它为机器学习问题建立了一个很好的理论框架。实践表明，建立 在( s l t ) 之上支持向量机不仅结构简单，而且技术性能尤其是推广能力明 显提高，能够解决好大量现实中的小样本学习问题，它是一个全新的神 经网络技术。目前，s v m 己成为国际上机器学习领域新的研究热点。本 文首次深入系统地对支持向量机( s v m ) 进行了研究讨论。 论文的主要贡献可归纳如下： 首先，第一章简要介绍了由于传统神经网络的发展和它在机器学习 上的缺陷，导致支持向量机的诞生：并提出了研究和应用支持向量机的 必要性和重要性以及现有支持向量机的研究成果和存在的不足。第二章 探讨了支持向量机理论基础一一学习问题，尤其是对v a p n i k 等人的统计 学习理论( s l t ) 结合学习问题作了系统的阐述。 其次，第三章从模式识别中引出最优分类超平面，然后按训练集线 性可分和线性不可分讨论，运用最优化理论中的拉格朗日乘子法( l m t ) 推导出相对应地最优超平面和判别函数( 决策函数) ；最后通过统计学习 理论和泛函分析理论推导出支持向量机。 再次，为了进一步提高支持向量机的通用性以及推广能力、应用能 力、识别速度等性能，在第四、第五两章运用模糊集理论( f s t ) 币h 粗糙集 理论( r s t ) 对支持向量机进行研究，采用优势互补原则，先是把模糊集与 支持向量机有机结合，构造出基于模糊集的支持向量机( f s s v m ) ，然 后把粗糙集理论与支持向量机相互结合，进而把r s t 与f s s v m 相互结 合，构造出基于r s t 的支持向量机。很好地推广了s v m 的技术性能。 最后，在第六章中，把第三章s v m 核函数的思想和第四章简化 f s s v m 的思想运用到回归分析( 函数拟合) 、主成分分析( p c a ) 中，提 高了二者的分析、处理数据的能力，简化了处理过程。 关键词：支持向量机，神经网络，机器学习，模式识别，模糊集理 论，粗糙集理论，主成分分析，回归分析 i i 1 1 王子科技大学碳士学位论文 t h es t u d ya n d a p p l i c a t i o no fs u p p o r t v e c t o rm a c h i n e s 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 eo r s v mi sn e wm a c h i n el e a r n i n gt e c h n i q u e d e v e l o p e df r o mt h em i d d l eo f19 9 0 s b e i n gd i f f e r e n tf r o mt r a d i t i o n a ln e u r a l n e t w o r ko rn n ，n ni sb a s e do nt r a d i t i o n a ls t a t i s t i c s ，w h i c hp r o v i d e s c o n c l u s i o no n l yf o rt h es i t u a t i o nw h e r es a m p l es i z ei s t e n d i n gt oi n f i n i t y ， w h i l es v misb a s e do ns t a t i s t i c a l l e a r n i n gt h e o r y o rs l t , w h i c hi sa s i n a i l - s a m p l e s t a t i s t i c sa n dc o n c e r n sm a i n l yt h es t a t i s t i c p r i n c i p l e sw h e n s a m p l e a r e l i m i t e d ，e s p e c i a l l y t h e p r o p e r t i e s o fl e a r n i n g p r o c e d u r e s l t p r o v i d e s u san e wf r a m e w o r kf o rt h eg e n e r a ll e a r n i n gp r o b l e m al a r g e n u m b e ro fe x p e r i m e n t sh a v es h o w nt h a ts v mh a sn o to n l ys i m p l es t r u c t u r e ， b u ta l s ob e t t e rp e r f o r m a n c e s ，e s p e c i a l l yb e t t e rg e n e r a l i z a t i o na b i l i t y s v m c a ns o l v es m a l l s a m p l el e a r n i n gp r o b l e mb e t t e r ，a n di ti sac o m p l e t e l yn e w n e u r a ln e t w o r kt e c h n i q u e c u r r e n t l y ，s v mi s b e c o m i n gan e w h o ta r e ai n t h ef i e l do fm a c h i n el e a r n i n gi nt h ew o r l d t h i sp a p e rh a st h ef i r s tt i m e s s y s t e m a t i c a l l ys t u d i e ds v md e e p t h em a i nc o n t r i b u t i o no ft h ed i s s e r t a t i o nc a nb es u m m a r i z e da s f 0 1 l o w s ： f i r s t l y ，c h a p t e r 1h a si n t r o d u c e dt h ef a c tt h a tn a i s s a n c eo fs v m b e c a u s eo ft h ed e v e l o p m e n tn na n ds o m es h o r t a g e so ft h ec u r r e n ts v m a n dw eh a v eb r o u g h tf o r w a r ds o m es h o r t a g e so ft h ec u r r e n ts v m c h a p t e r 2h a ss y s t e m a t i c a l l yd i s c u s s e dm a c h i n e l e a r n i n gp r o b l e m ，w h i c hi st h eb a s i c o fs v m ，w i t hs t a t i s t i c a ll e a r n i n gt h e o r yo rs l t s e c o n d l y ，c h a p t e r3 h a se d u c e dt h eo p t i m a l h y p e r p l a n ef r o mp a t t e r n r e c o g n i t i o n a c c o r d i n g t ot h ed i f f e r e n t s a m p l es e t ，w e h a v e b e e no n d i s c u s s i o n ，u s i n gl a g r a n g i a nm u l t i p l i e rt e c h n i q u eo rl m t i nt h eo p t i m a l t h e o r y ，s l ta n df u n c t i o na n a l y s i s ，t h e nw eg e tt h ed e c i s i o nf u n c t i o na n d s v mw i t ht h ec o r r e s p o n d i n gd i f f e r e n ts a m p l es e t t h i r d l y ，f o ri m p r o v i n gg e n e r a l i z a t i o na b i l i t y ，a p p l i c a t i o na b i l i t y a n d r e c o g n i t i o ns p e e d o fs v m ，w eh a v eu s e d f u z z y s e tt h e o r y ( f s t ) a n d r o u g hs e tt h e o r y t o s t u d ys v md e e p ，a n di n t e g r a t e dt h e mi n t os v m ， c o n s t r u c t e df s s v m ( f u z z ys e ts v m ) a n ds v mb a s e do nr o u g hs e tt h e o r y ， a n de x t e n d e dp e r f o r m a n c e so fs v mi nt h ec h a p t e r4 ，5 f i n a l l y ，c h a p t e r6i s t w oa p p l i c a t i o n so ni d e aa n da p p r o a c ho fs v m o n ei s r e g r e s s i o na n a l y s i s ，t h e o t h e ri s p c a ( p r i n c i p a lc o m p o n e n t s a n a l y s i s ) w eh a v ei m p r o v e dt h e i ra b i l i t yo fa n g l i c i z i n ga n dd e a l i n gw i t h d a t a ，a n ds i m p l i f i e dp r o c e d u r eo fp r o c e s s i n gt h e m k e yw o r d s ：s u p p o r t v e c t o rm a c h i n e ，n e u r a ln e t w o r k ，m a c h i n el e a r n i n g ， p a t t e r nr e c o g n i t i o n ，f u z z y s e t t h e o r y ，r o u g hs e tt h e o r y , p c a ，r e g r e s s i o n a n a l y s i s i l l 屯子科技大学颂十学位论文 独创性声明 本人声明所。一交的学位论文是在导师指导f 进行的研究l ：作及取得的研究成 果。据我所知，除了文中特别加以标注平致谢的地方外，论文中不包括其他人已 经发表或撰写过的研究成果，也不包含为获得电子科技火学或其他教育机构的学 位或证1 5 而使州过的材料。与我一同j ：作的同志对研究所作的贡献均已在论文中 作了明确的说明并表示谢意。 签名：日期：年月日 关于论文使用授权的说明 本学位论文的作者完全了解电子科技大学有保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 签名导师签名 日期：年月日 l 乜子科技大学硕士学位论文 第一章概论 1 t 引言 人类在很多方面都已成功地采用机器来完成繁重的体力工作，人们也从来没 有放弃让机器具有人类思维能力的努力。计算机的诞生和发展，使这种梦想有了 成为现实的可能。特别是人工智能技术的发现，使得人们又向思维机器的研究方 向迈进了一大步。 人工智能自1 9 5 6 年问世以来，已经取得了引人瞩目的成就，形成了专家系 统、机器学习、智能决策支持系统、人工神经网络等诸多研究和应用领域。尤其 是人工神经网络，自1 9 8 2 年，美国加州理工学院物理学家j j h o p f i e l d 提出 h o p f i e l d 网络模型【3 4 】和1 9 8 6 年r u m e l h a r t 等人提出b p 学习算法 3 5 以来，人工 神经网络取得前所未有的好局面，进入了快速发展时期，一度成为人工智能中最 为活跃的分支之一。 然而，从b p 算法产生到1 9 9 5 年( v a p n i kv 提出支持向量机 1 5 】之前) ，这十 年间，虽然人工神经网络在许多领域，如自组织映射，反馈网络等方面取得很重 要的成果 3 6 - 3 8 。 但是，由于传统的人工神经网络是以传统的统计学作为重要理论基础，而传 统的统计学研究的是样本数目趋于无穷大的渐近理论，传统神经网络的学习方法 也多是基于此假设。可是，在实际问题中，样本数目往往是有限的；因此传统人 工神经网络在机器学习上，尤其是在一般学习理论上缺乏实质性进展。 直到1 9 9 5 年v a p n i kv 等人运用统计学习理论对神经网络进行研究，创立了 一种全新的通用学习方法支持向量机( s v m ) 。与传统统计学相比，统计学 习理论是一种专门研究小样本( 样本数有限) 条件下机器学习规律的理论。支持 向量机从根本上解决了神经网络无法解决的网络( 学习机) 小样本条件下的机器 学习问题。随着其理论的不断发展和成熟，现在已基本成为继传统神经网络、模 式识别之后国际上新的研究热点 1 7 - 2 3 】。有力地推动了机器学习理论和技术的发 展，推动了人工神经网络技术的发展，推动了人工智能技术的发展。 然而，比较遗憾的是，在国内，关于支持向量机的研究较少，只有少部分学 者认识到这个重要的研究方向。目前，国内对这方面的研究还刚刚起步。 本论文作者在对现有的支持向量机研究中发现： ( 1 ) 支持向量机方法虽然在理论上具有较为突出的优势，但应用研究却比较 滞后。 ( 2 ) 支持向量机所能解决的只是训练集是普通集合( 精确集) 的情形，但 对含有模糊成员的、不精确的样本就不适用了。 ( 3 ) 支持向量机虽然比神经网络识别的成功率高，但识别速度不如传统的神 经网络。 针对上述问题本文用全新的方法对s v m 作了较为细致地研究，对s v m 方法 电子科技大学硕：l ：学位论文 的应用作了较为深入的讨论，推广了s v m 应用和研究范围。 1 2本文所作的工作及创新之处 在导师钟守铭教授的悉心指导下，作者在攻读硕士研究生期刚开展了如下工 作： 1 ) 在深入研究神经网络理论和统计学习理论，尤其是支持向量机( s v m ) 理论的基础上，在前期研究者们的研究成果之上，对s v m 作了某些改进工作。 目的主要是提高s v m 识别速度、适用范围( 通用性) 、控制力和推广能力。这时 本文主体方向。 2 ) 模糊集理论( 模糊数学) 和粗糙集理论( r s t ) 作为数学的两大分支，分 别于1 9 6 5 年和1 9 8 2 年建立。前者曾为模糊电气技术、模糊智能系统等领域立下 过汗马功劳；而后者由于它在数据挖掘、决策支持与分析、机器学习等方面的成 功应用，近年来它成为国际上的大研究热点。本文首次创造性把这两个理论与 支持向量机理论相互结合起来，推广了s v m ，并取取得了良好的结果。( 参见第 四、五章) 3 ) 本文研究所运用的另两个理论基础是最优化理论和模式识别。用前一个理 论中的拉格朗日乘子法( l m t ) 对支持向量机作了较为深入的研究讨论；后一理 论中的决策规则用于基于模糊集支持向量机算法和s v m 与r s t 相结合的系统 中，简化和加快了算法和系统的实现。( 参见第三、四、五章) 4 ) 主成分分析( p c a ) 和回归分析是应用极广的两个分析数据的方法。本文 成功地把改进的s v m 和s v m 的思想运用到主成分分析( p c a ) 和回归分析之中， 提高了主成分分析( p c a ) 和回归分析的处理数据的能力，简化了处理过程。( 参 见第六章) 支持向量机是一个极其有用技术，且目前的研究方兴末艾，我们国家才刚刚 起步。本文在结束语中，谈到当前s v m 有待解决一些问题，意在唤起国内学者 对此方向的关注。 电子科技大学硕士学位论文 第二章学习问题的探讨 学习问题是人工智能( a i ) 、神经网络( n n ) 最为重要的基础和内容，也是s v m 最为重要的理论基础。为后面讨论的需要，本章将对此进行讨论。 学习的目的是通过对有限个训练样本的学习找到、发现隐含在训练样本背后 的规律( 如函数形式等) ，通过学习解决问题是神经网络的重要特点。学习方法 有三种：监督学习非监督学习再励学习。 ( 1 ) 监督学习。这种学习方式外界环境存在训练器“教师”，他可对一组给 定输入提供应有的输出结果。这组已知的输入一输出数据对称为训练样本集。学 习系统( 如n n ) 可根据已知输出与实际输出之间的差值( 误差信号) 来调节系统 参数。 ( 2 ) 非监督学习。这种学习方式不存在外部“教师”，学习系统完全按照环 境能提供数据的某些统计规律来调节自身参数或结构( 这是一种自组织过程) 。 ( 3 ) 再励学习( 强化学习) 。这种学习介于上述两种情况之间，外部环境对 系统输出结果只给出评价而不是给出正确结果，学习系统通过强化那些受奖励的 动作来改善自身性能。 本文所讨论的学习是监督学习。 2 1 学习模型 我们用下列三个部分来描述监督学习模型： ( 1 ) 产生器( g ) ( 又称环境) 。它是被学习的对象，产生随机向量x r ”，它 们是从固定但未知的概率分布函数f ( x ) 中独立抽取的。 ( 2 ) 训练器( s ) ( 又称教师) 。它本身存储了有关环境的知识，因而可对每一 输入x 返回一个( 应有) 输出值y ，产生输出的根据同样是来自未知条件分布函数 f ( y l x ) 。 ( 3 ) 学习机( l m ) ( 算法，网络) 。它可实现一组输入输出映射： y = f ( x ，a ) ，口a 其中y 是由学习机产生的实际输出，a 是一组自由参数集合 ( 如权值，阀值等) 。如下图所示：( 图1 ) ( 图1 ) 电子科教大学硕士学位论文 根据这个模型，在学习过程中，观察数据对( x ，y ) ( 训练集) 在训练之后，学 - j 机l m 必须对任意输入x 给出输出y 。学习的目标是能够给出输出y ，使之最佳 接近训练器( s ) 的响应( 应有的输出) y 。也就是说，学习问题就是在一组给定函 数集( 某固定结构的网络) 中选择出能最佳逼近训练器的响应y 的函数歹= f ( x ，口) ( 如通过调节权值) 。这种选择是基于训练集的。训练集由根据联合分布函数 f ( x ，y ) = f ( x ) f ( y i x ) 抽取出的，个独立分布的观测值： 组成的。 对上述模型，我们提出如下问题：给出的训练样本中是否包含足够的信息， 使学习后的学习机具有良好的推广能力? 回答该问题要用到v a p i n k 与 c h e r v o n e m k o 的经验风险最小化理论 1 5 ，1 9 。 2 2 经验最小原则( e m p i r i c a l r i s k m i n i m i z a t i o n ) ( e r m 原则) 令l ( y ，f ( x ，w ) ) 表示某输入x 的应有输出y 与实际输出歹= f ( x ，w ) 之间的损 失或差异，称为损失函数。 一种常用的损失函数定义为：l ( y ，f ( x ，w ) ) = ( y f ( x ，w ) ) 2 损失函数的期望值称为期望风险( r i s k ) 。则期望风险为： r ( w ) = i l ( y ，厂( z ，w ) a f ( x ，y ) 其中：f ( x ，y ) 为x 与y 的联合分布。 学习的目的是在函数类f ( x ，w ) ( w w ) 中寻找是r ( w ) 值最小的函数，实 际上就是确定w 的值。由于联合分布，( x ，y ) = f ( y l x ) f ( x ) 为未知，所以很难计算 期望风险r ( w ) 。 我们唯一的信息来源是训练集( x ，y ，) ，所以要构造经验风险函数： 1 ， r 。( w ) = 工( m ，f ( x iw ) ) i = 1 它就不需知道f ( z ，y ) 。用胄。，( w ) 代替真正的风险只( ”，令w 钿和，( z ，w ，) 分 别为使r 。( w ) 达到最小的权值和相应的响应，w 0 和厂( x ，w 0 ) 分别为使r ( w ) 值达 4 电子科披人学硕1 ：学位论文 到最小的权值和相应的响应。”，和w o 都属于权空间w ，我们要研究在什么条件 下近似解厂( x ，h ，) 接近于希望的解厂( x ) 。对于某一固定的权值_ h ，+ ，风险函 数确定了随机变量z 。= l ( y ，( x ，w + ) ) 的数学期望，而经验风险函数r 。( w ) 则 是随机变量z 。的均值。 根据概率理论，在一般情况下，训练样本数，趋于无穷大时均值收敛于期望 值，但应注意，仅仅由于z 。的均值趋于它的期望还不能得出使经验风险r 。( w ) 最小的毗。，同时也会使月( w ) 最小这个结论。如下图所示( 图2 ) 。 差 为了得到上述结论则需要更强的条件，即经验风险最小化原理。 经验风险最小化原理可简述如下：令k 。，表示使经验风险月。( w ) 最小化的 权值，则在经验风险r 。( w ) 一致收敛于实际风险r ( 们的条件下，r ( w 0 。) 依概率 r。1 收敛于实际风险r ( w ) 的最小值。即：p s u p 陋( w ) - r 。( w ) i 占 一0 也就是说： l 。 j 当样本趋于无穷时，使经验风险最小化毗。的对应的期望风险，也差不多是最小 的。这就是e r m 原则。 然而，用e r m 原则的经验风险最小化代替实际风险最小化并没有经过充分的 理论论证，只是直观上合理的想当然做法，而这种思想却在多年的机器学习方法 研究中占据了主要地位。人们多年来将大部分注意力集中到如何更好地最小化经 验风险上。而且在实际问题中，很多问题中的样本数目也离无穷大相去甚远。那 么在有限样本下e r m 原则得到的结果能使真实风险也较小吗? 显然不能。e r m 不 成功的一例子就是神经网络的“过学习问题”在五( w ) 接近最小时，也就 电子科技大学硕：卜学位论文 是训练误差接近最小时，并不总能导致好的预测结果，某些情况下，训练误差过 小反而会导致推广能力下降，即真实风险的增加。 之所以出现过学习现象，一是因为样本不充分，二是学习机设计t 不合理。这 两个问题是互相关联的。由此产生了通过改进网络结构( 学习机结构) 来改善学 习方法的原则：结构风险最小原则( s r m 原则) 2 3 结构风险最小化原$ 1 ( s t r u c t u r a lr i s km i n i m i z a t i o n l ( s r m 原则) 如前所述，e r m 原则是建立在大样本数的问题基础之上的，而实际情况往往 是样本数有限，如果还是利用e r m 原则对学习机进行研究和运用的话，势必会造 成巨大误差甚至错误，那么是否存在一种理论是建立小样本( 数目) 之上的昵? 这就是“统计学习理论”。统计学习理论是研究小样本统计估计和预测的理论 1 9 。本文只是提到它的核心内容： 1 ) 经验风险最小化原则下统计学习一致性的条件。 2 ) 在这些条件下关于统计学习方法推广的结论 3 ) 在这些界的基础上建立的小样本归纳推理原则 4 ) 实现新的原则的实际方法。 其中，最有指导性的理论结果是推广性的界，紧密相关的一核心概念是v c 维。 1 v c 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有 关函数集学习性能的指标，其中最重要的是v c 维。v c 维直观的定义是：对一个 指示函数集，如果存在h 个样本能够被函数集中的函数按所有可能的2 “种形式分 开，则称函数集能够把h 个样本打散，函数集v c 维就是它能打散的最大样本数 目h 。 用数学描述为：假定空间r ”中有h 个样本( 工，y ) ，x r n , y - 1 ，1 ) ，f 是 r “寸 - 1 ，1 ) 的某种函数集，办( s ) 表示由厂，对s 产生的不同二分割数，且 d ，? ( ) = m a x d ，? ( s ) ，其中：s ( s r ”) 是所有样本数为h 的集合。 若d ，( 厅) 能实现s 中所有2 6 个可能的二分割，即砟( ) = 2 “时，则称s 可被f 细分，函数集f 的v c 维定义为能被f 细分s 的最大元素数。也就是能使出( ) = 2 的最大h 值。 例如：对实轴r ，f 是所有区间( 开或闭) 的集合。对于含任意两个点五，x ：e r 的集合s ，可以找到f 中的区间z ，五，五和五，使得所以n s = 五) ， 以n s = x ： ，工f l s = ，af l s = s 是被f 所细分的。然而，若 6 电子科技大学硕士学位论文 s = x 1 ，x 2 ，x ，且一x 2 x 3 ) ，由于没有一个区间f f 能够包含x 1 和而，而不包 含x ，故s 不能被细分。所以f 的v c 维数为2 。 再如，在空间中，f 是n 维平面所划分的半空间的集合，可以证明超平面所 能细分的样本数最多为n + l ，故半空间f 的v c 维数为n + 1 v c 维反映了函数集的学习能力，v c 维越大则学习机越复杂( 容量越大) 。遗 憾的是，目前尚没有计算函数集v c 的通用表达式。对神经网络( 函数集) v c 维 数的求解就更加困难了，通常只能给出它的界。( 如何计算其v c 维是当前统计学 习理论中有待研究的一个问题 2 8 ) 2 推广性的界 对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界 1 9 ，关于两类分类问题，结论是：对指示函数集中的所有函数( 包括使经验风 险最小的函数) ，经验风险月( w ) 和实际风险月( w ) 之间以至少l 一叩的概率满足如 下关系 2 0 ： r ( w ) r ( w ) + jh ( 1 n ( 2 l h ) 1 ) - i n ( r 4 ) 其中，h 是函数集的v c 维，是样本数。 这一结论从理论上说明了学习机的实际风险是由两部分组成的：一是经验风 险( 训练误差) ，另一部分称作置信范围，它和学习机v c 维及训练样本数有关。 可以简单地表示为： 尺( w ) r 。，( w ) + 中( 彳) 它表明在有限训练样本下，学习机的v c 维越高，则置信范围越大，导致真 实风险与经验风险之间可能的差别越大。这就为什么出现“过学习现象”的原因， 机器学习过程不但要使经验风险最小，还要使v c 维尽量小以缩小置信范围，才 能取得较小的实际风险，即有较好的推广性。 3 结构风险最小化原则( s r m 原则) 统计学习理论提出新的策略，即把函数集构造为一个函数子集序列，使各个 子集按照v c 维的大小排列，在每个子集中寻找最小经验风险，在子集间折衷考 虑经验风险和置信范围，使实际风险最小。如图3 所示，这种思想就称作为结构 风险最小化。( s r m 原则) 电子科技大学颂士学位论文 风险欠学习过学习 函数集子集：s lc s 2 c 瓯，v c 维：h l h 2 0 对应的向量x ，起作用，我们称x ，为支持向量( s v ) 。于 是，最优超平面方程为： 采用判别函数 q g ，x ) + 6 = 0 胂弘防m 6 ( 7 ) ( 8 ) 一般来说，实际问题中支持向量仅占训练样本的一小部分( 如图3 1 所示虚 直线上实心圆和三角形) ，这样( 8 ) 中加的项数就很少了。 电子科技大学碳士学位论文 o 3 2 线性不可分情形 若训练集是线性不可分的，或事先不知道它是否线性可分，引入非负变量 鲁0 ( i = 1 , 2 ，) 和函数： 该函数在条件： f ( 善) = 岳 y ， ( w 一) + b 】1 - 4 ，i = 1 ，( 9 ) 用l a g r a n g e 乘子法可以把上述问题转化成其对偶形式 m a x ，) 2 酗一嘉叩崩y 鹏l i o n y ，口= 0 ，c + 0 ( 1 0 ) 电子利技大学硕士学位论文 0 兰a 1 剥于样本线性不可分的情形，为了简化计算，我们可引入广义最优超平面的 概念，它是由下面的优化问题： m i n 去1 1 w , 1 1 2 + c 善 孝，0 得到的权值向量w 决定的。 ( 1 2 ) 这里孝，可看作训练样本关于分离超平面的偏差，茧= o 时问题变为线性可分情 形，c 0 是自定义的惩罚系数，用来控制样本偏差与机器推广能力之间的平衡。 同样地，我们可以用l a g r a n g e 乘子法把( 1 2 ) 式化成其对偶形式： 和 s t m a x 杰一lt a i a j y i y j ( a j c l j y x m a x 一 x i = 1 ， ， y ，口，= 0，0 c ： i = 1 ，2 ， f _ l w = ”x ( 1 3 ) 若a ， o ，则称相应的x 为支持向量( s v ) 。于是，对应最优超平面方程为 其判别函数为 儿g x ) + 6 = o 心e n 融+ 6 ( 1 4 ) 屯子科技大学硕士学位论立 由上可以看出，线性不可分与线性可分基本一样，只是条件有点不同。 3 3 支持向量机 超平面的分类能力毕竟有限，为此引入分离曲面，主要思想是：作非线性映 射o ：r ”- f ，f 是高维内积空间称为特征空间，中( x ) 称为特征映射；然后在 f 中构造最优超平面。 然而，这个思想方法有两个问题： ( 1 ) 特征空间的维数将会很高，在它之上怎样找到一个推广性好的分离超 平面? ( 概念上的问题) ( 2 ) 怎样在计算上处理如此高维的空间? ( 技术上的问题) 例如：要一个2 0 0 维空间中构造一个4 阶多项式，需要构造一个上1 0 亿维 的特征空间。如何克服这种“维数灾难”? 上述概念性问题可以通过构造盯一间隔分类超平面和广义最优超平面来解 决。由定理1 可知，仃值越大的仃一间隔分类超平面集合的v c 维越小，所构造的 超平面将有较高的推广能力。 即便这样，最优超平面有很好的推广性并且理论上也可以找到，但却存在如 何处理高维特征空间的技术问题。这就需要核函数技术。 在上述的问题中，不论是寻优函数( 1 3 ) 还是判别函数( 1 4 ) 都只涉及训练 样本之间的内积运算，这样，在高维空间实际上只需进行内积运算，而这种内积 运算是可以用原空间中的核函数实现，我们甚至没必要知道变换的形式。 根据泛函中h i l b e r t s c h m i d t 理论，核函数k ( x ，x 。) 可以是满足下列m e r c e r 条件的任意对称函数都有： 开成 x ( x ，x ，) = ( 中( x ) 中( x ，) ) 定理2 ( m e r c e r 条件) 要保证r 下的对称函数k ( “，v ) 能以正系数吼 0 展 k ( u ，v ) = 吼也( “) 也( v ) 女= l 4 电子科技大学坝卜学位论文 ( 即k ( u ，v ) 描述了在某特征空间中的内积) 的充要条件是，对使得 f g 2 ) d u 0 这样，只要一种核函数k ( x ，x ，) 满足m e r c e r 条件，它就对应某一特征空间 中的内积，即在最优超平面中采用适当的核函数k ( x ，工，) 就可以实现某一非线性 变换后的线性分类，而计算复杂程度却不会增加。 此时，目标函数( 1 3 ) 变为 和 m a x 圭q 一圭a ，a j y j y j 世( x i ，x j ) j = l i , j = l j r e y ，口，= 0 0 a ，c ；卢1 ，2 ，一j w = y ，口，由( 一) 相应的判别函数( 1 4 ) 变为 y = s g n a ，y ，k ( x ，功+ 6 】 x i e s v 推导过程与前面完全相同，只是把那里的x ，工，分别换成中( 曲，巾( x ) 。 ( 1 5 ) ( 1 6 ) 不难看出为了求分离曲面，不必知道中( x ) 的确切表达式，只要知道如何由输 入x ，_ 计算内积和( x ) o ( x ，) ) 就够了，即 电子科技大学硕= l 学位论文 称对称函数k ( x ，x ，) 为核函数。 ( 中( x ) 中( x ，) ) = k ( x ，x ，) 这个事实对构造支持向量机有重要意义，当特征向量的维数巨大时( 实际情 况常常如此，有时甚至是无穷维) ，若直接计算内积其复杂程度是可想而知的。 因此行不通。上述事实指出：高维特征空间中内积运算，可转化为低维输入空间 ( 相对而言维数要低得多) 上一个简单的函数计算。 定义4 称判别函数y = s g n 口，y ，k ( x ，x ) + 6 】为支持向量机( s u p p o r t v e c t o rm a c h i n e s ) ，简写为：s v m 。 概括的讲，s v m 就是首先通过用内积空间定义的非线性变换把输入空间变换 到一个高维特征空间，在这个空间中求( 广义) 最优超平面。支持向量机分类函 数形式上类似于一个神经网络，其输出是若干中间层节点的线性组合，而每一个 中间层节点对应于输入样本与一个支持向量的内积。( 如图3 2 所示) 在支持向量机中，构造学习机的复杂程度取决于支持向量的数目，而不是特 征空间的维数。下图是s v m 的图解。 k ( x k ( x ，x ) z lx 2z 3 工， ( 图3 2s m m 的实现图解) 电子科技大学硕士学位论文 3 4 s v m 的构造 s v m 由训练集和核函数完全刻画。这样，在实际问题中，常常直接给出核函 数，且采用不同的核函数，我们可以构造实现输入空问中不同类型的非线性决策 面的学习机。所以如何构造、选择核函数是一个重要的问题。下面给出最常用的 三类核函数： 1 ) 多项式核函数： k ( x ，x ，) = 【( x z ) + 1 】” 2 ) 径向基函数( r b f ) ： k ( x ，一) = e x p ( 一i i x 一_ l f 2 ( 2 盯2 ) ) 3 ) s i g m o i d 型核函数： k ( x ，x ，) = s ( u ( x z ，) + c ) 它们分别对应三种类型的学习机：1 ) 多项式学习机器；2 ) 径向基函数学习机器 3 ) 两层神经网络。 为了简便起见，下面的讨论考虑的i j l 练样本是没有错误地分开的情况。 3 4 1 多项式学习机 要构造p 阶多项式决策规则，我们可以用下列函数作为核函数： k ( x ，x ，) = 【( x x ，) + 1 4 这个对称函数满足定理2 的条件( m e r c e r 条件) ，因此它描述了特征空间中 内积的回旋核函数。用前面讨论的技术，我们可以构造如下形式的判别函数： f ( x ，口) = s g n z a ，y ，【( x ，j ) + 1 】9 + 6 ，e 胛 尽管特征空间的维数很高( n 维输入空间中的p 阶多项式有0 0 一) 个自由参 数) ，解决现实的多项式子集的v c 维却可以很低的。 3 4 2 径向基函数机器 传统的径向基函数( r b f ) 机器采用下面的判别函数集： 电予科技大学硕d ：学位论文 ，( z ) = s g n ( 盯一k ( 1 l x - x ， 6 ) ( 1 6 ) ，= i 其中k ，( 1 l x 一一 | ) 依赖于两向量之阳j 的距离l i x - z 川。 要构造( 1 6 ) 式的判别函数，我们需估计 ( 1 ) 参数y 的值；( 2 ) 中心x ，的数目n ( 3 ) 描述各中心的向量_ ；( 4 ) 参数日，的值。 传统的r b f 方法中，前三步是基于启发式知识的，只有第四步是通过最小化风险 泛函确定的。 现在我们把径向基函数选作为s v m 的核函数，在这种情况下，要构造( 1 6 ) 式集 合中的一个函数，常取k ，( 1 l x t 1 1 = e x p ( 一圳x 一一怖，并且它是满足m e r c e r 条件 的。这样，可以确定： ( 1 ) 支持向量的数目n ；( 2 ) 支持向量工 ( 2 ) 展丌式的系数口，只；( 4 ) 核函数的宽度参数，。 3 4 3 两层神经网络 最后，我们选择核函数 k ( x ，x ，) = s ( u ( x z ，) + c ) 定义两层的神经网络，其中s ( x ) 是s i g m o i d 函数。与前两种不同，它们总是 满足m e r c e r 条件。于是我们可以构造实现下述判别函数的s v m ： f ( x ，a ) = s g n ( e , z ，s ( u ( x x ，) + c ) + 6 ) 。 ，= l 利用上面介绍的技术，可以得到下列内容： ( 1 ) 两成器的构造，即确定隐层单元的数目n ( 也就是支持向量的数目) 1 8 1 b 子科技大学硕士学位论文 小结 ( 2 ) 第一层( 隐层) 神经元( 支持向量) 的权值向量w ，= x ( 3 ) 第二层的权值向量a 的值。 本章利用最优化原理尤其是其中的拉格朗同乘子法( l m t ) ，从模式识别角度， 先从训练集可分和不可分讨论了最优分类超平面，然后利用泛函中的核函数推出 s v m ，最后s v m 作了较为深入讨论。 1 9 l 乜子科技大学硕+ 学位论文 4 1 引言 第四章基于模糊集的支持向量机 模糊数学是一门应用极为广泛的数学学科。尤其是近十多年来，它在信息科 学方面立下不朽功勋。模糊智能系统、模糊神经网络等模糊系统纷纷出现。 前面所讲的s v m 是基于普通集合( 训练集) 的学习机器，是一种通用性极强， 推广性很好的神经网络，是解决分类问题强有力的工具和方法。不过这个理论也 有一些美中不足。从前边的讨论可以看出，在s v m 中，每个训练样本都肯定的属 于这类或那类，而且对每类的每个训练点都同等对待处理，没有区分谁重要谁不 重要。也就是说，前面讲的s v m 所能解决的只是训练集是普通集合的情形。 然而，在大量的实际应用中，训练集中的元素不都是清晰的，且各个训练点 的