（计算机应用技术专业论文）支持向量机参数优化研究.pdf

r e s e a r c ho fp a r a m e t e r o p t i m i z a t i o nf o r s u p p o r tv e c t o rm a c h i n e at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em s d e g r e ei nc o m p u t e ra p p l i c a t i o nt e c h n o l o g y b y l ij i a o p o s t g r a d u a t ep r o g r a m c o m p u t e r s c i e n c ed e p a r t m e n t c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：d a is h a n g p i n g a c a d e m i ct i t l e ：a s s o c i a t ep r o f e s s o rs i g n a t u r e a p p r o v e d m a y , 2 0 1 1 ： ： 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：日期：沙f 年月2 彳日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：媚 日期加1 1 年j 月沾日 导师签名： 碳吁 日期：乒，i j 年y , q 彩日 规定享受相关权益。回童途塞握銮厦溢卮；旦圭生；旦= 生；旦三生筮查! 作者签名：蠲抑签名：碱、坪 日期： 口1 1 年s 月瑶日 日期：oo 年厂月夕日 ： ： 硕士学位论文 m a s t e r st h e s i s 摘要 支持向量机广泛地应用于分类和回归问题，其参数的选择对分类和回归的效果 有较大的影响，目前还没有确定的理论指导参数的选择。而遗传算法是模拟自然 界中的遗传和进化现象而形成的一种自适应全局搜索算法，粒子群算法是基于群体 智能的启发式全局搜索算法，遗传算法和粒子群算法都是广泛运用的智能优化算 法，本文分别利用遗传算法和粒子群算法研究支持向量机参数的选择问题，避免实 际应用中因参数选择不当导致实验效果不理想，本文主要工作如下： ( 1 ) 研究利用遗传算法来优化支持向量回归机的惩罚参数c ，径向基核函 数参数0 以及损失函数参数e ，并进行仿真实验，并与以往只是优化支持向量回 归机的惩罚参数c ，径向基核函数参数0 两个参数做比较，前者提高了回归预测的 精度。 ( 2 ) 研究利用粒子群算法来优化e 支持向量回归机的惩罚参数c ，径向基核 函数参数0 以及损失函数，并进行仿真实验。仿真实验采取同一样本集：u c i 的 混凝土抗压强度，仿真实验结果显示基于遗传算法的参数优化算法比基于粒子群的 参数优化取得了更好的预测效果，而基于粒子群的参数优化算法能够较快地收敛。 并与传统的非启发式的网格搜索寻优算法进行比较，利用遗传算法和粒子群算法寻 优显著地提高了预测的精度。 支持向量机参数的选择对实际应用有重大的影响，仿真实验显示选择参数优化 算法对回归预测的精度有了显著的提高，所以针对具体的实际问题，应考虑多种方 法选择合适的支持向量机参数进而提高推广能力。 关键词：支持向量机：参数优化；遗传算法；粒子群算法 一， 硕士学位论文 m a s t e r st h e s i 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 ei sag e n e r a ll e a r n i n gm e t h o db a s e do ns t a t i s t i c a ll e a r n i n g t h e o r yh a v i n gs h o w nal o to fp e r f o r m a n c e ss u p e r i o rt ot h et r a d i t i o n a lm e t h o d s c u r r e n t l y i td e v e l o p sr a p i d l yi nt h ea l g o r i t h mr e s e a r c ha n d p r a c t i c a la p p l i c a t i o n s n l ep a r a m e t e r so f s u p p o r t v e c t o rm a c h i n eh a v eg r e a ti n f l u e n c eo nc l a s s i f i c a t i o na n dr e g r e s s i o n t h e r ei sn o t h e o r yt oc l e a rp a r a m e t e rs e l e c t i o n g e n e t i ca l g o r i t h mi m i t a t e sn a t u r a li n h e r i t a n c ea n d e v o l u t i o n a r yp h e n o m e n o na n df o r m sag l o b a ls e a r c ha l g o r i t h m p a r t i c l es w a r ma l g o r i t h m i sah e u r i s t i cg l o b a ls e a r c ha l g o r i t h mb a s e do ng r o u p i n t e l l i g e n t g e n e t i ca l g o r i t h ma n d p a r t i c l es w a r ma l g o r i t h ma r ew i d e l yu s e di ni n t e l l i g e n to p t i m i z a t i o na l g o r i t h m t h i s t h e s i ss t u d i e s s u p p o r tv e c t o rm a c h i n ep a r a m e t e rs e l e c t i o np r o b l e mu s i n gg e n e t i c a l g o r i t h ma n dp a r t i c l es w a r ma l g o r i t h m ，a v o i d i n ge x p e r i m e n tr e s u l ti sn o ti d e ac a u s e db y i m p r o p e rp a r a m e t e r t h er e s e a r c h e so ft h et h e s i sa r ea sf o l l o w s ： ( 1 ) i to p t i m i z e st h ep u n i s h m e n tp a r a m e t e rc ，t h ep a r a m e t e roo fi 也fk e r n e la n d t h ep a r a m e t e r o ft h el o s sf u n c t i o nu s i n g g e n e t i ca l g o r i t h m t h e nw ed oe x p e f i m e n t st o p r o v et h ee f f e c t c o m p a r e dw i t ho p t i m i z a t i o n so ft h ep u n i s h m e n tp a r a m e t e rca n dt h e p a r a m e t e r oo fi 强fk e r n e l ，t h et h r e ep a r a m e t e ro p t i m i z a t i o n ss h o w sb e t t e rp r e d i c t i v e a c c u r a c y ( 2 ) i to p t i m i z e st h ep u n i s h m e n tp a r a m e t e rc ，t h ep a r a m e t e r so fi 也fk e r n e lf u n c t i o n a n dt h ep a r a m e t e reo ft h el o s sf u n c t i o n u s i n gp a r t i c l es w a l t l la l g o r i t h m w ，ed o e x p e r i m e n t su s i n gt h ep a r a m e t e r so p t i m i z a t i o na l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m ， b a s e do np a r t i c l es w a r ma l g o r i t h ma n db a s e do n g r i ds e a r c h n eo p t i m i z a t i o na l g o r i t h m s u s et h es a m es a m p l es e t ：u c ic o n c r e t ec o m p r e s s i v es t r e n g t h 1 1 1 er e s u l t ss h o wt h a tt h e p a r a m e t e r so p t i m i z a t i o nb a s e do ng e n e t i ca l g o r i t h ma c h i e v eb e t t e re f f e c tt h a no t h e r s t h e p a r a m e t e r so p t i m i z a t i o nb a s e do np a r t i c l es w a r ma l g o r i t h mc a nc o n v e r g er a p i d l y t h e p a r a m e t e r so p t i m i z a t i o nb a s e do ng r i ds e a r c hg e t st h ew o r s tp r e d i c t i o n ，n l es e l e c t i o no fp a r a m e t e r st o s u p p o r tv e c t o rm a c h i n eh a ss i g n i f i c a n th a f t u e n c e e x p e r i m e n t ss h o wt h a tc h o o s i n gp a r a m e t e ro p t i m i z a t i o na l g o r i t h mc a l ls i g n i f i c a n t l y i n c r e a s et h ea c c u r a c yo fr e g r e s s i o nf o r e c a s t s ow es h o u l dc o n s i d e rt h ev a r i o u sm e t h o d s t oc h o o s et h e a p p r o p r i a t ep a r a m e t e r so fs u p p o r tv e c t o rm a c h i n ea n d i m p r o v e g e n e r a l i z a t i o na b i l i t y k e y w o r d s ：s u p p o r tv e c t o rm a c h i n e ；p a r a m e t e rs e l e c t i o n ；g e n e t i ca l g o r i t h m ；p a r t i c l e s w a r ma l g o r i t h m h ： 硕士学位论丈 m a s t e r st h e s i s 摘要 a b s t r a c t 目录 第一章绪论 i i 1 1 研究背景及意义1 1 2 国内外研究概况”2 1 3 论文的主要内容”4 第二章统计学习与支持向量机 2 1 统计学习理论基础”5 2 1 1 经验风险最小化5 2 1 2 复杂性与推广能力6 2 1 3v c 维7 2 1 4 结构风险最小化8 2 2 支持向量机理论9 2 2 1 广义最优超平面9 2 2 2 支持向量机思想“1 2 2 2 3 常用核函数1 4 2 2 4 支持向量回归机1 4 2 3 本章小结一1 5 第三章基于遗传算法的支持向量回归机参数优化方法 1 6 3 1 遗传算法概述16 3 1 1 遗传算法理论“1 6 3 1 2 遗传算法的应用2 1 3 2 基于遗传算法的支持向量回归机参数优化g a s v r 2 2 3 2 1 支持向量回归机参数”2 2 3 2 2g a s v r 算法”2 3 3 2 3g a s v r 算法的改进2 5 3 3 数值实验2 6 3 3 1 实验过程”2 6 3 3 2 实验结果与分析2 8 3 4 本章小结31 ： 硕士学位论文 m a s t e r st h e s l s 第四章基于粒子群算法的支持向量回归机参数优化方法3 2 4 1 粒子群算法概述3 2 4 1 1 粒子群算法理论3 2 4 1 2 粒子群算法的应用”3 5 4 2 基于粒子群算法的支持向量回归机参数优化p s o s v r ”3 5 4 2 1p s o s v r 算法3 5 4 2 2p s o s v r 算法优化c ，o ，3 6 4 3 数值实验3 7 4 3 1 实验过程”3 7 4 3 2 实验结果与分析3 8 4 4p s o s v r 、网格搜索、g a s v r 、优化c ，o ，对比分析3 9 4 4 1 网格搜索3 9 4 4 2 实验结果比较”4 0 第五章总结与展望 参考文献 攻读硕士学位期间参加的科研项目与工作 致谢 4 2 4 3 4 8 硕士学位论文 m a s t e r st h e s i s 第一章绪论 1 1 研究背景及意义 随着计算机技术的发展，计算智能化的要求也越来迫切，机器学习正是这样的 一个学科，让机器经过训练学习来拥有智能。简单来说就是让机器能够根据现有的 数据来研究发现其中蕴含的规律，利用规律来更好地指导未知的情况或者推测未知 的数据。经过几十年研究者的努力，机器学习获得了较大的发展。机器学习是在数 学理论统计学习的基础上发展起来的。最初通过观察研究演绎推理得到的统计学习 理论都是在样本数目趋向于无穷大的条件下才能成立的，但是在我们遇到的实际问 题中，样本数目往往是有限的，无法满足统计学理论的要求，所以传统统计学的方 法在实际问题中并不能取得理论中所能达到的效果，其表现并不能使人满意。随着 统计学的进一步发展，为了满足实际的需求，产生了新的统计学习理论并出现了基 于新理论的学习方法。统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 是利用小样本数 据研究机器学习相关内容的理论，已成为小样本预测学习的最佳理论。统计学习理 论的创始人之一、国际知名学者v v a p n i k 等人从2 0 世纪7 0 年代开始进行统计学习 理论的研究【l 】，随着其研究的不断深入和发展，也由于这个时期神经网络等方法的 研究没有从本质上推进对学习过程本质的认识，统计学习理论开始吸引更多的学 者，逐渐受到广泛的重视【2 j 【3 j 。 统计学习理论为解决有限数目样本的学习问题提供了统一的理论框架，使神经 网络结构选择问题、局部极小点问题等原来难以解决的问题得到了很好的解决；它 寻求的是现有信息情况下的最优解，并在此理论基础上发展起来一种新的学习方法 支持向量机1 4 】( s u p p o r tv e c t o rm a c h i n e ) 。支持向量是v v a p n i k 等人于1 9 9 5 年 首次提出来的，可用于模式分类和非线性回归，迅速发展成为一种基于统计学习的 机器学习方法，是近年来机器学习研究领域的一项重大成果。 支持向量机在解决实际问题拥有出色的表现，成为人们研究的热点内容，它的 出现有力地推动了机器学习的快速发展。在国内，有学者在八十年代注意到统计学 习的理论成果【5 】，但之后没有太多的注意，现在又逐渐成为研究的热点。 与支持向量机坚实的数学理论基础相比，其应用研究的发展相对缓慢，大多是 仿真实验。目前对s v m 的研究主要有以下两个方面：一是对s v m 算法本身的研究， 提出改进的方法，进步完善算法的性能，比如缩短训练的时间和多类分类问题等； 二是应用于新的领域，比如生物基因领域。s v m 本质上是一种非线性数据分析处 硕士学位论文 m a s t e r st h e s i s 理方法，其在图像处理、数字信号处理、智能控制、数据挖掘等方面有巨大的应用 前景。由于s v m 在实际应用中优越的性能表现，越来越多的研究者使用它进行专 业的研究，所以研究s v m 以及对s v m 参数的改进优化在实际的应用中还是有较大 的意义和价值。 1 2 国内外研究概况 支持向量机自1 9 9 5 年提出后，掀起了研究的热潮，由于支持向量机的巨大应 用价值，目前在算法理论研究和实践应用两方面都处于快速发展的时期。在算法理 论研究方面，许多学者对其提出了改进的算法以及对s v m 中核函数的构造研究。 其中对算法中参数的选取，许多研究者给出了不同的方法，其中主要的有： ( 1 ) 网格法 网格法是支持向量机中寻找合适的参数一种常用方法，参数的选择步骤如下： 首先设定所求参数变化的范围，然后设定参数变化的步长，这些参数值按照设定的 步长在参数空间中变化，每一对参数组合求出判断函数的值，搜索整个参数设定的 空间，求出判断函数的最值。这种方法思想简单，对于参数较少的情况下能够取得 较好的效果，但是在实际应用中，整个计算过程比较复杂，而且比较费时。文献 6 】 研究了利用网格搜索法确定支持向量机核函数的参数，提高了支持向量机的分类准 确率。 ( 2 ) 智能优化算法 函数寻优是机器学习领域中广泛研究的问题，我们把支持向量机参数的选择问 题作为函数的寻优过程。对于某一给定的样本集，s v m 的性能主要受模型参数的 影响。c h a p e l l e 和v a p n i k 指出：学习算法决定于参数，参数控制着假设空间的规模 以及假设空间的搜索方式。c h e r k a s s k y 认为：s v m 模型的性能依赖于参数的设置， 如何选择参数是应用s v m 的主要问题。因此，参数选择是s v m 模型选择的关键。 文献【7 研究了利用蚁群算法优化支持向量的核参数和惩罚参数，并应用于青霉素发 酵过程的建模研究，取得了较高的精度；文献 8 】利用遗传算法进行支持向量机的分 类和聚类研究，文献【9 】利用粒子群算法优化支持向量机的分类问题，并与网格法进 行比较，取得了较高的分类准确率 此外文献【1 0 】研究了支持向量机的核函数的构造方法，还有构造混合核函数的 研究等。 s v m 是统计学习理论的具体实现，由于其卓越的性能，它不仅在算法方面有 广泛深入的研究，而且在模式识别、函数逼近、时间序列预测、故障识别、信用评 2 一， 硕士学位论文 m a s t e r st h e s i s 价等领域都有较好的应用。 ( 1 ) 模式识别 模式识别是人类的一项基本智能模式，随着人工智能的兴起，其迅速发展成为 一门新的学科，模式识别是对表示事物或现象的现实信息进行分析和处理，总结或 者揭示蕴含在其中的规律，以使人们能够对事物或某种现象进行辨析、分类和解释， 是人工智能的重要组成部分。近年来，支持向量机最重要也是最成功的应用之一就 是模式识别，特别是在人脸、指纹识别方面，成为支持向量机的一大研究热点。在 文献【1 l i d 0 ，使用支持向量机来解决指纹识别的问题。文献 1 2 1 使用支持向量机来研 究生物基因数据分析和基因编码，取得了较好的效果。在文献【1 3 】中，作者基于支 持向量机对网络用户身份验证研究表明非法用户的通过率和合法用户的拒绝率相 较传统的神经网络方法要小得多。文献 1 4 1 研究了基于内容的语音分类和检索，表 明支持向量机在语音检索方面与传统语音检索具有更智能的优势。文献 1 5 1 研究了 基于支持向量机的图像检索问题，研究表明图像内容的检索相对于传统的检索方法 在准确率方面有较大的提高。 ( 2 ) 函数逼近 文献 1 6 研究了基于支持向量机的函数逼近方法。文献 1 7 】通过分形差值迭代一些 点，接着用支持向量机来拟合函数，有效地解决了图像的断裂现象。 ( 3 ) 时间序列预测 时间序列预测法就是一种历史资料延伸预测，它是将某种统计指标的数值，按 照时间顺序所形成的数列。它根据已有时间序列进行推理，预测下一段时间或者若 干时间段内所可能发生的情况。文献【1 8 】应用支持向量机算法进行金融领域时间序 列数据的预测。文献 1 9 1 利用基于构造核函数的支持向量机进行金融时间序列的分 析。电力负荷的预测也是一种时间序列预测的，文献 2 0 2 4 都研究了应用支持向量 机进行短期的电力负荷预测，取得了较高的预测精度。 ( 4 ) 故障诊断 随着工业的发展，工业领域也越来越多地引入人工智能来检测工业生产过程， 以及工业设备的使用情况。文献【2 5 将支持向量机应用到故障预测的研究中，取得 了较好的效果。文献【2 6 】应用支持向量机的分类方法来诊断电机设备，区别显示设 备的正常状态和故障状态。文献 2 7 】将支持向量机应用于电路故障的诊断中，对电 路故障的定位有较大的帮助。文献 2 8 】将支持向量机应用于汽车轴承的检测，能有 效地防范风险。 ( 5 ) 信用评价 硕士学位论文 m a s t e r st h e s i s 随着金融市场的发展，一个金融主体的信用评价越来越重要，它能有效地帮投 资者规避风险。文献 2 9 1 应用支持向量机对我国上市公司的信用进行分类，达到了 9 0 的准确率。文献【3 0 】应用支持向量机方法对美国的公司根据公司业务报告中的 相关经济属性进行信贷分类。文献【3 1 3 2 】应用支持向量机算法对商业银行进行信 用评估。 1 3 论文的主要内容 近年来，基于统计学习理论的支持向量机获得了广泛的应用，本文首先介绍了 支持向量机的发展状况、理论基础和算法思想，重点研究对支持向量机参数进行优 化，提高性能。本文采用遗传算法和粒子群算法对支持向量回归机的参数进行优化， 通过实证验算证明优化选择的参数能有更高的预测精度。 第一章：绪论。介绍了本文的研究背景和实际意义，概述了支持向量机近几年 快速的发展和广泛的应用领域； 第二章：简要介绍机器学习的表示，统计学习理论的基本内容，并介绍了支持 向量回归机的理论基础； 第三章：首先介绍了遗传算法的基本原理，然后讨论了支持向量回归机参数： 惩罚参数c ，径向基核函数参数。以及损失函数e 对其性能的影响，提出基于遗传 算法的支持向量回归机参数优化算法并对上述参数进行优化，并进行仿真实验； 第四章：首先介绍了粒子群算法的基本原理，然后讨论利用粒子群算法对支 持向量回归机的上述参数进行优化，并利用第三章所使用的样本对算法性能仿真实 验。最后把网格搜索优化参数、遗传算法优化参数和粒子群优化参数方法进行比较； 第五章：总结与展望，总结本文所做的工作，并指出进一步的工作，为未来的 研究指明方向。 4 硕士学位论文 m a s t e r st h e s i s 第二章统计学习与支持向量机 2 1 统计学习理论基础 传统统计方法是基于样本数目足够大的条件，也就说对于解决实际问题采取的 方法也只有满足上述条件下，此方法的性能才有一定的稳定性，有相应的理论基础。 而在我们遇到的实际问题中中，样本的数目常常是有限的，无法满足样本数目足够 大的条件，这样会使传统统计方法都无法取得理想的效果。由于传统统计学的条件 要求在实际问题中无法满足，促使我们研究新的方法。统计学习理论是由v a p n i k 等人提出的，并且其研究促进了统计学习理论的不断发展和完善，它为解决实际问 题中有限样本数目下的机器学习提供了理论基础，能帮助解决神经结构选择问题、 局部极小点，维数灾难等问题，成为机器学习研究的又热点。 2 1 1 经验风险最小化 机器学习的目标是对未知结果做出尽可能准确的预测，它根据给定的样本数据 寻找自变量和因变量之间的函数映射关系。转换为数学上的表述如下：因变量y 与 自变量x 存在着映射关系，那么机器学习也就是根据独立同分布样本序列 ( x 。，y ，) ，( x ：，y ：) ，( x 。，y 。) ，在一个函数组 厂( x ，w ) ) 中寻求函数 厂( x ，w o ) ) 对映射 关系进行估计，通过训练得到的 f ( x ，w o ) 能够满足使r ( w ) r ( w ) = il ( y ，f ( x ，w ) ) d f ( x ，j ，)，1 、 o 二1 达到最小。l ( y ，f ( x ，w ) ) 是用f ( x ，w ) 对y 进行预测而形成的损失造成的误差，对于 不同的实际问题我们可以定义不同的损失函数。例如在函数拟合问题中，j ，是因变 量，x 是自变量，则损失函数可以定义为 l ( y ，f ( x ，w ) ) = ( y - f ( x ，w ) ) 2 ( 2 2 ) 即是采用平方误差最小化原则。 机器学习的目标是使期望风险最小化，也就是要让公式( 2 1 ) 取得最小值，为 了达到上述目的，除了依赖针对不同的问题定义的损失函数，还必须依赖概率分布 函数f ( x ，y ) 。可是在实际的问题中我们只获取了样本，能够利用的只有样本的信 息，不能够计算出概率分布函数，所以公式( 2 1 ) 期望风险便无法计算。根据概率 论中大数定理的思想：事件发生的频率依概率收敛于事件的概率，大数定理以数学 理论形式表达了频率的稳定性。在传统的学习方法中采取了用算术平均代替公式 硕士学位论文 m a s t e r st h e s i s ( 2 1 ) 的期望误差，定义了如下公式( 2 3 ) 1 三 r 。胛，( w ) = 三( y ，f ( x ，1 4 ) ) ( 2 3 ) ，l j = i 来替代公式( 2 1 ) 。经验风险r ( w ) 是用我们得到的样本数据来表示的。而经验风 险最小化原则就是用对参数w 求得的公式( 2 3 ) 的最小值代替公式( 2 1 ) 的最小 值。上面所采取的方法存在如下的问题：并没有相应的理论能够保证使r 栅- 最小的 w l 等于使r 最小的w 2 同时也不能一定会有r e m p 趋近r 。所以在求解优化问题时 用经验风险最小化代替期望风险最小化在理论方面并没有可靠的依据。 2 1 2 复杂性与推广能力 机器学习是通过对己知样本数据的学习寻找到数据内在的函数依赖关系，从而 能够对未来的数据进行预测判断。推广能力( 泛化能力) 就是指对未来数据的预测判 断能力。 在早期的研究中，人们使用经验风险r 锄- 代替期望风险r 后，一直以来都是把 较多的工作集中在使融唧更小。但是出现了例外的情况，当r 咖- 较小时得到的预测 效果却不好，降低了模型的推广能力。其中神经网络的过学习问题就是一个典型的 例子。学习机器设计不合理或者学习样本不充分是发生过学习问题的原因，追根究 底，其根本的原因是用十分复杂的模型来拟合有限数目的样本，这样训练数据的误 差很小，可是把得到的模型应用于测试数据，得到的误差很大，这样模型的推广能 力很差。在神经网络的训练中，如果采用的学习方法对样本的学习能力过强，那 么其经验风险可以在较短的时间内收敛到较小的数值，但对新的样本进行预测时却 无法得到理想的效果。有这样一种情况，已知来自一个复杂模型的样本数据序列， 对于此序列我们用相对比较简单的模型通常能够得到比较理想的预测效果，虽然它 们的真实模型是比较复杂的，这主要是由于样本数据的有限性。文献 3 3 】介绍了上 述现象，首先用y = z 2 这个模型产生l o 个样本数据，对于此样本数据分别用一次 函数和二次函数来训练。实验结果却显示一次函数预测效果好于二次函数，虽然 真实的模型是二次函数，可是实验结果却是一次函数更好，主要原因是样本数据的 有限性。 在其他的学习方法也出现了学习机器的复杂性和推广性之间的矛盾中。由于实 际问题通常都是有限样本的情况，所以二者之间的矛盾似乎是不可调和的，为了减 小上述矛盾的影响，人们研究了多种办法来调和这一矛盾，比如通过交叉验证等方 法进行模型选择以及控制复杂度；或者在训练中对学习模型的复杂度进行惩罚等， 6 嚣、 硕士学位论文 m a s t e r st h e s i s 但是这些方法目前尚缺乏完善的理论基础，多带有经验性质。我们要在模型复杂度 和模型推广能力找到调和的办法，需要建立小样本下有效学习和推广能力的模型。 2 1 3v c 维 统计学习理论就是研究小样本估计和预测的理论，它从理论上研究了经验风险 最小化以及经验风险和期望风险的关系等问题，主要内容包括四个方面【4 】： ( 1 ) 经验风险最小化准则下统计学习一致性的条件； ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论； ( 3 ) 在这些界的基础上建立的小样本归纳推理准则； ( 4 ) 实现新的准则的实际方法； 统计学习理论的基础是学习的一致性。学习过程的一致性就是当样本数目 n - - - o o 时，有r 。( 忉- - r ( w ) ，只有这样，才能使得在经验风险最小化原则指导下得 到的训练模型也能使期望风险达到更小。 定理2 1当损失函数是有界的，学习一致性的充分必要条件如下表示 l i m p s u p ( r ( w ) 一r 。肼口( w ) ) 占】_ 0 ， v 占 0( 2 4 ) 其中，p 表示概率，尺唧( w ) 和r ( w ) 分别表示在样本下的经验风险和真实风险。 在具体的学习过程中，经验风险和期望风险都是预测函数的函数，也就是涉及 到泛函分析，我们的目的是求得经验风险最小化的函数，使此函数能够近似接近能 够使期望风险最小化的函数。 统计学习理论除了定义学习一致性的充分必要条件，它还定义了一系列有关函 数集学习性能的指标，也就是v c 维。 有一个指示函数集f ( x ，w ) 和一组训练样本集乏= 召砘，y a 扛】，z 。磅，此函数集中的 函数能对样本集合实现不同的分类的数目( 乙) ，函数集的生长函数g ( n ) 定义如 下： g ( 刀) = i n m a x ( 乙) ( 2 5 ) z “ 生长函数反映了函数集f ( x ，w ) 能把样本集乙= 弓砘，y ai = l 2 , 琦分成两类的能够出 现的最多可能的分法。由于是在样本集合上取得最大值，所以与样本具体分布无关。 v c 维( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) 是衡量函数集的学习过程一致收敛速 度和其推广能力的一个指标。它的定义如下：一函数集若能够把h 个样本按2 h 种 形式分开，则说明此函数集能够把h 个样本打散，其中样本数目h 就是函数集的 v c 维。v c 维反映了函数集的学习能力，它的值越大表示学习模型越复杂。v c 维 7 硕士学位论文 m a s t e r st h e s i s 与生长函数的关系如下：如果证明函数集的生长函数是线性的，那么它的v c 维是 无穷大；如果它是以参数的对数函数为上界限，那么它的v c 维就等于此参数。要 使学习过程一致收敛必须要求v c 维是一确定的数值，v c 是一个非常重要的概念。 但目前只知道一些比较特殊函数的v c 维度，对于如何计算任意函数集合的v c 维 尚没有通用的指导理论。v c 维度的大小不但与函数集本身有关，而且也与所采用 的学习算法有关，因此对其的确定有一定的难度。 2 1 4 结构风险最小化 基于经验风险最小化原则机器下学习的实际风险r 如下表示： r ( w ) r 。口( w ) + ( 2 6 ) 其中尺( w ) 是期望风险，( w ) 是经验风险，是置信区间。通过研究发现， 是函数集的v c 维h 和训练样本数目1 1 的函数，公式( 2 6 ) 可以如下表示： r ( w ) ( w ) + ( 等) ( 2 7 ) 月 由公式( 2 7 ) 可以看出，当n h 较小时，( 兰) 就较大，用经验风险( w ) 近 ，i 似真实风险尺( 叻就有较大的误差，可能会造成推广性差；反之，如果n h 较大，( 等) 仃 就会很小，( w ) 就会更接近于r ( w ) 。 学习机器的v c 维越高，说明该学习模型越复杂，在给定样本数目的情况下， 就会造成置信范围大，那么经验风险和真实风险的误差就大，所以在设计学习机器 时候，我们尽量要减小模型的v c 维，进而使置信范围减小，使期望风险最小。统 计学习理论中按照结构化风险最小化的准则来问题，具体解释如下：把函数集合 s = 厂( x ，w ) ，w q ) 表示为函数子序列 scsc c 墨c cs 把子集序列按照v c 维从小到大的顺序排列，即 忽珐历。 我们要在子集中寻求经验风险的最小值，经验风险越小可能会造成模型的复杂 度增加。我们要在训练过程中选择经验风险与置信范围之和达到最小值的子集，依 靠这种策略来逼近期望风险的最小值，这时得到的函数就是最优函数关系，这就是 结构化风险最小原则。具体思想如图2 1 表示。 8 硕士学位论文 m a s t e r st h e s i s 风险 图2 1 结构风险最小化示意图 按照结构风险最小化的原则解决问题要比按照经验风险最小化的原则取得更 好的效果，更能接近实际问题的情况。 2 2 支持向量机理论 1 9 9 5 年，随着统计学习理论的发展，在此基础上发展出了一种新的机器学习方 法一支持向量机，它在解决小样本、非线性和高维问题中表现出较好的性能，解 决了传统方法中的难题。 s v m 是从线性可分情况下的最优超平面发展起来的，它最初应用于分类问题， 它通过最大化分类超平面的间隔，实现结构风险最小化的原则。应用s v m 分类模 型求解具体问题时，s v m 通过核函数将样本从输入空间映射到高维的特征空间， 并在高维的特征空间中构造问题的最优分类超平面，也即是将问题转化成为一个凸 二次优化，实现了问题从低维空间像高维的推广，同时也解决了维数灾难的问题。 2 2 1 广义最优超平面 所谓最优分类面就是首先要求能够将样本数据正确分类，另外还要使样本数据 9 硕士学位论文 m a s i 、e r st h e s i s 之间的分类间隔最大。二维两类线性可分的问题如图2 2 所示。 h i 图2 2 二维两类分类问题 图2 2 中圆黑点和三角形点分别表示训练样本的分布，h 是把训练样本数据分 开的分类线，h 1 ，h 2 是平行于h 且分别过三角形类、实点类样本中离分类线h 最 近的点直线，h 1 和h 2 的距离m a r g i n 叫做两类样本的分类间隔，图2 2 展示的是二 维空间的情况，推广到三维或者高维空间，最优分类线就称为最优分类面。 在二维空间中，给定一样本集( 薯，只) ，i = 1 ，n ，x r a , y + 1 ，1 ) 是类别标号，如 果样本集能够线性可分的，那么其线性分类函数表示为p s o ，分类面方程为 x w + b = 0 ，它使得对所有样本满足l 厂( x ) i 1 ，此时h 1 ，h 2 的分类间隔是瓶i i ， 要使分类间隔取得最大值，由于其与0w i i 成反比，那么使1 w i l 取得最小值；如果分类 线把所有的样本都完全正确地分类，则有如下公式成立： y i ( w o x o + b 卜l 0i = l 2 1 1( 2 8 ) 满足公式( 2 8 ) 并且使i l w l 2 取得最小值的分类面就是最优分类面，支撑了最 优分类面的样本就叫做支持向量，就像图2 2 中圆圈所圈示的点。用数学语言来描 述，最优化分类面转化为约束优化问题，即是： r n j n ( w ) = 扣1 1 2 s t 少 ( w 知) + 6 卜1 0 i = l ，2 n 1 0 ( 2 9 ) ( 2 1 0 ) 硕士学位论丈 m a s t e r st h e s i s 根据拉格朗同定理，可以定义如下的拉格朗同函数： 三( w ，b ，口) = 去( w w ) 一口， 只【( w ) + 6 】一1 ( 2 1 1 ) 其中，口， o 为l a g r a n g e 系数，现在问题转化为求解l a g r a n g e 函数取得极小值 时w 和b 的值。 将公式2 1 1 分别对w 和b 求导并使得到的导数方程等于0 ，这样就把对原问题 的求解转化为对其对偶问题的求解。在约束条件 e m 口，= o ， 口，o ，f = l ，行 ( 2 1 2 ) 下求解函数g ( a ) 最大值 g ( 口) = q 一去口，口，y , y j k ( x , x j ) ( 2 1 3 ) j = l f j = l 若q 为最优解，则有 w 2 善咖x ，( 2 1 4 ) 这是在不等式约束条件下求解二次函数的极大值问题，根据定理存在唯一解， 根据k u h n t u c k e r 定理，要求解问题的解必须满足 口， 只( w 薯+ 6 ) - 1 】= 0 ，f = 1 ，甩 ( 2 1 5 ) 最终求得的结果，对于多数鼍，q 。取值为零，对于一部分样本取值x l 使得口，取值 不为零，对于这部分样本也就是模型的，他们的数量通常是样本的- - d , 部分。 通过运算后，得到的分类函数表示如下： 厂( x ) = s g n q 只k ( t x ) + 6 + ) ( 2 1 6 ) s 弘( ) 表示函数是符号函数。b 是分类函数的截距，可以把求得的支持向量代入 公式( 2 1 6 ) 求得。 上述的最优分类面首先是在样本线性可分的条件下分析的，实