（计算机科学与技术专业论文）非理想状态下支持向量机学习算法的研究.pdf

浙江大学博士学位论文 摘要 摘要 作为上世纪九十年代兴起的一种新的机器学习技术，支持向量机 ( s u p p o r t v e c t o r m a c h i n e ，s v m ) 在许多领域都取得了成功的应用。但它的应用 其实大多局限于常见的标准化或者说“理想化”的数据分布情况，对于在实 际应用中不得不面对的一些数据分布不合常规或者说不“理想”的机器学习 问题，比如：不确定性输入信息学习、不平衡数据集分类、半监督型数据学习 等，传统型支持向量机的学习性能则表现得不尽人意，有时甚至根本达不到 人们所期望的学习效果，这在很大程度上影响了支持向量机向更大范围的推 广和应用。针对这些问题，本文就几种非理想状态下的支持向量机学习算法 进行了研究和探讨，给出了较理想的解决方案。 在简单回顾标准支持向量机及其数学基础之后，本文重点研究了三类非 理想状态问题的支持向量机学习算法。 针对某些训练样本存在输入信息不确定的问题，通过引入灰色理论中区 间数及区间运算的概念，结合支持向量机的特性，提出了解决不确定信息的 灰信息支持向量机分类及回归算法。该类算法用区间数来表示不确定的输入 信息，利用区间运算来替代原来学习函数中的运算，并根据区间运算结果来对 信息不确定的输入模式进行学习。同时借鉴灰色理论中区问距离的思想，文 中还提出了解决单值分类问题的的灰信息支持向量域分类算法( g r a ys u p p o r t v e c t o rd o m a i nd e s c r i p t i o n ，g s v d d ) 针对不同类别样本在数量分布上存在差异的不平衡数据问题，本文研究 了不平衡状态下实际分类面和数据不平衡度的关系，通过采用一种新的上抽 样技术( o v e r s a m p l i n g ) s m o t e 来纠正实际分类面形状偏离理想分类 面的现象；同时还对传统支持向量机的惩罚函数进行了调整，引入了差异性 惩罚的思想来纠正传统算法中的分类面偏移现象。 在s v m 的实际应用中由于样本采集的困难以及采样成本的代价过高， 在给定的数据集中往往存在部分没有被标识的样本，这类问题称之为半监督 型学习( s e m i s u p e r v i s e dl e a r n i n g ) 问题。本文针对j o a c h i m s t 提出的解决半 监督型学习问题的直推式支持向量机学习算法( t r a n s d u c t i v es u p p o r tv e c t o r 浙江大学博士学位论文摘要 m a c h i n e ，t s v m ) 存在的诸如训练速度慢、泛化能力弱等一些缺点，提出 一种改进的直推式支持向量机分类学习算法。该算法通过采用个体样本标号 判断和交换准则取代t s v m 算法中的成对样本标标号交换法，能正确确定无 标识样本中的正标识样本数，克服了传统t s v m 算法存在的缺点，增强了 t s v m 算法学习算法的推广能力。 作者还对论文中提出的几种非理想状态支持向量机学习算法进行了实验 验证，结果表明这些算法在非理想状态下学习问题中均取得了较好的学习性 能。 关键词支持向量机、分类、回归、不确定信息、不平衡数据、直推式学习 浙江大学博士学位论文 a b 目 r c t a b s t r a c t a so n ek i n do f n e wm a c h i n el e a r n i n gt e c h n o l o g yr o s ei nt h ee a r l y1 9 9 0 s ， s u p p o r tv e c t o rm a c h i n e ( s v m ) h a sb e e ne x t e n s i v e l ys t u d i e da n dh a ss h o w n r e m a r k a b l es u c c e s si nm a n ya p p l i c a t i o n s h o w e v e r , t h es u c c e s so fs v mi s o n l yl i m i t e di ns t a n d a r do ri d e a ld a t ad i s t r i b u t i o ns t a t u s ，w h e nf a c e dw i t h n o n - i d e a lo r e x c e p t i o n d a t ad i s t r i b u t i o n c a s e s ，t h ec l a s s i c a ls v m p e r f o r m a n c e dd i s s a t i s f a c t o r y , a n dc a n n tm e e tt h ee x p e c t e dl e a r n i n gd e m a n d s w h i c hi n f l u e n c e dt h es v m sf u r t h e re x t e n s i o na n da p p l i c a t i o ni na g r e a te x t e n t i nt h el i g h to ft h e s ep r o b l e m so fs v m ，i nt h i sp a p e r , w es t u d ys o m es v m a l g o r i t h m st oc o p ew i t ht h en o n - i d e a ld a t ad i s t r i b u t i o nl e a r n i n gp r o b l e m s ，a n d g i v et h es u i t a b l es o l u t i o n s a f t e rr e v i e w i n gt h es t a n d a r ds u p p o r tv e c t o rm a c h i n ea n di t sm a t h e m a t i c a l f o u n d a t i o n ，w ef i r s t l ys t u d yt h ec l a s s i f i c a t i o na n dr e g r e s s i o na l g o r i t h m so fs v m o nt h es i t u a t i o no fu n c e r t a i n e di n p u ti n f o r m a t i o n t h i sp r o b l e mh a su n i v e r s a l s i g n i f i c a n c ei np r a c t i c a la p p l i c a t i o n s ，d u et ot h el i m i t i o no fs u b j e c t i v ea n d o b j e c t i v ec o n d i t i o n ，w ec a nh a r d l ye n s u r et h a ta l lt h ei n p u ti n f o r m a t i o no f t r a i n n g i n s t a n c e sa r ec l e a ro rp r e c i s e ，o nt h ec o n t a r y , t h e r ea r eo f t e nm i x e du pw i t hs o m e u n c e r t a i n e do r i n c o m p l e t e i n f o r m a t i o ni n s i d et h e t r a i n i n gs a m p l e s b y i n t r o d u c i n gi n t e r v a ln u m b e ra n di n t e r v a la r i t h m e t i ca sw e l la sc o m b i n i n gt h e c h a r a c t e ro fs v m ，w ep r o p o s e dg r a yi n f o r m a t i o ns u p p o r tv e c t o rm a c h i n e c l a s s i f i c a t i o na n dr e g r e s s i o na l g o r i t h mr e s p e c t i v e l y , w h i c hu s e si n t e r v a ln u m b e r t or e p r e s e n tt h eu n c c r t a i n e di n f o r m a t i o n , t r a n s f o r m st h eu n c e r t a i n e di n f o r m a t i o n i n p i tt oi n t e r v a lv e c t o rf o r m ，a n de x t e n d st r a d i t i o n a lo p e r a t i o nt oi n t e r v a l o p e r a t i o n t h eu n e c r t a i n e di n f o r m a t i o ni n p u tp a t t e r na r et h e nh a n d l e da c c o r d i n g t ot h ei n t e r v a lo p e r a t i o no u t p u t w ea l s oa p p l yt h i si d e at oo n e - c l a s ss u p p o r t v e c t o rd o m a i nd e s c r i p t i o n ( s v d d ) a n dg i v et h e g r a yi n f o r m a t i o ns v d d c l a s s i f i c a t i o na l g o r i t h m i no r d e rt os o l v et h i si m b a l a n c ec l a s s i f i c a t i o np r o b l e m ，w ea n a l y s et h e 浙江大学博士学位论文 a b 啦r a e t r e l a t i o nb e t w e e nl e a r n e db o u n d a r ya n dt h ei m b a l a n c eo ft r a i n i n gd a t a s e t ，t h e nw e i n t r o d u c ea no v e r - s a m p l i n gt e c h n o l o g y - - - s m o t et oc o r r e c tt h ed e f o r m e ds h a p e o fl e a r n e db o u n d a r y , m e a n w h i l e w ea l s oa d j u s tt h ep e n a r ym e t h o ds ot h a tl e t s v mg i v ed i f f e r e n tp e n a l t yt op o s r i v ei n s t a n c e sa n dn e g a t i v ei n s t a n c e s c o m p a r e dt oo t h e re x i s tm e t h o d s ，o u ra l g o r i t h mo u t e r f o r mt h e mo np r a c t i c a ! l e a r n i n gp e r f o r m a n c e f o rs e m i s u p e r v i s e dl e a r n i n gp r o b l e m ，j o a c h i m s tp r o p o s e dam e t h o d c a l l e dt r a n s d u c ti v es u p p o r tv e c t o rm a c h i n e 仃s v m ) t od e a lw i t hi t h o w e v e r , t s v mh a so b v i o u sd e f i c i e n c i e s ，f o re x a m p l e s ，i t st r a i n i n gs p e e di ss l o wa n di t s g e n e l i z a t i o np e r f o r m a n c ei s n o ts a t i s f a c t o r y i no r d e rt oo v e r c o m et h e s e s h o r t c o m i n g s w eg i v ean e w 臼a n s d u c t i v e 仃a i m n ga l g o r i t h mb ys u b s t i t u t i n gt h e p a i r - w i s ee x c h a n g ec r i t e r i o nw i t ht h ei n d i v i d u a l l yj u d g e i n ga n dc h a n g i n g c r i t e r i o n e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wm e t h o dr e l e a s et h er e s t r i c t i o no f t h ea p p o i n t e n to ft h en m n b e ro fp o s i t i v es a m p l e sb e f o r e h a n da n di m p r o v et h e a d a p t a b i l i t yo f t h et s v m e x i p e r i m e n t a l r e s u l ss h o wt h ea b o v ep r o p o s e dn o n i d e a ls t a t u ss v m l e a r n i n ga l g o r i t h m sc a no b t a i n e ds a t i s f a c t o r yl e a r n i n gp e r f o r m a n c e k e y w o r d ss u p p o r tv e c t o rm a c h i n e 、c l a s s i f i c a t i o n 、r e g r e s s i o n 、u n c e r t a i n e d i n f o r r n a t i o n 、i m b a l a n c e dd a t a s e t 、t r a n s d u c t i v ei n f e r e n c e 浙江大学博士学位论文目录 图目录 图2 1学习问题的一般模型1 l 图2 2结构风险最小化( s r m ) 示意图1 6 图2 3 线性可分模式最优超平面示意图。 1 7 图2 4 线性不可分最优超平面示意图 2 0 图2 5 非线性可分问题的s v m 实现思想示意图 2 2 图2 6 利用多项式核函数s v m 分类示意图( g = 2 1 2 4 图2 7 占不敏感损失函数示意图2 5 图2 8 松弛回归方法2 6 图2 9s v d d 示意图 2 7 图3 1r b f 函数的区间映射示意图3 8 图3 2 示意性例子分类边界图4 3 图4 1c h e c k e r b o a r d 不平衡数据分类问题示例 6 6 图4 2 不同i m b a l a n c e 条件下s v m 得到的分类线示意图6 7 图4 3 u n d e r - s a m p l i n g 前s v m 求得的实际分类面与理想分类面示意图 7 l 图4 5 不同i m b a l a n c e 下，实际分类面和理想分类面之间的夹角示意图7 4 图4 6 正样本稀疏的情况下，实际分类面和理想分类面示意图 7 6 图4 7 采用s m o t e 后，实际分类面和理想分类面示意图 7 7 图4 8s d p c s v m 算法实验结果直方图 8 l 图5 1t s v m 和s v m 算法最优分类边界示意图8 6 图5 2 一个t u t o r i a l 训练样本集9 4 浙江大学博士学位论文目录 表目录 表3 1 三种不确定方法的区别 3 5 表3 2 示意性例子实验数据4 2 表3 3 实验a 的数据及实验结果 4 5 表3 4 实验b 的先验知识4 6 表3 5 实验b 的数据及实验结果4 7 表3 6g s v d d 算法实验数据及实验参数5 5 表3 7g s v d d 算法实验结果5 5 表3 8网页日志实验数据6 0 表3 9 网页日志g s v r 算法实验结果6 1 表4 1 在不同i m b a l a n c e 下实际分类面和“理想”分类面在之间的夹角7 3 表4 2s d p c s v m 算法实验数据7 9 表4 3 以s e n s i t i v i t y ( s e ) 和s p e c i f i c i t y ( s p ) 为评价指标的实验结果 8 0 表4 4 以平均测度( g - m e a n ) 为评价指标的实验结果 8 l 表5 1t s 和i t s v m 在t u t o r i a l 数据集上的训练和测试结果比较9 4 表5 2r e u t e r s 数据集上的学习效果9 8 6 浙江大学博士学位论文第一章绪论 1 1 引言 第一章绪论 基于样本的机器学习问题是现代智能技术的一个重要分支，主要研究如 何从一些观测数据( 训练样本) 中挖掘出目前尚不能通过原理分析得到的规 律，并利用这些规律去分析客观对象，对未知数据或无法观测的数据进行预 测。有三类基本的机器学习问题，它们分别是模式分类、函数回归与预测以 及概率密度估计【1 - 2 , 1 0 3 。 统计机器学习( 人们一般简称其为统计学习) 是近几年被广泛应用的机 器学习方法【1 ，2 1 ，目前人们普遍认为统计学习理论是研究从数据到分布的归纳 机理问题，即要求解问题的目标是分布规律意义下的某种最优性，而我们所 知道的只有有限样本集合。因此，如何设计以训练数据为目标函数的机器学 习算法，从有限的样本集合得到分布意义下的最优，成为统计学习研究的主 要内容。 ；支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是建立在统计学习理论的基 础上的第一个学习算法，与其它机器学习算法仅仅考虑到经验风险最小化 ( e 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 ) 的原则不同，支持向量机是建立在统 计学习理论( 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 c 维理论和结构风险最小 化( s t r u c t u r a l 砒s km i n i m i z a t i o n ，s r m ) 原则上，在很大程度上克服了神经网 络等传统机器学习方法中的过学习( o v e r f i t t i n g ) 、非线性、维数灾难 】= o ，v 0 ( 2 6 ) 其中，p 表示概率，曩。 ) 和r ( 口) 分别表示在，个样本下的经验风险和对于 同一口的真实风险。它把学习一致性的问题转化为( 2 6 ) 的一致收敛问题。 式( 2 6 ) 称作单边一致收敛，与此相对应的是双边一致收敛，即 舰p br ( 咖( 口) | 占j = o ，v 譬 0 ( 2 1 7 ) 讨论单边收敛的条件和双边收敛的条件是密切相关的。 虽然学习理论关键定理给出了经验风险最小化准则成立的充分必要条 件，但这一条件并没有给出什么样的学习方法能够满足这些条件。为此，统 计学习理论定义了一些指标来衡量函数集的性能，其中最重要的是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 ) 。 2 2 2 v c 维 v c 维是统计学习理论中到目前为止对函数集学习性能的最好描述指标。 一个函数集的v c 维可以理解为由其分类函数能正确给以所有可能的二值标 识的最大训练样本数。也就是说，如果存在 个样本的样本集能够被函数集 打散，而不存在 + 1 个样本的样本集能够被函数集打散，则函数集的v c 维 就是j l 。如果对任意数目的样本都有函数能将它们打散，则函数集的v c 维是 无穷大。 1 4 浙江大学博士学位论文第二章统计学习理论 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越 大) 。遗憾的是，目前尚没有通用的关于任意函数集v c 维计算的理论，只对 一些特殊的函数集知道其v c 维。比如在押维实数空间中线性分类器和线性实 函数的v c 维是n + 1 。对于一些比较复杂的学习机器( 如神经网络) ，其v c 维除了与函数集( 神经网结构) 有关外，还受学习算法等的影响，其确定更 加困难对于给定的学习函数集，如何( 用理论或实验的方法) 计算其v c 维是当前统计学习理论中有待研究的一个问题【3 s 1 。 2 2 3 推广性的界 统计学 - 3 理论系统地研究了对于各种类型函数集的经验风险和实际风险 之间的关系，即推广性的界【2 1 。关于两类分类问题有如下结论：对指示函数 集中的所有函数( 包括使经验风险最小的函数) ，经验风险 ) 和实际风 险丑( 口) 之间以至少i 一，7 的概率满足如下关系【3 卿： r ( 口) s r 。( 口) + h ( i n ( 2 l h ) 1 ) - i n ( r 4 ) ( 2 8 ) 上式可以简单地表示为： r ( 盯) 墨( 口) + 妒( a ，) ( 2 9 ) 其中h 是函数集的v c 维，是样本数，r l 是满足0 r l s l 的参数，矿( ，) 称作 置信范围( c o n f i d e n c ei n t e r v a l ) ，也有人把它叫做v c 信任( v cc o n f i d e n c e ) 。 式( 2 9 ) 从理论上说明了学习机器的实际风险是由经验风险( 训练误差) 和置信范围两部分组成的。置信范围和学习机器的v c 维及训练样本数，有关。 因此，要想得到期望风险最小值，除了控制经验风险最小外，还要控制函数 集的置信范围，而置信范围随着函数集v c 维的增长而增大。在有限训练样本 下，学习机器的复杂性越高，v c 维越高，则置信范围越大，导致真实风险与 经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机 浙江大学博士学位论文第二章统计学习理论 器学习过程不但要使经验风险最小，还要使v c 维尽量小以缩小置信范围，才 能取得较小的实际风险，即对未来样本有较好的推广性。 2 2 4 结构风险最小化 从前面的结论可以看到，e r m 原则在样本有限时是不合理的。我们需 要同时最小化经验风险和置信范围。为此，统计学习理论提出了一种新的策 略，即把函数集构造为一个函数子集序列，使各个子集按照v c 维的大小( 亦 即( h z ) 的大小) 排列；在每个子集中寻找最小经验风险，在子集间折衷考 虑经验风险和置信范围，取得实际风险的最小，如图2 2 所示。这种思想称 作结构风险最小化( 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 原则可以有两种思路。一是在每个子集中求最先经验风险，然后选择使最小 经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子集数目 很大甚至是无穷多时是不可行的因此有第二种思路，即设计函数集的某种 结构使每个子集置范围最小，则这个子集中使经验风险最小的函数就是最优 函数。支持向量机方法实际上就是这种思想的具体实现。 2 3 支持向量机 图2 2 结构风险最小化( s r m ) 示意图 再 支持向量机( s u p p o r t v e c t o r m a c h i n e ，s v m ) 是统计学习理论中最年轻、 最实用的部分。s v m 理论最初来自于对数据分类问题的处理，不失一般性， 1 6 浙江大学博士学位论文第二章统计学习理论 本文先将分类问题限制在二分类范围内讨论。在此背景下，支持向量机的主 要思想是建立一个超平面作为决策曲面，使得正类和负类样本之间的隔离边 缘被最大化。 2 3 1 线性支持向量机 2 3 1 1 线性可分情况 首先把问题限定在线性可分的情况下讨论，然后再推广到线性不可分情 况。图2 3 所示为二维两类线性可分模式，图中的圈和叉分别表示两类的训 练样本，日为把两类没有错误分开的分类线，蜀、凰分别为过各类样本中 离分类线最近的点且平行于分类线的直线，那么玩和也之间的距离即为两 类的分类间隔( m a r g i n ) 。所谓最优分类线就是要求分类线不但能将两类无错误 的分开，而且要使两类的分类间隔最大。前者是保证经验风险最小( 为零) ， 后者实际上是为了使置信范围最小，从而使实际风险最小，这是对结构风险 最小化原则的具体实现。推广到高维空间，最优分类线就成为最优超平面 ( o p t i m a lh y p e r p l a n e ) 。 图2 3 线性可分模式最优超平面示意图 设包含f 个样本的训练集为( 工，咒) ，i - - 1 2 ，j ，输入向量鼍r ”，对应的 期望输出为乃 + l ，一1 ) ，其中+ l 和1 分别代表两类的类别标识，行为输入维 1 7 渐江大学博士学位论文 第二章统计学习理论 数。假定分类面方程( 判别函数) 为w z + 6 = 0 ，这里w 是司调的权值向量， b 是偏置。我们将判别函数归一化，为使分类面对所有样本正确分类并且具 备分类间隔，就要求它满足如下约束： 妒_ ：f o r 胪“ 咖而+ 6 ) - 1 o ( 2 1 0 ) w x i + 6 - 1 f o ry = 一1 j 7 。、 7、7 可以计算出，分类间隔为： m i n 叫旦萨一m a 叫x 竺铲2 概2 亿m 叫 矿一叫 i ：f 2 概 o j u 现在的目标就是在服从约束式( 2 1 0 ) 的条件下最大化分类间隔南，这可 1 1w 1 l 以通过最小化的l l w u 2 的方法来实现那么，求解最优超平面问题，可在条件 式( 2 1 2 ) 的约束下，转化成如下的约束优化问题： 曾抑2 。i 1 ( w 叻 ( 2 1 2 ) j j y f ( w 鼍+ 6 ) 1 ，i = l ，2 ，l 这个约束优化问题被称为原始问题( p r i m a lp r o b l e m ) 。 为了解这个约束最优化问题，引入式( 2 1 3 ) 所示的l a g r a n g e 函数： l ( w , b ，口) = 专1 1 q 2 - q ( ( w - 薯) + 6 ) 一1 ) ( 2 1 3 ) 其中，口= ( 口 ，嘶) 7 ，吒 0 为l a g r a n g e 系数，这个约束最优问题的解由 l a g r a n g e 函数l ( w , b ，口) 的鞍点决定，此函数对w 和6 必定最小化，对口必定 最大化。l ( w , b ，口) 对1 ，和b 求偏微分并置结果等与零，得到下面两个最优化 条件： 掣：o( 2 1 4 ) 掣：o ( 2 1 5 ) 把式( 2 1 4 ) 代入式( 2 1 3 ) 得到： 浙江大学博士学位论文第二章统计学习理论 w = q 咒墨 ( 2 16 ) 抽l 把式( 2 1 5 ) 代入式( 2 t 3 ) 得到： j a l y j = o ( 2 1 7 ) i s l 把式( 2 1 7 ) 代入式( 2 t 3 ) ，并利用式( 2 t 6 ) ，可将原始优化问题表示为其对偶问 题( d u a lp r o b l e m ) 警一三喜骞q q 咒乃 ，_ ，+ 喜q s j 弗啦= o q o ，f = 1 2 ， 如果口：为最优解，则： ( 2 1 8 ) ， w = 彳乃葺 ( 2 1 9 ) i f f i l 即最优超平面的权系数向量是训练样本向量的线性组合。 这是一个不等式约束条件下的二次规划问题( q u a d r a t i cp r o g r a m m i n g ，简 称q p ) 。根据最优性条件k a n l s h - k u h n - t u c k e r 条件( 简称k k t 条件) ， 这个优化问题的解必须满足： a a y , ( w + 葺+ 6 ) 一1 ) = 0 ，i = l ，2 ，z ( 2 2 0 ) 因此，对多数样本吼将为零t 取值不为零的吒对应于使式( 2 1 0 ) 中等号 成立的样本，即做支持向量( s u p p o r tv e c t o r ) ，如图2 3 中位于1 - i , 、h 2 上的 样本点所示，它们通常只是全体样本中的很少一部分。对于学习过程而言， 支持向量是训练集中的关键元素，它们离决策边界距离最近；如果去掉所有 其它训练点( 或者移动位置，但是不穿越e 或) ，再重新训练，得到的分 类面是相同的。 求解上述问题后得到的最优分类函数是： 1 9 浙江大学博士学位论文第二章统计学习理论 ，( x ) = s 驴 ( w x ) + 6 = s 萨 套西以( 毛x ) + 6 ( 2 2 1 ) s g n o 为符号函数。由于非支持向量对应的口，均为0 ，因此上式的求和实际上 只对支持向量进行。而矿是分类的阀值，可以由任意一个支持向量用( 2 1 0 1 式求得( 因为支持向量满足其中的等式) ，或通过两类中任意一对支持向量取 中值求得，即：6 = 竺! ! 坚生! 皇! 塑地。 z 线性可分情况下的支持向量机也被称作硬间隔支持向量机。 2 3 1 2 线性不可分情况 现实世界中的数据往往带有噪音，硬间隔支持向量机不能把含有噪音的 训练集中所有样本完全正确分开，我们称此种情况为线性不可分情况。图 2 4 是线性不可分情况示意图，可以看到此时有些样本点位于分类间隔内。 在此情况下，由于某些样本不能满足式( 2 1 0 ) 的约束，因此，就需要“软 化”对间隔的要求，即适当放宽式( 2 1 0 ) 的约束，这可以通过在条件式( 2 1 0 ) 中引入一个松弛变量点o 来实现，此时约束条件就变为： 以【( w 而+ 6 ) 】l 一当， i = 1 ， ( 2 2 2 ) 图2 4 线性不可分最优超平面示意图 1 当分类出现错误时，毒大于0 ，因此，毒是训练集中错分样本数的上界。 译i 显然，当缶充分大时，样本点( 鼍，咒) 总可以满足上述约束条件。为此我们在 2 0 浙江大学博士学位论文第二章统计学习理论 目标函数里对它们进行惩罚，比如可以在目标函数中加入含有茧的一项。 此时，式( 2 1 2 ) 变为下面的约束优化问题： 卿圳1 2 + c ( 妻当)( 2 2 3 ) s j 咒 ( w 毛+ 6 ) 】1 - 磊， i = l ， 其中，c 0 为某个指定的常数，它实际上起控制对错分样本惩罚的程度的作 用，实现在错分样本的比例与算法复杂度之间的折衷，c 越大表示对错误的 惩罚越重。 类似地，我们可以把式( 2 2 3 ) 转化为下面的对偶问题： n 一吉q 哆乃乃( 一t ) + q。 二扛if - lf l 旺圭鹏：0o 嘶s c 卢l ，2 ， 2 2 4 注意，松弛变量磊并没有出现在对偶问题里。除了一些少许的但很重要 的差别外，线性不可分情况的对偶问题与线性可分情况的对偶问题很相似。 它们的不同之处在于约束条件玛o 被替换为条件更强的o - 口j s c 。除了这 个修改，线行不可分情况的约束最优化问题中权值向量w 和偏置b 的最优值 计算过程与线性可分情况的过程是相同的，其支持向量和以前的定义也一样。 线性可分情况的最优化问题其实可以视作一种特殊的情形包含在线性不可分 情况的最优化问题之中。在式( 2 2 3 ) 中对所有f 令毒= o b p = - 3 得到相应的线性可 分情况时的形式。线性不可分情况下的支持向量机也被称作线性软间隔支持 向量机。 一般地，我们把线性可分支持向量机和线性不可分支持向量机统称为线 性支持向量机。 2 l 浙江大学博士学位论文 第二章统计学习理论 2 3 2 非线性支持向量机 这一节我们介绍支持向量机如何处理非线性可分数据，在非线性学习问 题上处理能力上的不凡表现，正是支持向量机得以被推广和研究的主要原因 之一。 首先回顾一下对于线性可分问题的硬间隔支持向量机，在那里，是在能 够正确分开训练集的分类面中，寻找一个几何间隔达到最大的“最优”超平 面。对于非线性可分问题，仍可试用上述思路。由于在输入空间中能正确分 划训练集的最优超平面已不存在，于是考虑将输入向量映射到一个高维的特 征向量空间，并在特征空间构造最优超平面。图2 5 是这一实现思想的一个 直观示意说明。 图2 5 非线性司分问题的s v m 实现思想不惹图 但是在低维输入空间向高维特征空间映射过程中，由于空间维数急剧增 长，这就使得在大多数情况下难以直接在特征空间直接计算最优分类平面。 支持向量机通过定义核函数( k e r n e l f u n c t i o n ) ，巧妙地将这一问题转化到输入 空间进行计算，其具体机理如下： 由式( 2 2 1 ) 和式( 2 2 4 ) 可知，要在特征空间中构造最优分类面，只涉及内 积计算，因此可以假设有非线性映射o ：r 4 寸h 将输入空间的样本映射到高 维特征空问日中，当在特征空间中构造最优超平面时，训练算法仅使用特征空 间中的点积，即m ( t ) m ；) 。所以若能找到一个函数k 0 使得 k ( ，x j ) = m ( 而) ( 工，) ，这样，在高维空间中实际上只需要进行内积运算， 浙江大学博士学位论文第二章统计学习理论 甚至不必知道燹挟的形式。 根据泛函中的h i b e r t - s c h m i d t 定理，只要k ( 薯，x j ) 是一个对称正定函数， 并满足下列m e r c e r 条件，则丘( 而，而) 就对应特征空问中两个向量毛与乃的内 积这两个向量与乃分别是输入空间中的向量鼍与t 到特征空间中某个非 线性映射的像函数量( 薯，) 称为核 定理2 2 ( m e r c e r 条件) ：对于任意的对称函数置( 而，一) ，它是某个特征 空间中的内积和运算的充分必要条件是：对于任意的p ( 工) o ，且 p 2 ( 砷出 o ( 2 2 5 ) 因此，在最优分类面中选定某个满足m e r c e r 条件的核函数足( t ，x ，) 就 可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加，此时的 决策函数就变为： 删= s g n 僖西桶薯咖b )(226)iffil ，( 功= s 印 西乃x ( 薯功+ ( 2 。 lj 引入核函数后，式( 2 2 4 ) q ，的对偶问题相应地变为式( 2 2 7 ) q h 的对偶问题 形式： t 一丢妻喜q q 以乃足c 一，+ 萋i q 旺圭鹏：oo s q 妃f = l ，2