雖然現在深度學習的浪潮席卷了學術界和工業界，但是傳統的boosting算法仍值得學習和思考。在一些業務場景下基于樹模型的boosting算法仍然發揮着巨大的作用。本文針對這些算法做一個歸納總結，友善個人查閱。
一、Boosting
Boosting 是一類非常經典的內建學習方法，通過內建一系列的基礎模型得到加強版的模型，進而對任務有更好的結果。在這一部分我們關注兩個算法，分别是 gradient boosting 和 Newton boosting。在介紹這兩個算法之前，先簡單的回顧一下Gradient Descent 和 Newton‘s method。
用
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 表示損失函數，
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 表示參數，當第
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 次疊代時，
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost ，
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 是這次疊代的更新。這個公式對于梯度下降和牛頓法都适用，差別隻在于
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 的計算方法。經過
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 次疊代後，
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 可以寫成一個求和的形式，
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost ，
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 是初始值。
梯度下降法 使損失函數下降最快的方向是負的梯度。當第
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 次疊代時，有
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 有了方向，步長
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 一般可以通過 line search 得到，即
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 然後可以得到
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 。
牛頓法 首先
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 必須是二次可微的。牛頓法的目标是在每次疊代中通過近似求解
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 來得到
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 。在
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 處做二階泰勒展開，有
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 其中
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 是Hessian矩陣，
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 。由以上公式，可以得到
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 繼而有
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 。和梯度下降法不同的是，牛頓法的步長是1，也就不再需要line search。
上面介紹的部分是在參數空間的數值優化，而Boosting算法可以看作是在函數空間的數值優化。用
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 表示要尋找的函數，将
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 替換上面公式中的
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 就可以得到boosting算法 。如果
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 用base model
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 表示，那麼 gradient boosting 和 Newton boosting 分别是
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 兩種算法都是通過最小化
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 來得到base model。
二、基于樹模型的boosting
基于樹模型的boosting中一般都采用CART回歸樹作為基礎模型，因為無論是梯度法還是牛頓法都需要用回歸的方法拟合目标，即使任務是分類任務，但是每棵樹的目标都和梯度有關。CART每次分裂都隻分裂兩個節點，選擇CART的原因可能也是因為其簡單。樹模型最重要的就是樹結構的生成以及葉子結點的輸出。
當确定好樹結構之後，葉子結點的輸出 為
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 也就是對于落在第
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 個葉節點的樣本，使這些樣本的loss最小的
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 就是該葉子子節點的輸出值。比如如果loss函數是平方誤差，那麼
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 就是這些樣本在這棵樹的殘差的均值；如果loss是mae，那麼
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 是中位數。舉一個具體的例子，對于Poisson回歸，損失函數為
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost ，求解
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 就是最小化
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 。求導有
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 。通過使得導數為0，有
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 。
樹每次分裂的基準 為最大
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost ，也就是分裂前和分裂後的loss改變最大。
回到boosting算法，由于樹節點都是獨立的，是以loss函數可以寫成對樹節點求和的形式。對于
牛頓boosting ，有
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 進一步的，可以求的下面的公式，其中
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost ，
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 是以葉節點的輸出為
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 。将其代回原來的公式，可以得到
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 進而分裂的準則為
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 如果是
梯度boosting ，損失函數為梯度的平方和，也可以寫成根據葉節點求和的形式。最終結果為葉節點為
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost ，n為樣本數，分類的Gain是
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 但是對于梯度boosting，算出的葉節點輸出并不是最終的葉節點輸出。而是通過進一步求解
boosting算法_基于樹模型的boosting算法總結：GBDT、XGBoost 得到。但是牛頓boosting可以直接得到葉節點。
三、Gradient Boosting 和 Newton Boosting的對比
梯度boosting和牛頓boosting都是在boosting的架構下的兩種算法。梯度boosting拟合的是梯度，而牛頓boosting通過泰勒展開近似來求解最小。正是因為這兩個算法的優化目标不同，是以樹結構的分裂以及葉子結點的輸出也不同。尤其是葉子結點的輸出，牛頓boosting可以看作是同時優化樹結構和葉節點，而梯度boosting的葉節點通過進一步的求解得到，是以葉節點的輸出更準确，但是樹結構的準确性會下降。
除此之外，梯度boosting的适用範圍會更廣，因為隻需要loss 函數一階可微，但是牛頓boosting要二階可微。不過在實際應用上即使不能二階可微但可以手動設定Hession矩陣，當然這樣準确性會有所下降。
參考文獻
- Greedy Function Approximation : A Gradient Boosting Machine
2. Generalized Boosted Models : A guide to the gbm package
3. Tree Boosting With XGBoost. Why Does XGBoost Win "Every" Machine Learning Competition?
