XGBoost: 你不能不知的機器學習算法

  • 2019 年 10 月 22 日
  • 筆記

XGBoost作為一個非常常用的算法，我覺得很有必要了解一下它的來龍去脈，於是抽空找了一些資料，主要包括陳天奇大佬的論文以及演講PPT，以及網絡上的一些博客文章，今天在這裡對這些知識點進行整理歸納，論文中的一些專業術語儘可能保留不翻譯，但會在下面寫出自己的理解與解釋。

資料下載：公眾號（SAMshare）回復"xgb"獲取

? Index

  • XGBoost介紹
  • XGBoost亮點
  • 梯度增強樹算法介紹
    • Regularized Learning Objective
    • Gradient Tree Boosting
    • Shrinkage and Column Subsampling
  • 分裂查找算法介紹
    • Basic Exact Greedy Algorithm
    • Approximate Algorithm
    • Weighted Quantile Sketch
    • Sparsity-aware Split Finding
  • XGBoost的系統設計
    • Column Block for Parallel Learning
    • Cache-aware Access
    • Blocks for Out-of-core Computation

? XGBoost介紹

在Paper中，作者定義XGBoost：

a scalable machine learning system for tree boosting.

XGBoost為「Extreme Gradient Boosting」的縮寫，裏面包含了關鍵字’Boosting’，意味着它是一個boosting集成算法，所以它的主要思路是將成百上千個樹模型組合起來成為一個準確率很高的模型，此模型通過不斷迭代生成新的樹。

XGBoost我們常用於監督學習，即建立一個數據模型，輸入相關特徵從而預測出目標，而這一過程，需要我們找到訓練數據最好的參數，所以我們需要定義一個目標函數，通常由訓練損失（traning loss）和正則項（regularization term）組成。

訓練損失評估了預測模型的效果，例如常用的訓練損失指標是均方誤差或是邏輯回歸的logistic loss。正則項則是控制着模型的複雜度，避免模型不被過度擬合。這兩個互相博弈（tradeoff）的指標保證了模型的預測效果以及簡潔程度。

? XGBoost亮點

  • We design and build a highly scalable end-to-end tree boosting system.
  • We propose a theoretically justified weighted quantile sketch for efficient proposal calculation.
  • We introduce a novel sparsity-aware algorithm for par- allel tree learning.
  • We propose an effective cache-aware block structure for out-of-core tree learning.

翻譯來說，就是它設計並構建了適用於大規模的 end-to-end 的Boosting系統（end-to-end指的是端到端，就是只關心輸入和輸出，中間過程都不care），而且實現特徵選擇的並行處理，正則使用L2的稀疏感知算法，而且也提出了有效的緩存結構，加大訓練效率

另外，其他博文也有一些總結：

  • 相對GBDT來說，XGB在增加二階梯度有更高的精度；
  • XGB的節點劃分策略帶有進行預排序，利用樣本在損失函數上面的二階梯度作為權值；
  • XGB對稀疏的特徵劃分方式；
  • 在處理特徵的粒度上進行多線程的優化；
  • 使用近似算法替代每個樣本逐個判斷最佳分裂點的Exact Greedy Algorithm算法。

? 梯度增強樹算法介紹

XGBoost還是採用屬於gradient tree boosting algorithms，推導過程和已有的算法理論類似，但這裡有了一些創新，比如正則化學習目標、樣本子採樣、特徵子採樣、近似算法等等。

3.1 Regularized Learning Objective

給定一個n X m維的數據集D，通過訓練D，得到K棵樹，而這K棵樹累加的值作為我們的預測值。
file

其中，file
是CART的空間，q表示每個樹的結構，其可以將每個樣本映射到對應的葉節點中，T是樹中葉子節點的個數。

有了上面的預測值，我們可以代入loss function，得到我們的損失函數：

file

可以看出損失函數由兩部分組成，Training Loss和Regularization。

3.2 Gradient Tree Boosting

這一節是對損失函數的推導求解，這裡不是採取傳統的優化方法進行優化，而是採用了Additive Training訓練，我們將Training Loss部分，展開成K棵樹疊加的形式，開始於一個常數，每次增加一個新的函數學習當前的樹，貪婪地利用誤差函數改善當前模型，而這裡創新的點在於對誤差函數進行二階泰勒近似展開。

具體公式推導就不展開了，建議查閱：

XGBoost原理介紹：https://blog.csdn.net/yinyu19950811/article/details/81079192

3.3 Shrinkage and Column Subsampling

這一節講到了兩種防止過擬合的tricks，Shrinkage和Column Subsampling。

  • Shrinkage：權值收縮，主要針對葉子節點，在每一次的Tree Boosting後，收縮葉子節點的權重，降低了每棵獨立樹的影響，為將來的優化留出一些空間。
  • Column Subsampling：這種技術出現在RF中，這種做法不僅可以防止過擬合，還能提升一部分訓練效率。

分裂查找算法介紹

4.1 Basic Exact Greedy Algorithm

這個是常見的基礎貪心算法，即對所有的特徵進行遍歷處理，這就要求對計算資源要求比較高，因為需要對每個特徵計算其信息增益，選擇增益最大的作為分裂點，當然是需要比較多的時間和算力。

file

4.2 Approximate Algorithm

顧名思義，近似算法就是可能效果或者原理和Exact Greedy Algorithm差不多的算法，它的原理是根據特徵分佈的百分位數進行採樣，選擇待分裂點，然後，該算法將連續特徵映射到由這些候選點分割的桶中，匯總統計信息並根據匯總的信息找到最佳解決方案，這裡選擇分裂點的方式有global和local：

  • global：在樹構建的初始狀態階段選出所有候選分裂點，後面每層都使用相同的策略選擇分裂點。
  • local：每次分裂後重新選出候選分裂點，適合深度較大的樹，因為不需要提前準備過多的候選分裂點。

file

4.3 Weighted Quantile Sketch

分佈式加權直方圖算法是XGBoost提出的一種可並行的算法，樹節點在進行分裂時，需要計算特徵的信息增益，該算法用於高效地生成候選分裂點，對於大型的數據集，如果每個實例具有相等權重時，quantile sketch算法可以解決，但對於加權數據集來說，則不適用，為了解決該問題，XGBoost提出了分佈式加權quantile sketch算法。

4.4 Sparsity-aware Split Finding

稀疏感知分裂發現，在現實生活中，特徵往往都是稀疏的，有幾種可能的原因導致特徵稀疏：

1）presence of missing values in the data;

2）frequent zero entries in the statistics;

3）artifacts of feature engineering such as one-hot encoding

XGBoost以統一的方式處理缺失的情況，分裂中只選擇沒有缺失的數據去進行節點分支，然後缺失情況默認指定一個方向，其效率paper里說了是提升了50倍。

file

file

? XGBoost的系統設計

5.1 Column Block for Parallel Learning

即按列分塊並行化學習，XGBoost會對每個特徵的值進行排序，使用CSC結構存儲到塊（block）中，訓練過程對特徵分枝點計算採用並行處理，尋找合適的分裂點。所以我們常說的XGBoost的並行計算指的是不是樹的學習上，而是在特徵上的並行處理。

所以，這裡XGBoost在設計系統的時候，預留額外的空間（Block）賴儲存排序好的數據，這裡的排序，是按照每列的值排序，所以索引在不同特徵之間是不一樣的。

file

所以，特徵預排序只需要在開始的時候做一次即可，後續可以重複調用，大大減少了每次排序的耗時，所以也可以實現並行化學習，計算每個特徵的信息增益。

5.2 Cache-aware Access

即緩存感知訪問，對於有大量數據或者說分佈式系統來說，我們不可能將所有的數據都放進內存裏面。因此我們都需要將其放在外存上或者分佈式存儲。但是這有一個問題，這樣做每次都要從外存上讀取數據到內存，這將會是十分耗時的操作。

因此我們使用預讀取（prefetching）將下一塊將要讀取的數據預先放進內存裏面。其實就是多開一個線程，該線程與訓練的線程獨立並負責數據讀取。此外，還要考慮Block的大小問題。如果我們設置最大的block來存儲所有樣本在k特徵上的值和梯度的話，cache未必能一次性處理如此多的梯度做統計。如果我們設置過少block size，這樣不能充分利用的多線程的優勢，也就是訓練線程已經訓練完數據，但是prefetching thread還沒把數據放入內存或者cache中。

經過測試，作者發現block size設置為2^16個examples最好。

file

5.3 Blocks for Out-of-core Computation

因為XGBoost是要設計一個高效使用資源的系統，所以各種機器資源都要用上，除了CPU和內存之外，磁盤空間也可以利用來處理數據。為了實現這個功能，我們可以將數據分成多個塊並將每個塊儲存在磁盤上。

在計算過程中，使用獨立的線程將Block預提取到主內存緩衝區，這樣子數據計算和磁盤讀取可以同步進行，但由於IO非常耗時，所以還有2種技術來改善這種核外計算：

  • Block Compression： 塊壓縮，併當加載到主內存時由獨立線程動態解壓縮；
  • Block Sharding： 塊分片，即將數據分片到多個磁盤，為每個磁盤分配一個線程，將數據提取到內存緩衝區，然後每次訓練線程的時候交替地從每個緩衝區讀取數據，有助於在多個磁盤可用時，增加讀取的吞吐量。

? References

VirMach 便宜 VPS

QNews

QNews