（管理科学与工程专业论文）求解分类问题的支持向量机方法与应用研究.pdf

摘要 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，简称s v m s ) 是基于统计学习理论，借助最优化方法 来解决机器学习问题的新工具它是c o r t e s 和v a p n i k 于1 9 9 5 年首先提出来的，已成为近年来 机器学习研究的一项重大成果目前对支持向量机的研究主要集中在对其本身性质的研究和完善 以及加大应用研究的深度和广度两方面本文以解决分类问题为目标，对支持向量分类机从其理 论和模型的完善及应用两个方面，进行了较深入的研究和实践，以达到理论和实践的结合 本文的主要研究工作如下： 1 在深入研究现有支持向量分类机和支持向量回归机的基础上，把分类问题看作特殊的回 归问题来处理，通过引入不同的范数以及不同的损失函数，构建求解分类问题的支持向量回归机 新模型并对引入高斯损失函数得到的新模型，给出求解的简便方法一简化的序列最小最优化算 法进一步，对多类分类问题，提出了新的多类分类模型，数值试验表明了该模型的鲁棒性和有效 性从而给出求解分类问题的支持向量机的新思路和新途径 2 f u n g 和m a n g a s a r i a n 从直观上提出了中心支持向量分类机，本文通过理论推导和分析构造 出中心支持向量分类机的原始优化阿题，从不同的途径给出了中心支持向量分类机在此基础上， 酋次给出了稀疏的中心支持向量分类机、加权的中心支持向量分类机对含有不确定信息的分类 问题，通过引入概率变量，构建了不确定中心支持向量分类机从而实现对中心支持向量分类机理 论的推广、完善和创新 3 v a p n i k 提出了推理型支持向量分类机，其优化问题的求解比较困难本文将其原始最优化 问题变为无约束问题。并对其进行光滑化，从而构建了改进的推理型支持向量机和加权的推理型 支持向量机，并成功的将新模型应用到网络入侵检测中，给出了网络入侵检测的新方法，使推理型 支持向量机的理论和应用研究有了新的突破 4 首次将支持向量分类机应用到海水工厂化养殖中的环境监测问题对河北省唐山市、秦 皇岛市沿海的养殖工厂，随机采集了鱼类生长环境数据，进行了检测、监控实验，取得了较好的应 用效果，在切实解决实际问题的同时，进一步拓宽r 支持向量机的应用领域 本文构建的各种新的支持向量分类机，较一般支持向量分类机有各自明显优势和良好的性能， 主要体现在有的模型有求解的简便算法，有的模型测试精废高，有的模型解决实际问题时针对性 强，这均在数值试验和实际应用中得到证实 关键词： 支持向量分类机，支持向量回归机，中心支持向量机，推理型支持向量机鱼类生 长环境检测 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 e s ( s v m s ) a r en e wd e v e l o p e dm a c h i n el e a r n i n gm e t h o d sb a s e do nt h e f o u n d a t i o n so 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 ) a n do p t i m i z a t i o nt h e o r y t h e ya l ep r o p o s e df i m t l yb y c o r t e sa n dv a p n i ki n1 9 9 5a n dh a v eb e c o m ea ni m p o r t a n tr e s e a r c hd i r e c t i o ni nt h ef i e l do fm a c h i n e l e a r n i n g 1 1 1 i sp a p e rr e s e a r c h e so ns u p p o av e c t o rc l a s s i f i c a t i o n ( s v c ) i nt h e o r ya n dm o d e li no r d e rt o s 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 sa r em a i nw o r k s ： 1 d e a lw i t hc l a s s i f i c a t i o np r o b l e ma ss p e c i a lr e g r e s s i o np r o b l e mb a s e do nt h et h e o r yo fs v ca n d s u p p o r tv e c t o rr e g r e s s i o n ( s v g ) 。b yi n t r o d u c i n gd i f f e r e n tn o h n s a n dd i f f e r e n tl o s sf u n c t i o n s ，an e w s v rm o d e ls o l v i n gc l a s s i f i c a t i o np r o b l e mi sc o n s t r u c t e d f o rt h ec a s eo fg a u s sl o s sf u n c t i o ni m p l i e d ，a s i m p l es o l v i n gm e t h o d - - c o n c i s es e q u e n t i a lm i n i m a lo p t i m i z a t i o n ( s m o ) a l g o r i t h mi sp r o p o s e d f u r t h e r m o r e ，f o rm u l t i - c l a s sp r o b l e man e wc l a s s i f i c a t i o ns v ra l g o r i t h m k - s v ri sc o n s t r u c t e d ，a n d e x p e r i m e n t ss h o wt h em o d e l sr o b u s t n e s sa n de f f i c i e n c y , t h e r e f o r ew eg i v eo u tn e wi d e 女a n dm e t h o do f s o l v i n gc l a s s i f i c a t i o np r o b l e m 2 f o rt h ep r o x i m a ls u p p o r tv e c t o rm a c h i n ef o rc l a s s i f i c a t i o no s v m op r o p o s e di n t u i t i v e l yb y f u n ga n dm a n g a s a r i a n ，w eg e ti t sp r i m a lp r o b l e mb yt h e o r e t i c a ld e d u c t i o ns ot h a tc o n s t r u c tt h ep s v m c b yd i f f e r e n tw a y a n do nt h i sb a s e , w ep r o p o s es p a r s ep s v v l ca n dw e i g h t e dp s v m c f i r s tt i m e f o rt h e c l a s s i f i c a t i o np r o b l e mw i t hu n c e r t a i ni n f o r m a t i o n w ec o n s t r u c tu n c e r t a i np s v m cb yi n t r o d u c i n g p r o b a b i l i t yi n v a r i a b l e t h e r e f o r ew eg e n e r a l i z ea n dd e v e l o pt h et h e o r ya n da l g o r i t h mo fp s v m c 3 v a p n i kp r o p o s e dt h et r a n s d u c f i v es u p p o r tv e c t o rm a c h i n ef r s v m ) , t h eo p t i m i z a t i o np r o b l e mi n i ti sd i f f i c u l tt os o l v eb e c a u s eo fi t ss p e c i a l p r o p e r t y w ec o n s t r u c ti m p r o v e dt s v mb yt r a n s f o r mt h e c o n s t r a i n e dp r o b l e mi n 璐v mt ou n c o n s t r a i n e dp r o b l e ma n ds m o o t hi t f u r t h e r m o r e , w e i g h t e dt s v m i sa l s op r o p o s e di no r d e rt os o l v er e a lp r o b l e mw i t hu n b a l a n c e dt r a i n i n gp o i n t s t h en e wm o d e l c o n s t r u c t e di sa p p l i e di n t od e t e c t i o no f w e bi n t r u s i o ns u c c e s s f u l l y t h e r e f o r e ，t h et h e o r ya n da p p l i c a t i o n o f t s v ma r eb o t hi m p r o v e d 4 a p p l ys v ci n t oe n v i r o n m e n ts u p e r v i s ep r o b l e mo fs e a w a t e ri n d u s t r i a l i z a t i o nb r e e da q u a t i c s f i r s tt i m e a f t e rc o l l e c tl i v i n ge n v i r o n m e n td a t ao ff i s hr a n d o m l yi ni n d u s t r i o ft a n g s h a nd t ya n d q i n g h u a n g d a oc i t yo fh e b a ip r o v i n c e 。w ed ol o t so fd e t e c t i n ga n dm o n i t o r i n ge x p e r i m e n t sb ys v ca n d g e tt h ec o r r e s p o n d i n gr e s u l t s , w h i c hs h o wt h a tt h ea p p l i c a t i o ni ss u c c e s s f u la n dm e a n i n g f u l t h e r e f o r e ， w i t hs o l v i n gt h er e a lw o r l dp r o b l e m , w ee x t e n dt h ef i e l do f s v ma p p l i c a t i o n s t h en e ws v mm o d e l sc o n s t r u c t e di nt h i sp a p e rh a v et h e i ro b v i o u sp r i o r i t yt h a ns t a n d a r ds v m , s o m eh a sm o r es i m p l es o l v i n gm e t h o d ，s o m eh a sm o r eh i g ht e s t i n gp r e c j s i o n 。a n ds o m ed e a l sw i t hr e a l w o r l dp r o b l e me f f e c t i v e l y , a i lo f w h i c ha r ep r o v e di ne x p e r i m e n t sa n dr e a la p p l i c a t i o n s k e yw o r d s ：s u p p o r tv e c t o rc l a s s i f i c a t i o n ，s u p p o r tv e c t o rr e g r e s s i n n ，p r o x i m a ls u p p o r tv e c t o r m a c h i n e ，t t a n s d u c t i v es u p p o r tv e c t o rm a c h i n e 。e n v i r o n m e n ts u p e r v i s eo fh s h n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得中国农业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：阍i 为岛时间：2 一j 年g 月2 4 日 关于论文使用授权的说明 本人完全了解中国农业大学有关保留、使用学位论文的规定，即 学校有权 保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。同意中国农业大学可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 阁躲 时间：拍卜年月吩日 导师签名：种侈扬 时间：姚年g 月如日 第一章绪论 分类问题是现实生活中普遍存在的问题分类的作用和根本且的在于面对某一具体事物时将 其正确地归于某一类，然后用同一种方法去处理同一类中的不同事物将某一事物正确归入某一 类的方法即分类方法，研究分类方法首先要确定分类标准，而对任何事物都不存在纯客观的分类 标准，任何分类都带有主观性，因此，对不同的分类标准会产生不同的分类方法目前已有各种各 样的分类方法，如人工神经网络，贝叶斯决策、决策树等等，本文将要研究的是分类问题的新方法 ，即支持向量机方法 支持向量机( 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 9 9 5 年首先提出来的【l 】，已成为近年来机器学习研究的一项重大成果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 gt h e o r y , s l t ) 2 一【4 l 对有限样本情况下模式识别 中的一些根本性i 司题进行了系统的理论研究，很大程度上解决了模型选择与过学习问题、非线性 和维数灾难问题、局部极小点等问题，支持向量机正是在这一理论基础上发展起来的与传统的 人工抻经网络相比。支持向量机不仅结构简单，两且各种技术性能尤其是泛化( g e n e r a l i z a t i o n ) 能 力明显提高，这已被大量实验证实【5 】近年来，对s v m 的研究主要集中在对s v m 本身性质的研 究和完善以及加大s v m 应用研究的深度和广度两方面。到目前为止，支持向量机已应用于模式分 类、回好分析、函数估计等领域，并已成功应用到手写阿拉伯数字识别【i 】、文本自动分类【6 、 说话人识别【7 】、人脸检测【8 l f 9 】、性别分类【1 0 】、计算机入侵检测( 1 1 】、生物信息技术f 1 2 1 、遥 感图象分析【i3 】、目标识别【1 4 等诸多实际问题中本章首先介绍机器学习，统计学习理论的一 些基本内容和支持向量机的基本思想，然后详细讨论支持向量机的研究现状，最后对本文的主要 研究工作和结论进行概述 1 1 机器学习 在人们对机器智能的研究中，希望能够用机器来模拟人从实例学习的能力，这就是我们所说 的基于数据的机器学习问题【2 1 ，或者简单地称作机器学习问题机器学习是现代智能技术中的重 要方面，研究从观测数据( 样本) 出发寻找规律，利用这些规律对未来数据或无法观测的数据进行 预测包括模式识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是缝计学传 统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设但在现 实问题中，、我们所面对的样本数日通常是有限的，有时还十分有限因此一些理论上很优秀的学 习方法实际中表现却可能不尽人意( 比如表现出很差的推广能力) 与传统统计学相比，统计学习 理论是一种专门研究小样本情况下机器学习规律的理论，它是建立在一套较坚实的理论基础之上 的，为解决有限样本学习问题提供了一个统一的框架它能将很多现有方法纳入其中，有望帮助 解决许多原来难以解决的问题( 比如神经网络结构选择问题、局部投小点问题等) ；同时，在这一理 论基础上发展出来的新的通用学习方法一支持向昔机巳初步表现出很多优于巳有方法的性能 v v a p n i k 等人从上世纪六、七十年代开始致力于此方面研究【2 】，到九十年代中期，随着其理论的 不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展统计学习理论开始受到 越来越广泛的重视一些学者认为，s l t 和s v m 正在成为继神经网络研究之后新的研究热点， 并将有力地推动机器学习理论和技术的发展 1 1 1 机器学习的主要问题 机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够 对未知输出作出尽可能准确的预测可以一般地表示为：变量y 与2 存在一定的未知依赖关系， 即遵循某一未知的联合概率f 0 ，9 ) ，如和p 之间的确定性关系可以看作是其特例) ，机器学习问题 就是根据n 个独立同分布观测样本 仕1 ，”1 ) ，( 却，妇) ，一，( 卸，们) 其中z t ：( 扛小，k l 。) 7 月”，鼽五，i = 1 ，z ，在一组函数t ，忙，) 中寻求一个最优的函 数，( 毛撕) 对依赖关系进行估计，使期望风险 ， r ( ) = l ( u ，扛，) ) d f 恤，) ( 1 - 2 ) j 最小其中， ，( ) ) 称作预测函数集，为函数的广义参数， ，( z ，t ，) ) 可以表示任何函数集； 白，( $ ，w 1 ) 为由于用，( $ ，) 对进行预测而造成的损失，我们称它为损失函数它是评价预测 准确程度的一种度量不同类型的学习问题有不同形式的损失函数预测函数也称作学习函数、 学习模型或学习机器 有三类基本的机器学习问题，即模式识别( 分类同题) 、函数逼近和概率密度估计对模式识 别问题，输出y 是类别标号，两类情况下y = f 0 ，1 j 或 l ，- 1 ，预测函数称作指示函数，损失函数 可以定义为 地州删肛r 羚嬲： m s ， 使风险最小就是b a y e s 决策中使错误率最小在函数逼近问题中，”是连续变量( 这里假设为单值 函数) ，损失函数可定义为 l ( ，缸，t ，) ) = ( y 一( x ，”) ) 2 ，( 1 - - 4 ) 即采用最小平方误差准则而对概率密度估计同题，学习的目的是根据训练样本确定z 的概率密 度记估计的密度函数为“z ， ) ，则损失函数可以定义为 l 扫( z ，t o ) ) = 一i o g p ( x ，) ( 1 - 5 ) 1 1 2 经验风险最小化 在上面的问题表述中，学习的目标在于使期望风险最小化，而联合分布f ( ”) 是未知的，所 以我们可以利用的信息只有样本( 卜1 ) ，式( 卜2 ) 的期望风险并无法计算和最小化，因此传统的学 习方法中采用了所谓经验风险最小化f e r m ) 准掰，即用样本定义经验风险 d 。) ：；壹l ( y i , f ( z l , w ) ) ， ( 16 ) 式( 1 - 6 ) 作为对式( 1 2 ) 的估计，设计学习算法使它最小化。对损失函数( 1 - 3 ) ，经验风险就是训 练样本错误率；对式( 卜4 ) 的损失函数，经验风险就是平方训练误差；而采用式( 1 - 5 ) 损失函数的 e r m 准则就等价于最大似然方法事实上，用e r m 准则代替期望风险最小亿并没有理论上的保 证，只是直观上合理的想法，但这种思想却在多年的机器学习方法研究中占据了主要地位人们 多年来将大部分注意力集中到如何更好地最小化经验风险上，而实际上，即使可以假定当f 趋向 于无穷大时式( 1 - 岳) 趋近于式( 1 - 2 ) ，在很多问题中的样本数目也离无穷大相去甚远那么在有限 样本下e r m 准则得到的结果能使真实风险也较小吗? 1 1 3 复杂性与推广能力 e r m 准则不成功的一个例予是神经网络的过学习问题最初，很多注意力都集中在如何使 或。，) 更小，但很快就发现，洲练误差小并不总能导致好的预测效果某些情况下，训练误差 过小反而会导致推广能力( 学习机器对未来输出进行正确预测的能力) 的下降，即真实风险的增 加，这就是过学习问题之所以出现过学习现象，一是因为样本不充分，二是学习机器设计不合 理，这两个问题是互相关联的设想一个简单的例子，假设有一组实数样本 霉，v ) ，取值在l o l l l 之间，那么不论样本是依据什么模型产生的，只要用函数f ( x ，a ) = s i i l ( a z ) 去拟合它们( n 是待定 参数) ，总能够找到一个a 使训练误差为零，但显然得到的。最优”函数并不能正确代表真实的函 数模型究其原因，是试图用一个十分复杂的模型去拟合有限的样本，导致丧失了推广能力在 神经网络中，若对有限的样本来说网络学习能力过强，足以记住每个样本，此时经验风险很快就 可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预测学习机器的复杂性与 推广性之间的这种矛盾同样可以在其它学习方法中看到文献1 1 6 】给出了一个实验饲子，在有噪 声条件下用模型f = 护产生1 0 个样本，分别用个一次函数和一个二次函数根据e r m 厦c 剐去 拟合，结果显示，虽然真实模型是二次，但由于样本数有限且受噪声的影响，用一次函数预测的结 果更好同样的实验进行了1 0 0 次，7 1 的结果是一次拟合好于二次拟台由此可看出，有限样 本情况下， 1 ) 经验风险最小并不一定意味着期望风险最小；2 ) 学习机器的复杂性不但应与所研 究的系统有关，而且要和有限数目的样本相适应我们需要一种能够指导我们在小样本情况下建 立有效的学习和推广方法的理论 1 2 统计学习理论 统计学习理论就是研究小样本统计估计和预测的理论，它从理论上给出了e r m 原则成立的 条件，有限样本情况下经验风险与期望风险的关系等问题主要内容包括四个方面【2 1 ： 1 ) 经验风险最小化准则下统计学习一致性的条件； 3 2 ) 在这些条件下关于统计学习方法推广性的界的结论i 3 ) 在这些界的基础上建立的小样本归纳推理准则； 4 ) 实现新的准则的实际方法( 算法) 这里学习的一致性就是当训练样本数目趋于无穷大时，经验风险的最优值能够收敛到真实风险的 最优值， 1 ) 一4 ) 中最有指导性的理论结果是推广性的界，与此相关的一个核心概念是v c 维 1 2 1v c 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性 能的指标，其中最重要的是v c 维( v 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 维的直观定义是；对一个指示函数集，如果存在1 个样本能够被函数集中的函数按所有可能的寥 种形式分开，则称函数集能够把z 个样本打散；函数集的v c 维就是它熊打散的最大样本数目f 若对任意数目的样本都有函数能将它们打散，则函数集的v c 维是无穷大有界实函数的v c 维 可以通过用一定的阚值将它转化成指示函数来定义 由v c 维的直观定义可知，的v c 维就是它能打散的爿中的点的最大个数即若存在1 个 点组成的集合局能被，打散，且任意z + 1 个点的集合西+ 1 不能被，打散，则，的v c 维就是 j ；若任给正整数l ，都存在1 个点组成的集合五能被，打散，则，的v c 维就是o 。例如函数集 合 ，= ，( z ，a ) = s g n ( s i n ( a x ) ) ，n r ) ( 1 7 ) 的v c 维就是o o ， v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 遗憾的是，目前 尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知道其v c 维比如在n 维实数空间中线性分类器和线性实函数的v c 维是n + 1 ，对于一些比较复杂的学习机器( 如神经 网络) ，其v c 维除了与函数集( 神经网结构) 有关外，还受学习算法等的影响，其确定更加困难 对于给定的学习函数集，如何( 用理论或实验的方法) 计算其v c 维是当前统计学习理论中有待研 究的一个问题( 17 】 1 2 2 推广性的界 统计学习理论系统地研究丁对于各种类型的函数集，经验风险和实际风险之间的关系，即推 广性的界 2 】关于两类分类问题的结论是一对指示函数集中的所有函数( 包括使经验风险最小的函 数) ，经验风险冗c m ，( ”) 和实际风险r ( w ) 之间以至少1 一q 的概率满足如下关系【1 8 1 ： r ( ”) s 冗。，( ”) + 1 垒q 兰尘兰! _ 专! ! = ：生盟， ( 1 8 ) 其中 是函数集的v c 维，z 是样本数这说明学习机器的实际风险是由两部分控制的：一部分 是经验风险( 训练误整) ，另一部分称作置信范围，它和学习机器的v c 维及训练样本数有关可以 简单地表示为 冗( 叫) 冗e m p ( 钟) + 西( f ) ， ( 1 - 9 ) 上式表明，在有限训练样本下学习机器的v c 维越高( 复杂性越高) 则置信范围越大，导致真实 风险与经验风险之间可能的差别越大这就是为什么会出现过学习现象的原因机器学习过程不 仅要使经验风险最小，还要使v c 维尽量小，从而缩小置信范围，这样才能取得较小的实际风险。 即对未来样本有较好的推广性需要指出，推广性的界是对于最坏情况的结论，在很多情况下是 较橙的，尤其当v c 维较高时更是如此( 文献f 1 8 】指出当h n 0 3 7 时这个界肯定是松弛的。当 v c 维无穷大时这个界就不再成立) 而且，这种界只在对同一类学习函数进行比较时有效，可以指 导我们从函数集中选择最优的函数，在不同函数集之间比较却不一定成立v a p i k 指出【2 1 ，寻找 更好地反映学习机器能力的参数和得到更紧的界是学习理论今后的研究方向之一 1 2 3 结构风险最小化 从上面的结论看到，e r m 原则在样本有限时是不舍理的，我们器要同时最小化经验风险和 置信范围事实上，在传统方法中，选择学习模型和算法的过程就是调整置僖范围的过程，如果模 型比较适合现有的胡f 练样本( 相当于h n 值适当) ，则可以取得比较好的效果但因为缺乏理论指 导，这种选择只能依赖先验知识和经验，造成了如神经网络等方法对使用者。技巧”的过分依赖 统计学习理论提出了一种新的策略，即把函数集构造为一个函数子集序列，使各个子集按照 v c 维的大小( 亦即圣的大小) 排列；在每个子集中寻找最小经验风险，在子集间折衷考虑经验风 险和置信范围，使之达到实际风险的最小如图1 1 所示- 失掌毒 过，哥 叠盘鲁子i s - c o c 她 v c 堆；屯 t i 圈1 1 结构风险最小化 这种思想称作结构风险最小化( 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 准则统计学习理论 还给出了合理的函数子集结构应满足的条件及在s r m 准则下实际风险收敛的性质f 2 1 实现s r m 原则可以有两种思路，一是在每个子集中求最小经验风险，然后选择使最小经验风 险和置信范围之和最小的子集显然这种方法比较费时，当子集数目很大甚至是无穷时不可行， 因此有第二种思路，即设计函数集的某种结构使每个子集中都能取得最小的经验风险( 如使训练误 差为o ) ，然后其需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就足最 5 优函数支持向量机方法实际上就是这种思想的具体实瑷文献1 1 6 j 中讨论了一些函数子集结梅 的例子和如何根据s r m 准则对某些传统方法进行改进的问题 1 3支持向量机基本思想 在第二节中我们介绍了统计学习理论的前三部分事实上，这些内容是其理论部分，而要发 挥理论在实际问题中的作用，即实现这些理论思想是由它的第四部分完成的支持向量机正是实 现这些新思想的具体方法支持向最机( s u p p o r tv e c t o rm a c h i n e ) 简称s v m ，是统计学习理论中最 年轻的内容，也是最实用的部分其核心内容是在1 9 9 2 到1 9 9 5 年间提出的 1 1 9 1 2 0 ，目前仍处 在不断发展阶段 1 3 1 最大间隔分类超平面 我们以分类问题为例说明s v m 的基本思想 2 1 2 3 2 4 用数学语亩可以把分类问题描述如 下： 分类问题根据给定的训练集t = ( z l ，y 1 ) ，鲫) ) y ) 。，其中戤省= r n , 虮 y = 1 ，一1 ) ，t = 1 ，z ，寻找z = 屁”上的一个实值函数9 ( z ) ，以便用决策函数 ，( z ) = s g n ( g ( 。) ) ， ( i - 1 0 ) 推断任一模式$ 相对应的y 值由此可见，求解分类问题，实质上就是找到一个把r ”上的点分 成两部分的规则 s v m 是从线性可分的分类问题的最优分类面发展而来的，其基本思想可用图1 2 的两维情况 说明 h 围1 2 最大间隔分类超平面 图中实心点和空心点代表两类样本，耳为分类线，h ，h z 分别为过两类中离分类线最近的 样本且平行于分类线的寅线，它们之间的距离叫做分类闻隔( m a r g i n ) 所谓最大间隔分类线就是 它不但能将两类正确分开f 训练错误率为o ) ，而且使分类间隔最大，分类线方程为 在n 维空间中，不失一般性，可以对它进行规范化，使得对线性可分的样本集 t = ( 研，矾) ，。，( 魏，驰) ，其中戤r “，鼽 + l ，一1 ) ，( i - 1 2 ) 满足 敬f ( 搿。甄) 十珂一1 三o ， = 1 ，7 f l 一1 3 ) 容易计算分类间隔等于研2 ，使闰隔最大等价子使掣最小满足条件( 1 1 3 ) 且使掣最小的 分类面就叫做最优分类面，脯，z 如上的训练样本点就称作支持向量 1 3 2最大间隔与结构风险最小的等价性 使分类间隔最大实际上就是对推广能力的控制，这是s v m 的核心思想之一统计学习理论指 出【1 1 ，在维空间中，设样本分布在一个半径为冗的超球范围内，则满足条件 训is a( i - 1 4 ) 的超平面$ ) + b = 0 构成的指示函数集 ，扛，”，”= 8 9 n ( ( $ ) + 砷)( i - i 5 ) 的v c 维满足 h 墨m m ( 妒a 2 】，v ) + 1 ， ( 1 - 1 6 ) 因此使掣最小就是使v c 维的上界最小，从而实现s r m 准则中对函数复杂性的选择 当满足条件( 卜1 4 ) 时，训练集中的每一点到规范的分类超平面的距离为 d ( ”，6 ，甄) = 掣万1 ，( 1 - 1 7 ) 由此可觅超平面离任何点z 。的距离都不能比 小，从图1 3 可以看出它是如何减少可能的超平 面的数量的，因而也减少了函数集的容量 1 3 3 对偶问题 由1 3 1 的讨论可知，寻求最优分类超平面，就是要求解最优化问题 鼍警r 舢) = 扣酬2 ， 8 t 玑( ( w ) + 6 ) 1 ，i = 1 ， 根据l a g r a n g e 乘子法转化为求下面l a g r a n g e 函数的鞍点过程 ， l ( 叫，b ，n ) = ；ij 圳| | 2 一o i ( 班( ( 埘- 鳓) + 6 ) 一1 ) ， ( 1 - 1 8 ) ( 1 一1 9 ) 圉1 3 其中n = ( n l i 一，q 1 ) 7 磕为拉格朗日乘子先求拉格朗日函数关于 ，6 的极小由极值条件 得到 v b l ( w ，b ，d ) = 0 ，v 。l ( w ，b ，q ) = 0 把式( 1 2 2 ) 代入拉格朗日函数( 1 - 2 0 ) ，并利用式( 1 - 2 3 ) ，即得到对偶问题为 警一；壹i = l 圭j = l 螂啪出t s t 蚋产o ， a l 0 ，i = 1 ，一，z ( 1 2 1 ) ( 1 2 2 ) ( 1 - 2 3 ) ( 1 2 4 ) ( 1 2 5 ) ( 1 - 2 6 ) 问题( 1 2 4 ) 一( 1 2 s ) 是个不等式约束t - - - 次函数寻优的同题，显然它存在唯一解容易证明， 解中将只有一部分( 通常是少部分) n ，不为零，不为零的啦对应的样本就是支持向量求出问题 ( 1 - 2 4 ) 一( 1 - 2 6 ) 的最优解矿，就可以得到最优分划超平面 ( - z ) + 矿= 0 ， 其中 l ”+ = n 孙 b + ：一；( ( 。+ ) + ( 。一) ) + = 一；( ( 叫z + ) + f 叫+ - 茁一) ) 而。+ ，z 一是满足下列条件的支持向量 n ： 0 ，n 二 0 ，+ = 1 ，y 一= 一1 o = n y 。_l z 茸 盘 。 | | m 吩 。芦 + 即 盯 勰 1 l 1 l 最后得到的最优分类函数是 l ，( z ) = s g n ( ( w + z ) + 矿) = s g n ( 2 0 ；蹦戤z ) 十矿) f l 一3 1 ) t = 1 从上述结论可以推导出 i l w l l 2 = ( n 孙戤) 2 其中s v 为支持向量的下标集合，这时函数集的v c 维满足 h 兰m i n r 2 q ；，n ) + 1 i s y ( 1 3 2 ) ( 1 3 3 ) 对于线性不可分的| 可题求晟优分类超平面，【1 引入了非负变量f 和惩罚函数 l 乃( ) = 器， ( 1 3 4 ) i = l 其中是对错分误差的度量一般的口取为1 或2 ，当取1 时，即是在条件( 1 - 1 9 ) 中增加一个松 弛项6 兰0 ，成为 挑( 【埘蚴) + 6 ) 一1 + 靠0 ，i = 1 - 一，f( 1 3 5 ) 将目标函数( 1 - 1 8 ) 改为 r ( t j ，) = 加训1 2 + c 6 ( 1 3 6 ) 一 i = 1 即折衷考虑最少错分样本和最大分类间隔，就会得到广义最优分类面其中，c 0 是个常数， 它控制对错分样本惩罚的程度广义最优分类面的对偶问题与线性可分情况下几乎完全相同，其 具体形式为 1ll 哮 i 圣玑蜥n 嘶( 即) 一萎q ， ( 1 - 3 7 ) t = lj = l j = l 最后得到的最优分类函数是 ( 1 3 8 ) 0 o ci = 1 ，f ( 1 - 3 9 ) l ，( ) = s g n cc w - z ) + 矿) = s g n ( o 洲”z ) + ”0 - 4 0 ) i = 1 1 3 4 支持向量机算法 对于n 维空间中的线性函数，其v c 维为n + l ，但根据式( 1 - 3 3 ) 的结论，在1 1 w l i a 的约束 下其v c 维可能大大减小，即使在维数很高的空闻中也可以得到较小v c 维的函数集，以保证有 9 o 刚 i i ， o 1 i 。 t8 中国农业大学博士学位沦文第一章绪沦 较好的推广性同时我们看到，通过把原问题转化为对偶问题，计算的复杂度不再取决于空间维 数，而是取决于样本数，尤其是样本中的支持向基数这些特点使有效地解决高维问题成为可能 对非线性问题，s v m 把输入戤，i = 1 ，l 通过某个非线性变换圣( - ) 映射刭某个高维空间中 的向量圣( 戤) ，i = 1 ，f ，把非线性问题转化为在该高维空间中的线性问题，然后在这个高维空间 中求最优分类面这种变换可能比较复杂，艘情况下不能明确地知道变换的具体形式。但是我 们注意到，在上面的对偶问题中，不论是对偶问题( 1 - 3 7 ) 一( 1 - 3 9 ) 还是分类函数( 1 4 0 ) 仅涉及训练 样本的内积运算( 露- q ) 这样，在高维空间实际上只需进行内积运算，而这种内积运算是可以用 原空间中的函数实现的，我们甚至没有必要知道变换的形式根据芝函的有关理论，只要一种核 函数k ( x l ，巧) 满足m e r c e r 条件，它就对应某一变换空间中的内积 2 1 1 8 1 因此，在最优分类面中采用适当的内积函数( ，q ) 就可以实现某一非线性变换后的线性分 类，而计算复杂度却没有增加，此时对偶问题( 1 - 3 7 ) 一( 1 3 9 ) 变为 嘎n ；妻妻彬 s t 舭f 0 0 n ，s ci = 1 ，t ，f ( 1 _ 4 1 ) ( 1 4 2 ) ( 1 4 3 ) 相应的分类函数变为 m ) = s g n ( n ；玑( 口) + 峨( 1 - 4 4 ) t = l 其中 1 f 矿= 一；a 训k ( z + ) + k ( $ 一) ) ( 1 - 4 5 ) t = 1 概括地说，构造式( 1 “) 所示的决策函数的学习机器叫做支持向量机它是首先通过用内积函数 定义的非线性变换将输入空间变换到一个高缎空间，然后在这个高维空间中构造最优分类超平面。 1 3 5 核函数 核函数把高维空间中两个点的内积运算，用原来输入空间中的两个模式的简单函数的求值来 代替，从而解决了维数灾难问题其计算量只依赖于训练样本的数目，但要在高维空间中得到一个 样本的比较均匀的分布，仍需要提供大量的样本 定义1 3 1 核函数( 接或正定核) f 2 1 】设爿是j p 中的一个子集称定义在z z 上的函数 k ( x ，一) 是核函数( 或正定核或核) ，如果存在着从z 到某一个h i l b e r t 空间咒的映射， 圣：爿。+ 7 ， ( 1 q 6 ) z 卜圣扛) 使得 k ( 。，一) = 仲( z ) 西( 。，( 卜4 7 ) l u 。 其中( ，) 表示w 中的内积 而m e r c e r 定理给出了一个彤z 上连续实值对称函数对应某一个空间的内积的条件 2 1 】，即 核函数的等价条件 定理1 3 2 ( m e r c e r 定理) 令戈是j p 上的一个紧集，k 是爿z 上的连续实值对称涵 数则 k ( x ，一) ，p ) ，( 一) d x d x 0 ，v ，e 工2 ( z ) ，( 1 - 4 8 ) j x x 疋 等价于k ( - ，) 可表示为只x z 上的一致收敛序列 0 0 ( $ ) = 丸仇o ) 讥( ) t = l ( 1 4 9 ) 其中 0 是强的特征值，讥工2 ) 是对应九的特征函数( i 忆，= 1 ) 它也等价于g ( x ，一) 是一个核函数； 耳( z ，) = ( 垂( z ) - 垂( 一) ) 其中 壬：肌：舻- k 1 2 # 卜( x 劫( z ) ，移西2 ( z ) ，) 7 而( ) 是h i l b e r t 空间f 2 上的内积 下面给出一些常用的核函数； 1 ) 多项式核： 耳( $ ，z ) = 忙嚣) 4 ，d = 1 ，2 ， ( z ，z ) = ( p - 一) + 1 ) 4 ，d = 1 ，2 ， 2 ) 高斯径向基核 脚) = 酬一訾华) 3 ) 多层感知器，又称s i g m o i d 核 ( z ，一) = t a n h ( k ( x z 7 ) + u ) 其中k 0 ，” o ，( 1 - 5 7 ) i o z 墨o 更复杂的核函数可以通过一些运