（计算机应用技术专业论文）支撑矢量机混合算法的研究.pdf

摘要 摘要 统计学习理论是一种研究基于样本的机器学习理论。v v a p n i k 等人从六、 七十年代开始致力于此方面研究，到九十年代中期，其理论的不断发展和成熟， 已基本形成一套比较完整的理论体系。在这一理论基础上发展了一种新的通用学 习方法支撑矢量机( s v m ) 。支撑矢量机是一种普遍适用的方法，已经广泛地用 于模式识别、回归估计、函数逼近、密度估计等方面。本文在对支撑矢量机研究 的基础上，分别研究了四种方法： 1 ) 提出了基于晟小支撑矢量集的s v m 算法。通过减少支撑矢量集合中冗余 矢量的方法来减少支撑矢量的规模以获得较短的检测时间。 2 ) 研究了基于线性组合核的s v m 算法。根据核函数的特性引入半正定规 划，把已知的几种核函数组合起来，以求得性能更佳的核函数。 3 ) 提出了基于遗传算法的s v m 多参数选择算法。利用遗传算法的并行性和 全局性，来调整核函数的参数获得较精确的核形状。 4 ) 提出了基于免疫算子的s v m 多参数选择算法。遗传算法在搜索时是盲目 的，而免疫算子正能够避免盲目搜索在提高精度的同时也大大减少了计算时间。 理论分析和仿真实验证明了本文中方法的正确性和有效性。 关键词：统计学理论模式识别支撑矢量机半正定规划 遗传算法免疫算 子 支撑矢量机混台算法的研究 a b s t r a c t s t a t i s t i c a ll e a r n i n gy h e o r yi sam a c h i n el e a r n i n gt h e o r yb a s e do nr e s e a r c h i n g d a t a m a n yp e o p l ei n c l u d i n gvv a p n i k w e r ee n g a g e di nt h i sf i e l d i td i dn o tb e c o m ea f u l l e rl e a r n i n gt h e o r yu n t i lt h em i d d l eo f9 0 ”b a s i n go nt h i st h e o r yan e w g e n e r a l l e a r n i n gm e t h o dw a so b t a i n e d ，i ti ss u p p o r tv e c t o rm a c h i n e ( s v m ) s v mh a sb e e n w i d e l yu s e df o rp a t t e r nr e c o g n i t i o n ，t h er e g r e s s i o ne s t i m a t i o n ，f u n c t i o na p p r o a c h ， d e n s i t ye s t i m a t i o n ，e t c t h i st h e s i s c o n t a i n sd e s c r i p t i o n so ff o u rm e t h o d st h a tc a n i m p r o v e t h ep e r f o r m a n c eo f s v m t h e y a r el i s t e di nt h ef o l l o w i n g 1 ) b yg e t t i n gr i do ft h el i n e a rs u p p o nv e c t o r s ，w ec a nd e c r e a s et h ea m o u n to f s u p p o r t v e c t o r s i no t h e rw e r d s ，t h et i m e o f t e s t i n g d a t ac o u l db er e d u c e d 2 ) a c c o r d i n gt ot h ep r o p e r t yo ft h ek e r n e lf u n c t i o n s ，w ec a nc o m b i n es e v e r a l k e m e lf u n c t i o n sb ys e m i d e f i n i t ep r o g r a m m i n g an e wb e t t e rp e r f o r m a n c ek e r n e j f u n c t i o ns h o u l db eg e n e r a t e db yt h i sm e t h o d 3 ) g e n e t i ca l g o r i t h mi s p a r a l l e la n d 百o b a l ，s o i tc a nb eu s e dt ot u n et h e p a r a m e t e r so f s v m 4 ) b u tt h es e a r c h i n gp a t ho f g e n e t i ca l g o r i t h mi sb l i n d n e s s i no r d e rt oa v o i dt h i s s h o r t c o m i n g ，w e u s ea ni m m u n e o p e r a t o r i ng e n e t i c a l g o r i t h m t or e d u c et h e s e a r c h i n gt i m e t h e o r ya n a l y s i sa n ds i m u l a t i o nr e s u l t sf o rd a t as h o wt h er e s u l tb a s e do nt h e s e m e t h o d sa r ei m p r o v e dm u c hm o r et h a nn o r m a la l g o r i t h m s k e y w o r d s ：s t a t i s t i c st h e o r ys u p p o r tv e c t o rm a c h i n e s ( s v m ) s e m i - d e f i n i t e p r o g r a m m i n g g e n e t i c a l g o r i t h m i m m u n e o p e r a t i o n p a t t e r nr e c o g n i t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期：2 塑! ：兰 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然为西 安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校 可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存 论文。( 保密的论文在解密后遵守此规定) 本人签名 导师签名： 日期：迎2 ，z 日期：d 口3 、z 魔干 一堕垤 翌 第一章绪论 第一章绪论 i i 统计学习理论的进展 人们生活在客观世界中，为了适应和改造客观世界，就必须认识世界。模式 识别诞生于2 0 世纪2 0 年代，随着4 0 年代计算机的出现，5 0 年代人工智能的兴 起，模式识别在6 0 年代迅速发展成为一门学科。它所研究的理论和方法在很多科 学和技术领域中得到了广泛的重视，推动了人工智能系统的发展，扩大了计算机 应用的可能性。模式识别就是用计算机实现人的模式识别能力，即面对于某具 体事物时将其正确地归入某一类别，在错误率尽可能小的情况下，使识别的结果 尽量与客观事物相符。几十年来模式识别研究获得了大量的成果，在很多地方得 到了成功的应用。模式识别方法是由两个过程所组成的：设计和实现。设计是指 用一定数量的样本( 训练集或学习集) 进行分类器的设计；实现是指用所设计的 分类器对待识别的样本进行分类决策。所以基于统计方法的模式识别系统主要由 4 个部分组成：数据获取、预处理、特征提取和选择、分类决策i ”。 f ! j ；j ：熹 传统的模式识别的方法都是在样本数目足够多的前提下进行研究的，所提出 的各种方法只有在样本数都趋向无限大时其性能才有理论上的保证。而在多数实 际应用中样本数目通常是有限的，这使很多方法都很难以取得理想的效果。统 计学习理论是一种专门的小样本统计理论，它是在经验风险最小化和有序风险最 小化的基础上发展起来的，为研究有限样本情况下的统计模式识别和更广泛的机 器学习问题建立了一个较好的理论框架同时也发展了一种新的模式识别的方法 支撑矢量机，能够较好的解决小样本学习问题。 统计模式识别问题可以看成是一个广义问题的特例，就是基于数据的机器学 习问题，基于数据的机器学习是现代智能技术中十分重要的个方面，主要研究 如何从一些观测样本数据出发得出目前尚不能通过原理分析得到的规律，利用这 些规律去分析客观对象对未来数据或无法观测的数据进行预测。现实世界中存 在大量我们无法准确认识但可以进行观测的事物，因此这种机器学习从科学、技 术到社会、经济等各领域都有着十分重要的应用。 支撑矢量机混合算法的研究 统计是我们面对数据而又缺乏理论模型时最基本的也是唯一的分析手段，它 是支撑矢量机的基础。传统统计学所研究的是渐进理论，即当样本数目趋向于无 穷大时的极限特性。统计学中关于估计的一致性、无偏性和估计方差的界等，以 及分类错误率的诸多结论都属于这种渐进特性。但实际应用中，这种前提条件却 往往得不到满足，当问题处在高维空间时尤为如此，这实际上是包括模式识别和 神经网络等在内的现有的机器学习理论和方法中的一个根本问题。 v l a d i m i rn v a p n i k 等人早在2 0 世纪6 0 年代就开始研究有限样本情况下的机 器学习问题，经验风险最小化和有序风险最小化就是在这个方向上较早期的研究 成果由于当时这些研究不十分完善，在解决模式识别问题中往往趋于保守，且 数学上比较艰涩，而直到9 0 年代以前并没有提出能够将其理论付诸实现的较好的 方法0 , 2 1 。加之当时正处在其他学习方法飞速发展的时期，因此这些研究一直没 有得到充分的重视。直到9 0 年代中期，有限样本隋况下的机器学习理论研究逐渐 成熟起来，形成一个较完善的理论体系统计学习理论( s t a t i s t i c a ll e a r n i n g t h e o r y ，简称s l t l 。而同时，神经网络等较新兴的机器学习方法的研究则遇到一 些重要的困难，比如如何确定网络结构的问题、过学习与欠学习问题、局部最小 点问题等。在这种隋况下，试图从更本质上研究机器学习问题的统计学习理论逐 步得到重视。 1 9 9 2 年1 9 9 5 年。在统计学习理论的基础上发展出了一种新的模式识别方 法支撑矢量机( 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 方法研究的同时，学者们对它进行了改进。如引 入关于不变性的知识，识别和去除样本集中的冗余，通过样本集预处理提高识别 速度。如：1 9 9 2 年b o s e r , g u y o n 和v a p n i k 提出的c h u n k i n g 算法【4 j 。其基本思想 是把大规模的二次规划问题分解成一系n d , 规模的二次规划问题。当支撑矢量的 数量较少时，c h u n k i n g 算法能够提高训练速度，但如果支撑矢量的数量较多时， 工作的样本集也就越来越多，算法依然很复杂。针对这一问题，o s u n a ，f r e u n d 和 g i r o s i 于1 9 9 7 年提出了o s u n a 算法【5 j ，它不同于c h u n k i n g 算法，c h u n k i n g 算法 的训练样本规模会不断增大而且从工作集中删除的样本都是非支撑矢量，而 o s u n a 算法的训练样本的规模是固定的。而且删去的样本是任意选取的。1 9 9 8 年 j o a c h i m s 在o s u n a 算法的基础上提出了一种改进算法s v m “g 呲【6 1 该算法的训练速 度得到了一定的提高。1 9 9 8 年p l a t t 提出工作集中的样本只有两个的s m o 第一章绪论 ( s e q u e n t i a lm i n i m a lo p t i m i z a f i o n ) 算法1 7 ，该算法只需要进行数值分析即可，而 且时间和存储空间的复杂度都有了明显的减少。 b e n n e a 和d e m i r i z 提出了半监督的支撑矢量机，该方法在训练时不仅采用了 有监督输出的训练集，而且还采用了无监督输出的工作集 8 】。s m o l a 等人把参数 模型扩展到支撑矢量机中，提出了半参数的支撑矢量机【9 】。 对于多分类问题的情况，最常用的是把多分类问题简化成为多个二类问题的 算法如o n e a g a i n s t a l l 方法【i 。 统计学习理论虽然己经提出多年，但支撑矢量机从它自身成熟和被重视到现 在也只有十年左右，其中还存在一些尚未解决和尚未充分解决的问题，如：根据 实际问题如何选择核函数，现在还没有理论依据；核函数的参数应该定为多少， 也没有明确的方法。 1 2 本文的主要工作 本论文主要就支撑矢量机方法的一些基本理论进行了一些讨论并在其基础上 作了一些改进以提高分类能力和速度。本论文研究的主要内容有三个方面：减 少支撑矢量集中的冗余矢量、使用半正定规划构造新的核函数、使用进化算法优 化核函数的参数。本论文章节安排如下： 在第二章阐述了有关统计学习理论、支撑矢量机、核函数和核学习方法的基 本知识。 第三章中给出了去除线性相关的支撑矢量的方法，来达到减少支撑矢量集合 规模的目的。经过试验观察当样本规模较大时，训练出的支撑矢量总有一些是 线性相关的也就意味着其中有些支撑矢量是可以由其他支撑矢量线性表示出来 的，即支撑矢量集合中有冗余。我们通过线性代数和矩阵论中的一些方法寻找出 支撑矢量集合中线陛无关的支撑矢量并用它们表达出其余的支撑矢量，使得用 于检测的支撑矢量集合变小，以达到减少检测时间，又不降低算法精确度的目的。 第四章中对如何按照实际数据选择核函数做了一些讨论，针对这个问题本章 给出了一种利用半正定规划构造新的核函数的方法。我们知道支撑矢量机中面临 的一个重要的难题就是如何选择一个更好的核函数来适应特定问题，到目前为止 在这方面还没有理论依据。近年来半定规划算法逐渐成熟己经成为解决复杂矩 阵问题的一种较好的方法而支撑矢量机中的核函数可以表示成为一个对称并正 定的g r a m 矩阵，正好符合半正定规划的要求。我们把现有的几个核函数组合起 来以支撑矢量机的误差界及新核函数半正定为约束条件，求得对于某个问题最 优的新核函数来提高识别率。 支撑矢量机混合算法的研究 第五章中讨论了核函数参数的选择问题。我们知道支撑矢量机中核函数的参 数一般都是凭经验给出，当然支撑矢量机本身对不同的方法具有一定的不敏感性， 但是当问题要求精度很高时，经验参数往往达不到要求。本章中分别提出了利用 遗传算法和免疫算子两种进化算法来提取参数。遗传算法是近年来一种新的智能 算法，它具有搜索能力强、搜索范围广、本身具有并行性的优良特点。免疫算子 是在遗传算法的基础上对算法的搜索路径进行了修正，避免了遗传算法的盲目搜 索，在提高算法精度的同时又减少叠代的次数，大大减少了计算时间，获得了较 好的效果。 本文的工作得到了国家自然科学基金( 6 0 0 7 3 0 5 3 和6 0 1 3 3 0 1 0 ) 的资助。 第二章统计学习理论和支撑矢量机算法 第二章统计学习理论和支撑矢量机算法 基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据( 样本) 出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。包括模式 识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。 传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基 于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学 习方法实际中表现却可能不尽人意。 与传统统计学相比，统计学习理论( 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 l t ) 是一 种专门研究小样本情况下机器学习规律的理论。v v a p n i k 等人从六、七十年代开 始致力于此方面研究1 ，到九十年代中期，随着其理论的不断发展和成熟，也由 于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越 广泛的重视“ j 。 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习 问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多 原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) ：同时， 在这一理论基础上发展了一种新的通用学习方法支撑矢量机( s u p p o r t v e c t o r m a c h i n e 或s v m ) ，它己初步表现出很多优于已有方法的性能。一些学者认为， s l t 和s v m 正在成为继神经网络研究之后新的研究热点，并将有力地推动机器学 习理论和技术的发展”1 。支撑矢量机是一种普遍适用的方法，已经广泛地用于模 式识别【t 3 , 3 3 1 、回归估计、函数逼近、密度估计等方面。 2 1 机器学习的基本问题 2 1 1 问题的表示 机器学习的目的是根据给定的训练样本求得对某系统输入输出之间依赖关系 的估计，使它能够对未知输出做出尽可能准确的预测。可以一般地表示为：变量y 与x 存在一定的未知依赖关系，即遵循某一未知的联合概率盹力，( x 和y 之间 的确定性关系可以看作是其特例) ，机器学习问题就是根据n 个独立同分布观测 样本 ( ，m ) ，( x 2 ，儿) ，( 屯，“)( 2 - 1 ) 在一组函数( ，k w ) ) 中求一个最优的函数a x , w 。) 对依赖关系进行估计使期望风 险最小。其中， ( 他w ) ) 称作预测函数集，w 为函数的广义参数 ，w ) ) 可 6 支撑矢量机混合算法的研究 以表示任何函数集：工舷w ) ) 为由于用如w ) 对y 进行预测而造成的损失，不同 类型的学习问题有不同形式的损失函数。预测函数也称作学习函数、学习模型或 学习机器。 r ( w ) = i l ( y ，f ( x ，w ) ) d f ( x ，y )( 2 - 2 ) 有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计。对模 式i q ，3 u 问题，输出y 是类别标号，两类情况下尸( 0 ，1 ) 或 1 ，一1 ) 预测函数称 作指示函数，损失函数可以定义为 坳撇w 胪置黑鬟( 2 - 3 ， 使风险最小就是b a y e s 决策中使错误率最小。 2 1 2 经验风险最小化 在上面的问题表述中，学习的目标在于使期望风险最小化，但是，由于我们 “j 以利用的信息只有样本( 2 1 ) ，( 2 2 ) 式的期望风险并无法计算，因此传统的学习 方法中采用了所谓经验风险最小化( e r m ) 准则，即用样本定义经验风险 尺。，( w ) = 告上( m ，厂( 一，w ) ) ( 2 4 ) i = 1 作为对( 2 2 ) 式的估计设计学习算法使它最小化。对损失函数( 2 3 ) ，经验风险就 是训练样本的错误率。 事实上，用e r m 准则代替期望风险最小化并没有经过充分的理论论证，只是 直观上合理的想当然做法，但这种思想却在多年的机器学习方法研究中占据了主 要地位。人们多年来将大部分注意力集中到如何更好地最小化经验风险上，而实 际上即使可以假定当月趋向于无穷大时( 2 4 ) 式趋近于( 2 2 ) 式，在很多问题中的 样本数目也离无穷大相去甚远。那么在有限样本下e r m 准则得到的结果能使真实 风险也较小吗? 2 1 3 复杂性与推广能力 e r m 准则不成功的一个例子是神经网络的过学习问题。开始，很多注意力都 集中在如何使月( w ) 更小，但很快就发现，训练误差小并不总能导致好的预测效 果。某些情况下，训练误差过小反而会导致推广能力的下降，即真实风险的增加， 这就是过学习问题。 之所以出现过学习现象，一是因为样本不充分，二是学习机器设计不合理 这两个问题是互相关联的。设想一个简单的例子假设有一组实数样本“y ，y 第二章统计学习理论和支撑矢量机算法 取值在 0 ，1 之间那么不论样本是依据什么模型产生的，只要用函数 f ( x ，口) = s i n ( 以) 去拟合它们( 是待定参数) ，总能够找到一个a 使训练误差为 零，但显然得到的“最优”函数并不能正确代表真实的函数模型。究其原因，是试图 用一个十分复杂的模型去拟合有限的样本，导致丧失了推广能力。在神经网络中， 若对有限的样本来说网络学习能力过强，足以记住每个样本，此时经验风险很快 就可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预测。学 习机器的复杂性与推广性之间的这种矛盾同样可以在其它学习方法中看到。 由此可看出，有限样本情况下 1 1 经验风险最小并不一定意味着期望风险最小； 2 1 学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目的样本 相适应。我们需要一种能够指导我们在小样本情况下建立有效的学习和推广方法 的理论。 2 2 统计学习理论的核心内容 统计学习理论就是研究小样本统计估计和预测的理论，主要内容包括四个方 面引： 1 ) 经验风险最小化准则下统计学习一致性的条件： 2 ) 在这些条件下关于统计学习方法推广性的界的结论： 3 ) 在这些界的基础上建立的小样本归纳推理准则： 4 ) 实现新的准则的实际方法( 算法) 。 其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是v c 维。 2 2 1v c 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有 关函数集学习性能的指标，其中最重要的是v c 维( v a p n i k c h e r v o n e n k i s d i m e n s i o n ) 。模式识别方法中v c 维的直观定义是：对一个指示函数集如果存在 h 个样本能够被函数集中的函数按所有可能的2 6 种形式分开，则称函数集能够把h 个样本打散；函数集的v c 维就是它能打散的最大样本数目h 。若对任意数目的样 本都有函数能将它们打散，则函数集的v c 维是无穷大。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。 遗憾的是，目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的 函数集知道其v c 维。比如在n 维实数空间中线性分类器和线性实函数的v c 维是 n + l ，而上一节例子中f ( x ，口) = s i n ( a x ) 的v c 维则为无穷大。对于一些比较复杂的 支撑矢量机混合算法的研究 学习机器( 如神经网络) ，其v c 维除了与函数集( 神经网结构) 有关外，还受学 习算法等的影响其确定更加困难。对于给定的学习函数集，如何( 用理论或实 验的方法) i , t g nv c 维是当前统计学习理论中有待研究的一个问题 1 2 1 。 2 2 2 推广性的界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之 间的关系，即推广性的界阻1 。关于两类分类问题结论是：对指示函数集中的所 有函数( 包括使经验风险最小的函数) 经验风险r 。“w ) 和实际风险r ( w ) 之间以 至少1 一玎的概率满足如下关系( 1 3 3 ： r ( w ) r 一( w ) + h ( 1 n ( 2 n h ) + 1 ) - l n ( r 4 ) ) ( 2 - 5 ) ， 其中h 是函数集的v c 维h 是样本数。 这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验 风险( 训练误差) ，另一部分称作置信范围它和学习机器的v c 维及训练样本数 有关。可以简单地表示为： r ( w ) j 乙。( w ) + 中( 厅，h )( 2 - 6 ) 它表明，在有限训练样本下，学习机器的v c 维越高( 复杂性越高) 则置信范围越 大，导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习 现象的原因。机器学习过程不但要使经验风险最小，还要使v c 维尽量小以缩小置 信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。 需要指出，推广性的界是对于最坏情况的结论，在很多情况下是较松的，尤 其当v c 维较高时更是如此( 当h n o 3 7 时这个界肯定是松弛的，当v c 维无 穷大时这个界就不再成立) 。而且，这种界只在对同一类学习函数进行比较时有 效，可以指导我们从函数集中选择最优的函数，在不同函数集之间比较却不一定 成立。v a p n i k 指出阻3 ，寻找更好地反映学习机器能力的参数和得到更紧的界是学 习理论今后的研究方向之一。 2 2 3 结构风险最小化 上面的结论看到，e r m 原则在样本有限时是不合理的，我们需要同时最小化 经验风险和置信范围。其实，在传统方法中，选择学习模型和算法的过程就是调 整置信范围的过程，如果模型比较适合现有的训练样本( 相当于h 九值适当) ， 则可以取得比较好的效果。但因为缺乏理论指导，这种选择只能依赖先验知识和 经验，造成了如神经网络等方法对使用者“技巧”的过分依赖。 第二章统计学习理论和支撑矢量机算法9 统计学习理论提出了一种新的策略即把函数集构造为一个函数子集序列， 使各个子集按照v c 维的大小( 亦即o 的大小) 排列；在每个子集中寻找最小经 验风险，在子集问折衷考虑经验风险和置信范围，取得实际风险的最小，如图2 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 或译有序风险 最小化) 川即s r m 准则。统计学习理论还给出了合理的函数子集结构应满足的 条件及在s r m 准则下实际风险收敛的性质”3 。 欠学习斗过学习 鋈髫一 函数寨子集，墨c c 墨v c 维t i 与王 | 图2 1 有序风险最小化示意图 实现s r m 原则可以有两种思路，一是在每个子集中求最小经验风险，然后选 择使最小经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子集 数目很大甚至是无穷时不可行。因此有第二种思路，即设计函数集的某种结构佼 每个子集中都能取得最小的经验风险( 如使训练误差为0 ) ，然后只需选择选择适 当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。 支撑矢量机方法实际上就是这种思想的具体实现。 2 3 支撑矢量机分类机理 支撑矢量机简称s v m ，是统计学习理论中最年轻的内容，也是最实用的部分。 其核心内容是在1 9 9 2 到1 9 9 5 年间提出的【2 4 ，m 1 4 ，3 4 1 ，目前仍处在不断发展阶段。 1 0支撑矢量机混合算法的研究 2 3 1 广义最优分类面 s v m 是从线性可分情况下的最优分类面发展而来的，基本思想可用图2 - 2 的 两维情况说明。图中，实心点和空心点代表两类样本，h 为分类线，h i h 2 分别为 过各类中离分类线最近的样本且平行于分类线的直线。它们之间的距离叫做分类 间隔( m a r g i n ) 。所谓最优分类线就是要求分类线不但能将两类正确分开( 训练错 误率为0 ) ，而且使分类间隔最大。分类线方程为x - w + b = o ，我们可以对它进行 归一化，使得对线性可分的样本集( 乩蝴，i = 1 ，n ，x r 4 ，y ( + 1 ，一1 ) ，满足 y ， ( w 工，) + b 】一1 2 0 ，i = l ，- ，n ( 2 9 ) 图2 2 线性司分情况f 的最优分类线 此时分类问隔等于2 11 1w 扎使间隔最大等价于使i | w1 12 最小。满足条件( 2 9 ) 且 使0wi l2 2 最小的分类面就叫做最优分类面，h i i h 2 上的训练样本点就称作支持矢 量。 使分类间隔最大实际上就是对推广能力的控制，这是s v m 的核心思想之一。 统计学习理论指出阻1 ，在n 维空间中，设样本分布在一个半径为r 的超球范围内， 则满足条件| | wl ls a 的正则超平面构成的指示函数集f i x , w b ) = s g n ( - x ) + 6 ) ( s g n ( ) 为符号函数) 的v c 维满足下面的界 h ! r a i n ( r 2 a 2 n ) + 1( 2 1o ) 因此使wi i2 最小就是使v c 维的上界最小，从而实现s r m 准则中对函数复杂性 的选择。 利用l a g r a n g e 优化方法可以把上述最优分类面问题转化为其对偶问题引， 即在约束条件 m 口= o ( 2 1 1 a ) i _ l 和 a i 兰0 ，i = l ，n( 2 - 11b ) 下对m 求解下列函数的最大值 第二章统计学习理论和支撑矢量机算法 q ( a ) ：主旷导主q 吁y , y j ( 一 1 = 1 i , j = l ( 2 - 1 2 ) 为与每个样本对应的l a g r a n g e 乘子。这是一个不等式约束下二次函数寻优的问 题存在唯一解。容易证明，解中将只有一部分( 通常是少部分) 不为零，对应 的样本就是支持向量。解上述问题后得到的最优分类函数是 厂( x ) = s g n ( w x ) + 6 ) = s g n 口j 咒( _ - x ) + 6 ) ( 2 - 1 3 ) 式中的求和实际上只对支持向量进行。6 是分类阈值，可以用任一个支持向量( 满 足( 2 9 ) 式中的等号) 求得，或通过两类中任意一对支持向量取中值求得。 下面通过一个模式识别问题来说明s v m 算法。 设数据集合c l a s s l 和c l a s s 2 是线性可分的，即存在( 6 ) ，使 w - x j + 6 o ，v x f c l a s s l ， w 而+ 6 o ，v x 。c l a s s 2 分类的目的是寻求( j 6 ) ，最佳分离c l a s s l 和c l a s s 2 ，此时假设空间由所有的 6 = s g n ( w x ) + b ) 组成。为减少分类平面的重复，对( 6 ) 进行如下约束： m i n l w x j + b i = 1 i = 1 , 2 月 ( 2 - 1 3 1 ) 满足( 2 1 3 1 ) 的超平面称为典型超平面，可以证明典型超平面集合的v c 维是 n + i 即所有自由参数的数目。如果x 1 j 耽，h 位于n 维单位球内，集合 无。= s g n ( w x + 6 ) ；j j 叫j a ) 的v c 维h 满足： hs m i n ( a 2 ，n ) + 1( 2 1 3 2 ) 当数据点轧x 2 , x n 位于半径为r 的球内时，上式变为： h 茎r a i n ( r 2 a 2 n ) + l( 2 1 3 3 ) 注意到点z 到( 州6 ) 确定的超平面距离为 m ，w 6 ) = 锴 ( 2 1 3 4 ) 根据约束条件( 2 - 1 3 1 ) 可知，典型超平面到最近数据点的距离为1 1 1w l i ，显然如 果1 1 w lj _ a ，典型平面到最近数据点的距离必然大于或等于l 圳a 实际上此时典 型超平面已将分类的对象由单纯的数据点变为数据点的l 圳a0 球形领域。 对线性可分的情形( 即经验风险为o ) ，求最佳( 6 ) 归结为下列= 次规划问 题： 1 2 支撑矢量机混合算法的研究 m i n + h 2(2-135)wg, 、， s f 儿( w x ，+ b ) li = 1 , 2 ，n 根据( 2 1 3 3 ) 式问题( 2 1 3 5 ) 的意思是指在经验风险为0 的情形下，使 v c 维的界最小化，从而最小化v c 维，这正是结构风险最小化原理。根据( 2 一1 3 4 ) 式，最小化忡酽等价于寻求一种特殊的超平面，它是数据集合c l a s s l 和c l a s s 2 凸 包之问沿垂直于自己方向的距离最大故s v m 有时也称为最大边缘( m a x i m u m m a r g i n ) 算法，可以用下图来说明边缘大小和泛化性能之间的关系： 图2 3 ( a ) 小边缘分类示意图图2 3 ( b ) 大边缘分类示意图 在线性不可分的情况下，可以在条件( 2 9 ) r 9 增加一个松弛项6 三0 ，成为 只【( w - t ) + b 一1 + 毒0 ，i = 1 ，1 ( 2 - 1 4 ) 将目标改为求最小 ( w f ) ：细卅2 + c ( 主鼻) ( 2 - 1 5 ) 其中c 为一正常数。上式的第1 项使样本到超平面的距离尽量大，从而提高泛 化能力：第2 项则使误差尽量小。为求解这个优化问题，引入拉格郎日函数 l ( w ，b ，掌，口，) = 1 2 w w + c 参一坼【 ( w x i + 6 ) 一1 + 毒】一 点 ( 2 1 6 ) 其中口，o ，y o ，f _ 1 ，k 函数上应对国和咒最大化，且对w , b 和6 最小化。函数工的极值应满足条件 兰上= o ，旦上= o ，昙l = 0 ( 2 1 7 ) 却c o b 7 a 占? 、 从而得到 第二章统计学习理论和支撑矢量机算法1 3 吼y 。= 0 w = q y 工 c 一口一 = 0 ，i 21 ，k 将以上三式代入式( 2 1 6 ) 可以得到优化问题的对偶形式，最大化函数 1pp ( a ) = 一去q y 。y 小。x j ) + q 二f j = l j - 】 ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) ( 2 2 1 ) 其约束为 口，y ，= 0 0 s 口，c ，i = 1 ，k ( 2 2 2 ) j = 1 这是一个典型的二次优化问题，已有高效的算法求解，w 可由式( 2 1 9 ) 求出。 按照优化理论的k u h n t u c k e r 定理，在鞍点，对偶变量与约束的乘积为0 ，即 口， ( w + b ) 一1 + 善， = 0 i = 1 ，k ( 2 - 2 3 ) 一孝，= 0 i = 1 ，k ( 2 - 2 4 ) 由式( 2 - 2 3 ) 可以看出，非o 的饼所对应的样本仅由最靠近超平面的样本组成，这 些样本完全确定了超平面，因此称为支持向量。对于0 国 c ，由式( 2 2 0 ) 可知0 曲售-皇山nu 第三章一种基于最小支撑矢量集的s v m 算法 i 盯：3 0消除线性相关矢量方法( 个数)2 75 6 减少率 4 4 9 4 2 3 表3 3 使用r b f 核 闰3 , 3 使用r b f 核 从表31 3 3 可以看出在数据量较大时或核函数参数不同时均有冗余的支撑 矢量，在计算时如能把它们去掉的话，就减少了计算量，也就意味着减少了计算 时间。 3 5 结论 从仿真结果可以看出多数情况下支撑矢量集内部都有线性相关的支撑矢量， 但是线性相关的支撑矢量的数量是根据实际问题与核函数的不同而不同的，但是 有个大概的规律可寻，如：多项式核随着