XGBoost: A Scalable Tree Boosting System

1. XGBOOST 回顾

这是一篇2015年陈天奇发表的文章，主要是大名鼎鼎的XGBOOST算法的介绍。XGBOOST广泛用于各种比赛和实际应用中，是非常实用的算法。XGBOOST是ensemble decision tree算法系列中的一个改进算法，与常规决策树（复习一下：最大化信息增益（ID3），信息增益率（C4.5）或GINI值（CART））中损失函数为不同，XGBOOST的损失函数不是计算ensemble中的每棵树的真实值与预测值的残差之和，而是在一棵树的残差之下进行继续的decision tree的计算。
首先回顾一下tree ensemble 模型。
假设数据集包含n个样本，每个样本有m个特征。一个包含了K个树的tree ensemble模型可以表示为：

$\hat{y}_{i}=\phi\left(\mathbf{x}_{i}\right)=\sum_{k=1}^{K} f_{k}\left(\mathbf{x}_{i}\right), \quad f_{k} \in \mathcal{F} \hspace{1in}(1)$

其中 $\mathcal{F}=\left\{f(\mathrm{x})=w_{q(\mathrm{x})}\right\}\left(q: \mathbb{R}^{m} \rightarrow T, w \in \mathbb{R}^{T}\right)$
是回归树（CART）。这里 $q$ 表示每个树的对应的叶子index，T是每个树的叶子数量。每个 $f_{k}$ 对应于一个独立的树结构q和叶子权重w。
Tree ensemble的损失函数为：

$\begin{aligned} \mathcal{L}(\phi) &=\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)+\sum_{k} \Omega\left(f_{k}\right) \\ \text { where } \Omega(f) &=\gamma T+\frac{1}{2} \lambda\|w\|^{2} \hspace{2in}(2)\end{aligned}$

其中 $l$ 是可微凸函数，测量的是每个树的预测值与真实值的差别。 $\gamma$ 是正则项。

对于XGBOOST来说，损失函数为：
$\mathcal{L}^{(t)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(\mathbf{x}_{i}\right)\right)+\Omega\left(f_{t}\right)$
其中 $\hat{y}_{i}^{(t)}$ 是第i个instance在第t次迭代的预测值，而xgboost会继续添加 $f_{t}$ 函数来最小化loss function。从损失函数的角度来看，因为里面的参数包含函数，这不是一个传统方法可以优化的损失函数，因此Gradient Tree Boosting用的是一步步相加的办法。

这个损失函数可以进行泰勒二级展开： $f(x+\Delta x) \simeq f(x)+f^{\prime}(x) \Delta x+\frac{1}{2} f^{\prime \prime}(x) \Delta x^{2}$
定义 $g_{i}=\partial_{\hat{y}^{(t-1)}} l\left(y_{i}, \hat{y}^{(t-1)}\right), \quad h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right)$ ，可以把损失函数进行变形：
$\mathcal{L}^{(t)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}^{(t-1)}\right)+g_{i} f_{t}\left(\mathrm{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathrm{x}_{i}\right)\right]+\Omega\left(f_{t}\right)$

经过一系列变换并展开正则项，最后可以把损失函数写成：
$\begin{aligned} \tilde{\mathcal{L}}^{(t)} &=\sum_{i=1}^{n}\left[g_{i} f_{t}\left(\mathrm{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathrm{x}_{i}\right)\right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2} \\ &=\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \end{aligned}$
对于一个固定的结构，叶子j的最优的权重 $w_j^*$ 可以算出
$w_{j}^{*}=-\frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i}+\lambda}$
带入损失函数后可以写作：
$\tilde{\mathcal{L}}^{(t)}(q)=-\frac{1}{2} \sum_{j=1}^{T} \frac{\left(\sum_{i \in I_{j}} g_{i}\right)^{2}}{\sum_{i \in I_{j}} h_{i}+\lambda}+\gamma T$
上式可以看作对于树结构的一个评估。对于boosting tree，我们一般从一个叶子开始，然后greedly增加分叉。假设左叉和右叉上的instances sets可以表示为 $I_L$ 和 $I_R$ 。所以增加一个分叉损失函数降低的值可以计算为：
$\mathcal{L}_{s p l i t}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_{L}} g_{i}\right)^{2}}{\sum_{i \in I_{L}} h_{i}+\lambda}+\frac{\left(\sum_{i \in I_{R}} g_{i}\right)^{2}}{\sum_{i \in I_{R}} h_{i}+\lambda}-\frac{\left(\sum_{i \in I} g_{i}\right)^{2}}{\sum_{i \in I} h_{i}+\lambda}\right]-\gamma$

在grow tree的时候，一般还有一些方法可以减少过拟合，比如对feature也就是column进行下采样。另一种方法是shrinkage，即每长出一个树杈一个小于1的权重（一般是0.1）。

2. 本文的一些优化

2.1 分支点选取

一般的，有贪心的分支点选取，即对于一个新的叶子，遍历所有的feature和所有的数据，得到最优的分界点。然后数据量过大无法全部fit进缓存里时，这种贪心算法却没有办法有效的计算了。一种优化方法是根据特征的quantile作下采样，保证采样的样本跟原分布的是相似的，从而根据样本搜索的给出一些分支点的推荐，从而加快找到最优点。

2.2 Weighted Quantile Sketch

对于所有样本权重相同的一般的下采样，已经有算法（quantile sketch）来解决这个问题，但对于boosted tree的loss function，可以发现这是个带权重的下采样，每个样本的权重是loss function的二次偏导。见下式：
$\sum_{i=1}^{n} \frac{1}{2} h_{i}\left(f_{t}\left(\mathbf{x}_{i}\right)-(-g_{i} / h_{i})\right)^{2}+\Omega\left(f_{t}\right)+\text { constant }$
XGboost也开发一套考虑了weight的distributed weighted quantile sketch algorithm来找下采样的样本集。

2.3 Sparsity-aware Split Finding

由于大多数的输入（X）都是稀疏矩阵，所以XGBOOST也考虑到了这个问题，对missing value做了default的归类。至于向哪个方向归类，则通过优化完成。结果表示，对于稀疏矩阵的特殊处理，及大的提高了计算效率。

Fig.1 Impact of the sparsity aware algorithm on Allstate-10K. The dataset is sparse mainly due to one-hot encoding. The sparsity aware algorithm is more than 50 times faster than the naive version that does not take sparsity into consideration.

3. 系统设计

3.1 Block system

对于寻找split point，由于需要sort每个feature，所以可以把feature sort好以后按CSC format存储在内存里，下次直接调用，这些内存单元叫block。对于贪心算法，所有数据存在一个block里，下次计算的时候复杂度只是线性搜索，而这种方法也可以帮助近似算法。可以把不同的行存在不同的block中，并行调用。具体可见下图：

Fig.2 Block structure for parallel learning. Each column in a block is sorted by the corresponding feature value. A linear scan over one column in the block is sufficient to enumerate all the split points.

3.2 Cache Aware

这里没太明白，似乎是csc按列存储的数据，在计算时由于要算score，需要按行抽取数据，结果造成了不连续的memory access. "This slows down split finnding when the gradient statistics do not fit into CPU cache and cache miss occur."

Fig.3 Short range data dependency pattern that can cause stall due to cache miss.

对于贪心算法，作者通过增加一个线程来抽取梯度的统计值，然后用mini batch的方法来计算累加。
对于近似算法，通过控制block的大小。具体可见图4.

Fig.4 The impact of block size in the approximate algorithm.

3.3 Blocks for Out-of-core Computation

这里有两点优化：block compression和block sharding。一方面，利用CSC压缩数据，然后在用的时候利用额外的线程解压。另一方面，用不同的磁盘来存数据，并用额外的线程来分别调用，减少IO瓶颈。

4 xboost评估和个人总结

作者总结了各个系统里关于tree boosting的实现情况，其中xgboost是最全面的。作者又在几个领域的公开数据集里用XGBOOST的效率做了验证，证明了XGBOOST的性能显著好于其他的tree boosting的实现。
在实现一个算法的时候，不仅要考虑算法的准确性，还要考虑算法在大规模数据集上的实现效率。本文中的几种加速方法都很值得借鉴，包括做近似计算，列存储，压缩，分布式，缓存等等。

5 Reference

[1]T. Chen和C. Guestrin, 《XGBoost: A Scalable Tree Boosting System》, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD 2016, San Francisco, California, USA, 2016, 页 785–794.