（应用数学专业论文）多分类支持向量机的推广性能.pdf

摘要 支持向量机( s v m ) 是通过执行结构风险最小化原则来获得好的推广能力 的学习机器，它最初是设计用以处理二分类问题的然而，许多实际问题中都 需要处理多类的分类问题因而，如何有效的推广该算法到多类的情形具有 重要的实际意义目前，主要有两种类型的方法利用支持向量机处理多分类 问题一是通过某种方式构造一系列的两类分类器并将它们组合在一起来实 现多类分类第二种类型是将多个分类器的参数求解合并到一个最优化问题 中，通过求解该最优化问题“一次性”的实现多类分类多分类学习算法的推 广性能研究是机器学习的热点问题之一 在本文中，基于多分类间隔和算法稳定性的相关结论，我们从算法稳定性 的角度分析了误差修正码核机器，基于特征函数的多分类支持向量机，有向无 环图支持向量机的推广能力，证明了三种多分类学习算法是一致稳定的，从而 获得了相应多分类算法的推广误差界 第一部分，引言阐述了支持向量机的基本思想，介绍了多分类支持向量机 的几种主要类型和相应背景 第二部分，介绍了误差修正码支持向量机的基本知识，利用算法稳定性的 性质得到了该算法推广误差的界 第三部分，分析了一种基于特征函数的多分类支持向量机，得到了其独立 于类别数的推广误差界 第四部分，估计了有向无环图支持向量机的推广误差界， 第五部分，简要探讨了局部多分类支持向量机的推广性 最后，在第六部分中，分析了前面得到的主要结果，并对未来进一步的研 究方向进行了展望， 关键词 多分类支持向量机；一致稳定性；推广能力；误差修正码；有向无环图 i i i 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 ) a r el e a r n i n gm a c h i n e si m p l e m e n t i n gt 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 ni n d u c t i v ep r i n c i p l et oo b t a i ng o o dg e n e r a l i z a t i o n ， w h i c ha r ei n t r i n s i c a l l yc o n c e i v e df o rb i n a r yc l a s s i f i c a t i o nh o wt oe f f e c t i v e l y e x t e n dt h eb i n a r ya l g o r i t h mt oi t sm u l t i - c l a s sc o u n t e r p a r th a sb e e nt h ef o c u s o fa t t e n t i o n0 fm u c hr e c e n tw o r k u pt on o w ，t h e r ea r et w ot y p e so fa p p r o a c h e s f o rt h en m l t i - c i a s sc l a s s i f i c a t i o np r o b l e m t h ef i r s ta p p r o a c hp r o p o s et od e r i d e t h ei n i t i a lm u l t i - c l a s sc l s s s i f i c a t i o np r o b l e mi n t os e v e r mb i n a r yc l a s s i f i c a t i o n p r o b l e m s t h es e c o n da p p r o a c hi sr e f e r e dt od e v e l o pa na l g o r i t h mc o n s i d e r i n g a l lc l a s s e sa to n c e t h e o r e t i c a la n a l y s i so fg e n e r a l i z a t i o ni sv e r yi m p o r t a n t a n dh a v es t a r t e dt od r a wm o r ea t t e n t i o nr e c e n t l y b a s e do nt h em a r g i no f m u l t i - c a t e g o r yc l a s s f f i c a t i o n ：w ep r o v et h e s ea l g o r i t h m sa r eu n i f o r ms t a b i l i t y a n dd e r i v et h e i rg e n e r a l i z a t i o ne r r o rb o u n d s t h ef i r s tp a r t ，p r e h m i n a r y , i n t r o d u c e st h eb a s i cd e f i n i t i o na n dp r o b l e m s o fs v m ，t h em a i ni d e a so fm u l t i - c a t e g o r ys v ma n dt h er e s e a r c hf o u n d a t i o n o fm u l t i c a t e g o r y s v m i np a r tt w o ，b a s e do na l g o r i t h m i cs t a b i t yp r o p e t i e s ， w es t u d yt h eg e n e r a l i z a t i o nc a p a b i l i t yo fe c o ck e r n e lm e t h o l d sa n dg i v ei t s t r a i n i n ge r r o ra n a l y s i sa n dg e n e r a l i z a t i o ne r r o ra n a l y s i s i np a r tt h r e e ，w ef u r - t h e ra n a l y s i sg e n e r a l i z a t i o no fm u l t i - c a t e g o r ys v ma n dd e r i v ei t se r r o rb o u n d s w h i c ha r ec l a s s - s i z ei n d e p e n d e n t i np a r tf o u ra n df i v e ，w eg i v eab r i e fg e n e r _ a l i z a t i o na n a l y s i sf o rd a g s v ma n dl o c a lm u l t i - c a t e g o r ys v mc l a s s i f i c a t i o n f i n a l l y , i np a r ts i x ，w ea n a l y s et h o s et h r e eb o u n d sg o ti np r e v i o u sp a r t s a n dg i v eap r o s p e c tf o rf u r t h e rr e s e a r c h k e yw o r d s m u l t i c a t e g o r ys u p p o r tv e c t o rm a c h i n e s ；g e n e r a l i z a t i o nc a p a b i f i t y ；u n i f o r ms t a b i l i t y ；e r r o rc o r r e c t i n go u t p u tc o d e s ；d i r e c t e da c y c l i cg r a p h 1 v 湖北大学学位论文原创性声明和使用授权 说明 原创性声明 本人郑重声明；所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个 人或集体已经发表或撰写过的作品或成果对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本声明的法律后果由本人承担。 论文作者签名佑、浓 签名日期：口6 年f 月f o 日 学位论文使用授权说明 本人完全了解湖北大学关于收集保存、使用学位论文的规定，郎：按照 学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷 本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化 或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部 分或全部内容 ( 保密论文在解密后遵守此规定) 论文作者签名：瞄、娥 签名日期：0 6 年 月，o 日 l l 导师签名 签名日期 粕f 笔 “年亍月口日 一引言 支持向量机算法是由v a p n i k 及其合作者在计算学习理论( c o l t ) 1 9 9 2 年 的会议中首次提出来的，之后受到了广泛的关注在2 0 世纪9 0 年代后期得 到了全面深入的发展，现已成为机器学习和数据挖掘领域的标准工具主要原 因之一是s v m 是机器学习领域若干标准技术的集大成者，它集成了最大间隔 超平面，m e r c e r 核，凸二次优化，稀疏解和松弛变量等技术，在若干挑战性 的应用中获得了目前为止最好的性能，在美国科学杂志上，s v m 及核方法被 认为是虮器学习领域非常流行的方法和成功的例子，并是一个令人瞩目的发 展方向”近年来，s v m 的理论已经取得了重大进展，其算法实现策略及实 际应用也发展迅速，可以确信t 该技术的研究已发展成为机器学习中一个独立 的领域，在理论和实践两方面都有着光明的前景 1 1 支持向量机简介 在统计学习理论的基础上发展起了一种通用的机器学习方法一支持向量 机( s v m ) ，较以往方法表现出很多理论和实践上的优势它建立在统计学习理 论的v c 维理论和结构风险最小化( s r m ) 原则基础上，根据有限样本信息在 模型的复杂性和学习能力之间寻求最佳折衷以期获得最好的推广髓力s v m 是统计学习理论的一种成功实现虽然这一新兴的学习方法中尚有许多问题 需要进一步研究，但很多学者认为，它正成为继模式识别和神经网络研究之后 机器学习领域新的研究热点在模式识别，函数逼近，信号预测，信息融合等 领域，s v m 已得到了广泛应用，它的进一步研究必将推动机器学习理论和技 术的重大发展 1 1 1 支持向量机的思想 支持向量( s v ) 机实现了下列思想：通过事先选择好的某一个非线性变 换，将输入向量。映射到高维空间z ；在这一特征空间中构造一个最优分类超 平面 在上面的方法中会出现两个问题；一个概念性问题和一个技术性问题 1 如何找到一个推广能力好的分类超平面( 概念性问题) 特征空间的维 数是非常高的，分开训练数据的超平面不一定具有好的推广能力 2 计算上如何处理如此高的高维空间( 技术性问题) 为了在2 0 0 维空间 中构造一个4 阶或5 阶多项式，必须在数亿维空间中构造超平面如何才能 克服“维数灾难”问题呢? 这一问题的概念部分可以通过构造最优超平面来解决根据最优超平面 的统计性质。如果我们髓够以训练祥本的最大范数和间隔的比值的平方的一 个小的期望或以支持向量数的一个小的期望来构造最优超平面，则所构造的 超平面的推广能力是好的 但是，即使最优超平面具有好的推广能力并可以从理论上找到它，如何处 理高维特征空间的技术同题依然存在然而，应注意的是，对于特征空间z 中构造最优分类超平面，我们并不需要以显式形式考虑特征空间我们仅仅需 要计算支持向量与特征空间的向量之间的内积 我们考虑h i l b e r t 空间中内积的一般性质假定，我们将向量z 即映 射到一个h i l b e r t 空间，其坐标为： 。l ( z ) ，( o ) ， 根据h i l b c r t s c h m i d t 理论，h i l b e r t 空间中的内积有一个等价表达式： ( 旬女施) = 坼为( 。1 ) 砷( z 2 ) 错( z 1 ，z 2 ) ，o ，0 ， r = 1 其中k ( x t ，x 2 ) 为满足下列条件的对称函数 定理1 1 为了保证一个连续对称函数k ( u ，u ) 在l 2 ( c 1 ) 空间中有一个含 有正系数的a k 0 的展开式 k ( u , v ) = a k z k ( u ) 讯( ”) ( 1 ) k = l ( 即k ( u ，”) 描述了某一特征空间的内积) ，充分必要条件为 ， 厶上，k ( u ， ) 9 ( “) g ( ) d u d v o 对于所有的g l 2 ( c 1 ) 成立( a 为郧的一个紧子集) 2 可用于构造支持向量机的h i l b e r t 空间中内积结构的好的性质是，对于满 足m c e r 条件的任何核函数耳( “，u ) ，存在一个特征空间( = ，( “) ，( “) ，) ， 在这一空间的核函数生成内积( 1 ) 1 1 2 构造支持向量机 在( 高维) 特征空间中生成内积允许我们构造一些决策函数，它们在输入 空间中是非线性的： f ( x ，n ) = s g i l ( 价n ? k ( 叩。) 枷， s v 而它们在特征空间2 ( z ) ，( z ) 、中等价于线性决策函数 ，扣，a ) = s g n ( z 肌。? 并( ) 知( z ) + 6 ) s vr = l 其中k ( z ，翰) 是生成特征空间中的内积的核因此，为了构造分类函数( 2 ) ， 我们可以利用构造线性分类超平面的方法，其中，我们使用由核 ，现) 来 代替由( z ，x i ) 定义的内积 1 为了在可分情况y j ( z , ，n ) = 1 下找出系数o ：i ，充要条件是，找出泛函 n n 哪) 2 若。一；t , 3 c q a j y t y j k ( 巧) 的最大值，约束条件为 瓯弘= 0 ，。i 0 ，i = 1 ，n t = 1 2 在不可分的情况下找出最优软间隔解，充分条件是，最大化泛函( 3 ) 约束条件是 0 毗c ，i = 1 ，n 3 最后，为了对给定的间隔1 m 找出最优解 m l n ) _ s 酬面蓊藏a n 。淞 o = 弘 o 。m 我们必须最大化泛函 约束条件为 ( o ) = 幽一a a t 机= 0 ，0 s 。1 ，i = 1 ，几 = 1 构造这一类决策函数的学习机器称为支持向量机 11 3 支持向量机回归 支持向量机的方法也可以应用到回归河题( 即实值函数估计) 中，仍保留 最大间隔算法的所有主要特征：非线性函数可以通过特征空间中的学习机器 得到，同时系统的容量由与特征空间维数不相关的参数控制，同分类算法一 样，学习算法要最小化一个凸函数，并且它的解是稀豌的。 为估计实值函数，我们采用二次 不敏感函数作为损失函数的定义，即 v ( y ，扛) ) ：= 1 9 一，( 。) i ；= ( i 一，( 。) l e ) 2 x f y 一，( 。) j e ) s v m 二次争不敏感损失回归定义为，其中 砖盯g m i 。1 2 + c 妻( 等+ e ) 1 i = 1 s t ，( 。 ) 一骄+ 毛， 轨一，( z 1 ) e + 已， 矗0 ，f 0 ，i = 1 ，一“ 这里引入了两个松弛变量，一个是在目标值之上超出所设，另一个是在目 标值之下超出s 所设 综合前面三节的内容，我们得到s v m 实现的就是如下的思想；通过某种 事先选择的菲线性浃射将输入向量映射到高维特征空间，再在这个空间中构 造优化间隔的超平面 4 眵 1 2 多分类支持向量机 最初的s v m 是用以解决两类分类问题，不能直接用于多类分类，如何有 效地将其推广到多类分类问题还是一个正在研究的问题当前已经有许多算 法将s v m 推广到多类分类问题，这些算法统称为“多分类支持向量机”它 们可以大致分为两大类：一种是通过某种方式构造一系列的两类分类器并将 它们组合在一起来实现多类分类；另一种是将多个分类超平面的参数求解合 并到一个最优化问题中，通过求解该最优化阊题“一次性”埯实现多类分类 第二类方法尽管看起来简洁，但是在最优化问题求解过程中的变量远远多于 第一类方法，训练速度不及第一类方法，而且在分类精度上也不占优当训练 样本数非常大时，这一问题更加突出正因如此，第一类方法更为常用多类 分类问题可以形式化地表述为：给定n 个训练样本( z - ，y 1 ) ，( x 。，g 。) ，其中 r ”， = 1 ，n ，且y l 1 ，埘，要通过上述训练样本构造一个分类函 数，使对未知样本。进行分类时的错误概率( 或者造成的损失) 尽可能小 本文将对上述两类学习算法作一定的理论分析下面介绍常用的多分类 支持向量机 1 2 1 第一型多分类支持向量机 下面分别简单地介绍属于第一类型的用8 v m 锯决多类分类问题的现有 主要方法 ( 1 ) “一对余”支持向量机 用s v m 解决多类分类问题最早的方法可能就是“一对余”支持囱量机 ( o n e - v e r s u s r e s ts v m s ) 算法该方法依次用一个两类s v m 分类器将每一类 与其它所有类别区分开来，得到k 个分类函数分类时将未知样本分类为具 有最大分类函数值的那一类例如，第i 个s v m 训练样本集，其中属于第i 类的样本标为正类，其它所有的样本标为负类因此，对给定的f 个训练样本 ( x 1 ，y 1 ) ，( z 。，) ，其中日舻，i = 1 ，竹，且y l l ，埘，则第i 个s v m 5 通过求解下面的优化问题获得： i n i n 呲p ) t c o l + c n 写 j = l ( u ) 丁妒( 即) + 酽1 一g ，当y i = i ， ( u 。) t 妒( q ) + b 4 - 1 + 苗，当肌i g 0 ，= l ，n ， 其中训练祥本a 通过事映射到高维空间，g 为惩罚因子 最小化( ) 7 2 意味着最大化2 1 1 u 4 m 它实际上为两组数据之间的间 隔，当训练数据线性不可分时，惩罚项c j ；。舒用以减少训练样本的错分数 目s v m 实质就是在正则项( 0 3 。) 。2 和训练误差中寻找一种折衷 通过解上述优化问题，可以得到个决策函数：( ) 7 妒( 。) + ei = 1 ， 从而依据上述算法，决策函数为 口gm a x ( 和) r ( 。) + 6 t ) t = 1k ( 2 ) “一对一”支持向量机 该方法在每两类间训练一个分类器，故对于一个k 类问题，将有k ( k - 1 ) 2 个分类函数( 见文【3 2 】) 对第i 类和第j 类的训练样本，我们通过解下面的优 化问题获得其分类器t r a i r 。o , b i “”；( w i j ) r 泸+ g 护 一 ( u 巧) r ( 观) + b 2 1 一专p ，当y t = i ， ( u 巧) 7 咖( ) + b l j 一1 + 口，当y t = j ， 馨0 ，i ，j = 1 ，n 这里有许多不同的方法对一1 ) 2 个分类器进行组合来实现多类分类通 常，我们采用如下“投票法”进行决策：若分类器s g n ( 巧) t ( 趿) + ) 分z 到第i 类，那么分其第i 类的票数增加一票否则，第类增加一票最后，我 们分输入向量z 到具有最大票数的类别这种方法称作“最大投票法”采用 上述方法的多分类s v m s ，简称为1 十1s v m s ( o n e - v e r s u s o n es v m s ) 算法 r ( 3 ) 有向无环图s v m s 有向无环图决策分类法( d i c i s i o nd i r e c t e da c y c l i cg r a p h ) 是p l a t t 等在 文f 3 7 1 中提出的一种多分类算法它在训练阶段和“1 1 ”投票一样，也要 构造出每两类间的分类面，即有k ( k 一1 ) 2 个分类器但是在分类阶段，该 方法将所用分类器构造成一种两向有向无环图：包括k ( k 一1 ) 2 个节点和k 个“叶”其中每个节点为一个分类器，并与下一层的两个节点( 或者叶) 相 连当对一个未鼹样本进行分类时，蕾先从顶部的根节点开始，根据根节点的 分类结果用下一层中的左节点或者右节点继续分类，直到达到底层某个叶为 止，该叶所表示的类别即未知样本的类别( 详见f 3 7 1 ) 1 2 ，2 燕二型多分类支持向量机 v a p n i k 和w e s t o n 等分别在f 4 5 4 3 中提出了一种通过解单一优化问题 来实现多类分类的方法该方法的思想与“一对余”方法相似它构造k 个两 类分类器区分第m 类与其它类，其中第m 个分类函数为壕( z ) + 6 因此， 这里有k 个决策函数，但是它们通过求解一个最优化问题得到，其优化形式 如下： n m i n 枷；) t + c “ l i = 1m m ( “) t ( 嗣) + 、( u m ) t 曲( 如) + 6 m + 1 一薯 算0 ，i = 1 ，n ，m ( 1 ，) y i 相应决策函数为 a r gm a x ( w 。) 7 毋( 。) + k ) r n = l ，1 k 7 该决策方法与“一对余”分类算法相同类似如二分类s v m ，其二元表示为： m i n n ( ；哼a a 一簖蟛4 + ；a ? 哆) k 扩2 a ? o y = 中a ，m = 1 ，。， 0 a 茎c ，a = 0 ， a 2 塞砰心2k 蓑y l 乳y j ： m = 】 lu ，肖， i = 1 ，n ，m = 1 ， 其中r i , j = 毋( 。) r 咖( z ，) 那么 n = ( 中a q ，) ( q ) ，m = 1 ，k t ：1 在文 7 j 中说明了上述优化形式等价于下面优化结构 k “ i n j j ，f ；j i 一岫jj 2 + g p o 玑 ( 6 ) 同样由文 2 5 1 结论，在与( 4 ) 相同的限制条件下，该优化形式也等价于 m i n i | | 一1 1 2 + 壕+ g g ”， ( 8 ) o m m 2 1口lm m 对式( 4 ) 的最优化解，考虑到限制条件( 6 ) 和( 5 ) ，我# 有 因此有 ( a 一a 跏( 翰) = 0 t = 1 ”# l 一| 1 2 = 壕u 。 0 一 q c，c。，v，：i一，c。，兰 e c o c 核学习机器的推广性能 9 0 ，y ) 0 ； 0 g ( x ，y ) ，y ； g ( x ，y ) 7 我们记0 ( 。) = 白( 9 ( z ，们) 类似的有 g ( ，) = ) 注意到，我们的损失函数由参数7 控制，因而可以根据实际要求通过调节1 的大小来测算风险 下面，利用前面稳定性和推广能力的关系，得到如下结论： 定理2 8 在定理2 7 的条件下，用f ，( ，z ) 代替解码损失函数f ( ，。) ，那 么帑21 ，5 ( 0 ，1 ) ，7 o ，下式以至少1 6 的概率成立， w ，吲胚竿( 刚k - 一i ，) + 。8 n c 7 p o t ( 、删k - 一1 ，) + b ) , f 6 证明注意到白满足1 ，y - l i p s c h i t z 条件，由定义，t ，也满足该条件因 此，vi ，s ，z ，有 如( ，z ) 一0 ( ，v ，z ) i = l 唧0 ( 。，) ) 一q ( 9 v ( z ，) ) ；i g ( z ，一9 ( z ，翟) 1 进一步，利用定理27 中相似的方法有 i i y ( f - 1 r ( ，圳下c p o t 。( 。譬，) 因此算法是一致稳定的，由定理2 5 ，即得所证 i 24 小结 根据定理2 7 的结论知道，e c o c 多分类算法的稳定性参数廓与常数 n ，卢，c ，p o ，一有关，即它由码阵的性质。，卢，p o ，核机器的正则化参数c 及核函 2 3 数k 来控制从算法本身的角度而言，是希望岛越小越好，因此码阵的设计 及参数g 的控制就很重要 稳定性的保证使得在e c o c s v m 中我们最终得到的结论定理2 7 和定 理2 8 中，随着n 趋于。o 时， 这祥一个结论成立 ( ，) 一( ，) 三独立于类别数目的多分类支持向量机误差分析 我们先考虑多分类问题的基本思想学习的目的是找到一个分类器p ： z y 使得对任意的输入z 爿其分类错误尽可能的小，其中z 可能输入 的向量组成的集合，y 是可能输出的类别组成的集合这里记输入x 所联系 的所有可髓输出的类别组成的集合为g e n ( x ) ，显然有g e n ( x ) cy 在实际 问题中，g e n ( x ) 中的类别数目可能仍非常大，为了有效的处理此类问题， 分析学习算法独立于类别数目的推