（计算机应用技术专业论文）基于机器学习法的酶耐热性影响因素的研究.pdf

摘要 摘要 耐热酶之所以较常温酶受到更多的关注，是因为它在高温下比常温酶有更多的功 能，而且具有反应速度快、不易被杂菌污染等特点，不过它的难以培养、不易获得恐怕 是引起更多人兴趣的原因。目前，它主要通过筛选耐热微生物获得，不过产酶量很低。 尽管如此，耐热酶仍然在食品酿造、医药、环境保护和金属冶炼等领域得到了广泛的应 用。所以本文的出发点就是想通过机器学习的方法来研究耐热酶耐热的分子机制，了解 蛋白质的折叠过程，寻求通过蛋白质工程手段提高常温酶耐热性的途径。 本实验首先比较了支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 和人工神经网络 ( a r t i f i c i a ln e u r a ln e t w o r k s ，a 卜小i ) 的优缺点，而后决定使用s v m 进行酶耐热性的研 究。因为氨基酸的组成是影响酶耐热性的主要因素之一，所以以2 0 种氨基酸所占比例 作为特征向量，利用s v m 预测酶的耐热性。在比较了s v m 中核函数的分类能力之后， 最终选择了分类能力最好的径向基核函数( r a d i a lb a s i sf u n c t i o n ，r b f ) 进行分类，其 预测率为8 5 4 。随后分别使用几何方法、s v m k n n 和重复训练三种参数优化方法优 化s v m ，得出的预测率分别是8 8 2 、8 6 1 和8 6 1 ，从预测率中可以看出几何方法 提升的幅度最大为2 8 。所以按预测率的高低选择了几何方法来优化s v m 分类器的参 数。随后以氨基酸极性的不同将氨基酸含量数据分为4 类，并以其作为特征向量分别用 原始的s v m 和参数优化过的s v m 进行预测，分别得到的预测率为7 2 2 和7 6 4 ，可 以看出优化过的s v m 得出的预测率相比原始的提高4 2 。在基于二肽的酶耐热性预测 实验中，以二肽为特征向量进行s v m 的预测，预测率为7 1 9 。在高级结构的实验中， 分别以氢键、盐桥、体积和温度因素( b f a c t o r ) 为特征向量进行s v m 的预测，而得到 了预测率分别是8 1 3 、8 8 9 、5 5 8 和5 9 0 。最后对环糊精葡萄糖基转移酶 ( c y c l o m a l t o d e x t r i ng l u c a n o t r a n s f e r a s e ，c g t a s e ) 进行突变，其目的是在保持其原有功 能不变化的前提下，提高它在高温环境下耐热性。首先是统计出突变前后c g t a s e 的盐 桥数目，而后利用在高级结构中的盐桥数据作为训练集，突变前后c g t a s e 的盐桥数据 和随机抽取的部分盐桥数据作为测试集放入s v m 中预测，在重复实验1 0 0 次后，发现 突变前后c g t a s e 均被正确分类。 通过以上的实验，可以得到以下结论：( 1 ) 在一级结构中，氨基酸含量、氨基酸极 性和二肽都是影响酶耐热性的关键因素。( 2 ) 在高级结构中，氢键和盐桥对酶耐热性影 响比较大，而体积和温度因素对酶耐热性影响比较小。( 3 ) 以盐桥作为特征向量的分类 器是正确的，并且对c g t a s e 的突变实验是成功的。 关键词：支持向量机；参数优化；结构参数；环糊精葡萄糖基转移酶 a b s t r a c t a b s t r a c t t h e r m o p h i l i ce n z y m eh a sm o r ea t t e n t i o nt h a nm e s o p h i l i ce n z y m e ，b e c a u s ei t h a sm o r e f u n c t i o nt h a nm e s o p h i l i ce n z y m ei nh i g ht e m p e r a t u r e b u ti t sd i f f i c u l t t op r e p a r et h a t p r o b a b l yc a u s e db ym o r ep e o p l e i n t e r e s t i ti so b t a i n e dt h r o u g hf i l t e r i n gt h e r m o p h i l i c m i c r o o r g a n i s m s ，b u tt h ep r o d u c t i o ni sv e r yl o w i ns p i t eo ft h i s ，t h e r m o p h i l i ce n z y m e h a sb e e n w i d e l y u s e di n m a n y f i e l d so ff o o d ，m e d i c i n e ，e n v i r o n m e n t a lp r o t e c t i o n a n dm e t a l s m e l t i n g t h ei d e ao ft h i sp a p e ri st h a ts t u d ym o l e c u l a rm e c h a n i s mo ft h e r m o p h i l i ce n z y m et o k n o wt h ef o l do fp r o t e i nb yn a c h i n el e a m i n ga n df i n dt h ew a yt oi m p r o v et h e r m o s t a b i l i t yo f m e s o p h i l i ce n z y m eb yp r o t e i ne n g i n e e r i n g s u p p o r tv e c t o rm a c h i n e ( s v m ) w a sc h o s e n t os t u d ye n z y m et h e r m o s t a b i l i t ya f t e r c o n t r a s t i n gs v m a n da r t i f i c i a ln e u r a ln e t w o r k s a m i n oa c i dc o m p o s i t i o ni so n eo fp r i m a r y f a c t o r s a f f e c t i n gp r o t e i nt h e r m o s t a b i l i t y t h e r e f o r e t h e p e r c e n t a g e o f2 0 - a m i n oa c i d c o m p o s i t i o ni nt h e i rp r o t e i ns e q u e n c ew a sc h o s e na st h ef e a t u r ev e c t o ro fs v m t h e n ， p r e d i c t e dp r o t e i nt h e r m o s t a b i l i t yb ys v m a f t e rc o n t r a s t i n gk e r n e lf u n c t i o n si ns v m ，r a d i a l b a s i sf u n c t i o nw a sc h o s e nt ot r a i ns v ma n dt h ea c c u r a r yw a s8 5 4 t h e nw eo p t i m i z e d s v mb vg e o m e t r i c a lm e t h o d ，s v m 1 c 心烈a n di t e r a t i o no ft r a i n i n g t h ea c c u r a c yw e r e 8 8 2 ，8 6 1 a n d8 6 1 ，r e s p e c t i v e l y 7 1 1 1 eg e o m e t r i c a lm e t h o dg o tt h eb i g g e s ti n c r e a s eo f 2 8 s ow ec h o s et h eg e o m e t r i c a lm e t h o dt oo p t i m i z es v mp a r a m e t e r sa c c o r d i n gt ot h e a c c u r a r y t h e nd a t ao fp e r c e n t a g eo fa m i n oa c i dw a sd i v i d e di n t o4a c c o r d i n gt op o l a ro f a m i n oa c i d t h eo r i g i n a ls v ma n ds v mw i t hp a r a m e t e ro p t i m i z a t i o np r e d i c t e dr e s p e c t i v e l y w h e np o l a ro fa m i n oa c i dw a sf e a t u r ev e c t o r t h ea c c u r a r yw e r e7 2 2 a n d7 6 4 t h e a c c u r a r yr o s e4 2 f r o mt h er e s u l t s i nd i p e p t i d eb a s e dp r e d i c t i o ne x p e r i m e n t so fe n z y m e t h e r m o s t a b i l i t y t h ea c c u r a r yw h e np o l a ro fa m i n oa c i dw a sf e a t u r ev e c t o rw a s7 1 9 i n h i g h e rs t r u c t u r e ，t h ef e a t m ev e c t o rw e r eh y d r o g e nb o n d ，s a l tb r i d g e ，v o l u m ea n dt e m p e r a t u r e f a c t o r ( b f a c t o r ) r e s p e c t i v e l y t h ea c c u r a r y w e r e8 1 3 ，8 8 9 ，5 5 8 a n d5 9 0 f i n a l l y ，m e a i mo ft h ee x p e r i m e n to fc y c l o m a l t o d e x t r i ng l u c a n o t r a n s f e r a s e ( c g t a s e ) m u t a t i o nw a s i m p r o v e d i t st h e r m o s t a b i l i t yi nh i g ht e m p e r a t u r ee n v i r o n m e n tw i t h o u tc h a n g e so fi t s f u n c t i o n s ot h ef i r s ts t e pw a sc a l c u l a t e ds a l tb r i g d eo fo r i g i n a lc g t a s ea n dc g t a s ew i t h m u t a t i o n t h e nt h et r a i n i n gs e tw a st h es a l tb r i d g ed a t ao fh i g h e rs t r u c t u r e s a l tb r i d g eo f o r i g i n a lc g t a s ea n dc g t a s ew i t hm u t a t i o na n dp a r to fs a l tb r i d g ew h i c hw a sc h o s e n r a n d o m l yw e r ef o r m e dt e s t i n gs e t t h ep r e d i c t e dr e s u l tb ys v mw a st h ea c c u r a r y o f c l a s s i f y i n go r i g i n a lc g t a s ea n dc g t a s ew i t hm u t a t i o nc o r r e c t l y a f t e ri t e r a t i o no f10 0 ，t h e o r i g i n a lc g t 瓠ea n dc g t a s e w i t hm u t a t i o nw e r ec l a s s i f i e dc o r r e c t l yp e rt i m e s ow ec a ng e ts o m ec o n c l u s i o n ：( 1 ) i nt h ep r i m a r ys t r u c t u r e ，t h ek e yf a c t o r so fe n z y m e t h e r m o s t a b i l i t ya r ep e r c e n t a g eo fa m i n oa c i d ，p o l a ro fa m i n oa c i da n dd i p e p t i d e ( 2 ) h y d r o g e n b o n da n ds a l tb r i d g ea r ei m p o r t a n tf a c t o r sf o re n z y m et h e r m o s t a b i l i t yi nh i g h e rs t r u c t u r e t h e r ei sn o tac l o s er e l a t i o n s h i pb e t w e e nv o l u m e ，t e m p e r a t u r ea n de n z y m et h e r m o s t a b i l i t y ( 3 ) t h ec l a s s i f i e ro fs a l tb r i d g ea sf e a t u r ev e c t o ri sc o r r e c ta n dt h em u t a t i o ne x p e r i m e n to f c g t a s ei ss u c c e s s f u l k e y w o r d s ：s v m ；p a r a m e t e r so p t i m i z a t i o n ；s t r u c t u r a lp a r a m e t e r s ；c g t a s e i i 独创性声明 本人声明所呈交的学位论文是衣人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定 签名： 丝兰工望 导师签名： 日 期： 第一章绪论 第一章绪论 1 1 研究背景 1 1 1 酶的耐热性 蛋白质是一类结构极其复杂的生物大分子，是生命活动的主要承担者。它是由氨基 酸分子呈线性排列所形成，即相邻氨基酸残基的羧基和氨基通过形成肽键连接在一起 ( 见图卜1 ) 。蛋白质的氨基酸序列是由对应基因所编码，遗传密码所编码的2 0 种基 本氨基酸( 见表卜1 ) 瞻3 。在蛋白质中，某些氨基酸残基还可以被翻译后修饰而发生化 学结构的变化，以此对蛋白质进行激活或是调控。而多个蛋白质通常是结合在一起形成 稳定的蛋白质复合物，从而发挥一定的功能。 m 铲hm c h 表1 - 1 2 0 种氨基酸 t a b 1 12 0k i n d so fa m i n oa c i d s f z 江南大学硕士学位论文 大多数的蛋白质都可以自然地折叠为一个特定的三维结构，而这一特定的结构被称 为天然状态。多数蛋白质可以通过本身氨基酸序列的性质进行自我折叠，但是还是有些 蛋白质需要分子伴侣的帮助来完成折叠。在高温或极端p h 值的条件下，大多数蛋白质 会失去它的天然活性，这叫做变性。而蛋白质的结构可分为； 1 一级结构；对于简单蛋白质来说一级结构就是多肽链中的氨基酸的排列顺序，靠 共价键维持多肽链的连接，而不涉及其空问结构。对复合蛋白，完整的一级结构包 括肽链以外的其他成分。蛋白质的一级结构是一个无空间概念的一维结构。 2 二级结构：指多肽链借助于氢键沿一维方向排列成具有周期性的空间结构。主要为 口螺旋、卢折叠、转角、环形和无规卷曲等( 见图l 一2 ) 】。但是并不是所有的蛋白 质的肽链都有规则的二级结构。 3 三级结构：通过多个二级结构元素在三维空间的排列所形成的蛋白质分子的三维结 构。 4 四级结构：是指亚基与亚基之间通过疏水相互作用，结合成为有序排列的空间结构 川m 。 潘攀i ( ，螺旋体 图1 - 2 口螺旋和口折叠 f i g1 - 2 口- h c l i x a n d 口f o l d 蛋白质具有的生物学功能主要有：催化功能、运输功能、营养存储功能、收缩和运 动功能、结构功能、防御功能和调控功能州。其中的催化功能的主角是酶，它作为具有 催化功能的蛋白质，在催化反应体系中起了至关重要的作用。在反应中，反应物分子被 称为底物底物通过酶的催化转化为另一种分子。几乎所有的细胞活动进程都需要酶的 参与，以提高效率。与其他非生物催化剂相似，酶通过降低化学反应的活化能来加快反 应速率，大多数的酶可以将催化的反应速率提高上百万倍，又因为酶是催化剂，所以本 身在反应过程中不被消耗，也不影响反应的化学平衡。与其他非生物催化剂不同的是， 酶具有高度的专一性，只催化特定的反应或产生特定的构型。目前己知的可以被酶催化 的反应有约4 0 0 0 种。当然，酶的催化活性可以受其他分子影响：抑制剂是可以降低酶 活性的分子；激活剂则是可以增加酶活性的分子。有许多药物和毒药就是酶的抑制剂。 酶的活性还可以被温度、化学环境( 如p h 值) 、底物浓度以及电磁波( 如微波) 等许多 因素所影响。 第一章绪论 酶与酶之间的差别是很大的。酶的三维结构决定了它们的催化活性和机理。大多数 的酶都要比它们的催化底物大得多，并且酶分子中只有一小部分( 3 4 个残基) 直接参 与催化反应。这些参与催化的残基加上参与结合底物的残基共同构成了发生催化反应的 区域，这一区域就被称为“活性中心或“活性位点”。有许多酶含有能够结合其催化 反应所必需的辅因子的结合区域。此外，还有一些酶能够结合催化反应的直接或间接产 物或者底物，这种结合能够增加或降低酶活，是一种反馈调节手段。通常情况下，酶对 其所催化的反应类型和底物种类具有高度的专一性。酶的活性位点和底物，它们的形状、 表面电荷、亲疏水性都会影响专一性。酶的催化可以具有很高的立体专一性、区域选择 性和化学选择性【6 朋。 目前，有关酶耐热性的研究已经越来越多的受到关注。究其原因主要是耐热酶较常 温酶有太多的优势，比如耐热酶在高温下比常温酶有更多的功能，而且具有反应速度快、 不易被杂菌污染等特点，最重要的是人类又无法工业化地培养和获取。但这并没有影响 耐热酶的推广，因为它已经在食品酿造、医药、环境保护和金属冶炼等领域得到了广泛 的应用。 至今为止，人类发现的最耐热的蛋白质是“c u t a l ”，它是由日本科学家于2 0 0 6 年发 现的，它在高达1 4 8 5 c 的情况下才会被破坏，比之前知道的最高耐热温度高出了3 0 c 【8 】o 现在普遍认为耐热温度超过5 0 的酶为耐热酶。而在目前人类获得耐热酶的方法主 要是通过筛选耐热微生物获得，不过产酶量很低。这些都促使人类去研究酶的耐热性的 机理。在以往的研究中，人们更多的是从分子生物学、结构生物学的角度，去分析二级 结构和三级结构等不同结构层次，来了解某个或某些酶的耐热性。至于研究发现的影响 耐热的因素也很多，比如氨基酸组成、二肽含量、氢键、盐桥、紧密度和疏水性等等。 其中： ( 1 ) 氨基酸组成( a m i n oa c i dc o m p o s i t i o n ) 在众多的影响因素中，氨基酸的组成被普遍认为跟蛋白质的耐热性有关。卢柏松等 【9 】通过比较耐热和常温的蛋白质在氨基酸组成上的差别，发现耐热蛋白质比常温蛋白质 含有更高的平均疏水性和带电荷氨基酸组成。s u h r e 等【l0 1 发现可以利用带电荷氨基酸和 非电荷氨基酸的比例的不同来区分耐热和常温蛋白质。 ( 2 ) 二肽组成( d i p e p t i d ec o m p o s i t i o n ) 有研究表明影响古细菌和细菌类蛋白质热稳定性的二肽种类是不同的【1 1 1 。g r o m i h a 等【1 2 】认为由于l y s t y r 和t y r - l y s 的作用，c a t i o n - n 效应可以稳定蛋白质。另外，l y s t y r ， g l u - i l e 和v a l r y r 在耐热蛋白质中具有显著的残基内部相互作用【1 3 1 。这也表明二肽对于 蛋白质耐热性起了重要作用。 ( 3 ) 氢键( h y d r o g e nb o n d s ) 人们对氢键影响蛋白质耐热性方面有不同的观点。有人【1 4 】认为氢键的形成对蛋白质 的稳定性有帮助，而又有研究f l5 j 表明氢键在耐热和常温蛋白质中没有明显的差别，对耐 热性没有影响u6 1 。 ( 4 ) 盐桥( s a l tb r i d g e ) 江南大学硕士学位论文 跟氢键一样，人们对盐桥的影响也持两种观点。有人认为盐桥对酶的耐热性没有太 大的影响。而有的观点则是认为盐桥是稳定耐热蛋白质的重要因素f 1 4 】【1 7 】。 ( 5 ) 疏水作用( h y d r o p h o b i ci n t e r a c t i o n s ) 疏水作用是一个从高能态向低能态转变的自动发生的过程，是稳定耐热蛋白质的重 要因素【1 4 】。s a r a b o j i 等【1 8 】认为疏水自由能对稳定耐热蛋白质很有作用。 ( 6 ) 包装效应( p a c k i n ge f f e c t ) 和溶剂接触表面积( s o l v e n ta c c e s s i b l ea r e a ) 建立在晶体结构基础上的突变试验表明，通过填充折叠构象中的疏水空腔和增加疏 水性包装可以增加蛋白质的耐热性【19 1 。s a d e g h i 等【1 4 】却发现耐热蛋白质和常温蛋白质有 相似的极性和非极性表面积和紧密度。 ( 7 ) 口一螺旋( 口h e l i x ) 口螺旋是蛋白质空间结构的基本组件，普遍存在于各种蛋白质中。而在耐热酶的口 螺旋中a l a 的含量较多。 ( 8 ) l o o p 区的稳定性 l o o p s 和转角( t u r n s ) 被认为是蛋白质中相连核心元件的弱连接，但研究表明它们可 能潜在地对提高蛋白质稳定性有作用，而l o o p 和n ，c 末端是影响蛋白质结构耐热性的 区域。f i s h 等【2 0 】发现耐热铁氧化还原蛋白的l 1 ，2l o o p 区可以增加疏水表面积，以提高 耐热性。而b e r z o v s k y 等【2 1 1 缩短l o o p 区后发现耐热性没有明显变化【2 2 1 。 ( 9 ) 温度因子( t e m p e r a t u r ef a c t o r ) 温度因子( b 因子) 反映了晶体中原子电子密度的“模糊度”，与酶活性中心的柔 性有关，不同的t 4 溶解酵素( 1 y s o z y m e ) 的稳定性随着结构刚性的增加而增大，晶体结构 中的b 因子随之减小f 2 3 】。p a r t h a s a r a t h y 等在比较耐热和常温蛋白质的b 因子之后，认 为b 因子的不同反映出了耐热和常温蛋白质在动力学方面的差别【2 5 】【2 6 】。 1 2 新的研究方法机器学习法 人们在按着生物学的角度继续深入研究的同时，也在尝试用其他思路和方法去解决 这个问题，而机器学习法就是在这个背景下被运用到这里来解决这样的问题。并且目前 已经取得了很好的研究成果，比如c h e n g 等人利用序列和结构的信息来预测单个氨基酸 突变对耐热性的影响，而他们选择了s v m 来进行预测的工作并得到了8 4 的准确率【2 7 1 。 而z h a n g 等人利用新型分类器l o g i t b o o s t 通过蛋白质主要结构来区分喜温和嗜热的蛋白 质，同样也得到了相当好的效果【2 引。 机器学习是一个多学科的领域，它包括人工智能，计算复杂性理论，概率统计，控 制论，信息论，哲学，生理学，神经生物学等学科。它是一个系统自我改进的过程，它 最初是从基于神经元模型以及函数逼近论的方法研究开始，而后发展到以符号演算为基 础的规则学习和决策树学习，在引入认知心理学中的归纳，解释，类比等概念之后，直 至最新的计算学习理论和统计学习( 包括基于马尔可夫过程的增强学习) ，它都在相关 学科的应用中起着重要的作用【2 9 1 。而在生物信息学方面，机器学习中被最广泛用到的方 法是支持向量机( s u p p o r tv e c t o rm a c h i n e s ) 和人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ) 。 4 第一章绪论 当计算机解决实际问题时，通常的过程是描述出一组给定输入如何推出所需的输 出。而人们的任务就是将其转化成一系列的指令，使计算机能够遵循指令得到期望的结 果。但是对于更复杂的问题有时无法由给定的输入计算出期望的输出，或者是代价太高。 所以这些问题都不能用传统的方法来解决，解决这类问题的一种策略是让计算机从指定 的样例中学习输入到输出的函数对应关系。这种过程通常称为学习方法，其中当样例是 由输入输出对给出时，称为监督学习。有关输入输出函数关系的样例称为训练数据。 当输入到输出存在内在函数时，该函数称为目标函数。由学习算法输出的对目标函数的 估计称为学习问题的解。而在学习模型中还有一个方面的问题是训练数据如何生成及如 何输入到学习器中，这其中就有批量学习和在线学习的区别。前者是直接把所有的数据 在学习一开始就全部提供给学习器；而后者则是让学习器一次只学习一个样例，并在接 受正确的输出前给出自己对输出的估计。在线学习中的学习器根据每个新样例更新当前 的假设，学习器的质量由学习期间产生的总错误数量来衡量。 而我们所用的这两种方法都是属于批量学习的，这样带来的问题是怎样衡量批量学 习中所产生假设的质量。在早期学习算法中通过学习产生简单的符号表示，再由专家来 理解验证。但是对于机器学习者来说，他们感兴趣的数据将越来越多，这会使得上面的 质量衡量标准难以实现，即使能够找到与训练数据一致的假设，它也可能无法对未见的 数据进行分类。所以一个假设正确分类训练集之外的能力称为泛化性，这正是要优化的 属性。在这种意义上，就不再要求把假设看做是真实目标函数的正确表示，即如果一个 假设能给出正确的输出，它就满足泛化性准则，所以泛化性在这种意义上就成为一个功 能性准则而不是描述性准则。接下来的问题就是提高泛化性，其中奥卡坶( o c k h a m ) 剃刀就是为了解决因为得到一致假设而使假设变得过度复杂问题而提出的。它是为了限 制假设的规模，它提出如无必要，不必增加复杂性，或者说是更加复杂的复杂性必须有 助于大幅提高训练数据的分类正确率。当然，也不是一味的降低复杂性，必须在复杂性 和精度之间做到启发式的平衡，比如最小描述长度( m d l ，m i n i m u md e s c r i p t i o nl e n g t h ) 准则就建议使用这样的假设：其函数描述长度与训练错误列表长度的和最短。采用的方 法是为了获得另一种平衡，它涉及泛化误差率上的统计边界，这些边界通常依赖于分类 器间隔这样的变量，并引发最优化该变量的算法。其优点在于统计结果为其提供了一个 有充分依据的理论基础，因此避免了基于错误直觉的启发式方法所带来的危险1 3 。 1 2 1 支持向量机原理 支持向量机( s v m ) 是在高维特征空间使用线性函数假设空间的学习系统，它是一 个来自最优化理论的学习训练算法，该算法实现了一个由统计学习理论导出的学习偏 置。此学习策略由v a p n i k 和他的合作者提出【3 1 1 ，是一个有准则性并且强有力的方法。 首先对监督学习来说，学习器会输入一个带有标记( 输出值) 的样例( 输入) 的训 练集。样例通常是以属性向量的形式给出，因此输入空间是r ”的子集。一旦给定输入 向量，就可以为问题选择一定数目的假设函数集。其中，线性函数是最容易理解而且应 用最简单。在两类问题的分类中通常用一个实值函数f ：x r ”专r 然后是：当( x ) 0 江南大学硕士学位论文 时，输出x = ( 而，) 给正类，否则给负类。考虑当厂( x ) ，x x 是线性函数的情况，函 数可以写成：厂( i ) = ( 协i ) + 6 2 砉嵋薯+ 6 ，这里( 访，b ) r ”r 是控制函数的参数， 决策规则有s g n ( 厂( i ) ) 给出，其中s g n ( o ) = l 。学习方法意味着要从数据中学习到这些 参数。其几何解释是，( 泓i ) + 6 = 0 定义的超平面将输入空间x 分成两个部分( 见图1 - 3 ) 。 图1 3 超平面和几何间隔 f i g 1 - 3h y p e r p l a n ea n dg e o m e t r i cd i s t a n c e 超平面是维数为1 1 1 的仿射子空间，它将空间分为两个部分，分别对应输入中的两类。 在图1 。l 中超平面是黑线，对应着上面的正区域和下面的负区域，当b 值变化时，超平 面平行于自身移动。而样例( i ，乃) 对应于超平面( 见6 ) 的间隔乃= 以( ( 办霉) + 6 ) ，其中 乃 0 ，表明( i ，乃) 被正确分类。超平面( 访，b ) 对应于训练集s 的间隔分布就是训练集s 中样例的间隔分布。有时所谓间隔分布的最小值指超平面( 访，b ) 对应于训练集s 的间隔。 在固定7 0 的情况下，定义样例( i ，m ) 对应于超平面( 访，b ) 和目标间隔厂的间隔松弛变 量，为f ( ( 暑，m ) ，( 访，6 ) ，) = 毒= m a x ( o ，7 一咒( ( 见i ) ) + 6 ) 。 对于感知器算法来说，它是通过在任意初始权重向量上增加误分的正训练样例或者 减去误分的负样例来工作地，在不失一般性的情况下，假定初始权重向量是零向量，这 样最终的假设是训练样例的线性组合：访= 窆口，m 毛，其中暑的系数由类别 决定，是 个正值，正比于墨被误分后的权重的更新次数。这使得误分次数少的点将有较小的啦， 而难分类的点将有较大的值。一旦样本s 固定，向量舀是一个在不同或者对偶坐标上可 供选择的表示假设的方法。不同的厅可能对应着相同的假设访，所以在对偶坐标中，决 策函数可以手写为：办( i ) - - - - s g l l ( ( 办i ) + 6 ) = s g n 【、 + 6 j ，最后整理z v _ 1 4 ： 办( i ) = s g n ( 砉哆乃( 砖冤) + b ) 。而感知器算法见图1 - 4 。 给定训练集s 6 第一章绪论 西卜0 ；b4 - - - 0 r - - m a x l g 划 重复 f o ri = lt o ， i f 乃( ：；。哆乃( 弓i ) + 6 ) o t h e n q 卜q + 1 b 。b + y f r 2 e n d i f e n df o r 直到在f o r 循环没有错误发生 返回办( i ) 的( 舀，b ) 图1 4 感知器算法( 对偶形式) f i g 1 4p e r c e p t r o na l g o r i t h m ( d u a lf o r m ) 但是线性学习器计算能力是有限的，目标概念通常不能由给定属性的简单线性函数 组合而成，而是应该寻找更抽象的特征。多层阈值线性函数可能可以作为这个问题的解， 这将把问题导向多层神经网络系统，这将是下面讲的第二种方法。在这，核函数是另一 种解决办法，即将数据映射到高维空间来增加线性学习器的计算能力。而线性学习器的 对偶形式使这种操作成为可能。因为用对偶形式表示学习器的优势在于在该表示中可调 参数的个数不依赖于输入属性的个数。通过选择恰当的核函数来代替内积，可以隐式地 将训练数据非线性地映射到高维空间，而不增加可调参数的个数，当然核函数必须能够 计算对应的两个输入特征向量的内积。为了用线性学习器学习一个非线性的关系，需要 选择一个非线性的特征集，并且将数据用新的表达式表示出来。这就说明应用一个固定 的非线性的映射，将数据映射到特征空间，在特征空间中使用线性学习器。所以，假设 考虑的假设集是如下类型的函数：厂( i ) = 芝谚( i ) + b ，其中歹：x 专f 是从输入空间到 某个特征空间的映射。先前线性学习器的对偶形式可以表达为训练点的线性组合，因此 决策规则可以用测试点和训练点的内积来表示：厂( 孑) = 耋q ( 芗( 墨) 歹( i ) ) + b ，见图 l - 5 。而核是一个函数k ，对于所有的i ，三x ，满足：k ( i ，三) = ( 歹( i ) 歹( 艺) ) ，其中孑是 从x 到特征空间f 的映射。所以之前的线性学习器的内积表达式将变化为如下的形式： ( i ) = 壹q 彤k ( 墨，孑) + 6 。在使用了核函数后，就不在需要为了在特征空间中学习而了 解潜在的特征映射。当然，想成为核函数还必须具备很多性质，其中对称性是明显的： k ( i ，孑) = ( 歹( 元) 歹( 三) ) = ( 歹( 三) 歹( 夏) ) = k ( 三，i ) ，再者，核函数中最重要的性质就是它 7 江南大学硕士学位论文 图1 - 5 特征映射 f i g 1 - 5f e a t u r em a p 必须满足m e r c e r 定理，即设x 是有限输入空间，k ( i ，三) 是x 上的对称函数。那么k ( i ，三) 是核函数的充分必要条件是矩阵足= ( k ( 霉，巧) ) ：，= 。是半正定的( 即特征值非负) 瞄1 。 接下来将要讨论的是机器学习算法的能力，即它在什么样的情况下能学习成功。不 过首先需要了解几个概念： ( 1 ) 样本复杂度( s a m p l ec o m p l e x i t y ) ：学习器以较高的概率收敛得到成功的假设， 需要多少训练样例。 ( 2 ) 计算复杂度( c o m p u t a t i o n a lc o m p l e x i t y ) ：学习器以较高的概率收敛得到成功 的假设，需要对大的计算量。 ( 3 ) 出错边界( m i s t a k eb o u n d ) ：在成功收敛到一个假设后，学习器对训练样例的 错误分类有多少次【2 9 】。 所以为此要讨论学习问题的一个特殊框架，在统计学里它被称为一致收敛比率。在 在计算机科学中，它被称为可能近似正确( p a c ，p r o b a b l ya p p r o x i m a t e l yc o r r e c t ) 学习模 型。一个模型的关键假设是训练数据和测试数据是根据某个未知但固定的分布d 独立同 分布的( i i d ) 产生的。比如输入输出对( i ，y ) x 一1 ，1 ) 是同分布，在考虑了分布随 时间变化或训练集的产生不是完全无关的情况下，对模型做了修改。同时模型还忽略了 学习器影响样例选择的情况。因为测试样例也是由分布d 产生的，所以自然由随机产生 的样例被误分来进行误差的度量。所以，定义分类函数h 在分布d 上的误差p ( h ) 为： e r r ( h ) = d ( 孑，y ) ：办( 孑) y ，这个度量也称为风险函数。其目的是为了用几个量来断定 d 误差界，因为p a c 的结论通常都是表示为要获得特定等级误差在样本个数上的界。考虑 一个固定的推断规则，它从学习器配置的分类规则h 中选择一个假设办。，而后建立数据 集s = ( ( 墨，m ) ，( 墨，m ) ) ，其中s 包括了从分布d 按照i i d 标准选择的，个训练样例。 8 第一章绪论 在这里可以将泛化误差p ( 红) 看作是在训练样例上的随机变量。p a c 模型需要一个可 靠的泛化误差界，因为它界定了泛化3 差e r r d ( 红) 分布的尾部。其大小由学习器指定的 参数艿决定。所以一个p a c 界的形式是占= s ( z ，日，艿) ，并在随机产生的数据集s 上产生 至少以概率1 - 万判定所选假设红的泛化误差界是：p ? ( 忽) s ( ，h ，艿) ，所以这个也就是 可能近似正确学习p a c ，同样这也导出了训练集在一个假设下误差的概率为： d 7 s ：e ? ( 吃) 占( z ，h ，万) g 的概率界是： d s ：与办一致而且p ( 办) 占 ( 1 一s ) 7 e x p ( - m ) ( 1 1 ) 下面假定所有的1 日1 个假设有大的误差，其中的与s 的一致的概率至多为：i h l e x p ( 一占z ) ， 所以这样就得到了：d 。 s ：与办一致而且p ( 办) 占 - 一2 。 到现在问题就都转化为在寻找一个参数向量，而在通常的情况下该向量在某种约束 下使某个代价函数最小( 或是最大) 。所以，机器学习的问题到这就转化成了在最优化 9 江南大学硕士学位论文 理论框架下进行分析的形式。而在s v m 中遇到的代价函数都是凸二次函数问题。其中 最原始的问题是：在给定的域q 冬r ”上定义的函数f ，9 1 ，i = 1 ，k 与囊，i = 1 ，m ： 在这样的条件下：吕( 访) 0 i = 1 ，k 曩( 访) = 0 i = 1 ，m 求该式的最小值：( 访) 谚q ( 1 2 ) 在这里厂( 访) 就是目标函数，其他关系被称为不等式约束和等式约束。而解决该类问题 的最重要的方法就是拉格朗日理论。这个理论最核心的概念就是拉格朗日乘子和拉格朗 日函数。而在k u h n t u c k e r 理论中进一步将这个方法扩展到不等式约束的情况，而这个 扩展的理论为优化s v m 提供了有效地方法。下面假设建立个最优化问题，其中目标 函数( 访) ，等式约束曩( 访) = 0 ，= 1 m ，定义拉格朗日函数： 三( 茹，方) = ( ；) + 喜屈囊( 茹) c ，3 ， 其中的系数层称为拉格朗日乘子。所以在f ，曩c 1 下，对于一些万值，点秽在约束 红( 访) = 0 ，扛1 ，1 7 1 下是厂( 访) 的最小值的必要条件是： 掣：石( 1 4 ) 驾箬：。 ( 1 5 ) 8 8 一。 如果三( 死矽) 是访的凸函数，上述条件也是充分的。其中第一个条件是给出了一个新的 方程组，而第二个条件是返回等式约束。当然联立解这个方程组可以得到解。而 k u h n t u c k e r 定理给出了一般的最优化问题有最优解的条件。给定一个定义在凸域 q r ”上的最优化问题： 在这样的条件下：岛( 访) 0 i = l ，k 曩( 访) = 0 i = 1 ，m 求该式的最小值：( 访) 访q ( 1 6 ) 其中f c 1 是凸的，并且，曩是仿射函数，一般地，一个点秽是最优点的充要条件是 存在反，厉满足： 兰曼堡笪) ：石 0 w 兰曼堡鲨! ：o o p z ( 莎) = o i = 1 k 蜀( 矿) o i = 1 k 1 0 ( 1 7 ) ( 1 8 ) ( 1 9 ) ( 1 1 0 ) 第一章绪论 彳0 待1 ，k( 1 1 1 ) 在这些条件中，第三个关系称为k a r u s h k u h n t u c k e r 互补条件，它意味着对于积极约束 有z 0 ，但是对于非积极约束有口j = 0 。在使用拉格朗日定理解凸最优化问题应该使 用对偶形式来描述，因为用对偶形式来表示原问题通常比较容易处理，而直接处理不等 式约束比较困难。而对偶的形式可以在问题中引入对偶变量的拉格朗日乘子来解决问 题，这也是之前讨论对偶形式的原因。之后，可以把拉格朗日函数对于各个原变量的导 数置零，并将得到的关系代入原拉格朗日函数，这样的话就将原问题转化为对偶问题并 消除了原变量的相互关系。而对应于显示的计算函数： 口( 厅，万) = 聪三( 访，舀，万)