（通信与信息系统专业论文）基于afsa的svm参数优化及其应用.pdf

太原理工大学硕士研究生学位论文 基于a f s a 的s v m 参数优化及其应用 摘要 语音识别是语音信号处理的一个重要方面，是人机交互技术的基础， 有着广阔的应用前景。语音识别是典型的多类分类问题，因此，善于解决 高维分类问题的支持向量机很快被应用到语音识别中。支持向量机是在统 计学习理论基础上发展起来的一种性能优良的学习机器。目前存在的问题 是支持向量机的执行效果依赖于其参数的设置，但到目前为止还没有一个 固定的理论来指导如何寻找其参数。本文分析了支持向量机模型中各个参 数对模型的影响，并选用人工鱼群算法对模型中的参数进行了优化，形成 了基于人工鱼群算法的支持向量机参数优化方法。 本文首先系统地介绍了支持向量机的基本原理以及目前已存在的支持 向量机的种类，分析了模型中参数对其性能的影响，并采用人工鱼群算法 优化支持向量机参数。为了验证基于人工鱼群算法的支持向量机在语音识 别系统中的识别效果，本文构建了基于径向基核支持向量机的非特定人孤 立词语音识别系统，并进行了大量的仿真实验。实验结果表明，基于基本 人工鱼群算法的支持向量机应用于语音识别系统中均取得了优于隐马尔柯 夫模型的识别结果。 其次，为了提高所构建模型的识别效果，本文对人工鱼群算法进行了 深入的研究，对其进行改进，引入小生境技术，用来维持算法中样本数据 的多样性。同时，利用常用测试函数对改进算法进行测试，取得了满意的 太原理工大学硕士研究生学位论文 结果。本文构建了基于径向基核支持向量机的非特定人孤立词语音识别系 统进行实验。实验结果表明，基于改进人工鱼群算法优化的支持向量机参 数的语音识别系统的识别效果较理想，从而说明核参数和惩罚因子的不同 取值也会影响支持向量机的推广性能，从而影响语音识别系统的识别效果。 核函数的类型、核参数以及惩罚因子的选取直接影响着支持向量机语 音识别系统的识别效果。然而，到目前为止，支持向量机的核函数、核参 数及惩罚因子的选择还没有科学的方法，它们的选择只能根据经验、大量 的反复实验进行对比等方法来进行选择，带有很大的局限性。针对这个问 题，本文做了初步的研究，实现了在核函数类型确定的前提下，用人工鱼 群算法对核参数和惩罚因子进行优化，并用基于优选参数值的支持向量机 进行语音识别实验，识别率得到了一定的改善和提高。 关键词：支持向量机，参数优化，人工鱼群算法，小生境技术，语音识别 n u u 蝴t e r so p t i m i z a t i o na n d a p p l i c 钢 1 i o no fs v mb a s e do n a f s a a b s t r a c t s p e e c hr e c o g n i t i o ni sa ni m p o r t 趾ta s p e c to fs p e e c hs i g n a lp r o c e s s i n g i ti s t h ef - o u n d 撕o no fh u m a n c o m p u t e ri n t e r a c t i o n t e c h n o l o g y a n dh a sw i d e a p p l i c a t i o np r o s p e c t a u t o m a t i cs p e e c hr e c o g 血i o ni se s s e 埘a l l yap r o b l e mo f p a t t e m 珈i u l t i c l a s sc l a s s i f i c a t i o n ，s ot h es v mc l a s s i f i e rw h i c hi sw e l la d 印t e dt o 1 1 i 曲- d i m e n s i o n a lc l a s s i 矗c a t i o np r o b l e m si s 印p l i e di n 也es p e e c hr e c o g l l i t i o n q u i c l ( 1 y s u p p o nv e c t o rm a c h i n ei sah i 曲- p e 墒衄a n c e1 e 锄i n gm a c h i n eo nt h e b a s i so fm es t a t i s t i c a l l e a n l i n gt h e o r y h o w e v e rt h e r ei sap r o b l e mi ns v m t h a t i td 印e n d so nt h ep e 、o 衄a n c eo ft h ep a r a m e t e r ss e t t i n g s ，i n c l u d i n gp e n a l t i e sa n d k e m e lp 越吼e t e r s ，b u tn os u i t a b l e 1 e o 巧c a ng u i d et of i n da d a p t e d p 掘i m e t e r s t h ep a r a m e t e r si ns v mm o d e la r ea 1 1 a l y z e d ，m es v m m o d e lp 啪m e t e r sa r e o p t i i n i z e db ya r t i 丘c i a lf i s hs w 锄ma 1 9 0 r i 也l ，a n das v mp a r a m e t e r s o p t i 工n i z a t i o nm e t h o db a s e do na n i 丘c i a lf i s hs w a l l 咂a l g o r i t h m t h i sp a p e rf i r s ti n t r o d u c e dt h eb a s i cp r i n c i p l eo fs u p p o r tv e c t o rm a c h i n e a j l dt h ee x i s t i n gt y p i c a lt y p e s s y s t e m a t i c a l l y a n a l y z e dt h ei n n u e n c eo ft h e p 硼a m e t e r sf o rt h es v mm o d e la n du s e da f s at oo p t i m i z et h es v m p a r a m e t e r s i no r d e rt ov 谢矽t h er e c o g l l i t i o ne f f e c to fs u p p o nv e c t o rm a c h i n eb a s e do n a f s ai ns p e e c hr e c o g l l i t i o ns y s t e m ，t h i sp 印e rc o n s 缸u c t e df o u rn o n s p e c i f i c i i 工 p e r s o na 1 1 di s o l a t e dw o r d ss p e e c hr e c o g n i t i o ns y s t e m w h i c hi sb a s e do ns u p p o r t v e c t o rm a c h i n e so fr a d i a lb a s i sk 锄e l 向n c t i o na n dd i da1 0 to fs i m u l a t i o n 唧丽m e n t s t h ee x p 耐m e n t a lr e s u l t s s h o wt h a tt 1 1 er e c o 印i t i o nr e s u l t so f s n e e c hr e c o 蛐j t i o ns v s t e mw h i c hi sb a s e do nr a d i a lb a s i sk 锄e 1s u p p o r tv e c t o r s d e e c hr e c o 聊n o ns y s t e mw n l c nl sb a s e qo nr a q l a ld a s l sk e i i l e ls u p p u i lvc o l u l m a c h i n eb a s e do na f s ai sv e 巧g o o da n db e t t e rt h a nt h er e c o g n i t i o nr e s u l t st h a t i sb a s e do nh i d d e nm 破o vm o d d s e c o n d l y ，i no r d e rt oi m p r o v et h er e c o g n i t i o nr e s u l t s o ft 1 1 ec o n s t n l c t e d m o d e l ，t 1 1 i sp 印e rs t i l d i e da f s aa j l dd i ds o m ei m p r o v e m e n tu s i n gt h en i c h e t e d m o l o g yt om a i n t a i nm ed i v e r s i t yo f t h es 锄p l ed a t a a tt h es 锄et i m e ，t h e c o m m 咖t e s t i n g 如n c t i o n sw e r eu s e dt ot e s tt h ep e 而珊a n c eo ft h ei i n p r 0 v e d a l g o r i t h m a n da 出e v e d s a t i s f a c t o 巧 r e s u l t s t h i s p 印e r c o n s t m c t e da n o n s p e c i 丘cp e r s o na n di s o l a t e d w o r d ss p e e c hr e c o g n i t i o ns y s t e mb a s e do n s u p p o r tv e c t o rm a c h i n eo f r a d i a lb a s i sk e m e l 如n c t i o n i nt h ee x p e r i m e n t s ，t h e r e c o g n i t i o nr e s u l t so fs p e e c hr e c o g n i t i o ns y s t e mw h i c h i sb a s e do nr a d i a lb a s i s k e m e ls u p p o r tv e c t o rm a c h i n eb a s e do ni m p r o v e da f s ai sv e r yg o o d t 1 1 e e x p 丽m e n t a lr e s u l t ss h o w t h a tt h ed i 丘e r e n tv a l u e so f k e m e lp 踟e t e ra n de 仃o r p e n a l t yp a r a m e t e r sa 骶c tt 1 1 eg e n e r a l i z a t i o np e 墒册a n c e o fs u p p o r tv e c t o r m a c h i n ea n da c c o r 血g l ya 圩e c tt h er e c o g n i t i o ne 虢c to ft h es p e e c hr e c o 印i t i o n s y s t e m t h es e l e c t i o no fk 锄e lf l c t i o nt y p e ，k e m e lp a r 锄e t e rv a l u ea 1 1 de r r o r p e n a l 够p 舢e t e rv a l u ed i r e c t l y a f j | e c t st h er e c o g n i t i o ne f r e c t o fs p e e c h r e c o g n i t i o ns y s t e mb a s e do ns u p p o r tv e c t o rm a c h i n e h o w e v e r m e r ei s n o i v 太原理工大学硕士研究生学位论文 s c i e n t 俯cm e t h o dt os e l e c tm e s et h r e ef a c t o r sa n dp e o p l es e l e c tt h e mo n l y a c c o r d i n gt oe x p e r i e n c ea j l dr 印e a t e de x p 谢m e n t s t h e r e 耐s t sg r e a tl i m i t a t i o n a i 血n ga tt l l i sp r o b l e m ，t h i sp 印e rd i dp r e l i m i n a 拶r e s e a r c ha n dp r o p o s e da m e t h o dt od op 猢e t e r s 叩t i m i z a t i o nt h a tu s e s 枷f i c i a l 丘s hs w 赫a l g o r i 也n l i nc o n d i t i o no ft h ek e m e l 向n c t i o n t y p ei sf i x e d a t1 a s tt b j sp a p e rc o n s m l c t e da s p e e c hr e c o g n i t i o ns y s t e mb a s e do nt h es u p p o r tv e c t o rm a c h i n e 、h o s ek e m e l p 越i m e t e ra j l de 啪rp e n a l t yp 猢e t e rh a v eb e e no p t i m i z e da n dt 1 1 er e c o 印i t i o n r a t e sg e tc e r t a i ni m p r o v e m e n t k e yw o r d s ： s u p p o r t v e c t o rm a c h i n e ， a n i f i c i a lf i s hs w 釉a l g o 打也m ， p a r a m e t e r so p t i m i z a t i o n ，n i c h et e c h n o l o g ms p e e c hr e c o g n i t i o n v 太原理工大学硕士研究生学位论文 二l 一 v i 太原理工大学硕士研究生学位论文 1 1 课题研究的背景及意义 第一章绪论 近年来，计算机技术取得了飞速的发展，人工智能机器的应用也越来越广泛，给人 类的生活带来了无穷的便捷。然而，随着生活水平的提高，人们对计算机的智能化要求 也越来越高，最迫切的需求体现在人机接口上，因此，直接用语言对计算机发号施令成 了人们渴望的事情。而语言是人类联络感情、交流思想，传递信息最自然、最有效、最 常用的方式。所以，人与机器最方便直接的交流方式就是语言通信。 语言是人与人之间交流信息的主要手段之一，自计算机发明以来，人们就一直致力 于使其能够理解人类语言。语音是语言的一种声学表现，语音识别技术是一门交叉学科， 正逐步成为人机接口的关键技术，语音识别技术是让机器通过识别和理解过程把语音转 变为相应的文本或命令的高级技术，它是将声学、语音学、计算机、信息处理和人工智 。能等结合在一起的一项综合技术，其应用需求十分广泛。语音识别技术分为狭义和广义 。两种，其中狭义上的语音识别技术是指准确地理解语音信号的含义；而广义上的语音识 别技术是指分辨出语音信号中特定的内容，包括识别说话人的语言、说话人的身份等等。 语音识别技术在很多方面已经达到了实用化的程度，同时高性能的语音识别系统也相继 问世，如听写机、语音拨号系统、银行信用卡查询等等。目前，语音识别技术已经进入 家电、汽车电子、工业、医疗、家庭服务、通信、消费电子产品等多个领域【l 】，在一些 手工难以操作的情况下、对人体造成伤害的工作条件下或者工作环境恶劣时，均可采用 语音发出的相应控制命令，来操作设备使其完成相应的任务。由此看来，语音识别技术 不仅能使计算机成为人类日常生活中得心应手的工具，而且在操作机器、控制生产过程、 通信等领域也大有用武之地。 1 2 语音识别的发展与研究现状 2 0 世纪5 0 年代语音识别技术的研究工作开始起步，以a t & tb d l 实验室的a u d r 系统为标志，它是一个可以识别十个英文数字的特定人孤立词语识别系统。1 9 5 9 年， j w r o 哂e 和c d f 嘶g e 采用数字计算识别孤立字及英文元音，由此开始了计算机语音 识别。6 0 年代末，n a k u r a 提出的动态时间规整算法和语音信号线性预测技术，解决了 太原理工大学硕士研究生学位论文 语音的不等长匹配和特征提取问题，为特定人孤立词识别技术提供了有效的途径。8 0 年代初，矢量量化技术和隐马尔柯夫模型理论的成熟，推动了基于线性预测倒谱和唧 技术的特定人孤立小词汇量语音识别系统的实现。此时研究者将语音识别的研究重点转 向连接词的语音识别以及各种连接词语音识别算法的开发。同时，语音识别算法逐渐从 模板匹配技术转向基于统计模型技术，这是语音识别技术发展的一个方向。研究方向逐 渐从微观转向宏观，将研究的重点由追求细化语音特征转向从统计的角度来建立最佳的 语音识别系统。其中隐马尔柯夫模型是典型，该模型很好的描述语音信号的时变性和平 稳性，将大词汇量连续语音识别系统的成功开发变为可能。同时统计语言模型也开始逐 渐取代基于规则语言的模型。8 0 年代中期，研究者们在实践中成功应用了隐马尔柯夫模 型和人工神经网络。9 0 年代之后，人工神经网络技术为语音识别技术的发展提供了一条 新途径，它具有自鲁棒性、并行性、非线性、适应性、容错性和学习特性，这些特性在 结构和算法上都显示出了很大的潜力。此时，在参数提取和优化、细化模型的设计以及 系统的自适应技术上取得了关键进展。语音识别技术进一步成熟，语音识别系统开始从 实验室走向实用。 目前，一语音识别技术在实验室研究中的识别精度已经达到了相当的高度。美国的 c 锄e 西em e l l o n 大学开发的s p h i n x 系统将语言理解和语音识别结合在一起，成功的完 成了非特定人大词汇量连续语音识别的任务。2 0 0 3 年，m 的大词表两级搜索语音识 别系统在康柏i p a q 掌上电脑成功实现。另外，i b m 以其大词汇量连续语音识别引擎 a v o i c e 为基础，研究开发了嵌入式a v o i c e ，并在各项应用中取得了骄人的成绩。 汉语的一些特性使得汉语的语音识别技术具有更大的难度。我国的语音识别研究工 作起步于五十年代，稍晚于国外，但近年来飞速发展，并取得了突出的成果，逐步开始 从实验室走向实用。我国中科院自动化所成功研制了非特定人、连续语音听写系统和汉 语语音人机对话系统，该系统的字准确率或系统响应率可达9 0 以上。近年来，随着中 国的国际地位与日俱增，以及在经济和市场方面所处的重要位置，汉语语音识别也越来 越被重视，国外许多大公司也纷纷投入到汉语语音识别系统的开发中，如i b m 、a p p l e 、 m o t o r o l a 等公司。 尽管语音识别技术的研究工作已经进行了5 0 多年，同时也取得了很大的成绩，然 而研究出一台能听懂任何人的任何语言的机器还是研究者们追求的目标，距离技术的实 现还有一定的距离。系统的识别速度、机器对说话者的依赖程度、词汇量的大小、语言 2 太原理工大学硕士研究生学位论文 的类型等很多方面都达不到实际的需要。所以，语音识别技术的发展还有待于更加深入 的研究。 1 3 支持向量机与语音识别 人工神经网络和隐马尔柯夫模型是目前使用较多的语音识别模型。人工神经网络【2 】 具有自学功能、联想存储功能以及高速寻找优化解的能力，该方法以其较强的模式分类 能力在语音识别中取得了广泛应用，然而也存在着一些难以弥补的缺陷，如容易过学习 或泛化能力差、网络结构难以确定、局部最优等。基本隐马尔柯夫模型【3 】作为一种统计 分析模型，具有很强的动态时间序列建模能力，其计算量小，但分类决策能力差，需要 用到语音识别的先验统计知识等。上面提到的两类方法都是建立在样本数目趋于无穷大 的渐进理论基础上的，因此只有当训练样本集充分大时，性能才会最好，然而实际问题 中样本数目往往很难趋于无限大，因此难以达到理想的效果。 近年新发展起来的支持向量机技术【4 】是建立在统计学习理论的v c 维理论和结构风 险最小化原理基础上的。统计学习理论既考虑了对渐近性能的要求，又追求在有限的信 息条件下获得最优的结果。与神经网络相比，支持向量机具有更坚实的数学理论基础， 能够有效地克服神经网络方法所固有的过学习和欠学习的问题。另一方面支持向量机具 有很强的非线性分类能力，它通过引入核函数，将输入空间的样本映射到高维特征空间， 将输入空间的非线性划分问题转化为高维特征空间的线性划分问题，有效地解决了有限 样本条件下的高维数据模型构建问题，解决了维数灾难问题，同时还具有泛化能力强、 收敛到全局最优、维数不敏感等优点。同时，支持向量机这种算法也是对隐马尔柯夫模 型的有效补充。从原理上来分析，隐马尔柯夫模型受极大似然准则的限制，分类能力较 差，其结果主要反映了相同种类样本的相似度，而支持向量机的输出结果则侧重体现了 不同种类样本间的差异，具有极强的分类能力。综上所述，支持向量机这一方法能较好 地解决小样本、非线性、高维数和局部极小点等实际问题，它与基于经验风险最小化的 隐马尔柯夫模型以及人工神经网络等方法相比具有更好的泛化能力和分类精确性，研究 证明【5 】更适合用于语音识别。 1 4 人工鱼群算法与支持向量机 支持向量机是从样本线性可分条件下的最优超平面发展起来的，目前已应用于分类 3 太原理工大学硕士研究生学位论文 问题，通过最大化分类超平面的间隔，实现结构风险最小化的原则。应用支持向量机分 类模型求解具体问题时，支持向量机通过核函数将样本从输入空间映射到高维的特征空 间，并在高维的特征空间中构造问题的最优分类超平面，即将问题转化成一个凸二次优 化，实现了问题从低维空间像高维的推广，同时也解决了维数灾难的问题。支持向量机 是在统计学习理论基础上发展出的一种性能优良的学习机器，其根据有限的样本信息在 模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力，然而，支持向 量机始终存在的一个问题是它的执行效果依赖于参数的设置【6 j ，其中包括惩罚因子和和 参数，但却没有一个合适的理论来指导如何寻找适应于具体的样本数据的参数。 人工鱼群算法是一种基于群体行为的动物自治体模式，其本质是一个复杂的智能体 系统，主要利用了鱼的觅食、聚群和追尾行为，从构造个体的简单的底层行为做起，通 过各动物个体的局部寻优行为，最终在群体中使全局最优值突现出来，具备分布并行的 寻优能力，该算法具有对初值和参数选择不敏感、鲁棒性强、简单、易于实现等方面的 特点。人工鱼群算法【7 】自李晓磊等人在2 0 0 2 年首次提出以来，得到了国内外学者的广泛 关注，对算法的研究应用已经渗透到多个应用领域并由解决一维静态优化问题发展到解 决多维动态组合优化问题。近年来，研究者们对人工鱼群算法从各个方面进行改进例， 以提高算法的优化性能，同时将人工鱼群算法与其它智能优化算法融合驯，以克服相互 的缺陷，并已取得了良好的效果，关于人工鱼群算法的应用范围也扩展到了更多的领域 【1 0 】，如油田系统、计算机网络优化、数据挖掘、离散优化问题等。 从目前对人工鱼群算法的研究来看，该算法只需要比较目标函数值，对目标函数的 性质要求不高；对初值和参数的设定要求不高，有较大的容许范围；具备并行的处理能 力，对于一些精度要求不高的场合，可以快速得到一个可行解；不需要问题的严格机理 模型，这使得它的应用范围得以延伸。因此，本文选用人工鱼群算法这一方法来优化支 持向量机的参数，解决支持向量机参数寻优的问题，从而提高其性能。 1 5 本文的结构安排 本文共分为五章，具体内容如下： 第一章是绪论，简单介绍了本课题的研究背景和意义、语音识别的发展与现状研究， 同时对支持向量机应用于语音识别的状况进行分析，并对将人工鱼群算法应用于支持向 量机参数优化的优势进行了简单阐述，最后介绍了本文结构的安排。 4 太原理工大学硕士研究生学位论文 第二章主要阐述了支持向量机的理论知识和基本原理，着重讲述了关于支持向量机 模型的建立以及参数选择的重要性，并对支持向量机在语音识别领域的应用进行了初步 研究。 第三章主要介绍了人工鱼群算法的基本原理和流程，人工鱼群算法用于优化支持向 量机参数的优势，选用测试函数对该算法进行测试实验，并取得了满意的结果，接着进 行了语音识别系统的仿真实验，随后，对人工鱼群算法进行改进。 第四章本章主要介绍了小生境技术的发展，提出了生境鱼群算法，并采用典型的测 试函数对之进行了测试实验，阐述了用生境鱼群算法优化支持向量机参数的问题。本章 在将i m f 函数当作核函数的情况下，仿真实现了生境鱼群算法对核参数和惩罚因子的 优化，并将优选出的核参数和惩罚因子用作支持向量机参数，应用到了语音识别系统， 识别率得到了提高。 第五章是总结与展望，总结了研究生期间的主要工作，并对其中存在的一些不足和 以后的研究方向做了分析。 5 太原理工大学硕士研究生学位论文 2 1 支持向量机基础 第二章支持向量机基础研究 支持向量机( s u p p o r tv e c t o rm a c b j n e ，s v m ) 是k 等人于1 9 9 5 年提出的一种 新型机器学习方法，它是一种建立在统计学习理论的结构风险最小化原理和v c 维理论 基础上的算法，主要根据有限样本信息在模型的复杂性和学习能力之间寻求最佳折衷， 从而获得最好的推广能力1 1 】。支持向量机在很大程度上解决了非线性和维数灾难、模型 选择与过学习以及局部极小点等问题。 2 1 1 支持向量机的发展 机器学习主要研究的是从现有的观测数据出发寻找规律，并遵循这些规律对无法观 测的数据及未来的数据进行分类和预测，统计学习理论是其中的一种实现方法，是一种 专门研究小样本情况下机器学习规律的理论。该理论主要针对小样本统计问题建立了一 套新的理论体系，其不仅考虑了对渐进性能的要求，而且追求在有限信息的条件下得到 最优结果。直到2 0 世纪9 0 年代，统计学习理论趋于成熟，并且开始受到越来越广泛的 重视。随后，支持向量机一种新的机器学习算法出现了，它是在统计学习理论基础 上发展起来的，该方法根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折 衷，以期获得更好的推广能力。 支持向量机的奠基者、却m k 早在2 0 世纪6 0 年代就开始研究统计学习理论，直到 1 9 7 1 年提出了v c 维理论，它是一个支撑支持向量机算法的重要理论，随后，进一步提 出了结构风险最小化原理，该原理被认为是支持向量机的又一理论基础。随着最优边界 分类器概念的提出以及对非线性最优分类问题进行的探讨和分析，1 9 9 5 年，v a p 址完 整地提出了支持向量机算澍1 2 】。支持向量机算法的潜在应用价值吸引了国内外众多学者 的目光，近年来，学者们提出了一系列改进的支持向量机算法【1 3 】，并对核函数进行了大 量的研究l l 引，同时，支持向量机也成功的应用于模式识别的众多领域，如人脸识别和人 脸检测【15 1 、信号处理【1 6 1 、手写字体与数字识别【17 1 、图像分类与识别【1 8 】、文本分类【19 1 、 语音识别【2 0 】等众多研究领域。 通过对目前已有相关文献和研究成果的归纳，可以得知，目前对支持向量机理论与 6 太原理工大学硕士研究生学位论文 应用的研究主要集中在三个方面： ( 1 ) 对现有支持向量机算法的改进与完善。随着对支持向量机的深入研究，研究 人员对支持向量机算法做了一些变形从而提出一些支持向量机的变形算法，如v s 、 c 。s 订、o n e c l a s ss 订、w s v m 、r s 订和l s s v m 等算法。这些变形算法主要是通 过增加函数项、改变变量或系数等方法使公式变形，从而产生各种有某一方面优势或者 一定应用范围的算法。 ( 2 ) 针对规模较大的数据集的有效学习算法的研究。随着计算机配置的提升，人 们很自然地使用并行计算来处理规模较大的数据集。对于支持向量机，并行的概念有两 种解释方式：一是算法本身计算步骤的并行性；一是通过同时使用多个支持向量机分类 器实现的并行。前者的实现相对困难，而且对实际问题的贡献不大；后者容易实现也能 达到并行处理数据集的目的。 ， ( 3 ) 核函数的构造和选择。支持向量机的核心为其核函数，采用不同的核函数就 可以构造不同类型的非线性决策的学习机，从而产生不同的支持向量机算法。在解决实 际问题时，通常会直接给出核函数的形式，目前研究最多的核函数有线性核函数、多项 式核函数、径向基核函数和多层感知机等。 2 1 2 统计学习理论核心内容 v c 维是统计学习理论中的一个重要概念也是支持向量机的一大理论基础，在模式 识别方法中关于v c 维的直观定义【2 1 】是：对于一个指示函数集，若存在七个样本能够被 函数集中的函数按所有可能的2 种形式分开，则称函数集能把七个样本打散，此时函数 集的v c 维就是它能够打散的最大样本数目| j 。如果存在七个样本的样本集能够被函数 集打散，而不存在七十1 个样本的样本集能被该函数集打散，那么函数集的v c 维就是七。 同时需要注意的是，存在七个样本的样本集能够被函数集打散并不等同于任意七个样本 的样本集都能够被函数集打散。函数集能打散的样本的个数越多，则函数集的“表达能 力 越强。函数集的“表达能力 在这里是指函数集的大小或者丰富程度。若对任意数 日的样本都有函数能将它们打散，则函数集的v c 维是无穷大。有界实函数的v c 维可 以通过用一定的阈值将它转化成指示函数来定义。 如图2 1 所示，可以形象的说明大三的问题，图中七= 3 ，表示样本集中有三个样本， 且每个样本都有两种可能的形式，分别为十字星或者五角星，则样本集所有可能的形式 7 太原理工大学硕士研究生学位论文 有2 3 = 8 种，若一个指示函数集中的函数能够按所列的8 种形式把该样本集分开，则可 称该函数集的v c 维是3 。 图2 - l “打散”概念示意图 f i g l l r e 2 - ln es c h 锄a t i cd i a 鲫no f s c a t t 盯c 0 n c e p 6 0 n v c 维反映了函数集的学习能力，函数集的v c 维越大则其学习机器越复杂。然而， 现在还没有一种通用的理论或方法来计算任意函数集的v c 维，而只是对一些特殊的函 数集可以计算其v c 维。对于一些较复杂的学习机器，其v c 维除了与函数集有关外， 还受学习算法等的影响，v c 维的确定就更加困难。所以，对于给定的函数集，如何用 理论或实验的方法来计算其v c 维是进一步研究的一个问题。 结构风险最小化理论是支持向量机的另一大基础，它是对经验风险和置信范围进行 综合而得到的，是期望风险的一个上界。从推广性的界圈的讨论中可以发现，我们需要 同时最小化经验风险和置信范围，因此，经验风险最小化准则在样本数目有限时是不合 理的。为了得到较小的真实风险，我们需要最小化结构风险，即经验风险和置信范围的 和。在传统的机器学习方法中，调整置信范围的过程实际上就是选择学习模型和算法的 过程，如果已选模型比较适合现有的训练样本，就可以取得比较好的结果。然而一般来 说，这种方法缺乏理论指导，只能依赖先验知识和经验，这样就造成了对使用者经验技 巧的过分依赖。 统计学习理论提出了一种新的策略，它把函数集构造成一个函数子集序列，同时使 各个子集按照v c 维的大小排列，然后在每个子集中寻找最小经验风险，从而在子集间 折衷考虑经验风险和置信范围，最终取得真实风险的最小，将这种思想称作结构风险最 小化( s 仃u c n l 同础s km i l l i l l l i z a t i o n ) 准则，即s i 乇m 准则。 8 太原理工大学硕士研究生学位论文 风险 函数集子集：墨c 岛c 岛 v c 维五2 五3 图2 2 结构风险最小化示意图 f i g 盯e 2 - 2n e s c h e i i l a t i cd i a g r a mo fs t r u c t i l 】m 鼬s km i l l i m i z a t i o n 如图2 2 所示，形象地表明了各种状态之问的关系，图中表示寻找最小期望风险上 界时需要综合考虑经验风险和置信范围的变化趋势，最后，选取的函数子集可看作是具 有最佳泛化能力的函数集合。 实现结构风险最小化有两种思路：一种是在每个子集中求最小经验风险，然后依据 每个子集的置信范围选择使最小经验风险和置信范围之和最小的子集，但这样比较费 时，尤其是在子集数目比较大时可行性不是很强；另一种是先设计函数集的某种结构从 而使每个子集中都能取得最小的经验风险，然后只需选择使得置信范围最小的子集，子 集中使经验风险最小的函数即为最优函数。支持向量机也是采用第二种方法来实现结构 风险最小。 2 1 3 最优分类面 在讨论线性可分情况下的两分类问题时，学者们提出了支持向量机这一种新型机器 算法，随后在此基础上逐渐将问题扩展到非线性问题分类的情况下，然而其基本思想也 可以用两类个体的线性可分情况来说明 1 2 】。假设一组两类个体线性可分的样本集为： 丁= ( 五，y 。) ，( 五，乃) ) ( 工，j ，) 7 ，其中x = r ”，职】，= 一1 ，1 ，净1 ，。分类的目的就 是寻找一个最优分隔超平面h ：( 国x ) + 6 = o ，将两类样本按照各自归属的类别完全分 9 太原理工大学硕士研究生学位论文 开，其中的线性判别函数由参数( 缈，6 ) 来确定，6 是阈值，国是判别函数的权向量。图 2 3 形象地表示了二维线性可分问题的情况，如图中所示实心点和空心点各自表示一类 训练样本，h 是把两类样本正确分开的一个分类面，h l 、h 2 均为平行于正确分类面的平 面，且其均过各类样本中离分类面最近的点，这样h i 、h 2 之间的距离为两类样本的最 大间隔，这里将其称作分类间隔( m a 啦1 ) 2 3 1 。 h l 图2 3 二维线性可分情况 f i g u r e 2 - 31 1 l es 印啪b l ec a s eo f t w od i m e i l s i o n s 所谓最优分类面指的是既能把两类样本无错误地分开，又能使两类样本的分类间隔 最大的平面。按照结构风险最小化准则，前者是为了保证经验风险最小，而后者中的使 分类间隔最大实际上就是使得推广性的界中的置信范围最小，这样可使真实风险最小。 综上所述，可以发现最优分类面将由离它最近的少数样本点决定，而与其他样本关系不 大，因此，这些少数的对最优分类面的确定起着关键作用的样本点被称作支持向量。 2 1 4 非线性支持向量机 假设存在样本瓴，乃) ，如，儿) h “，m ) ，其中x f r d ，苁 + 1 ，一1 ，江1 ，z ，其中d 为输入维数，为样本个数，咒表示它所对应的向量薯属于两类中的哪一类。 如果存在分类面w 石+ 6 = 0 使得 y ，( w x ，+ 6 ) 1 ， v f 1 ，2 ，)( 2 1 ) 则我们称此训练集是线性可分的。其中分类面w x + 6 = 0 的分类间隔为： 1 0 太原理工大学硕士研究生学位论文 地垆黜，箐一篇，箐 112 i 叫l 叫i 叫 ( 2 2 ) 满足不等式( 2 1 ) 且能够使分类间隔最大化的分类面就是所找的最优分类面，显然， 使分类间隔d ( w ，6 ) 最大化的问题可以转化为在约束条件( 2 1 ) 下使得m 2 2 最小化。这里 采用拉格朗日乘数法求解，问题就等价于： 哑埘= 三喜喜q 哆咒乃五。t 一窨哆 c 2 渤 s t ： 0( 2 4 ) ， 口，y ，= o ( 2 5 ) 其中f = 1 ，2 ，z 。 呸为上述问题所求解的拉格朗日乘子，其中每一个拉格朗日乘子口；都有一个对应 的训练样本。而 o 所对应的那些训练样本就被称为“支持向量。同时，设口+ 为 上述问题所得解，则得到分类函数为： 厂( x ) = s 印( w + x + 6 ) ， = s 印( 西y ，( t x ) + 6 ) f = l 其中w ：壹口? y ，6 ：y ，一杰乃口? ( v - ) ， i 口 o ) 。 ( 2 6 ) 如果训练样本线性不可分，仍按照上述方法推导则会发现优化问题将变得无解。为 此引入松弛变量茧0 ，扛1 ，得： 咒丐+ 功1 一专 1 ，2 ，砖 ( 2 7 ) 这样分类间隔d ( 功最大化问题可以转化为在约束条件( 2 7 ) 和缶o 下最小化 w 1 2 2 + c ( 孝，) 。其中c o 是控制惩罚程度的常数，c 越大表示对错误分类的惩罚越 太原理工大学硕士研究生学位论文 大。 s t ： 采用拉格朗日乘数法求解，上述问题等价于： 呼矽 ，= 丢喜骞口；口成y 一，x ，一喜 c 2 固 0 够c ( 2 9 ) ( 2 1 0 ) 其中f = 1 ，。 一般的，非线性分类问题是通过引入一个非线性变换：r dh 日来实现，将原输入 空间中的向量一通过非线性变换转化为某个高维特征空间h 中的向量矽( x ，) ，这样在这 个新空间中求取最优线性分类面既可实现正确的分类，从而将原输入空间中的非线性划 分问题转化为某个高维特征空间中的线性划分问题。如图2 4 所示为非线性变换过程。 图2 4 非线性变换示意图 f i 目l r e 2 4 i h es c h e m a 石cd i a g r a mo f n o l l l i n e a rt 1 柚s f - o i m 然而，这样的非线性变换的形式一般都非常复杂，很难实现。但是观察可以发现在 线性划分的问题中，不论是分类函数还是优化的目标函数，都只涉及到向量的点积运算， 即x 的形式，这样在高维特征空间中进行线性划分时，一定也只涉及到矽( 薯) 矽( x ) 的 形式。因此，如果可以找到一个核函数k ，满足k ( 一，石j ) = 矽( 一) 矽( _ ) ，那么就能用原 输入空间中的函数来实现高维特征空间中的点积，当然也就不必知道映射痧的具体形式 了。 1 夕 o = y ，日 引入核函数k ( 墨，x j ) 后，优化问题可以等价为： m i n 形( 口) ：丢圭圭口崩y j k ( x j 一) 一吝嗷 q 1 d a 二i = lj = 1 一 s t ： 其中i ；1 ，j 。 这样，决策函数为： ， 口；y ，= o i - 1 0 口j c f 厂( x ) = s 烈口；) ，k ( 而，x ) + 6 + ) f = l 其中6 + ：y j 一圭y ，口墨( x ，) ，w 歹l 口 o ) 。 i = l 2 1 5 支持向量机算法 ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 支持向量机算法的主要思想可以概括为：通过一个非线性变换将输入空间转换到一 个高维特征空间，然后在这个新空间中寻找最优线性分类面。通过定义适当的内积函数 来实现其中的非线性变换，即用原空间的函数实现新空间的内积。 以是否引入核函数k ( x ，x ) 和惩罚参数c 为标准，可以将支持向量机分为四大类： 线性硬间隔分类机( 无k ，无c ) ；线性软间隔分类机( 无k ，有c ) ；非线性硬间隔分类机 ( 有k ，无c ) ；非线性软间隔分类机( 有k ，有c ) 。 四大类中应用最广泛的是非线性软间隔分类机，本文也选择此类支持向量机进行研 究，其算法可简单地描述为：? ( 1 ) 已知训练集丁= ( 五，j ，) ，( 一，y ，) ) ( x 乃。， 其中z ，彳：r 一， 儿y = 一1 ，1 ) ，f = l ，； ( 2 ) 选取合适的核函数k “一) 和适当的惩罚参数c ，构造并求解最优化问题： 呼矽( 叻。主善荟哆哆咒乃足瓴，_ ) 一圭哆( 2 1 5 )。f = l ，= j。? 。、j j ， l3 太原理工大学硕士研究生学位论文 二二二二_ = = - 二= ：= 二： s t ： ， y f = o ，o 口f c ，扛1 ， f 驾l 可以求得最优解口+ = 缸i i ，口，西) 7 ； ( 3 ) 选取口中的一个分量口j ，满足o 口； c ，由此算出： ( 4 ) 构造决策函数： ， 6 + = y 厂儿口；i k ( x ，x ) f = l ( 2 1 6 ) ( 2 1