（电路与系统专业论文）支持向量机及其在癌症诊断中的应用研究[电路与系统专业优秀论文].pdf

摘要 支持向量机( s u p p o nv e c t o rm a c l l i n e s 简称s v m ) 是在统计学习理论的v c 维理论和 结构风险最小化原则的基础上提出的一种新的模式识别技术，它追求的是在有限样本情况 下的最优解而不仅仅是样本数趋于无穷时的最优解。支持向量机具有很好的推，“性能，对 末知样本的预测有较高的准确率，因此得到广泛心用，目前s v m 己成为国际上机器学习 领域的研究热点。 鉴于支持向量机具有良好学习性能和潜在应用价值，本文将其应用于癌症诊断领域。 主要进行了如下工作： 1 、介绍了统计学习理论及支持向量机基本原理。 2 、讨论了几种支持向量机算法：c s v m 、v s v m 、b s v m 和l s s v m 。 3 、通过对训练模型的参数优化方法来构造支持向量机非线性分类器，并将其应用于 癌症病人的诊断，取得了较高的识别率。 4 、根据传统的s v m 算法，提出把对所有训练数据训练得到的主支持向量再次训练， 用得到的次支持向量构造s v m 非线件分类器，将该方法应用在癌症诊断中，取得了比传 统s v m 分类器更高的识别率。 关键词：支持向量机；机器学习；模式识别；统计学习理论 a b s t l a c t s u p p o nv e c t o rm a c h i n ei san e wp a t t e mr e c o 印i t i o nt e c h n o l o g yw h i c hi sb a s e do nv c d i m e n s i o n 也e o r yo fs t a t i s t i c a ll e a m m gt h e o r ya 1 1 d t h ep r i n c i p l eo fs t m c t l l r a lm s k m i n i n l i z a 廿o n s v mc a i lo b t a i nt h eo p t i m 眦r e s u i t 疔- o mt h ef i n i t es a m p l e sw l i c hi sn o to n l y m e o p t i m l i 工1 1r e s u l tw h e n t h es 砌p l e sa r ei n f i n i t e s v mh a sb e 船g e n e 删j z a t i o np e r f o r n l a f l c e a n dh i 曲e rp r e d i c t i o na c c 埘a c yt ot e s te x a m p l e s os v mh a sh a dal o to fa p p l i c a t i o n c u r r n t l y ，s v mi sb e c o m i n gah o ta r e ai nm e f l e l do f m a c l l i n e1 e a m i n gi nt h ew o r l d i nv i e wo fi t sb e t t e “e a n 血喀c 印a b i l 时a j l dp e r s p e c t i v ei na p p l i c a t i o n ，t 1 1 i sp 印e rt r i e dt o a p p i ys v m t ot t l ec a n c e rd i s e a s ed i a g n o s e s t h em a i nw o r k sa r ea sf o i l o w s ： f i r s t l y ，s t a t i s t i cl e a m i n gt h e o r ya n dt h et h e o r e t i cb a s eo fs v m a r ei n t r o d u c e db r i e n y s e c o n d l y a no v e r v i e wo n av a r i e t yo fc l a s s j f i c “o na l g o r i t | 1 i n sf o rs u p p o r tv e c t o r m a c h i n ei sg i v e n s o m ea l g o r i t h m ss u c ha sc s v m ，v s v m ，b s v ma n dl s s v ma r ea i m e d t ob ed i s c u s s e d 1 1 1 i r d l y ，s v mn o n l i n e a rc l a s s m e ri se m p l o ”dt ob r e a s tc a n c e rd i s e a s ed i a g n o s e sb y o p t i m i z i n gp 猢e t e r so f t r a i n i n gm o d e l s h i g hr e c o g n i t i o nr a t ei so b t a i n e di n 血ep r e d i c t i o n f i n a l l y ，o nt h eb a s eo ft 1 1 e 廿a d i t i o n a ls v ma l g o r i t l l i l l ，t h es v mi si m t i a l l yt r a i n e d 丘o m t 1 1 e 订a 血i n gs a m p l e s ，t 1 1 e r e b yp r o d u c i n gan u m b e ro fm a i ns u p p o r tv e c t o r s s u b s e q u e m l y ，t h e s v ma r er e t r a i n e do n l yf m mt h em a i ns u p p o nv e c t o r s ，t 1 1 e r e b yp r o d u c i n gan u m b e ro f s u b s u p p o r tv e c t o r s i nt h ea r e ao fc a n c e rd i s e a s ed i a g n o s e s ，t t l es v m n o n l i n c a rc l a s s i f i e r w l l i c hi sc o n s t m c t e db ys u b s u p p o nv e c t o r s ，c a i la c h i e v em o r eh i 曲e rr e c o g n i t i o nr a t et h a l l u s i n gt h et r a d i t i o n a ls v m c l a s s i f i e r si nm ep r e d i c t i o n k e yw o r d s ：s u p p o r tv e c t o rm a c l l i n e ； m a c h i n el e 锄i n g ：p a t t e mr e c 0 9 1 1 i t i o n ；s t a t i s t i c a l l e a r n i n gt 1 1 e o r y i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得东北师范 大学或其他教育机构的学位或证书而使用过的材料。与我一同【：作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：多红0 学位论文版权使用授权书 本学位论文作者完仝了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和磁盘，允许论文被奄阅和借阅。本人授权东北师范大学可以将学 似论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其它复制手段保1 竽、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 日期： 学位论文作者牛业后去向 工作单位 通讯地址 片? _ ： 指导教师签名： - 。、， 日期：i 研 电 邮 话 编 黪 第一章引言 1 1 支持向量机产生背景 模式识别诞生于2 0 【业纪2 0 年代，随着4 0 年代计算机的出现，5 0 年代人工智能的兴 起，模式识别在6 0 年代初迅速发展成一门学科。它所研究的理论和方法在很多科学和技 术领域中得到了广泛的重视，推动了人工智能系统的发展，扩大了计算机应用的可能性。 几十年来，模式识别研究取得了大量的成果，在很多地方得到了成功的应用。 模式识别是指用计算机实现人的模式识别能力。模式识别的作用就在于让计算机面对 某种事物时将其正确的归入某一类别。经典的模式识别方法有统计模式识别和结构( 句法) 模式识别。统计模式识别可看成是基于数据的机器学习的特例。 基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据出发寻找规律， 利用这些规律对未来数据或无法观测的数据进行预测。迄今为止，关于机器学习还没有一 种被共同接受的理论框架，关于其实现方法大致可以分为三种： 第一种是经典的统计估计方法【2 】。包括模式识别、神经网络等在内，现有机器学习方 法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这种方法中， 参数的相关形式是已知的，训练样本用来估计参数的值。这种方法有很大的局限性，首先， 它需要已知样本分布形式，这需要花费很大代价，还有，传统统计学研究的是样本数目趋 于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中，样本数往往 是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。 第二种方法是经验非线性方法，如人工神经网络口】。这种方法利用已知样本建立非线 性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。容 易陷入局部极小，网络的泛化能力不强，结构的设计( 例如隐结点的数目的选择) 依赖于 设计者的先验知识和经验，缺乏一种有理论依据的严格设计程序。尽管存在上述问题，这 些网络在原有的框架内仍然取得了许多成功的应用，原因在于这些应用的设计者在设计过 程中利用了自己的经验和先验知识。 第i 种是统计学习理论【4 】( s t a t i s t i c a l l e a m i n g t h e o r y 或s l t ) 。与传统统计学相比， 统计学习理论是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统 计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能 的要求，而且追求在现有有限信息的条件下得到最优结果。随着该理论的不断发展和成 熟，产生了基于统计学习理论体系的新的通用机器学习方法，即支持向量机( s v m ， s 印p o nv 毫c t o rm a c h i n e ) 。 ， 1 2 支持向量机的发展历史与研究现状 v 、却v i k 早在6 0 年代就丌始了统计学习理论的研究【5 1 ，1 9 7 1 年，v v a p v i k 和 l a c h e r v o n i n k i s 在“t h en e c e s s a r ya n ds u m c i e mc o n d i t i o n sf o rt 1 1 eu n i f o r m sc o n v e r g e n c e o f a v e r a g e st oe x p e c t e dv a l u e s ”提出s v m 的一个重要的理论基础一v c 维理论。 1 9 8 2 年，在“e s t i m “o no f d 印e n d e n c e sb a s e do ne m p m c a ld a t a ”中v v a p n i k 提出结 构风险最小化原理，称为s v m 算法的基石。 1 9 9 2 年，b o s e r ，g u v o n 以及v v a p n i k 提出了最优边界分类器 1 9 9 3 年，c o r t e s 和v v a p n i k 进一步探讨了非线性最优边界分类问题l “ 1 9 9 5 年，v v a p n i k 在“t h e n a t l l r e o f s t a t i s t i c a l l e a r n i n g t h e o r y ”中完整地提出了s v m 分类。 19 9 7 年，v v a p n i k ， s g o k o 谢c h 发表的“s u p p o r tv e c t o r m e t h o df o rf u i l c t i o n a p p r o x i m a t i o n ，r e g r e s s i o ne s t i m a t i o na n ds i 印a lp m c e s s i n g ”介绍了基于s v m 方法的同 归算法。 在模式识别方面最突出的应用研究是贝尔实验室对美幽邮政于写数字库进行的实验 8 l ，这是一个可识别性较差的数据库，人工平均识别率2 5 ，用决策树方法识别错误率是 1 6 2 ，两层神经网络中错误率最小的是5 9 ，专门针对该特定问题设计的工层神经网络 错误率5 1 ( 其中利用了大量先验知识) ，而用三种s v m 方法( 分别采用多项式核函数、 径向基核函数和s i 舯o i d 核函数) 得到的错误率分别为4 0 ，4 1 和4 2 ，其中直接采 用1 6 1 6 的字符点作为s v m 的输入，并没有进行专门的特征提取。实验一方面说明了 s v m 方法较传统方法有明显的优势，同时也说明了不同的s v m 方法可以得到性能相近的 结果( 不像神经网络那样可依赖于模型的选择) 。实验还观察到，三种s v m 求出的支持 向量中有8 0 以上是重合的，它们都只是总样本中很小的一部分，说明支持向量机本身对 不同方法具有定的不敏感性( 遗憾的是这些结论仅仅是从有限的实验中观察到的现象，如 果能得到证明，将会使s v m 的理念和应用有更大的突破) 。罔绕这字符识别实验，还提出 了一些对支持向量机的改进，比如引入关于f i 变性的知识【9 j 、通过样本预处理提高识别速 度1 叫等。相荚的应用还包括s v m 与神经网络相结合对笔迹进行的在线适应。除此之外， m i t 用s v m 进行的人检测实验也取得了较好的效果，i u 以较好地学会在图像中找出可能 的人脸位置l l “。 其它有报道的实验领域还包括文本识别、二维对象识别f 1 4 】、支持向量机算法的硬件 实现研究、系统辨识旧、遥感图像分析、材质分类、医疗诊断1 1 6 】、网页分类、图 像处理、故障渗断、信号处理、光谱分析【2 0 】等，这些研究大多为实验和仿真研究，如何应 用到实际当中去，仍有大量问题需要去研究。 1 3 本文的主要内容 本文针对支持向量机方法进行了研究，具体内容如下： 第一章为本文的引言部分，首先阐明了支持向量机的理论背景，概述支持向量机的 发展历史和研究现状，最后综述了本文的主要研究工作。 第二章首先简要介绍了机器学习的基本方法，然后引出统计学习理论的基本思想，并 对统计学习理论的一些基本概念进行了介绍。 第三章介绍支持向量机基本理论。 第四章介绍了几种常见和变形的支持向量机算法。 第五章介绍支持向量机在癌症诊断中的应用。 第二章统计学习理论 传统统计模式识别的方法都是在样本数目足够多的前提下进行研究的，只有在样本数 趋向无穷大时其性能才有理论上的保证。而在多数实际应用中，样本数目通常是有限的， 这时很多方法都难以取得理想的效果。统计学习理论是一种专门的小样本统计理论，为研 究有限样本情况下的统计模式识别和更广泛的机器学习问题建立了一个较好的理论框架。 统计模式识别问题可以看作是个更广义的问题的特例，就是基于数据的机器学习问 题。基于数据的机器学爿是现代智能技术中十分重要的一个方面，丰要研究如何从一些观 测数据出发得出目前尚不能通过原理分析得到的规律，利用这些规律去分析客观对象，对 未米数据或无法观测的数据进行预测。现实世界中存在大量我们尚无法准确认识但却可以 进行观测的事物，因此这种机器学习在从现代科学、技术到社会、经济等各领域中部有着 十分重要的应用。当我们把要研究的规律抽象成分类关系时，这种机器学习问题就是模式 识别。 统计是我们面对数据而又缺乏理论模型时最基本的分析手段，传统统计学所研究的是 渐进理论，即当样本数目趋向于无穷大时的极限特性，统计学中关于估计的一致性、无偏 性和估计方差的界等，以及分类错误率诸多结论，都具有这种渐近特性。但实际应用中， 这种前提条件却往往得不到满足，当问题处在高维空间时尤其如此，这实际上是包括模式 识别和神经嘲络等在内的现有机器学习理论和方法中的一个根本问题。 v v a p n i k 等人早在2 0 【! = 纪6 0 年代就开始研究有限样本情况卜的机器学习问题。由于 当时这些研究尚不十分完善，在解决模式识别问题中往往趋于保守，且数学上比较艰涩， 9 0 年代以前并没有提出能够将其理论付诸实现的较好的方法。加之当时正处在其他学习方 法飞速发展的时期，囚此这些研究一直没有得到充分的重视。直到9 0 年代中期，有限样 本隋况下的机器学习理论研究逐渐成熟起来，形成了一个较完善的理论体系统计学习 理论( s 诅t i s t i c a ll e a n l i n g1 1 h e o r y ，简称s l t ) 。同时，神经网络等较新兴的机器学习方法的 研究则遇到一些重要的困难，比如如何确定网络结构的问题、过学习与欠学习问题、局部 极小点问题等等。在这种情况下，试图从更本质上研究机器学习问题的统计学习理论逐步 得到重视。 在本章中，我们将从机器学习入手，并对统计学习理论进行介绍。 2 1 机器学习的基本问题 机器学习是一种基于数据的学习方法，研究从观测数据所包含的有限信息构造一个模 型，利用该模型可对未知数据或无法观测的数据进行尽可能准确的预测，这种模型称为学 习机器。对计算机科学而言，所有的数据都是以数字彤式表示的，因此机器学习问题实际 上是函数估计问题，相应地称函数估计器( f u n c t i o 璐e s t i m a t o r ) 为学习机器。 2 1 1 机器学习问题的表示 机器学习问题的基本模型，可以用图2 1 表示。其中，系统s 是我们研究的对象，它 在给定一定输入x 下得到定的输出y ，l m 是我们所求的学习机，输出为多。机器学习 的目的是根掘给定的已知训练样本求取对系 统输入输出之间的依赖关系，使它能够对未 知输出作出尽可能准确的预测。 图2 1机器学习问题的基本模型 机器学习问题的数学模型可以表示为：变量x 与变量_ y 存在一定的未知依赖关系，即 遵循某一未知的联合概率密度f ，y ) ，机器学习的问题就是根据，个独立同分布的观测 样本 ( 2 1 ) 在一组函数扩( x ，w ) ：w a ) 中寻找一个最优的函数，( x ，) 对( x ，_ y ) 的依赖关系进 行估计，使得期望风险( 义称实际风险) 最小。 r ( w ) = i l ，( x ，w ) ) d f ( x ，力 ( 2 2 ) 其中， 厂( x ，w ) ：w a 称为预测函数集( 又称学习函数、学习模型或者学习机器) ， 它可以是任何函数集；w 是，( x ，w ) 的广义参数；( y ，厂( 工，w ) ) 是用，( w ) 对茁进行预测 时产生的损失( 误差) 。由期望风险的定义可以看出，它描述了学习机器在样本所在空间 的每一个点上的风险的平均期望值，反映了学习机器的真实推广能力。机器学习的任务 就是通过在有限样本卜的训练，寻找一个使得期望风险( 2 2 ) 式最小的具体的函数 ，( x ，) 。 不同的损失函数构成了不同类型的学习问题，主要有三类不问的学习问题，即模式 ： 别，函数逼近和概率密度估计。对模式识别问题，一般其输出y 是样本类别标号，对丁- y = o ，l ，此时损失函数为： 坳心w 胪 ? ；嚣驾 ， 在函数逼近问题中，y 是连续变量，损失函数可以定义为 l ( y ，( 工，w ) ) = ( y 一厂( x ，w ) ) 2 ( 2 4 ) 即采用最小二乘误差准则。而对于概率密度估计问题，学习的目的是根据训练样本 决定茁的概率密度，估计的概率为p ( x ，w ) ，其损失函数定义为 l ( p ( x ，w ) ) = 一l o g p ( x ，w ) ( 2 5 ) 本文主要讨论的模式识别问题，也就是在大部分情况下采用( 2 3 ) 式所示的损失函数。 2 1 2 经验风险最小化( e r m ) 原则 机器学习的目的在于通过对训练样本的学习，使得学习机器对所有样本预测厂( x ，w ) 和 其真实输出y 尽可能相同，也就是使得期望风险( 2 2 ) 式最小。但在实际问题中，联合概率 f ( t y ) 未知，只知道，个观测样本式( 2 1 ) ，因此期望风险是1 i 能直接计算的，最直观的方 法是计算学习机器在有限个训练样本上的损失的平均值，并选择使它最小的函数作为学习 机器，也就是 m i ( w ) 弓枷，他，w ) ) ( 2 6 ) 式( 2 6 ) 的损失计算方法称为学习机器的经验风险，而通过使得经验风险最小来选择学习 机器的训练方法称为经验风险最小化原则( e m p i r i c a l 砒s km i n i m i z a t i o n ，e r m ) 。 事实上，用e m r 原则代替期望风险最小化并没有经过充分的理论论证，只是直观上 合理的想当然做法，但这种思想却在多年的机器学习研究中占据了主要地位。人们多年来 将大部分注意力集中到如何更好地最小化经验风险上。而实际上，即使可以假定当n 趋向 于无穷大时( 2 6 ) 式趋近于( 2 2 ) 式，在很多问题中的样本数目也离无穷大相去甚远， 当样本的数目f 有限时，e r m 原则并不能保证学习机器的期望风险最小。 2 1 3 复杂性与推广能力 e m r 原则不成功的一个典型的例子是神经网络的过学习现象，也就是当经验风险达 到最小时神经网络的推广能力反而变差的现象。开始，很多注意力都集中在如何使r 。( w ) 更小，但很快就发现，训练误差小并不总能导致好的预测效果。某些情况下，训练误差过 小反而会导致推广能力的下降，即真实风险的增加，这就是过学习问题。 之所以会出现过学习现象，一是因为样本不充分，二是学习机器设计不合理， 这两个问题是互相关联的。设想一个简单的例子，假设有一组实数样本( x ，y ) ，y 在 o ，1 】 之间取值，那么不论样本是依据什么模型产生的，只要用函数，( x ，口) = s i n ( 锻) 去拟合它们 ( 口是待定参数) ，总能够找到一个口使训练误差为零，但显然得到的“最优”函数并不 能正确代表真实的函数模型。究其原因，是试图用一个十分复杂的模型去拟合有限的样本， 导致模型丧失了推广能力。在神经网络中，若对有限的样本来说网络学习能力过强，足以 记住每个样本，此时经验风险很快就可以收敛到很小甚至零，但却根本无法保证它对未来 样本能给出好的预测。由此可看m ，有限样本情况卜，( 1 ) 经验风险最小并不一定意味 着期望风险最小；( 2 ) 学习机器的复杂性不但应与所研究的系统有关，而且要和有限数 目的样本相适应。我们需要一种能够指导我们在有限样本情况下建立有效的学习和推广方 法的理论。 2 2 统计学习理论 为了解决有限样本的机器学习问题，在过去二十多年里，发展了很多新的统计学方法， 其中v v a p | 1 i k e 等发展了专门研究小样本统计估计和预测的统计学习理论以及结构风险最 小化原则( s 佻t u m l 砌s km i n i m i z a l j o n ，s r m ) 。 统计学习理论就是研究小样本统计估计和预测佝理论，主要内容包括四个方面： 1 ) 经验风险最小化原则下统计学习一致性的条件； 2 ) 在这些条件下关于统计学习方法推广性的界的结沦： 3 ) 在这些界的基础上建立的小样本归纳推理准则； 4 ) 实现新的准则的实际方法( 算法) 。 其中，最有指导性的理沦结果是推广性的界，与此相天的一个核心概念是v c 维。 2 2 1 v c 维 模式识别方法中v c ( v a p l l i kc h e n r o n e l l l ( d i n l e n s i o n ) 维的直观定义是：对个指示函数 集，如果存在h 个样本能够被函数集中的函数按所有可能的2 “种形式分开，则称函数集能 够把h 个样本打散；函数集的v c 维就是它能打散的最大样本数目h 。若列任意数目的样 本都有函数能将它们打散，则函数集的v c 维是无穷大。有界实函数的v c 维可以通过用 一定的阈值将它转化成指示函数来定义。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。遗憾的 是，目前尚没有通用的关于任意函数集v c 维训算的理论，只对一些特殊的函数集知道其 v c 维。比如在n 维实数空间中线性分类器和线性实函数的v c 维是n + 1 。而上一节例子中 ，( x ，d ) = s i n ( 僦) 的v c 维则为无穷大。对于些比较复杂的学习机器( 如神经网络) ，其 v c 维除了与函数集( 神经网结构) 有关外，还受学习算法等的影响，其确定更加困难。对于 给定的学习函数集，如何( 用理论或实验的方法) 计算其v c 维是当前统计学习理论中有待 研究的一个问题。 2 2 2 推广性的界 统计学习理论系统地研究了对于各种类型的函数集，经验飙险和实际风险之间的关 系，即推广性的界。关于两类分类问题，结论是：埘指示函数集中的所有函数f 包括使经验 风险最小的函数) ，经验风险r 。( w ) 和真实风险r ( w ) 之问以至少l n 的概率满足如下关 系： 月( 。) 月。，( 。) + 兰卫旦生! 堑生2 _ 上l 二三! 业 、 ( 2 7 ) v以 上式右端第一项反映训练样本的拟合程度；第二项称为v a p l l i l ( c h e r v o n e n 虹s 置信范围 ( 义称v c 置信范围) ，h 是函数集的v c 维。 式( 2 7 ) 表明，在有限训练样本下，学习机器的v c 维越高( 复杂性越高) 则置信范围 越大，导致真实风险与经验风险之问町能的差别越大。这就是为什么会出现过学习现象的 原因。机器学习过程不但要使经验风险最小，还要使v c 维尽量小以缩小置信范围，j 能 取得较小的实际风险，即对末来样本有较好的推广性。 2 2 3 结构风险最小化( s r m ) 原则 在传统方法中，选择学习模型 和算法的过程就是调整置信范围 的过程，如果模型比较适合现有的 飙浚 的训练样本( 相当于n | l 值适当) ， 则可以取得比较好的效果。但因为 缺乏理论指导，这种选择只能依赖 先验知识和经验，造成了如神经网 络等方法对使用者“技巧”的过分 依赖。 当“h 较大时，式f 2 7 ) 右边的 第部分就较小，真实风险就接近 经验风险的取值。如果n l l 较小， 那么一个小的经验风险值并不能 保证小的真实风险值。在这种情况 下，要最小化真实风险值，就必须 对1 i 等式( 2 7 ) 右边的两项同时最 受三彳 两数黛了集：s ，c s i o 岛 v c 维： i 矗： j 图2 2 结构风险最小化示意图 小化。但是需要注意，不等式( 2 7 ) 右边的第一项取决于函数集中的一个特定函数，而第 二项取决于整个函数集的v c 维。因此要对风险的界，即式( 2 7 ) 的右边的两项同时最小 化，我们必须使v c 维成为一个可以控制的变昔。 统计学习珲论提出了种新的策略，即把函数集构造为一个函数子集序列，使各个 子集按照v c 维的大小( 亦即中的大小) 排列，在每个子集巾寻找最小经验风险，在 子集问折衷考虑经验风险和置信范围，取得真实风险的最小，如图2 2 。 丁是有两个思路：一是在每个子集中求最小经验风险，然后选择使最小经验风险和置 信范围之和最小的子集。这种方法比较费时，当子集数目很大甚至是无穷时不可行。于是 有第二种思路，即设计函数集的某种结构使每个子集中都能取得最小的经验风险f 如使训 练误差为o ) ，然后只需选择适当的子集使置信范围最小，这个子集中使经验风险最小的函 数就是最优函数。支持向量机就是这种思想的具体实现。 第三章支持向量机基本理论 在上一章，我们指出了统计学习理论有四部分内容，其前三个部分的核心内容，是其 理论的部分，已在上一章中介绍。而要使理论在实际中发挥作用，还要求它能够实现，这 就是本章所要讨论的统计学习理论中的第四部分内容，即实现其理论思想的方法一支持 向量机( s u p p o r tv e c t o rm a c h i l l e 简称s v m ) 方法，它是统计学习理论中最年轻的部分，也是 最实用的部分。其核心内容是在1 9 9 2 到1 9 9 5 年问提出的，目前仍处住不断发展阶段。山 以说，统计学爿理论之所以从上世纪9 0 年代以来受到越来越多的重视，很大程度上是因 为发展了支持向量机这一通用学习算法。因为从某种意义上s v m 可表示成类似神经网络 的形式，故s v m 在最仞也叫支持向量网络。 支持向量机的基本思想是在样本空间或特征空间，构造出最优超平面，使得超平面与 不同类样本集之间的距离最大，从而达到最人的泛化能力。下面仅讨论s v m 二分类的非 增量训练算法。 设训练样本集为( x 。，“) ，( f _ 1 ，2 ，3 ，”) ，x ，r 4 ，儿 + 1 ，一1 是类别标号。学习目标是根 据结构风险最小化原则，构造一个目标函数，将两类模式尽量正确地灭分开来。下面针刘 训练样本集为线性可分和非线性可分两种情况分别讨论。 3 1 线性情况 如果存在超平面方程为： w x + 6 = 0 使样本集满足 w z ，+ 6 】 咒= j w 。t + 6 1y 。= 一l ( 3 1 ) ( 3 2 ) 称训练集为线性可分。( 3 1 ) ( 3 2 ) 式可以写成如下形式： y ，( w x ：+ 6 ) 1 ( 3 3 ) 如果训练样本集被超平面正确分开，并且距超平面最近的样本数据与超平面之间的距 离最大，则该超平面为最优分类超平面( 如图3 1 ) 。距离该最优超平面最近的向量就是所 谓的支持向量( s u p p o r tv e c t o r ) ，一组支持向量可以唯一确定一个超平面。支持向量与超平 而之间的距离为l 川w i | ，则支持向量间距为2 川w l l 。因此构造最优超平面的问题就转化为 在( 3 3 ) 的约束下求函数最小值问题： 中( w ) ：如w 0昙( 石i ) 在维空间中，设样本分布住一个半径为 r 的超球范围内，则满足条件m 悟爿的l f 则超 平面构成的指示函数集 厂( x ，w ，6 ) = j 国 ( w x + 6 ) 的v c 维满足下 面的界 厶m i n ( 【r 2 彳2 】，) + 1 因此使j f w 20 最小就是使v c 维的上界最小，从 而实现s r m 原则中对函数复杂性的选择。 v a p n j k 证明，如果训练集中的向量能被最优超 平面完全划分，则在测试未知样本时的最大山 n l 第类 l p 、+ 西= l 支 = 拘量 箍二粪 ( 3 4 ) 1 p + 矗= 一l 错概率，目口支持向量机期望风险的上界为： 图3 1 最优分类超平面 叫阶岫肛甓妻蒜梁挚 由上面的讨论可知，在线性可分情况下构造最优超平面的问题可以转化为在式( 3 | 3 ) 的约束下最小化式( 3 4 ) ，这是个二次规划问题，其最优解为下列l a g r a n g e 函数的 鞍点： 1口 = 去( w t 切一q 眈如w + 6 ) 一1 - z = l ( 3 5 ) 口。 o 为l a g r a n g e 系数。式( 3 4 ) 存在唯一的最优解，在鞍点处，由于w 和6 的梯度均 为零，则可得： q 只= o 呸o ，：i ，2 ，甩 ( 3 6 ) 坶l d ，蹦= w 、 ( 3 7 ) 将( 3 6 ) ( 3 7 ) 代入( 3 5 ) 式，构建最优超平面的叫题就转化为一个较简单的二次规划 问题，即在式( 3 8 ) ( 3 9 ) 的约束下，最大化式( 3 10 1 ： q o，= l ，肝 ( 3 8 ) 口，咒= o ( 3 9 ) 岛= q 一去w - w = q 一去q 吁咒乃玛- 乃 ( 3 1 0 ) _ l 厶 f 爿山阔，= l 根据k u h r 卜t u c k e r 定理，优化问题的解须满足：在鞍点，对偶变量与约束的乘积为 零， 口， y ，( w - x ，+ 6 ) 一1 = o ( f = 1 ，挚t ，? ) ( 3 1 1 ) 多数样本口。将为零，取值不为零的口，对应于使( 3 4 ) 式等号成立的样本，即支持向量， 它们通常只是全体样本中的很少一部分。 求解上述问题后得到的最优分类函数是 厂( x ) = j 忉 ( w x ) + 6 】= s 堙w ( 口，少，_ x + 6 ) ( 3 1 2 ) 由于非支持向量对应的口，均为零，因此式中的求和实际上只对支持向量进行。6 是 分类域值。 训练样本集为线性不可分时，需引入非负松弛变量孝，j _ 1 ，2 ，即，构造最优超平面 问题转化为二次规划问题： 慨扣n c 喜手。1 s ty 。( w x 。+ 6 ) 1 一善， ( 3 1 3 ) f ；o ，f = 1 ，2 ，胛 j 当划分出现错误时专大于零，因此缶是训练集中划分错误的向量数量上界。c 为惩 罚参数，c 越大对错误分类的惩罚越大。采用拉格朗曰乘子法求解这个具有线性约束 的二次规划问题，即 学噢 工，= 扣圳2 + c 喜茧一喜引蹦w 喁+ 6 ) 一1 + 引一喜嘴 ( 3 1 4 ) 其中口。，_ 为l a g r a i l g e 乘予。由此得 等：o j w ：窆哪，x 。 汐w智 盟：o j 争刚，：o 矛6 鲁“。 ( 3 1 5 ) ( 3 1 6 ) 孚：o 乍c q 一：o 蚕芎j j。 将式( 3 1 5 ) ( 3 ，1 6 ) ( 3 1 7 ) 代入式( 3 1 4 ) ，得到对偶最优化问题 n a = 乏弘一 q m 乃鼍x ) “ f d 二问一 s t0 晓c 口，y ，= o ( 3 1 7 ) ( 3 1 8 ) ( 3 1 9 ) ( 3 2 0 ) 最优化求解得到的口，可能足：1 ) 口，= o ；2 ) o 甜。 c ；3 ) 口，= c 。后两者所射应的工，为支 持向量。由式( 3 1 5 ) 知只有支持向量对w 有贡献，也就对最优超平面和判别函数有贡献。2 ) 所对应的x 。称为标准支持向量( n o n n a ls u p p o nv e c l o r ) ，3 ) 所对应的t 称为边界支持向量 ( b o u i 】岫s u p p o r tv e c t o r ) ，实际上是错分的训练样本点。 这是一个典型的_ 次优化问题，按照优化理论的k u l l l l 一t u c k e r 定理，在鞍点，对偶 变萤与约束的乘积为零，即 d ， y ，( w 工，+ 6 ) 一1 + 点】= 0 ( 3 2 1 ) 六= o ，= l ，栉 ( 3 2 2 ) 对于标准支持向量( o q c ) ，由式( 3 1 7 ) 可知o o ，表示集合中的样本数目) 的两个集合 s + 和s 一，s + 表示从证类别选取的集合，s 一表示从负类别选取的集合。它们包含的支 持向量x i 满足0 1 ，所以根据k k t 条件，式( 4 7 ) 的约束条件 9 d 叫 t 口 j j 0 ， 拶 d + 吒 k ：哒莒眠 咒矽地) + 功p 一戋变为等式，并且茧= o 。经过公式变换得到的b 和尸用核函数 表示为： 6 = 一。去口，y ，k ( x ，x ，) ( 4 1 0 ) 二j x e s u 5， p = 。去( 口，y ，k ( x ，x ，) 一吩乃k ( x ，x ，) ) o 。fx e sl 4 2 4l s s 、，m 算法 ( 4 1 1 ) 在s u y k e n s 和v a i l d e w a l b 提出的最小二乘支持向量机( 1 e a s t - s q u a r es v m ，l s s v m ) 中， 优化指标采用了平方项，只有等式约束，而没有c s v m 的1 i 等式约束，从而推出不同的 一系列的等式约束，而不是二次规划问题。其问题表示为 璁圳心薏茧 j ，少，( 脚。妒( 蕾) + 6 ) = 1 一毒 ( 4 1 2 ) f = 1 ， 可得到线性方程组 匕矗d 。m 。，习 其中p 尺7 为元素为1 的向量，r 为单位阵，口= k l ，口2 ，口汀尼。 y = b 。，y ：，y j 月，