（计算机应用技术专业论文）支持向量机在模式识别领域中的应用研究.pdf

捅芰 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 方法是v a p n i k 等人根据统计学习 理论提m 的。种新型的、有效的机器学习方法，它以结构风险最小化准则和v c 维理 论为理论基础，通过适当地选择函数子集以及该子集中的判别函数，使学习机器的 实际风险达到最小，保证了通过有限训练样本得到小误差分类器。支持向量机较好 的解决了以往困扰很多学习方法的小样本、非线性、过学习、高维数、局部极小点 等实际问题，同时具有很强的推广能力。目前，统计学习理论和支持向量机理论作 为小样本学习的最佳理论，开始受到越来越广泛的重视，正在成为人工智能和机器 学习领域新的研究热点。 本论文研究的主要内容包括以下几个方面：支持向量机算法的改进、支持向量机 多类分类方法、支持向量机在模式识别中的具体应用等。论文主要研究工作包括： ( 1 ) 针对传统的增式算法在求解s v m 问题时存在的瓶颈问题，提出了一种新型 的增式支持向量机训练算法，决策函数的阈值化以及k k t 条件的引入使得保留下来 的训练样本都是最有效的，从而提高了迭代速度和分类效率。 ( 2 ) 针对传统的基于决策树方法的支持向量机多类分类方法训练样本数目过多、 时间复杂度过高的缺点，提出了一种基于聚类思想的支持向量机多类分类算法。空 间距离和聚类思想的引入，有效的提高了算法的分类效率。仿真实验表明，该方法 在保持算法良好推广性的同时降低了算法的复杂度，从而提高了分类效率和分类速 度。 ( 3 ) 系统介绍了模式识别理论，并将本研究中的改进算法应用到船舰目标识别和 人脸识别中，与传统的支持向量机分类方法相比较，改进算法在分类效率和分类速 度上表现出了明显的优越性。 关键字：支持向量机；多类分类；增式算法；聚类思想；模式识别 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 san o v e lp o w e r f u lm a c h i n el e a r n i n gm e t h o dd e v e l o p e di n t h ef r a m e w o r ko fs t a t i s t i c a ll e a r n i n gt h e o r y ( s l t ) w h i c hp r o v i d e db yv a p i n k i tu s e s s t r u c t u r er i s km i n i m i z a t i o n ( s r m ) a n dv 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 ( v c ) a st h e o r y b a s e ，m i n i m i z e dt h ep r a c t i c a lr i s ko fl e a m i n gm a c h i n eb ys e l e c tf u n c t i o ns u b s e t sa n di t s d e c i s i o nf u n c t i o nc o r r e c t l y , i tm a k es u r et og a i n e dm i n i m u me r r o rc l a s s i f i e rb yl i m i t e d s a m p l e s s v ms o l v e sp r a c t i c a lp r o b l e m ss u c h a ss m a l ls a m p l e s ，n o n l i n e a r i t y , o v e r l e a r n i n g ，h i g hd i m e n s i o na n dl o c a lm i n i m a ，w h i c he x i ti nm o s to fl e a r n i n gm e t h o d s ，a tt h e s a m et i m e ，i th a sb e t t e rg e n e r a l i z a t i o nc a p a b i l i t y c u r r e n t l y , b e i n gt h eo p t i m a ll e a r n i n g t h e o r yf o rs m a l ls a m p l e s s l ta n ds v mi sa t t r a c t i n gm o r ea n dm o r er e s e a r c h e ra n d b e c o m i n gan e w a c t i v ea r e ai nt h ef i e l do f a r t i f i c i a li n t e l l i g e n ta n dm a c h i n el e a r n i n g t h em a i nr e s e a r c ho ft h i sp a p e rc a nb ec l a s s e da sf o l l o w s ：i m p r o v e da l g o r i t h mo f s u p p o r tv e c t o rm a c h i n e 、m u l t i c l a s s i f i c a t i o na l g o r i t h mo fs v m 、s t u d yo fs u p p o r t v e c t o r m a c h i n ea l g o r i t h mf o rp a t t e r nr e c o g n i t i o na n ds oo n t h em a i nr e s u l t so ft h ep a p e ra r ea s f o l l o w s ： ( 1 ) f o rt h eb o t t l e n e c kp r o b l e mo fo r i g i n a li n c r e m e n t a la l g o r i t h mo fs u p p o r tv e c t o r m a c h i n e ，t h i sp a p e rp r e s e n t san e wi n c r e m e n t a la l g o r i t h mo fs u p p o r tv e c t o rm a c h i n e ， w h i c hm a k e st h e r e s e r v e d s a m p l e s a r e a l lt h em o s te f f e c t i v e b y a d d s k k t ( k a r u s h k u h n t u c k e ) c o n d i t i o na st h er e s t r i c tc o n d i t i o na n dt h r e s h o l dt h ed e c i s i o n f u n c t i o n ，i m p r o v et h eo p e r a t i o ns p e e da n dc l a s s i f i c a t i o ne f f i c i e n c y ( 2 ) f o rt h eo n g i n a lm u l t i c l a s s i f i c a t i o ns v m w h i c hi sb a s e do ns v m - d e c i s i o nb i n a r y t r e eh a st o om a n yt r a i n i n gs a m p l e sa n dh i g ht i m ee x p e n d e d ，t h ep a p e rp r e s e n t s a m u l t i c l a s s i f i c a t i o ns v mw h i c hb a s e so nc l u s t e r i n gi d e a i ti m p r o v e st h eo p e r a t i o ns p e e d b yi m p o r ts p a t i a ld i s t a n c ea n dc l u s t e r i n gi d e a 1 1 1 ee x p e r i m e n tr e s u l ti n d i c a t e dt h a tt h e n e wa l g o r i t h mn o to n l yc a ni n d u c et h e t i m ee x p e n d e d ，b u ta l s oc a nk e e pt h e g e n e r a l i z a t i o nc a p a b i l i t y , i m p r o v et h eo p e r a t i o ns p e e da n d c l a s s i f i c a t i o ne f f i c i e n c y ( 3 ) i n t r o d u c et h ep a t t e r nr e c o g n i t i o nt h e o r ys y s t e m a t i c a l l y , a n da p p l yt h ei m p r o v e d a l g o r i t h m st o t h es h i pr e c o g n i t i o na n df a c er e c o g n i t i o n ，c o m p a r ew i t ht h eo r i g i n a l m u l t i c l a s s i f i c a t i o ns v ma l g o r i t h m s ，t h ei m p r o v e da l g o r i t h mh a so b v i o u sa d v a n t a g e so n t h eo p e r a t i o ns p e e da n dc l a s s i f i c a t i o ne f f i c i e n c 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 ；m u l t i - c l a s s i f i c a t i o n ；i n c r e m e n t a la l g o r i t h m ； c l u s t e r i n gi d e a ；p a t t e r nr e c o g n i t i o n 学位论文独创性说明、学位论文知识产权权属说明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：村芴、 r 期：加岔年5 月1 1 1 7 1 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在 年解密后适用于本声明。 不保密函 ( 请在以上方框内打“4 一) 论文作者签名： 斟篙。 日期：) 必年易月以日 日期：) 口时年5 月1 - e t 第一章引言 第一章引言 1 1 研究的背景及意义 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 方法是在统计学习理论( 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 v m 在使用结构风险最小化 原则替代经验风险最小化原则的基础上，又结合了统计学习、机器学习和神经网络 等方面的技术，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有 的优势。它一方面可以克服神经网络等方法所固有的过学习和欠学习问题，另一方 面又有很强的非线性分类能力，通过引入核函数，将输入空问的样本映射到高维特 征空间，输入空间的线性不可分问题就转化为特征空间的线性可分问题。支持向量 机被看作是对传统分类器的一个好的发展，并被证明可在保证最小化结构风险的同 时，有效地提高算法的推广能力。 随着计算机技术的蓬勃发展以及人们在各个领域对模式识别技术的需求与应 用，计算机模式识别技术也有了很大的发展。模式识别就是设计一个能够对未知数 据进行自动分类的方法，常用模式识别方法有统计识别方法、句法结构识别方法、 模糊理论识别方法、神经网络识别方法、模板匹配识别方法和支持向量机的识别方 法等。其中，基于支持向量机的模式识别方法是目前最为有效的模式识别方法之一。 1 2 支持向量机理论的发展 v v a p n i k 等人早在2 0 世纪6 0 年代就开始研究小样本情况下的机器学习问 题，当时这方面的研究尚不十分完善，且数学上比较艰涩，大多数人难以理解和接 受，直到9 0 年代以前还没能够提出将其理论付诸实现的方法，加之当时正处在其 他学习方法飞速发展的时期，因此这方面的研究一直没有得到足够的重视。直到9 0 年代中期，小样本情况下的机器学习理论研究逐渐成熟起来，形成了较完善的理论 体系统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y , s l t ) z 3 ，而同时，神经网络等 新兴的机器学习方法的研究则遇到了许多困难，在这种情况下，试图从更本质上研 究机器学习问题的统计学习理论逐步得到重视。 统计学习理论是建立在坚实的理论基础之上的，为解决小样本学习问题提供了 统一的框架。统计学习理论的核心是v c 维理论与结构风险最小化理论，它用v c 维 来描述学习机器的复杂度，并以此为出发点导出了学习机器推广能力的界的理论。 该理论致力于寻找在小样本情况下学习问题的最优解，而不需要利用样本数趋于无 穷大的渐进性条件，这使得统计学习理论在小样本情况下同样能得到具有推广价值 的知识。 青岛大学硕十学位论文 1 9 9 2 年至1 9 9 5 年，在统计学习理论的基础上发展m 了一种新型的学习机器一 一支持向量机( s u p p o r tv e c t o rm a c h i n e 简称s v m ) 。支持向量机是建立在统计学习 理论的v c 维理论和结构风险最小原理基础上的，根据有限的样本信息在模犁的复杂 性和学习能力之间寻求最佳折衷，以期获得最好的推广能力。支持向量机被看作足 对传统分类器的一个好的发展，在解决小样本、非线性和高维的机器学习问题中表 现出了许多特有的优势。 s v m 方法口1 是由v a p n i k 及其合作者b o s e r 、g u y o n 、c o r t e s 及s c h o l k o p f 在 a t & tb e l l 实验室共同创造与发展起来的一种新方法。近年来，许多关于s v m 方 法的研究，包括算法本身的改进和算法的实际应用，都陆续被提了出来，如s c h o l k o p h 等人提出了v s v m 方法、s u y k e n s 等人提出了最小二乘支持向量机( l s s v m ) 、 z h a n g 提出的类中心支持向量机( c s v m ) 方法、l i n 等提出了模糊支持向量机方 法( f u z z y s v m ) 等h 1 。其中，在理论上主要以v a p n i k 及其研究小组做了大量开创 性及奠基性的工作。 随着支持向量机的不断发展，人们对支持向量机的研究也越来越细化，其主要 研究方向大致可分为：求解支持向量机问题，支持向量机多类分类问题，参数的选 择和优化问题等。 求解一个s v m 问题最终都转化为解一个具有线性约束的凸规划问题或其对偶问 题的二次规划问题( q u a d r a t i cp r o g r a m m i n g ，q p ) 。传统的方法是利用标准二次型 优化技术解决对偶问题，这就导致算法的训练速度很慢，一方面是由于s v m 需要计 算和存储核函数矩阵，当样本规模较大时必然导致内存需求增加；另一方面，s v m 在二次寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法占用了大部分的 算法时间，这就使得存储空间和和计算时间成了求解二次规划问题的瓶颈。常用的 解决方法是将一个大的二次规划问题转化为若干个小的二次规划问题以提高分类效 率，如块算法、分解算法、s m o 算法、增式算法等等。 支持向量机分类理论是针对两类分类问题提出的，然而，现实世界的分类问题， 如船舰识别、字体识别、人脸识别等，都属于多类分类的范畴。如何将二类分类方 法扩展到多类分类情况是支持向量机方法研究的重要内容之一。目前，用s v m 解决 多类分类问题方法主要是通过构造或组合多个两类分类器来实现多类问题的分类。 子分类器的构造和组合将两类分类扩展到多类问题，将多类分类问题逐步转化为两 类分类问题。常用的算法有“o n e a g a i n s t - o n e 方法、“o n e a g a i n s t r e s t ”方法、 “基于决策树的方法等。支持向量机多类分类方法的引入拓展了支持向量机的应 用范围，也加快了支持向量机方法的改进和创新。同时，支持向量机的核函数的选 择以及核参数的选择也是一个重要的研究方向。 2 第一章引言 1 3 支持向量机在各个领域的具体应用 近年来，支持向量机理论同趋成熟，s v m 算法在模式识别、回归估计、概率密 度函数估计等方面都得到了广泛的应用。 在模式识别方面，p o n t i l 等人将s v m 应用于三维物体的识别，f u k u d a 及 z h a o q u n 等人利用s v m 进行s a r 自动目标的识别，k i m 等对纹理图像进行了有监 督分割，s v m 在医学图像分割1 中也有成功的应用，如i s s a m 等人利用s v m 分类 器从超声图像中识别病变组织，m a n g a s a r i a n 等利用s v m 进行了乳腺癌的识别与诊 断。 支持向量机在工业领域的应用研究正逐渐受到研究者的重视。一些文章将支持 向量机用于系统辨识，进行线性和非线性动态系统的辨识。d ek r u i f 将支持向量机 用于前馈学习控制，s u y k e n s 将最小二乘支持向量机应用于非线性系统的最优控制。 支持向量机用于工业故障诊断h 旧1 。 支持向量机还被应用到其它一些领域。支持向量机在时间序列的预测和混沌系 统的动态重构中显示出了强大的优势。在信号处理方面，c h e n 对多路径通道d s - c d m a 信号传输构造了一个基于支持向量机的自适应多用户检测器。c a o 将自适应参数s v m 用于对经济时间序列的预测h 1 5 1 。总之，随着s v m 的理论的逐步完善，s 在各个 领域的应用越来越广泛，支持向量机算法的研究也越来越受到重视。 1 4 本文的创新工作和内容安排 文章以统计学理论和支持向量机理论为基础，以支持向量机在多类分类中的应 用为重点，深入阐述了当前支持向量机理论研究的几个热点，并对相关算法进行改 进，提出了一种新型的增式支持向量机训练算法和一种基于聚类思想的支持向量机 多类分类算法。 ( 1 ) 针对传统s v m 算法在求解二次规划问题中存在的瓶颈问题，提出一种新型 的增式支持向量机训练算法，该算法不是简单的保留了上一步训练的支持向量，而 是通过增加k k t 限制条件并对决策函数的输出阈值化的方法，舍弃了与训练分类器 无关的样本，使得保留下来的样本都是最有效、最可能成为支持向量的样本，从而 大大减少了训练样本的数目。实验结果表明，与传统的增式算法相比，改进算法在 保持传统s v m 性能的同时，在迭代速度和分类效率上均表现比明显的优越性。 ( 2 ) 基于聚类思想的支持向量机多类分类算法，通过计算各样本间的空间距离 和，选择最优的分类顺序，让最容易分割的样本最先分割出来，保证了算法良好的 推广性能；同时，聚类思想的引入，使得只有最有可能成为支持向量的样本才能参 与分类器的训练，提高了算法的分类速度和分类效率。 3 青岛大学硕士学位论文 全文的组织结构如下： 第一章为引言，简单介绍了支持向量机的发展历程以及当前支持向量机方法在 各个领域中的具体应用，同时概述了本文的主要研究工作。 第二章介绍了统计学理论、支持向量机的基本原理和支持向量机的几个研究热 点：支持向量机多类分类问题、求解二次规划问题、核函数的选择以及核参数的确 定问题等。同时分析了现有的一些支持向量机的改进算法，为以后各章奠定理论基 础。 第三章针对传统的优化方法在求解s v m 时存在的瓶颈问题，提出了一种新型 的增式支持向量机训练算法，并通过具体的仿真实验证明了该算法的有效性。 第四章针对传统的基于决策的支持向量机多类分类方法存在的不足，提出了一 种基于聚类思想的决策树方法。空间距离的计算以及聚类思想的引入在保证了算法 良好的推广性的同时，降低算法时间复杂度和空间复杂度。 第五章将三、四章改进的算法用于具体的模式识别领域。介绍了模式识别理论 以及常用的特征提取方法，并将改进的算法应用于船舰目标识别、人脸识别中。仿 真结果表明，改进算法在分类效率和运行时间上明显优于传统的支持向量机算法。 第六章是总结与展望，概括了全文的主要研究内容和创新点，并对未来的研究 提出了一些设想，为以后的研究提供参考。 4 第一二章支持向量机的基本原理 第二章支持向量机的基本原理 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是f l 了v a p n i k 及其合作者共同创造与 发展起来的一种新的机器学习方法，其核心内容在1 9 9 2 乍f 至1 9 9 5 年间提出的。目前， 支持向量机已经成为机器学习领域的标准工具之一并仍在不断的发展之中。支持向 量机集成了机器学习领域的若干标准，如最人间隔超平面，m e r c e r 核，凸二次规划， 松弛变量等技术等。支持向量机在语音识别、字符识别等领域均获得了目前为止最 好的性能。在美国的科学杂志上，支持向量机被认为“是机器学习领域中的一个令 人瞩目的发展方向”u 制。 本章系统的阐述了统计学习理论、支持向量机理论以及支持向量机的主要研 究热点，包括求解支持向量机问题、多类分类问题、参数优化问题、核函数的选 择问题等，为后续章节对支持向量机的深入研究奠定了理论基础。 2 1 统计学习理论 统计学习理论建立在一套较为坚实的理论基础之上，为解决有限样本的学习 问题提供了一个统一的框架。它能将许多现有的方法纳入其中，有望帮助解决许 多原来难以解决的问题，比如神经网络的结构选择问题、局部最小点问题等。 2 1 1 机器学习问题的描述 机器学习问题n 1 可以看作是通过某种训练方法，对某一系统的输入与输出之间 的依赖关系进行估计，并且期望这一估计可以对任意给定输入尽量准确地进行输出 预测。一般地，机器学习问题可以表示为：假设变量y 与x 之间存在一定的未知依 赖关系，即遵循某一未知的联合概率f ( x ，y ) ( x 和y 之间的确定性关系可以看作是其 特例) ，机器学习问题就是根据n 个独立同分布观测样本 ( x i ，y 1 ) ，( x 2 ，y 2 ) ，( x 。，y 。) ，在一组函数( f ( x ，缈) ) 中求一个最优的函数f ( x ，) 对依赖关系进行估计，使得期望风险最小。 r ( c o ) = i ，( y ，f ( x ，c o ) ) d f ( x ，y ) 2 - ( 1 ) 其中 f ( x ，c o ) 称作预测函数集，c o 为函数的广义参数， f ( x ，c o ) 可以表示任何函 数集；l ( y ，f ( x ，c o ) ) 为由于用f ( x ，国) 对y 进行预测而造成的损失，不同类型的学习 问题有不同形式的损失函数。 在上面问题的表述中，学习的目标在于使期望风险最小化，但是，由于可以利 用的信息只有样本最初的观测样本( x 。，y 1 ) ，( x ：，y 2 ) ，( x 。，y 。) ，因此，期望风险 2 - ( 1 ) 是无法计算的。传统的学习方法是采用了所谓经验风险最小化( e r m ) 准则， 气 青岛人学硕+ 学位论文 即用样本定义经验风险 ( 咖丢喜地，胞，硼 2 - ( 2 ) 来逼近2 ( 1 ) 定义的期望风险，用对参数c o 求经验风险足。( 缈) 的最小值代替求期望风 险r ( c o ) 的最小化，这就是所谓的经验风险最小化原则。 事实上，用经验风险最小化准则代替期望风险最小化并没有经过充分的理论论 证，只是直观上合理的想当然做法，但这种思想却在多年的机器学习方法研究中占 据了主要地位。而实际上，即使可以假定当n 趋向于无穷大时，公式2 ( 2 ) 趋近于公 式2 ( 1 ) ，但在很多实际的问题中，样本数目也离无穷大相去甚远，那么在有限样本 情况下，采用最小化经验风险准则，得到的结果能使真实风险也较小吗? 要得到这 个答案，需要了解统计学习理论对采用经验风险最小化准则解决期望风险最小化问 题的前提，如果这些前提不成立时，需要找到更合理的准则。 在早期的机器学习理论的研究中，人们总是把注意力集中在如何使冠。更小， 但很快便发现，一味追求训练误差小并不是总能达到好的预测效果。在某些情况下， 当训练误差过小反而会导致推广能力的下降，这就是几乎所有神经网络研究者都曾 到的过学习( o v e r f i t t i n g ) i h - 题，o p i ) l l 练误差过小反而导致推广能力下降、真实风险的 增加。从理论上看，模式识别中也存在同样的问题，但因为通常使用的分类器模型 ( 比如线性分类器) 都是相对比较简单的，因此过学习问题并不像神经网络中那样 突出。支持向量机是在统计学习理论的基础上发展起来的，它能够有效地解决小样 本问题，同时避免过学习问题的产生，它的出现推动了机器学习理论和技术的发展。 2 1 2 统计学理论的发展与支持向量机 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 是一种专门研究小样本情况 下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系，在 这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信 息的条件下得到最优结果。v v a p n i k 等人从六、七十年代开始致力于此方面研究， 到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理 论上缺乏实质性的进展，统计学习理论开始受到越来越广泛地重视。同时，在这一 理论基础上发展了一种新的通用学习方法一支持向量机。目前，支持向量机已初 步表现出很多优于各种传统方法的性能。 概括说来，统计学习理论就是研究小样本统计估计和预测的理论，主要内容包 括以下四个方面： 6 第二二章支持向量机的基本原理 ( 1 ) 经验风险最小化准则下统计学习一致性的条件； ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论； ( 3 ) 在这些界的基础上建立的小样本归纳推理准则； ( 4 ) 实现新的准则的实际方法( 算法) 。 其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是v c 维。统 计学习理论被认为是只前针对小样本统计估计和预测学习的最佳理论，它从理论上 较系统地研究了经验风险最小化原则成立的条件，有限样本下经验风险与期望风险 的关系及如何利用这些理论找到新的学习原则和方法等问题。 2 1 3 阳维理论 ， 模式识别方法中v c 维的直观定义是：对一个指示函数集，如果存在h 个样本能 够被函数集中的函数按所有可能的2 6 种形式分开，则称函数集能够把h 个样本打散； 函数集的l c 维就是它能打散的最大样本数目h 。若对任意数目的样本都有函数能将 它们打散，则函数集的v c 维是无穷大。 比维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。遗 憾的是，目前尚没有通用的关于任意函数集v c 维计算的理论，只确定了一些特殊 的函数集的v c 维。比如在n 维实数空间中线性分类器和线性实函数的v c 维是 n - t - 1 ，对于一些比较复杂的学习机器( 如神经网络) ，其v c 维除了与函数集( 神经网 结构) 有关外，还受学习算法等的影响，其确定更加困难。但是，在实际应用统计 学习理论时，可以通过变通的办法巧妙地避开直接求v c 维的问题。 2 1 4 推广性的界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之 间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有 函数( 包括使经验风险最小的函数) ，经验风险足。( 国) 和实际风险r ( 缈) 之间以概率 1 一，7 满足如下关系： 荆c缈，+、(h(1n(2nh)+1)-in(r4) 2 c 3 ， 其中h 是函数集的v c 维，n 是样本数。 这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风 险( 训练误差) ，另一部分称作置信范围，它和学习机器的v c 维及训练样本数有关， 可以简单地表示为： 7 青岛人学硕士学位论文 r ( 缈) s 冀( m ) + o ( h n )2 。( 4 ) 它表明，在有限训练样本下，学习机器的v c 维越高( 复杂性越高) 则置信范围越大， 导致真实风险与经验风险之间可能的差别越大，这就是为什么会出现过学习现象的 原因。机器学习过程不但要使经验嫩险最小，还要使v c 维尽量小以缩小置信范围， 才能取得较小的实际风险，即对未来样本有较好的推广性，这一理论可以由图2 1 说 明。 误差 图2 1 置信范围、经验风险与实际风险之间的关系 由图2 1 可以看出，当样本数目n 固定，算法的v c 维增大时，它对给定的训 练样本集合有更强的分类或拟合能力，导致了更小的经验风险如。( 计，甚至使它为 零。但是，v c 维增大时，o ( h n ) 也随之增大，即放大了置信范围，从而减小了算 法具有小的实际风险尺( 讷的可能性。反之，若v c 维缩小，那么它对给定的训练样 本集合的分类或拟合能力减弱，导致了大的经验风险，此时，虽然置信区间o ( h n ) 缩小了，但仍不能保证获得小的实际风险。可以看出以固定时如。( 计与o ( h n ) 是一 对矛盾体，它们不可能同时都减小，但确实存在某个h 值使实际风险上界达到最小 值。 2 1 5 结构风险最小化原则 经验风险最小化原则是目前绝大多数模式识别方法的基础，其定义为训练集上 的平均错误率，用于对整个样本集的期望风险进行估计，它建立在样本数目足够多 的前提下，致使各种方法只有在样本数趋向无穷大时，其性能才有理论上的保证。 而在现实世界的应用中，这一前提并不总能被满足，这时大多数此类方法都难以取 得理想的结果。 8 第二章支持向量机的基本原理 由2 1 4 节中的推广性的界可以看出，影响期望风险上界的因子有两个方面： 首先是训练集的规模n ，其次是v c 维h 。可见，在保证分类精度( 经验风险) 的同 时，降低学习机器的v c 维，可以使学习机器在整个样本集上的期望风险得到控制， 这就是结构风险最小化( s t r u c t u r er i s km i n i m i z a t i o n ，简称s r m ) 的由来。 由v c 维的讨论可以看到，经验j x l 险和期望风险依赖于学习机器函数族的选择。 把函数集s = f ( x ，c o ) ，国q 分解为一个函数子集序列 一c 是c c 瓯c c s 2 - ( 5 ) 使各个子集能够按照置信范围的大小排序，即 j l z l 如噍 2 - ( 6 ) 所谓结构风险最小化，便是构造一组嵌套的函数子集，使得其v c 维由内向外 依次递增，然后在其上寻找经验风险和置信范围之和最小的子集，从而使得实际风 险的上界最小化，如图2 2 所示 ，( 鼻) 胎 函鞋子集：1 1 ，- 2 ，摹3 v c 罐：h 2 2 结构风险最小化示意图 基于结构风险最小化准则的统计学习理论是一种专门研究小样本的统计理论， 它为研究有限样本情况下的统计模式识别，并为更广泛的机器学习问题建立了一个 较好的理论框架，同时也发展出了一种新的模式识别方法支持向量机，从而能够 较好地解决小样本的学习问题。 2 2 支持向量机理论 s v m 方法是由v a p n i k 及其合作者b o s e r 、g u y o n 、c o r t e s 及s c h o l k o p f 在 a t & tb e l l 实验室共同创造与发展起来的一种新的学习方法。近年来，许多关于s v m 方法的研究，包括算法本身的改进和算法的实际应用，都陆续被提了出来，其中在 理论上主要以v a p n i k 及其研究小组做了大量开创性及奠基性的工作。目前s v m 正处 9 青岛人学硕士学位论文 于不断发展阶段，现在已经成为机器学习领域的标准工具之一。 支持向量机是个三层网络结构，是一个多输入、单输出的学习机器，其体系结 构如图2 3 所示 五而而 2 3 支持向量机的体系结构 其中，位于体系结构最底层的五，x 2 ，x 3 ，以是输入样本， k ( x ；，x ) ( i = l ，2 ，1 3 ) 是样本x 与支持向量在特定空间的内积，( i = l ，2 ，n ) 是拉格朗 r 乘子，厂( x ) 是决策函数的输出。图2 3 清晰的表示出支持向量机的逻辑概念框架， 首先确定训练样本作为支持向量机的输入，然后选择适当的核函数，将样本从输入 空间映射到高维的特征空间，根据优化问题求解出来的支持向量最终得到相应的决 策函数。它与传统的神经网络的最大区别在于：神经网络结构的确定大多是凭经验 选取的，有一定的盲目性，无法确定泛化的置信空间界限，所以无法保证网络的推 广能力，容易出现过学习的现象。而支持向量机网络通过结构化风险最小化归纳原 理控制学习单元的v c 维的上界，限制了学习单元的能力，在一定程度上避免了过学 习现象。 支持向量机是建立在统计学习理论的v c 维理论和结构风险最小化原理基础上 的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获 得最好的推广能力。支持向量机被看作是对传统分类器的一个好的发展，在解决 小样本、非线性和高维的机器学习问题中表现出了许多特有的优势。概括的说， 支持向量机是以寻找最优分类面为目标、以二次规划为手段、以非线性映射为理 论基础的统计学习方法。下面将分别从这几个方面对支持向量机理论进行系统的 阐述。 1 0 第二章支持向量机的基本原理 2 2 1 最优分类面 支持向量机是从线性可分情况下的最优分类面发展而来的，其基本思想可用图 2 4 表示，对应于一维空间中的点，二维空间中的直线，三维空| 日j 中的平面，以及 高维空问中的超平面。图中圆形和三角形的标志分别代表两类样本，中间的实线 为两类样本之间的分类超平面，两条虚线分别表示过各类中距离分类面最近的样 本且平行于分类面的超平面，它们之间的距离叫做分类间隔( m a r g i n ) 。 、 2 分类间隔p 2 i w 1 1 2 图2 4 最优分类面不意图 最优分类面在把两类j 下确的分开的同时保证分类间隔最大，根据结构风险最小化 原则，前者是保证经验风险最小，而后者使分类问隔最大，导致昭维最小，实际上 就是使推广性的界中的置信范围最小，从而达到使真实风险最小。后者保证v c 维最 小，从而达到使真实风险最小。 假定给出一个样本集( 葺，咒) ，i = 1 ，n ，x r d , y + 1 ，- 1 ) 满足 乃【( 蕾) + 6 一l o ，i = 1 9 e 9 以 2 一( 7 ) 其中+ 6 = o 是分类面方程，此时分类间隔为p 2 夕仙l ：，最终目标是求一个分 类面，使得能够将两类样本正确分类的同时保证分类间隔最大，这里是使1 1 w | | 2 最小。 如图2 4 所示，中间的实线为最优分类面，两侧虚线上的样本即为支持向量。因而， 在线性可分的情况下，得到的s v m 的目标函数是： 中( w ) = 三1 2 2 - ( 8 ) s d y i ( w x l ) + 6 卜l 0 ，i = l ，l 2 ( 9 ) 为求得公式2 - ( 8 ) 的最小值，定义如下l a g r a n g e 函数： 青岛人学硕士学位论文 她如) = 剁w n 喜哆m m ) + 6 】州 2 - ( 1 0 ) 其中0 为各样本对应的l a g r a n g e 乘子。为了求解表达式2 - ( 1 0 ) 的最小值，可以 令该泛函对愀b 求偏导，并令其等于零，我们得到表达式2 - ( 1 0 ) 的相应的对偶函数： q ( c t ) = t t t i + i l c t i a y i y ( x i _ ) 2 一( 11 ) “善y 舻o2 - ( 1 2 ) o ， i = l ，n 在表达式2 - ( 1 2 ) 的约束下，求得表达式2 - ( 11 ) 的唯一解嘶，其中，不为零l a g r a n g e 乘子所对应的样本就是支持向量。 若口? 为最优解，相应的求出最优分类面权系数向量缈。和分类器的阈值b ： 彩= z 咒而 一(132) 2z q iy l x t 。 ) 6 = 寺p x + ( 1 ) + 彩，( 一1 ) 2 - ( 1 4 ) 其中x ( 1 ) 、x + ( - 1 ) 分别表示两类中任意一个支持向量。 由上面推导得出的参数愀b 可以得到分类器的决策函数： f ( x ) = s g n ( w x ) + 6 = s g n l c t i y i ( x r x ) + bl 2 - ( 1 5 ) 而e “ 上述方法可以确保在线性可分的情况下将全部样本正确分类，如果对于线性不 可分或者事先不知道是否线性可分的情况，可以通过引入非负松弛变量磊 i = 1 ，2 ，t 来允许错分样本的存在。相应地，表达式2 ( 7 ) 、2 - ( 8 ) 、2 一( 9 ) 分别变为： 乃【( 五) + b - i + 参o ，i = l ，n2 - ( 1 6 ) 圳= 洲1 2 + c ( 喜缶) 2 羽7 ， s t 【( w r 墨) + 6 卜1 + 缶o ，i = l ，n 2 - ( 1 8 ) 其中，c o 是一个自定义的惩罚因子，它表示对错分样本惩罚的程度，用来控制样 本偏差与机器推广能力之间的折衷。c 越大，对错分样本的惩罚就越大，对错分样 本的约束程度就越大。 容许错分的分类面又称为软问隔分类面n 8 1 ，求解表达式2 - ( 1 7 ) 的优化问题和求 1 2 第二章支持向量机的基本原理 解表达式2 一( 8 ) 的优化问题类似，都是通过引入相应的拉格朗同函数及其对偶问题并 对其求解，最终得到最优分类判别函数。 2 2 2 标准支持向量机 支持向量机是从线性可分情况下的最优分类面发展而来的，前面介绍的是在线 性分类情况下如何求解最优分类超平面。而在实际问题中，分类问题是常常是非线 性问题，理想的最优分类面应该是非线性的。支持向量机解决非线性问题的思想是： 首先选择适当的核函数n 引，将低维空间的训练样本通过非线性映射映射到高维特征 空间中，然后用前面介绍的方法在高维空间中求解最优分类超平面，高维空问中得 到的线性分类面就对应着低维空间的非线性分类面。如图2 5 所示，支持向量机处 理非线性分类问题时，只是比线性分类问题多了个非线性映射过程，设定该非线性 映射为： x _ 伊( x )2 - ( 1 9 ) 则，表达式2 - ( 11 ) 的优化问题就转化为： q ( 口) = q + 去哆咒乃缈( 蕾) 妒( t ) 2 一( 2 0 ) i = l 二f j = l 核函数映射 输入空间- 特征空间 图2 5 输入空间和特征空间所对应的分类面示意图 非线性映射的引入很好的解决了非线性分类问题，同时也增加了优化求解的困 难，使2 一( 2 0 ) 的计算非常不容易实现，但是注意到，上面的对偶问题中只涉及到高 维空间中的内积运算，即缈( 玉) 缈( 石，) ，而没有单独的映射缈( 蕾) 。因此，可以考虑是 否可以找到输入空间的一个函数k 来替代特征空间的内积运算，即 k ( 五，石，) = 伊( 薯) 妒( x ，) 2 一( 2 1 ) 这样就省去了高维空间中复杂的内积计算，我们甚至不需要知道映射变换缈( ) 的具 1 3 青岛人学硕十学位论文 体表示形式。根据泛函的有关理论，只要g c x , ，工川荫足下列定理的m e r c e r 条件，它就 对应某一变换空间的内积。 定理2 1 ( m e r c e r 条件) 对于任意的对称函数k ( x ，x ) ，它是某个特征空间中的 内积运算的充分必要条件是，对于任意的妒( x ) 0 且修2 ( x ) d x 0 2 - ( 2 2 ) 这样，在高维空间中求解最优分类面时，可以通过采用适当的核函数k ( x ；，x j ) 将 高维空将的内积运算转化为低维空间的函数运算，就可以在不影响计算复杂度的情 况下实现非线性分类问题。表达式2 - ( 2 0 ) 也相应的转化为： q ( 口) = q + 去嘶吩咒乃露( 五，一) 2 - ( 2 3