提升方法之AdaBoost算法
提升方法之AdaBoost算法
作為非數(shù)學(xué)專業(yè)出身看到密密麻麻的數(shù)學(xué)公式剛開始真的是非常頭疼。算法的物理邏輯的時候尚能理解,但是涉及到具體的數(shù)學(xué)公式實(shí)現(xiàn)就開始懵逼了:為什么要用這個公式,這個公式是怎么推到的,這個公式達(dá)到什么樣的效果?
這里結(jié)合自己的理解和畫圖,用最直白的語言對每個公式作用進(jìn)行解剖。
一、AdaBoost核心概念總結(jié)
提升方法是將弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法的統(tǒng)計(jì)學(xué)習(xí)方法。在分類學(xué)習(xí)中,提升方法通過反復(fù)修改訓(xùn)練數(shù)據(jù)的權(quán)值分布,構(gòu)建一系列基本分類器(弱分類器),并將這些基本分類器線性組合,構(gòu)成一個強(qiáng)分類器。代表性的提升方法是AdaBoost算法。(重點(diǎn)是:更新分類器的參數(shù)和訓(xùn)練集的權(quán)重見下2)
AdaBoost模型是弱分類器的線性組合:
- MM表示該提升樹共有MM個弱分類器組成
- Gm(x)Gm(x)表示第mm個弱分類器
- αmαm為第mm個弱分類器的參數(shù)(反應(yīng)該分類器的重要性)
AdaBoost算法的特點(diǎn)是通過迭代每次學(xué)習(xí)一個基本分類器。每次迭代中,核心思想是:提高那些被前一輪分類器錯誤分類數(shù)據(jù)的權(quán)值,而降低那些被正確分類的數(shù)據(jù)的權(quán)值。最后,AdaBoost將基本分類器的線性組合作為強(qiáng)分類器,其中給分類誤差率小的基本分類器以大的權(quán)值,給分類誤差率大的基本分類器以小的權(quán)值。
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)
(2)對 m=1,2,...Mm=1,2,...M:(弱分類器的個數(shù))
(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ì)算變得簡單)
wm+1,i=wmiZmexp(?αmyiGm(x?i)),i=1,2,...Nwm+1,i=wmiZmexp(?αmyiGm(x?i)),i=1,2,...N
- 這里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ù) sign()sign()的意義是將正數(shù)判別為1,負(fù)數(shù)判別為-1,最終達(dá)到分類的目的。如圖:
參數(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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 梯度下降法、随机梯度下降法、批量梯度下降
- 下一篇: 提升树算法总结(一)