中国科学院大学机器学习-AdaBoost解读

1、Boosting主要内容：AdaBoost简介训练误差分析测试误差分析贝叶斯最大后验前向递增建模一、AdaBoost简介：1.1算法简介给定训练集：(x,y(x,y)，其中yel,-l,表示x的正确的类别标签，i二1,N11NNii1训练集上样本的初始分布：D1(i)=1N对t=1,.,T，计算弱分类器h:XT-1,1，该弱分类器在分布D上的误差为:tt计算该弱分类器的权重：更新训练样本的分布：最后的强分类器为：(H(x)=signfinal(1-)tIt丿()D(i)exp(-ayh(x)i=ttitia=ilnt2Dt+1，其中Z为归一化常数。tattt=11.2.AdaBoost过程举例

2、因为权重更新依赖于a,而a又依赖于，所以我们直接将权重更新公式用表示。D(i)exp(-ayh(x)titiZt样本权重更新公式：D(i)=tF丿-t+1当样本分错时，yh(x)=-1,itiexp(-ayh(x)=exp(a)=titiexpt1-)tt丿丿=expt1-L当样本分对时，yh(x)=1,iti12（1-8）t例：给定如图1所示的样本，弱分类器采用平行于坐标轴的直线+-1)得到第一个弱分类器：e1=10=0-3,11骣-e十a=Ine1t=2桫e1正确分类样本权重：D=Dtexp（-a）=D?Z112ln骣i27个）12F110错误分类样本权重：D=Dexp(a)=1（3个）D

3、?12e11工10此时强分类器的训练错误为：0.32)继续计算第二个弱分类器：e=丄？3=0.21,21414a=2222lnP=%5正确分类样本权重：7个）1D=D?-322(1-e)2又分为两种：第一轮正确：4个）D=D？3212(1-e)1第一轮错分：3个）D=D?32(1-e)11?6,丄？丄丄142,112214172，116614错误分类样本权重：（3个）第一轮正确:（3个）：D=D?3214211此时强分类器的训练错误为：0.33）继续计算第三个弱分类器：e=?3=0.14,32222a3=2ln桫3i=2ln桫0.92正确分类样本权重：（7个）1432(1-e)3又分为三种情况

4、：1111苛卉於拥怖（1水、DD?刖两牝都正确：（11）DD432（1-e）322?2兰38221717?第扌匕千日分、J第-二扌匕正确.（3丨）DD432（1-e)366,2,1919?62211111冷Wft帘餡_杯聲/(a*、DD?弟轮正确、弟一轮日分：（3个）DD432（1-e)36、兰19?1222错误分类样本权重：（3个）前两轮正确:（3个）：D=D?D432e3322创1=13622此时强分类器的训练错误为：0二、训练误差分析1记二,t2t由于弱分类器的错误率总是比随机猜测（随机猜测的分类器的错误率为0.5),所以丫0,t则训练误差为：R(H)Y0，则R(H)e-2沿。ttrfi

5、nal证明：1、对Dt+1进行迭代展开D(i)=D(i)exp(-aTyihT(xi)T+1TZT正ah(x)itti丿t=-FIztt=1=D(i)旳(-叮gD。1rfztt=1=D(i)1exp-y令f(x)=ah(x)ttt=1由于Dt+1是一个分布,所以：迓D(i)=1T+1i=1所以Hz=丄艺exptNiit=1i=12、训练误差为Rtr(H)=丄为:y丰HfinalNi=1(x”ifinaliify主H(x)ifinalielseifyf(x)0ii*else丄工exp(一yf(x)Niii=1兀ott=1)0，所以0exp(一yf(x)1，是一个较小的正数。iiii当样本分错时，

6、yf(X)1。iiii所以将1I0变为exp(-yf(x),相当于对上述两种错误率都放大 HYPERLINK l bookmark123 o Current Document N10elseiii=1v了，这样不等式成立。(1-3、证明a二Int问题：给定弱分类器的集合：A=h(x),h(x),.,h(x)12Mtt(h,a)*=argminexp(-yf(x)(a,h)Ni=111=argminHZtt=1具体实现时，首先选一个错误率最小的弱分类器h，然后确定其权重，所以是一个贪t心算法。（相当于对f（x）=Hah（X），前向逐步递增特征选择，后面再详细描述）ttt=1aztaataD(i)

7、exp(-ayh(x)=，因为Z=D(i)exp(-ayh(x)aatttititi=1=-工D(i)yh(x)exp(-ayh(x)titititii=1-工D(i)exp(-a),ifxgA,A=x:yh(x)=1tti为D(i)exp(a),ifxgA,A=x:yh-ttiixgAiiiti(x)=iiti即A为分类正确的样本的集合，A为分类错误的样本的集合。aZ=0n工D(i)exp(-a)=工D(i)exp(a)SatttttxgAxgAiin工D(i)exp(a)=工D(i)exp(a)，两边同乘以exp(a)tttttD(i)=exp(2a戊D(i)tttxigAxigA正确率=

8、D(i)=1，错误率二D(i)=，ttxgAi所以1=exp(2a)ttttxgAi所以a二2】nt2当很小时，Q很大，即错误率很小的弱分类器的权重很大。tt4、训练误差Z-D(i)exp(-ayh(x)tttitii1-工D(i)exp(-a)+ED(i)exp(a)ttttxgAi-(1t令-1-y(Y=“edge”由于弱分类器的错误率总是比随机猜测(随机猜测的分类器的t2tt1错误率为0.5)，所以0yY0，即丫为所有丫中最小的一个。tt则训练误差的上界为：R(H)IHz-He%trfinaltt1t1He-2y2t1exp-2另y2e普t。t1所以，当TtoR(H)e*t0，即训练误差

9、的上界随T的增加指数减小。trfinal三、测试误差分析最终的强分类器为：H(x)sign另ah(x)。T为算法中唯一需要调整的参finalItt丿t1数，那么T该取多大值？初步猜测：T太大，模型会变得很复杂，会发生过拟合。0.2-traiii20406080100#ofrounds(7)但实际的运行结果为101001000#ofrounds(T)(boostingC4.5onletterdataset)当训练误差已经等于0后，测试误差仍然没有增加，即使T已经达到1000。#roundstrainerrortesterror0.08A1003310000?0更好的解释:Margin训练误差只考

10、虑了分类是否正确，还应该考虑分类的信度。由于f()tt=1f(x)=ah(x)为弱分类器的投票权重，可将辽定义为Margin，表示分类att=1的信度。highconf,incorrectlowconf.highconf,correctSinaiincorrect耳inalcorrect+1上述实验Margin的累积分布:trainerrortesterror%margins0.5minimummargin1.00.5-1-0.5.margin#rounds7.70.140.00520.00?55可以证明，随着T的增加，训练样本的Margin会增大(证明过程类似训练误差的证明)；而大的Marg

11、in会带来更好的泛化性能(如果所有样本的Margin都很大，可以用一个很简单的分类器实现分类)理论上，测试误差的界：Rtest(Hfinal)P(margin0)+O9其中D为弱分类器的复杂度。(boostingstumpsonheart-diseasedataset)AdaBoost也可能发生过拟合(如下图所示)。多时，样本均值趋近于期望，即期望风险/测试误差为E=E风险，我们在每个样本点(x)上最小化，E=Ey=p(y=1lx)exp(-f(x)+p(y=-1lx)exp(f(x)我们目标是风险最小的f(x)，艮卩expx,yL对上述exp(-yf(x)lx,通常当满足下述条件时，发生过拟

12、合的可能性很小：1弱分类器的Y(edge)较大(=-y),即弱分类器不太弱，错误率不太低,tt2t从而Margin较大；弱分类器相对样本规模不太复杂。事实上上述heart-diseasedataset就是数据规模太小，弱分类器的edge也较小。四、AdaBoost相当于最大贝叶斯后验(h,a=argmin兰exp(yf(x),(ahNi=11当损失函数取L(y,f(x)=exp(-yf(x)时，则上述表达式为经验风险，当样本很(-yf(x)o竺=-p(y=1lx)exp(-f(x)+p(y=-1lx)exp(f(x)=-p(y=11x)+p(y=-11x)exp2f(x)=0所以/(x)=；l

13、ogp(y=11x)p(y=-11x)所以p(y=11x)、p(y=-11x)JH(x)=sign(f(x)=signIlogfinal为最大贝叶斯后验。四、AdaBoost相当于前向逐步递增建模f(x)=Hah(x),ttt=1可视为基展开，其中h(x)为基函数，a为对应基函数的权重。对基展开，通常是给定tt基函数，一次联合求出所有的基函数中的参数及其权重a(如用最小二乘法或极大似然t估计方法)。而AdaBoost可视为一个逐步递增的方式增加基函数，并计算其权重，不调整已添加的基函数中的参数及其权重。因此亦被称为前向逐步递增建模(forwardstagewiseadditivemodelin

14、g).假设第T-1步的模型为：f(x)=ah(x)T-1ttt=1当损失函数取L(y,f(x)=exp(-yf(x)时，则第T步新增加的基函数h及其权T重a要使得训练误差/经验风险最小，即T(h,a)=argmin工exp(-y(f(x)+ah(x),TOC o 1-5 h zTTiT-1iih,ai=1=argmin工wrexp(-ayh(x),iiih,ai=1其中wr=exp(-yf(x)。因为每个wT不依赖于a,h，所以wT可以看作是应用于iiT-1iii每个观测的权值，该权值依赖于f(x)，所以，每个样本的权值随每次迭代改变。r-1i上述问题可以分两步实现：第一步：首先选一个错误率最小的弱分类器h,Tiihi=1h=argmin工wtI(y丰h(x)。第二步：然后确定其权重a,T艺wtexpii=1(-ayh(x)=e-a工iiWT+eaiy=h(x)ii工WT,iy.丰h(x.)ii因为(y=h(x)nyh(x)=1)iiii=(eae-a)送wtI(y丰h(x)+e-a艺wtTO