【技術分享】GBDT算法-原理篇
- 2019 年 10 月 5 日
- 筆記
本文原作者：蔣凱，經授權後發佈。
導語 ：工業界機器學習大殺器解讀。
GBDT是常用的機器學習算法之一，因其出色的特徵自動組合能力和高效的運算大受歡迎。
這裡簡單介紹一下GBDT算法的原理，後續再寫一個實戰篇。
1、決策樹的分類
決策樹分為兩大類，分類樹和回歸樹。
分類樹用於分類標籤值，如晴天/陰天/霧/雨、用戶性別、網頁是否是垃圾頁面；
回歸樹用於預測實數值，如明天的溫度、用戶的年齡、網頁的相關程度；
兩者的區別：
分類樹的結果不能進行加減運算，晴天+晴天沒有實際意義；
回歸樹的結果是預測一個數值，可以進行加減運算，例如20歲+3歲=23歲。
GBDT中的決策樹是回歸樹，預測結果是一個數值，在點擊率預測方面常用GBDT，例如用戶點擊某個內容的概率。
2、GBDT概念
GBDT的全稱是Gradient Boosting Decision Tree，梯度提升決策樹。
要理解GBDT，首先就要理解這個B(Boosting)。
Boosting是一族可將弱學習器提升為強學習器的算法，屬於集成學習（ensemble learning）的範疇。Boosting方法基於這樣一種思想：對於一個複雜任務來說，將多個專家的判斷進行適當的綜合所得出的判斷，要比其中任何一個專家單獨的判斷要好。通俗地說，就是「三個臭皮匠頂個諸葛亮」的道理。
基於梯度提升算法的學習器叫做GBM(Gradient Boosting Machine)。理論上，GBM可以選擇各種不同的學習算法作為基學習器。GBDT實際上是GBM的一種情況。
為什麼梯度提升方法傾向於選擇決策樹作為基學習器呢？(也就是GB為什麼要和DT結合，形成GBDT) 決策樹可以認為是if-then規則的集合，易於理解，可解釋性強，預測速度快。同時，決策樹算法相比於其他的算法需要更少的特徵工程，比如可以不用做特徵標準化，可以很好的處理字段缺失的數據，也可以不用關心特徵間是否相互依賴等。決策樹能夠自動組合多個特徵。
不過，單獨使用決策樹算法時，有容易過擬合缺點。所幸的是，通過各種方法，抑制決策樹的複雜性，降低單顆決策樹的擬合能力，再通過梯度提升的方法集成多個決策樹，最終能夠很好的解決過擬合的問題。由此可見，梯度提升方法和決策樹學習算法可以互相取長補短，是一對完美的搭檔。
至於抑制單顆決策樹的複雜度的方法有很多，比如限制樹的最大深度、限制葉子節點的最少樣本數量、限制節點分裂時的最少樣本數量、吸收bagging的思想對訓練樣本採樣（subsample），在學習單顆決策樹時只使用一部分訓練樣本、借鑒隨機森林的思路在學習單顆決策樹時只採樣一部分特徵、在目標函數中添加正則項懲罰複雜的樹結構等。
演示例子：
考慮一個簡單的例子來演示GBDT算法原理
下面是一個二分類問題，1表示可以考慮的相親對象，0表示不考慮的相親對象
特徵維度有3個維度，分別對象 身高，金錢，顏值。
對應這個例子，訓練結果是perfect的，全部正確， 特徵權重可以看出，對應這個例子訓練結果顏值的重要度最大，看一下訓練得到的樹。
Tree 0:
Tree 1:
3、原理推導
3.1 目標函數
監督學習的關鍵概念：模型（model）、參數（parameters）、目標函數（objective function）
模型就是所要學習的條件概率分佈或者決策函數，它決定了在給定特徵向量時如何預測出目標。
參數就是我們要從數據中學習得到的內容。模型通常是由一個參數向量決定的函數。
目標函數通常定義為如下形式：
3.2 加法模型
GBDT算法可以看成是由K棵樹組成的加法模型：
如何來學習加法模型呢？
解這一優化問題，可以用前向分佈算法（forward stagewise algorithm）。因為學習的是加法模型，如果能夠從前往後，每一步只學習一個基函數及其係數（結構），逐步逼近優化目標函數，那麼就可以簡化複雜度。這一學習過程稱之為Boosting。具體地，我們從一個常量預測開始，每次學習一個新的函數，過程如下：
在第t步，這個時候目標函數可以寫為：
舉例說明，假設損失函數為平方損失（square loss），則目標函數為：
其中，稱
之為殘差（residual）。因此，使用平方損失函數時，GBDT算法的每一步在生成決策樹時只需要擬合前面的模型的殘差。
3.3 泰勒公式
定義：
泰勒公式簡單的理解，就是函數某個點的取值可以用參考點取值和n+1階導數的來表示，而且這個公式是有規律的比較好記。
根據泰勒公式把函數
在
點處二階展開，可得到如下等式：
則等式(1)可轉化為：
假設損失函數為平方損失函數，把對應的一階導數和二階導數代入等式(4)即得等式(2)。
由於函數中的常量在函數最小化的過程中不起作用，因此我們可以從等式(4)中移除掉常量項，得：
3.4 GBDT算法
一顆生成好的決策樹，假設其葉子節點個數為
，
決策樹的複雜度可以由正則項
來定義，即決策樹模型的複雜度由生成的樹的葉子節點數量和葉子節點對應的值向量的L2範數決定。
定義集合
為所有被劃分到葉子節點的訓練樣本的集合。等式(5)可以根據樹的葉子節點重新組織為T個獨立的二次函數的和：
定義
，則等式(6)可寫為：
因為一元二次函數最小值處，一階導數等於0:
此時，目標函數的值為
綜上，為了便於理解，單顆決策樹的學習過程可以大致描述為： 1. 枚舉所有可能的樹結構 q 2. 用等式(8)為每個q計算其對應的分數Obj，分數越小說明對應的樹結構越好 3. 根據上一步的結果，找到最佳的樹結構，用等式(7)為樹的每個葉子節點計算預測值
然而，可能的樹結構數量是無窮的，所以實際上我們不可能枚舉所有可能的樹結構。通常情況下，我們採用貪心策略來生成決策樹的每個節點。 1. 從深度為0的樹開始，對每個葉節點枚舉所有的可用特徵 2. 針對每個特徵，把屬於該節點的訓練樣本根據該特徵值升序排列，通過線性掃描的方式來決定該特徵的最佳分裂點，並記錄該特徵的最大收益（採用最佳分裂點時的收益） 3. 選擇收益最大的特徵作為分裂特徵，用該特徵的最佳分裂點作為分裂位置，把該節點生長出左右兩個新的葉節點，並為每個新節點關聯對應的樣本集 4. 回到第1步，遞歸執行到滿足特定條件為止
3.5 收益的計算
如何計算每次分裂的收益呢？假設當前節點記為C,分裂之後左孩子節點記為L，右孩子節點記為R，則該分裂獲得的收益定義為當前節點的目標函數值減去左右兩個孩子節點的目標函數值之和：
根據等式(8)可得：
其中，
項表示因為增加了樹的複雜性（該分裂增加了一個葉子節點）帶來的懲罰。
最後，總結一下GBDT的學習算法： 1. 算法每次迭代生成一顆新的決策樹 ; 2. 在每次迭代開始之前，計算損失函數在每個訓練樣本點的一階導數和二階導數 ; 3. 通過貪心策略生成新的決策樹，通過等式(7)計算每個葉節點對應的預測值 4. 把新生成的決策樹
添加到模型中：
保持簡單
易經中說道「易則易知，簡則易從」，就是越是簡易的東西，越是容易被理解和得到執行。很多機器學習模型都會盡量讓學習到的模型盡量簡單，盡量減少參數，越是簡單的模型，通用性越好，也是這個道理。
Xgboost和GBDT的區別：
GBDT:
GBDT它的非線性變換比較多，表達能力強，而且不需要做複雜的特徵工程和特徵變換。
GBDT的缺點也很明顯，Boost是一個串行過程，不好並行化，而且計算複雜度高，同時不太適合高維稀疏特徵；
傳統GBDT在優化時只用到一階導數信息。
Xgboost：
它 有以下幾個優良的特性：
1. 顯示的把樹模型複雜度作為正則項加到優化目標中。
2. 公式推導中用到了二階導數，用了二階泰勒展開。（GBDT用牛頓法貌似也是二階信息）
3. 實現了分裂點尋找近似算法。
4. 利用了特徵的稀疏性。
5. 數據事先排序並且以block形式存儲，有利於並行計算。
6. 基於分佈式通信框架rabit，可以運行在MPI和yarn上。（最新已經不基於rabit了）
7. 實現做了面向體系結構的優化，針對cache和內存做了性能優化。
