GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一種迭代的決策樹算法溶褪，該算法由多棵決策樹組成食茎，所有樹的結(jié)論累加起來做最終答案。它在被提出之初就和SVM一起被認(rèn)為是泛化能力（generalization)較強(qiáng)的算法稀颁。近些年更因為被用于搜索排序的機(jī)器學(xué)習(xí)模型而引起大家關(guān)注芬失。在正式介紹GBDT之前，我想先簡單的介紹一下boosting算法匾灶。
Boosting
Boosting算法是一種把若干個分類器整合為一個分類器的方法棱烂，在boosting算法產(chǎn)生之前，還出現(xiàn)過兩種比較重要的將多個分類器整合為一個分類器的方法阶女，即boostrapping方法和bagging方法颊糜。我們先簡要介紹一下bootstrapping方法和bagging方法。
1）bootstrapping方法的主要過程：
i)重復(fù)地從一個樣本集合D中采樣n個樣本
ii)針對每次采樣的子樣本集秃踩，進(jìn)行統(tǒng)計學(xué)習(xí)衬鱼，獲得假設(shè)Hi
iii)將若干個假設(shè)進(jìn)行組合，形成最終的假設(shè)Hfinal
iv)將最終的假設(shè)用于具體的分類任務(wù)
2）bagging方法的主要過程：
i)訓(xùn)練分類器憔杨，從整體樣本集合中鸟赫，抽樣n* < N個樣本 針對抽樣的集合訓(xùn)練分類器Ci
ii)分類器進(jìn)行投票，最終的結(jié)果是分類器投票的優(yōu)勝結(jié)果
但是，上述這兩種方法抛蚤，都只是將分類器進(jìn)行簡單的組合台谢，實際上，并沒有發(fā)揮出分類器組合的威力來岁经。到了1995年对碌，F(xiàn)reund and schapire提出了現(xiàn)在的adaboost算法，其主要框架可以描述為：
i)循環(huán)迭代多次
ii)更新樣本分布
iii)尋找當(dāng)前分布下的最優(yōu)弱分類器
iv)計算弱分類器誤差率
v)聚合多次訓(xùn)練的弱分類器
數(shù)學(xué)上蒿偎，如下表達(dá)：
具體實例見這篇博文朽们。
GBDT
目前GBDT有兩個不同的描述版本，兩者各有支持者诉位，讀文獻(xiàn)時要注意區(qū)分骑脱。殘差版本把GBDT說成一個殘差迭代樹，認(rèn)為每一棵回歸樹都在學(xué)習(xí)前N-1棵樹的殘差苍糠，可以參見這篇博客叁丧；Gradient版本把GBDT說成一個梯度迭代樹，使用梯度下降法求解岳瞭，認(rèn)為每一棵回歸樹在學(xué)習(xí)前N-1棵樹的梯度下降值拥娄，之前leftnoteasy的博客中介紹的為此版本（準(zhǔn)確的說是LambdaMART中的MART為這一版本，MART實現(xiàn)則是前一版本）瞳筏。
總的來說兩者相同之處在于稚瘾，都是迭代回歸樹，都是累加每顆樹結(jié)果作為最終結(jié)果（Multiple Additive Regression Tree)姚炕，每棵樹都在學(xué)習(xí)前N-1棵樹尚存的不足摊欠，從總體流程和輸入輸出上兩者是沒有區(qū)別的；兩者的不同主要在于每步迭代時柱宦，是否使用Gradient作為求解方法些椒。前者不用Gradient而是用殘差----殘差是全局最優(yōu)值，Gradient是局部最優(yōu)方向*步長掸刊，即前者每一步都在試圖讓結(jié)果變成最好免糕，后者則每步試圖讓結(jié)果更好一點。
兩者優(yōu)缺點忧侧∈ぃ看起來前者更科學(xué)一點--有絕對最優(yōu)方向不學(xué)，為什么舍近求遠(yuǎn)去估計一個局部最優(yōu)方向呢苍柏？原因在于靈活性尼斧。前者最大問題是，由于它依賴殘差试吁，cost function一般固定為反映殘差的均方差棺棵，因此很難處理純回歸問題之外的問題楼咳。而后者求解方法為梯度下降，只要可求導(dǎo)的cost function都可以使用烛恤，所以用于排序的LambdaMART就是用的后者母怜。
文章來源：Markdown原文
