（概率论与数理统计专业论文）boost方法在统计中的应用.pdf

摘要 判别分析主要是通过对给定的样本集合用某种分类方式产生一种判别准则的方 法根据已知的历史信息，对已被分类的研究对象产生判别函数，来判定新的观测样 本应归属的类别 经过长时间的发展，判别分析方法已经形成了一整套经典的解决方案我们在假 设样本服从多元正态分布下给出了一些经典的方法，但实际中对数据作这样的假设往 往是达不到的，那么将这样的判别方法用于非正态的情况下，其效果就不理想；而一 些简单的方法虽然不受分布的影响，但其误判率又往往较高，也限制了方法的应用 近几十年间，由于计算机的飞速发展，机器学习在统计、数据挖掘、人工智能和 工程等领域发挥熏大作用一些机器学习方法被用于对已知类别的样本产生判别准 则，判别新的样本的所属类别，像决策树和神经网络等，这与统计中的判别分析方法 有异曲同工之效近十年间，机器学习领域中出现了一种可以通过多次学习而提高 学习算法精度的方法，它采用综合选优的原则而使算法的效率明显改善，此方法被 称为b o o s t i n g 方法这种方法可以有效地将效率较低的所谓“弱学习算法”转化成 效率较高的“强学习算法”，但由于它需要预先知道一些参数，而这些参数在实际中 又无法获得，因而其实用性受到很大的限制随后出现了对b o o s t i n g 改进的方法一 a d a b o o s t 方法它不仅可以达到与b o o s t i n g 同样有效，而且不需要预先知道那些 参数，因此它的出现不仅在理论上完善了b o o s t i n g 方法的原理，而且在实践中得到 广泛的应用我们用它来改进统计中的字蜗4 分析，使那些简单的方法和基于正态假设 给出的方法在非正态的条件下均能继续保持或提高其精确度 因此，本文将a d a b o o s t 方法应用到判别分析的部分方法中，利用它能提高算法 精度的优势，使某些简单粗略的判别方法可以得到广泛的应用，克服其判别精度不高 的缺点得到比较准确的结果；使某些在正态假设条件下得到的判别方法在总体并非 正态的条件下依然能够保持或提高判别精度从而使得这些方法原来的小范围应用 变成广泛地应用于对各类数据的判别分析中 在第一章中，我们将介绍判别分析的几种基本方法，主要是我们将应用a d a b o o s t 方法进行改进的几种方法第二章中，我们将详细介绍b o o s t i n g 方法的来源和发 展，a d a b o o s t 方法的具体思想、步骤及其一些参数的确定在第三章中，我们利用 a d a b o o s t 方法改进判别分析的某些方法并模拟检验方法的有效性第四章中我们给 出一些实例分析，验证方法的有效性最后，总结a d a b o o s t 方法在判别分析中的用 途及效果，讨论a d a b o o s t 方法在其它领域的应用，例如。数据压缩。回归问题。寻 找异常点，等等另一方面。从b a y e s 观点的角度阐述a d a b o o s t 方法的基本思想 关键词：a d a b o o s t 方法b o o s t i n g 方法判别分析弱学习算法误判率 a b s t r a c t d i s c r i m i n a n ta n a l y s i si sa ne f f e c t i v em e t h o do fp r o d u c i n gad i s c r i m i n a n tr u l e b a s e do i lt h e g i v e n o b s e r v a t i o n sc l a s s f f i e db yc e r t a i nc l a s s i f i c a t i o nm e t h o d s a c c o r d i n g t oh i s t o r i ci n f o r m a t i o n ，i tg e n e r a t e sad i s c r i m i n a n tf u n c t i o na b o u tc l a s s i f i e dt r a i n i n g o b j e c t sa n dd e t e r m i n e sw h i c hc l a s san e ws a m p l eb e l o n g st o w i t ht h el o n g - p l a y i n gd e v e l o p m e n t ，d i s c r i m i n a n ta n a l y s i sh a sb u i l tas e r i e so f c l a s s i c a ls o l v i n gs c l l e m e s w eg i v es o m en o r m a lm e t h o d su n d e rt h em u l t i v a r i a t en o r - m a l d i s t r i b u t i o n h o w e v e r ，i np r a c t i c es u c hs u p p o s e sa r eu n s u i t a b l e w h e na p p l y i n g t h e s em e t h o d su n d e rt h en o n - n o r m a l d i s t r i b u t i o n ，t h ee f f e c ti s n tp e r f e c t a l t h o u g h s o m es i m p l e rm e t h o d sa r e n ti n f l u e n c e db yd i s t r i b u t i o n s ，t h e i re r r o rr a t e sa r ea l w a y s h i g h ，s ot h ea p p l i c a t i o n so ft h e ma r er e s t r i c t e d i nt h ep a s ts e v e r a ld e c a d ey e a r s ，b e c a u s eo ft h eh i g h s p e e dd e v e l o p m e n to fc o i n - p u t e r s ，m a c h i n el e a r n i n gp l a y sak e yr o l e i nt h ef i e l d so fs t a t i s t i c s ，d a t a m i n i n g ， a r t i f i c i a li n t e l l i g e n c e ，e n g i n e e r i n ga n ds oo n s o m eo ft h e mc a l lp r o d u c ead i s c r i m - i n a n tr u l ef o rg i v e ns a m p l es e t sa n du s et h er u l et od e t e r m i n et h ec l a s s e so fn e w s a m p l e s ，s u c ha sd e c i s i o nt r e ea n dn e u r a ln e t w o r k i ti ss i m i l a rt od i s c r i m i n a n ta n a l - y s i si ns t a t i s t i c s d u r i n gt h el a s tt e ny e a r s ，t h e r ea p p e a r sa ne f f e c t i v em e t h o d ，w h i c h c a ni m p r o v et h ep r e c i s i o no ft h e a l g o r i t h mb ym a n y r o u n d s l e a r n i n ga n do b t a i nm u c h m o r ea c c u r a t e p r e d i c t i o nr u l eb ym a j o r i t y i ti sa l w a y sc a l l e db o o s t i n g t h i sm e t h o d c a n e f f e c t i v e l yt r a n s f o r mt h ew e a kl e a r n i n ga l g o r i t h mi n t os t r o n gl e a r n i n ga l g o r i t h m h o w e v e r ，b e c a u s ei tr e q u i r e ss o m ek n o w np a r a m e t e r st h a tc a l ln o tb ef o u n di np r a c t i c e b e f o r el e a r n i n g ，i t sa p p l i c a t i o n sa r el i m i t e d l a t e r ，a d a b o o s tm e t h o d ，a n i m p r o v e d m e t h o di n t r o d u c e db y f r e u n d & s c h a p i r e ，n o to n l y i sa 8e f f e c t i v ea s b o o s t i n g ，b u t a l s o n e e d n ta n yp a r a m e t e r sb e f o r el e a r n i n g i t sa p p e a r a n c ei m p r o v e st h e o r e t i c a ls t u d y o fb o o s t i n gm e t h o da sw e l la ss o l v e sm a n y p r a c t i c a ld i f f i c u l t i e so ft h ee a r l i e rb o o s t i n gm e t h o d sa n da p p l i e si nm o r ef i e l d s w ea p p l yi tt om e n dd i s c r i m i n a n ta n a l y s i s ， i i i w h i c hc a nm a k em e t h o d sb a s e do nn o r m a ld i s t r i b u t i o nw h e nd i v o r c e df r o mn o r m a l h y p o t h e s i sa n ds i m p l em e t h o d sk e e p o ri m p r o v et h e i rp r e c i s i o n i nt h i sp a p e r ，w ea p p l ya d a b o o s tm e t h o dt oi m p r o v es o m em e t h o d si nd i s c r i m - i n a n ta n a l y s i si no r d e rt om a k e s i m p l ed i s c r i m i n a n ta n a l y s i sm e t h o d sa p p l yi nw i d e r f i e l d sa n dg e tp r e c i s er e s u l t sb y o v e r c o m i n g i t ss h o r t c o m i n g s tw h i c hu s e 8i t sa d v a n t a g e o fi m p r o v i n gt h ep r e c i s i o no fa l g o r i t h m s ；a n dm a k em e t h o d sb a s e do nn o r m a ld i s t i l b n t i o nw h e nd i v o r c e df r o mn o r m a l h y p o t h e s i sc o n t i n u et oe x e r tt h ea d v a n t a g eo fw e l l d i s c r i m i n a t i n ga n dp r o d u c eam u c hm o r ep r e c i s ed i s c r i m i n a n tr e s u l ta f t e ra p p l y i n g a d a b o o s tm e t h o dt om e n di t a sa r e s u l t ，w ec a ni m p r o v et h ee f f e c to fd i s c r i m i n a n t a n a l y s i sa n da p p l yd i s c r i m i n a n ta n a l y s i si nm u c hb r o a d e rf i e l d so fd a t aa n a l y s i s ， i nc h a p t e rl twi n t r o d u c es e v e r a lb a s i cm e t h o d si nd i s c r i m i n a a ta n a l y s i 8 ，w h i c h w i l lb ei m p r o v e db ya p p l y i n ga d a b o o s tm e t h o d w ep r e s e n tt h es o u r c ea n dd e - v e l o p m e n to fb o o s t i n gm e t h o d ，t h ei d e a sa n ds t e p so fa d a b o o s tm e t h o da n dt h e d e t e r m i n a t i o no fs o m ep a r a m e t e r si nd e t a i l si nc h a p t e r2 i nc h a p t e r 3 ，w ei m p r o v e s o m ed i s c r i m i n a n ta n a l y s i sm e t h o d sb y a p p l y i n ga d a b o o s tm e t h o d a n dm a k eas i m - u l a t i o n c h a p t e r4s h o w ss o m ee x a m p l e st ov a l i d a t et h ee f f i c i e n c yo ft h em e t h o d s f i n a l l y , w es u m m a r y t h eu s ea n de f f e c to fa d a b o o s tm e t h o di nd i s c r i m i n a n ta n a l y s i s ， d i s c u s si t sa p p l i c a t i o n si no t h e rf i e l d s ，s u c hb 8c o m p r e s s d a t a ，r e g r e s s i o n ，l o o k i n gf o r o u t l i e r s ，e t c o nt h eo t h e rh a n d ，w ei n t e r p r e tt h eb a s i ci d e ao fa d a b o o s tm e t h o di n b a y e s i a nt h e o r y k e y w o r d s ：a d a b o o s tm e t h o db o o s t i n gm e t h o dd i s c r i m i n a n ta n a l y s i s ，e a kl e a r n e re r r o r 第一章判别分析 在科学研究和日常生活中，我们经常会遇到对观测到的样本数据进行分类和判 别的问题例如，在经济学中，可以根据各国的人均国民收入、人均工业农业产值和 人均消费水平等多种指标来判定一个国家经济发展程度的所属类型；在医学上，经常 要根据患者的不同症状和化验结果等多项指标来判断其患病类型；在气象学中，要根 据最近的一些气象资料来判断明天是否会下雨；等等所有这些问题一般都可以应用 统计学中的判别分析方法予以解决判别分析要解决的问题就是在已知历史信息的 情况下，用某些方法对已分类的研究对象给出判别准则，来判定新的观测样本应归属 的类别 判别分析( d i s c r i m i n a n ta n a l y s i s ) 是由r a f i s h e r 于1 9 3 6 年提出的它在许 多领域中都得到了成功的应用它是根据历史上划分类别的有关资料和某种最优准 则，确定一个新样本归属于哪一类的方法实际问题中，我们也是常常会遇到需要根 据事物的若干性质的差别来判断事物的类别这一类问题在数理统计中屑于判别分 析的范畴 一般的判别分析用统计的语言可以这样描述已知n 个样本，每个样本测到p 个指标( 变量) 的数据已知每个样本属于k 个总体g - ，瓯之一，利用这些数据 及类别信息找出一个判别函数，使得这一函数具有某种最优性质，能把属于不同类别 的样本尽可能区分开来当测得一个新的样本时。通过判别函数将其归类 解决这类问题的判别分析方法有很多种，本文只着重介绍我们将用到的几种判 别分析方法 1 距离判别 对于任何两个p 维向量，它们之间的距离d ( x i ，x j ) 通常有以下几种t p ( i ) 欧氏距离t d ( x i ，q ) = ( ( 蛳一。弛) ) m ， k = l 堑二茎型型壁堑 ! ( i i ) 马氏距离：d ( 墨，q ) = 【( 一) e 一1 一巧) 】， n 其中= 面与( z 认一a ) ( z 让一盈) ，氟= 寺z 弛 k = l七= l 对于距离判别，首先考虑两个总体的情形 设两个总体为g 1 ，g 2 ，卫为一个需要判别的p 维样本如果z 到g l 和g 2 的距 离分别为d ( x ，g a ) 和d ( x ，g 2 ) ，则可用如下规则进行判别t ， io g 1 ，d ( x ，g z ) d ( x ，c 2 ) ， i 随机判定，d ( z ，g 1 ) = d ( z ，g 2 ) 、 对于多总体的情形，设各总体为g l ，g ，计算需拳蜗0 的样本z 与各总体的距 离d ( x ，g t ) ，i = 1 ，判别准则为： z 哪啤地g t ) 2b a y e s 判别 设已知各总体为g l ，g ，讯为类别k 的先验概率， x 在g = k 类的密度函数应用b a y e s 理论。可得 p ( g = 七i x 3 。) = 燕， z 属于此后验概率最大的一类 怎1 矾= 1 ，k ( x ) 为 1 发设备总体月陵从多兀正悉分布，g k ”坼( m ，琢) ，k = 1 ，k 如各总体有共同的协方差阵，= e ，v k 对于两类g 1 ，g 2 ，我们有似然比t 蜿器舞 一g 锱仙g 署 = l 。嚎一扣+ 蚓t 1 ( p 1 一p 2 ) + x t 一( p l p 2 ) ( 1 2 ) 由( 1 2 ) ，我们得到线性判别函数( 1 i n e a rd i s c r i m i n a n t u n c t i o n ) ： 靠( z ) = ，- l # k - - i 1 如t 一1 脚+ l o g 丌b 箜二重型型壁堑 ! 判别准则为： z 酊g 群以( g ) 但在实际中，我们往往不知道分布的参数，因此需要由训练集样本进行估计 i r k = ；，j 为第七类中样本的个数， m 2 袁互叭 旺南苫互( x i - # k ) ( x - p k ) ，_ 对于一般的判别问题，e k 并不相同，当遇到这种情形，我们通常使用二次判别 函数f q u a d r a t i cd i s c r i m i n a n tf u n c t i o n ) ： 颤 ) = 一a l o g l e i 一互1 一脚) t i 1 ( x - # k ) + l 。g 7 r ( 1 3 ) 判别准则为t $ 口r g i 孕争x 6 k ( z ) 注t 当样本量很大的时候，计算e 及e _ 1 就非常困难为了简化计算，我们作 如下变换：将氩或宝进行谱分解，可得到& = u k d k u k t ，其中u k 为p p 的正 交阵，d k 为以特征值为对角元素的对角阵，这样( 1 3 ) 式的元素变换如下； ( z 一扛 ) t i 1 ( z 一口) = 【u k t ( 。一口) 】r u k t ( z 一口) 】， x o gi 瓢1 = l o g d k z 在进行判别分析之前，我们对训练集进行预处理，使得判别分析的计算步骤简 化首先对训练集的t 鼢) 磐1 进行标准正交化，矿一d ；u t x ，宝= u d u t ，这样， 共同协方差阵就变为单位阵，简化了计算 第二章b o o s t i n g 和a d a b o o s t 方法 机器学习是对具有学习能力的计算机算法以其经验不断改进其完成任务效果的 研究它是人工智能的一个领域，是知识获取的一个过程，其关键在于学习学习是 一个系统的改进，这种改进可以使该系统更有效地处理同样的工作获取知识正是学 习的本质学习的关键是构造对目标的表示这种表示可以是符号描述、算法描述、 模拟的模型、控制过程、神经网络、图形等等将要学习的信息提供给系统，通过分 析、归纳、演绎信息，构造出对目标的表示，为新信息提供进一步学习的指导这就 是学习的过程 我们所用到的机器学习是一种归纳学习，即对已分类的数据，通过归纳其分类的 原因。产生一些概念性描述作为学习的结果例如，通过对温度，湿度，有无风等观 测结果的分析来判断是否适于打高尔夫由归纳学习的一种算法一决策树算法，利 用温度，湿度，有无风等探索性信息计算生成决策树，然后将其变换成分类准则的集 合这些分类准则即为学习的结果 我们已经了解的许多学习算法，它们的准确率各不相同我们希望每个学习算法 都有较高的准确率，但这在实际中不易做到b o o s t i n g 方法的出现对提高学习算法 的准确率起到了积极作用 b o o s t i n g 是用来提高不同学习算法准确率的方法。它使许多算法发挥出巨大的 效用为了使判别分析方法也可以提高准确率。我们应用b o o s t i n g 方法的思想于判 别分析，来得到高效的判别准则 首先，让我们了解一下b o o s t i n g 方法 4 堑三至墅箜! ! 竺曼堑垒! ! 里! 竺! 壅鲨! l 基本概念 1 学习算法( l e a r n e r ) 对已知数据信息通过分析、归纳其被分类的原因，生成数据特征的描述 作为学习的结论用来完成这样过程的计算机算法称为学习算法我们把 需要用b o o s t i n g 方法进行改进的精度不高的算法称为弱学习算法( w e a k l e a r n e r ) 2 讨h 练集( t r a i n i n gs e t ) ：s = ( z 1 ，玑) ，( 茁，毫，) ) 训练集是已知的数据信息，即所谓弱学习算法用于获得学习结论的样本 集合它包含个样本，每个样本有观测值瓤和标识值玑组成，其中x t 是属性值( 多元指标) 的一个向量，属于样本空间x ；每个y i 为x i 的类别标 识，属于一个有限标识空问y 3 假设( h y p o t h e s i s ) 学习的目的是构造对目标的表示作为学习的结论，在这里即产生一个函 数此函数通过作用在训练集的观测值上而产生一个标识，这样的函数称为 假设，记为 ( 口) ：x h 在b o o s t i n g 中，每次学习都产生一个假设，我们称为弱假设；最终联合所有 弱假设而得到的判别函数称为最终假设或最终判别准则，记为日( z ) 4 分布d b o o s t i n g 方法的第次循环中提供给弱学习算法的关于训练集样本的分 布，记为d t 5 误判率( e r r o r ) 由第t 次弱学习而得弱假设的错判概率称为误判率，这里此误判率( e r - m 帕定义如下。 龟= e d 。执( z ) 】_ p d 白也( z ) ) = 觑( i ) ， 整三主璺! 竺! 些墨塑生些竺! 查鎏曼 其中e d 。，p d 。分别为训练集关于分布d 。的期望及概率1 s 为集合s 的 指示函数，即s 成立取l ，否则取0 注意：这里的误判率是基于弱学习算法学习的训练集的分布d t 的 2b o o s t i n g 方法 b o o s t i n g 方法来源于p a c 学习结构( v a l i a n t ，1 9 8 4 ，k e a r n s & v a z i r a n i1 9 9 4 ) 它的提出是为了将弱学习算法( 准确率不高，仅比随机猜测略好) 提升为强学习算法 ( 准确率很高) s c h a p i r e ( 1 9 9 0 ) 提出了最初的b o o s t i n g 方法它的主要方法如下： 通过对个训练样本的学习，得出初始判别g l ； 判别g 2 是对新的个样本学习的结果，此个样本中的半数为被g l 错 判的； g s 的训练集为由g l ，g 2 作出不同判断的个样本组成； 由b o o s t i n g 作出最终判别准则tg b = 多数意见( g l ，g 2 ，g 3 ) 在这篇文章中。s c h a p i r e 在理论上证明了最终判别准则g 口对g ，判别准确率 的提高但由于此方法实施起来需要大景的时间、存储空闾及样本。因此使用起来极 不方便 f r e u n d ( 1 9 9 5 ) 提出了“投票方式b o o s t i n g 方法”对s c h a p i r e 的方法进行了改 进这种相对简单、行之有效的方法通过平行地作多次学习，再对各次学习的弱假设 以多数意见来作为最后的判别准则 这两种方法都是通过多次运行弱学习算法，每次将其应用于样本空间的不同分 布上，得出多个弱学习所产生的弱假设。最后采用多数投票的原则综合所有弱假设给 出一个简单的最终的判别准则，从而达到提高弱学习算法的准确率的目的两种算法 都是通过不断加大样本中难以判别的样本的权重，迫使弱学习算法得出在这些样本 上犯更少错误的假设b o o s t i n g 和投票方式b o o s t i n g 方法结构的异同由图2 1 可 见 两种算法在理论上都要求弱学习算法有固定的误判率，但实际中这是很难做到 蔓三主墅塑! ! 坚塑生堂璺! 堕! 麦造 1 0 t ) 一多数意见 口一由弱学习算法产生的弱假设 图2 1 ：b o o e t i n g 方法( i ) 和投票方式b o o s t n g 方法( i i ) 的结构图 的这使得人们迫切地想找到一种更具适应性和实用性的算法a d a b o o s t 方法 ( f r e u n d s c h a p i r e ，1 9 9 6 ) 的产生和它的推广使这种想法得以实现，也使b o o s t i n g 方 法得到广泛的应用 3a d a b o o s t 方法 1 9 9 5 年，f r e u n d s c h a p i r e ( 1 9 9 6 ) 提出了a d a b o o s t 方法。它有效地解决了上 文所遇到的问题它的最终判别准则的精确度是依赖所有弱学习过程得出的弱假设 的，因而更能全面地挖掘弱学习算法的能力也正是由于此种原因而得名“a d a p t i v e b o o s t i n g ”，简称a d a b o o s t 同时，它也是能应用于实际问题的一个有效的方法 a d a b o o s t 方法将训练集作为输入，在循环t = 1 ，t 中反复应用已知的弱学 习算法在每次循环中，保持训练集样本的分布或权重，对每个样本i ，其第t 次循 环的分布权重记为取( t ) 初始时，令所有权重相等在每次循环中。根据前一次的 学习而得的假设对训练集样本进行判别。加大被错判样本的权重，使弱学习算法被 迫集中精力于难于判别的样本上弱学习算法的目的是依据分布d t 学习得到弱假设 ：x r 其优劣程度由误判率日度量实际中弱学习算法可以利用加了权风的 训练集样本，也可以利用根据d l 进行重抽样所得的训练集样本一旦弱假设h t 已 经我到，a d a b o o s t 方法将选取参数a t 来量度的重要程度分布权重现也将根 据一定的原则c j 羊见以下各方法中更新原则) 进行更新最终，我们联合t 次弱假设 蔓三主墅竺! ! 坚塑生堂旦! 竺! 麦鎏 ! h 。，t = l ，t 及其对应参数q 。，t = l ，r 作出加权多数投票作为最终的判别准 则此方法的大致结构如图2 2 所示 圃一h t ( z ) ： 1 伍磊a h 3 ( x n 3 t x ) 、 ( 垫坚堂查) 1 伍磊a h 2 ( x n 2 1 x 、) 【! ! 坚堂查j f 图2 2 ：a d a b o o s t 方法的结构图 下面，我们将介绍a d a b o o s t 的几种主要算法，并对训练误判率及参数确定进行 分析 3 1 两类问题的a d a b o o s t 方法 一、离散a d a b o o s t 方法 给定训练集s = ( 。1 ，y 1 ) ，( x n ，”) 包含个样本，其中每个3 7 i 是属性值 的一个向最，属于样本空间x ；每个玑是q 的类别标识，属于有限标识空间l ，这 里我们只着重针对两类的问题，因此可设y = f 一1 ，1 ) 所谓离散a d a b o o s t 方法，即我们学习而得的弱假设仅取离散值，那么所得的假 设h 有如下形式： h ( x ) ：x 一 一1 ，1 ) ， 其主要步骤见表2 1 所示 在每次循环中，算法更新权重采用如下原则；减小被h 。判对样本的权重，将其 权重乘以一个依赖加权训练误判率的因子；对于判错的样本，其权重保持不变然后 将训练集所有权重通过标准化常数五进行标准化，使篓。岛( i ) = 1 换言之，我 们的原则是对于那些被以前多个弱假设正确分类的样本给以相对低的权重，而对那 z及 r h 佗 9 s | | zh 笪三童墅堂! ! 坚塑墨螋! 箜! 左鎏 ! 些难于判对的样本给与高权重，追使弱学习算法集中精力于那些难于判对的样本在 最后一步。对于高误判率的弱假设给于低的权重，算法联合所有弱假设h l ， t 通 过加权求和给出一个最终的简单的判别( $ ) 对训练误判率的分析 定义2 1 h ( x ) 对训练集的误判率称为训练误判牢，记为厶即 1 e = e d h ( x ) y 】= 寺f d ：日( ) 弘) i ， ( 2 1 ) 其中i j 4 i 表示集合a 的元素个数 对于a d a b o o s t ，f r e u n d s c h a p i r e ( 1 9 9 7 ) 给出了一个关于训练误判率的重要理 论结果 定理2 1 设已知弱学习算法，运行a d a b o o s t 改进弱学习算法，产生以e 1 ，e 为误判率的弱假设，则训练误判率有如下上界。 堑三茎曼竺! ! 堕塑生堂璺! 竺! 左造 ! ! t e s 2 r 以丌习 t = 1 其中z t = d t ( i ) e x p ( 一啦! ( 虮乩( ) ) i = 1 在这里，我们给出一种基于离散a d a b o o s t 的证明方法 首先注意到 e = e d h ) y j = 专盼h ( x t ) 玑) l = d ，( ) 矾产盯t 以j = 丙1 l 彬酬 因为 d ( t ) = 手d t ( i ) e x p ( - - a t l ” r ( 。) ) ) 厶t = i i 杀所一e x p ( 一a 丁。伽嘶“别e x p ( 一叼l 嘶) ) =鬲1训州喜t=l山舻州，)z t 、7 = 烹唧( 毒 ，州引，) 五 、8 17 = - 烹唧( 一壹t = la t 掣) n z f 、7 =熹exp(1和慨1纠tt 2 磊唧p 酽d 鼢卜互驯 ( 2 2 ) ( 2 3 ) 邑 r： 一 0或 2 而1 e x p ( 如池1 纠t ， 协4 ) 以及当日( 锄) y i ，u i h i ( x i ) 0 ，有e x p ( 一 鼽 ，( 戤) ) 1 ，所以由( 2 4 ) 式， 又因为 斋喜m 斋喜唧( 节1 州瑚) 垂五娄dr+(i)expl( 鸯1 1 五+ l ；q f 】 = li =t = t 1 1 z te x p ( 套)( ；若吼) 矗五 五= d t ( t ) e x p ( 一毗1 “乩( 叫，) i = l = 娄d t ( i ) e x p l( hr 鼍削，) = ( h 丁削) ) t = 、 ， = 娄州忐) 1 q 伽舢出m ， 由z 1 一( 1 一x ) r 可得 若n 叫，一( - 一点) ”鳓出m ) 溪叫( ，一( t 一志) ”q ，) z 一( - 一惫) c - 刊 2 e t ， 一 五 t 潍 有贝 e r 矿 阿 丁 矿 r m 一 e 蔓三童堕盟塑墨坐幽! 立迭 ! ! 在上述定理中，如果设每个龟sj 1 ，令饥= e t ，则最终判别h 的训练误判率上 界可改写为； ( 2 6 ) = e x p ( 一垂k l c i i l ；一m ，) c z ， = l 一k l ( i i l i m ) ) ( 2 7 ) = 1 一一 ( 砉醒) ， s ， 其中k l ( a l l b ) = al i l ( o 6 ) + ( 1 一a ) l n ( 1 一n ) ( 1 一b ) 为k u l l b a c k - l e i b e r 散度 注t ( 2 8 ) 式由当0 x 0 时，实值a d a b o o s t 方法更新权重的原则为t 根据h t 增加错判样本的 权重，减少判对样本的权重 对训练误拳率的分析 实值a d a b o o s t 方法最主要的性质在于它减小训练误判率的能力通过下面的定 一 t 僦 一 e 笪三茎里! 竺! i 坚塑垒垡苎! 垫竺! 立鲨 坐 理。我们可以看到实值a d a b o o s t 方法的确是离散a d a b o o s t 的一个推广，尤其当k 取一1 和1 时 定理2 2 表2 2 中实值a d a b o o s t 的最终假设h 的训练误判率有如下上界z e = 蜓掣专砉时舭踟= 娶t 五，仁9 ， 其中 出) = 。t h t 慨) 此定理的证明类似定理2 1 的证明对于参数铆及t 的选取，我们将在本章的 最后一部分详细讨论 下面，我们讨论对于多类问题如何解决 3 2 多类问题的a d a b o o s t 方法 对于多类的问题，主要有两种情形：一种是一个观测对应一个标识，每个样本只 笪三茎里! 竺! ! 堕堑垒堂星! 竺! 查鲨笪 属于类；另一种是每个样本同时属于多个类由于后者较复杂，我们在这里不加讨 论，具体实施方法可以参见s c h a p i r ea n ds i n g e r ( 2 0 0 0 ) 所给出的方法下面。我们仅 就第一种情况讨论 设训练集s = ( z l ，y 1 ) ，( x n ， ) ) ，其中标识y i y = l ，k ) 为有限标 识空间，每个戤对应唯一的玑我们学习的目的是在第次学习中产生h t ：x y ， 其误判率c l = e o 。( ( 。) y ) 较小最直接的方法可见f r e u n da n ds c h a p i r e ( 1 9 9 6 ) 文中的a d a b o o s t m 1 方法当弱学习算法能产生误判率小于1 2 的弱假设时，此方 法将非常有效但在实际中，由于需要分成类，达到每次学习的误判率都小予1 2 是很困难的，因此这个方法在实际运用中受到限制 在f r e u n da n ds c h a p i r e ( 1 9 9 7 ) 中，a d a b o o s t m 2 方法解决了这个问题它通 过把多类的问题转化为进行多次两类的问题，并使用“伪损失”进行权重的修改 对于每个样本( z ，) ，我们作一系列二类问题弱学习算法产生的假设h 为如下 形式t h ( x ，y ) ：x y 一 0 ，1 ， 即h 量度了y 为z 的正确标识的程度它不仅包含正确标识的信息，也包括了很可 能为正确标识的信息，所有这些对a d a b o o s t 方法都有潜在的用处 下面我们来定义伪损失 对于每个训练样本( 鼢，们) ，利用弱假设h 来回答k 一1 个二元问题对任何不 正确的标识( 鼽) ，计算h ( x i ，y ) 与 ( 戤，挑) 将 ( z ，y ) 作为一个随机决策，则选择 错误标识y 的概率为 p 【 ( 鼢，y ) = 1ah ( x i ，虮) = 0 l + 妄p 陋( 鼢，y ) = h ( 戤，弘) 】( 2 1 0 ) = 去( 1 一h ( x i ，玑) + h ( x i ，) ) ( 2 1 1 ) 若k 一1 次二元问题的判别结果的重要性相同，我们很自然地定义其平均值作 为损失，即 8 = 志；( 1 一h ( x i , y i ) + h ( x i , 掣) ) ( 2 1 2 ) f 产执 = i ( 1 一 ( 戤，轨) + 志 ( 掣) ) ( 2 1 3 ) 筮三主里! 塑! ! 竖塑丛i 塑塑! 壹鎏 堡 然而在实际中，不同的判别往往具有不同的重要性这样我们就需要给每次的判 别加上不同的权重对每对( x i ，s ，( 雏) ) ，我们赋予权重窜( i ，y ) 作加权平均谋判率如 ( 2 1 4 ) ，即所谓的“伪损失”t p l o s 如( ，i ) = ；( 1 一 ( 虮) + q ( i ，u ) h ( x 删) ) ， ( 2 1 4 ) “ 群们 其中，函数q ( i ，) ：t l ，n xy f 0 ，1 j 为标识权重函数，满足机q ( i ，y ) = 1 学习的目的就是最小化伪损失的期望； p l o s s o ，口( ) = e d p l o s s g ( ) 】 ( 2 1 5 ) 使用p l o s s d , q ( ) 作为误判率“，a d a b o o s t m 2 方法的主要步骤见表2 3 定理2 3 在a d a b o o s t m 2 方法中，用p l o s s d 口( ) 作为误判率而产生的最终假 设日的谢练误判率有如下上界， 1 1 e ( k 1 ) 2 r 正硒 ( 2 1 6 ) t = l 证明同定理2 1 这个定理表明，只要弱假设的伪损失小于1 2 ，学习算法就可以 用a d a b o o s t 改进而任何学习算法均可产生伪损失至多为i 2 的弱假设，而且即使 h 的伪损失大于1 2 ，由伪损失自身的性质，它也可以被a d a b o o s t 改进 4 参数的确定及分析 在进行b o o s t i n g 和投票方式b o o s t i n g 时，我们必须事先知道弱学习算法的误判 率白，且误判率必须是固定不变的，还要知道它的偏差7 ，这些均制约着方法的可行 性而在a d a b o o s t 方法中，我们就不需要这样，其误判率e t 会随着弱学习算法的 运行而自动调整我们需要知道的只有弱学习算法所需要进行的总次数t ，方法中o t 。 的选取也是基于最小化误判率的目的而定的 下面我们分别讨论两个参数的确定 4 1 t 的选取 如果所有m 均为，y ，( 2 8 ) 可简化为： e e x p ( - 2 t 7 2 ) ，( 2 1 7 ) 簦三童墅竺! 垒堕塑垒尘里! 箜! 立鎏 ! ! 由此