AdaBoost是一種典型的提升樹算法。

通過上面的總結(jié)我們看到，AdaBoost是一個神奇的算法，以精妙的方式通過更新數(shù)據(jù)集的權(quán)重以及各個弱分類器的參數(shù)組合成一個強(qiáng)分類器。那么它具體是怎么做到的呢？

二、AdaBoost算法推導(dǎo)

輸入：訓(xùn)練數(shù)據(jù)集T=(x1,y1),(x2,y2),...,(xN,yN)T=(x1,y1),(x2,y2),...,(xN,yN)，其中xi∈X?Rn,yi∈Y={?1,1}xi∈X?Rn,yi∈Y={?1,1}，弱學(xué)習(xí)算法Gm(x)Gm(x);

輸出：最終強(qiáng)化算法分類器G(x)G(x)
（1）初始化訓(xùn)練數(shù)據(jù)總和為1的權(quán)值分布：（初始權(quán)重為歸一化后的均值既1N1N）

（a）使用具有權(quán)值分布的DmDm的訓(xùn)練數(shù)據(jù)集學(xué)習(xí)，得到基本分類器：(數(shù)據(jù)集XX到{-1,1}的映射)
Gm(x):X?>{?1,1}Gm(x):X?>{?1,1}
（b）計(jì)算Gm(x)Gm(x)在訓(xùn)練數(shù)據(jù)集上的分類誤差率：（公式不夠簡潔明了，其實(shí)總結(jié)下來非常好理解：誤差率emem=誤分類樣本的權(quán)值之和）

• 我們來考慮下誤差emem的取值空間：由于訓(xùn)練集權(quán)制之和為1，因此誤差0≤em≤10≤em≤1。但是這樣還不夠。因?yàn)槲覀冊谶x擇分裂閾值的時候會選擇一個最優(yōu)或局部最優(yōu)的取值來分裂，且當(dāng)em=0.5em=0.5是表明該分裂閾值對預(yù)測無貢獻(xiàn)。因此最終得到的emem的實(shí)際取值應(yīng)小于em≤0.5em≤0.5。
• 所以最終：0≤em≤0.50≤em≤0.5，且每次迭代誤差emem遞減。這點(diǎn)對下面的參數(shù)理解很重要。

（c）計(jì)算Gm(x)Gm(x)的系數(shù):(這里對數(shù)為自然對數(shù))

• 那么問題來了，為什么要用這個公式來計(jì)算更新每個基分類器的參數(shù)？我們先畫個圖出來觀察下這個函數(shù)。（其中y軸為αmαm，x軸為誤差emem）

• 由（2-b）我們得到誤差emem的取值范圍為0≤em<0.50≤em<0.5，結(jié)合該圖可以可知0<αm<10<αm<1。
• 另外可以發(fā)現(xiàn)，通過該函數(shù)的轉(zhuǎn)換，弱分類器Gm(x)Gm(x)的誤差的越小，參數(shù)αmαm越大。即實(shí)現(xiàn)了給分類誤差率小的基本分類器以大的權(quán)值，給分類誤差率大的基本分類器以小的權(quán)值

（d）更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布：（該權(quán)值決定數(shù)據(jù)集的重要性，并讓誤差的計(jì)算變得簡單）

• 這里yi={?1,1}yi={?1,1}為真實(shí)值，Gm(xi)={?1,1}Gm(xi)={?1,1}為預(yù)測值。當(dāng)預(yù)測正確時yiGm(xi)yiGm(xi)為1，反之為-1。
• 令δmi=αmyiGm(xi)δmi=αmyiGm(xi)，θmi=wmiZmθmi=wmiZm(把它看作一個用于歸一化權(quán)值的加權(quán)平均常數(shù))。權(quán)重wm+1,iwm+1,i的更新函數(shù)可以簡化為wm+1,i=θmiexp(δmi),i=1,2,...Nwm+1,i=θmiexp(δmi),i=1,2,...N畫出y=wm+1,i=exp(δmi)y=wm+1,i=exp(δmi)的圖形來看一下：由于0<αm<10<αm<1，所以?1<δm,i<1?1<δm,i<1。且使得預(yù)測錯誤的數(shù)據(jù)集樣本點(diǎn)更新后的權(quán)重變大，預(yù)測正確的權(quán)值變小，然后對所有權(quán)值進(jìn)行歸一化。這就是該函數(shù)實(shí)現(xiàn)的作用。(圖中y=1是當(dāng)αα無限接近于0時的情況：解釋為，當(dāng)αmαm權(quán)值越大，權(quán)重wm+1,iwm+1,i更新改變的效果越明顯。)
• 這里，ZmZm是規(guī)范化因子，目的是使各數(shù)據(jù)集的權(quán)重進(jìn)行歸一化。理解為ZmZm=更新后的各數(shù)據(jù)集權(quán)重之和。
  Zm=∑Ni=1wmiexp(?αmyiGm(xi))Zm=∑i=1Nwmiexp(?αmyiGm(xi))

（3）構(gòu)建基本分類器的新型組合f(x)=∑Mm=1αmGm(x)f(x)=∑m=1MαmGm(x)，即：

參數(shù)αmαm公式及權(quán)重wm+1,iwm+1,i其實(shí)是通過前向分步算法分別得到的αmαm和Gm(x)Gm(x)并使得fm(x)fm(x)再訓(xùn)練數(shù)據(jù)集TT上的指數(shù)損失最小。具體的推導(dǎo)過程可參考《統(tǒng)計(jì)學(xué)習(xí)方法》–李航 第145～146頁

三、AdaBoost算法實(shí)現(xiàn)步驟

上面解釋了AdaBoost算法的具體內(nèi)容。這里寫出它的分布實(shí)現(xiàn)步驟再對上文算法加深下理解：

（1）假設(shè)訓(xùn)練數(shù)據(jù)集具有均勻的權(quán)值分布，即每個訓(xùn)練樣本在基本分類器的學(xué)習(xí)中作用相同，這一假設(shè)保證第1步能夠在原始數(shù)據(jù)上學(xué)習(xí)基本分類器G1(x)G1(x)。

（2）AdaBoost反復(fù)學(xué)習(xí)基本分類器，在每一輪m＝1,2,…,Mm＝1,2,…,M順次地執(zhí)行下列操作：

（a）使用當(dāng)前分布DmDm加權(quán)的訓(xùn)練數(shù)據(jù)集，學(xué)習(xí)基本分類器Gm(x)Gm(x)

（b）計(jì)算基本分類器Gm(x)Gm(x)再加權(quán)訓(xùn)練數(shù)據(jù)集上的分類誤差率（即誤分類樣本的權(quán)值之和。這里要注意wmiwmi表示第mm輪中第ii個實(shí)例的權(quán)值，且權(quán)值之和為1，即∑Ni=1wmi=1∑i=1Nwmi=1）：

（c）計(jì)算基本分類器Gm(x)Gm(x)的系數(shù)αmαm。alphamalpham表示Gm(x)Gm(x)在最終分類器中的重要性。由上面（2-c）可知，當(dāng)em≤1/2em≤1/2時，alpham≥0alpham≥0，并且αmαm隨著emem的減小而增大，所以分類誤差率越小的分類器在最終分類器中的作用越大。

（d）更新訓(xùn)練數(shù)據(jù)的權(quán)值分布為下一輪作準(zhǔn)備。式（2-d）的權(quán)重更新函數(shù)可以寫成：

• 由此可知，被基本分類器Gm(x)Gm(x)誤分類樣本的權(quán)值得以擴(kuò)大，而被正確分類樣本的權(quán)值卻得以縮小。兩相比較，誤分類樣本的權(quán)值被放大e(2αm)=em1?eme(2αm)=em1?em倍。因此，誤分類樣本在下一輪學(xué)習(xí)中起更大的作用。不改變所給的訓(xùn)練數(shù)據(jù)，而不斷改變訓(xùn)練數(shù)據(jù)權(quán)值的分布，使得訓(xùn)練數(shù)據(jù)在基本分類器的學(xué)習(xí)中起不同的作用，這是AdaBoost的一個特點(diǎn)。

（3）線性組合f(x)f(x)實(shí)現(xiàn)MM個基本分類器的加權(quán)表決。系數(shù)αmαm 表示了基本分類器Gm(x)Gm(x)的重要性，這里，所有αmαm 之和并不為1。f(x)f(x)的符號決定實(shí)例x的類，f(x)f(x)的絕對值表示分類的確信度。利用基本分類器的線性組合構(gòu)建最終分類器是AdaBoost的另一特點(diǎn)。

提升方法是即采用加法模型（即基數(shù)函數(shù)的線性組合）與前向分步算法，以決策樹為基函數(shù)的提升方法稱為提升樹（boosting tree）。對分類問題決策樹是二叉分類樹，對回歸問題決策樹是二叉回歸樹。

喜歡本文的伙伴請關(guān)注我的博客http://ihoge.cn

總結(jié)

以上是生活随笔為你收集整理的提升方法之AdaBoost算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。