綜述
GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)濒持，是一種迭代的決策樹算法肉瓦，該算法由多棵決策樹組成疮绷，所有樹的結論累加起來做最終答案耸峭。它在被提出之初就和SVM一起被認為是泛化能力較強的算法茉帅。
GBDT中的樹是回歸樹（不是分類樹）处窥，GBDT用來做回歸預測重付，調(diào)整后也可以用于分類。
GBDT的思想使其具有天然優(yōu)勢可以發(fā)現(xiàn)多種有區(qū)分性的特征以及特征組合障贸。業(yè)界中错森，F(xiàn)acebook使用其來自動發(fā)現(xiàn)有效的特征、特征組合篮洁，來作為LR模型中的特征涩维，以提高 CTR預估（Click-Through Rate Prediction）的準確性（詳見參考文獻5、6）袁波；GBDT在淘寶的搜索及預測業(yè)務上也發(fā)揮了重要作用（詳見參考文獻7）瓦阐。
一、Regression Decision Tree：回歸樹
回歸樹總體流程類似于分類樹篷牌，區(qū)別在于睡蟋，回歸樹的每一個節(jié)點都會得一個預測值，以年齡為例枷颊，該預測值等于屬于這個節(jié)點的所有人年齡的平均值戳杀。分枝時窮舉每一個feature的每個閾值找最好的分割點该面，但衡量最好的標準不再是最大熵，而是最小化平方誤差信卡。也就是被預測出錯的人數(shù)越多隔缀，錯的越離譜，平方誤差就越大傍菇，通過最小化平方誤差能夠找到最可靠的分枝依據(jù)猾瘸。分枝直到每個葉子節(jié)點上人的年齡都唯一或者達到預設的終止條件(如葉子個數(shù)上限)，若最終葉子節(jié)點上人的年齡不唯一丢习，則以該節(jié)點上所有人的平均年齡做為該葉子節(jié)點的預測年齡牵触。（引用自一篇博客，詳見參考文獻3）
回歸樹示例
回歸樹算法如下圖（截圖來自《統(tǒng)計學習方法》5.5.1 CART生成）：
回歸樹生成算法
二泛领、Boosting Decision Tree：提升樹算法
提升樹是迭代多棵回歸樹來共同決策荒吏。當采用平方誤差損失函數(shù)時，每一棵回歸樹學習的是之前所有樹的結論和殘差渊鞋，擬合得到一個當前的殘差回歸樹绰更，殘差的意義如公式：殘差 = 真實值 - 預測值 。提升樹即是整個迭代過程生成的回歸樹的累加锡宋。
舉個例子儡湾，參考自一篇博客（參考文獻 4），該博客舉出的例子較直觀地展現(xiàn)出多棵決策樹線性求和過程以及殘差的意義执俩。
訓練一個提升樹模型來預測年齡：
訓練集是4個人徐钠，A，B役首，C尝丐，D年齡分別是14，16衡奥，24爹袁，26。樣本中有購物金額矮固、上網(wǎng)時長失息、經(jīng)常到百度知道提問等特征。提升樹的過程如下：
提升樹示例
該例子很直觀的能看到档址，預測值等于所有樹值得累加盹兢，如A的預測值 = 樹1左節(jié)點 值 15? + 樹2左節(jié)點 -1 = 14。
因此守伸，給定當前模型 fm-1(x)绎秒，只需要簡單的擬合當前模型的殘差。現(xiàn)將回歸問題的提升樹算法敘述如下：
提升樹算法
三尼摹、Gradient Boosting Decision Tree：梯度提升決策樹
提升樹利用加法模型和前向分步算法實現(xiàn)學習的優(yōu)化過程替裆。當損失函數(shù)時平方損失和指數(shù)損失函數(shù)時校辩，每一步的優(yōu)化很簡單，如平方損失函數(shù)學習殘差回歸樹辆童。
損失函數(shù)列表
但對于一般的損失函數(shù)，往往每一步優(yōu)化沒那么容易惠赫，如上圖中的絕對值損失函數(shù)和Huber損失函數(shù)把鉴。針對這一問題，F(xiàn)reidman提出了梯度提升算法：利用最速下降的近似方法儿咱，即利用損失函數(shù)的負梯度在當前模型的值庭砍，作為回歸問題中提升樹算法的殘差的近似值，擬合一個回歸樹混埠。（注：鄙人私以為怠缸，與其說負梯度作為殘差的近似值，不如說殘差是負梯度的一種特例）算法如下（截圖來自《The Elements of Statistical Learning》）：
梯度提升決策樹算法
算法步驟解釋：
1钳宪、初始化揭北，估計使損失函數(shù)極小化的常數(shù)值，它是只有一個根節(jié)點的樹吏颖，即ganma是一個常數(shù)值搔体。
2、
（a）計算損失函數(shù)的負梯度在當前模型的值半醉，將它作為殘差的估計
（b）估計回歸樹葉節(jié)點區(qū)域疚俱，以擬合殘差的近似值
（c）利用線性搜索估計葉節(jié)點區(qū)域的值，使損失函數(shù)極小化
（d）更新回歸樹
3缩多、得到輸出的最終模型 f(x)
四呆奕、重要參數(shù)的意義及設置
推薦GBDT樹的深度：6；（橫向比較：DecisionTree/RandomForest需要把樹的深度調(diào)到15或更高）
以下摘自知乎上的一個問答（詳見參考文獻8）衬吆，問題和回復都很好的闡述了這個參數(shù)設置的數(shù)學原理梁钾。
【問】xgboost/gbdt在調(diào)參時為什么樹的深度很少就能達到很高的精度？
用xgboost/gbdt在在調(diào)參的時候把樹的最大深度調(diào)成6就有很高的精度了咆槽。但是用DecisionTree/RandomForest的時候需要把樹的深度調(diào)到15或更高陈轿。用RandomForest所需要的樹的深度和DecisionTree一樣我能理解，因為它是用bagging的方法把DecisionTree組合在一起秦忿，相當于做了多次DecisionTree一樣麦射。但是xgboost/gbdt僅僅用梯度上升法就能用6個節(jié)點的深度達到很高的預測精度，使我驚訝到懷疑它是黑科技了灯谣。請問下xgboost/gbdt是怎么做到的潜秋？它的節(jié)點和一般的DecisionTree不同嗎？
【答】
這是一個非常好的問題胎许，題主對各算法的學習非常細致透徹峻呛，問的問題也關系到這兩個算法的本質(zhì)罗售。這個問題其實并不是一個很簡單的問題，我嘗試用我淺薄的機器學習知識對這個問題進行回答钩述。
一句話的解釋寨躁，來自周志華老師的機器學習教科書（ 機器學習-周志華）：Boosting主要關注降低偏差，因此Boosting能基于泛化性能相當弱的學習器構建出很強的集成牙勘；Bagging主要關注降低方差职恳，因此它在不剪枝的決策樹、神經(jīng)網(wǎng)絡等學習器上效用更為明顯方面。
隨機森林(random forest)和GBDT都是屬于集成學習（ensemble learning)的范疇放钦。集成學習下有兩個重要的策略Bagging和Boosting。
Bagging算法是這樣做的：每個分類器都隨機從原樣本中做有放回的采樣恭金，然后分別在這些采樣后的樣本上訓練分類器操禀，然后再把這些分類器組合起來。簡單的多數(shù)投票一般就可以横腿。其代表算法是隨機森林颓屑。Boosting的意思是這樣，他通過迭代地訓練一系列的分類器蔑水，每個分類器采用的樣本分布都和上一輪的學習結果有關邢锯。其代表算法是AdaBoost, GBDT。
其實就機器學習算法來說搀别，其泛化誤差可以分解為兩部分丹擎，偏差（bias)和方差(variance)。這個可由下圖的式子導出（這里用到了概率論公式D(X)=E(X^2)-[E(X)]^2）歇父。偏差指的是算法的期望預測與真實預測之間的偏差程度蒂培，反應了模型本身的擬合能力；方差度量了同等大小的訓練集的變動導致學習性能的變化榜苫，刻畫了數(shù)據(jù)擾動所導致的影響护戳。這個有點兒繞，不過你一定知道過擬合垂睬。
如下圖所示媳荒，當模型越復雜時，擬合的程度就越高驹饺，模型的訓練偏差就越小钳枕。但此時如果換一組數(shù)據(jù)可能模型的變化就會很大，即模型的方差很大赏壹。所以模型過于復雜的時候會導致過擬合鱼炒。
當模型越簡單時，即使我們再換一組數(shù)據(jù)蝌借，最后得出的學習器和之前的學習器的差別就不那么大昔瞧，模型的方差很小指蚁。還是因為模型簡單，所以偏差會很大自晰。
模型復雜度與偏差方差的關系圖
也就是說凝化，當我們訓練一個模型時，偏差和方差都得照顧到缀磕，漏掉一個都不行缘圈。
對于Bagging算法來說，由于我們會并行地訓練很多不同的分類器的目的就是降低這個方差(variance) ,因為采用了相互獨立的基分類器多了以后袜蚕，h的值自然就會靠近.所以對于每個基分類器來說，目標就是如何降低這個偏差（bias),所以我們會采用深度很深甚至不剪枝的決策樹绢涡。
對于Boosting來說牲剃，每一步我們都會在上一輪的基礎上更加擬合原數(shù)據(jù)，所以可以保證偏差（bias）,所以對于每個基分類器來說雄可，問題就在于如何選擇variance更小的分類器凿傅，即更簡單的分類器，所以我們選擇了深度很淺的決策樹数苫。
五聪舒、拓展
最近引起關注的一個Gradient Boosting算法：xgboost，在計算速度和準確率上虐急，較GBDT有明顯的提升箱残。xgboost 的全稱是eXtreme Gradient Boosting，它是Gradient Boosting Machine的一個c++實現(xiàn)止吁，作者為正在華盛頓大學研究機器學習的大牛陳天奇 被辑。xgboost最大的特點在于，它能夠自動利用CPU的多線程進行并行敬惦，同時在算法上加以改進提高了精度盼理。它的處女秀是Kaggle的 希格斯子信號識別競賽，因為出眾的效率與較高的預測準確度在比賽論壇中引起了參賽選手的廣泛關注俄删。值得我們在GBDT的基礎上對其進一步探索學習宏怔。
