中國科學(xué)院大學(xué)機(jī)器學(xué)習(xí)-AdaBoost解讀

1、Boosting主要內(nèi)容：AdaBoost簡介訓(xùn)練誤差分析測試誤差分析貝葉斯最大后驗前向遞增建模一、AdaBoost簡介：1.1算法簡介給定訓(xùn)練集：(x,y(x,y)，其中yel,-l,表示x的正確的類別標(biāo)簽，i二1,N11NNii1訓(xùn)練集上樣本的初始分布：D1(i)=1N對t=1,.,T，計算弱分類器h:XT-1,1，該弱分類器在分布D上的誤差為:tt計算該弱分類器的權(quán)重：更新訓(xùn)練樣本的分布：最后的強(qiáng)分類器為：(H(x)=signfinal(1-)tIt丿()D(i)exp(-ayh(x)i=ttitia=ilnt2Dt+1，其中Z為歸一化常數(shù)。tattt=11.2.AdaBoost過程舉例

2、因為權(quán)重更新依賴于a,而a又依賴于，所以我們直接將權(quán)重更新公式用表示。D(i)exp(-ayh(x)titiZt樣本權(quán)重更新公式：D(i)=tF丿-t+1當(dāng)樣本分錯時，yh(x)=-1,itiexp(-ayh(x)=exp(a)=titiexpt1-)tt丿丿=expt1-L當(dāng)樣本分對時，yh(x)=1,iti12（1-8）t例：給定如圖1所示的樣本，弱分類器采用平行于坐標(biāo)軸的直線+-1)得到第一個弱分類器：e1=10=0-3,11驏-e十a(chǎn)=Ine1t=2桫e1正確分類樣本權(quán)重：D=Dtexp（-a）=D?Z112ln驏i27個）12F110錯誤分類樣本權(quán)重：D=Dexp(a)=1（3個）D

3、?12e11工10此時強(qiáng)分類器的訓(xùn)練錯誤為：0.32)繼續(xù)計算第二個弱分類器：e=丄？3=0.21,21414a=2222lnP=%5正確分類樣本權(quán)重：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錯誤分類樣本權(quán)重：（3個）第一輪正確:（3個）：D=D?3214211此時強(qiáng)分類器的訓(xùn)練錯誤為：0.33）繼續(xù)計算第三個弱分類器：e=?3=0.14,32222a3=2ln桫3i=2ln桫0.92正確分類樣本權(quán)重：（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錯誤分類樣本權(quán)重：（3個）前兩輪正確:（3個）：D=D?D432e3322創(chuàng)1=13622此時強(qiáng)分類器的訓(xùn)練錯誤為：0二、訓(xùn)練誤差分析1記二,t2t由于弱分類器的錯誤率總是比隨機(jī)猜測（隨機(jī)猜測的分類器的錯誤率為0.5),所以丫0,t則訓(xùn)練誤差為：R(H)Y0，則R(H)e-2沿。ttrfi

5、nal證明：1、對Dt+1進(jìn)行迭代展開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、訓(xùn)練誤差為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，是一個較小的正數(shù)。iiii當(dāng)樣本分錯時，

6、yf(X)1。iiii所以將1I0變?yōu)閑xp(-yf(x),相當(dāng)于對上述兩種錯誤率都放大 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具體實現(xiàn)時，首先選一個錯誤率最小的弱分類器h，然后確定其權(quán)重，所以是一個貪t心算法。（相當(dāng)于對f（x）=Hah（X），前向逐步遞增特征選擇，后面再詳細(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當(dāng)很小時，Q很大，即錯誤率很小的弱分類器的權(quán)重很大。tt4、訓(xùn)練誤差Z-D(i)exp(-ayh(x)tttitii1-工D(i)exp(-a)+ED(i)exp(a)ttttxgAi-(1t令-1-y(Y=“edge”由于弱分類器的錯誤率總是比隨機(jī)猜測(隨機(jī)猜測的分類器的t2tt1錯誤率為0.5)，所以0yY0，即丫為所有丫中最小的一個。tt則訓(xùn)練誤差的上界為：R(H)IHz-He%trfinaltt1t1He-2y2t1exp-2另y2e普t。t1所以，當(dāng)TtoR(H)e*t0，即訓(xùn)練誤差

9、的上界隨T的增加指數(shù)減小。trfinal三、測試誤差分析最終的強(qiáng)分類器為：H(x)sign另ah(x)。T為算法中唯一需要調(diào)整的參finalItt丿t1數(shù)，那么T該取多大值？初步猜測：T太大，模型會變得很復(fù)雜，會發(fā)生過擬合。0.2-traiii20406080100#ofrounds(7)但實際的運行結(jié)果為101001000#ofrounds(T)(boostingC4.5onletterdataset)當(dāng)訓(xùn)練誤差已經(jīng)等于0后，測試誤差仍然沒有增加，即使T已經(jīng)達(dá)到1000。#roundstrainerrortesterror0.08A1003310000?0更好的解釋:Margin訓(xùn)練誤差只考

10、慮了分類是否正確，還應(yīng)該考慮分類的信度。由于f()tt=1f(x)=ah(x)為弱分類器的投票權(quán)重，可將遼定義為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的增加，訓(xùn)練樣本的Margin會增大(證明過程類似訓(xùn)練誤差的證明)；而大的Marg

11、in會帶來更好的泛化性能(如果所有樣本的Margin都很大，可以用一個很簡單的分類器實現(xiàn)分類)理論上，測試誤差的界：Rtest(Hfinal)P(margin0)+O9其中D為弱分類器的復(fù)雜度。(boostingstumpsonheart-diseasedataset)AdaBoost也可能發(fā)生過擬合(如下圖所示)。多時，樣本均值趨近于期望，即期望風(fēng)險/測試誤差為E=E風(fēng)險，我們在每個樣本點(x)上最小化，E=Ey=p(y=1lx)exp(-f(x)+p(y=-1lx)exp(f(x)我們目標(biāo)是風(fēng)險最小的f(x)，艮卩expx,yL對上述exp(-yf(x)lx,通常當(dāng)滿足下述條件時，發(fā)生過擬

12、合的可能性很?。?弱分類器的Y(edge)較大(=-y),即弱分類器不太弱，錯誤率不太低,tt2t從而Margin較大；弱分類器相對樣本規(guī)模不太復(fù)雜。事實上上述heart-diseasedataset就是數(shù)據(jù)規(guī)模太小，弱分類器的edge也較小。四、AdaBoost相當(dāng)于最大貝葉斯后驗(h,a=argmin蘭exp(yf(x),(ahNi=11當(dāng)損失函數(shù)取L(y,f(x)=exp(-yf(x)時，則上述表達(dá)式為經(jīng)驗風(fēng)險，當(dāng)樣本很(-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相當(dāng)于前向逐步遞增建模f(x)=Hah(x),ttt=1可視為基展開，其中h(x)為基函數(shù)，a為對應(yīng)基函數(shù)的權(quán)重。對基展開，通常是給定tt基函數(shù)，一次聯(lián)合求出所有的基函數(shù)中的參數(shù)及其權(quán)重a(如用最小二乘法或極大似然t估計方法)。而AdaBoost可視為一個逐步遞增的方式增加基函數(shù)，并計算其權(quán)重，不調(diào)整已添加的基函數(shù)中的參數(shù)及其權(quán)重。因此亦被稱為前向逐步遞增建模(forwardstagewiseadditivemodelin

14、g).假設(shè)第T-1步的模型為：f(x)=ah(x)T-1ttt=1當(dāng)損失函數(shù)取L(y,f(x)=exp(-yf(x)時，則第T步新增加的基函數(shù)h及其權(quán)T重a要使得訓(xùn)練誤差/經(jīng)驗風(fēng)險最小，即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可以看作是應(yīng)用于iiT-1iii每個觀測的權(quán)值，該權(quán)值依賴于f(x)，所以，每個樣本的權(quán)值隨每次迭代改變。r-1i上述問題可以分兩步實現(xiàn)：第一步：首先選一個錯誤率最小的弱分類器h,Tiihi=1h=argmin工wtI(y豐h(x)。第二步：然后確定其權(quán)重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