XGBoost – A Scalable Tree Boosting System：Kaggle 競賽最常被使用的演算法之一

9 min readJul 6, 2018

此為論文整理筆記
原論文網址：http://www.kdd.org/kdd2016/papers/files/rfp0697-chenAemb.pdf

簡介

XGBoost ( Extreme Gradient Boosting ) 是基於 Gradient Boosted Decision Tree (GBDT) 改良與延伸，被應用於解決監督式學習的問題。

1. 基於 Tree Ensemble 模型

需要考慮多棵樹的參數優化問題，但是我們卻無法一次訓練所有的樹，因此會透過增量訓練 (additive training) 的方式，每一次保留原來的模型不變，並且加入一個新的函數至模型中，也就是說每一步皆會在前一步的基礎上增加一顆樹，以利修復上一顆樹的不足，有助於提升目標函數。

2. XGBoost 有別於傳統的 GBDT

選擇新增的樹、找到最好的樹以及減枝過程的方法差異。主要是透過貪心法，在樹的每層建構過程中優化目標函式的最大增益。

3. 優點以及使用方式

背後是 C++，所以速度很快，有競賽神器 ( Kaggle 競賽最常被選擇使用的演算法之一)之稱。儘管如此，雖許多隊伍都使用 XGBoost，得分的差異也非常大，涉及更多的是 XGBoost 背後的思想原理及數學模型的描述，因此只有深刻理解的人，才能發揮其最大價值。

要解決的問題

目標：在不同使用情境之下，都有很強的擴展性( scalibility )

算法優化：改善式的 tree-learning 算法：處理稀疏數據( sparse data )
系統優化：並行式和分佈式計算，使得 learning 過程比其它模型實現要快。更重要地，XGBoost 實現了核外計算 ( out-of-core computation )。

做法

1. Tree Boosting

Ensemble tree

目標函數

懲罰項是衡量模型的複雜度(懲罰複雜的模型)；GBDT 無此懲罰項的設計，故當懲罰項為 0 的時候，即為一般的 GBDT。

增量訓練 ( additive training)

每一次保留原來的模型不變，並且加入一個新的函數至模型中，也就是說每一步我們皆會在前一步的基礎上增加一顆樹，以修復上一顆樹的不足，有助於提升目標函數。

避免 overfitting 的兩個小設計
(1) shrinkage：在每一步的加強訓練之後，增加一點 weighted，有點像是learning rate 的意味。
(2) column ( feature ) subsampling：這個技巧在 RF 當中也有使用到，同時也有助於加快訓練速度。

2. split finding algorithms (劃分點查找算法)

exact greedy algorithm（貪心算法獲取最優切分點）
列舉所有可能的情形
approximate algorithm（近似算法）
提出了候選分割點概念，先通過直方圖算法獲得候選分割點的分佈情況，然後根據候選分割點將連續的特徵信息映射到不同的buckets中。
weighted quantile sketch (分佈式加權直方圖算法)
近似算法和分佈式加權算法是為了解決數據無法一次載入內存或者在分佈式情況下（貪心算法）效率低的問題。

3. system design

由於 XGBoost 是遵循上述 Boosted Tree 思想的工程實現，但同時又考慮兼顧系統優化和機器學習原理，最大化的保證可擴展性、便捷性以及準確性。

column block for parallel learning：記憶體優化
為了節省排序的時間，XGBoost 將數據存在內存單元 block 中，同時在block 採用 CSC 格式存放(compressed column format)，一次性讀入數據並排好序後，以後均可使用。
cache-aware access：快取優化
blocks for out-of-core computation：包含 block compression (按列壓縮)、block sharding (有助於平行運算時降低資料從 disk 讀取的時間)。

如何衡量該解法的好壞?

論文當中主要都是以訓練速度、樣本大小數等去做實驗設計，較少看到以提升準確度這個目標去做達成。這也與作者對於 XGBoost 的設計理念有關：還記得本篇 paper 是：A Scalable Tree Boosting System嗎？

有利於提升大樣本的訓練效率

和其他 tree boosting method 的比較

設計理念 (from 作者陳天奇)

XGBoost = SVDFeature + GBDT 的概念 (多線程的GBDT)

SVDFeature 是陳天奇在XGBoost前所寫的另一個作品：SVDFeature: A Toolkit for Feature-based Collaborative Filtering，XGBoost 把單個的樹模型和對樹的控制分得很清楚，保持易用性。

不管是 SVDFeature 或是 XGBoost，陳天奇當初在寫的時候，只是要解決他當前的問題，進而優化成更好介接的工具 (e.g. 初版的 XGBoost 用C++，後來寫了 Python 的接口)，有興趣可以看陳天奇的專訪，以下是擷取：

「我喜歡做的一件事情是把一個工具推到極限。需要能懂系統設計的東西，也要懂機器學習的知識。我現在希望能把這些系統方面的知識抽象成標準庫，然後讓別人用的時候不需要了解系統級別的知識也能得到很好的優化。我們現在已經做了一些這樣的事情，在這方面應該比現有的一些機器學習工具有一定的優勢。」

「我覺得設計一個新系統是個很有意思的事情，或者是不斷地去做一些不一樣的事情。人很多時候會陷入一個舒適區（comfort zone）裡，比如我們做完SVDFeature之後其實可以考慮用它來發一堆論文，因為在這個領域有積累就會傾向於在這方面做下去。但是至少在讀PhD或者未來更長的時間裡，需要有機會來做一些不會做的事情。比如當初我們在SVDFeature上加入樹模型，其實就是一個探索的過程。等XGBoost成熟之後，或許我也不會永遠做樹模型，可以去做一些其他的模型。就是盡量不要讓自己陷入舒適區裡，嘗試一些自己以前不能夠做的事情」

XGBoost 實作

Install (mac OS)、XGBoost 官方安裝文件：可以參考這裡

# 記得先更新 Xcode 
brew gcc  
pip install xgboost

2. Usage

3. 調參數 (最佳參數搜尋)

常見調整的參數

(1) max_depth(): 樹的深度

(2) n_estimator(): 樹的個數

(3) colsample_bytree(): 用來控制每棵隨機採樣的列數的佔比(每一列是一個特徵)

以下使用 Titanic 數據集測試調參數 ( Test acc = 0.7799 )，只牛刀小試，沒有優化到最好，參數的詳細說明可以參考這篇。

4. 視覺化：須先下載 graphviz 套件

xgb.fmap 的功用是在樹的節點上呈現變數名稱 (有助於判斷該分裂點的特徵為何)

可以透過 num_trees 的設定去看不同顆樹的分裂結果，以下是第 1 棵樹 ( num_trees = 0 )的結果：

後記

可以看到 XGBoost 是基於 GBDT 的改良，接著，建立於 XGBoost 的基礎上，以「比 XGBoost 更快」之姿出現了微軟開源的 LightGBM (2017)、以及 CatBoost (2017) ，也都在實驗結果上看到更好的表現。

但無論是哪一種，背後核心概念都是 Tree-based family，只要掌握核心概念，在使用改善的新方法實作時，就會更好延伸理解 Tree-based model 的精髓。

1. LightGBM 使用 leaf-wise tree算法，因此在迭代過程中能更快地收斂；但leaf-wise tree算法較容易過擬合。
2. CatBoost 同樣是基於 Boosting tree 的梯度提升樹模型框架，最大的特點對category 特徵的直接支持，甚至支持字符串類型的特徵。

參考來源

如果這篇文章有幫助到你，可以幫我在下方綠色的拍手圖示按5下，只要登入Google或FB，不需任何花費就能【免費支持】youmgmi 繼續創作。