【推荐收藏】带你撸一遍 XGBoost论文

石晓文

发布于 2019-07-09 01:02:34

1.9K0

发布于 2019-07-09 01:02:34

XGBoost作为一个非常常用的算法，我觉得很有必要了解一下它的来龙去脉，于是抽空找了一些资料，主要包括陈天奇大佬的论文以及演讲PPT，以及网络上的一些博客文章，今天在这里对这些知识点进行整理归纳，论文中的一些专业术语尽可能保留不翻译，但会在下面写出自己的理解与解释。

资料下载：公众号回复"xgb"获取

? Index

XGBoost介绍
XGBoost亮点
梯度增强树算法介绍
- Gradient Tree Boosting
- Shrinkage and Column Subsampling
- Regularized Learning Objective
分裂查找算法介绍
- Approximate Algorithm
- Weighted Quantile Sketch
- Sparsity-aware Split Finding
- Basic Exact Greedy Algorithm
XGBoost的系统设计
- Cache-aware Access
- Blocks for Out-of-core Computation
- Column Block for Parallel Learning

? 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棵树累加的值作为我们的预测值。

其中，

是CART的空间，q表示每个树的结构，其可以将每个样本映射到对应的叶节点中，T是树中叶子节点的个数。

有了上面的预测值，我们可以代入loss function，得到我们的损失函数：

可以看出损失函数由两部分组成，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

这个是常见的基础贪心算法，即对所有的特征进行遍历处理，这就要求对计算资源要求比较高，因为需要对每个特征计算其信息增益，选择增益最大的作为分裂点，当然是需要比较多的时间和算力。

4.2 Approximate Algorithm

顾名思义，近似算法就是可能效果或者原理和Exact Greedy Algorithm差不多的算法，它的原理是根据特征分布的百分位数进行采样，选择待分裂点，然后，该算法将连续特征映射到由这些候选点分割的桶中，汇总统计信息并根据汇总的信息找到最佳解决方案，这里选择分裂点的方式有global和local：

global：在树构建的初始状态阶段选出所有候选分裂点，后面每层都使用相同的策略选择分裂点。
local：每次分裂后重新选出候选分裂点，适合深度较大的树，因为不需要提前准备过多的候选分裂点。

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倍。

? XGBoost的系统设计

5.1 Column Block for Parallel Learning

即按列分块并行化学习，XGBoost会对每个特征的值进行排序，使用CSC结构存储到块（block）中，训练过程对特征分枝点计算采用并行处理，寻找合适的分裂点。所以我们常说的XGBoost的并行计算指的是不是树的学习上，而是在特征上的并行处理。

所以，这里XGBoost在设计系统的时候，预留额外的空间（Block）赖储存排序好的数据，这里的排序，是按照每列的值排序，所以索引在不同特征之间是不一样的。

所以，特征预排序只需要在开始的时候做一次即可，后续可以重复调用，大大减少了每次排序的耗时，所以也可以实现并行化学习，计算每个特征的信息增益。

5.2 Cache-aware Access

即缓存感知访问，对于有大量数据或者说分布式系统来说，我们不可能将所有的数据都放进内存里面。因此我们都需要将其放在外存上或者分布式存储。但是这有一个问题，这样做每次都要从外存上读取数据到内存，这将会是十分耗时的操作。

因此我们使用预读取（prefetching）将下一块将要读取的数据预先放进内存里面。其实就是多开一个线程，该线程与训练的线程独立并负责数据读取。此外，还要考虑Block的大小问题。如果我们设置最大的block来存储所有样本在k特征上的值和梯度的话，cache未必能一次性处理如此多的梯度做统计。如果我们设置过少block size，这样不能充分利用的多线程的优势，也就是训练线程已经训练完数据，但是prefetching thread还没把数据放入内存或者cache中。

经过测试，作者发现block size设置为2^16个examples最好。

5.3 Blocks for Out-of-core Computation

因为XGBoost是要设计一个高效使用资源的系统，所以各种机器资源都要用上，除了CPU和内存之外，磁盘空间也可以利用来处理数据。为了实现这个功能，我们可以将数据分成多个块并将每个块储存在磁盘上。

在计算过程中，使用独立的线程将Block预提取到主内存缓冲区，这样子数据计算和磁盘读取可以同步进行，但由于IO非常耗时，所以还有2种技术来改善这种核外计算：

Block Compression： 块压缩，并当加载到主内存时由独立线程动态解压缩；
Block Sharding： 块分片，即将数据分片到多个磁盘，为每个磁盘分配一个线程，将数据提取到内存缓冲区，然后每次训练线程的时候交替地从每个缓冲区读取数据，有助于在多个磁盘可用时，增加读取的吞吐量。