XGBoost原理详解及系统优化

XGBoost，全称“Extreme Gradient Boosting”，和GBDT一样属于Boosting类型的模型，也是一种加法模型。

1 XGBoost原理

1.1 监督学习概念回顾

1.1.1模型和参数

监督学习中模型表示从样本输入 $x_{i}$ 到预测输出 $y_{i}$ 的映射关系，参数是我们要学习的部分，比如线性回归模型 $\hat{y}_{i}=\sum_{j}^{ }\theta _{j}*x_{ij}$ ， $\theta$ 是我们要学习的参数。

1.1.2 目标函数：损失+正则

模型训练的过程就是寻找最优参数，使得模型能够很好的拟合样本和标签。为了评价模型拟合样本和标签的好快程度，我们需要一个评估指标，即模型的目标函数。

通常目标函数由两部分组成：损失部分和正则部分： $obj(\theta ) = L(\theta ) + \Omega (\theta )$ ，其中L是损失函数，衡量模型的预测能力， $\Omega$ 是正则项，控制模型的复杂度，防止模型过拟合。

1.2 决策树加法模型

1.2.1 加法模型的训练Additive Training

XGBoost是基于CART决策树的加法模型，形式可以表示为：

$\hat{y}_{i}=\sum_{k=1}^{K}f_{k}(x_{i}), f_{k}\epsilon F$

其中K表示树的棵数，f是函数空间F中的函数，F代表所有可能的CART树。目标函数表示为

$obj(\theta )=\sum_{i}^{n}l(y_{i}, \hat{y}_{i}) + \sum_{k=1}^{K}\Omega(f_{k})$

有了目标函数之后，XGBoost的训练过程就是寻找最优参数最小化目标函数。XGBoost的参数是什么呢？XGBoost和GBDT一样，是函数空间的加法模型，其参数为函数，每个函数表示一棵CART树，包含树的结构和树中叶子节点的分数。

XGBoost的加法模型表示为：

$\hat{y}_{i}^{(0)} = 0$

$\hat{y}_{i}^{(1)} = f_{1}(x_{i}) = \hat{y}_{i}^{(0)} + f_{1}(x_{i})$

$\hat{y}_{i}^{(2)} = f_{1}(x_{i}) + f_{2}(x_{i}) = \hat{y}_{i}^{(1)} + f_{2}(x_{i})$

...

$\hat{y}_{i}^{(t)} = \sum_{k=1}^{t}f_{k}(x_{i}) = \hat{y}_{i}^{(t-1)} + f_{t}(x_{i})$

在每一步中，我们想要学习的函数或CART树必须能够使得目标函数最优：

$obj^{(t)} = \sum_{i=1}^{n}l(y_{i}, \hat{y}_{i}^{(t)}) + \sum_{i=1}^{t}\Omega(f_{i})$

$=\sum_{i=1}^{n}l(y_{i}, \hat{y}_{i}^{(t-1)} + f_{t}(x_{i})) + \Omega(f_{t}) + constant$

使用展开到二阶的泰勒展开式 $f(x) = \frac{f(x_{0})}{0!} + \frac{f'(x_{0})(x-x_{0})}{1!} + \frac{f''(x_{0})(x-x_{0})^2}{2!} + ...+\frac{f^{(n)}(x_{0})(x-x_{0})^{n}}{n!} + R_{n}(x)$

将目标函数展开到二阶项：

$obj^{(t)} = \sum_{i=1}^{n}[l(y_{i},\hat{y}_{i}^{(t-1)}) + g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t}) + constant$

其中：

$g_{i} = \partial_{\hat{y}_{i}^{(t-1)}}l(y_{i}, \hat{y}_{i}^{(t-1)})$

$h_{i} = \partial_{\hat{y}_{i}^{(t-1)}}^2l(y_{i}, \hat{y}_{i}^{(t-1)})$

移除所有的常数项之后，在第t步的目标函数就变为：

$obj^{(t)} \approx \sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t})$

这就是我们每学习一棵新决策树时的优化目标，该优化目标的值只依赖于 $g_{i}$ 和 $h_{i}$ ，这也就是为什么XGBoost支持自定义损失函数的原因：只要损失函数是一阶和二阶可导的，我们就可以一阶导数和二阶导数优化目标函数。

1.2.2 模型复杂度

目标函数中除了损失之外，还有一项：正则项，也就是说我们还需要定义决策树的复杂度。

首先，定义一棵决策树为：

$f_{t}(x) = w_{q(x)}, w\epsilon R^T, q: R^d \rightarrow \left \{1,2,...,T\right \}$

其中 $w$ 是表示叶子节点的分数的向量， $q$ 表示把每个样本映射到对应叶子节点的函数， $T$ 是叶子节点的数量。

基于以上的决策树定义，XGBoost中决策树复杂度定义为：

$\Omega(f) = \gamma T + \frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^2$

当然，决策树复杂度的定义可以有多种，但是这里使用的定义方式在实践中比较有效。很多关于树模型的算法包中经常忽略正则项，是因为传统树的学习重点关注提高节点纯度。XGBoost通过在目标函数中增加决策树复杂度，we can get a better idea of what we are learning and obtain models that perform well in the wild.

1.2.3 模型训练

在定义了决策树复杂度之后，我们在第t步的目标函数可以进一步做如下变换：

$obj^{(t)} \approx \sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t})$

$=\sum_{i=1}^{n}[g_{i}w_{q(x_{i})} + \frac{1}{2}h_{i}w_{q(x_{i})}^2] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2$

$=\sum_{j=1}^{T}[(\sum_{i \epsilon I_{j}}^{}g_{i})w_{j} + \frac{1}{2}(\sum_{i \epsilon I_{j}}^{}h_{i} + \lambda )w_{j}^2] + \gamma T$

其中 $I_{j} = \left \{i|q(x_{i}) = j \right \}$ 是分配到叶子节点j的样本集合。由于同属一个叶子节点的样本具有相同的分数，所以可以进行以上的变换。

如果定义：

$G_{j} = \sum_{i\epsilon I_{j}}^{}g_{i}$

$H_{j} = \sum_{i\epsilon I_{j}}^{}h_{i}$

那么上面的目标函数可以简化为：

$obj^{(t)}=\sum_{j=1}^{T}[G_{j}w_{j} + \frac{1}{2}(H_{j} + \lambda )w_{j}^2] + \gamma T$

上面的目标函数中 $G_{j}w_{j} + \frac{1}{2}(H_{j} + \lambda )w_{j}^2$ 可以看做是关于 $w_{j}$ 的二次方程，那么使得目标函数取得最优值时的 $w_{j}$ 以及目标函数的最优值分别为：

$w_{j}^* = -\frac{G_{j}}{H_{j}+\lambda }$

$obj^* = -\frac{1}{2}\sum_{j=1}^{T}\frac{G_{j}^2}{H_{j}+\lambda } + \gamma T$

对于一棵决策树， $w_{j}^2$ 定义了叶子节点的分数， $obj^*$ 相当于树的纯度，并且包含了树复杂度的度量。

有了树的度量标准之后，理想情况下可以遍历所有可能的树结构，选择最优的结构。但是在实际中是行不通的，所以我们选择每次优化树的一层结构，即当我们需要把树的一个叶子节点分裂成两个的时候，分裂的Gain为：

$Gain = \frac{1}{2}[\frac{G_{L}^2}{H_{L} + \lambda } + \frac{G_{R}^2}{H_{R} + \lambda } - \frac{(G_{L} + G_{R})^2}{H_{L} + H_{R} + \lambda }] - \gamma$

Gain由四部分组成：1）分裂之后左边叶子节点的分数；2）分裂之后右边叶子节点的分数；3）分裂之前叶子节点的分数；4）一个叶子节点分裂为两个叶子节点时额外增加的正则。

从Gain的表达式可以看出，如果叶子节点分裂的分数差小于 $\gamma$ ，就不要再进行分裂了。

Gain就是XGBoost在选择分裂点时的评估依据。在实际进行分裂时，为了比较高效的选择最优的分裂点，通常我们先把样本按照候选特征进行排序，然后进行遍历并计算每个可能分裂点的Gain。

2 XGBoost算法优化

2.1 Shrinkage and Column Subsampling

除了使用正则项之外，XGBoost还使用另外两种技术进一步防止过拟合。第一个是shrinkage，由Friedman提出（就是那个提出GBDT算法的Friedman）。Shrinkage对新学习到的树节点的分数进行缩放，类似于梯度优化中的学习率，shrinkage对单棵树的预测结果进行缩放，降低了单棵树的预测结果在模型中的权重，并且给以后的树留出了学习空间。第二个是列采样，列采样通常被用在RandomForest中。列采样相比行采样（也就是对样本进行采样，XGBoost也支持行采样），防止过拟合的效果更好，同时，列采样也一定程度上加速了XGBoost的并行计算。

2.2 最佳分裂点寻找算法

2.2.1 精确贪婪算法

树训练中的一个比较重要的问题就是寻找最佳分裂点。最基本的精确贪婪算法通过遍历所有可能的分裂点，然后计算Gain，选择Gain最大的分裂点。为了提高遍历效率，需要首先对样本按照特征值进行排序。精确贪婪算法的流程见Algorithm1。

image-20200326135621161.png

2.2.2 近似算法

精确贪婪算法因为要遍历所有可能的分裂点，所以总是能够找到最佳的分裂点，但是当数据量足够大，超出内存容量的时候，这种方式就失效了。另外，在分布式计算的情况下，数据分布在不同的节点上，精确贪婪算法也不能进行有效的计算。在这两种情况下，就需要采用近似算法。近似算法首先根据特征值分布的百分位数产生一些候选分割点，然后根据候选分割点把连续的特征离散化，然后计算梯度统计gi和hi，根据梯度统计计算obj*和gain，进而寻找最佳候选分割点。详细的算法流程见Algorithm2.

2.png

根据候选分割点在什么时候产生，近似算法又分成两种形式。第一种是global variant，是在树构造之前首先产生所有的候选分割点，后面在树的每一层进行分裂的时候都使用这些候选分割点。另外一种是Local variant，是在每次节点分裂之后，根据分配到节点的样本重新产生候选分割点。Global variant只产生一次候选分割点，而local variant需要多次产生候选分割点，但是由于属于树中间层节点的样本较少，尤其是随着树的深度增加，local variant相比global variant产生的候选分割点数量更少，而且由于local variant产生候选分割点只依赖于当前节点的样本特征值，因此更适合于deeper tree。

为了对比global variant和local variant，我们在Higgs boson dataset（一个kaggle比赛的数据集）上对两种方式进行试验，试验结果见下图。

3.png

（说明：eps越小，说明产生的候选分割点越多，原因或原理见2.2.3）

试验结果：1）global eps=0.05和exact greedy对比说明，近似算法的global variant如果产生足够多数量的候选分裂点，基本达到和精确贪婪算法同样的模型效果；2）global eps=0.3和local eps=0.3对比说明，产生候选分裂点数量相同的情况下，local variant相比global variant能达到更好的模型效果（因为在树的非根节点，相同数量的候选分裂点的情况下，实际上local variant要比global variant划分的更加精细），或者反过来说也可以，要达到同样的模型效果，local variant相比global variant需要更少的候选分裂点。

2.2.3 加权的百分位数候选分裂点产生方法（weighted quantile sketch）

近似算法中重要的一步就是产生合理的候选分裂点，通常是根据特征值的百分位数点产生候选分割点，这样可以把特征值平均的分成若干个区间。实际上，XGBoost中采取的方法是，计算 $D_{k} = \left\{(x_{1k}, h_{1}), (x_{2k}, h_{2}), ... (x_{nk}, h_{n})\right\}$ ，其中 $x_{nk}$ 表示第k个特征的第n个样本的值， $h_{n}$ 表示目标函数关于 $x_{nk}$ 的二阶导数，然后定义排序函数 $r_{k}, R\rightarrow \left [0,+\infty \right ]$ ：

$r_{k}(z)=\frac{1}{\sum_{(x,h)\epsilon D_{k}}^{}h}\sum_{(x,h)\epsilon D_{k},x<z}^{}h$

表示在 $D_{k}$ 中特征值小于z的样本加权占比，权重为h。

为什么把二阶导数作为权重呢？原因来源于目标函数表达式：

$obj^{(t)} \approx \sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t})$

对以上表达式变换一下：

$\sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t})$

$=\sum_{i=1}^{n}\frac{1}{2}h_{i}(f_{t}(x_{i}) - \frac{g_{i}}{h_{i}})^2 + \Omega(f_{t}) + constant$

这个表达式格式可以看做是以 $\frac{g_{i}}{h_{i}}$ 为label，以 $h_{i}$ 为权重的加权平方损失。

定义排序函数的目标是寻找候选分裂点 $\left\{s_{k1},s_{k2}, ...s_{kl}\right\}$ ，候选分裂点必须满足：

$|r_{k}(s_{k}, j) - r_{k}(s_{k}, j+1)| < \epsilon , s_{k1}=\underset{i}{min}\mathbf{x}_{ik},s_{kl}=\underset{i}{max}\mathbf{x}_{ik}$

这里 $\epsilon$ 是一个超参数（2.2.2中的eps就是指的这个超参数），直观上可以理解为，候选分裂点的数量大概为 $\frac{1}{\epsilon }$ .

2.2.4 稀疏数据的最佳分裂点寻找算法

在实际应用中，最常见的是类型是稀疏类型的特征，就是特征里面可能包含大量的缺失值。为了使XGBoost能够适用大量缺失值的场景，在树分裂的时候，给缺失值一个默认的分裂方向（全部分裂到左子节点或者全部分裂到右子节点），默认的分裂方向是通过在训练数据上学习得到的。学习默认分裂方向的算法见Algorithm3。算法只遍历没有缺失的样本，然后把有缺失值的样本当做一个整体，通过全部将其分到左子节点或右子节点，比较分到左边或右边的效果更好，就把全部缺失值样本分到哪边。

clip_image001.png

大多数已有的树学习算法要么仅针对密集数据进行了优化，要么需要特定的过程来处理有限的情况，例如分类编码。 XGBoost以统一的方式处理所有稀疏模式。更重要的是，我们的方法利用了稀疏性，使计算复杂度与输入中非缺失项的数量呈线性关系。

2.3 并行学习（Column Block for Parallel Learning）

XGBoost中最耗时的部分是对特征进行排序。为了提高排序的效率，我们采取事先把数据存储在被称为block的内存单元里，每个block中的数据是以列压缩（CSC）的格式存储，每列都按照该列的数值大小进行排序。这种输入数据只需要在训练之前计算一次，就可以重复用于之后每棵树的迭代训练。

在精确贪婪算法中，我们把整个数据集存储在同一个block中，并且存储在block中的数据已经是按照每列的特征值进行排序后的，所以只需要遍历一次block，并且根据每个样本点属于哪个叶子节点，就能同时为每个叶子节点寻找到最佳分裂点。下图表示了如何把数据集转换成列压缩（CSC)的格式，并且使用block高效的完成寻找最佳分裂点。

5.png

在近似算法寻找最佳分裂点中，采取的block存储方式与精确贪婪算法中有所不同，近似算法中采取用多个block对数据进行存储，每个block对应于一部分样本数据，并且block可以分布在不同的机器上，或存储在磁盘上。因为每个block是根据特征值预先排序的（此处，我理解应该是整体数据集先排序之后，然后分散在不同的block中），近似算法中的分位数搜索就变成了线性搜索，尤其是在local proposal模式下，候选分割点需要在每个分支下搜索产生，线性搜索相比分位数搜索极大的提高了效率。

收集每列的梯度统计信息可以并行进行，从而为我们提供了一种候选分裂点查找的并行算法。另外重要的是，CSC列压缩存储格式和block存储结构支持列采样，所以可以很方便的选择block中的部分列。

2.4 Cache-aware Access缓存感知访问

block结构降低了选取候选分裂点的计算复杂度，但是由于block中的数据是按照CSC的列压缩格式存储的，并且每列是按照特征值排序的，除了特征值之外，还存储了指针从特征值指向样本索引，所以在选取候选分割点的时候，会不断的根据特征值对应的样本索引去取梯度统计值，也就是说CPU会不断地访问非连续的内存单元，增加CPU的负担。最简单的实现方法是，CPU读取一次内存单元中的梯度统计值，就进行一次累计计算，就回引起CPU在累计计算和访问非连续的内存单元之间的读写依赖关系。如果block中的梯度统计数据不能进入CPU缓存（比如block太大等原因），或者发生缓存丢失cache miss，就会降低候选分裂点选取的效率。

对于精确的贪婪算法，我们可以通过缓存感知的预提取算法来缓解问题。具体来说，我们给每个线程分配一个内部缓冲区，将梯度统计信息提取到其中，然后以小批量的方式执行累加。这种预提取将直接读/写依赖关系更改为更长的依赖关系，并在行数较大时帮助减少运行开销。在数据集较大时，精确贪婪算法的可感知缓存的运行速度是普通版本的两倍。

对于近似算法，我们通过选择合适的block大小来解决该问题。我们将block大小定义为一个block中包含的最大样本数，因为这反映了梯度统计信息的缓存存储成本。选择过小的block大小会较小每个线程的工作量，但是同时也会降低并行化效率。另一方面，太大的block会导致高速缓存丢失cache miss，因此 block大小的选择应该要平衡这两个因素。通过在不同数据集上的测试，block大小设置为 $2^{16}$ 是个合适的选择。

2.5 Block for Out-of-core Computation核外计算

为了充分利用机器的资源来实现可扩展的学习，除了处理器和内存之外，利用磁盘空间来处理不能放在主内存的数据也很重要。为了实现核外计算，我们将数据分为多个block，并将每个block存储在磁盘上。在计算过程中，重要的是要使用独立的线程将block预提取到主存储器缓冲区中，这样就可以在读取磁盘的同时进行计算。但是，磁盘读取占用了大部分计算时间，所以要减少开销并增加磁盘IO的吞吐量。我们主要使用两种技术来改进核外计算。

1）block压缩

将block按列进行压缩，然后在加载到内存时通过独立的线程解压缩，相当于用解压缩时间换取磁盘读取成本。我们使用通用压缩算法来压缩特征值。对于行索引，我们把block中每个样本的索引值都减去开始索引，并使用16位整数存储每个样本的索引偏移量。在我们测试的大多数数据集中，我们实现了大约26％至29％的压缩率。

2）block分片

将block中的数据分片到多个磁盘上，并且给每个磁盘分配独立的线程，将数据提前取入内存缓冲区中，然后，训练线程可以从每个缓冲区读取数据。当有多个磁盘可用时，这有助于增加磁盘读取的吞吐量。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,189评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,577评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,857评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,703评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,705评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,620评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,995评论 3赞 396
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,656评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,898评论 1赞 298
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,639评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,720评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,395评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,982评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,953评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,195评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,907评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,472评论 2赞 342

XGBoost原理详解及系统优化

1 XGBoost原理

1.1 监督学习概念回顾

1.1.1模型和参数

1.1.2 目标函数：损失+正则

1.2 决策树加法模型

1.2.1 加法模型的训练Additive Training

1.2.2 模型复杂度

1.2.3 模型训练

2 XGBoost算法优化

2.1 Shrinkage and Column Subsampling

2.2 最佳分裂点寻找算法

2.2.1 精确贪婪算法

2.2.2 近似算法

2.2.3 加权的百分位数候选分裂点产生方法（weighted quantile sketch）

2.2.4 稀疏数据的最佳分裂点寻找算法

2.3 并行学习（Column Block for Parallel Learning）

2.4 Cache-aware Access缓存感知访问

2.5 Block for Out-of-core Computation核外计算

推荐阅读更多精彩内容