（应用数学专业论文）关于支持向量机方法的探讨.pdf

摘要 统计学习理论研究的是与利用经验数据进行机器学习相关的一般理论，由于对样本 数目有限的情况进行了比较系统的考虑，其实用性比传统统计学理论更好。在此基础上 发展起来的支持向量机方法因为其在样本有限情况下的推广能力较好而受到广泛重视， 它不同于其余机器学习算法( 它们只利用经验风险最小化原则) ，训练学习机时使用结 构风险最小化原则，并采用v c 维理论对结构风险进行衡量。支持向量机是机器学习领 域内若干标准技术当中的集大成者，它不但集成了最大间隔超平面、凸二次规划技术， 还集成了m e r c e r 核、松弛变量以及稀疏解等多项技术，在众多富有挑战性的应用( 模 式识别、回归估计等) 中，获得了现在为止最好的性能。 本文一开始对机器学习与统计学习理论进行了介绍，在此基础上介绍了支持向量机 方法的特点，又对它在分类问题中的应用进行了讨论。本文主要涉及两方面内容：第一， 在前人对支持向量机的研究成果基础上对其光滑函数进行了研究，并推导出了一个八阶 光滑函数。通过对它的光滑性能和逼近精度进行讨论，我们得出了下面的结论：同已有 的一到七阶的光滑函数相比，本文提出的新光滑函数的逼近性能更高。第二，文章在前 人的成果基础上讨论了基于支持向量机的概率密度估计问题，进一步的研究了基于多核 结构可调支持向量机的概率密度估计问题，将多种有关支持向量机的技术和用于解决不 适定性问题的p 方法融合起来对概率密度估计问题进行解决。这一方法综合考虑了多种 实际因素，因而其稳健性更强、适用范围更广。 关键词 统计学习理论，多核结构可调支持向量机，密度估计，光滑函数 a b s t r a c t 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 ) i sag e n e r a lt h e o r yr e l a t e dt ot h em a c h i n el e a r n i n gu s i n g e m p i r i c a ld a t a i ts y s t e m a t i c a l l yc o n s i d e r st h es i t u a t i o nt h a tt h en u m b e ro fs a m p l e si sl i m i t e d ， s oi t sp r a c t i c a l i t yi sb e t t e rt h a nt h et r a d i t i o n a ls t a t i s t i c a lt h e o r y t h es u p p o r tv e c t o rm a c h i n e ( s v m ) ，w h i c hi sd e v e l o p e do nt h eb a s i co fs l t , i sw i d e l yr e c o g n i z e db e c a u s eo fi t sb e t t e r p r o m o t i o na b i l i t yi n t h ec a s eo fli m i t e ds a m p l e s i ti sd i f f e r e n tf r o mt h eo t h e rm a c h i n e l e a r n i n ga l g o r i t h m s ( t h e yo n l yu s ee m p i r i c a lr i s km i n i m i z a t i o np r i n c i p l e ) i t u s e st h e s t r u c t u r a lr i s km i n i m i z a t i o n p r i n c i p l e s t ot r a i nt h e l e a r n i n gm a c h i n e ，a n da p p l i e s v c d i m e n s i o n a lt h e o r i e st om e a s u r et h es t r u c t u r er i s k s v mi sam a s t e ro fan u m b e ro f s t a n d a r dt e c h n i q u e sw i t h i nt h ef i e l do fm a c h i n el e a r n i n g 。i tn o to n l yi n t e g r a t e st h el a r g e s t i n t e r v a lh y p e r - p l a n ea n dc o n v e xq u a d r a t i cp r o g r a m m i n gt e c h n i q u e s ，b u ta l s oi n t e g r a t e s m e r c e rn u c l e a r , s l a c kv a r i a b l e s , s p a r s es o l u t i o nt e c h n i q u e sa n ds oo i l a n di th a st h eb e s t p e r f o r m a n c ei nm a n yc h a l l e n g i n ga p p l i c a t i o n s ( s u c ha sp a t t e r nr e c o g n i t i o n ，r e g r e s s i o n e s t i m a t i o n ，e t c ) t h i sp a p e ri n t r o d u c e s ，f i r s t l y , t h em a c h i n el e a r n i n ga n ds t a t i s t i c a ll e a r n i n gt h e o r y , a n d d e s c r i b e st h ec h a r a c t e r i s t i c so fs u p p o r tv e c t o rm a c h i n e so nt h i sb a s i s ，t h i st h e s i si n v o l v e st w o a s p e c t sm a i n l y ：f i r s t l y , t h ee x p r e s s i o no fn e w s m o o t hf u n c t i o n so fs v ma n di t sp e r f o r m a n c e a n a l y s i s t h er e s u l t ss h o w st h a t ：t h ea p p r o x i m a t i o np e r f o r m a n c eo fn e ws m o o t hf u n c t i o ni s b e t t e rt h a nt h a to ft h el o w e ro r d e rs m o o t hf u n c t i o n ，t h u s ，i tp r e p a r e san e ws m o o t hf u n c t i o n f o r t h ef u r t h e rs t u d yo ns v m s e c o n d l y , t h ep r o b a b i l i t yd e n s i t ye s t i m a t i o nb a s e do n m u l t i c o r ea n ds t r u c t u r ea d j u s t a b l es v m t h i sa r t i c l ec o m b i n e st h epm e t h o d ( w h i c hi s s p e c i f i c a l l ya d d r e s st h en o tf i x e dp r o b l e m ) a n dm u l t i - c o r es t r u c t u r ea d j u s t a b l es v m t os o l v e t h ep r o b l e mo fp r o b a b i l i t yd e n s i t ye s t i m a t i o n t h em e t h o dw ep r o p o s ec a nb eu s e dw i d e l y b e c a u s ei th a sm o r er o b u s tt h a nt h a to ft h es t a n d a r ds v m ， k e yw o r d s s t a t i s t i c a ll e a r n i n gt h e o r y m u l t i k e r n e la n da d j u s t a b l e s t r u c t u r e - s u p p o r tv e c t o r m a c h i n e ，e s t i m a t i o no fd e n s i t y , s m o o t h i n gf u n c t i o n 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： 驽塑 指导教师签名 v f 。年6 月。日 函c 9 年j l t 。e t 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论 文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大学 或其它教育机构的学位或证书而使用过的材料。与我同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 獬嚷 矽p 年易月o 日 两北大学硕_ i 学位论文 1 1 支持向量机的研究背景 第一章绪论弟一早殖化 由于现代科学技术的快速发展以及计算机网络技术的日益成熟和普及，信息产生和 传播以几何级数的速度增长。在人们的日常生产和生活中，每天都要产生和积累大量的 信息数据，由信息数据量的急剧增大带来的问题是需要对越来越多的复杂非线性高维数 据进行整理、分析。因此，从大量复杂的信息数据中提炼出对人们有用的信息，就成为 当前非常迫切的具有挑战性的课题。信息数据的数量是如此巨大，以至于我们采用手工 方式去对其进行处理就变得很困难，机器学习方法( 以信息数据为基础) 于是应运而生。 作为现代人工智能的一个核心研究领域，机器学习使用实例数据或者过去的经验去训练 计算机，以使其性能标准得到优化。对于机器学习而言，到目前为止，还未能构建起这 样一种理论框架，使得它能得到人们的普遍认可。有三种方法可以实现机器学习：经典 的( 参数) 统计估计方法、经验非线性方法和统计学习理论【1 1 。 参数统计估计方法是以传统的统计学为理论基础的，这类方法有神经网络、模式识 别等。在经典的参数统计估计方法中，通常有这样的要求，即总体的密度形式是已经确 定的，对各个参数的值进行估计是通过训练样本来进行的。在实际问题当中，对许多训 练样本来说，事先并不能对它们的分布做出假定，或者，要付出相当大的代价才可以知 道其密度形式。另外，传统统计学探讨的渐进理论是建立在样本个数趋于无穷大时的基 础上的，目前多数学习方法都是以上面的假设为基础。可是在现实情形中，我们得到的 通常是有限的样本数目，因此一些算法从理论上来说很好，在实际应用中表现的却不那 么完美。也就是说，统计学习方法的局限性比较大。 经验非线性方法所构建的非线性模型以已知的样本数据为基础，它没有统一的数学 理论作为基础，尽管它解决了传统的参数估计中的一些困难。 统计学习理论【2 j ( s t a t i s t i c a ll e a r n i n gt h e o r y ) 不同于传统统计学，它是这样的一种 理论，即致力于探索样本有限情形下的机器学习规律。它所构建的理论体系是全新的， 是以小样本统计问题为基础而构建起来的，该全新体系下的统计推理规则探索在现有信 息有限的情况下获得某种最优结果，同时也把渐近性能方面的要求考虑进去。早在二十 世纪六、七十年代，v a p n i k 等研究者从就开始研究统计学习理论，并建立起它的框架与 基础思想。到了九十年代中期，统计学习理论得到了比较完善的发展，理论逐渐得到完 1 第一章绪论 善，加上神经网络等其它学习方法在理论方面没有什么突破进展，使得众多研究者越来 越青睐于统计学习理论。 统计学习理论属于模式识别、计算机科学及应用统计学相交叉与结合的范畴，它是 一种研究如何利用经验数据来进行机器学习的一般理论。已初步显示出许多较好性能的 支持向量机( s u p p o r tv e c t o rm a c h i n e ，一新的通用学习方法) 就是以统计学习理论为基 础建立起来的。 s v m 采用结构风险最小化原贝, l j ( s t r u c t u r a lr i s km i n i m i z a t i o n ，s r m ) 去训练学习机， 并使用v c 维理论对相应的结构风险来进行度量。建立在v c 维理论与s r m 的基础之 上，s v m 在学习能力与模型的复杂性之间，即在提高对随机抽取样本的识别能力与增 加对某一确定样本的学习精度之间，根据有限的样本数据来寻找最优选择，使它的推广 能力更好。由于s v m 主要对样本个数有限的情况进行讨论，取得的不只是当样本个数 为相当大时的最优解而是当前已有数据条件下的最优解，这就是s v m 的目标。同时， s v m 把机器学习问题归结成为一个凸二次规划问趔引，这样就能够保证达到目标( 即取 得在样本有限情况下的全局最优解) 。通常，因为比较难于对低维空间数据集进行划分， 为了便于我们处理数据，可以这样来考虑，即先把数据样本映射到高维的特征空间再来 进行整理，但是这种方法会大大地增加计算的复杂度。为了使算法的复杂度不受样本维 数的直接影响，s v m 引入核函数，较好地对这一问题进行了处理。s v m 不仅有统计学 习理论作为其坚实的基础，而且具有直观的几何解释以及完美的数学形式。 综合以上原因，s v m 就自然而然地成为目前在机器学习领域当中受到大量学者广 泛关注的一项新的研究课题。s l t 和s v m 的发展势头良好，s v m 方法1 4 j 目前取得了不 少理论成果，在应用方面的研究成果相对来说比较有限，还需要我们做大量的工作。无 论是在实际工程应用还是理论方法上，s v m 的研究空间都还很大，值得人们对其进一 步探讨。 1 2 本文主要内容 s v m 在机器学习领域中已经受到了人们的广泛关注，并且成为了机器学习与数据 挖掘领域的众多标准工具之一。 支持向量机( s v m ) 作为机器学习领域内众多标准技术当中的集大成者，将最大间 隔超平面、凸二次规划、松弛变量以及稀疏解和m e r c e r 核等多种技术集成在一起。到 目前为止，在众多具有挑战性的应用中，支持向量机获得了最优的性能。支持向量机以 2 西北大学硕上学位论文 及核学习方法在美国的科学杂志上被认为是机器学习领域中相当流行的方法与成功 的例子，它是一个备受瞩目的发展方向。 本论文的内容如下： 第二章首先对机器学习的定义、发展历史以及统计学习理论的相关问题进行了介 绍，并对统计学习理论的几个重要概念进行了着重介绍。 第三章主要介绍了在统计学习理论下发展出的支持向量机方法的特点，分别针对线 性、非线性两种情形讨论了它在分类问题中的应用。 第四章在前人对支持向量机的研究成果基础上对其光滑函数进行了研究，并推导出 了一个八阶光滑函数。对支持向量机进行研究的重要问题之一就是求得新的光滑函数。 王斌等人于2 0 0 8 年使用积分的方法，得到一新递推公式，可用该公式对光滑函数的表 达式进行求解。本文在这一部分利用该递推公式对新光滑函数的表达式进行了推导，接 下来对它的光滑性能进行了分析( 用求导的方法) ，又对它的逼近性能进行了论证( 用 二分法) ，我们得出了下面的结论：同已有的光滑函数( 一到七阶) 相比，本文提出的 新光滑函数的逼近性能更高，有一定的应用价值。 第五章对基于多核结构可调支持向量机的概率密度估计进行了介绍。概率密度作为 解答不确定性问题的基本工具，一直以来对它的研究都是统计学所探讨的关键问题之 一。统计推断的根本任务就是做出对数据分布的推断。统计学中的许多问题之所以能够 得到圆满解决都是因为获得了概率密度函数。该部分在前人研究的基础上进一步的研究 了基于多核结构可调支持向量机的概率密度估计问题，融合多种有关支持向量机的技术 和用于解决不适定性问题的p 方法来对概率密度估计问题进行解决。这一方法综合考虑 了多种实际因素，因而其稳健性更强。 3 第二章机器学习与统计学习理论 2 1 机器学习概述 第二章机器学习与统计学习理论 机器学习的最初研究动机是使人的学习能力能为计算机系统所具备，以便于人工智 能的实现。伴随着计算机科学技术的快速发展，人类对数据的收集和存储能力有了极大 提高。不论是在科学研究还是在社会生活的各个领域内都积累了大量的数据，如何对这 些数据进行有效的分析，发现在其中蕴涵着的规律，这些几乎都已成为了所有领域的共 同的需求，这也就使得机器学习技术受到人们越来越广泛的关注。如今，机器学习技术 在搜索引擎、信息安全、地质勘探、医学诊断、遥感图像识别、战略游戏、d n a 序列 测序、语音和手写识别、机器人运用、证券市场分析等各个方面已得到了广泛地应用， 已经成为了又一个在人工智能应用方面继专家系统之后的重要研究领域。 2 1 1 机器学习的定义 什么叫做机器学习? 关于这一概念到现在为止也没有一个统一的定义。稍微正式一 点的定义【4 j ：机器学习是这样的一门学问，它不但对当下已经存在的知识进行识别而且 专门对机器关于新知识与新技能的获取过程进行探讨。 2 1 2 发展历史 发展历程可分为以下四个阶段： 第一，二十世纪六十年代，创立了第一个学习机器的模型感知器模型，从此 人们对学习过程开始了真正意义上的数学研究。在机器学习领域中提出这一模型意义十 分重大。生理学家er o s e n b l a t t 把感知器的模型表示成一个计算机程序，用于解决最简 单的学习问题，即分类问题，并且通过一些简单的例子证明该模型具有一定的推广性。 接着，感知器的第一个定理的证明过程由n o v i k o f f 于一九六二年给出。在s l t 的建构 过程中此定理起到的作用非常关键。模式识别这个崭新的学科也在这一阶段产生，与此 同时一种重要的方法一机器学习的判别函数法【5 】也在这个阶段形成。 第二，理论分析学派在二十世纪六十至七十年代这段时间里获得许多关于s l t 的研 究成果，这些成果为创立学习理论打下了良好的基础。v c ( v a p n i k - c e r v o n e n k i s ) 维与v c 熵f 6 】两个重要概念在这一时期也被给出。而且泛函空间的大数定律正是以v c 维与v c 熵为基础才发现的，与此同时，一些主要结论( 诸如关于收敛速率的非渐进界) 也被给 4 西北人学硕上学位论文 出，而且正则化理论 7 1 ( 可用于解决不适定问题) 也被提出。经验风险最小化归纳推理 【8 】也在这个阶段由理论分析学派完成。 第三，机器学习在二十世纪八十年代这一阶段呈现出良好的发展态势， d e r u m e l h a r t 和j l m m c c l e l l a n d 于1 9 8 6 年提出了可对感知器所有的神经元的向量系数 同时进行构造的误差反向传播算法【9 1 。作为感知器研究过程中的一次飞跃，发现反向传 播技术有着十分重要的意义，这个阶段的感知器又叫神经网络【1 0 l 。该方法到目前为止仍 具有很大影响。 第四，人们在二十世纪九十年代对神经网络替代方法的研究更为热衷。专门探讨小 样本情形下的机器学习规律的s l t 就是在这个阶段产生的。在s l t 这一体系下，为了 寻求最优解，统计推理规则要对当前样本个数有限的前提以及获得一定程度的渐进性能 这两个方面的要求进行综合考虑。鉴于这一学习方法的优越性显著，国内外众多研究者 对其颇为青睐，以致有关s l t 的研究越来越流行。 2 2 统计学习理论 起源于3 0 年前的统计学习理论，主要探讨的是样本有限情形下的机器学习规律。 这一理论在预测学习以及在样本数目有限的情况下进行统计估计的实际应用过程中表 现良好。这一节我们介绍几个基本的统计学问题以及统计学习理论中的几个主要概念。 2 2 1 三个基本统计学问题 基本统计学中大致存在三个问题【2 】：模式识别问题、回归估计问题和密度估计问题。 在讨论这三个问题之前，我们先看一下学习问题和风险最小化问题。 1 学习问题 学习问题可以这样描述：对于任意一个给定的随机变量x ，都对应着一个未知的不 变的概率分布f ( x ) ；存在着一种这样的依赖关系：每一个输入变量x 都将产生一个输出 变量y ( 遵循某一不变、未知的条件分布f ( yj x ) ) ；通过学习机器可以实现一系列的预 测函数集船o ，f ) ，v e a 。学习过程是根据随机抽取的z 个独立同分布观测样本 ( 而，y 。) ，o ：，y ：) ，“，y ，) ( 遵循某一未知的联合分布f ( x ，y ) 一f ( x ) f ( yx ) ) ，从所给定的 函数集伯 ，f ) ，f a 中寻求一个最优的函数( 即使得输入和输出之间的依赖关系达到最 优的函数) 的过程。 s 第- 二章机器学习与统计学习理论 2 风险最小化问题 通过输出变量y ( 与给定的输入变量x 相对应) 以及函数g ( x ，f ) ( 通过学习机器所 产生) 之间来构造损失函数l ( y ，g ( x ，f ) ) 以便选择最好的近似值以对依赖关系进行预测， 考虑由风险函数 尺o ) 2 严( ) ，g ，z ) 矽o ，) ，) ( 2 1 ) 给定的损失函数的期望值。 从所给定的函数集括o ，f ) ，f 人 中找寻最小化期望风险的函数( 即最优的函数) g o ，) 就是学习的目标。而在实际问题中联合概率分布f ，y ) 是未知的，我们现在知 晓的数据只有独立同分布的样本训练组( 一，y 。) ，0 ：，y ：) ，“，y ，) 。 下面分别介绍上面提到的三个基本统计学问题： ( 1 ) 模式识别问题 我们看两类情况下的识别问题，设输出变量y 只取两个值：y 一 0 ，1 ( 或y = 一1 1 ) ， k 0 ，z ) ，t e a 是一指示函数集( 此函数只取两个值：o 与1 ，或1 与1 ) 。考虑最简单的 损失函数 地如咖o f y y = 嬲 ( 2 2 ) 针对以上函数而言，在输出变量y 与指示函数g o ，f ) 给定的情况下分类错误的概率 由尺 ) 2 f l ( y ，g o ，f ) 矽 ，y ) 给出，这样问题即为在只给出数据观测值 “，y 。) ，o ：，y ：) ，“，乃) 而不知道概率分布f 0 ，y ) 的条件下找寻一个使分类错误的概率 最小化的函数。 ( 2 ) 回归估计问题 设y ( 为实值) 是与输入变量x 相对应的输出变量，馏o ，f ) ，z - e a 是一给定的函数 集( 包括回归函数g ，) 2 f y d f ( y i x ) ) 。众所周知，如果g o ，r ) ：，回归函数就是在 损失函数 l ( y ，g ( x ，f ) ) = ( y g ( x ，f ) ) 2( 2 3 ) 6 两北大学硕十学位论文 的条件下，最小化尺 ) 2 f ( y ，g o ，o ) d f ( x ，y ) a 于是回归估计的问题就是在给定数据观 测值( 一，y 。) 化，y ：) ，“，乃) 而不知道联合分布f ，y ) 的情况下，最小化 r p ) 2 f ( y ，g ( x , o ) d f ( x ，y ) ( 在损失函数( y ，g o ，f ) ) = ( y g o ，f ) ) 2 下) 。 ( 3 ) 密度估计问题 考虑密度估计问题，假设有概率密度函数集 g ，z ) ，t e a ，定义损失函数如下 l ( 9 0 ，f ) ) = 一l o gg ( x ，z ) ( 2 4 ) 概率密度估计就是这样的一个问题，即使得函数r ) 2f y ，g o ，v ) ) d f ( x ，) ，) 在以上 函数l ( gx ，z ) ) * - l o g g ( x ，f ) 下最小化。于是，我们需要在给定独立同分布样本观测数据 “，m ) ，o ：，y ：) ，“，m ) 而不知道概率分布f ) 的情况下，最小化风险函数的值，这样 就可对概率密度估计问题进行解决。 经验风险最小化原则 由于在实际问题中概率分布f o ，y ) 是未知的，我们已知的数据仅有一些独立同分布 的观测样本，故无法对期望风险进行尺p ) 2 严( y ，g o ，v ) ) d f ( x ，y ) 计算得出它的值。所以， 为了最小化风险函数月o ) 2 f o ( z ，o ) d f ( z ) ，f 人( 对于一个未知的概率分布f ( z ) ) ，我 们通常采用下面介绍的归纳原则。 通常是由根据样本训练集乙，z ：，z t 来构造的经验风险函数 p ) 2 善q ( z ，z ) ，z 人 ( 2 - 5 ) 来代替期望风险函数r ( o 。经验风险最小化( e r m ，即为e m p i r i c a lr i s km i n i m i z a t i o n 的缩写) 原则就是这样一种原则，它通过用使经验风险( 2 5 ) 最小的函数q ( z ，) 来逼近使 风险函数尺o ) 。f e ( z ，f ) 炒q ) ，z 人最小化的函数q ( z ，t o ) 。如何才能使风险函数尺o ) 的 值最小化，这是传统学习理论需要解决的问题，e r m 原则也正是属于传统统计理论的 范畴。当训练样本数目f 很大时，e r m 原则就会是非常合理的一个选择，因为这时经验 风险大体能代表期望风险，然而，当训练样本数目，不一定很大，尤其是样本数目，较小 的时候，经验风险和期望风险两者之间会有一些比较大的区别。在这样的情况下，如何 7 第二二章机器学习与统计学习理论 更确切地估计期望风险，从而对经验风险最小化原则进行改进正是统计学习理论所需要 研究的内容。 2 2 2v c 维 作为s l t 的重要概念之一，v c 维【1 】( 由v a p n i k 和c h e r v o n e n k i s 提出) 是到现在为止 一系列描述函数集学习性能的指标当中最好的一个。要对函数集的学习能力进行定量地 表示或是对函数集的复杂程度进行标识，我们就可使用v c 维。 模式识别方法中认为函数集可以打散的样本的最大个数就是v c 维的直观意义，作 为函数集学习能力的体现，如果它的值越大，就表示有越强的学习能力( 因为这时机器 容量也就越大) 。可以通过增大函数集的v c 维来使学习能力增强。但遗憾的是，目前 统计学理论中还存在着一个亟待解决的问题，就是无论是采取实验方法，还是使用理论 上的方法，如何对它的值进行计算的问题，此问题有待于我们进一步研究而解决。 2 2 3 泛化性的界 统计学习理论从v c 维的概念出发，把推广性的界定义为各个类型的函数集的 0 ) 和尺p ) 之间的关系。泛化性的界在两类分类问题中是指对于指示函数集 妇 ，f ) ， t e a 中包含的所有函数，即使经验风险p ) 最小化的函数g ( x ，) 也包括在 内，经验风险 ) 与实际风险r 0 ) 之间满足如下关系( 以最少l - r 的概率) ： 尺p ) s p ) + h ( 1 n ( 2 n h ) + 1 ) - l n ( r 4 ) ( 2 6 ) 上式中r 是满足0sr 墨1 的参数，忍代表从总体中抽得的样本个数，h 表示函数集的 v c 维。从( 2 6 ) 式我们可以看出学习机器的期望风险尺p ) 是由g ) 和 严型掣世幽两部分组成，其中前一项 ) 是经验风险懒差) ，后 一项丛型垒丛生专幽是黄信范围，它不但受到从总体中抽到的样本个数玎的影 响，还受到学习机器的v c 维h 的影响。它不仅是真实风险与经验风险的差值的上确界 的体现，也可表示由复杂的结构而带来的风险，可用下式表示( 2 6 ) 式： r 0 ) s r 唧0 ) + m ( j i l n )( 2 7 ) 8 两北大学硕f ：学位论文 从上式不难看出，在从总体中抽得的样本数珂为定值时，置信范围西 n ) 会随着 学习机器的v c 维h 的增大而变大，这样就会造成真实风险尺p ) 与经验风险( z - ) - 者 之间可能存在的差异变大。机器学习过程中之所以会出现过学习现象，原因就是如此。 为了提高泛化能力，在机器学习过程中，不但要使h 、m o n ) 变小，也要使经验风险 p ) 最小化。 2 2 4 结构风险最小化 结构风险最小化原则【1 1 1 的基本思想：在最小化经验风险p ) 的同时，为了得到较 小的实际风险尺p ) ，可通过控制v c 维h 来缩小置信范围m ( j l l ，1 ) ，这样才可保证达到 对未来样本泛化能力较强的目标( 在机器学习过程中) 。 由足如) s p ) + 西q n ) 式可知，如果固定训练样本数目雄的大小，则可以通过对 参量p ) 和 的大小进行调整来对风险函数的大小进行控制，其中：经验风险p ) 的大小依赖于指示函数g ( x ，f ) ( 由学习机器所选定) 。因而我们可以通过改变该指示函 数的值( 通过控制刁的大小) 来对经验风险进行调整；受到学习机器工作的函数集影响， 可以通过对函数结构进行恰当选取来实现对v c 维进行控制。另外，统计学习理论中有 这样的方法：第一，这样来构造函数集s = 倌0 ，r ) ，f a ，即把它分解成一个函数子集 序列 墨cs 2c c c 第二，根据v c 维的大小对各个子集进行排列 7 l lsh 2s s ，s 第三，寻求使经验风险最小的函数( 在各个子集中) ，我们在这样的子集( 即置信 范围、最小经验风险的和为最小) 中对最小化经验风险的函数进行选择，也就求得我们 所要找的最优函数。 以上过程实际上就是使用e r m 原则在一个大小合适的决策函数候选集中选择决策 函数。 9 第三章支持向量机 第三章支持向量机 3 1 支持向量机方法的特点 在统计学习理论基础上发展起来的支持向量机方法因为其在样本有限情况下的推 广能力较好而受到广泛重视，作为统计学习理论中最年轻的理论，支持向量机方法的几 个主要优点有【4 j ： ( 1 ) 比较通用，可在范围较广的各个类型的函数集中构造函数； ( 2 ) 稳健性强，它对问题的适应性相比于其余方法要更好，无需根据具体问题在 算法上作出许多调整； ( 3 ) 有效性，在对实际问题的解决过程中，是众多好的方法中的一种，能有效的 解决问题； ( 4 ) 计算较简单，支持向量机的求解只涉及到一个不等式约束的二次优化问题。 在理论上，使用简单的优化技术便可以实现s v m 方法。 在s v m 方法中，现有的众多学习算法( 如贝叶斯分类器、多层感知网络、径向基 函数方法等) 可通过定义不同的各种内积函数而得到。假定训练样本集t 中的样本数目 为z ，即z = ，咒) ，咒 一1 ，u ，i e 82 ” z 】 ，毛e r 。该监督学习( 即对一组给定的输入提 供应有的输出结果) 问题包括两个类别，若t 属于第一类，则可标识这一类别为咒= 1 ， 若是属于第二类，那么y i = 一1 。下面我们针对线性和非线性两种情况分别讨论。 3 2 线性情形 1 线性可分情形 定义如下： 假设大小为珀勺训练样本集丁= 瓴，y i ) | y i 一1 ，b ，薯e r ，i e n2 ，“，】) 可分成两类。 如果存在分类超平面： t 0 。工+ 6 0 ( 3 1 ) 使得对于i = 1 ，2 ，z ，满足 1 0 两北大学硕j ：学位论文 ：二：尝三二1z 咒= ；i 一1 c 3 2 ， 就可以说训练样本集是线性可分的。式0 1 ) 和式( 3 2 ) 中表示是向量的内积。 t o c _ r “, b e r 都进行了规范化，使满足条件( 到超平面的距离最近) 的两种类别的样本 点满足式( 3 2 ) 中等式要求。左式也可写成： 咒( 缈。x + 6 ) 芑1 , i = 1 ，2 ，z h 1 h h 2 嗝 o 、 图2 1 线性可分情形 可用图2 1 比较直观地说明s v m 的基本思想。从线性可分情形下的最优分类超平 面而提出支持向量机。在该图中，两类样本分别用星形、空心两类点来代表。h 代表分 类超平面，两侧的q ，4 是这样的两个分类超平面，它们平行于胃，分别过两类样本中 离日最近的一些样本，分类间隔就是它们( 一，h ：) 之间的距离。不但能j 下确地划分开 两类样本( 分别由星形、空心点表示) ，同时可最大化分类间隔，这样的超平面就是最 优分类超平面。 找寻一个最优分类超平面( 在最大化间隔的同时能完全正确地分开这两类样本) 就是 线性支持向量机的目的。 1 】 第三章支持向量机 数学推导过程如下： 假设最优分类超平面日的方程为： 工+ b 一0 经过适当变换，分类超平面日，和h ：的方程为： h 1 ：。x + 6 = 1 ，矿y f = 1 h 2 ：x + b 一一1 ，矿y i = - 1 ( 3 3 ) ( 3 4 ) 直接计算后可得，超平面日，或日：上的点到达最优分类超平面h ：z + 6 0 的距离 为：l x , t , 1 1 0 - - 1 1 1 , o l l ，超平面q 到日：之间的距离是2 忪i l 即就是说相应的分类间 隔为2 l l 甜0 。这样要求0 0 2 最小与要求分类间隔最大是一样的。因为当两类样本是线性 可分的情况时，有y ； 石+ 6 ) 苫1 。于是，可以通过如下的约束优化问题对最优分类超平 面求解。 1 2 彻n 割国8 s j y f ( t o 毪+ 6 ) 1 i = 1 ，2 ，z ( 3 5 ) ( 3 6 ) 这是一个对变量和6d h 的- - 次规划问题【3 1 ，可以通过它的拉格朗日的对偶问题的 进行求解而得到其最优解( 利用l a g r a n g e 优化理论) 。为了导出原始问题( 3 5 ) 、( 3 6 ) 的 对偶问题，在这里引入口g 阳n 伊函数： l ( 缈，玩a ) ：1 1 1 1 1 2 一塞q ( ) ，；( t o x ；+ b ) 一1 ) 3 一 s ，口i 芝0 令式( 3 7 ) 中关于和b 的梯度为零，而且q 0 ： 这里a ；为大于或等于零的数。 芝岩一p i 舻。 b 8 ， 等竽；驷i i t ；一o 。一；f f i - 的惫“1 1 2 ( 3 9 ) 两北大学硕上学位论文 由( 3 8 ) 和( 3 9 ) 可得： = , 善a i y i x i 弘咒却 把( 3 1 0 ) 和( 3 1 1 ) 式代入( 3 7 ) ，可得到( 3 5 ) 、( 3 6 ) 的对偶问题： ( 3 1 0 ) ( 3 1 1 ) m t n c ，6 ，口，；丢砉j 再7a i a j y i y j 工，一善i 口； 3 1 2 豇酗咒乩q 加， 所以，最优分类超平面问题以及约束条件如下： ( 3 1 3 ) 卿n 三1 刍! 再iq 口，咒y ，瓴一) 一妻q ( 3 1 4 ) 由k a r u s h k u l m t u c k e r ( k k t ) 1 l 定理可知，最优解满足： q ( y f ( 薯+ 6 ) 一1 ) = 0 ，i = 1 , 2 , - - - , 1 ( 3 1 5 ) 故b = y i 一 。毛) 。于是可得新的分类决策函数的表示式： 厂o ) l s g n ( ( ) + 6 ) = s g l l ( 善q y i ( x i 工) + 6 ) ( 3 1 6 ) 式中呸是与对应于每个样本的拉格朗日乘积因子，解中只有少量q 满足q 0 ，满 足该条件的q 对应的样本薯就为支持向量( 由支持向量机训练而得到) 。 2 线性不可分情形 当线性函数不能完全划分训练样本集时，即数据是线性不可分的，则不能使用以上 我们所介绍的线性可分情形下的模型。在这样的一种情况下，为了解决上述问题，我们 可找出出错最少并能使分来间隔达到最大的超平面，把松弛项毒o 加入到式( 3 6 ) 中， 使超平面x + 6 a 0 满足： 2 0 l l l 咒 叫 锁 乩 ，x智q 第三章支持向量机 这时，目标函数变为： y f ( t o + 6 ) 一1 ) 1 一毒， i 一1 ，2 ，z ( 3 1 7 ) m i n 扣| 2 + c 善i 皇 s j y i ( 毛+ 6 ) - x ) 乏1 一皇 皇20 ， i = 1 ，2 ，z ( 3 1 8 ) 式中，c 为惩罚参数，满足c 0 ，可通过它对错分样本的惩罚程度进行控制，即 如果对错误分类的惩罚越大则c 取值越大。由优化理论可知，最优分类超平面的对偶问 题在线性不可分情形下可表示为： 啤。n 三1 刍t 荟tq 口，咒y ， 一) 一骞q ( 3 1 9 ) s 1 0s q 墨c 荟q 咒- 0 ，扛啦， 与线性可分情形一样，支持向量所对应的q 满足( z i 0 。因而可得广义最优分类超 平面的决策函数： ，o ) ls g n ( 荟西咒瓴_ ) + 6 ) ( 式中o f * - - - - ( 西，西) r 为( 3 1 9 ) 的解) ( 3 2 0 ) 我们可由任意不为零的a ? 求出6 2 y j - 善西m _ ) 。 3 3 非线性情形 当训练集为非线性时，s v m 用这样的方法使得我们可用线性判别函数对样本在高 维特征空间中来进行分类，即通过一非线性函数m ( 。) 将样本映射到一高维线性特征空 间，这样就把不可分问题( 原低维输入空间中) 通过非线性变换而变为线性可分问题( 高 维特征空间中) 。与前面的方法类似，需要用m ) 代替公式中的x ，则便可以得到一个 分类超平面1 5 1 ( 在特征空间上) ，它与一个分类超平面( 原空间上) 相对应，是高维特征 1 4 西北人学硕l 学位论文 空间中的超平面。为了得出相应的二次规划问题可将上节的算法用于高维特征空间中， 我们只需要用m ( 鼍) 。 ) 对薯。工j 进行替换。可由核函数k z j ) ( 满足m e r c e r 定理条 件) 对非线性映射的内积m ( t ) 西( z ，) 进行替代，即： ( 薯) m o ，) = k ( 五z ，)( 3 2 1 ) 这时的分类超平面为： 币0 ) + 6 ) 一0 ，式中b e r ，w e h ( h 为特征函数) 是如 下最优化问题的解： m i n 抑| 2 + c 砉岛 s t y i ( t o 。t + 6 ) - 1 ) 之1 一磊 戛0 ， ii1 ，2 ， 于是构造非线性判别函数的任务就可以转化成求解下面的优化问题： ( 3 2 2 ) 哑n 丢套套q a ，咒y ，k 一，一妻q c 3 2 3 ， 珐罗呸y i ；0 舒 0 s o f is c ，i 一1 , 2 , - - , 1 求解就可以得到相对应的那个决策函数表达式为： 厂o ) = s g n ( 善a i y i k ( x i 。工) + 6 ) ( 3 2 4 ) 若使用的内积核函数( 在支持向量机中) 不一样，得到的算法也就不一样，常用的 核函数主要有以下几种【4 】： ( 1 ) 线性函数：在线性可分的情形下，核函数可表示为两个向量的内积形式： k o ，y ) = 工y ( 2 ) 多项式核函数：多项式核函数可表示为如下形式： ( 3 ) 径向基核函数： k ，y ) 一 。y + 1 ) ，t = 1 ，2 ， 第三章支持向量机 k ( x ，y ) = e x p ( 一忙一y l2 2 6 2 ) ( 4 ) 多层感知机： 支持向量机采用s i g m o i d 函数作为内积时，实现的便为多层感知机( 它包含一隐含 层，通过算法可以自动对该隐含层中的节点个数进行确定) ，s i g m o i d 函数表达式： k o ，y ) 一t a n h ( 比 y ) - h ) 1 6 两北大学硕十学位论文 第四章支持向量机的新光滑函数及其性能分析 作为数据挖掘的一种新方法，支持向量机s v m ( s u p p o r tv e c t o rm a c h i n e ) 是建立在 严格的理论基础之上的，它较好地解决了高维数、非线性、局部极小点等问题，因此， 继神经网络研究后在机器学习领域，大量研究者都对其颇为重视。支持向量机无论是在 应用研究上( 在回归分析、时间序列的分析以及模式识别领域等较突