（应用数学专业论文）基于人为误差的支持向量机.pdf

摘要 内容摘要：支持向量机是v a p n i k 等人提出的一种以统计学习理论为基 础的机器学习方法，它以结构风险最小化代替经验风险最小化作为 优化准则，在最小化样本点误差的同时缩小模型预测误差的上界， 从而提高了模型的泛化能力，即使在小训练样本的情况下理论上也 可以得到很好的效果 对于分类问题，支持向量机的基本思想是在线性情况下，在原 空间寻找两类样本的最优分类超平面；而在非线性的情况下，是通 过一个非线性映射将输入数据映射到一个高维内积空间并在这一高 维特征空间中寻找最优分类超平面，因此可以很好的解决样本高维 问题另外，支持向量机通过解一个线性约束的二次规划问题得到全 局最优解 本文以解决分类问题为目标，对支持向量分类机从理论和模型 等方面进行深入研究，主要工作如下： 从两类训练样本近似线性可分的情况入手，本文对传统的支 持向量机算法及其变形算法进行分析和研究 通过对传统的支持向量机算法及其变形算法的分析和研究， 考虑当训练集数据有较大人为误差参与的情况本文以训练集数据受 到较大的人为误差影响为出发点，研究了当训练集数据含有人为误 差时如何保障其算法精度的问题，提出了基于人为误差的支持向量 机( a r t i f i c i a le r r o r - - s u p p o r tv e c t o rm a c h i n e 以下称a e - - s v m ) 的思 想 介绍了基于人为误差的支持向量机的基本理论，并建立 i 基于人为误筹的支持向最机 t a e - - s v m 的理论模型，是c s y m 模型的改进和推广 关键词：支持向量机( s y m ) ；统计学习理论；分类问题；机器学 习：经验风险：错划程度；c s y m ：人为误差：a e s y m ：非 光滑最优化 a b s t r a c t c o n t e n t ：s u p p o r tv e c t o rm a c h i n e ( s v m ) w a si n t r o d u c e db yv a p n i k o nt h ef o u n d a t i o no ft h es t a t i s t i c a ll e a r n i n gt h e o r y i nt h e o r y , s v m p e r f o r m 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 ( s r m ) p r i n c i p l e ，w h i c hm i n i m i z e sa nu p p e rb o u n do nt h eg e n e r a l i z a t i o ne r r o r ，a so p p o s e dt oe m - p i r i c a lr i s km i n i m i z a t i o n ( e r m ) w h i c hm i n i m i z e st h ee r r o ro nt r a i n i n g d a t a a l lt h e s ei n h e r e n tc h a r a c t e r i s t i c sd e c i d et h a tt h eg e n e r a l i z a t i o n o fs v mi sg o o de v e ni nh i g hd i m e n s i o n a ls p a c e su n d e rs m a l lt r a i n i n g s a m p l ec o n d i t i o n s r e g a r d i n gc l a s s i f i c a t i o np r o b l e m ，w h e nt h et r a i n i n gd a t as e ti s l i n e a r ，t h eb a s i ci d e ao fs v m i st os e e kt h eo p t i m a ls e p a r a t i n gh y p e r - p l a n ef o rt w ok i n d so fs a m p l e si nt h eo r i g i n a ls p a c e ；w h e nt h et r a i n i n g d a t as e ti sn o n l i n e a r ，t h eb a s i ci d e ao fs v mi st om a pt h ei n p u td a t a i n t oah i g h e rd i m e n s i o n a lf e a t u r es p a c ea n dt h e ns e a r c hf o rt h eo p - t i m a ls e p a r a t i n gh y p e r p l a n ei nt h i sf e a t u r es p a c e t h e r e f o r e ，s v m r e s o l v e sp r o b l e m se v e ni ft h es a m p l e si sh i g h - d i m e n s i o n a l m e a n w h i l e ， s vmt r i e st os o l v eaq u a d r a t i cp r o g r a m m i n gp r o b l e mw i t hal i n e a r c o n s t r a i n tt os e e kag l o b a lo p t i m i z e ds o l u t i o n t h i sp a p e rr e s e a r c h e so ns u p p o r tv e c t o rm a c h i n e ( s v m ) i nt h e o r y a n dm o d e li no r d e rt os o l v ec l a s s i f i c a t i o np r o b l e m t h ef o l l o w i n gp a r t s a r em a i nw o r k s ： o b t a i n sf r o mt w ok i n d so ft r a i n i n gs a m p l e sa p p r o x i m a t el i n n l 基于人为误差的支持向量机 e a r i t ys e p a r a b l es i t u a t i o n ，t h i sa r t i c l ea n a l y s e sa n dr e s e a r c h e st h et r a - d i t i o n a ls u p p o r tv e c t o rm a c h i n ea l g o r i t h m sa n dt h ed e f o r m a t i o na l g o - r i t h m s i nt h i sp a p e r ，w ea n a l y s ea n ds t u d yt h et r a d i t i o n a ls u p p o r t v e c t o rm a c h i n ea l g o r i t h ma n dt h ed e f o r m a t i o na l g o r i t h m ，c o n s i d e r i n g t h es i t u a t i o no ft h el a r g e ra r t i f i c i a le r r o ri n v o l v e di nt r a i n i n gs e td a t a b a s e do nt r a i n i n gd a t as e tb yt h el a r g e ri m p a c to fa r t i f i c i a le r r o ra st h e s t a r t i n gp o i n t ，t h i sa r t i c l eo b t a i n sf r o mt h i sf l a w ，t os t u d y ，w h e nt h e t r a i n i n gr e g u l a t i o n sd a t ai n c l u d e dt h ea r t i f i c i a le r r o rh o wt os a f e g u a r d t h ea u c c u r a c yo ft h ea l g o r i t h m s ，p r o p o s e st h es u p p o r tv e c t o rm a c h i n e s b a s e do na r t i f i c i a le r r o r ( a r t i f i c i a le r r o r - - s u p p o r tv e c t o rm a c h i n eh e r e - i n a f t e r ) t h i n k i n g t h i sp a p e ri n t r o d u c e st h eb a s i ct h e o r yo ft h es u p p o r tv e c t o r m a c h i n eb a s e do nt h ea r t i f i c i a le r r o r ，a n de s t a b l i s h e st h et h e o r e t i c a l m o d e lo fa e - - s v m t h i sm o d e li st h ei m p r o v e m e n ta n dt h ep r o m o - t i o no fc s v mm o d e l k e yw o r d s ：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 ll e a r n i n g t h e o r y ；c l a s s i f i c a t i o np r o b l e m ；m a c h i n el e a r n i n g ；e m p i r i c a lr i s k ；w r o n g z o n e dd e g r e e ；c s vm ：a r t i f i c i a le r r o r ；a e - - s v m ；n o n s m o o t ho p - t i m i z a t i o n 1 v 学位论文独创性声明 本人承诺：所旱交的学位论文是本人在导师指导下所取得的研究成果论文中除特别 加以标注和致谢的地方外，不包含其他人和其他机构已经撰写或发表过的研究成果，其他同 志的研究成果对本人的启示和所提供的帮助，均已在论文中做出了明确的声明并表示谢意 学位做作者繇王淑仙日期： 哪，厂甲 学位论文版权使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有权 保留并向国家有关部门或机构送交复印件和磁盘，允许论文被查阅和借阅本人授权辽宁师 范大学，可以将学位论文的伞部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其他复制手段保存、汇编学位论文保密的论文在解密后使用本授权书 学位论文作者签名：j 二誓坟关j 指导教师签名： e t期： 基丁二人为误差的支持向最机 1绪论 1 1引言 基于人为误差的支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是一种新的通用机器学 习方法它是c o r t e s 和v a p n i k 首先提出来的1 ，已成为近年来机器学习研究 的一项重大成果v a p n i k 与c h e r v o n e n k i s 的统计学习理论( s t a t i s t i c a ll e a r n i n g t h e o r y ，s l t ) 2 卜【4 】，对有限样本情况下模式识别中的一些根本性问题进行了系 统的理论研究，很大程度上解决了模型选择与过学习问题、非线性和维数灾难 问题、局部极小点等问题，支持向量机正是在这一理论基础上发展起来的与 传统的人工神经网络相比，支持向量机不仅结构简单，而且各种技术性能尤其 是泛化( g e n e r a l i z a t i o n ) 能力明显提高，这已被大量实验证实 尽管目前支持向量机的性能己经十分出色，并且其理论也日趋完善，但我 们认为对支持向量机在某特定情况进行研究是十分必要的基于惩罚参数的支 持向量机有两个相互矛盾的目标，即：最大化间隔和最小化训练错误通常引入 & 作为一种经验风险的度量，描述训练集被错划的程度引入惩罚参数c 描 述模型对这两个矛盾目标的重视程度而c 没有明确的物理意义，所以c 的选 择比较困难为此，支持向量机的若干变形算法被提出然而，c s y m 算法 及其变形算法均忽略了训练集中的数据若存在较大的人为误差时，如何保障模 型的精度这个问题当训练集中有人为误差参与的时候，以上算法的效果会与实 际产生较大的偏差因此，本文主要针对近似线性可分的i ) l i 练集中存在人为误 差的情况，提出了基于人为误差的支持向量机( a e - - s v m ) 的基本理论，改造 c s 矿m 的经验风险度量，建立了a e s y m 的理论模型 1 1 1 支持向量机的背景 统计学在机器学习中起着重要的基础性作用但是传统的统计学研究的主 要是渐近理论，即当样本趋于无穷多时的统计性质所以基于传统统计理论的 各种学习方法，都是以样本无穷多为假设来推导算法然而在现实中，我们面 对的样本数量往往是十分有限的，通常的方法是仍以样本无穷多为假设进行算 基丁二人为误差的支持向肇机 法推导和建模当样本数较少时，用这种方法得到的结果有时是差强人意的 为了解决此类问题，研究者们的工作一直在进行，直到2 0 世纪7 0 年 代v a p n i k 等人开始建立一个新的统计学理论体系，即：统计学习理论( s t a t i s t i c a l l e a r n i n gt h e o r y ，简称s l t ) 统计学习理论系统地研究了机器学习的问题，尤 其是小样本情况下的统计学习问题统计学习理论为人们系统地研究小样本情况 下机器学习问题提供了有力的理论基础，并在此理论的框架体系下，产生了一 种新的非常有力的通用学习方法：支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称 s v m ) 由于支持向量机具有非常优良的性能，该理论正吸引着大量的研究者 1 1 2 支持向量机的基本思想 支持向量机是在统计学习理论基础上发展出的一种性能优良的学习机器 其基本的思想是，在线性情况下，在原空间寻找两类样本的最优分类超平面； 而在非线性情况下，首先将输入数据映射到高维的特征空间，并在该特征空间 中寻找最优分类超平面( v a p n i k ，1 9 9 5 ) 1 1 | 支持向量机利用一些具有特殊性质的 核函数，将特征空间中的内积运算转化为低维空间中的非线性运算，从而巧妙 地避免了高维空间中的计算问题 支持向量机拥有众多的优良性，如利用核技术避免了解的局部最小、具有 解的稀疏性、通过界限的作用达到容量控制或支持向量数目的控制等等实际 上支持向量机的这些特性从上世纪6 0 年代就已经在机器学习研究中提出并得到 应用到1 9 9 2 年，所有这些特征被整合到一起，构建了最大边界分类器，即基 本的支持向量机( b o s e r ，g u y o na n dv a p n i k ，1 9 9 2 ) 1 4 1 1 2研究现状和发展 1 2 1支持向量机的研究现状 由于支持向量机在许多应用领域表现出较好的推广能力，自9 0 年代提出 以后，得到了广泛的研究在机器学习领域内的学术杂志如m a c h i n el e a r n i n g ) ) 、( ( i e e et r a n so nn e u r a ln e t w o r k s ) ) 等刊登了许多与s v m 相关的文 章，与机器学习有关的著名国际会议都将s y m 作为一个重要的讨论主题，不 少论文更是以其为研究对象概括的说，目前有关支持向量机的研究状况和成果 主要有： 2 基丁人为误差的支持向最机 s v m 算法改进人们通过增加函数项、变量或修改系数等方法使标准的 支待向量机中的最优化问题变形产生出能解决某一类问题或在某方面有优势的 算法；另一方面最初的支持向量机是用来解决分类问题的，后来推广到回归问 题、多类问题等，针对不同问题产生了各种变形算法目前，建立高效的求解 支持向量机中的最优化问题算法，是支持向量机理论的研究中一个很有意义且 急需解决的问题 海量数据的分类由于s v m 的训练过程就是求解一个凸的二次规划问 题( q p ) ，需要训练和存储核函数矩阵，其大小与训练样本数的平方相关对于 小规模的( q p ) 问题，经典的最优化算法，如牛顿法、拟牛顿法等都可以较好的 求解但当训练集很大特别是支持向量数目很大时，多数算法复杂度会急剧增 加，而且占用极大的系统内存为降低计算资源、提高算法效率，研究者们提 出许多针对大规模样本集的训练算法，如块算法、子集选择算法、序列最小优 化算法等 利用s v m 解决多分类问题由于支持向量机是针对两分类问题提出的， 因此存在一个如何将其推广到多分类问题上特别是对极大类别分类的问题上 目前有一对一、一对多、s y m 决策树、m u l t i s y m 几种方案 近年来，对s y m 的研究主要集中在对s y m 本身性质的研究和完善以及 加大s y m 应用研究的深度和广度两方面 1 2 2 支持向量机的发展 到目前为止，支持向量机已应用于模式分类、回归分析、函数估计等领 域，并已成功应用到手写阿拉伯数字识别、文本自动分类、说话人识别、人脸 检测、性别分类、计算机入侵检测、生物信息技术、遥感图象分析、目标识别 等诸多实际问题中当前对s v m 的研究方兴未艾，训练算法的研究方向主要 是确定不同的优化目标，根据k k t 约束优化条件寻找大规模训练样本下的实 用算法；应用方向主要是为模式识别的多类问题寻找好的算法和解决训练样本 规模和训练速度之间的矛盾、解决支持向量数目和分类速度之间的矛盾在此 基础上进行进一步的机理分析和试验分析，探索和拓宽s v m 新的应用领域， 使其成为更有发展前途的新技术 3 基于人为误差的支持向最机 1 3本文的研究内容和全文组织结构 1 3 1 本文的主要研究内容 本文的研究内容和主要结果如下： 从传统的s v m 模型c s y m 算法出发，肯定c s y m 算法的优点的 同时指出了c s y m 及其修正算法的不足这些模型的不足之处就在于它们都 忽略了当训练集中某些样本点信息含有一定的人为误差的情况 针对近似线性可分的训练集中存在人为误差的情况，改进现有的算法模 型，提出了基于人为误差的支持向量机一一a e s y m 的基本理论 改造c s y m 的经验风险度量，建立了a e s y m 的原始理论模型， 是c s y m 的改进和推广 1 3 2全文的组织结构 第一章是绪论，概述了支持向量机的背景和基本思想，对目前国内外支持 向量机的研究现状和发展进行了描述，并对本文的研究内容和组织结构作了阐 述 第二章简述了支持向量机相关的基本理论从统计学习理论的内容出发，介 绍了v c 维、推广性的界、结构风险最小化原则的基本内容，引出了支持向量机 的理论，以此作为以后章节研究的基础 第三章着力研究当训练集中的数据存在较大的人为误差时，如何保障模型 的精度问题先分析了传统的支持向量机模型c s y m ，指出了c s y m 算 法的优点和不足然后概述了针对c s y m 的不足提出的一系列s v m 变形算 法，它们都忽略了当样本中出现受人为误差影响很大的训练点的情况针对训 练集中某些样本点信息含有一定的人为误差的情况来改进现有的s v m 算法， 其核心就是选用更为合理的经验风险的度量方法引入了基于人为误差的支持 向量机( a e s y m ) 的基本理论，并建立了基于人为误差的支持向量机的原始 模型 第四章是结论和展望，对全文进行系统概括，指出了本文的创新点和存在 的问题，并对今后支持向量机的研究工作做出展望 4 基丁二人为误差的支持向最机 2统计学习理论和支持向量机 本章首先介绍了统计学习理论的主要内容，在此基础上讨论了简单的线性 情况下的支持向量机，然后进步将其推广到非线性的情况，介绍了核函数的 有关知识 2 1 统计学习理论 与传统统计学相比，统计学习理论( 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 s 一种专门研究小样本情况下机器学习规律的理论v a p n i k 等人从六、七十年代开 始致力于此方面研究【6 1 6 ，到九十年代中期，随着其理论的不断发展和成熟，也 由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越 来越广泛的重视【7 一 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学 习问题提供了一个统一的框架它能将很多现有方法纳入其中，有望帮助解决 许多原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) ： 同时，在这一理论基础上发展了一种新的通用学习方法一一支持向量机，它已 初步表现出很多优于已有方法的性能一些学者认为，统计学习理论和支持向量 机正在成为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论 和技术的发展i s 统计学习理论中最有指导性的理论结果是推广性的界，与此相关的一个核 心概念是y c 维统计学习理论用y c 维来描述学习机器的容量，并从控制学习 机器容量的思想出发，结合经验风险和训练样本数目，导出了期望风险在不同 情况下的一组风险上界这些界具有如下特点： 1 、这些界是通用的，与具体数据的分布无关； 2 、在小样本情况下同样成立 在实际的训练过程中，可以通过最小化风险上界，实现对学习机器的优 化，因此所得到的学习机器的复杂度受到很好地控制，即使在小样本情况下也 同样具有比较高的泛化能力 2 1 1v c 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列 5 基丁人为误差的支持向最机 有关函数集学习性能的指标，其中最重要的是y c 维( v a p n i k - - c h e r v o n e n ki s d i m e n s i o n ) 模式识别方法中y c 维的直观定义是：对一个指示函数集，如果存 在h 个样本能够被函数集中的函数按所有可能的2 种形式分开，则称函数集能 够把h 个样本打散；函数集的y c 维就是它能打散的最大样本数目h 若对任 意数日的样本都有函数能将它们打散，则函数集的y c 维是无穷大有界实函数 的y c 维可以通过用一定的阈值将它转化成指示函数来定义 y c 维反映了函数集的学习能力，y c 维越大则学习机器越复杂f 容量越 大) 遗憾的是，目前尚没有通用的关于任意函数集v c 维计算的理论，只对一 些特殊的函数集知道其y c 维比如在佗维实数空间中线性分类器和线性实函 数的y c 维是礼- t - 1 对于一些比较复杂的学习机器( 如神经网络) ，其y c 维除 了与函数集( 神经网结构) 有关外，还受学习算法等的影响，其确定更加困难对 于给定的学习函数集，如何( 用理论或实验的方法) 计算其v c 维是当前统计学 习理论中有待研究的一个问题【9 】 2 1 2 推广性的界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险 之间的关系，即推广性的界【2 】关于两类分类问题，结论是：对指示函数集中的 所有函数( 包括使经验风险最小的函数) ，对于任意的参数aer ( r 是抽象参数 集合) ，经验风险思唧( 口) 和实际风险冗( 口) 之间以至少1 一刁的概率满足如下关 系【1o 】： r ( q ) r m p ( q ) + 其中，h 是函数集的y c 维，z 是样本数 这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经 验风险( 训练误差) ，另一部分称作置信范围，它和学习机器的y c 维及训练样 本数有关对于一个特定的学习问题，当样本数固定时，如果学习机器的v c 维越高( 复杂度越高) ，则置信范围越大，导致实际风险与经验风险之间的差就 越大因此，在设计分类器时，不但要使经验风险尽可能小，而且要控制其v c 维也尽可能小，从而缩小置信风险，使实际风险最小，即对未来样本有较好的 推广性 6 基于人为误差的支持向最机 2 1 3 结构风险最小化原理 如果我们要求实际风险最小，就需要使得不等式中两项相瓦权衡，需要同 时最小化经验风险和置信范围；另外，在获得的学习机器经验风险最小的同 时，希望学习机器的泛化能力尽可能大，这样就需要h 值尽可能小，即置信范 围最小统计学习理论提出了一种新的策略，即把函数集构造为一个函数子集 序列，使各个子集按照v c 维的大小排列；在每个子集中寻找最小经验风险， 在子集间折衷考虑经验风险和置信范围，使之达到实际风险的最小这种思想 称作结构风险最小化( 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 准则 根据( 木) 式，如果固定训练样本数目f 的大小，则控制实际风险r ( q ) 的参 量有两个：r e m p ( a ) 和h 随着h 的增加，经验风险危m p ( q ) 递减这是因为 h 增加，根据v c 维的定义，对应的函数集合的描述能力增加，学习机器的学 习能力就增强，可以使有限样本的经验风险很快的收敛，甚至于变为0 ；根 据( 木) 式，置信范围随着h 的增加而增加，所以要获得小的实际风险，就要折中 考虑经验风险和置信范围的取值 支持向量机通过最大化分类边界以最小化y c 维，也即在保证经验风险最 小的基础上最小化置信范围，从而达到最小化结构风险的目的，因此支持向量 机方法实际上就是结构风险最小化思想的具体实现 2 2 支持向量机 2 2 1两类样本训练集线性可分的情况 给定训练集t = ( ( z 1 ，v 1 ) ，( x l ，轨) ) ( xx y ) ，戤x = r n ，犰 y = - 1 ，1 ) ，i = 1 ，f 寻找x = 舒上的一个实值函数g ( x ) ，以便用 决策函数f ( x ) = s g n ( g ( x ) ) 推断任一模式z 相对应的y 值由此可见，求解分类 问题实质上就是找到一个把舻上的点分成两部分的规则 当训练集线性可分【1 1 】时，s v m 模型为： m i n m l n 去1 2 。i i i u - s t 玑( ( u x i ) + 6 ) 1 ， ( 1 ) i = 1 ，f 解上述对变量u 和b 的最优化问题( 1 ) ，求得最优解u + 和b ，构造分化超 平面p z ) + b = 0 ，由此求得决策函数f ( z ) = s 夕几( ( u z ) + b 4 ) 7 基于人为误差的支持向量机 2 2 2两类样本训练集线性不可分的情况 当训练集线性不可分时，对第i 个训练点( x i ，y i ) 引进松弛变量矗，把约 束条件放松为犰( ( u x t ) + b ) + 毛1 ，s v m 模型为： 1 z m i n 钏u l l 2 + c 已 一 i = 1 s t 玑( ( u x i ) + b ) 1 一已， ( 2 ) 已0 ， i = 1 ，z 其中，毫一一松弛变量；c 一一惩罚参数 目标函数的前一项反映的是置信范围，后一项反映的是训练误差，前后两 项体现了结构风险最小化原则根据优化理论，上述优化问题的对偶形式是： m i n 巾) = 丢q t q q e t q s t 厂q = 0 ， 0 q c 式中q = ( q 1 ，q f ) 丁，o q 是问题( 1 ) 或( 2 ) 中不等式对应的拉格朗日乘 子，h e s s i a n 阵q 是半正定的，q 玎= y i y j x i x j ，e = ( 1 ，1 ) t 2 2 3 样本训练集非线性可分的情况 当样本训练集是非线性的时候，核函数的引入极大地提高了学习机器处理 非线性分类问题的能力，同时也保持了学习机器在高维空间中的内在线性，从 而使学习易于掌握和控制s y m 通过使用核函数，实现了把低维空间中的非线 性可分问题转化成在高维空间中的线性可分问题，该训练过程并不需要知道具 体的非线性映射s v m 利用核函数的方法在输入向量和高维空间向量之间建 立一种映射关系，从而避免了在高维空间中直接计算的难题，即高维空间中的 内积运算可以通过原空间中定义的核函数来完成，不需要直接利用映射后的样 本在高维空间中进行复杂的运算空间升维后，仅仅改变了内积的运算，并没有 使算法的复杂性随维数的增加而增加，并且在高维空间中的推广能力并不受维 数的影响也就是，引入核函数不仅可以实现非线性算法，而且算法的复杂度不 会增加，从而为在高维特征空间解决复杂的分类或回归问题奠定了理论基础 8 基于人为误差的支持向最机 核函数的确定并不困难，对任何的对称函数只要满足m e r c e r 定理即可符合 要求常用的核函数有： ( 1 ) 多项式核：k ( x ( 2 ) 径向基( r b f ) 核：g ( x ( 3 ) 傅立叶核：k ( x ( 4 ) 样条核：g ( x ( 5 ) s i g m o i d 核：k ( x ， z 7 ) = ( ( z 。7 ) + 1 ) d z 7 ) = e x p ( - 一r l l a ：一z 川2 ) z 7 ) = 币丽1 _ ( z q 2 ；矸雨 ) = b 2 。+ 1 ( z x 7 ) z 7 ) = t a n h ( k ( x x 7 ) 一) ，其中，k 0 ， 0 9 基于人为误筹的支持向最机 3基于人为误差的支持向量机 3 1引言 支持向量机( s y m 【1 1 】) 是统计学习理论的新发展，算法建立在结构风险最小 化原则之上，是一种新型的结构化学习方法 基于惩罚参数的支持向量机有两个相互矛盾的目标，即：最大化间隔和最 小化训练错误，通常引入已作为一种经验风险的度量，描述训练集被错划的 ；= 1 程度引入惩罚参数c 描述模型对这两个矛盾目标的重视程度而c 没有明确 的物理意义，所以c 的选择比较困难为此，支持向量机的若干变形算法被提 出，比较成功的有 一s y m 【1 1 】、冗一s v m 1 2 1 、w s y m 【1 3 、三s s y m l l 4 等一系列变形的支持向量机算法然而，这些算法均忽略了训练集中的数据若 存在较大的人为误差时，如何保障模型的精度这个问题另外，这种现象在实 践中是经常发生的，是考验模型适应性的重要因素例如现有技术的不完善造 成的人为误差、医学观察中的人为误差等当训练集中有人为误差参与的时 候，以上算法的效果会与实际产生较大的偏差因此，本文丰要针对近似线性 可分的训练集中存在人为误差的情况，改造e s y m 的经验风险度量，建立 a e s y m 的理论模型 3 2 传统的s y m 模型( 线性可分的情况) 给定训练集t = 题z 1 ，y 1 ) ，( x l ，们) ) ( x y ) 。，孔x = 形，犰 y = 一1 ，1 ) ，i = l ，z 如第二章所述当训练集线性可分时，s v m 模 型为= 1 m l r l 去叫1 2i l i u i i _ s t 玑( ( u 毛) + 6 ) 1 ， ( 1 ) i = l ，z 当训练集近似线性可分时，任何分划超平面都有可能出现错划情况【1 5 1 所 以不能再要求所有训练点满足约束条件玑( 反) + b ) 1 为此对第i 个训练 点( 甄，玑) 引进松弛变量已0 ，把约束条件放松为玑( ( u ) + b ) + & 1 显然向量= ( f 1 ，剐t 体现了允许训练集被错划的情况，而由f 可以 构造出描述训练集被错划的程度例如，已可以作为描述训练集被错划程 1 0 基丁人为误差的支持向量机 度的一种度量这时仍希望间隔丽2 尽可能大，同时希望错划程度已尽可 能小引入惩罚参数c 作为综合这两个目标的权重，即最小化新的目标函数 m i n ；l 川1 2 + c 已因此有上述s v m 模型： m i n 知圳z + c 壹已 一 i - - - - 1 s t 犰( ( 彬反) 十功1 一矗， ( 2 ) 6 0 ， i = 1 ，f 其中，已一一松弛变量；c 一一惩罚参数 也称该支持向量机为c s y m 【i i j i i 科研工作者经过大量试验证明了该支 持向量机无论是在理论还是实践中都是比较成功的，同时也发现了一些不足。 例如：c 没有直观解释，在实际应用中很难选择适当值：c s y m 算法不 适合处理大规模问题；c s y m 算法不能根据每个样本点数据的重要性区 别对待等针对这些不足，研究者们分别建立了一些修正模型，如口一s y m 、冗一s y m 、一s y m 等除此之外，近期最受关注的一个修改模型就是 三s s y m 它是传统的s y m 算法与最小二乘技术的完美结合虽然目前 s v m 有很多种类的修改模型，但是它们都忽略了如果训练集中某些样本点信 息含有一定的人为误差的情况，本文就从该缺陷入手，引入了a e s y m 的基 本理论 3 3a e s y m 基本理论和原始模型建立 3 3 1a e s 矿m 基本理论 以上几种算法忽略了当样本中出现受人为误差影响很大的训练点的情况， c s y m 算法不能根据每个样本点数据的重要性区别对待，。w s y m 中用 & 来惩罚c 已一项，但是8 i 的选取需要合理化文献f 1 6 】认为在样本集中 第一个样本的重要性最低，8 。选取为小于1 的值，最后一个样本的重要性最 高，8 设定为1 ，采用线性插值方法得到其他样本点的加权系数文献【1 7 】针 对v - - s v m 提出w - - s v m 方法，s i 只有2 个值8 + 和s 一，分别表示正类和 1 1 基丁人为误差的支持向最机 负类对应的加权系数，根据二类别中每类样本的数量来确定s + 和s 的值，即 s + ：s 一= z + ：f 一，f + 、l 分别表示正、负类的样本数 其实，针对训练集中某些样本点信息含有一定的人为误差的情况来改进现 有s y m 的核心就是选用更为合理的经验风险的度量方法 3 3 24 e s y m 原始模型的建立 给定训练集t = & z 1 ，! 1 ) ，( 动，犰) ) ( x y ) 。，鼢x = 舻，玑 y = - 1 ，1 ) ，i = 1 ，z 对此训练集应用c s y m 算法，解c s y m 模型的对偶问题，求得最优解( i t = ( q ；，q ；) 7 原始问题的l a g r a n g e 函数为： 己p = 扣圳2 + c 妻已一妻口如c 即u 舶，- - 1 + i ，一妻胁毛 q t 0 ，地0 原始问题的k k t 条件是： u 一q i y i x t _ 0 ，啦y 产0 ，c - a t 一肌= 0 ， = 1i = 1 y i ( w x i + b ) 一1 + 已0 ， 矗0 ，o l i 0 ，p t 0 ， o t ( 玑( u x i + b ) 一1 + 矗) = 0 ， 肌矗= 0 由最优解矿和k k t 条件中的互补松弛条件可求得已，i = 1 ，z 下面利用上述求得的已，i = 1 ，2 以及预先给定的常数6 ( 0 6 1 ) 的信息，提取受人为误差影响严重的训练点的集合， 由于已度量了第i 个训练点的误差情况，那么认为“若毛比已的某个倍 数大时，其对应的训练点可能存在较大的人为误差”这一结论成立是有道理的 于是可以取 r f 、 r = ( y i ) l i 6 已 c z 1 2 基丁人为误筹的支持向最机 显然上述参数6 ( 0 6 1 ) 的意义是很明显的。例如取6 = 芝1 ，则有 ，= c 魏修 、 毛 c r j = 1 j 知 j 这说明只有明显大于其它值的已对应的训练点才被认为存在较大的人为误 差易知，6 ( 0 万 1 ) 取值越大时，被认为存在较大人为误差的判别条件越苛 刻。因此，用这样的集合来改造c s y m 会得到较好的效果 定义函数 i 1 一，、i h z ) = ( 1 l- ( z - 6 ie 活1 当6 j 矗时，认为相应的训练点受人为误差的影响不是很大；当 i = 1 z 矗6 已时，6 可能不是很小，即人为误差对该训练点的影响可能会很大 i = 1 ff 目标函数中的矗会很大，为使错划程度矗尽可能的小，引入 悠) ，使相 i = 1i = l f 应的6 ( 射较已要小，以此达到减小错划程度6 的目的 得到基于函数h ( z ) 的改进c s y m 算法的模型如下： 呼扣1 1 2 + c 已九( 已) 比，：如：i=囊11 ( ，) ， i = 1 定义3 3 2 ( 错误率o r ) ：当对一个近似线性可分的训练集进行分类时，分类 发生错误的百分比定义为错误率，记作o r 。 1 3 & & ，斟。：l f o 6 z z 基于人为误芳的支持向量机 命题3 3 2 1 ：( i ) 若，= 0 ，则；h ( z ) = 1 ； ( i i ) r 仍，g a e s v m 仃e s v m 证明：( i ) 若，= o ，即已 6 已+ a t = 1 f q x ( z ) 一q x ( 5 6 一a ) l i m t 型一= 0 ， i ：一p i 靠一a ) 一 一( 6 已一a ) = 1 z 、，一一 l = l f 纵( 名) 一q x ( 5 已一a ) 区( 6 已一ato ) = l i m 产l = 0 仁1 z - - ( 6 量矗一a ) + z 一( 6 已一a ) l = 1 l 所以以( 6 t = l l 已一a ) 存在，且以( j 矗 i = l f 同理可证q i ( 6 已+ a ) 存在， i = 1 一a 1 =l i m f ：一( 6 矗一