PaperlayerView exact revision on arXiv

Source-linked AI summary

XGBoost: A Scalable Tree Boosting System

Tianqi Chen, Carlos Guestrin

arXiv:1603.02754v3cs.LG

TL;DR

Existing tree-boosting systems lacked an end-to-end approach combining scalability techniques for real-world large-scale learning. This paper presents XGBoost with sparsity-aware learning, weighted quantile sketching, and system optimizations, achieving state-of-the-art results across problems while scaling to billions of examples with fewer resources.

  • Problem

    Existing work had not combined out-of-core computation, cache-aware learning, and sparsity-aware learning in an end-to-end tree-boosting system.

  • Method

    XGBoost combines scalable end-to-end tree boosting with sparsity-aware learning, weighted quantile sketching, and cache-conscious system optimizations.

  • Results

    17 of 29 Kaggle challenge-winning solutions in 2015 used XGBoost, which delivered state-of-the-art results across a wide range of problems.

  • Takeaways & Limitations

    XGBoost shows that cache access patterns, data compression, and sharding are essential elements for scalable end-to-end tree boosting.

Abstract

from arXiv · show

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.

1. INTRODUCTION

XGBoost is presented as a scalable end-to-end tree boosting system motivated by the strong practical performance of gradient tree boosting and its variants. Its success is attributed to algorithmic and systems innovations that deliver broad state-of-the-art performance and scalability across large datasets.

  • 1. INTRODUCTION: Gradient tree boosting is widely used in practice, achieving state-of-the-art results on classification benchmarks, ranking tasks through LambdaMART, ad click-through-rate prediction, and ensemble applications such as the Netflix prize.The paper positions XGBoost within this broader success of tree boosting methods.
  • 1. INTRODUCTION: XGBoost appeared in 17 of 29 Kaggle challenge-winning solutions published in 2015, with eight solutions using only XGBoost.The solutions covered diverse tasks including sales prediction, event classification, text classification, customer behavior prediction, and ad click-through-rate prediction.
  • 1. INTRODUCTION: The system runs more than ten times faster than existing popular single-machine solutions and scales to billions of examples in distributed or memory-limited settings.Its scalability also enables processing hundreds of millions of examples on a desktop and larger datasets with fewer cluster resources.
  • 1. INTRODUCTION: The paper’s main contribution is a highly scalable end-to-end tree boosting system that combines algorithmic and systems optimizations for real-world use.The authors emphasize that combining out-of-core, cache-aware, and sparsity-aware learning provides a novel end-to-end solution.
  • 1. INTRODUCTION: The proposed learning innovations are a theoretically justified weighted quantile sketch for efficient proposal calculation and a novel sparsity-aware algorithm for parallel tree learning.These methods address efficient split proposals and sparse-data tree learning.
  • 1. INTRODUCTION: XGBoost also introduces a cache-aware block structure for out-of-core tree learning, extending scalability beyond in-memory computation.The system-level design combines cache-aware computation with out-of-core processing and data sharding or compression optimizations.

2. TREE BOOSTING IN A NUTSHELL

This section presents gradient tree boosting as an additive ensemble of regression trees trained by minimizing a regularized objective. It derives second-order greedy optimization and describes shrinkage and feature subsampling to improve generalization and efficiency.

  • Tree ensemble model: XGBoost predicts by summing continuous leaf scores from K regression trees, with each tree mapping examples to leaf indices.The ensemble uses independent tree structures and leaf weights, and the final prediction sums the corresponding scores.
  • Regularized objective: The model minimizes a differentiable loss plus tree-complexity regularization, which smooths learned weights and favors simple predictive functions.The regularized objective is optimized in an additive manner because tree functions are not ordinary Euclidean parameters.
  • Tree construction: Second-order gradient statistics enable greedy tree construction: leaf sums determine structure scores, while candidate splits are evaluated by their loss reduction.The structure score generalizes decision-tree impurity scoring to a wider range of objective functions.
  • Overfitting prevention: Shrinkage scales each newly added tree’s weights by η, reducing individual-tree influence and leaving future trees room to improve the model.This technique is introduced alongside the regularized objective as an additional means of preventing overfitting.
  • Overfitting prevention: Column subsampling further prevents overfitting than traditional row subsampling according to user feedback and accelerates the later parallel algorithm.The passage states that column subsampling was implemented in TreeNet [13] and was absent from existing open-source packages.

3. SPLIT FINDING ALGORITHMS

XGBoost supports exact greedy split finding on a single machine and approximate split finding for data that exceeds memory or is distributed. Its approximate framework uses percentile-based proposals, while weighted quantile sketching and sparsity-aware defaults address weighted data and missing entries.

  • Split finding framework: XGBoost supports exact greedy split finding for single-machine data and approximate split finding with both local and global proposals for all settings.Users can choose between methods according to their needs.
  • Approximate split finding: The approximate algorithm proposes percentile-based candidate splits, maps continuous features into buckets, aggregates statistics, and selects the best proposed split.Global proposals are made once, whereas local proposals are refined after each split; global methods need fewer proposal steps but usually more candidates.
  • Weighted quantile sketch: A distributed weighted quantile sketch handles weighted data with provable theoretical guarantees through merge and prune operations that preserve accuracy.Weighted candidates are needed because second-order gradient statistics act as instance weights, and existing unweighted sketches do not solve this problem.
  • Sparsity-aware split finding: The sparsity-aware algorithm learns default directions for missing or absent values while enumerating only non-missing entries.It can also handle user-specified non-presence values by restricting enumeration to consistent solutions.
  • Sparsity-aware split finding: More than 50 times faster, the sparsity-aware algorithm outperforms the naive implementation on the sparse Allstate-10K dataset.The method’s computation is linear in the number of non-missing entries and handles sparsity patterns uniformly.

4. SYSTEM DESIGN

XGBoost’s system design organizes sorted, compressed data into reusable blocks to reduce split-finding costs and support scalable exact, approximate, parallel, and out-of-core computation. Cache-aware access and block-size selection further address memory-access and parallelization bottlenecks.

  • Approximate algorithms: For approximate algorithms, multiple row-partitioned blocks support distributed or disk-based storage, and sorted columns make quantile finding a linear scan.This is especially valuable for local proposal algorithms, which generate candidates frequently at each branch.
  • Resource utilization: The block layout enables parallel split-statistics collection and straightforward column subsampling, while multiple disk-resident blocks with independent prefetching enable out-of-core computation.Independent threads prefetch blocks into main-memory buffers so computation can proceed concurrently with disk reading.
  • Block structure and complexity: The block structure reduces exact greedy boosting from O(Kd∥x∥0 log n) to O(Kd∥x∥0 + ∥x∥0 log n), with preprocessing amortized across iterations.Data is stored once in compressed-column blocks with sorted feature values, enabling reuse during later training iterations.
  • Cache-aware computation: Non-continuous gradient-statistics access creates cache-related stalls, while cache-aware prefetching makes the exact greedy algorithm twice as fast as the naive version on large datasets.The method fetches statistics into per-thread buffers and accumulates them in mini-batches; the reported comparison covers the Higgs and Allstate datasets.
  • Block-size selection: Choosing 216 examples per block balances cache capacity and parallelization, because overly small blocks reduce thread workload while overly large blocks cause cache misses.Block size is defined by the maximum number of examples per block, reflecting the cache storage cost of gradient statistics.

5. RELATED WORKS

XGBoost builds on gradient tree boosting and regularization while extending parallel tree learning with systems techniques. Its weighted quantile sketch addresses weighted-data quantiles as a problem not previously solved to the authors’ knowledge.

  • Gradient boosting and regularization: XGBoost implements gradient boosting, extending gradient tree boosting’s uses in classification, learning to rank, and structured prediction with regularization against overfitting.Its regularized model resembles regularized greedy forests but simplifies the objective and algorithm for parallelization.
  • Parallel tree learning: Existing parallel tree-learning methods mostly use the paper’s approximate framework, while XGBoost also supports column-wise partitioning with the exact greedy algorithm [23].Cache-aware prefetching can benefit this column-partitioned approach, complementing prior work’s algorithmic focus.
  • Weighted quantile sketch: The weighted quantile sketch is presented as the first method, to the authors’ knowledge, for finding quantiles on weighted data.Unlike classical unweighted quantile summaries, this generalization may benefit other data-science and machine-learning applications.

6. END TO END EVALUATIONS

End-to-end evaluations show that XGBoost is portable across data-science ecosystems and scales from single-machine learning-to-rank workloads to out-of-core and distributed processing of 1.7 billion examples. Compression, disk sharding, and out-of-core computation are key to its performance and scalability.

  • Implementation: The open-source XGBoost package supports weighted classification, ranking, user-defined objectives, multiple programming languages, and native integration with data-science pipelines.Its distributed version is built on the Rabit library for allreduce.
  • Experimental setup: The evaluation uses Allstate, Higgs, Yahoo! learning-to-rank, and Criteo datasets, assigning the first three to single-machine experiments and Criteo to distributed and out-of-core settings.Allstate and Higgs use randomly selected 10M-instance training sets; Yahoo! uses its official train-test split.
  • Learning-to-rank evaluation: On Yahoo! learning-to-rank data, XGBoost runs faster than pGBRT, while column subsampling further reduces runtime and slightly improves performance.XGBoost uses the exact greedy algorithm, whereas pGBRT supports only an approximate algorithm.
  • Out-of-core evaluation: Compression provides a 3x speedup, while sharding across two disks adds another 2x speedup in out-of-core Criteo experiments.The experiment uses one AWS c3.8xlarge machine with 32 vcores, two 320 GB SSDs, and 60 GB RAM.
  • Distributed evaluation: XGBoost runs faster than Spark MLLib [18] and H2O, scales smoothly to all 1.7 billion examples, and uses out-of-core computation when memory is insufficient.On 32 EC2 nodes, the comparison uses varying Criteo input sizes; Spark suffers drastic slowdown when running out of memory.

7. CONCLUSION

The paper presents XGBoost as a scalable tree boosting system that is widely used and achieves state-of-the-art results on many problems. It contributes methods for sparse and approximate learning and identifies key systems considerations for scalability.

  • XGBoost is a scalable tree boosting system widely used by data scientists and providing state-of-the-art results on many problems.
  • The paper proposes a novel sparsity-aware algorithm for handling sparse data.
  • It introduces a theoretically justified weighted quantile sketch for approximate learning.
  • The authors identify cache access patterns, data compression, and sharding as essential elements for building a scalable end-to-end system.

APPENDIX · A. WEIGHTED QUANTILE SKETCH

This section introduces a weighted quantile sketch for approximate tree boosting on weighted data, extending quantile-summary methods built around merge and prune operations. The proposed summary preserves the guarantees of the GK framework while supporting weighted quantiles.

  • A. WEIGHTED QUANTILE SKETCH: Quantile summaries answer quantile queries with relative accuracy of ϵ and form the basis of distributed and streaming quantile computation.The section identifies the GK algorithm [14] and GK-based extensions as classical approaches.
  • A. WEIGHTED QUANTILE SKETCH: The merge operation combines summaries with errors ϵ1 and ϵ2 into a summary whose approximation error is max(ϵ1, ϵ2).This operation is one of the two basic quantile-summary operations.
  • A. WEIGHTED QUANTILE SKETCH: The prune operation reduces a summary to b+1 elements and changes its approximation error from ϵ to ϵ + 1.This operation provides the summary-size reduction described in the section.
  • A. WEIGHTED QUANTILE SKETCH: The weighted quantile sketch addresses the need to compute quantiles on weighted data for approximate tree boosting, which existing algorithms do not support.It provides a weighted quantile summary structure for this more general problem.
  • A. WEIGHTED QUANTILE SKETCH: The new weighted summary includes merge and prune operations with the same guarantee as the GK summary.This preserves the guarantees associated with the established summary framework.
  • A. WEIGHTED QUANTILE SKETCH: Because it retains these operations and guarantees, the weighted summary can be plugged into frameworks that use GK summaries as building blocks.Quantile summaries with merge and prune operations support distributed and streaming quantile algorithms [24].

A.1 Formalization and Definitions

This section formalizes weighted multisets, rank functions, and quantile summaries for estimating point ranks under a total order. It extends summary functions beyond stored points and defines the approximation framework used in later proofs.

  • Weighted data: The input is a weighted multiset of ordered points, allowing duplicate records with identical positions and weights.Each point has a nonnegative weight, and the multiset weight is the sum of all point weights.
  • Quantile summary: A weighted quantile summary stores an ordered subset of input points together with approximate rank and weight functions, while preserving the minimum and maximum points.Because the functions are defined only on the stored subset, the summary requires 4k records for k stored points.
  • Function extension: The summary functions are extended to all positions by handling points below, above, or between the stored points without requiring extra storage.The extension is based on the ground-case definitions on the stored subset.
  • Approximation guarantee: An ϵ-approximate summary bounds rank-estimation error by at most ϵω(D), with equivalent constraints on the stored and extended functions.The stated equivalence supports later proofs using constraints on the extended functions.

A.2 Construction of Initial Summary

For a small multiset D, the method constructs an initial summary Q(D) from the values in D. This summary is 0-approximate, answers all queries accurately, and can support subsequent operations.

  • The initial summary Q(D) is constructed from a small multiset D.
  • Q(D) includes the set S of all values appearing in D.
  • The constructed summary is 0-approximate because it answers all queries accurately.
  • The summary can be used in subsequent operations.

A.3 Merge Operation · A.4 Prune Operation

The merge operation combines two quantile summaries into a valid summary whose approximation error is the larger input error. The prune operation queries an existing summary to fit a memory budget while preserving validity, with its approximation guarantee characterized by Theorem A.2.

  • A.3 Merge Operation: The merged summary forms its point set from points in S1 or S2 and adds the corresponding weights from both input summaries.For x_i in the merged support, ˜ω_D(x_i) = ˜ω_D1(x_i) + ˜ω_D2(x_i).
  • A.3 Merge Operation: The merge construction satisfies all constraints in Definition A.1, so Q(D) is a valid quantile summary.The construction combines summaries for D = D1 ∪ D2.
  • A.3 Merge Operation: If Q(D1) and Q(D2) are ϵ1- and ϵ2-approximate summaries, their merged summary is max(ϵ1, ϵ2)-approximate.The merged summary is proven valid using the additive properties of rank and weight quantities and the extended constraint property.
  • A.4 Prune Operation: The query function g(Q, d) returns a data value whose rank is close to the requested rank d.It is introduced before pruning and defined in Algorithm 4.
  • A.4 Prune Operation: Given a summary and memory budget b, pruning queries the original summary to select at most b+1 retained entries for a new summary Q′(D).The retained entries x′_i are selected by querying the original summary, and the new summary restricts the original domain to S′.
  • A.4 Prune Operation: Pruning preserves a valid quantile summary because Q′ copies rank and weight information from Q over the restricted domain, and duplicate retained entries can be removed safely.All elements of Q′ come from Q, allowing the constraints in Definition A.1 to be verified.
  • A.4 Prune Operation: Theorem A.2 characterizes the approximation guarantee of pruning an ϵ-approximate summary under memory budget b.The supplied passage states that the pruned summary is a bounded-error approximation, but the displayed bound is truncated.
Loading 1603.02754v3…