GBDT與Adaboost的區別與聯繫

02-04

隔了這麼久才更新博文，因為最近遇到了一些事情，雖然也都不是什麼大事，但累加在一起還是會擾亂人的意志。年關將近，大家似乎都變得特別浮躁，偶爾能不小心看到同事與獵頭聯繫的痕迹，於是安慰自己這不是我能控制的，做好自己的事就好了，但心裡總有一點不是滋味。第一份工作我希望自己能夠呆在一個很有競爭力的團隊，抱著學習的態度老老實實地呆兩年，向其他互聯網公司的同學了解了一下，似乎大家都過的不是很滿意，無法做自己想做的東西。還是積極一點吧，只要公司在向上發展，團隊總會越來越大，學習的地方也會越來越多的。

回到正題，關於GBDT與Adaboost的區別與聯繫，它們都屬於boosting提升方法，只是損失函數不同：AdaBoost 是通過提升錯分數據點的權重來定位模型的不足，而Gradient Boosting是通過算梯度來定位模型的不足。

boosting提升方法

Adaboost

Adaboost的難點在於如何得到學習器的權重 $alpha_{t}$ 以及下一時刻的權重分布 $D_{t+1}$ 。

當第 $t$ 個基分類器產生後，我們應該使得其在數據集第 $t$ 輪樣本權重基礎上的指數損失最小，即

$begin{align} l_{exp}(alpha_{t}h_{t}|D_{t})&=E_{x~D_{t}}[e^{-f(x)alpha_{t}h_{t}(x)}] &=E_{x~D_{t}}[e^{-alpha_{t}}I(f(x)=h_{t}(x))+e^{alpha_{t}}I(f(x) ne h_{t}(x))] &=e^{-alpha_{t}}P_{x~D_{t}}(f(x)=h_{t}(x))+e^{alpha_{t}}P_{x~D_{t}}(f(x) ne h_{t}(x)) &=e^{-alpha_{t}}(1-epsilon_{t})+e^{alpha_{t}}epsilon_{t} end{align}$

對 $alpha_{t}$ 求導可得

$frac{partial l_{exp}(alpha_{t}h_{t}|D_{t})}{partial alpha_{t}}=-e^{-alpha^{t}}(1-epsilon_{t})+e^{alpha^{t}}epsilon_{t}$

使其等於 $0$ 後得到

$alpha_{t}=frac{1}{2}ln(frac{1-epsilon_{t}}{epsilon_{t}})$

那訓練樣本的權重分布 $D_{t+1}$ 應該怎麼變化呢?

$begin{align} D_{t+1}(x)&=frac{D(x)e^{-f(x)H_{t}(x)}}{E_{x~D}[e^{-f(x)H_{t}(x)}]} &=frac{D(x)e^{-f(x)H_{t-1}(x)}e^{-f(x)alpha_{t}h_{t}(x)}}{E_{x~D}[e^{-f(x)H_{t}(x)}]} &=D_{t}(x)cdot e^{-f(x)alpha_{t}h_{t}(x)}frac{E_{x~D}[e^{-f(x)H_{t-1}(x)}]}{E_{x~D}[e^{-f(x)H_{t}(x)}]} end{align}$

從上面的式子可以看出，由於 $alpha_t>0$ ，當樣本上一次被誤分類時，其下一次的權重會變大；而當樣本上一次被分類正確時，其下一次的權重會變小，因此誤分類樣本在下一輪學習中起到的作用更大。而後半部分看成一個常數，實際上對權重分布並沒有什麼影響。

GBDT

由於我一直以為GBDT每一輪學習的是上一輪的殘差，這讓我走了不少彎路，因此一開始直接看公式推導非常困惑，為什麼用負梯度就可以代替殘差呢？直到我看到了《GBDT梯度提升決策樹的簡單推導》。

GBDT分為兩種：

（1）殘差版本　
殘差其實就是真實值和預測值之間的差值，在學習的過程中，首先學習一顆回歸樹，然後將「真實值-預測值」得到殘差，再把殘差作為一個學習目標，學習下一棵回歸樹，依次類推，直到殘差小於某個接近0的閥值或回歸樹數目達到某一閥值。其核心思想是每輪通過擬合殘差來降低損失函數。總的來說，第一棵樹是正常的，之後所有的樹的決策全是由殘差來決定；
（2）梯度版本
與殘差版本把GBDT說成一個殘差迭代樹，認為每一棵回歸樹都在學習前N-1棵樹的殘差不同，Gradient版本把GBDT說成一個梯度迭代樹，使用梯度下降法求解，認為每一棵回歸樹在學習前N-1棵樹的梯度下降值。總的來說兩者相同之處在於，都是迭代回歸樹，都是累加每顆樹結果作為最終結果（Multiple Additive Regression Tree)，每棵樹都在學習前N-1棵樹尚存的不足，從總體流程和輸入輸出上兩者是沒有區別的。

兩者的不同主要在於每步迭代時，是否使用Gradient作為求解方法。前者不用Gradient而是用殘差—-殘差是全局最優值，Gradient是局部最優方向*步長，即前者每一步都在試圖讓結果變成最好，後者則每步試圖讓結果更好一點。
兩者優缺點。看起來前者更科學一點–有絕對最優方向不學，為什麼捨近求遠去估計一個局部最優方向呢？原因在於靈活性。前者最大問題是，由於它依賴殘差，cost function一般固定為反映殘差的均方差，因此很難處理純回歸問題之外的問題。而後者求解方法為梯度下降，只要可求導的cost function都可以使用。

GB演算法的步驟：

初始化模型為常數值：

$F_{0}(x)=arg,minsum_{i=1}^{n}{(y_{I},gamma)}$

2.迭代生成 $M$ 個基學習器

1.計算偽殘差

$gamma_{im}=-[frac{partial L(y_{i},F(x_{i}))}{partial F(x_{i})}]_{F(x)=F_{m-1}(x)} ,for,i=1,2,...,n$

2.基於 ${{(x_{i},gamma_{im})}}_{i=1}^{n}$ 生成基學習器 $h_{m}(x)$

3.計算最優的 $gamma_{m}$

$gamma_{m}=arg,minsum_{i=1}^{n}{L(y_{I},F_{m-1}(x_{i})+gamma h_{m}(x_i))}$

4.更新模型

$F_{m}(x)=F_{m-1}(x)+gamma_mh_m(x)$

可以看到在第三步的優化過程中，會得到這個學習器的權重，因此殘差就約等於負梯度乘以權重。

本想在下一篇中學習一下XGBOOST的一些推導和調參技巧，但有點迫不及待想進軍深度學習領域了，那就順便提一下GBDT與XGBOOST之間有什麼區別：

xgboost在目標函數中顯示的加上了正則化項，基學習為CART時，正則化項與樹的葉子節點的數量T和葉子節點的值有關；
GB中使用Loss Function對f(x)的一階導數計算出偽殘差用於學習生成fm(x)，xgboost不僅使用到了一階導數，還使用二階導數；
在尋找最佳分割點時，考慮傳統的枚舉每個特徵的所有可能分割點的貪心法效率太低，xgboost實現了一種近似的演算法。大致的思想是根據百分位法列舉幾個可能成為分割點的候選者，然後從候選者中根據上面求分割點的公式計算找出最佳的分割點；
xgboost考慮了訓練數據為稀疏值的情況，可以為缺失值或者指定的值指定分支的默認方向，這能大大提升演算法的效率，paper提到50倍；
另外xgboost在儲存和計算上也做了很多優化。

參考資料：

CART 分類與回歸樹www.jianshu.com

Adaboost 演算法www.jianshu.com

CART 分類與回歸樹www.jianshu.com

Adaboost 演算法www.jianshu.com

淺談 GBDTwww.jianshu.com

周志華-機器學習pan.baidu.com

余文毅：當我們在談論GBDT：從 AdaBoost 到 Gradient Boostingzhuanlan.zhihu.comGBDT是如何生成一棵向著梯度下降的方向的樹的?www.zhihu.com機器學習--Gradient Boost Decision Tree(&amp;amp;Treelink)blog.csdn.netGBDT 梯度提升決策樹的簡單推導blog.csdn.net一步一步理解GB、GBDT、xgboost - CSDN博客blog.csdn.net

Greedy function approximation: A gradient boosting machine.projecteuclid.org

推薦閱讀：

徐小賤民：FingercrossAI鏈接匯總zhuanlan.zhihu.com