GBDT和XGBoost的區(qū)別是什么

1 傳統(tǒng)GBDT以CART作為基分類器，xgboost還支持線性分類器，這個時候xgboost相當(dāng)于帶L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）。

2 傳統(tǒng)GBDT在優(yōu)化時只用到一階導(dǎo)數(shù)信息，xgboost則對代價函數(shù)進(jìn)行了二階泰勒展開，同時用到了一階和二階導(dǎo)數(shù)。順便提一下，xgboost工具支持自定義代價函數(shù)，只要函數(shù)可一階和二階求導(dǎo)。

3 xgboost在代價函數(shù)里加入了正則項，用于控制模型的復(fù)雜度。正則項里包含了樹的葉子節(jié)點個數(shù)、每個葉子節(jié)點上輸出的score的L2模的平方和。從Bias-variance tradeoff角度來講，正則項降低了模型的variance，使學(xué)習(xí)出來的模型更加簡單，防止過擬合，這也是xgboost優(yōu)于傳統(tǒng)GBDT的一個特性。(關(guān)于這個點，接下來詳細(xì)解釋)

4 Shrinkage（縮減），相當(dāng)于學(xué)習(xí)速率（xgboost中的eta）。xgboost在進(jìn)行完一次迭代后，會將葉子節(jié)點的權(quán)重乘上該系數(shù)，主要是為了削弱每棵樹的影響，讓后面有更大的學(xué)習(xí)空間。實際應(yīng)用中，一般把eta設(shè)置得小一點，然后迭代次數(shù)設(shè)置得大一點。（補(bǔ)充：傳統(tǒng)GBDT的實現(xiàn)也有學(xué)習(xí)速率）

5 列抽樣（column subsampling）即特征抽樣。xgboost借鑒了隨機(jī)森林的做法，支持列抽樣，不僅能降低過擬合，還能減少計算，這也是xgboost異于傳統(tǒng)gbdt的一個特性。

6 對缺失值的處理。對于特征的值有缺失的樣本，xgboost可以自動學(xué)習(xí)出它的分裂方向。

7 xgboost工具支持并行。boosting不是一種串行的結(jié)構(gòu)嗎?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能進(jìn)行下一次迭代的（第t次迭代的代價函數(shù)里包含了前面t-1次迭代的預(yù)測值）。xgboost的并行是在特征粒度上的。

我們知道，決策樹的學(xué)習(xí)最耗時的一個步驟就是對特征的值進(jìn)行排序（因為要確定最佳分割點），xgboost在訓(xùn)練之前，預(yù)先對數(shù)據(jù)進(jìn)行了排序，然后保存為block結(jié)構(gòu)，后面的迭代中重復(fù)地使用這個結(jié)構(gòu)，大大減小計算量。這個block結(jié)構(gòu)也使得并行成為了可能，在進(jìn)行節(jié)點的分裂時，需要計算每個特征的增益，最終選增益最大的那個特征去做分裂，那么各個特征的增益計算就可以開多線程進(jìn)行。

可并行的近似直方圖算法。樹節(jié)點在進(jìn)行分裂時，我們需要計算每個特征的每個分割點對應(yīng)的增益，即用貪心法枚舉所有可能的分割點。當(dāng)數(shù)據(jù)無法一次載入內(nèi)存或者在分布式情況下，貪心算法效率就會變得很低，所以xgboost還提出了一種可并行的近似直方圖算法，用于高效地生成候選的分割點。

補(bǔ)充

xgboost/gbdt在調(diào)參時為什么樹的深度很少就能達(dá)到很高的精度？用xgboost/gbdt在在調(diào)參的時候把樹的最大深度調(diào)成6就有很高的精度了。但是用DecisionTree/RandomForest的時候需要把樹的深度調(diào)到15或更高。用RandomForest所需要的樹的深度和DecisionTree一樣我能理解，因為它是用bagging的方法把DecisionTree組合在一起，相當(dāng)于做了多次DecisionTree一樣。但是xgboost/gbdt僅僅用梯度上升法就能用6個節(jié)點的深度達(dá)到很高的預(yù)測精度，使我驚訝到懷疑它是黑科技了。請問下xgboost/gbdt是怎么做到的？它的節(jié)點和一般的DecisionTree不同嗎？

這是一個非常好的問題，題主對各算法的學(xué)習(xí)非常細(xì)致透徹，問的問題也關(guān)系到這兩個算法的本質(zhì)。這個問題其實并不是一個很簡單的問題，我嘗試用我淺薄的機(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。

其實就機(jī)器學(xué)習(xí)算法來說，其泛化誤差可以分解為兩部分，偏差（bias)和方差(variance)。這個可由下圖的式子導(dǎo)出（這里用到了概率論公式D(X)=E(X^2)-[E(X)]^2）。偏差指的是算法的期望預(yù)測與真實預(yù)測之間的偏差程度，反應(yīng)了模型本身的擬合能力；方差度量了同等大小的訓(xùn)練集的變動導(dǎo)致學(xué)習(xí)性能的變化，刻畫了數(shù)據(jù)擾動所導(dǎo)致的影響。這個有點兒繞，不過你一定知道過擬合。

如下圖所示，當(dāng)模型越復(fù)雜時，擬合的程度就越高，模型的訓(xùn)練偏差就越小。但此時如果換一組數(shù)據(jù)可能模型的變化就會很大，即模型的方差很大。所以模型過于復(fù)雜的時候會導(dǎo)致過擬合。