XGBoost explained

XGBoost
Developer:	The XGBoost Contributors
Operating System:	Linux, macOS, Microsoft Windows
Programming Language:	C++
Genre:	Machine learning
License:	Apache License 2.0

XGBoost^[1] (eXtreme Gradient Boosting) is an open-source software library which provides a regularizing gradient boosting framework for C++, Java, Python,^[2] R,^[3] Julia,^[4] Perl,^[5] and Scala. It works on Linux, Microsoft Windows,^[6] and macOS.^[7] From the project description, it aims to provide a "Scalable, Portable and Distributed Gradient Boosting (GBM, GBRT, GBDT) Library". It runs on a single machine, as well as the distributed processing frameworks Apache Hadoop, Apache Spark, Apache Flink, and Dask.^{[8] [9]}

XGBoost gained much popularity and attention in the mid-2010s as the algorithm of choice for many winning teams of machine learning competitions.^[10]

History

XGBoost initially started as a research project by Tianqi Chen^[11] as part of the Distributed (Deep) Machine Learning Community (DMLC) group. Initially, it began as a terminal application which could be configured using a libsvm configuration file. It became well known in the ML competition circles after its use in the winning solution of the Higgs Machine Learning Challenge. Soon after, the Python and R packages were built, and XGBoost now has package implementations for Java, Scala, Julia, Perl, and other languages. This brought the library to more developers and contributed to its popularity among the Kaggle community, where it has been used for a large number of competitions.

It was soon integrated with a number of other packages making it easier to use in their respective communities. It has now been integrated with scikit-learn for Python users and with the caret package for R users. It can also be integrated into Data Flow frameworks like Apache Spark, Apache Hadoop, and Apache Flink using the abstracted Rabit^[12] and XGBoost4J.^[13] XGBoost is also available on OpenCL for FPGAs.^[14] An efficient, scalable implementation of XGBoost has been published by Tianqi Chen and Carlos Guestrin.^[15]

While the XGBoost model often achieves higher accuracy than a single decision tree, it sacrifices the intrinsic interpretability of decision trees.  For example, following the path that a decision tree takes to make its decision is trivial and self-explained, but following the paths of hundreds or thousands of trees is much harder.

Features

Salient features of XGBoost which make it different from other gradient boosting algorithms include:^{[16] [17] [15]}

• Clever penalization of trees
• A proportional shrinking of leaf nodes
• Newton Boosting
• Extra randomization parameter
• Implementation on single, distributed systems and out-of-core computation
  • Automatic Feature selection Theoretically justified weighted quantile sketching for efficient computation
• Parallel tree structure boosting with sparsity
• Efficient cacheable block structure for decision tree training

The algorithm

XGBoost works as Newton-Raphson in function space unlike gradient boosting that works as gradient descent in function space, a second order Taylor approximation is used in the loss function to make the connection to Newton Raphson method.

A generic unregularized XGBoost algorithm is:Input: training set

\{(x _{i,} y _{i)\}} ^{N} ^{i =1} , a differentiable loss function L(y, F(x)) , a number of weak learners M and a learning rate \alpha .

Algorithm:

1. Initialize model with a constant value: $$\backslash hat\_(x)\; =\; \backslash underset\; \backslash sum\_^N\; L(y\_i,\; \backslash theta).$$
2. For = 1 to :
   1. Compute the 'gradients' and 'hessians': $$\backslash begin$$

\hat_m(x_i) &= \left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_. \\\hat_m(x_i) &= \left[\frac{\partial^2 L(y_i,f(x_i))}{\partial f(x_i)^2} \right]_.\end

1. 1. Fit a base learner (or weak learner, e.g. tree) using the training set

\left\{x _{i,\dfrac{\hat{g}} _{m(x} _{i)}{\hat{h}} _{m(x} _{i)}\right\}} ^{N} ^{i =1} by solving the optimization problem below: $$\backslash hat\_m=\backslash underset\backslash sum\_^\backslash frac\backslash hat\_m(x\_i)\backslash left[\backslash phi(x\_i)\; -\; \backslash frac\{\backslash hat\{g\}\_m(x\_i)\}\{\backslash hat\{h\}\_m(x\_i)\}\backslash right]^2.$$ $$\backslash hat\_m(x)=\backslash alpha\; \backslash hat\_m(x).$$

1. 1. Update the model: $$\backslash hat\_(x)\; =\; \backslash hat\_(x)\; +\; \backslash hat\_m(x).$$
2. Output

\hat{f}(x) = \hat{f} _{(M)} (x) = \sum ^{M} _{m =0} \hat{f} _{m(x).}

Awards

• John Chambers Award (2016)^[18]
• High Energy Physics meets Machine Learning award (HEP meets ML) (2016)^[19]

See also

• LightGBM
• CatBoost

Notes and References

1. Web site: GitHub project webpage . . June 2022 . 2016-04-05 . 2021-04-01 . https://web.archive.org/web/20210401110045/https://github.com/dmlc/xgboost . live .
2. Web site: Python Package Index PYPI: xgboost. 2016-08-01. 2017-08-23. https://web.archive.org/web/20170823013244/https://pypi.python.org/pypi/xgboost. live.
3. Web site: CRAN package xgboost. 2016-08-01. 2018-10-26. https://web.archive.org/web/20181026172734/https://cran.r-project.org/web/packages/xgboost/index.html. live.
4. Web site: Julia package listing xgboost. 2016-08-01. 2016-08-18. https://web.archive.org/web/20160818144844/http://pkg.julialang.org/?pkg=XGBoost#XGBoost. dead.
5. Web site: CPAN module AI::XGBoost. 2020-02-09. 2020-03-28. https://web.archive.org/web/20200328204421/https://metacpan.org/pod/AI::XGBoost. live.
6. Web site: Installing XGBoost for Anaconda in Windows. IBM. 2016-08-01. 2018-05-08. https://web.archive.org/web/20180508185540/https://www.ibm.com/developerworks/community/blogs/jfp/entry/Installing_XGBoost_For_Anaconda_on_Windows?lang=en. live.
7. Web site: Installing XGBoost on Mac OSX. IBM. 2016-08-01. 2018-05-08. https://web.archive.org/web/20180508185643/https://www.ibm.com/developerworks/community/blogs/jfp/entry/Installing_XGBoost_on_Mac_OSX?lang=en. live.
8. Web site: Dask Homepage. 2021-07-15. 2022-09-14. https://web.archive.org/web/20220914010952/https://www.dask.org/. live.
9. Web site: Distributed XGBoost with Dask — xgboost 1.5.0-dev documentation. 2021-07-15. xgboost.readthedocs.io. 2022-06-04. https://web.archive.org/web/20220604151406/https://xgboost.readthedocs.io/en/latest/tutorials/dask.html. live.
10. Web site: XGBoost - ML winning solutions (incomplete list). GitHub. 2016-08-01. 2017-08-24. https://web.archive.org/web/20170824150805/https://github.com/dmlc/xgboost/tree/master/demo#machine-learning-challenge-winning-solutions. live.
11. Web site: Story and Lessons behind the evolution of XGBoost. 2016-08-01. 2016-08-07. https://web.archive.org/web/20160807033610/http://homes.cs.washington.edu/~tqchen/2016/03/10/story-and-lessons-behind-the-evolution-of-xgboost.html. dead.
12. Web site: Rabit - Reliable Allreduce and Broadcast Interface. GitHub. 2016-08-01. 2018-06-11. https://web.archive.org/web/20180611023836/https://github.com/dmlc/rabit. live.
13. Web site: XGBoost4J. 2016-08-01. 2018-05-08. https://web.archive.org/web/20180508185409/https://xgboost.readthedocs.io/en/latest/jvm/index.html. live.
14. Web site: XGBoost on FPGAs. GitHub. 2019-08-01. 2020-09-13. https://web.archive.org/web/20200913114254/https://github.com/inaccel/xgboost. live.
15. Chen . Tianqi . Guestrin . Carlos . Krishnapuram . Balaji . Shah . Mohak . Smola . Alexander J. . Aggarwal . Charu C. . Shen . Dou . Rastogi . Rajeev . XGBoost: A Scalable Tree Boosting System . 10.1145/2939672.2939785 . 1603.02754 . 9781450342322 . 4650265 . 785–794 . ACM . Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016 . 2016.
16. Web site: Gradient Boosting and XGBoost. Gandhi. Rohith. 2019-05-24. Medium. en. 2020-01-04. 2020-03-28. https://web.archive.org/web/20200328204417/https://medium.com/hackernoon/gradient-boosting-and-xgboost-90862daa6c77. live.
17. Web site: Tree Boosting With XGBoost – Why Does XGBoost Win "Every" Machine Learning Competition?. 2017-10-22. Synced. en-US. 2020-01-04. 2020-03-28. https://web.archive.org/web/20200328204421/https://syncedreview.com/2017/10/22/tree-boosting-with-xgboost-why-does-xgboost-win-every-machine-learning-competition/. live.
18. Web site: John Chambers Award Previous Winners. 2016-08-01. 2017-07-31. https://web.archive.org/web/20170731231612/http://stat-computing.org/awards/jmc/winners.html. live.
19. Web site: HEP meets ML Award. 2016-08-01. 2018-05-08. https://web.archive.org/web/20180508185553/https://higgsml.lal.in2p3.fr/prizes-and-award/award/. live.