2. GBDT

對於上圖中的樣本數據X及其加標Y，生成的回歸樹定義為T1，T1會對X中每個sample有一個預測值，則T1對X樣本的所有預測值定義為y1，Y和y1的差值定義為diff1（diff1=Y-y1）；然後重新定義樣本X的加標為diff1，並以樣本X及加標diff1，生成第二棵樹定義為T2，T2對樣本X的預測值為y2，diff2定義為Y-y1-y2；依次循環直到生成第k棵樹；這一系列樹生成完成後，對新sample進行預測時，每棵樹都對sample進行預測，其預測值分別為p1，p2，p3，…，pk，則sample最終的預測值為p1+p2+p3+…+pk；

Note：GBDT中diff通常會乘以一個係數，即α*diff作為下一次的加標；類似學習率，在訓練過程中實現「小步多次」，通常最終效果更好；

GBDT運行的通用表達式如下：

其中?(0)是起始預測值，初始化為0；f1(x)是第一棵樹的預測值，?(1)=0+f1(x)；f2(x)是第二棵樹的預測值；?(2)=0+f1(x)+f2(x)，依次類推，直到?(t)=0+ f1(x)+f2(x)+…+ ft(x)，而?(t)就是GBDT對樣本的最終預測值；上圖中的Y（即Y-0），diff1和diff2分別是訓練第1,2,3棵決策樹時的label值；

每棵樹訓練時的特徵值相同，而label值不同，當前label值是通過最小化如下loss函數獲得（其中yi是樣本原始加標值）：

，即ft(x)= yi- ?(t-1) ；

3. XGBoost

GBDT中的決策樹，用的loss函數並未考慮正則化，比如葉子節點數目，葉子值的平方和等，而XGBoost中的決策樹在loss函數中添加了這兩項正則化表達式，分別是L1正則化和L2正則化；

其中T是葉子節點數目，w是每個葉子的值；XGBoost最小化以上loss函數求出ft(x)，作為當前決策樹訓練時的label，生成第t棵樹；依次循環，直到生成最後一棵樹；

求解ft(x)

將loss函數泰勒級數展開到第二階，可得到二次凸函數，便於求最小值；

帶入正則項，並求解ft(x)，即w；

以上求出了w*以後，即ft(x)，可以用以訓練第t棵樹；依次循環，直到訓練完指定的所有樹，以上即為XGBoost的主體部分；

Tips

obj*用於判斷分支

求解w*後，帶回到loss函數中得到obj*；該公式可作為判斷在樹的生成過程中是否分支的公式，分之後如果有增益即Gain>0，則分支，否則不分；

樹的收縮，類似學習率

和GBDT類似，「小步多次」；

特徵下採樣

類似隨機森林，防止過擬合；

精確貪婪演算法

在尋找特徵切分點時，遍歷每個值，尋找到最優點；

近似演算法

根據百分位數，推薦切分點，提高計算效率；

其它：

稀疏感知分裂查找，並行學習，緩存感知訪問，塊壓縮，塊分區；

4. lightGBM

lightGBM的主體結構和XGBoost類似，但在處理細節方面做了相應的優化修改，兩者都在升級迭代，彼此借鑒，所以一些處理細節趨於一樣；

分支：由level-wise growth 修改為leaf-wise growth；兩者都用；

直方圖：相當於下採樣，將一系列連續值分為幾個bin，提高運算效率；兩者都用；

忽略稀疏輸入：在split時忽略0值，分完後，將所有零值歸入增益大的一個分支（分別帶入兩個分支，在哪個分支的增益大，歸為哪個）；兩者都用；

GOSS：訓練階段，僅僅讓梯度大的點參與，梯度小的點不再參與到下一輪訓練（梯度小意味著已經夠好了，接下來的訓練將集中在梯度大的點上，即訓練的還不夠好的點）；僅lightGBM使用；

這樣的一個副作用是造成樣本偏差，為對沖這一缺點，在訓練時通常會隨機添加一部分梯度小的樣本點；

專一屬性合併：相關性極低的兩個稀疏屬性合併為一個屬性；僅lightGBM使用；

5. CatBoost

CatBoost和lightGBM類似，也是對細節進行了改進優化；其中最經典的是類別特徵賦值，即根據不同類別特徵，用其對應的label值計算相應數值賦給該類；

附：github代碼（決策樹，隨機森林，Adaboost，GBDT）

推薦閱讀：