引言
上一節(jié)中介紹了《隨機(jī)森林算法》煌贴，該算法使用bagging的方式作出一些決策樹來篮撑，同時(shí)在決策樹的學(xué)習(xí)過程中加入了更多的隨機(jī)因素狡汉。該模型可以自動(dòng)做到驗(yàn)證過程同時(shí)還可以進(jìn)行特征選擇压鉴。
這一節(jié)萌壳，我們將決策樹和AdaBoost算法結(jié)合起來，在AdaBoost中每一輪迭代摹芙，都會給數(shù)據(jù)更新一個(gè)權(quán)重灼狰，利用這個(gè)權(quán)重宛瞄，我們學(xué)習(xí)得到一個(gè)g浮禾，在這里我們得到一個(gè)決策樹，最終利用線性組合的方式得到多個(gè)決策樹組成的G份汗。
1. 加權(quán)的決策樹算法(Weighted Decision Tree Algorithm)
在引言中介紹了盈电，我們利用AdaBoost的思想，為數(shù)據(jù)賦予不同的權(quán)重杯活，而在將要介紹的Adaptive Boosted Decision Tree中匆帚，要建立加權(quán)的決策樹，所以接下來就要介紹它旁钧。
在之前含有權(quán)重的算法中吸重，權(quán)重作為衡量數(shù)據(jù)重要性的一項(xiàng)指標(biāo)互拾，用來評估訓(xùn)練誤差，如下面的公式所示：
上面的公式中嚎幸，權(quán)重是包含在誤差的公式中的颜矿，也就是說，我們想要構(gòu)造一個(gè)帶有權(quán)重的決策樹算法嫉晶，需要改造決策樹的誤差度量函數(shù)骑疆。然而換一個(gè)角度，權(quán)重也可以等效于數(shù)據(jù)的重復(fù)次數(shù)替废，重復(fù)次數(shù)越多的數(shù)據(jù)箍铭，說明其越重要。在廣義的隨機(jī)算法中椎镣，我們可以根據(jù)權(quán)重比例來進(jìn)行隨機(jī)采樣（比如诈火，如果權(quán)重比例是30%，那么采樣該數(shù)據(jù)的概率就是30%）衣陶，根據(jù)這種方式得到一組新的數(shù)據(jù)柄瑰，那么這組新的數(shù)據(jù)中的比例大概就是和權(quán)重的比例呈正比的，也就是說它能夠表達(dá)權(quán)重對于數(shù)據(jù)的意義剪况。
在AdaBoost-DTree中教沾，為了簡單起見，我們不去改變AdaBoost的框架译断，也不去修改決策樹的內(nèi)部細(xì)節(jié)授翻，而只是通過基于權(quán)重的訓(xùn)練數(shù)據(jù)的采樣來實(shí)現(xiàn)。
1.1 弱決策樹算法
在AdaBoost算法中孙咪，我們通過錯(cuò)誤率εt來計(jì)算單個(gè)的g的權(quán)重αt堪唐，那么如果我們使用決策樹作為g的時(shí)候，g是一個(gè)完全長成的樹翎蹈，該樹對整個(gè)數(shù)據(jù)集進(jìn)行細(xì)致的切分導(dǎo)致Ein=0淮菠，那么這使得εt=0，但計(jì)算得到的權(quán)重αt會變成無限大荤堪。
其意義是合陵，如果使用一個(gè)能力很強(qiáng)的樹作為g的話，那么該算法會賦予該樹無限大的權(quán)重或票數(shù)澄阳，最終得到了一棵“獨(dú)裁”的樹（因?yàn)锳daBoost的哲學(xué)意義是庶民政治拥知，就是集中多方的意見，及時(shí)有的意見可能是錯(cuò)誤的）碎赢，違背了AdaBoost的宗旨低剔。
上面的問題出在使用了所有的數(shù)據(jù)和讓樹完全長成這兩方面。針對這兩個(gè)問題，我們要通過剪枝和部分訓(xùn)練數(shù)據(jù)得到一個(gè)弱一點(diǎn)的樹襟齿。
所以實(shí)際上姻锁，AdaBoost-DTree是通過sampling的方式得到部分訓(xùn)練數(shù)據(jù)，通過剪枝的方式限制樹的高度猜欺，得到弱一點(diǎn)的決策樹屋摔。
1.2 AdaBoost-Stump
什么樣是樹才是弱決策樹呢？
我們這里限制這棵樹只有一層替梨，即決策樁(Decision Stump)钓试。這樣我們需要讓CART樹的不純度(impurity)盡可能低，學(xué)習(xí)一個(gè)決策樁副瀑。
所以弓熏，使用決策樁作為弱分類器的AdaBoost稱為AdaBoost-Stump，它是一種特殊的AdaBoost-DTree糠睡。
2. AdaBoost深入解釋和最佳化
我們回顧一下AdaBoost算法流程：
其中權(quán)重un(t+1)通過
◆t對un(t)進(jìn)行修正得到挽鞠，由于◆t是一個(gè)大于1的數(shù)，對錯(cuò)誤數(shù)據(jù)加大權(quán)重以讓算法更加重視錯(cuò)分的數(shù)據(jù)狈孔。我們可以用下面的方式來描述un(t+1)：
下面的公式是我們將un(T+1)展開信认，我們看到圖中橘色的部分∑αt·gt(xn)是G(x)中的分?jǐn)?shù)，它出現(xiàn)在AdaBoost的權(quán)重的表達(dá)式中均抽，我們稱∑αt·gt(xn)為投票分?jǐn)?shù)(voting score)嫁赏。
所以，AdaBoost里面每一個(gè)數(shù)據(jù)的權(quán)重油挥，和exp(-yn(voting score on xn))呈正比潦蝇。
2.1 投票分?jǐn)?shù)(Voting Score)和間隔(Margin)的關(guān)系
線性混合(linear blending)等價(jià)于將假設(shè)看做是特征轉(zhuǎn)換的線性模型：
其中
αt·gt(xn)如果換作是wT·φ(xn)可能就更清楚了，這與下面給出的在SVM中的margin表達(dá)式對比深寥，我們可以明白投票分?jǐn)?shù)∑αt·gt(xn)的物理意義攘乒，即可以看做是沒有正規(guī)化的邊界(margin)。
所以惋鹅，yn(voting score)是有符號的则酝、沒有正規(guī)化的邊界距離，從這個(gè)角度來說闰集，我們希望yn(voting score)越大越好沽讹，因?yàn)檫@樣的泛化能力越強(qiáng)。于是返十，exp(-yn(voting score))越小越好妥泉，那么un(T+1)越小越好椭微。
AdaBoost在迭代過程中洞坑，是讓
∑un(t)越來越小的過程，在這個(gè)過程中蝇率，逐漸達(dá)到SVM中最大分類間隔的效果迟杂。
2.2 AdaBoost誤差函數(shù)
上面解釋到了刽沾，AdaBoost在迭代學(xué)習(xí)的過程，就是希望讓∑un(t)越來越小的過程排拷，那么我們新的目標(biāo)就是最佳化∑un(T+1)：
我們可以畫出0/1錯(cuò)誤和AdaBoost誤差函數(shù)
err(s,y) = exp(-ys)的函數(shù)曲線侧漓，我們發(fā)現(xiàn)AdaBoost的誤差函數(shù)（稱為exponential error measure）實(shí)際上也是0/1錯(cuò)誤函數(shù)的上限函數(shù)，于是监氢，我們可以通過最小化該函數(shù)來起到最佳化的效果布蔗。
2.3 AdaBoost誤差函數(shù)的梯度下降求解
為了最小化AdaBoost的誤差函數(shù)Ein，我們可以將Ein函數(shù)在所在點(diǎn)的附近做泰勒展開浪腐，我們就可以發(fā)現(xiàn)在該點(diǎn)的附近可以被梯度所描述纵揍，我們希望求一個(gè)最好的方向（最大梯度相反的方向），然后在該方向上走一小步议街，這樣我們就可以做到比現(xiàn)在的函數(shù)效果好一點(diǎn)點(diǎn)泽谨，依次進(jìn)行梯度下降，最終達(dá)到最小化誤差函數(shù)的效果特漩。
現(xiàn)在我們把gt當(dāng)做方向吧雹，希望去找到這個(gè)gt（這里函數(shù)方向gt和上面介紹的最大梯度的方向向量沒有什么差別，只是表示方式有所不同而已）涂身。
我們解釋一下上面的公式：
- 我們需要找到一個(gè)新的函數(shù)雄卷，這里表示為h(xn)和步長η，將這個(gè)函數(shù)加入到表達(dá)式中去蛤售；
- 我們將第一個(gè)公式中紫色的部分合起來龙亲，簡化表示為權(quán)重un(t)；
- 將
exp(-y·η·h(xn))在原點(diǎn)處做泰勒展開悍抑，得到(1-yn·η·h(xn))鳄炉； - 然后拆成兩部分
∑un(t)和η·∑un(t)·yn·h(xn)，第一部分是Ein搜骡，第二部分就是要最小化的目標(biāo)拂盯。
我們對∑un(t)·yn·h(xn)整理一下，對于二元分類情形记靡，我們把yn和h(xn)是否同號進(jìn)行分別討論：
上面的公式中谈竿，我們特意將
∑un(t)·yn·h(xn)拆成-∑un(t)和Ein(h)的形式，這里最小化Ein對應(yīng)于AdaBoost中的A（弱學(xué)習(xí)算法）摸吠，好的弱學(xué)習(xí)算法就是對應(yīng)于梯度下降的函數(shù)方向空凸。
2.4 最佳化步長η
我們要最小化Eada，需要找到好的函數(shù)方向gt寸痢，但是得打這個(gè)gt的代價(jià)有些大呀洲，梯度下降的過程中，每走一小步，就需要計(jì)算得到一個(gè)gt道逗。如果轉(zhuǎn)換一下思路兵罢，我們現(xiàn)在已經(jīng)確定了好的gt，我們希望快速找到梯度下降的最低點(diǎn)滓窍，那么我們需要找到一個(gè)合適的最大步長η卖词。
我們這里使用貪心算法來得到最大步長η，稱為steepest decent for optimization吏夯。
讓Eada對η求偏微分此蜈，得到最陡時(shí)候的ηt，我們發(fā)現(xiàn)這時(shí)ηt等于AdaBoost的αt噪生。所以在AdaBoost中αt是在偷偷地做最佳化的工作舶替。
2.5 小結(jié)
在第二小節(jié)中，我們從另外一個(gè)角度介紹了AdaBoost算法杠园，它其實(shí)是steepest gradient decent顾瞪。
上面的式子很清楚了，我們將AdaBoost的誤差函數(shù)看做是指數(shù)誤差函數(shù)抛蚁，AdaBoost就是在這個(gè)函數(shù)上一步一步做最佳化陈醒，每一步求得一個(gè)h，并將該h當(dāng)做是gt瞧甩，決定這個(gè)gt上面要走多長的距離ηt钉跷，最終得到這個(gè)gt的票數(shù)αt。
3. 梯度提升(Gradient Boosting)
梯度提升是對AdaBoost的延伸肚逸，它不再要求誤差函數(shù)是指數(shù)誤差函數(shù)爷辙，而可能是任意一種誤差函數(shù)（因?yàn)檫@里是用梯度下降法來最佳化誤差函數(shù)，所以這里要求誤差函數(shù)是平滑的）朦促。
在這個(gè)架構(gòu)下膝晾，我們就可以使用不同的假設(shè)和模型，來解決分類或者回歸的問題务冕。
3.1 梯度提升應(yīng)用于回歸問題
梯度提升應(yīng)用于回歸問題時(shí)血当，誤差函數(shù)選中均方誤差函數(shù)。
緊接著禀忆，我們對這個(gè)誤差函數(shù)中變量s在sn處進(jìn)行一階泰勒展開的近似臊旭，我們發(fā)現(xiàn)要最小化的實(shí)際是∑h(xn)·2(sn-yn)，要讓該表達(dá)式最小箩退，需要h(xn)和(sn-yn)的方向相反：
要求解最佳化問題离熏，需要h(xn)和(sn-yn)的方向相反，而h(xn)的大小其實(shí)不是我們關(guān)系的問題戴涝，因?yàn)椴介L問題是由參數(shù)η決定的滋戳。
如果將h(xn)強(qiáng)制限制為1或者某個(gè)常數(shù)的話钻蔑，那么就得到了一個(gè)有條件的最佳化問題，增加了求解的難度胧瓜。不如我們將懲罰項(xiàng)h(xn)的平方放進(jìn)最佳化式子中（意思是，如果h(xn)越大郑什，我們就越不希望如此）府喳。
我們可以將平方式子變換一下，得到有關(guān)(h(xn)-(yn-sn))^2的式子蘑拯，所以我們要求一個(gè)帶懲罰項(xiàng)的近似函數(shù)梯度的問題钝满，就等效于求xn和余數(shù)(residual)yn-sn的回歸問題。
我們現(xiàn)在確定了gt申窘，接著我們要確定步長η弯蚜，這里我們可以將誤差函數(shù)寫成余數(shù)
(yn-sn)的形式，這是一個(gè)單變量的線性回歸問題剃法，其中輸入是用gt轉(zhuǎn)換后的數(shù)據(jù)碎捺，輸出是余數(shù)(residual)。
4. 梯度提升決策樹
綜合第三小節(jié)的步驟贷洲，我們就可以得到梯度提升決策樹的算法流程：
- 在每一次迭代過程收厨，解決一個(gè)回歸問題，這里可以用CART算法來解{xn, (yn-sn)}的回歸問題优构；
- 然后诵叁，用gt做轉(zhuǎn)換，做一個(gè){gt(xn), yn-sn}的單變量線性回歸問題钦椭；
- 更新分?jǐn)?shù)sn拧额；
- 經(jīng)過T輪迭代，得到G(x)彪腔。
這個(gè)GBDT算法可以看做是AdaBoost-DTree的回歸問題版本侥锦。
參考資料
機(jī)器學(xué)習(xí)技法課程，林軒田德挣，臺灣大學(xué)
決策樹模型組合之隨機(jī)森林與GBDT
機(jī)器學(xué)習(xí)——Gradient Boost Decision Tree(&Treelink)
轉(zhuǎn)載請注明作者Jason Ding及其出處
GitCafe博客主頁(http://jasonding1354.gitcafe.io/)
Github博客主頁(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354進(jìn)入我的博客主頁
