XGBoost
Last updated
Last updated
Tree boosting是一种高效且广泛使用的机器学习方法。 在本文中，我们描述了一个可扩展的端到端树推进系统XGBoost，它被数据科学家广泛使用，以在许多机器学习挑战中实现最先进的结果。我们提出了一种新的稀疏数据稀疏算法和近似树学习的加权量化框架。更重要的是，我们提供了有关缓存访问模式，数据压缩和分片的见解，以构建可扩展的树提升系统。通过结合这些见解，XGBoost使用比现有系统少得多的资源来扩展数十亿个示例。
我们回顾了梯度树提升算法。这个推导是从梯度提升中现有迭代的相同思想得出的。特别是第二阶方法起源于弗里德曼等人。[12]。我们对规定的目标进行了改进，这在实践中是有帮助的。
集成树模型使用K个树预测的结果相加
其中 ，q表示每个树的结构，它将一个例子映射到相应的叶子索引。T是树中叶子的数量。 每个 对应于独立的树结构q和叶子权重w。与决策树不同，每个回归树包含每个叶子上的连续分数，我们使用 代表i-th 叶子的分数。
树的求解目标是最小化以下损失
其中第二项是正则化，用来防止过拟合问题。
因为是加法模型，每次训练一颗新树，我们的求解目标为：
二阶泰勒展开
其中
去除常量
设 是叶子节点 上的实例，代入展开：
对于固定结构q(x)，我们可以计算出叶子的最佳权重
并计算相应的最优值
等式(6)可用作衡量树形结构质量的评分函数q。这个分数就像评估决策树的不纯分数，除了它是为更广泛的目标函数而衍生的。图2举例说明了如何计算这个分数。
通常，不可能枚举所有可能的树结构。 使用一种贪婪算法，该算法从单个叶子开始并迭代地将分支添加到树中。一个节点分裂成L、R两部分后的评分可以表示为：
除了第二节中提到的正则化目标。 2.1，使用另外两种技术来进一步防止过度拟合。第一种技术是Fried-man引入的收缩[11]。 在树木提升的每个步骤之后，收缩比例新增加了因子η。 与随机优化中的学习率相似，收缩减少了每棵树的影响，并为未来的树木留下了空间来改进模型。第二种技术是列(特征)二次采样。这种技术在随机森林中使用。根据用户反馈，使用列子采样比传统的行子采样(也受支持)更能防止过度拟合。列子样本的使用也加速了后面描述的并行算法的计算。
树学习中的一个关键问题是找到最佳分裂，如公式（7）所示。 为此，split finding算法枚举所有特征上的所有可能拆分。我们称之为exact greedy algorithm。大多数现有的单机树提升实现，例如scikit-learn [20]，R的gbm [21]以及XGBoost的单机版本支持精确的贪婪算法。确切的贪婪算法如Alg1所示。 计算连续特征的所有可能分裂的计算要求很高。 为了有效地执行此操作，算法必须首先根据特征值对数据进行排序，并按排序顺序访问数据，以便在方程（7）中累积结构分数的梯度统计数据。
精确贪婪算法非常强大，因为它贪婪地收集所有可能的分裂点。然而，当数据没有完全装入内存时，就不可能有效地这样做。为了在这两个设置中支持有效的梯度树增强，需要近似算法。
我们总结了一个近似的框架，它类似于过去的文献[17,2,22]中提出的思想。 2.总之，该算法首先根据特征分布的百分位数提出了可以分割的分裂点（具体标准将在3.3节中给出）。然后，算法将连续特征映射到由这些候选点分割的分数点，聚合 统计数据，并根据聚合统计数据找到提案中的最佳解决方案。
给定 表示每个训练实例的第k个特征值和二阶梯度统计。 我们可以定义一个排名函数。
表示特征值小于z的实例的比例。目标是找到候选分割点 ：
这里 是一个近似因子，直觉上，这意味着大约有 个候选点。为了了解为什么 会代表权重，我们可以将等式(3)改写为：
这是用 和 精确加权的平方损失。
在许多现实问题中，输入稀疏是很常见的。使算法了解数据中的稀疏模式是非常重要的。为了做到这一点，我们建议在每个树节点中添加一个默认方向，如图4所示。当稀疏矩阵x中缺少A值时，实例将被分类为默认方向。
从数据中学习最佳默认方向。 该算法显示在Alg3中。 关键的改进是只访问non-missing entries。
树学习中最耗时的部分是将数据按顺序排列。 为了降低分类成本，我们建议将数据存储在内存单元中，我们称之为块。每个块中的数据以压缩列（CSC）格式存储，每列按相应的特征值排序。 该输入数据布局通常需要在训练之前计算一次，并且可以在以后的迭代中重复使用。
在精确的贪婪算法中，我们将整个数据库存储在一个块中，并通过对预先排序的条目进行lin-early扫描来运行拆分搜索算法。 我们集体对所有叶子进行分割，因此对块的一次扫描会收集所有叶子中分割候选的统计数据。 图6显示了我们如何将数据集转换为格式并使用块结构找到最佳分割。
收集每列的统计数据可以并行化，为我们提供了一种用于拆分查找的并行算法。 重要的是，列块结构还支持列子数据，因为很容易在块中选择列的子集
虽然所提出的块结构有助于优化分裂查找的计算复杂度，但是新算法需要通过行索引间接提取梯度统计量，因为这些值是按特征顺序访问的。 这是一种非连续的内存访问。 分裂枚举的简单实现引入了累积和非连续记忆提取操作之间的立即读/写依赖性（参见图8）。 当梯度统计信息不适合CPU缓存并发生缓存未命中时，这会减慢split finding。
对于精确的贪婪算法，我们可以通过缓存感知预取算法来缓解这个问题。具体来说，我们在每个线程中分配一个内部缓冲区，获取数据统计信息，然后以小批量的方式执行累加。这种预取将directread/write依赖项更改为更长的依赖项，并有助于在预取中的行数很大时减少运行时开销。
我们系统的一个目标是充分利用机器的资源来实现可扩展的学习。除处理器和内存外，利用磁盘空间处理不适合主内存的数据也很重要。为了实现核外计算，我们将数据分成多个块，并将每个块存储在磁盘上。在计算过程中，使用独立的线程将块预取到主内存缓冲区是很重要的，因此计算可以在与磁盘读取相关的情况下进行。但是，这并不能完全解决问题，因为磁盘读取占用了大部分计算时间。减少开销并增加磁盘IO的吞吐量非常重要。
Block Compression 我们使用的第一种技术是块压缩。 该块由列压缩，并在加载到主存储器时由独立的线程在运行中解压缩。
Block Sharding 第二种技术是以另一种方式将数据分割到多个磁盘上。预提取线程被分配给每个磁盘，并将数据提取到内存缓冲区中。
