原创：程祥国

1. XGBoost概述

XGBoost是陈天奇提出的一个端对端的梯度提升树系统，该算法在GBDT【关于GBDT这里不再展开叙述，可以参考李航老师统计学习方法一书中对该算法的讲述】的基础之上，在算法层面和系统设计层面都做了一些创新性的改进，可以把XGBoost看作是GBDT更好更快的实现。XGBoost在许多机器学习以及数据挖掘的任务中表现惊艳，2015年，kaggle竞赛平台上发布了29个挑战获胜的解决方案，其中17个解决方案用了XGBoost。由于XGBoost在实际任务中的良好表现，因此搞清XGBoost的实现细节对于在实践中应用XGBoost是非常有帮助的。因此本文基于陈天奇的论文XGBoost: A Scalable Tree Boosting System，详细阐述XGBoost的各种细节。

上述我们提到XGBoost在算法层面和系统设计层面都做了一些创新性的改进，我们首先将XGBoost的创新做一个总结：

算法层面

（1）在GBDT目标函数的基础上，在对优化目标求解的时候使用了二阶导数的信息，因此会使优化目标的定义更加精确，训练速度会更快；此外，XGBoost在优化目标函数中加入了正则项，这会限制模型的复杂度，防止过拟合的发生。

（2）提出了一种处理缺失值的算法，XGBoost能够自动对缺失值进行处理

（3）在树生成选择特征划分节点的时候，通过加权分位数草图算法，预先对每个特征建立候选的划分节点，不在使用原先的贪婪算法（遍历每个特征所有取值），从而大大加快训练速度

系统设计层面

（1）对训练的每个特征排序并且以块（block）的结构存储在内存中，方便后续训练迭代重复使用，减少计算量。对于不同的特征的特征划分点，XGBoost分别在不同的线程中并行选择分裂的最大增益，从而实现了并行训练。

（2）提出了一种有效的缓存感知块结构用于树模型的核外学习

下面我们将分别对上述5项进行分析。

2. 模型层面

2.1 优化目标函数

假设数据集D有n个样本m个特征:,树集成算法使用加法模型对K个基学习器进行合成，作为最终的预测输出。如图1所示。

图1：树集成模型，最终的预测结果为两棵树的和

为了使上述预测的结果尽可能的接近实际值，我们首先定义模型的优化目标函数，优化目标函数如下所示：

这里是一个可微的凸损失函数，它表示预测和目标之间的差值。T是每棵树叶子的数量，表示模型对叶子节点的预测数值。第二项是惩罚项，限制回归树模型的复杂度。正则化项有助于使最终学习到的权值更加平滑，避免过拟合。直观地说，带有正则化的目标函数倾向于选择简单的预测模型。当第颗树生成的时候，我们可以将公式1.1变成如下形式：

在公式1.3中，是前颗树对样本的预测值，是第颗树对样本的预测值，是第棵树叶子节点的个数，是第颗树第个叶子节点的数值，而我们模型的学习目标就是最小化公式1.3的数值，从而得到第t颗树：最优的所有个叶子节点区域和每个叶子节点区域的最优解。在此处，我们使用泰勒公式展开，来对公式1.3中的第一项进行二阶导数展开，展开后公式1.3变为如下：

在公式1.4中,,,公式1.4中是一个常量，因此对我们的优化目标没有影响，我们可以将该项删掉，此外为了便于公式1.4中第一项和第三项的合并，我们将公式1.4转换为以叶子节点作为累加，可将上式转换为如下形式：

在公式1.5中，,;公式1.5可以看作是一个关于的一元二次函数，当第颗树的结构已知时，我们能够计算出公式1.5的最小值在,时取得，当我们的取得最优值的时候，公式1.5可以转换为如下形式：

当我们在生成棵树的时候，每次选择划分节点的时候，我们都希望公式1.6的数值能够减少的更多一些，假设当前节点左右子树的一阶二阶导数和为,, ,则我们期望最大化下式：

公式1.7就是我们在生成第颗树的时候，用来选择最优划分节点的标准。

至此我们完成了XGBoost优化目标函数的推导，基于此我们可以简单总结一下XGBoost的核心流程（此处暂不涉及缺失值处理以及分位数缩略草图等细节）：当我们在学习一颗新树的时候，我们通过对每个特征每个特征值作为划分节点计算公式1.7的数值，每个节点的划分我们都选择使公式1.7取值最大的那个特征的特征值，不断分裂节点，直至公式1.7的最大取值小于0，则我们的新树就生成好了。

2.2 稀疏感知算法

缺失值在实际的工作数据中是经常会遇到的，传统的许多算法都需要对缺失值进行预处理：比如使用各种方法进行缺失值的填充，而XGBoost能够自动的处理缺失值，在每颗树生成的时候，在选择以哪一个特征哪一个特征值作为划分节点时，会使用没有缺失值的样本对每个特征的特征值进行排序，然后遍历的对每个特征每个特征值作为划分节点，会自动的将缺失值样本，分别放在左叶子节点和右叶子节点，然后分别计算缺失值样本在左叶子节点和右叶子节点哪一个情况公式1.7的减少的大【因为要涉及到将缺失值的样本分别划到左叶子节点和右叶子节点，相当于计算公式1.7减少的算法流程要进行两次】，就选择哪一个特征的哪一个特征值作为最佳的划分节点。算法的详细情况如图2所述【原始论文中的流程是分别从小到大和从大到小对特征进行排序，然后分别将特征值样本划分到右叶子节点和左叶子节点，这样看起来会有点绕，实质就是我们传统的将特征值从小到大排序以后，遍历以所有特征值作为划分节点，第一轮计算是将缺失值样本划分为左叶子节点，第二轮计算就是将缺失值样本划分为右叶子节点】。

图2 稀疏感知算法流程

2.3 加权分位数草图算法

我们在2.1小节探讨分析了每棵树生成时候的核心流程，在每棵树生成的时候，最消耗时间的就是我们划分节点的选取，使用贪心算法遍历所有特征所有可能的候选值会消耗大量的时间，因此XGBoost提出了一种近似算法以及相应的加权分位数草图算法，近似算法的核心思想是：对每个特征不在遍历所有的特征值，而是将特征按照一定的规则找到几个关键的百分位数节点，这个规则就是加权分位数草图算法，加权分位数草图算法的流程及证明过程较复杂，在这里我们不在展开分析，该算法的详细流程以及证明过程可以参见论文附录【XGBoost: A Scalable Tree Boosting System】。

3. 系统设计层面

3.1 块结构

传统的GBDT在每颗树生成的时候，无法进行并行计算，而XGBoost实现了并行计算，这里的并行计算是指在生成每棵树的时候能够并行计算所有特征的划分节点。XGBoost中将排好序的数据存储在内存单元中，称之为block。每个block中的数据根据每列特征取值排序，并以压缩列（CSC）格式储存。这种输入数据布局只需要在训练前计算一次，可以在后续迭代中重复使用。

在贪婪算法中【选择最佳划分节点时，遍历所有特征所有可能的值】，我们将整个数据集存储在单个block中，并通过对预排序的数据进行线性扫描来实现分割点搜索。这样只需扫描一次block就可以得到所有特征所有候选分裂节点的统计信息。下图显示了如何将数据集转换成相应格式并使用block结构找到最优分割。

图3 数据排序后存入block结构

当使用近似算法【选择最佳划分节点时，只计算每个特征预先选取的几个百分位处的特征值】时，block结构也非常有用。在这种情况下，可以使用多个block，也可以实现并行计算。

3.2 核外学习

XGBoost系统的一个目标是充分利用机器的资源来实现可扩展的学习。 除处理器和内存外，利用磁盘空间处理不适合主内存的数据也很重要。为了实现核外计算，我们将数据分成多个块并将每个块存储在磁盘上。在计算过程中，使用独立的线程将块预取到主存储器缓冲区是非常重要的，因为计算可以因此在磁盘读取的情况下进行。但是，这并不能完全解决问题，因为磁盘读取会占用了大量计算时间。减少开销并增加磁盘IO的吞吐量非常重要。 我们主要使用两种技术来改进核外计算。

Block Compression 我们使用的第一种技术是块压缩。该块从列方向压缩，并在加载到主存储器时通过独立的线程进行解压。这可以利用解压过程中的一些计算与磁盘读取成本进行交换。我们使用通用的压缩算法来压缩特征值。对于行索引，我们通过块的起始索引开始减去行索引，并使用16位整型来存储每个偏移量。这要求每个块有个样本，这也被证实是一个好的设置。在我们测试的大多数数据集中，我们实现了大约26％到29％的压缩率。

Block Sharding 第二种技术是以另一种方式将数据分成多个磁盘。为每个磁盘分配一个实现预取的线程，并将数据提取到内存缓冲区中。然后，训练线程交替地从每个缓冲区读取数据。当有多个磁盘可用时，这有助于提高磁盘读取的吞吐量。

至此，我们已经对XGBoost的主要内容进行了分析讨论，通过上述分析我们能够看到XGBoost在许多方面都进行了创新改进，这也是XGBoost在实际工作中表现优异的原因：在算法层面更精确的定义了优化目标函数，使得学习的目标更加准确；稀疏感知算法使得算法能够处理缺失值，从而使算法的稳健性更强大；加权分位数草图算法减少了候选划分节点的数量，从而提高了算法的运行效率；在系统设计层面，block结构实现了选择候选划分节点时的并行计算，从而大大提高了运行效率。

参考文献

1、XGBoost: A Scalable Tree Boosting System—陈天奇

2、XGBoost算法原理小结—刘建平

3、XGBoost原论文阅读翻译—了不起的赵队