摘要

Tree boosting是一种高效、应用广泛的机器学习方法。在本文中，我们描述了一个名为XGBoost的可扩展端到端树增强系统，该系统被数据科学家广泛使用，在许多机器学习难题上取得了最新的成果。我们提出了一种新的稀疏数据稀疏感知算法和加权分位数草图的近似树学习。更重要的是，我们提供了关于缓存访问模式、数据压缩和分片的见解来构建一个可伸缩的树增强系统。通过结合这些见解，XGBoost可以使用比现有系统少得多的资源扩展数十亿个示例

1、介绍

在本文中，我们描述了XGBoost，一个可扩展的机器学习系统的树增强。该系统以开放源码包的形式提供。。
XGBoost成功背后的最重要因素是它在所有场景中的可伸缩性(scalability)。该系统在一台机器上的运行速度比现有的流行解决方案快十倍以上，并可在分布式或内存限制设置中扩展到数十亿个示例。XGBoost的可伸缩性来自于几个重要的系统和算法优化。这些创新包括：针对稀疏数据的处理，提出了一种新的树学习算法。一个理论上合理的加权分位数草图程序，使处理实例权值在近似树学习。并行和分布式计算使学习速度更快，从而使模型探索速度更快。更重要的是：XGBoost利用核外计算，使数据科学家能够在台式机上处理亿万个示例。最后，更令人兴奋的是将这些技术组合在一起，使端到端系统能够以最少的集群资源扩展到更大的数据。本文的主要贡献如下:
① 我们设计并构建了一个高度可扩展的端到端树提升系统。
② 我们提出了一个理论上合理的加权分位数草图，以有效的方案计算。
③ 介绍了一种新的稀疏感知并行树学习算法。
④ 我们提出了一种有效的缓存感知块结构用于核外树学习

虽然已有一些关于parallel tree boosting的工作，但对于核外计算、缓存感知和稀疏感知学习等方向还没有进行探索。更重要的是，结合所有这些方面的端到端系统为真实的用例提供了一种新颖的解决方案。这使得数据科学家和研究人员能够构建强大的tree boosting算法变种。除了这些主要的贡献之外，我们还在提出一个正则化学习目标方面做了额外的改进，为了完整起见，我们将包括这个目标。

2、果壳里的tree boosting

在这一节中，我们将回顾梯度树增强算法。这一推导是根据已有文献中梯度推进的相同思路进行的。其中二阶方法是由Friedman等人提出的。我们在反流目标上做了微小的改进，这在实践中被发现是有用的。

2.1学习目标正规化

对于具有n个例子和m个特征的给定数据集 ,树系综模型使用K个加性函数预测输出。(Tree Ensemble Model：对于给定例子的最终预测是每棵树预测的总和)

回归树的空间(也称为CART)，这里q表示将示例映射到相应叶索引的每棵树的结构。T是树的叶节点数。每个fk对应一个独立的树结构q和叶权w。与决策树不同，每个回归树在每个叶上都包含一个连续的分数，我们使用wi来表示第i个叶上的分数。对于给定的示例，我们将使用树中的决策规则（由q给出）将其分类为叶子，并通过对相应叶子（由w给出）中的得分求和来计算最终预测。为了学习模型中使用的函数集，我们最小化以下正则化的目标

是损失函数去测量预测值y ̂与目标值yi的差别。第二项Ω惩罚模型的复杂性(即回归树函数)。额外的正则化项有助于平滑最终学习的权重，以避免过拟合。直观地看，正则化的目标往往会选择一个采用简单的预测函数的模型。在Regularized greedy forest (RGF)模型中也采用了类似的正则化技术。我们的目标和相应的学习算法比RGF更简单，更容易并行化。当正则化参数设置为零时，目标回落到传统的梯度树增强。

2.2 Gradient Tree Boosting

Eq.(2)中的树系综模型包含函数作为参数，传统的欧几里得空间优化方法无法对其进行优化，相反，模型是以相加的方式训练的。正式,让y ̂_i(t)是第i个实例在第t次迭代时的预测，我们需要添加ft来最小化以下目标。

这意味着我们贪婪地根据公式(2)添加了最能改进我们模型的ft。二阶近似可以用于在一般设置中快速优化目标


是关于损失函数的一阶和二阶梯度统计量。我们可以去掉常数项，在步骤t得到如下简化的目标。

定义作为叶子j的实例集
将上式通过等式变换

对于固定结构q(x)，我们可以计算出最优权值ω_j^*的叶子j 通过
并计算出相应的最优值

上式可以作为一个评分函数来衡量树结构q的质量。这个分数类似于评价决策树的杂质分数，只是它是针对更大范围的目标函数而推导的。图2说明了如何计算这个分数。
通常不可能枚举所有可能的树结构q，取而代之的是贪婪算法，即从单个叶子开始，迭代地向树中添加分支。假设IL和IR是拆分后左右节点的实例集。

2.3 收缩和柱取样（Shrinkage and Column Subsampling）

除了第2.1节中提到的正则化目标外，还使用了另外两种技术来进一步防止过拟合。第一种技术是由弗里德曼提出的收缩技术，收缩以一个因素η衡量新增的权重每一步后的树形提升。与模型优化中的学习率相似，收缩减小了每棵树的影响，为未来树改进模型留下了空间。
第二种技术是列(特征)子抽样。这种技术在随机森林中使用，它是在一个用于增强梯度的商业软件中实现的，但在现有的开源包中没有实现。根据用户反馈，使用列子抽样比传统的行子抽样(也支持行子抽样)更能防止过拟合。列子样本的使用也加速了后面描述的并行算法的计算。

3、分裂发现算法

构建树,寻找分裂点的时候的问题
1、沿着【哪个维度】切
2、在这个维度上，将【取值大于几】的样本切到右子树

3.1 精确贪心算法(Basic Exact Greedy Algorithm)

一个直观的想法，就是写两层循环穷举这两个参数，逐个尝试后保留最优的切分方案。 这就是论文中的算法1: Exact Greedy Algorithm for Split Finding

3.2 近似算法

精确贪婪算法贪婪地枚举所有可能的分裂点，是一种非常强大的算法。然而，当数据不能完全装入内存时，就不可能有效地这样做。在分布式环境中也会出现相同的问题。为了在这两种情况下支持有效的梯度树增强，需要一种近似算法。
上述精确贪心方法性能不好，因为在内层循环中需要遍历每个特征维度的每种取值。 设有 m维特征，每个特征的取值平均有s种，则遍历成本就是O(m·s)
一个直观的想法是：上述复杂度中的s 来源于对特征的每种取值都逐个尝试， 这观察得太细了。如果我们把各种特征的取值都大致分到10个桶，而非精确到具体每一个取值，则复杂度变成O(m·10)

通过特征的分布，按照分布式加权直方图算法确定一组候选分裂点，通过遍历所有的候选分裂点来找到最佳分裂点。在寻找split point的时候，不会枚举所有的特征值，而会对特征值进行聚合统计，然后形成若干个bucket(桶)，只将bucket边界上的特征值作为split point的候选，从而获得性能提升。 算法二给出的是global的算法
该算法有两种变体，取决于何时给出建议。全局变量在树构造的初始阶段提出了所有的候选分割，并在所有层次上使用相同的分割查找建议。局部变体在每次分割后重新提出。
① 所谓"per tree(global) proposal"是指
在建树之前，只有一个根节点，所有样本都在一起。
针对这种情况，求解并记下建树前的最优分桶方案。
随后，逐层深化构建树；在建树过程中，样本逐渐被分割到各个子树
考虑具体某一次split动作，当前节点下，待分割的样本集合与全集不一样早前的最优分桶方案变得"未必合理"了，但是global假设它仍然近似合理，只需算一次proposal即可但是考虑到后续无法再细化分桶效果，所以这一次要尽可能分得细一点。
②"per split(local) proposal"是指
每次执行split之前，现算现用此时的最优分割方案适合于较深的树结构
local不用像global方式那样设定分桶分的很细，因为它是有针对性的设置，可以在很粗粒度上就达到相同的效果

上述 "算法2"遗留了一个问题: 怎么分桶?
比较naive的想法是：就按照该维度上的取值大小，等宽/等频分桶呗。 这也未尝不可，不过作者有个更巧妙的做法: 按照【对loss的影响权重】等宽分桶. e.g. 如果只允许分3个桶，就在该特征的取值范围上切两刀成三段，使得每一段内的样本们对loss的影响权重之和占总体比例都约为 33%

如果损失函数是Square loss，即 ,那么实际上是不带权(每个样本的权重一样)。 如果损失函数是Log loss，则h = pred ∗ (1− pred) h=pred∗(1−pred)h=pred∗(1−pred). 这是个开口朝下的一元二次函数，所以最大值在p r e d = 0.5 pred=0.5pred=0.5。当pred在0.5附近，值都比较大，也就是权重都比较大，在切直方图时，我们希望桶比较均匀，因此这部分就会被切分的更细。


ε为采样率，直观上理解，我们最后会得到1/ε个分界点。注意，这里的ε就是每个桶的比例大小

3.4 存在稀疏值时的分裂 Sparsity-aware Split Finding

在许多现实问题中，输入x是稀疏的是很常见的. 稀疏性可能有多种原因:1)数据中存在缺失值;2)统计中经常出现零记录;3)特征工程的工件，如单点编码. 重要的是要使算法意识到数据中的稀疏模式。为了做到这一点，我们建议在每个树节点中添加一个默认方向。
当稀疏矩阵x中缺少值时，实例将分类为默认方向. 在每个分支中有两个默认方向的选择。该算法将不存在视为缺失值，并学习处理缺失值的最佳方向。当不存在对应于用户指定的值时，通过将枚举限制为一致的解决方案，也可以应用相同的算法。
据我们所知，大多数现有的树学习算法要么只针对密集数据进行优化，要么需要特定的程序来处理有限的情况，比如分类编码

4、系统设计

4.1针对内存优化（列分块）

选择分裂点时候需要排序，为了减少排序的成本，论文提出将数据存储在内存单元中，称之为block。每个block中的数据每列根据特征取值排序，并以压缩列（CSC）格式储存。这种输入数据布局只需要在训练前计算一次，可以在后续迭代中重复使用。对应精确算法采用一个block，对于近似算法有多个block分别不同的数据子集。
在精确算法中，我们将整个数据集存储在单个block中，并通过对预排序的数据进行线性扫描来实现分割点搜索。我们集体对所有叶子进行分割查找，这样只需扫描一次block就可以得到所有叶子节点处所有候选分裂节点的统计信息。图6显示了如何将数据集转换成相应格式并使用block结构找到最优分割。

当使用近似算法时，可以使用多个block，每个block对应于数据集中的不同的行子集。不同的block可以分布在机器上，或者在非核心设置中存储在磁盘上。使用排序结构，分位数查找步骤在完成排序的列上就变成了线性扫描。这对于在每个分支中频繁更新候选分割点的本地优先算法非常有价值。直方图聚合中的二分搜索也变成了线性时间合并样式算法。
可以并行地收集每个列的统计信息，从而为拆分查找提供并行算法。重要的是，列块结构还支持列子抽样，因为很容易在块中选择列的子集。

4.2 Cache-aware Access

虽然block结构有助于优化分割点查找的时间复杂度，但是算法需要通过行索引间接提取梯度统计量，因为这些值是按特征的顺序访问的，这是一种非连续的内存访问（意思就是按值排序以后指针就乱了）。 分割点枚举的简单实现在累积和非连续内存提取之间引入了即时读/写依赖性。 当梯度统计信息不适合CPU缓存进而发生缓存未命中时，这会减慢分割点查找的速度。
对于贪心算法，我们可以通过缓存感知预取算法来缓解这个问题。 具体来说，我们在每个线程中分配一个内部缓冲区，获取梯度统计信息并存入，然后以小批量方式执行累积。 预取的操作将直接读/写依赖关系更改为更长的依赖关系，有助于数据行数较大时减少运行开销。 图7给出了Higgs和Allstate数据集上缓存感知与非缓存感知算法的比较。 我们发现，当数据集很大时，实现缓存感知的贪婪算法的运行速度是朴素版本的两倍。
对于近似算法，我们通过选择正确的block尺寸来解决问题。 我们将block尺寸定义为block中包含的最大样本数，因为这反映了梯度统计量的高速缓存存储成本。 选择过小的block会导致每个线程的工作量很小，并行计算的效率很低。 另一方面，过大的block会导致高速缓存未命中现象，因为梯度统计信息不适合CPU高速缓存。良好的block尺寸平衡了这两个因素。 我们在两个数据集上比较了block大小的各种选择，结果如图9所示。该结果验证了我们的讨论，并表明每个块选择2^16个样本可以平衡缓存资源利用和并行化效率。

4.3 Blocks for Out-of-core Computation

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

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

2020_9_20 组会