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 Machine Learning1. 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 s-pam data and user feedback; advertising systems learn tomatch the right ads with the right context; fraud detectionsystems protect banks from malicious attackers; anomalyevent detection systems help experimental physicists to findevents that lead to new physics.

2 There are two importan-t factors that drive these successful applications: usage ofeffective (statistical) models that capture the complex datadependencies and Scalable learning systems that learn themodel of interest from large the machine learning methods used in practice,gradient tree Boosting [10]1is one technique that shinesin many applications. Tree Boosting has been shown togive state-of-the-art results on many standard classificationbenchmarks [16]. LambdaMART [5], a variant of tree boost -ing for ranking, achieves state-of-the-art result for ranking1 Gradient tree Boosting is also known as gradient boostingmachine (GBM) or gradient boosted regression tree (GBRT)Permission to make digital or hard copies of all or part 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 cita-tion on the first page.

3 Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re-publish, to post on servers or to redistribute to lists, requires prior specific permissionand/or a fee. Request permissions from 16, August 13-17, 2016, San Francisco, CA, USAc 2016 ACM. ISBN 978-1-4503-4232-2/16/08.. $ : Besides being used as a stand-alone predictor, itis also incorporated into real-world production pipelines forad click through rate prediction [15]. Finally, it is the de-facto choice of ensemble method and is used in challengessuch as the Netflix prize [3].In this paper, we describe XGBoost, a Scalable machinelearning System for tree Boosting . The System is availableas an open source package2. The impact of the System hasbeen widely recognized in a number of machine learning anddata mining challenges. Take the challenges hosted by themachine learning competition site Kaggle for example.

4 A-mong the 29 challenge winning solutions3published at Kag-gle s blog during 2015, 17 solutions used XGBoost. Amongthese solutions, eight solely used XGBoost to train the mod-el, while most others combined XGBoost with neural net-s in ensembles. For comparison, the second most popularmethod, deep neural nets, was used in 11 solutions. Thesuccess of the System was also witnessed in KDDCup 2015,where XGBoost was used by every winning team in the top-10. Moreover, the winning teams reported that ensemblemethods outperform a well-configured XGBoost by only asmall amount [1].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.

5 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. 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 algorithmis for handlingsparse data; a theoretically justified weightedquantile sketch procedure enables handling instance weightsin approximate tree learning. Parallel and distributed com-puting makes learning faster which enables quicker model ex-ploration. More importantly, XGBoost exploits out-of-core2 come from of top-3 teams of each and enables data scientists to process hundredmillions of examples on a desktop.

6 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 propose a theoretically justified weighted quantilesketch for efficient proposal calculation. We introduce a novel sparsity-aware algorithm for par-allel tree learning. We propose an effective cache-aware block structurefor out-of-core tree there are some existing works on parallel tree boost -ing [22, 23 , 19 ], 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 well asresearchers to build powerful variants of tree Boosting al-gorithms [7, 8].

7 Besides these major contributions, we alsomake additional improvements in proposing a regularizedlearning objective, which we will include for remainder of the paper is organized as follows. Wewill first review tree Boosting and introduce a regularizedobjective in We then describe the split finding meth-ods in as well as the System design in , includingexperimental results when relevant to provide quantitativesupport for each optimization we describe. Related workis discussed in Detailed end-to-end evaluations areincluded in Finally we conclude the paper in TREE Boosting IN A NUTSHELLWe review gradient tree Boosting algorithms in this sec-tion. The derivation follows from the same idea in existingliteratures in gradient Boosting . Specicially the second ordermethod is originated from Friedman et al. [12]. We make mi-nor improvements in the reguralized objective, which werefound helpful in Regularized Learning ObjectiveFor a given data set withnexamples andmfeaturesD={(xi,yi)}(|D|=n,xi Rm,yi R), a tree ensem-ble model (shown in ) usesKadditive functions topredict the output.

8 Yi= (xi) =K k=1fk(xi), fk F,(1)whereF={f(x) =wq(x)}(q:Rm T,w RT) is thespace of regression trees (also known as CART). Hereqrep-resents the structure of each tree that maps an example tothe corresponding leaf the number of leaves in thetree. Eachfkcorresponds to an independent tree structureqand leaf weightsw. Unlike decision trees, each regressiontree contains a continuous score on each of the leaf, we usewito represent score oni-th leaf. For a given example, wewill use the decision rules in the trees (given byq) to classifyFigure 1: Tree Ensemble Model. The final predic-tion for a given example is the sum of predictionsfrom each into the leaves and calculate the final prediction by sum-ming up the score in the corresponding leaves (given byw).To learn the set of functions used in the model, we minimizethe ( ) = il( yi,yi) + k (fk)where (f) = T+12 w 2(2)Herelis a differentiable convex loss function that measuresthe difference between the prediction yiand the second term penalizes the complexity of the model( , the regression tree functions).

9 The additional regular-ization term helps to smooth the final learnt weights to avoidover-fitting. Intuitively, the regularized objective will tendto select a model employing simple and predictive similar regularization technique has been used in Regu-larized greedy forest (RGF) [25] model. Our objective andthe corresponding learning algorithm is simpler than RGFand easier to parallelize. When the regularization parame-ter is set to zero, the objective falls back to the traditionalgradient tree Gradient Tree BoostingThe tree ensemble model in Eq. (2) includes functions asparameters and cannot be optimized using traditional opti-mization methods in Euclidean space. Instead, the modelis trained in an additive manner. Formally, let y(t)ibe theprediction of thei-th instance at thet-th iteration, we willneed to addftto minimize the following (t)=n i=1l(yi, yi(t 1)+ft(xi)) + (ft)This means we greedily add theftthat most improves ourmodel according to Eq.

10 (2). Second-order approximationcan be used to quickly optimize the objective in the generalsetting [12 ].L(t)'n i=1[l(yi, y(t 1)) +gift(xi) +12hif2t(xi)] + (ft)wheregi= y(t 1)l(yi, y(t 1)) andhi= 2 y(t 1)l(yi, y(t 1))are first and second order gradient statistics on the loss func-tion. We can remove the constant terms to obtain the fol-lowing simplified objective at stept. L(t)=n i=1[gift(xi) +12hif2t(xi)] + (ft)(3)Figure 2: Structure Score Calculation. We onlyneed to sum up the gradient and second order gra-dient statistics on each leaf, then apply the scoringformula to get the quality {i|q(xi) =j}as the instance set of leafj. Wecan rewrite Eq (3) by expanding as follows L(t)=n i=1[gift(xi) +12hif2t(xi)] + T+12 T j=1w2j=T j=1[( i Ijgi)wj+12( i Ijhi+ )w2j] + T(4)For a fixed structureq(x), we can compute the optimalweightw jof leafjbyw j= i Ijgi i Ijhi+ ,(5)and calculate the corresponding optimal value by L(t)(q) = 12T j=1( i Ijgi)2 i Ijhi+ + T.