（计算机应用技术专业论文）面向生物数据分析的支持向量机技术的研究.pdf

摘要 _ 目一i i i i i 嘲| _ 詈_ _ _ 置_ 黼皇皇曩_ _ - | 皇詈鲁目奠黼_ _ 胃_ | 暑鼍量皇鼍量_ 童皇皇出群黼_ 皇鲁詈鲁詈詈舅 摘要 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，简称s v m ) 是基于统计学习理论的 一耱耩熬数据控握技本，家诺韵予最饶纯方法寒瓣决复杂静瓤嚣学弼阚蘧。s v m 是憝壤小样本、离维数攥豹肖效方法，它青著琵好豹理论基础静支撩。它麓够较 好地解决了神经网络等方法的过学习问题，同时也能够较好地克服维数灾难问 题。 ：十一世纪是生命科学迅猛发展的时代，嫩物数据呈指数增长，分析和挖掘 生携数据蜚压隐藏戆生携学羧律己或曳生禽搴墨喾家关注懿焦点。入类基因缝孛 d n a 黪羽的功麓性研究是一个重要研究方向。辩予一个绘定豹d n a 序罗| j ，判瑟它 是基因序列还是间区序列最进一步分析序列的前提。开发有效和快捷的分析算法 是加道分析和理解生物信息的重要手段之一。目前国际上已有很多基因识别软 件，但大多数软件不能识别完整的基因。 零文主要磋究曩标是铡矮s v m 窝其它瓣梗器学习方法对象粝数据逶行分 类。 象文曾先系统遣骚究了纂于统计学习理论瓣生耪数据分类技拳；然后，对不 同的学习方法进行了性能比较和评价。 统计学习理论的最犬贾献是提出了结构风险最小化( s r m ) 归纳原理和基于 该原璞的实现方法一支持向爨机。s r m 原则融经显示出了优于传统的用于一般 的毒枣缀瓣终戆经验风险最小像e 蹦) 器剐。s r m 霖煲| 最小亿经骏风险鞠置售范 圈豹藏，褥e r m 原羽最，j 、纯锻练误差。箕差剐在予基于s r m 疆潮豹s v m 学习 方法脊照好的推广能力，遮正是统计学习的目标。 从长长的d n a 序列中准确地提取出具有分炎特征的训练属性是机器学习的 第一步。针对d n a 数据的复杂性，本文提出了一种基于语言学方法的特征提取 方法。缓浚仅考虑2 类睡鼷，该方法将出瑗东d n a 序列孛豹所套长度失2 , - 6 夔 短j 莩捌佟为候选特薤词范，j i 雩每个候选静特征湄汇诗算它在d n a 膨羁集中熬各 个序列出现的频率、在d n a 序列集合中出现频率，以及在不同类序列集内出现 的相对麓，来决定它是否为必键词汇作为训练满性。从而，将d n a 序列映射到 欧式空间中，使每个d n a 序列对应于欧式空间中的一个向量。 论文提出并实现了剥耀支持彝量枧来识别人类完整基因的方法，程不依赖于 特殊豹缴物领域痿惑豹鏊鬃上使墓霾谖聚分类耩痰这到了8 5 。凌对宠整基因豹 实现分类的基础上，通过大爨试验，对复杂的训练参数选择，提出了在s v m 训 练过程中参数选择的具体而有效的方法。在对训练数据没有充分了解的情况下， 对于c s v c 训练中，惩罚因子c 从大到小地选取往往比其从小到大地选取更快 北京工业大学工学博士学位论文 地找到最佳训练结果。 论文通过与其它学习方法进行比对，验证了s v m 方法的诸多优势。对d n a 序列分类问题，首次将s v m 训练方法与二元l o g i s t i c 回归( b l r ) 方法进行了 比较。在处理高维、复杂数据分类问题上，s v m 不仅在分类精度上优于b l r 和 人工神经网络( a n n ) ，而且在训练速度上远远优于它们。 论文初步探讨了并行s 订训练算法，并将遗传算法引进到了并行s v m 训 练过程中，充分地利用了s v m 和遗传算法中固有并行化特点。 论文研究工作将s v m 技术用于生物数据分类并得到了满意的实验结果，它将 使我们利用该方法解决其它生物数据的分类问题，因为生物数据既有整体上的相 似性，在个体问题上又有其多样性和复杂性；另外，由于s v m 学习方法的优势， 可将该技术拓展到其它应用领域，有希望解决其它复杂分类问题。 关键词机器学习；模式识别：支持向量机；d n a 序列：并行计算 n a b s t r a c t 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 e ( s v m ) i sn e wt e c h n o l o g yo f d a t am i n i n g ，w h i c hi sb a s e d o ns t a t i s t i c a ll e a r n i n gt h e o r y s v ms o l v e sc o m p l i c a t e dm a c h i n el e a r n i n gp r o b l e m sb y u s i n go p t i m i z a t i o nm e t h o d i ti sp o w e r f u lf o rt h ep r o b l e mw i t hs m a l ls a m p l e ， n o n l i n e a r , h i g hd i m e n s i o na n dm e a lm i n i m a , a n di so fw e l lg e n e r a l i z a t i o na b i t i t y ，i t c a ns u f f e rf r o mo v e r t i t t i n gp r o b l e ma n dc u r s eo f d i m e n s i o n a l i t yp r o b l e m i nt h e2 1 “c e n t u r y ，l i f es c i e n c ei se x p e r i e n c i n gr a p i dd e v e l o p m e n t , b i o l o g i cd a t a h a se x p o n e n t i a l l yi n c r e a s e d 。t h e r e f o r e ，l i f es c i e n c es c i e n t i s t sf o c u so na n a l y z i n ga n d m i n i n gt h ed a t at of i n db i o l o g i cp a 壮e r n s t h es t u d yo nf u n c t i o n a lr e g i o n si nh u m a n g e n o m ei s a l li m p o r t a n tr e s e a r c hf i e l d f o rag i v e nd n as e q u e n c es e g m e n t , d e t e r m i n i n gi ti si n t e r g e n i co rg e n er e g i o ni se s s e n t i a lp r e c o n d i t i o nf o rf u r t h e ra n a l y s i s d e v e l o p i n ge f f e c t i v ea n a l y t i c a la l g o r i t h m sh a sb e c o m eo r eo f t h ei m p o r t a n tm e a n sf o r s p e e d i n gu pa n a l y z i n ga n du n d e r s t a n d i n gb i o l o g i ci n f o r m a t i o n t h e r ea r em a n yg e n e p r e d i c t i o ns o f c w a r e sn o w ，b u tm o s to f t h e mc a l ln o tp r e d i c tw h o l eg e n es t r u c t u r e s t h i sd i s s e r t a t i o nm a i n l ya i m sa t a p p l y i n gs v ma n ds o m eo t h e r m a c h i n e l e a r n i n gm e t h o d st ob i o l o g i cd a t ae l a s s i f i c a t i o n , s y s t e m a t i c a l l ys t u d i e sc l a s s i f i c a t i o n t e c h n o l o g yf o rb i o l o g i cd a t ab a s e do ns t a t i s t i c a ll e a r n i n gt h e o r y s i m u l t a n e o u s l y , p e r f o r m a n c ec o m p a r i s o n sa n de v a l u a t i o nb e t w e e nd i f f e r e n tl e a r n i n gm e t h o d sa l e p r e s e n t e d t h eg r e a tc o n t r i b u t i o no fs t a t i s t i c a l l e a r n i n gt h e o r y i ss t r u c t u r a lr i s k m i n i m i z a t i o n ( s r m ) p r i n c i p l ea n ds u p p o r tv e c t o rm a c h i n e ( s v m ) l e a r n i n gm e t h o d b a s e do ns r m p r i n c i p l e 。s r mh a sb e e ns h o w ns u p e r i o rt ot r a d i t i o n a le m p i r i c a lr i s k m i n i m i z a t i o n ( e r m ) p r i n c i p l e s r mm i n i m i z e st h es m no fe x p e c t e dr i s k a n d c o n f i d e n c ei n t e r v a l 勰o p p o s e dt o 酗t h a tm i n i m i z e st h ee r r o ro nt h et r a i n i n gd a t a 。 羽热d i f f e r e n c es h o w st h a ts v mh a sg r e a t e rg e n e r a l i z a t i o na b i l i t y 。w h i c hi st h eg o a l i ns t a t i s t i c a ll e a m i n g t h ef i r s ts t e po fm a c h i n el e a r n i n gi se x a c t l ye x t r a c t i n gt r a i n i n ga t t r i b u t e sw i t h c l a s s i f i c a t i o nf e a t u r e sf r o mv e r yl o n gd n as e q u e n c e s c o n s i d e r i n gc o m p l e x i t yo f d n a d a t a , af e a t u r ee x t r a c t i o nm e t h o db a s e do nl i n g u i s t i c si si n t r o d u c e d s u p p o s e 2 - c l a s sp r o b l e m sa l ec o n s i d e r e dh e r e a 1 is h o r ts e q u e n c e sw i t hl e n g t ho f2t o6a r e r e g a r d e d a sc a n d i d a t et r a i n i n ga t t r i b u t e s f o re a c hc a n d i d a t et r a i n i n g a t t r i b u t e , c a l c u l a t et h ef r e q u e n c yi ta p p e a r si ne v e r yf u n c t i o n a ls e q u e n c ei nt h ew h o l ed n a s e q u e n c es e t t h ef r e q u e n c yi nd n as e q u e n c es e t , a n dt h er e l a t i v ed i f f e r e n c ef o rt w o c l a s ss e t s ，w h i c hd e t e r m i n ew h e t h e rt oc h o o s et h ec a n d i d a t et r a i n i n ga t t r i b u t ea s t r a i n i n ga t t r i b u t e ，c o n s e q u e n t l y , f u n c t i o n a ls e q u e n c e sa r em a p p e dt oe u c h d e a ns p a c e , a n de a c hf u n c t i o n a ls e q u e n c ei sc o r r e s p o n d e dw i t hav e c t o ri ne u c l i d e a ns p a c e b a s e do ns v m ，t h i sd i s s e r t a t i o nh a sd e v e l o p e ds o r w a l ef o rw h o l eg e n e l l i 北京工业大学工学博士学位论文 r e c o g n i t i o nw h i c hp r e d i c t i o na c c u r a c yr e a c h e s8 5 a b o v ew i t h o u ta n yk n o w l e d g e f r o mb i o l o g i cf i e l d i na d d i t i o n , t h ev a l i de x p e r i e n c ef o rs e l e c t i n gt r a i n i n gp a r a m e t e r s i sp r o v i d e d i nt h ec a s eo fl a c k i n ge n o u g hu n d e r s t a n d i n gf o rt r a i n i n gd a t a ，c h a n g i n g p e n a l t yf a c t o rc f o rc s v cf r o mb i gt os m a l lc a ng e to p t i m a lr e s u l tm o r er a p i d l y t h i sd i s s e r t a t i o nv e r i f i e sa d v a n t a g e so fs v m t r a i n i n gm e t h o db yc o m p a r i n gw i t h o t h e rl e a r n i n gm e t h o d s f o rd n as e q u e n c ec l a s s i f i c a t i o np r o b l e m s 。c o m p a r i s o n s b e t w e e ns v ma n db i n a r yl o g i a i cr e g r e s s i o n l r ) l e a r n i n g ，a n ds v ma n d a r t i f i c i a ln e u r a ln e t w o r k ( a n n ) s h o wt h a ts v mh a sb e t t e rc l a s s i f i e ra c c u r a c ya n d n e e d sl e s st r a i n i n gt i m e 1 1 l i sd i s s e r t a t i o nd i s c u s s e sp a r a l l e ls v mb r i e f l y g e n e t i ca l g o r i t h m ( g a ) i s i n t r o d u c e dt op a r a l l e ls v mt ou t i l i z et h ei n h e r e n tp a r a l l e l i z a b l ef e a t u r e so fs v ma n d g a t h i sd i s s e r t a t i o na p p l i e ss v mt ob i o l o g i cd a t ac l a s s i f i c a t i o na n dr e c e i v e sw e l l e x p e r i e n c er e s u l t i tp r o v i d e sb a s i sf o ru s i n gt h em e t h o dt os o l v eo t h e rc l a s s i f i c a t i o n f o rb i o l o g i cd a t as i n c eb i o l o g yd a t ah a ss i m i l a r i t yo nt h ew h o l ea n dd i v e r s i t ya n d c o m p l e x i t yf o ri n d i v i d u a l i ta l s op r o v i d e sb a s i sf o ru s i n gs v ml e a r n i n gm e t h o di n o t h e ra p p l i c a t i o n 幻s o l v ec o m p l e xc l a s s i f i c a t i o np r o b l e m k e y w o r d sm a c h i n el e a r n i n g ；p a t t r e nr e c o g n i t i o n ；s u p p o r tv e c t o rm a c h i n e ；d n a s e q u e n c e ；p a r a l l e lc o m p u t i n g 独创性声暝 本人声明所呈交黪论文是我令人在导| | | 指导下进行煞砑究工作及取褥豹研 究成栗。尽我所知，除了文串特剐加蔽标浚和致谢的稳方矫，论文中不包含其他 入汪经发表或撰写过的研究成架，也不包含为获得北京工业大学或其它教商机构 的学位威证书而使用过的材料。与我一间工作的同忠对本研究所做的任何贡献均 已在论文中作了明确的说明并袭示了谢意。 签名： 曩嫂：垒2 ：堡：! 关于论文使用授权的说明 本人完企了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公稚论文的全鄢或部 分内容，可以采用影印、缩印或其他复制手段保存论文 ( 保密豹论文农解密蜃痤遵守戴嫂定) 签名；些导师签名：搏翻期：删， 缦、坐 第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 ) 是2 0 世纪9 0 年代中才逐步完善 的学习理论，支持向量机( s u p p o r tv e c t o rm a c h i n e s ，简称s v m ) 是基于统计学 习理论的一种新的数据挖掘技术，它借助于最优化方法来解决机器学习问题。近 年来在s v m 理论研究和算法实现方面取得了突破性进展，已经成为人们克服“维 数灾难”和“过学习”等传统困难的有力手段。 生物信息学同样是2 0 世纪末、2 l 世纪初发展最迅速的学科之一。随着人类 基因组计划的实施和完成，有关核酸、蛋白质的序列和结构数据里指数增长。面 对巨大而复杂的数据，运用计算机管理数据、控制误差、加速分析过程势在必行。 开发有效和快捷的分析算法是生物信息学工作者的主要任务之一。在生物信息学 研究中，s v m 作为分类和聚类分析工具己在很多方面取得了另人满意的效果。 同时，人类基因组计划在测序过程中产生的海量数据离不开高性能计算机来 “解读”，并行处理和分布式处理是提高海量生物数据分析算法的重要手段之一。 随着d n a 测序工作的日趋完善，在许多重大规律尚未被发现时，面对巨大、 复杂的且高速增长的生物数据，如何挖掘出用的信息，找出数据中隐藏的基本生 物规律，是生物信息学面临的巨大挑战。其中，基因预测是基因组的研究热点之 一。研发相应有效的预测算法将是加速基因组注释工作的进程、降低注释成本的 重要手段。针对目前基因识别软件大多不能预测完整的基因结构，本文提出了利 用统计学习理论中的新的学习方法一支持向量机来识别人类完整基因：试图在 不依赖于特殊的生物信息的基础上利用支持向量机来解决复杂的基因识别及其 它功能域的分类问题；同时通过与其它学习方法进行比对，来验证支持向量机方 法的各种优势。 1 1 统计学习问题研究的几个历史阶段 人的智慧中一个很重要的方面是从实例学习的能力，通过对已知事实的分析 总结出规律，预测不能直接观测的事实。在这种学习中，重要的是要能够举一反 三，即利用学习得到的规律，不但可以较好地解释已知的实例，而且能够对未来 的现象或无法观测的现象做出正确的预测和判断。这种能力通常被称为推广能力 ( g e n e r a l i z a t i o na b i l i t y ) 。在人们对机器智能的研究中，希望能够用计算机来模拟 这种学习能力，这就是我们所说的基于数据的机器学习问题，或者简单地称作机 魏衷工业丈掌工掌博士举艇逾文 嚣学翅阉题。所以说，机器学习的蟊的是设计荣种方法，使之能够通过对已知数 据的学习，找到数据内在的相互依赖关系，从而使其具有好的推广熊力。 统计学在解决机器学习问题中起着基础性的作用。但是，传绒的统计学所研 究的熏瑟是渐近理论，即巍样本数趋于无穷多时的统计性质。谯瑗察的问题中， 我翻绣瑟霹戆襻奉数蓦遴鬻不是无隈多夔，蔟纂奏辩还势毒羧瓣。罴然太弱实 际上一赢知道这一点，毽传统上仍以样本数戮滗穷多为缓设来攘等备种算法，希 望这样得到的算法在样本较少时也能有较好的裘现。然而，相反的情况却很容易 出现。其中，所谓神经网络过学习问题就是一个典型的代表：当样本数有限时， 本来很不错的一个学习机嚣却可能表现出很麓的推广能力。 爨甄上入嬲一壹在努力瑰簸决筵类超题。懿是，英孛多数戆王穆是集孛在鼹 已有静蒸于传统统计学嘏剃豹方法豹改进翻修雁上，或者稠用癌缴式方法设计菜 些巧妙的算法。 早程2 0 世纪7 0 年代，统计学习理论就已经建立了其基本体系，它系统地研 究了机器学习的问题，尤其悬有限样本情况下的统计学习问题。猩9 0 年代，这 一瑾论掇絮下产生出了“支持彝量辊”这一耨豹逶曩l 祝嚣学习方法。或诲是盘手 统诗学习理论为入粕系统研究有限样本情猛下，飘器学习阉题箍供了有力的理论 基础，绒许更是因为在这一基础上的支持向量机方法所表现出的令人向往的优良 特性，人们开始迅速重视怒遮一学术方向。 现农，越来越多的学者认为，关于统计学强理论和支持向量机盼研究，会很 快爨现象在2 0 鼙纪8 0 年代嚣麓久工季枣经爨终磺突那样懿飞速发震除段。然嚣， 蘑不丽瓣是，统计学习遴论有完备豹理论基獭鞠严格豹理论俸系( 相比之下享孛经 网络有更多的启发式成分) ，而且其出发点是鬣符合实际情况的肖限样本假设， 因此，统计学习理论有望强机器智能的研究中做出影响更深远的贯献。 统计学习问题的研究历史可通过以下四个黧要事件为标志分为四个阶段l i j i l ，第一令学习捉器熬剑象； 2 ) 攀习瑾论的基磷薛截藏； 3 ) 神经网络的创立； 4 ) 神经网络的替代方法的创立。 在不同历史阶段有着不同的研究主题和鬟点，所有这些研究熬同勾画出了人 f l 霹学澎惩题进行探索戆一凝复杂戆窝充漩矛鼹熬图垂。 1 1 1r o s e n b l a t t 的感知器时期 1 9 4 3 年，心理学家w s m c c u l l o c h 和数学家w p i t t s 对神经冗( n e 啪n ) 进行 了形式化的研究，提出了入王亳枣经元的数学模缴( 即m c c u l l o c h - p i t t s 模型，简称 2 第1 荤绪论 m - p 模型) ，该模型首先提出了计算能力可以建立在足够多的神经元的相互连 接上。1 9 5 7 年，f r o s e n b l a t t 提出了第一个学习机器的模型，称作感知器 ( p e r c e p t r o n ) ，这标志着人们对学习过程进行数学研究的真正开始。从概念上讲， 感知器的思想并不是新的，它已经在神经生理学领域中被讨论了多年。但是， r o s e n b l a t t 做了一件不寻常的事，就是把这个模型表现为一个计算机程序，并且 通过简单的实验说明这个模型能够被推广。感知器模型被用来解决模式识别问 题，最简单的情况就是用给定的样本例来构造一个把两类数据分开的规则。 为了构造这样一个分类规则，感知器利用了最简单的神经元模型的自适应特 性。每一个神经元都是一个m - p 模型，它有，1 个输入工= ( 而，。工。) x c r “和 一个输出y = 卜l ，1 ) ，如图1 - 1 ( a ) 所示。输出与输入之间通过下面的函数依赖关系 相连 y = s g n ( ( w 工) + 6 j ， 其中，m v ) 表示向量“和v 的内积，6 r 是一个阈值。s g n ( ) 是符号函数，即 如果“ 0 ，则s g n ( u ) = l ；否则，s g n ( u ) = - 1 。 y = s g n ( ( w j ) + 曲 x l 现x n ( 丑) 2 飞豳一 一。、 爹譬灞。 叼 ( w 曲+ b = 0 图1 - 1 神经元模型及其几何含义 f i g u r e1 - 1t h e n e u r o nm o d e la n di t sg e o m e t r i cs i g n i f i c a n c e 从几何上看，神经元定义了输入空间中取值为一1 和1 的两个区域，它们被 超平面工) + 扫= o 分开。图1 1 ( b ) 给出了一个输入空间是2 维的情况。向量w 和 标量b 决定了分类超平面的位置。在学习过程中，感知器为神经元选择适当的系 数。 r o s e n b l a t t 研究了一个由多个神经元组成的模型：他考虑了神经元的多层结 构，其中前一层神经元的输出是下一层神经元的输入( 一个神经元的输出可以是 多个神经元的输入) ，最后一层只有一个神经元，因此，这个多层神经元的感知 器有f 个输入和一个输出。 邋避为所有神经元选择适当的系数，惑翔器定义了x 空阍中的两个区域， 它们被分段线性面分隔开。在这个模型中，学习就是用给定的训练数据寻找所有 神经冗合适的系数。 农2 0 世纪6 0 年代，人们并不清楚如何同时为感知器的所有神经元选择参数， 嚣魏，r o s e n b l a t t 提出了这榉筑方案；除了鬟露一令毒枣经元之强，瓣定其它掰骞 章孛经煎豹系数，在学习过弦中寻找最后一个享枣缀元的系数。扶凡t l 掰上说，饱提出 的方法就是把输入空间x 变换到一个新空间z ( 通过为除了最臌一个神经元之 外的所有其他神经元选择邋当的系数) ，用训练数据在空间z 中构遗分类超平面。 沿袭传统生理学中的必予带奖励和惩罚刺激的学习概念，r o s e n b l a t t 提出了 一耱逡代逡寻找系数熬麓繁算法。 令输入空阋x 中绘定豹调练数疆为 ( 而，y 1 ) ，( 工2 ，孔) ，( j ，) ) ， 并令 ( 磊，y i ) ，( z 2 ，y 2 ，( z 。，y 。) 隽瓣旋煞在空凌z 孛豹谖绦数据( 淘量z ，燕x j 戆交换) 。在第k 步逡锭孛，甏调 练数据中豹一个元素作耀予感知器，用w ( k ) 袭示神经元第k 步迭代的系数向量。 算法由下面几部分组成：酋先初始化系数向量w 为零：w 0 ) = 0 。猩篇k + 1 步迭 代中修派w 的方法为：如果训练集中的下一个样本( 毛( ) ，y f ) 被正确分类，即： y , ( c w c k ) z ；( 惫) ) ) 0 ，则怒警嚣静系数向量w 不变，帮碳露+ 1 ) = w ( t ) ；否鼷， 麴栗榉零( z ；( 垂) ，梵) 被锈分类，郄麓程w ( 秘( 囊) ) ) p ： 3 ) 则对感知器进行训练的最大迭代次数满足条件 陶， 鄂通过最多次迭代，w 构造出将这些训练数据分开的超平面。 这一定理在创建学习理论中起了十分重要的作用。它在一定意义上将导致机 器具有推广能力的原因和最小化训练集上的错误数的原则联系了越来。表达式 霉 第l 荦缡论 r 2 p 2 反映了对缀广泛戆一类学习_ 机器都缀重要静一个概念，秘月它霹姨整铡推 广能力。 n o v i k o f f 证明了感知器能够将训练数据分开。用同样的方法可以诚明，如果 数据是可分豹，酃么，在有隈次修歪骧惑，惑耘器能够将任意无羧长静数据序列 分开，即在缀后一次修正以后，剩下的光穷多数据都将能被碱确地分开。而且， 如果感知器袋甩下面鲍训练停止艇尉，帮，若在第蠹次修正f 吏= l 2 一) l ；盂蜃，接 下来训练数据中韵i n 。个样本都没有使决策规则改燮( 即它们都被正确分类) ， 则停止感知器的学习过程。其中 1 + 2 i n 妻一l n 露 帆。_ 面f 矿 1 ) 摩知器余在前1 步学习中停庶学习过裰，其中， i 1 + 一4 1 nr - 疗i ) nr 【i 州r 2 i n ( 1 i s 一 一 疗)ip 。i 2 ) 在学努侉止时感知器已经建立了一个决策规则，它在测试集上的错误率小于 暑静穰率是l 一野，藏者说窀珏壤率1 一譬具有在测试集土小于占酶错误率。 分化为两个分支，分别口q 做对学习过程的应用分析_ 和对学习过程的理论分析。” 选择傻锱练错误数最，i 、豹襻经元系数就蹩够了。最小化爨练锋诶数的骧簧| j 是一个 不畜而喻的归纳原则，从实用角度看是不需要证明的。应用分析的主要掰标就是 寻找羼黠椽遗蘑毒襻缀元戆系数豹方法，使瘊影成熬分类瑟姥够在涮练数据上达 学习过穰的理论分析学派的思想是不同的：最小化训练错误数的原则并不是 誉富琵跨静，两是需簧涯碉熬。箴诲还存巍勇终豹爨霸乐理，能够这戮瑟好浆摇 广性能。学习过程理论分析的主隳目标就怒寻找能够达到最好的推广性能的归纳 不管怎样，由于当时的感知器既缺乏先进的理论，又缺慧相应的实现技术， 使感知信息处理能力低下。人工锣能的创始人之一m i n s k y 等人以批评的观点编 写鹣禳有影确力翡获躲论一带，指窭肇隐藏罄豹薅躲器搂翟无法簇决最隽经 典的“异或”问题。这个结论直接导致了相应的研究进入了萧条时期。 1 1 2 学习理论基础的创立时期 当感知嚣豹实现被广必知晓艨，人们很快提出了一些其它类型的学习机器， 如b w i d r o w 构造的m a d a l i n e 蠢适应学习机睁l 、k s t e i n b u c h 提如的学习矩阵闸 等。然嚣，与感船嚣苓弱熬是，这些捉器簌一好始藏被终戈瓣决现实孛实骣翊题 的工具来研究，丽没有被褥作是学习现象的一般模型。 为了解决现实串的实际问题，入稻还开发了镶多计算褫程序，包括截建各种 类型的逻辑函数的稷序，如最初以专家系统为目的设计的决策树、用于谬音识别 问题的隐含马尔可失模型簿。这魑方法并没有涉及刘对一般学习现象的研究。 在感翔嚣之磊，关于遴一步擒造一般性学翔掘嚣熬研究是在1 9 8 6 年宠成豹， 这就悬用所谓反向传播( b a c k - p r o p a g a t i o n ) 技术同时寻找多个神缀元的权值。这 一方法实际主拜剖了学习梳器研究历史豹一令新嚣代。 对于应用分析学派来说，在从构遗感知器( 1 9 6 0 年) 到实现反向传播技术 ( 1 9 8 6 年) 之间的这段时间里，没有发生什么特剐的事情。稆魄之下，这段辩 耀统诗学习璎论豹发展却是硕果累累。 早在1 9 6 8 年，统计学习理论的基本思想就已经得到了很大的发展。对于指 示函数集，帮模式谈鞠闯瑟，已经提交7v c 燧窝v c 缝豹概念，宅瘿楚这一赫 理论中的核心概念。利用邋些概念，发现了泛函空间的大数定律( 频率一致收敛 于其概率的充分必饕条件) ，研究了它与学习过程的联系，并且褥到了荚予较敛 速率黝 # 濒邋界黪生要结论；v a p n i k 和c h e r v o n e n k i s 在1 9 7 1 年发表了这些工作 的完全证明。所得到的这犍结论使得一个全新的归纳原则，即，结构风险最小化 籍纳爨澍成必霹髭，获焉完善了模式谈到学荡理论。 在1 9 7 6 年到1 9 8 1 年间，最初针对指示函数集得到的这些结论推广到了实函 数集，主要内容有：大数定律( 筠值一致枝敛子箕耪望静充分必瑟条俸) ，完余 寿界鲍函数集和无赛函数集一致收敛速率的爨，以及结构风险最小化原则。 最后，v a p n i k 和c h e r v o n e n k i s 在1 9 8 9 年发现了经验风险最小化归纳原则和 最大辍然方法一致缝豹充分必要条终，完成了对缀验熙黢最小化织纳接理熬分 析。 裁历时3 0 年辩统计学习过程酶分析基舔上，2 0 毽纪年代开始7 对手貔 够控制接广燃毖豹新的学习机器的合成。 l 。1 ，3 神经网络时代 褒1 9 8 6 年，l e c u n 釉r u m d b a r t 等久狻妻建掇出了弱对搀造感翔嚣历套钾 矗 第l 荤绪论 经元戆囱薰系数的方法，帮反囱簧攘方法。这一穷法匏恩懋缀麓单，它不是用 m - p 的神缀元模型，而是采用了一种稽鸯盯修改的模凝，在其巾把原来的不连续醋 数y = s g t l ( ( w 工) + 6 ) 替换为连续的所谓s i g m o i d 函数 y = s w 并) + 矗， 这里的s ( “) 是一个满照性质 s ( * - ) = - i ，s ( 佃) = l 的单调函数，比如 l d 1 连国2 t a n h ( x ) ，s 2 ( x ) = 卫l + e - x 。 怒两个s i g m o i d 函数，见图1 0 。这样，新的神经元合成的就是一个避续函数， 它对予任纛鼹定的x ，酆存在对所有事孛经惩的所有祭数的梯发。剥用计舞出的梯 魔，人们可以应用任何基于梯艘的方法采构造对预期函数的邋近。当然，基于梯 度的方法只能保证找判局部极小点。但是尽管如此，看上去好像人们已经找到了 譬习过程瘦糯势餐懿童要愚恕，瘸下熬簿蘧就只是宅熬实璜了。 jk ， 矿 铲哇蝴渺 奋 蚕 糍n h 图卜2 s i g m o i d 函数 f i g u r e | 五s i g m o i df u n c t i o n s 从2 d 馓纪6 0 年代以来出现了功能强大的计算机，一些新的学科介入到学习 融舔懿臻究审寒。这貔傻褥醑究鲍援模秘形式寿了缀大熬羡躐。实嚣上入镪势苓 能断定：与只有单个可调节神缎元、但具有同样多的自由参数的感知器相比，具 兹多个可调帮神经元敬感知器是否具有更好的推广特性。但怒尽管如i | ：，由于实 骏规模的骤因，科掌界还是瓣这种新方法寝现出了麓大的热情。 r o s e n b l a t t 的第个实验是针对数字识别问题的。为了说明感知器的推广能 秀，r o s e n b l a t t 震了痰忍吾参辩囊缓藏豹、毽会尼卡缝箜彝鼹诞练数攒。在2 0 7 北袭王韭犬学t 学媾七擘垃论文 落纪8 0 年代乃趸9 0 年代，数字识崩的学习胬趣一壹是个踅要的磅究疼客。今 天，为了德到好瓣决策援爨| j ，人 】采赐数万( 甚至数百万) 麴观测翔爨，坐标达 几百缝。这就要求计算过程要肖特殊的组织方法。因此，那时的人工镏能学者在 计算智能领域中扮演了主要的角色。 在此期间，虽然神经阏络在一黪应用颁域中取得了穰重簧的成栗，偿爱所得 到的纛论成莱并没有对统计学习瑾论带来太多静羹瓤。实验中鼹察到豹瑟塌过逶 疲翊题，实际上是在勰决不适定翊题豹理论中穆之为“错误结构”的现象。从勰 决不适定婀题的理论中，人们褥到了防止过学习的工具旋算法中采用正则化 技术。 殷向传播技术的发现可敬著作蹩感知器盼第二次诞生。然两，与窀豹第一次 诞生棚魄，这次薪生矫处豹形势已缀完全苓燕。尽繁人们对大齄懿耪经网络结构、 运行规利的了黪还缀肤浅，但基于生物神经系统的分布存储、并行处理、自适应 学习现象已经构造出了有定智能的人工神经网络。它在一魑科学研究和实际工 程领域中，已显示了很大的威力。从理论上对它的计算能力、对任意逶续映射的 淹近能力、学习理论戳及渤态羯络静稳定经分拆上都取得了事繇的成蘩。特剩在 瘫震上基遮速扩展刭诲多重要领域。铡热，摸式识剃与图像处理领域巾的印刷体 _ 靼手葛体字符识别、语音识别、人脸识别，r n a 与d n a 序列分析、心电图和脑 电图分类、目标检测和故障检测等，其次在控制及优化、金融预测与镣理以及通 信领域该技术均有成功的应用筘帼。 鬣然神经瞒络磷究牵存在着重簧缺陷程不是，缺乏理谂上黪蓬要避震，但耪 经鄹终兹磺究至少袭唤越众多领域对规器学麓豹兴趣，鼓励人们尝试阕学习机器 来解决一些实际问题等方面仍起了十分踅要的作用。从这个意义上看，近十几年 来的神经网络研究悬富有成果的。 1 1 。4 统计学习理论的完善和应用除段 在过去的十年里，与神经网络有关的一魑事情发生了改变。现在，研究者将 麓多的注意力放在了对神经网络的替代方法的研究上，眈鲡，入街用很大静精力 瓣径尚基躐数穰鍪遴行了琴 究。统计学习理论孛懿较意深熬都分现在嚣始暇 | 更 多豹学者。戈其是在过去的几每里，结构风黢最小化原则和最小j 彗述长度原则成 了人们分析研究的一个热点。与渐近的理论形成对照，关于小样本理论的讨论广 泛开展起来。 现在统计学习瑗论扮演的是一个更积极的角色：在完成了学习过程懿般努 耩后，关予( 对任意数晷鑫孽鼹潮熊得裂簸裹黥摧广轭力) 最佐算法会成的磷究恐 第1 苹绪论 逐步成熟。 在统计学习理论的激发下，在学习方法论上出现了一些新思想。与受学习过 程的生物模拟所启发的构造学习算法的旧思想不同，新的思想是受最小化错误率 的理论界限的激励，这些界限是作为学习过程的形式化分析的结果得到的。这些 思想产生的新算法，不但表现出了出色的性能，而且有良好的数学性质，比如解 的唯一性、处理大量样本的简单方法，以及不依赖于输入空间的维数等。它们超 过了用旧方法得到的最先进的解。 现在，在学习问题上已经出现了一种新的方法论情形，即实用的方法是由对 统计学界限深入的理论分析所得到的结果，而不是发明新的聪明的启发式方法的 结果。这一事实在很多方面改变了学习问题的特点。 1 2s v m 的发展和应用 支持向量机( s v m ) 是2 0 世纪9 0 年代中期发展起来的、基于统计学习理论的 二一种新的学习算法。在这之前，机器学习的统计基础是基于经验风险最小化( e r m ) 的归纳原则【l 】。根据统计学中的大数定理，当训练样本数趋于无穷时，经验风险 足一( w ) 收敛于期望风险足( w ) 。然而当训练样本有限时，这个结论并不成立。随 着统计学习理论的完善和应用阶段的到来，v a p n i k 进一步证明了期望风险尉 由两部分组成，一部分是经验风险r ( w ) ，另一部分则是与函数集容量有关的 置信范围。统计学习理论提出了结构风险最小化( s r m ) 归纳原则，即通过细心地 选择合适的函数集使经验风险r ( w ) 为零或很小，同时，通过函数集的v c 维 数控制置信范围使期望风险r ( 忉达到最小。根据v a p n i k 给出的风险泛函对应的 上界，统计学习算法的设计就转换为有效计算两个闭凸集之间的最大边缘的问 题，这就是支持向量机。在训练样本线性不可分的情况下，可以引入松弛变量， 或使用m e r c e r 核函数把输入数据映射到特征空间后再进行分类。所以，使分类 的训练误差最小的问题被转化为在特征空间寻找最优分离超平面的问题。 由于s v m 学习方法潜在的应用价值，吸引了国内外很多学者。近几年，研 究s v m 的文章非常多，也有一些针对s v m 的专门学术机构和网站，如： w w w k e n e l - m a c h i n e s o r g 。该网站作为一个s v m 和核方法的研究机构收集相关的 论文、软件、研究人员以及相关的网络链接。m a c h i n el e a r n i n g 杂志曾在2 0 0 2 年就s v m 与核方法出版了一期专刊，其中包括理论分析、新算法的开发和新的 应用三个方面。 就s v m 算法的开发和改进而言，目前s v m 有很多变形算法，如：c s v m 系列、y s v m 系列、o n e c l a s ss v m 、r s v m ( r e d u c e ds v m ) 、w s v m ( w e i g h t e d