XGBoost: A Scalable Tree Boosting System

1 xgboost : A Scalable tree Boosting SystemTianqi ChenUniversity of GuestrinUniversity of Boosting is a highly effective and widely used machinelearning method. In this paper, we describe a Scalable end-to-end tree Boosting System called xgboost , which is usedwidely by data scientists to achieve state-of-the-art resultson many machine learning challenges. We propose a novelsparsity-aware algorithm for sparse data and weighted quan-tile sketch for approximate tree learning. More importantly,we provide insights on cache access patterns, data compres-sion and sharding to build a Scalable tree Boosting combining these insights, xgboost scales beyond billionsof examples using far fewer resources than existing Concepts Methodologies Machine learning; Informationsystems Data mining;KeywordsLarge-scale Machine Learning1.

2 INTRODUCTIONM achine learning and data-driven approaches are becom-ing very important in many areas. Smart spam classifiersprotect our email by learning from massive amounts of spamdata and user feedback; advertising systems learn to matchthe right ads with the right context; fraud detection systemsprotect banks from malicious attackers; anomaly event de-tection systems help experimental physicists to find eventsthat lead to new physics. There are two important factorsthat drive these successful applications: usage of effective(statistical) models that capture the complex data depen-dencies and Scalable learning systems that learn the modelof interest from large the machine learning methods used in practice,gradient tree Boosting [9]1is one technique that shines in1 Gradient tree Boosting is also known as gradient boostingmachine (GBM) or gradient boosted regression tree (GBRT)

3 Permission to make digital or hard copies of part or all of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for third-party components of this work must be all other uses, contact the owner/author(s).c 2016 Copyright held by the owner/author(s).ACM ISBN .DOI:many applications. tree Boosting has been shown to givestate-of-the-art results on many standard classification bench-marks [14].

4 LambdaMART [4], a variant of tree Boosting forranking, achieves state-of-the-art result for ranking prob-lems. Besides being used as a stand-alone predictor, it isalso incorporated into real-world production pipelines for adclick through rate prediction [13]. Finally, it is the de-factochoice of ensemble method and is used in challenges such asthe Netflix prize [2].In this paper, we describe xgboost , a Scalable machinelearning System for tree Boosting . The System is available asan open source package2. The impact of the System has beenwidely recognized in a number of machine learning and datamining challenges.

5 Take the challenges hosted by the ma-chine learning competition site Kaggle for example. Amongthe 29 challenge winning solutions3published at Kaggle sblog during 2015, 17 solutions used xgboost . Among thesesolutions, eight solely used xgboost to train the model,while most others combined xgboost with neural nets in en-sembles. For comparison, the second most popular method,deep neural nets, was used in 11 solutions. The successof the System was also witnessed in KDDCup 2015, whereXGBoost was used by every winning team in the , the winning teams reported that ensemble meth-ods outperform a well-configured xgboost by only a smallamount [1].

6 These results demonstrate that our System gives state-of-the-art results on a wide range of problems. Examples ofthe problems in these winning solutions include: store salesprediction; high energy physics event classification; web textclassification; customer behavior prediction; motion detec-tion; ad click through rate prediction; malware classification;product categorization; hazard risk prediction; massive on-line course dropout rate prediction. While domain depen-dent data analysis and feature engineering play an importantrole in these solutions, the fact that xgboost is the consen-sus choice of learner shows the impact and importance ofour System and tree most important factor behind the success of XGBoostis its scalability in all scenarios.

7 The System runs more thanten times faster than existing popular solutions on a singlemachine and scales to billions of examples in distributed ormemory-limited settings. The scalability of xgboost is dueto several important systems and algorithmic innovations include: a novel tree learning algorithm2 solutions come from of top-3 teams of each :submit/1502704 [ ] 9 Mar 2016 Figure 1: tree Ensemble Model. The final predic-tion for a given example is the sum of predictionsfrom each for handlingsparse data; a theoretically justified weightedquantile sketch procedure enables handling instance weightsin approximate tree learning.

8 Parallel and distributed com-puting makes learning faster which enables quicker model ex-ploration. More importantly, xgboost exploits out-of-corecomputation and enables data scientists to process hundredmillions of examples on a desktop. Finally, it is even moreexciting to combine these techniques to make an end-to-endsystem that scales to even larger data with the least amountof cluster resources. The major contributions of this paperis listed as follows: We design and build a highly Scalable end-to-end treeboosting System . We introduce a novel sparsity-aware algorithm for par-allel tree learning.

9 We propose a theoretically justified weighted quantilesketch for efficient proposal calculation. We propose an effective cache-aware block structurefor out-of-core tree there are some existing works on parallel tree boost-ing [19, 20, 16], the directions such as out-of-core compu-tation, cache-aware and sparsity-aware learning have notbeen explored. More importantly, an end-to-end systemthat combines all of these aspects gives a novel solution forreal-world use-cases. This enables data scientists as wellas researchers to build powerful variants of tree boostingalgorithms [6, 7].

10 Besides these major contributions, wealso make additional improvements in proposing a regular-ized learning objective and supporting column sub-sampling,which we will include for remainder of the paper is organized as follows. Wewill first review tree Boosting and introduce a general regu-larized objective in Sec. 2. We then describe the split findingalgorithms in Sec. 3 as well as the System design in Sec. 4, in-cluding experimental results when relevant to provide quan-titative support for each optimization we describe. Relatedwork is discussed in Sec.