GBDT：梯度提升決策樹(shù)
綜述
GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Tree)，是一種迭代的決策樹(shù)算法，該算法由多棵決策樹(shù)組成，所有樹(shù)的結(jié)論累加起來(lái)做最終答案。它在被提出之初就和SVM一起被認(rèn)為是泛化能力較強(qiáng)的算法。
GBDT中的樹(shù)是回歸樹(shù)(不是分類(lèi)樹(shù))，GBDT用來(lái)做回歸預(yù)測(cè)，調(diào)整后也可以用于分類(lèi)。
GBDT的思想使其具有天然優(yōu)勢(shì)可以發(fā)現(xiàn)多種有區(qū)分性的特征以及特征組合。業(yè)界中，F(xiàn)acebook使用其來(lái)自動(dòng)發(fā)現(xiàn)有效的特征、特征組合，來(lái)作為L(zhǎng)R模型中的特征，以提高 CTR預(yù)估(Click-Through Rate Prediction)的準(zhǔn)確性(詳見(jiàn)參考文獻(xiàn)5、6);GBDT在淘寶的搜索及預(yù)測(cè)業(yè)務(wù)上也發(fā)揮了重要作用(詳見(jiàn)參考文獻(xiàn)7)。
一、Regression Decision Tree：回歸樹(shù)
回歸樹(shù)總體流程類(lèi)似于分類(lèi)樹(shù)，區(qū)別在于，回歸樹(shù)的每一個(gè)節(jié)點(diǎn)都會(huì)得一個(gè)預(yù)測(cè)值，以年齡為例，該預(yù)測(cè)值等于屬于這個(gè)節(jié)點(diǎn)的所有人年齡的平均值。分枝時(shí)窮舉每一個(gè)feature的每個(gè)閾值找最好的分割點(diǎn)，但衡量最好的標(biāo)準(zhǔn)不再是最大熵，而是最小化平方誤差。也就是被預(yù)測(cè)出錯(cuò)的人數(shù)越多，錯(cuò)的越離譜，平方誤差就越大，通過(guò)最小化平方誤差能夠找到最可靠的分枝依據(jù)。分枝直到每個(gè)葉子節(jié)點(diǎn)上人的年齡都唯一或者達(dá)到預(yù)設(shè)的終止條件(如葉子個(gè)數(shù)上限)，若最終葉子節(jié)點(diǎn)上人的年齡不唯一，則以該節(jié)點(diǎn)上所有人的平均年齡做為該葉子節(jié)點(diǎn)的預(yù)測(cè)年齡。(引用自一篇博客，詳見(jiàn)參考文獻(xiàn)3)
回歸樹(shù)示例
回歸樹(shù)算法如下圖(截圖來(lái)自《統(tǒng)計(jì)學(xué)習(xí)方法》5.5.1 CART生成)：
回歸樹(shù)生成算法
二、Boosting Decision Tree：提升樹(shù)算法
提升樹(shù)是迭代多棵回歸樹(shù)來(lái)共同決策。當(dāng)采用平方誤差損失函數(shù)時(shí)，每一棵回歸樹(shù)學(xué)習(xí)的是之前所有樹(shù)的結(jié)論和殘差，擬合得到一個(gè)當(dāng)前的殘差回歸樹(shù)，殘差的意義如公式：殘差 = 真實(shí)值 – 預(yù)測(cè)值 。提升樹(shù)即是整個(gè)迭代過(guò)程生成的回歸樹(shù)的累加。
舉個(gè)例子，參考自一篇博客(參考文獻(xiàn) 4)，該博客舉出的例子較直觀地展現(xiàn)出多棵決策樹(shù)線性求和過(guò)程以及殘差的意義。
訓(xùn)練一個(gè)提升樹(shù)模型來(lái)預(yù)測(cè)年齡：
訓(xùn)練集是4個(gè)人，A，B，C，D年齡分別是14，16，24，26。樣本中有購(gòu)物金額、上網(wǎng)時(shí)長(zhǎng)、經(jīng)常到百度知道提問(wèn)等特征。提升樹(shù)的過(guò)程如下：
提升樹(shù)示例
該例子很直觀的能看到，預(yù)測(cè)值等于所有樹(shù)值得累加，如A的預(yù)測(cè)值 = 樹(shù)1左節(jié)點(diǎn) 值 15 + 樹(shù)2左節(jié)點(diǎn) -1 = 14。
因此，給定當(dāng)前模型 fm-1(x)，只需要簡(jiǎn)單的擬合當(dāng)前模型的殘差。現(xiàn)將回歸問(wèn)題的提升樹(shù)算法敘述如下：
提升樹(shù)算法
三、Gradient Boosting Decision Tree：梯度提升決策樹(shù)
提升樹(shù)利用加法模型和前向分步算法實(shí)現(xiàn)學(xué)習(xí)的優(yōu)化過(guò)程。當(dāng)損失函數(shù)時(shí)平方損失和指數(shù)損失函數(shù)時(shí)，每一步的優(yōu)化很簡(jiǎn)單，如平方損失函數(shù)學(xué)習(xí)殘差回歸樹(shù)。
損失函數(shù)列表
但對(duì)于一般的損失函數(shù)，往往每一步優(yōu)化沒(méi)那么容易，如上圖中的絕對(duì)值損失函數(shù)和Huber損失函數(shù)。針對(duì)這一問(wèn)題，F(xiàn)reidman提出了梯度提升算法：利用最速下降的近似方法，即利用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值，作為回歸問(wèn)題中提升樹(shù)算法的殘差的近似值，擬合一個(gè)回歸樹(shù)。(注：鄙人私以為，與其說(shuō)負(fù)梯度作為殘差的近似值，不如說(shuō)殘差是負(fù)梯度的一種特例)算法如下(截圖來(lái)自《The Elements of Statistical Learning》)：
算法步驟解釋?zhuān)?/p>
1、初始化，估計(jì)使損失函數(shù)極小化的常數(shù)值，它是只有一個(gè)根節(jié)點(diǎn)的樹(shù)，即ganma是一個(gè)常數(shù)值。
2、
(a)計(jì)算損失函數(shù)的負(fù)梯度在當(dāng)前模型的值，將它作為殘差的估計(jì)
(b)估計(jì)回歸樹(shù)葉節(jié)點(diǎn)區(qū)域，以擬合殘差的近似值
(c)利用線性搜索估計(jì)葉節(jié)點(diǎn)區(qū)域的值，使損失函數(shù)極小化
(d)更新回歸樹(shù)
3、得到輸出的最終模型 f(x)
四、重要參數(shù)的意義及設(shè)置
推薦GBDT樹(shù)的深度：6;(橫向比較：DecisionTree/RandomForest需要把樹(shù)的深度調(diào)到15或更高)
以下摘自知乎上的一個(gè)問(wèn)答(詳見(jiàn)參考文獻(xiàn)8)，問(wèn)題和回復(fù)都很好的闡述了這個(gè)參數(shù)設(shè)置的數(shù)學(xué)原理。
【問(wèn)】xgboost/gbdt在調(diào)參時(shí)為什么樹(shù)的深度很少就能達(dá)到很高的精度?
用xgboost/gbdt在在調(diào)參的時(shí)候把樹(shù)的最大深度調(diào)成6就有很高的精度了。但是用DecisionTree/RandomForest的時(shí)候需要把樹(shù)的深度調(diào)到15或更高。用RandomForest所需要的樹(shù)的深度和DecisionTree一樣我能理解，因?yàn)樗怯胋agging的方法把DecisionTree組合在一起，相當(dāng)于做了多次DecisionTree一樣。但是xgboost/gbdt僅僅用梯度上升法就能用6個(gè)節(jié)點(diǎn)的深度達(dá)到很高的預(yù)測(cè)精度，使我驚訝到懷疑它是黑科技了。請(qǐng)問(wèn)下xgboost/gbdt是怎么做到的?它的節(jié)點(diǎn)和一般的DecisionTree不同嗎?
【答】
這是一個(gè)非常好的問(wèn)題，題主對(duì)各算法的學(xué)習(xí)非常細(xì)致透徹，問(wèn)的問(wèn)題也關(guān)系到這兩個(gè)算法的本質(zhì)。這個(gè)問(wèn)題其實(shí)并不是一個(gè)很簡(jiǎn)單的問(wèn)題，我嘗試用我淺薄的機(jī)器學(xué)習(xí)知識(shí)對(duì)這個(gè)問(wèn)題進(jìn)行回答。
一句話的解釋?zhuān)瑏?lái)自周志華老師的機(jī)器學(xué)習(xí)教科書(shū)( 機(jī)器學(xué)習(xí)-周志華)：Boosting主要關(guān)注降低偏差，因此Boosting能基于泛化性能相當(dāng)弱的學(xué)習(xí)器構(gòu)建出很強(qiáng)的集成;Bagging主要關(guān)注降低方差，因此它在不剪枝的決策樹(shù)、神經(jīng)網(wǎng)絡(luò)等學(xué)習(xí)器上效用更為明顯。
隨機(jī)森林(random forest)和GBDT都是屬于集成學(xué)習(xí)(ensemble learning)的范疇。集成學(xué)習(xí)下有兩個(gè)重要的策略Bagging和Boosting。
Bagging算法是這樣做的：每個(gè)分類(lèi)器都隨機(jī)從原樣本中做有放回的采樣，然后分別在這些采樣后的樣本上訓(xùn)練分類(lèi)器，然后再把這些分類(lèi)器組合起來(lái)。簡(jiǎn)單的多數(shù)投票一般就可以。其代表算法是隨機(jī)森林。Boosting的意思是這樣，他通過(guò)迭代地訓(xùn)練一系列的分類(lèi)器，每個(gè)分類(lèi)器采用的樣本分布都和上一輪的學(xué)習(xí)結(jié)果有關(guān)。其代表算法是AdaBoost, GBDT。
其實(shí)就機(jī)器學(xué)習(xí)算法來(lái)說(shuō)，其泛化誤差可以分解為兩部分，偏差(bias)和方差(variance)。這個(gè)可由下圖的式子導(dǎo)出(這里用到了概率論公式D(X)=E(X^2)-[E(X)]^2)。偏差指的是算法的期望預(yù)測(cè)與真實(shí)預(yù)測(cè)之間的偏差程度，反應(yīng)了模型本身的擬合能力;方差度量了同等大小的訓(xùn)練集的變動(dòng)導(dǎo)致學(xué)習(xí)性能的變化，刻畫(huà)了數(shù)據(jù)擾動(dòng)所導(dǎo)致的影響。這個(gè)有點(diǎn)兒繞，不過(guò)你一定知道過(guò)擬合。
如下圖所示，當(dāng)模型越復(fù)雜時(shí)，擬合的程度就越高，模型的訓(xùn)練偏差就越小。但此時(shí)如果換一組數(shù)據(jù)可能模型的變化就會(huì)很大，即模型的方差很大。所以模型過(guò)于復(fù)雜的時(shí)候會(huì)導(dǎo)致過(guò)擬合。
當(dāng)模型越簡(jiǎn)單時(shí)，即使我們?cè)贀Q一組數(shù)據(jù)，最后得出的學(xué)習(xí)器和之前的學(xué)習(xí)器的差別就不那么大，模型的方差很小。還是因?yàn)槟Ｐ秃?jiǎn)單，所以偏差會(huì)很大。
模型復(fù)雜度與偏差方差的關(guān)系圖
也就是說(shuō)，當(dāng)我們訓(xùn)練一個(gè)模型時(shí)，偏差和方差都得照顧到，漏掉一個(gè)都不行。
對(duì)于Bagging算法來(lái)說(shuō)，由于我們會(huì)并行地訓(xùn)練很多不同的分類(lèi)器的目的就是降低這個(gè)方差(variance) ,因?yàn)椴捎昧讼嗷オ?dú)立的基分類(lèi)器多了以后，h的值自然就會(huì)靠近.所以對(duì)于每個(gè)基分類(lèi)器來(lái)說(shuō)，目標(biāo)就是如何降低這個(gè)偏差(bias),所以我們會(huì)采用深度很深甚至不剪枝的決策樹(shù)。
對(duì)于Boosting來(lái)說(shuō)，每一步我們都會(huì)在上一輪的基礎(chǔ)上更加擬合原數(shù)據(jù)，所以可以保證偏差(bias),所以對(duì)于每個(gè)基分類(lèi)器來(lái)說(shuō)，問(wèn)題就在于如何選擇variance更小的分類(lèi)器，即更簡(jiǎn)單的分類(lèi)器，所以我們選擇了深度很淺的決策樹(shù)。
五、拓展
最近引起關(guān)注的一個(gè)Gradient Boosting算法：xgboost，在計(jì)算速度和準(zhǔn)確率上，較GBDT有明顯的提升。xgboost 的全稱(chēng)是eXtreme Gradient Boosting，它是Gradient Boosting Machine的一個(gè)c++實(shí)現(xiàn)，作者為正在華盛頓大學(xué)研究機(jī)器學(xué)習(xí)的大牛陳天奇 。xgboost最大的特點(diǎn)在于，它能夠自動(dòng)利用CPU的多線程進(jìn)行并行，同時(shí)在算法上加以改進(jìn)提高了精度。它的處女秀是Kaggle的 希格斯子信號(hào)識(shí)別競(jìng)賽，因?yàn)槌霰姷男逝c較高的預(yù)測(cè)準(zhǔn)確度在比賽論壇中引起了參賽選手的廣泛關(guān)注。值得我們?cè)贕BDT的基礎(chǔ)上對(duì)其進(jìn)一步探索學(xué)習(xí)。
參考文獻(xiàn)
1、《The Elements of Statistical Learning》
2、《統(tǒng)計(jì)學(xué)習(xí)方法》
3、 分類(lèi)樹(shù)與回歸樹(shù)的區(qū)別
7、 為什么xgboost/gbdt在調(diào)參時(shí)為什么樹(shù)的深度很少就能達(dá)到很高的精度?
