Tree boosting is a highly effective and widely used machine learning method. In this paper, we describe a scalable end-to-end tree boosting system called XGBoost, which is used widely by data scientists to achieve state-of-the-art results on many machine learning challenges. We propose a novel sparsity-aware algorithm for sparse data and weighted quantile sketch for approximate tree learning. More importantly, we provide insights on cache access patterns, data compression and sharding to build a scalable tree boosting system. By combining these insights, XGBoost scales beyond billions of examples using far fewer resources than existing systems.
核心贡献 · Key contributions
提出 XGBoost，一个可扩展的端到端树提升系统，在众多机器学习挑战中取得最先进的结果。 Proposes XGBoost, a scalable end-to-end tree boosting system achieving state-of-the-art results on many ML challenges.
引入一种新颖的稀疏感知算法，高效处理稀疏数据。 Introduces a novel sparsity-aware algorithm for handling sparse data efficiently.
开发了一种理论上合理的加权分位数草图，用于近似树学习。 Develops a theoretically justified weighted quantile sketch for approximate tree learning.
提供了关于缓存访问模式、数据压缩和分片的见解，以构建可扩展系统。 Provides insights on cache access patterns, data compression, and sharding to build a scalable system.
XGBoost 使用比现有系统少得多的资源，可扩展到数十亿样本。 XGBoost scales beyond billions of examples using far fewer resources than existing systems.
在单机上比流行解决方案快 10 倍以上。 Achieves over 10x speedup compared to popular solutions on a single machine.
局限 · Limitations
加权分位数草图假设二阶梯度统计作为权重，可能并非对所有损失函数最优。 The weighted quantile sketch assumes second-order gradient statistics as weights, which may not be optimal for all loss functions.
缓存感知预取主要对大数据集上的精确贪心算法有益；近似算法需要仔细调整块大小。 Cache-aware prefetching is primarily beneficial for exact greedy algorithm on large datasets; approximate algorithms require careful block size tuning.
核外计算依赖磁盘 I/O，尽管有压缩和分片，仍可能成为瓶颈。 Out-of-core computation relies on disk I/O, which can become a bottleneck despite compression and sharding.
在极高维数据集上，由于列子采样开销，系统性能可能下降。 The system's performance may degrade on datasets with extremely high dimensionality due to column subsampling overhead.
论文未在图像或文本等非表格数据上与深度学习方法进行广泛比较。 The paper does not extensively compare with deep learning methods on non-tabular data like images or text.
论文章节 · Sections（共 22）
摘要Abstract
1 引言1 Introduction
2 树提升简介2 Tree Boosting in a NutShell
2.1 正则化学习目标2.1 Regularized Learning Objective
2.2 梯度提升树2.2 Gradient Tree Boosting
2.3 收缩与列子采样2.3 Shrinkage and Column Subsampling
3.1 基本精确贪心算法3.1 Basic Exact Greedy Algorithm
3.2 近似算法3.2 Approximate Algorithm
3.3 加权分位数草图3.3 Weighted Quantile Sketch
3.4 稀疏感知的切分点查找3.4 Sparsity-aware Split Finding
4.1 用于并行学习的列块4.1 Column Block for Parallel Learning
4.2 缓存感知访问4.2 Cache-aware Access
4.3 核外计算的块处理4.3 Blocks for Out-of-core Computation