綜述

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一種迭代的決策樹算法，該算法由多棵決策樹組成，所有樹的結(jié)論累加起來做最終答案。它在被提出之初就和SVM一起被認(rèn)為是泛化能力較強(qiáng)的算法。
??GBDT中的樹是回歸樹（不是分類樹），GBDT用來做回歸預(yù)測，調(diào)整后也可以用于分類。
??GBDT的思想使其具有天然優(yōu)勢可以發(fā)現(xiàn)多種有區(qū)分性的特征以及特征組合。業(yè)界中，F(xiàn)acebook使用其來自動發(fā)現(xiàn)有效的特征、特征組合，來作為LR模型中的特征，以提高 CTR預(yù)估（Click-Through Rate Prediction）的準(zhǔn)確性（詳見參考文獻(xiàn)5、6）；GBDT在淘寶的搜索及預(yù)測業(yè)務(wù)上也發(fā)揮了重要作用（詳見參考文獻(xiàn)7）。

一、Regression Decision Tree：回歸樹

回歸樹總體流程類似于分類樹，區(qū)別在于，回歸樹的每一個節(jié)點(diǎn)都會得一個預(yù)測值，以年齡為例，該預(yù)測值等于屬于這個節(jié)點(diǎn)的所有人年齡的平均值。分枝時窮舉每一個feature的每個閾值找最好的分割點(diǎn)，但衡量最好的標(biāo)準(zhǔn)不再是最大熵，而是最小化平方誤差。也就是被預(yù)測出錯的人數(shù)越多，錯的越離譜，平方誤差就越大，通過最小化平方誤差能夠找到最可靠的分枝依據(jù)。分枝直到每個葉子節(jié)點(diǎn)上人的年齡都唯一或者達(dá)到預(yù)設(shè)的終止條件(如葉子個數(shù)上限)，若最終葉子節(jié)點(diǎn)上人的年齡不唯一，則以該節(jié)點(diǎn)上所有人的平均年齡做為該葉子節(jié)點(diǎn)的預(yù)測年齡。（引用自一篇博客，詳見參考文獻(xiàn)3）

回歸樹示例

??回歸樹算法如下圖（截圖來自《統(tǒng)計(jì)學(xué)習(xí)方法》5.5.1 CART生成）：

回歸樹生成算法

二、Boosting Decision Tree：提升樹算法

提升樹是迭代多棵回歸樹來共同決策。當(dāng)采用平方誤差損失函數(shù)時，每一棵回歸樹學(xué)習(xí)的是之前所有樹的結(jié)論和殘差，擬合得到一個當(dāng)前的殘差回歸樹，殘差的意義如公式：殘差 = 真實(shí)值 - 預(yù)測值 。提升樹即是整個迭代過程生成的回歸樹的累加。
??舉個例子，參考自一篇博客（參考文獻(xiàn) 4），該博客舉出的例子較直觀地展現(xiàn)出多棵決策樹線性求和過程以及殘差的意義。
??訓(xùn)練一個提升樹模型來預(yù)測年齡：
??訓(xùn)練集是4個人，A，B，C，D年齡分別是14，16，24，26。樣本中有購物金額、上網(wǎng)時長、經(jīng)常到百度知道提問等特征。提升樹的過程如下：

提升樹示例

該例子很直觀的能看到，預(yù)測值等于所有樹值得累加，如A的預(yù)測值 = 樹1左節(jié)點(diǎn) 值 15 + 樹2左節(jié)點(diǎn) -1 = 14。
??因此，給定當(dāng)前模型 fm-1(x)，只需要簡單的擬合當(dāng)前模型的殘差?，F(xiàn)將回歸問題的提升樹算法敘述如下：

提升樹算法

三、Gradient Boosting Decision Tree：梯度提升決策樹

提升樹利用加法模型和前向分步算法實(shí)現(xiàn)學(xué)習(xí)的優(yōu)化過程。當(dāng)損失函數(shù)時平方損失和指數(shù)損失函數(shù)時，每一步的優(yōu)化很簡單，如平方損失函數(shù)學(xué)習(xí)殘差回歸樹。

損失函數(shù)列表

??但對于一般的損失函數(shù)，往往每一步優(yōu)化沒那么容易，如上圖中的絕對值損失函數(shù)和Huber損失函數(shù)。針對這一問題，F(xiàn)reidman提出了梯度提升算法：利用最速下降的近似方法，即利用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值，作為回歸問題中提升樹算法的殘差的近似值，擬合一個回歸樹。（注：鄙人私以為，與其說負(fù)梯度作為殘差的近似值，不如說殘差是負(fù)梯度的一種特例）算法如下（截圖來自《The Elements of Statistical Learning》）：

梯度提升決策樹算法

算法步驟解釋：

• 1、初始化，估計(jì)使損失函數(shù)極小化的常數(shù)值，它是只有一個根節(jié)點(diǎn)的樹，即ganma是一個常數(shù)值。
• 2、
  （a）計(jì)算損失函數(shù)的負(fù)梯度在當(dāng)前模型的值，將它作為殘差的估計(jì)
  （b）估計(jì)回歸樹葉節(jié)點(diǎn)區(qū)域，以擬合殘差的近似值
  （c）利用線性搜索估計(jì)葉節(jié)點(diǎn)區(qū)域的值，使損失函數(shù)極小化
  （d）更新回歸樹
• 3、得到輸出的最終模型 f(x)

四、重要參數(shù)的意義及設(shè)置

推薦GBDT樹的深度：6；（橫向比較：DecisionTree/RandomForest需要把樹的深度調(diào)到15或更高）
??以下摘自知乎上的一個問答（詳見參考文獻(xiàn)8），問題和回復(fù)都很好的闡述了這個參數(shù)設(shè)置的數(shù)學(xué)原理。
??【問】xgboost/gbdt在調(diào)參時為什么樹的深度很少就能達(dá)到很高的精度？
??用xgboost/gbdt在在調(diào)參的時候把樹的最大深度調(diào)成6就有很高的精度了。但是用DecisionTree/RandomForest的時候需要把樹的深度調(diào)到15或更高。用RandomForest所需要的樹的深度和DecisionTree一樣我能理解，因?yàn)樗怯胋agging的方法把DecisionTree組合在一起，相當(dāng)于做了多次DecisionTree一樣。但是xgboost/gbdt僅僅用梯度上升法就能用6個節(jié)點(diǎn)的深度達(dá)到很高的預(yù)測精度，使我驚訝到懷疑它是黑科技了。請問下xgboost/gbdt是怎么做到的？它的節(jié)點(diǎn)和一般的DecisionTree不同嗎？
??【答】
??這是一個非常好的問題，題主對各算法的學(xué)習(xí)非常細(xì)致透徹，問的問題也關(guān)系到這兩個算法的本質(zhì)。這個問題其實(shí)并不是一個很簡單的問題，我嘗試用我淺薄的機(jī)器學(xué)習(xí)知識對這個問題進(jìn)行回答。
??一句話的解釋，來自周志華老師的機(jī)器學(xué)習(xí)教科書（ 機(jī)器學(xué)習(xí)-周志華）：Boosting主要關(guān)注降低偏差，因此Boosting能基于泛化性能相當(dāng)弱的學(xué)習(xí)器構(gòu)建出很強(qiáng)的集成；Bagging主要關(guān)注降低方差，因此它在不剪枝的決策樹、神經(jīng)網(wǎng)絡(luò)等學(xué)習(xí)器上效用更為明顯。
??隨機(jī)森林(random forest)和GBDT都是屬于集成學(xué)習(xí)（ensemble learning)的范疇。集成學(xué)習(xí)下有兩個重要的策略Bagging和Boosting。
??Bagging算法是這樣做的：每個分類器都隨機(jī)從原樣本中做有放回的采樣，然后分別在這些采樣后的樣本上訓(xùn)練分類器，然后再把這些分類器組合起來。簡單的多數(shù)投票一般就可以。其代表算法是隨機(jī)森林。Boosting的意思是這樣，他通過迭代地訓(xùn)練一系列的分類器，每個分類器采用的樣本分布都和上一輪的學(xué)習(xí)結(jié)果有關(guān)。其代表算法是AdaBoost, GBDT。
??其實(shí)就機(jī)器學(xué)習(xí)算法來說，其泛化誤差可以分解為兩部分，偏差（bias)和方差(variance)。這個可由下圖的式子導(dǎo)出（這里用到了概率論公式D(X)=E(X^2)-[E(X)]2）。偏差指的是算法的期望預(yù)測與真實(shí)預(yù)測之間的偏差程度，反應(yīng)了模型本身的擬合能力；方差度量了同等大小的訓(xùn)練集的變動導(dǎo)致學(xué)習(xí)性能的變化，刻畫了數(shù)據(jù)擾動所導(dǎo)致的影響。這個有點(diǎn)兒繞，不過你一定知道過擬合。
??如下圖所示，當(dāng)模型越復(fù)雜時，擬合的程度就越高，模型的訓(xùn)練偏差就越小。但此時如果換一組數(shù)據(jù)可能模型的變化就會很大，即模型的方差很大。所以模型過于復(fù)雜的時候會導(dǎo)致過擬合。
??當(dāng)模型越簡單時，即使我們再換一組數(shù)據(jù)，最后得出的學(xué)習(xí)器和之前的學(xué)習(xí)器的差別就不那么大，模型的方差很小。還是因?yàn)槟Ｐ秃唵?，所以偏差會很大?/p>

模型復(fù)雜度與偏差方差的關(guān)系圖

??也就是說，當(dāng)我們訓(xùn)練一個模型時，偏差和方差都得照顧到，漏掉一個都不行。
??對于Bagging算法來說，由于我們會并行地訓(xùn)練很多不同的分類器的目的就是降低這個方差(variance) ,因?yàn)椴捎昧讼嗷オ?dú)立的基分類器多了以后，h的值自然就會靠近.所以對于每個基分類器來說，目標(biāo)就是如何降低這個偏差（bias),所以我們會采用深度很深甚至不剪枝的決策樹。
??對于Boosting來說，每一步我們都會在上一輪的基礎(chǔ)上更加擬合原數(shù)據(jù)，所以可以保證偏差（bias）,所以對于每個基分類器來說，問題就在于如何選擇variance更小的分類器，即更簡單的分類器，所以我們選擇了深度很淺的決策樹。

五、拓展

最近引起關(guān)注的一個Gradient Boosting算法：xgboost，在計(jì)算速度和準(zhǔn)確率上，較GBDT有明顯的提升。xgboost 的全稱是eXtreme Gradient Boosting，它是Gradient Boosting Machine的一個c++實(shí)現(xiàn)，作者為正在華盛頓大學(xué)研究機(jī)器學(xué)習(xí)的大牛陳天奇 。xgboost最大的特點(diǎn)在于，它能夠自動利用CPU的多線程進(jìn)行并行，同時在算法上加以改進(jìn)提高了精度。它的處女秀是Kaggle的 希格斯子信號識別競賽，因?yàn)槌霰姷男逝c較高的預(yù)測準(zhǔn)確度在比賽論壇中引起了參賽選手的廣泛關(guān)注。值得我們在GBDT的基礎(chǔ)上對其進(jìn)一步探索學(xué)習(xí)。

參考文獻(xiàn)
1、《The Elements of Statistical Learning》
2、《統(tǒng)計(jì)學(xué)習(xí)方法》
3、 http://blog.csdn.net/puqutogether/article/details/44593647
4、 http://blog.csdn.net/suranxu007/article/details/49910323
5、 http://blog.csdn.net/lilyth_lilyth/article/details/48032119
6、《Practical Lessons from Predicting Clicks on Ads at Facebook》
7、 http://www.searchtb.com/2010/12/an-introduction-to-treelink.html
8、 https://www.zhihu.com/question/45487317