Papper-XGBoost A Scalable Tree Boosting System

发表于 | 分类于

Abstract

  • xgb是可拓展的端到端的提升树，对于稀疏数据进行稀疏感知，用分布式加权直方图算法（weighted quantile sketch）来近似树学习。提供缓存访问模式、数据压缩和共享。
  • xgb可以使用比现有系统少得多的资源来拓展数十亿个样本。

1.Introduction

  • 一些大数据分析的成功的两个原因：
    • 有效的统计模型的应用，获取复杂的数据依赖
    • 可拓展的学习系统，从大数据种学习模型
  • 梯度提升树（Boosted Tree）是一种在多个应用中大放异彩的技术，LambdaMART 是用于排序等场景的提升树变体。除了用作独立模型之外，还被用于实际生产(如ctr预测)、融合方法的基分类器。
  • Xgboost：比现有的框架快10倍以上，可拓展性高（在分布式情景中扩展到数十亿个实例）！这是来源于一些创新：
    • 一种新颖的处理稀疏数据的树学习算法
    • 一种分布式加权直方图算法，可以在近似树学习的过程中处理样本权重
    • 并行和分布式计算使得学习速度快。
    • 利用核外（out-of-core）计算，针对核外树学习提出了一种有效的缓存感知块结构（cache-aware block structure）。

2.TREE BOOSTING IN A NUTSHELL（回归树）

2.1模型

  • 模型：用K个函数来进行预测，每个回归树每个叶子上有连续分数，我们使用wi表示第i个叶子上的分数，通过综合对应树叶的得分（由w给出）来计算最终预测。
    • 一共n个样本
    • xi是第i个样本的特征，有m个特征
    • yi∈ R^m是第i个样本的标签
    • F={f(x)=w_{q(x)}}(q:R^m->T,w∈R^T)是回归树的函数空间
    • q是每个树的结构（决策规则），将一个样本的特征映射到叶子节点的下标。
    • T是树上叶子的数量
    • fk对应于一个树结构q和叶子权重们w
    • wi是第i个叶子节点的score（连续值）

2.2目标函数

  • L是可微分的凸函数
  • 贪婪地进行分裂

  • 目标函数1包括函数作为参数，在欧式空间中不能使用传统的优化方法优化，使用加性方式训练。与adaboost相似，假设^ yi（t）是第t次迭代中第i个样本的预测，我们需要加上ft来最小化以下目标：

  • 二阶泰勒展开(近似)能快速优化目标。由于泰勒展开满足：
  • 用泰勒展开来近似目标。二阶近似可以用来快速优化目标，将上式进行二阶泰勒展开：
    • gi是一阶梯度
    • hi是二阶梯度

  • 去掉与待求参数无关的常数项，这个新目标函数有一个非常明显的特点，它只依赖于每个数据点的在误差函数上的一阶导数和二阶导数，从而得到新的优化目标为：

  • 将上式变形，将关于样本迭代转换为关于树的叶子节点迭代：

    • 因为每个数据点落入且仅落入一个叶子节点，所以可以把n个数据点按叶子成组，类似于合并同类项，两个数据点同类指的是落入相同的叶子，即这里的指示变量集Ij
    • Ij={i q(xi) = j}是落入叶子j的样本集合

  • 对于每个叶子j的wj，有以下计算最优解的公式

  • 求权重对应的最优值，下式可以用来衡量树的质量。代表了当我们指定一个树的结构的时候，我们在目标上面最多减少多少（这个分数越小，代表树的结构越好）。我们可以把它叫做结构分数(structure score)，类似于信息增益、基尼系数：

  • 分裂增益：记分到左子树的样本集为IL,分到右子树的样本集为IR，I=IL ∪ IR。分裂该节点的增益如下，这个loss用于选分裂方案候选：

  • 我们希望找到一个属性以及其对应的大小，使得上式取值最大。
  • 因为Loss Function满足累积性(对MLE取log的好处)，并且每个叶结点对应的weight的求取是独立于其他叶结点的（只跟落在这个叶结点上的样本有关），所以，不同叶结点上的loss function满足单调累加性，只要保证每个叶结点上的样本累积loss function最小化，整体样本集的loss function也就最小化了。
  • 为了限制树的生长，我们可以加入阈值，当增益大于阈值时才让节点分裂，上式中的gamma即阈值，它是正则项里叶子节点数T的系数，所以xgboost在优化目标函数的同时相当于做了预剪枝。
  • 大家可以发现，当我们正式地推导目标的时候，像计算分数和剪枝这样的策略都会自然地出现，而不再是一种因为heuristic而进行的操作了。

2.3算法

  • 枚举所有树结构：不能枚举所有树结构，太复杂。

  • 贪心算法求分割点。只能用贪心算法来分裂节点， 从单个节点开始，遍历所有属性，遍历属性的可能取值， 并反复将分支添加进来。

    • 精确：列举所有特征上的所有可能分割。根据特征对样本数据进行排序，然后特征从小到大进行切分，比较每次切分后的目标函数大小，选择下降最大的节点作为该特征的最优切分点。大多数现有的gbdt实现都是精确的贪婪算法。但是当数据不能完全载入内存时，就不能做到这一点了。流程如下：

    • 近似（分位点算法）：根据特征分布的百分位（等间隔）提出候选分裂点，该算法然后将连续特征值映射到由这些候选点分割的桶中，在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分。 在给定合理的近似水平的情况下，分位数策略可以获得与精确贪婪相同的精度。有两种方法：
      • 全局变体：是在树构建的初始阶段选出所有候选分隔点，后面每层都使用相同的策略选择分隔点
      • 局部变体：在每次split后重新选出候选分隔点，适合较深的树，这样步骤比global多。local只需要较少的候选点，而global必须要有足够多的候选点（桶）才能达到和local差不多的精确度。

2.4防止过拟合——收缩和采样

  • 收缩：在每棵树加进来后，将新增加的树的w按因子α缩放，类似于优化中的学习率，收缩减少了每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。
  • 特征列采样：使用列子采样可以比传统的行子采样（也支持）更加防止过度拟合。也加速了稍后描述的并行算法的计算。

2.5带权重直方图（分位点）算法

  • Dk = {(x1k, h1), (x2k, h2) · · · (xnk, hn)} 代表每个样本的第k个特征值和每个样本的二阶梯度。可以定义一个rank function如下，代表第k个特征的值比z小的比例，为了找到满足相邻两个分隔点的值相差不大于阈值e的分隔点：

  • 希望得到的分位点{sk1, sk2, · · · skl}满足如下条件：

  • 这意味着大概有1/ϵ个分位点，其中ϵ是一个近似因子。

  • 二阶导hi做为第i个样本的权重，因为目标函数还可以写成带权的形式 ，原理如下：

  • 相当于将特征的值排序，在这个序列上根据计算带权的序函数选择合适的分隔点，使得每个含有不同权重的特征值区间分布均匀。
  • 为了优化该问题，本文还提出了分布式 weighted quantile sketch algorithm ，该算法的优点是解决了带权重的直方图算法问题，以及有理论保证。

2.6Sparsity-aware Split Finding

  • 稀疏性可能有多种原因：
    • 数据中存在缺失值
    • 数据有很多0
    • onehot编码
  • 给每个树节点加一个默认方向，当稀疏矩阵中一个值缺失时，其样本被分到默认方向。
  • 默认方向选取：
    • 主要思想：分别假设特征缺失的样本属于右子树和左子树，而且只在不缺失的样本上迭代，分别计算缺失样本属于右子树和左子树的增益，选择增益最大的方向为缺失数据的默认方向。
      • 在寻找split point的时候，不会对该特征为missing的样本进行遍历统计，只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找split point的时间开销。在逻辑实现上，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向进行分裂即可。
      • 如果训练中没有数据缺失，预测时出现了数据缺失，那么默认被分类到右子树。
    • 计算复杂度：与输入中的非缺失条目的数量成线性关系。
    • 算法描述：

3.系统设计

  • boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

3.1Column Block for Parallel Learning

  • 算法中最耗时的部分就是特征排序
  • XGBoost将数据存在内存单元（block）中，每个块中的数据都以compressed column (CSC)形式存储，每一列(一个属性列)均按相应的特征值升序存放 。这个数据只需要在训练之前算一次，并且可以在以后的迭代中重复使用。
    • 对于精确算法，将所有数据均导入一个块中，算法只要在数据中线性扫描一次已经预排序过的特征就可以。
    • 对于近似算法，可以用多个block分别存储不同的行的子集，多个block可以并行计算，也可以在硬盘中存储。也是线性扫面即可。这对local分裂算法尤其有用。
  • 直方图聚合（histogram aggregation）中的二分搜索也变为线性时间的算法。
  • 重要的是，由于将数据按列存储，可以同时访问所有列，那么可以对所有属性同时执行split finding算法，从而并行化分裂（split finding）。
  • 块结构还支持列子采样，很容易在块中选择列的子集。
  • 时间复杂度分析：
    • 设d为树的最大深度
    • 设K为树的总数目
    • 设q为数据集中proposal candidates的数目，通常是32-100之间
    • 设B为所有block的campus最大行数
    •   x   代表训练集上的无缺失样本数
    • 精确算法
      • 传统方法：O(Kd   x   logn )
      • Block方法：O(Kd   x   +   x   log n)，第二项是预处理排序的时间
    • 近似算法
      • 传统方法：O(Kd   x   log q)
      • block方法：O(Kd   x   +   x   log B)

3.2Cache-aware Access

  • 由于样本按特征进行了预排序，样本对应的统计量(一阶和二阶梯度)需要根据行索引来查找（这里具体看论文的图，维护了一堆指针），这导致了内存的不连续访问，容易导致cpu cache命中率降低。
  • 对于精确的贪婪算法
    • 以通过Cache-aware Access来缓解这个问题。我们在每个线程中分配一个内部缓冲区，获取梯度统计信息，然后以小批量方式执行累积。此预取将直接读/写依赖关系更改为更长的依赖关系，并有助于在其中的行数较大时减少运行时开销。
    • 当数据集很大时，精确贪婪算法的缓存感知实现版本的运行速度是原版本的两倍。
  • 对于近似的贪婪算法
    • 通过选择正确的块大小来解决这个问题，我们将块的大小设为一个block中样本最大数，这反映了梯度统计信息在cache的存储成本。
    • 选择块大小过小会导致每个线程的工作量少，导致低效的并行化。
    • 选择块大小过大会导致高速缓存未命中，因为梯度统计信息没在CPU高速缓存命中。
    • 实验表明每个块选择216个样本可以平衡缓存属性和并行化。

3.3Blocks for Out-of-core Computation

  • 为了更好地利用计算机的磁盘空间，对于不能一次性导入到内存的数据，我们将数据分成多个block存在磁盘上，在计算过程中，用独立的线程读取数据到cache，计算和磁盘读取可以同时发生，但是由于磁盘IO速度太慢，通常跟不上计算的速度。所以，我们采用了下面两种方法有优化速度和存储：
    • Block compression：将block按列压缩，加载到主存储器的时候由独立线程动态解压缩，这有助于将解压缩中的一些计算与磁盘读取成本进行交换。对于行索引，只保存第一个索引值，然后只保存该数据与第一个索引值之差(offset)，用16个bits来保存此offset。在我们测试的大多数数据集中，我们实现了大约26％到29％的压缩比。
    • Block sharding：为每个磁盘分配一个预取程器线程，并将数据提取到内存缓冲区中。然后，训练线程交替地从每个缓冲区读取数据。 当有多个磁盘可用时，这有助于提高磁盘读取的吞吐量。

4.相关工作

5.实验

5.1系统实现

  • 支持分类、rank
  • 支持自定义目标函数
  • 分布式可以在hadoop、mpi、spark机器运行

5.2数据集和实验设置

  • 使用了四个数据集，每个数据集使用不同数目的样本做多次实验。
    • Allstate保险索赔数据集：据不同的风险因素预测保险索赔的可能性和成本。在实验中，我们将任务简化为仅预测保险索赔的可能性。 此实验验证稀疏感知算法的影响。10M样本做训练集，其余做验证集。
    • 希格斯玻色子数据集：数据是使用物理事件的蒙特卡罗模拟生成的。 它包含由加速器中的粒子检测器测量的21种运动特性。 它还包含七个额外的粒子派生物理量。 任务是分类事件是否与希格斯玻色子相对应。 我们随机选择10M实例作为训练集，并将其余部分用作验证集。
    • Yahoo! 学习排名挑战数据集：这是学习排名算法最常用的基准之一。数据集包含20K Web搜索查询，每个查询对应于大约22个文档的列表。 任务是根据查询的相关性对文档进行排名。
    • criteo terabyte点击日志数据集：评估xgb在分布式中的扩展属性。有13个连续特征，26个离散特征。 由于基于树的模型更好地处理连续特征，我们通过计算前十天的平均CTR和ID特征的统计数据来预处理数据，在接下来的十天内通过相应的计数统计替换ID特征进行训练。预处理后的训练集包含17个具有67个特征的实例（13个整数，26个平均点击率统计和26个计数统计）。 整个数据集的LibSVM格式超过1TB。
  • 前三个数据集单机训练，最后一个分布式核外训练。所有单机实验均在戴尔PowerEdge R420上进行，配备两个八核Intel Xeon（E5-2470）（2.3GHz）和64GB内存。
  • 在所有实验中，我们使用最大深度等于8的提升树，收缩等于0.1。除非明确指定的话不进行列子采样。

5.3分类

  • 单机训练，在Higgs-1M数据上使用精确贪婪算法，将其与其他两种精确贪婪的提升树实现进行比较。
  • 由于scikit-learn只处理非稀疏输入，我们选择密集的Higgs数据集进行公平比较。
  • 我们使用1M子集在合理的时间内运行scikit-learn。
  • 在比较的方法中，R的GBM使用贪婪的方法，只扩展树的一个分支，这使得它更快但可能导致更低的准确性，而scikit-learn和XGBoost都学习完整的树。
  • 结果显示XGBoost和scikit-learn都比R的GBM提供更好的性能，而XGBoost的运行速度比scikit-learn快10倍。
  • 我们还发现列子样本的性能略差于使用不采样的，但是差的很轻微。可能是因为此数据集中的重要特征很少，我们可以从所有特征中贪婪地选择。

5.4Learning to Rank

  • 比较对象是pGBRT，这是此任务先前最好的系统。xgb运行精确的贪心算法，pGBRT仅支持近似算法，我们发现xgb运行更快。列采样不仅减少运行时间，也给了更精准的表现，这能防止过拟合。

5.5核外实验

  • 基本算法智能处理200M样本，加入压缩可以提供3倍加速，并且分成两个磁盘可以提供另外2倍加速，系统从400M样本开始耗尽文件缓存，在此之后，算法速度必须依赖磁盘。压缩+分片方法在文件缓存耗尽时不会显著减慢，之后呈现线性趋势。
  • 对于此，我们使用非常大的数据集来排空系统文件缓存以实现真正的核心外设置。
  • 当系统用完文件缓存时，我们可以观察到转换点。 请注意，我们方法的转换点不那么引人注目， 这是由于更大的磁盘吞吐量和更好的计算资源利用率。 我们的最终方法能够在一台机器上处理17亿个样本。

5.6分布式实验

  • 我们在EC2上使用m3.2xlarge机器建立了一个YARN集群，这是集群的一个非常常见的选择。每台机器包含8个虚拟内核，30GB内存和两个80GB SSD本地磁盘。
  • 数据集存储在AWS S3而不是HDFS上，以避免购买持久存储。
  • 我们首先将我们的系统与两个生产级分布式系统进行比较：Spark MLLib [18]和H2O。
  • 我们使用32 m3.2xlarge机器并测试具有各种输入大小的系统的性能。
  • 两个基线系统都是内存分析框架，需要将数据存储在RAM中，而XGBoost可以在内存不足时切换到核外设置。
  • 我们可以发现XGBoost的运行速度比基线系统快。更重要的是，它能够利用核外计算，并在给定有限计算资源的情况下平滑扩展到所有17亿个示例。
  • 该实验显示了将所有系统改进结合在一起并解决实际规模问题的优势。
  • 我们还通过改变机器的数量来评估XGBoost的缩放属性。随着我们添加更多机器，我们可以找到线性的XGBoost性能。重要的是，XGBoost只需要四台机器即可处理整个17亿个数据。这表明系统有可能处理更大的数据。

6.结论

参考资料