《XGBoost: A Scalable Tree Boosting System》

01-24

寫在前面：

陳天奇寫的XGBoost的paper，它是Tree boosting的一種具體實現，在各類競賽中表現優異，同時使用於各種各樣的需求場景。

1 TREE BOOSTING IN A NUTSHELL

Regularized Learning Objective

先給出一個 tree ensemble model的整體展示：

（這裡需要注意的是f(x)是從整體樹的角度來刻畫的，w_q(x)是從具體樹結構，即葉子節點來刻畫的，兩者之間一一對應關係，只是刻畫角度不同。）

具體示例：

整體的目標：

前者刻畫在訓練數據上的損失情況；後者刻畫模型的複雜度，即在未知數據上的穩定性。

（這個給出了一個Ω(f)的具體形式，這只是刻畫模型複雜度的一種方式，也可以選擇其他的方式。）

Gradient Tree Boosting

關於Loss公式上的各種推演，在《Introduction to Boosted Trees》中已經都有具體注釋過，這裡不再詳述。（主要就是泰勒二階近似，常數項合併，表達約定以及最優解的選取。）

泰勒二階近似：

但枚舉整個樹結構的集合，顯然是不可能的，實踐中在當前節點上貪心的選擇最優的策略，選擇的方式如下：

這裡的formula是用來刻畫由於新增節點帶來的複雜度損失。

Shrinkage and Column Subsampling

除了上面介紹的刻畫模型複雜度的Ω來防止過擬合外，還有兩種方法來防止過擬合：Shrinkage and Column Subsampling。Shrinkage scales newly added weights by a factor $eta$ after each step of tree boosting。Column Subsampling不必過多解釋，如字面意所示。

（前者表示在疊加一棵新的樹時，相信你，但不完全相信你。後者表示咱不談廣，做個局部領域的專家即可。）

SPLIT FINDING ALGORITHMS

Basic Exact Greedy Algorithm

這裡先按某特徵sort，方便後續的計算。

注意這裡的max中並沒有上文中提及的formula，理由是對於本次查找的所有的特徵都是等價的，減不減都一樣。

However,it is impossible to eciently do so when the data does not fi t entirely into memory.

還有一種近似的方法，就是不逐一過樣本，而是對於當前特徵，選擇幾個分位點，利用這些分位點來將連續特徵值映射成獨立的分桶，然後用這些聚合後的信息來進行後續的分裂。

分桶當然是越多越好，但越多意味計算量也就更大，極端情況下就是一個數據一個桶，但這違背了分桶的初衷。所有，需要綜合balance考慮。

具體實施時，有兩者方式：global variant 和local variant ，前者是在每棵樹開始之前就分好，後續不再改變；而後者是在每個節點上都具體情況具體分析的考慮。當然，後者更好，但帶來的複雜度也更大。通常情況下，都會優先選用global的形式。

可以預見到的是，local不用像global方式那樣設定分桶分的很細，因為它是有針對性的設置，可以在很粗粒度上就達到相同的效果。

可以看到：

1 在全局分桶分的很細時，和exact greedy效果幾乎完全相同。（紫色，藍色）

2 當local較大時，幾乎可以達到global較小值一樣的效果。（紫色，綠色）

3 當global設置過大時，整體效果就很差了。（藍色，紅色）

Sparsity-aware Split Finding

現實實踐中，會遇到很多稀疏的情況，或是缺失值的情形。

（實際上就是將指定的default值或是預設值，放一起看看是統一放在左邊還是右邊。由於減少了大量預設值的遍歷，使得速度會有很大提高，究竟提高多少得看具體業務了。paper中給的是提高了50倍，但這跟具體業務關係太大了。）

SYSTEM DESIGN

Column Block for Parallel Learning

整個樹學習過程中最耗時的部分就是sort，為了後續的便利，在初始時就根據每一維度先對其進行排序，並記錄其對應的instance index，這樣後續的分裂中也是可以復用這個信息。伴隨每一次分裂，這個信息也會隨之更新。

具體說明以及在分類，LTR等場景下的效果不再贅述。

RELATEDWORKS

最後是對整體的一個回顧~

Our system implements gradient boosting, which performs additive optimization in functional space....XGBoost incorporates a regularized model to prevent overfitting. This this resembles previous work on regularized greedy forest , but simplies the objective and algorithm for parallelization. Column sampling is a simple but effective technique borrowed from RandomForest . While sparsityaware learning is essential in other types of models such as linear models...