論文筆記：XGBoost: A Scalable Tree Boosting System

08-14

1 人贊了文章

論文鏈接

XGBoost: A Scalable Tree Boosting System

參見Boosted Trees

這是另外兩個防止過擬合的技術

Shrinkage給新加的權重* $eta$ ，類似於梯度下降方法中的學習率。

Column Subsampling在隨機森林中被採用過，能防止過擬合，提高運算速度。

樹學習的關鍵問題是找到最佳的split點。

Basic Exact Greedy Algorithm

暴力窮舉

遍歷所有feature的所有可能split點

演算法1有兩層for循環，時間複雜度為 $O(mI)$

Approximate Algorithm

演算法2隻有一層for循環，所以時間複雜度為 $O(m)$

演算法2比演算法1花費時間少的原因是：對feature $k$ 進行等分，對每個分區進行求和，然後在一個分區一個分區大粒度進行遍歷。

Sparsity-aware Split Finding

找split的方法：為了適用於稀疏數據，給樹節點加默認方向，當數據的某個feature缺失時，則沿著這個樹節點的默認方向走下去。詳見下圖

從訓練數據中學習默認方向，從大到小遍歷，從小到大遍歷，然後選取max gain為默認方向，具體演算法如下：

Sparsity-aware Split Finding方法的效果是處理sparsity數據速度更快

訓練默認方向時只使用non-missing entries，所以速度更快。

Column Block for Parallel Learning

訓練之前將每一列進行單獨排序，存在內存中。

Cache-aware Access

問題

對於exact greedy algorithm

在每個線程里分配內部的緩存

效果

對於大數據，速度提升明顯

對於approximate algorithms

選取合適的block大小，block大小選為block中包含的最大example數量

block size太小，每個線程的壓力很小，但是整體的效率很低

block size太大，每個線程的緩存會溢出

block size為 $2^{16}$ 時，能最好的平衡緩存問題跟並行效率

Blocks for Out-of-core Computation

Block Compression

按列進行壓縮，當讀入內存時解壓

Block Sharding

在多個硬碟中共享數據