View source for XGBoost

{{Short description|Gradient boosting machine learning library}}
{{Infobox software
| name                   = XGBoost
| logo                   = XGBoost_logo.png
| screenshot             =
| caption                =
| developer              = The XGBoost Contributors
| released               = {{Start date and age|2014|03|27}}
| latest release version = {{wikidata|property|edit|reference|P348}}
| latest release date    = {{start date and age|{{wikidata|qualifier|P348|P577}}}}
| operating system       = [[Linux]], [[macOS]], [[Microsoft Windows]]
| programming language   = [[C++]]
| genre                  = [[Machine learning]]
| license                = [[Apache License 2.0]]
| website                = {{URL|https://xgboost.ai/}}
}}
'''XGBoost'''<ref name="source-code">{{cite web |url=https://github.com/dmlc/xgboost |title=GitHub project webpage |website=[[GitHub]] |date=June 2022 |access-date=2016-04-05 |archive-date=2021-04-01 |archive-url=https://web.archive.org/web/20210401110045/https://github.com/dmlc/xgboost |url-status=live }}</ref> (eXtreme Gradient Boosting) is an [[Open-source software|open-source]] [[Library (computing)|software library]] which provides a [[regularization (mathematics)|regularizing]] [[gradient boosting]] framework for [[C++]], [[Java (programming language)|Java]], [[Python (programming language)|Python]],<ref name="xgboost-python">{{Cite web|url=https://pypi.python.org/pypi/xgboost/|title=Python Package Index PYPI: xgboost|access-date=2016-08-01|archive-date=2017-08-23|archive-url=https://web.archive.org/web/20170823013244/https://pypi.python.org/pypi/xgboost|url-status=live}}</ref> [[R (programming language)|R]],<ref name="xgboost-cran">{{Cite web|url=https://cran.r-project.org/web/packages/xgboost/index.html|title=CRAN package xgboost|access-date=2016-08-01|archive-date=2018-10-26|archive-url=https://web.archive.org/web/20181026172734/https://cran.r-project.org/web/packages/xgboost/index.html|url-status=live}}</ref> [[Julia (programming language)|Julia]],<ref name="xgboost-julia">{{Cite web|url=http://pkg.julialang.org/?pkg=XGBoost#XGBoost|title=Julia package listing xgboost|access-date=2016-08-01|archive-date=2016-08-18|archive-url=https://web.archive.org/web/20160818144844/http://pkg.julialang.org/?pkg=XGBoost#XGBoost|url-status=dead}}</ref> [[Perl (programming language)|Perl]],<ref name="xgboost-perl">{{Cite web|url=https://metacpan.org/pod/AI::XGBoost|title=CPAN module AI::XGBoost|access-date=2020-02-09|archive-date=2020-03-28|archive-url=https://web.archive.org/web/20200328204421/https://metacpan.org/pod/AI::XGBoost|url-status=live}}</ref> and [[Scala (programming language)|Scala]]. It works on [[Linux]], [[Microsoft Windows]],<ref name="xgboost-windows">{{Cite web|title=Installing XGBoost for Anaconda in Windows|website=[[IBM]]|url=https://www.ibm.com/developerworks/community/blogs/jfp/entry/Installing_XGBoost_For_Anaconda_on_Windows?lang=en|access-date=2016-08-01|archive-date=2018-05-08|archive-url=https://web.archive.org/web/20180508185540/https://www.ibm.com/developerworks/community/blogs/jfp/entry/Installing_XGBoost_For_Anaconda_on_Windows?lang=en|url-status=live}}</ref> and [[macOS]].<ref name="xgboost-macos">{{Cite web|title=Installing XGBoost on Mac OSX|website=[[IBM]]|url=https://www.ibm.com/developerworks/community/blogs/jfp/entry/Installing_XGBoost_on_Mac_OSX?lang=en|access-date=2016-08-01|archive-date=2018-05-08|archive-url=https://web.archive.org/web/20180508185643/https://www.ibm.com/developerworks/community/blogs/jfp/entry/Installing_XGBoost_on_Mac_OSX?lang=en|url-status=live}}</ref> 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 (software)|Dask]].<ref name="Dask-docs">{{Cite web|title=Dask Homepage|url=https://www.dask.org/|access-date=2021-07-15|archive-date=2022-09-14|archive-url=https://web.archive.org/web/20220914010952/https://www.dask.org/|url-status=live}}</ref><ref>{{Cite web|title=Distributed XGBoost with Dask — xgboost 1.5.0-dev documentation|url=https://xgboost.readthedocs.io/en/latest/tutorials/dask.html|access-date=2021-07-15|website=xgboost.readthedocs.io|archive-date=2022-06-04|archive-url=https://web.archive.org/web/20220604151406/https://xgboost.readthedocs.io/en/latest/tutorials/dask.html|url-status=live}}</ref>

XGBoost gained much popularity and attention in the mid-2010s as the algorithm of choice for many winning teams of [[machine learning]] [[Competitive programming|competitions]].<ref name="xgboost-competition-winners">{{Cite web|title=XGBoost - ML winning solutions (incomplete list)|website=[[GitHub]]|url=https://github.com/dmlc/xgboost/tree/master/demo#machine-learning-challenge-winning-solutions|access-date=2016-08-01|archive-date=2017-08-24|archive-url=https://web.archive.org/web/20170824150805/https://github.com/dmlc/xgboost/tree/master/demo#machine-learning-challenge-winning-solutions|url-status=live}}</ref>

==History==
XG Boost initially started as a research project by Tianqi Chen<ref name="history">{{Cite web|url=http://homes.cs.washington.edu/~tqchen/2016/03/10/story-and-lessons-behind-the-evolution-of-xgboost.html|title=Story and Lessons behind the evolution of XGBoost|access-date=2016-08-01|archive-date=2016-08-07|archive-url=https://web.archive.org/web/20160807033610/http://homes.cs.washington.edu/~tqchen/2016/03/10/story-and-lessons-behind-the-evolution-of-xgboost.html|url-status=dead}}</ref> 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 [https://www.kaggle.com/c/higgs-boson Higgs Machine Learning Challenge]. Soon after, the Python and R packages were built, and XGBoost now has package implementations for Java, [[Scala (programming language)|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.<ref name="xgboost-competition-winners" />

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 (programming language)|Python]] users and with the caret package for [[R (programming language)|R]] users. It can also be integrated into Data Flow frameworks like [[Apache Spark]], [[Apache Hadoop]], and [[Apache Flink]] using the abstracted Rabit<ref name="rabit">{{Cite web|url=https://github.com/dmlc/rabit|title=Rabit - Reliable Allreduce and Broadcast Interface|website=[[GitHub]]|access-date=2016-08-01|archive-date=2018-06-11|archive-url=https://web.archive.org/web/20180611023836/https://github.com/dmlc/rabit|url-status=live}}</ref> and XGBoost4J.<ref name="xgboost4j">{{Cite web|url=https://xgboost.readthedocs.io/en/latest/jvm/index.html|title=XGBoost4J|access-date=2016-08-01|archive-date=2018-05-08|archive-url=https://web.archive.org/web/20180508185409/https://xgboost.readthedocs.io/en/latest/jvm/index.html|url-status=live}}</ref> XGBoost is also available on [[OpenCL]] for [[field-programmable_gate_array|FPGAs]].<ref name="xgboost FPGA">{{Cite web|url=https://github.com/InAccel/xgboost|title=XGBoost on FPGAs|website=[[GitHub]]|access-date=2019-08-01|archive-date=2020-09-13|archive-url=https://web.archive.org/web/20200913114254/https://github.com/inaccel/xgboost|url-status=live}}</ref> An efficient, scalable implementation of XGBoost has been published by Tianqi Chen and [[Carlos Guestrin]].<ref name="paper">{{cite conference
 | last1 = Chen | first1 = Tianqi
 | last2 = Guestrin | first2 = Carlos
 | editor1-last = Krishnapuram | editor1-first = Balaji
 | editor2-last = Shah | editor2-first = Mohak
 | editor3-last = Smola | editor3-first = Alexander J.
 | editor4-last = Aggarwal | editor4-first = Charu C.
 | editor5-last = Shen | editor5-first = Dou
 | editor6-last = Rastogi | editor6-first = Rajeev
 | contribution = XGBoost: A Scalable Tree Boosting System
 |doi=10.1145/2939672.2939785
 |arxiv=1603.02754
 |isbn=9781450342322
 |s2cid=4650265
 | pages = 785–794
 | publisher = ACM
 | title = Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016
 | year = 2016}}</ref>

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:<ref>{{Cite web|url=https://medium.com/hackernoon/gradient-boosting-and-xgboost-90862daa6c77|title=Gradient Boosting and XGBoost|last=Gandhi|first=Rohith|date=2019-05-24|website=Medium|language=en|access-date=2020-01-04|archive-date=2020-03-28|archive-url=https://web.archive.org/web/20200328204417/https://medium.com/hackernoon/gradient-boosting-and-xgboost-90862daa6c77|url-status=live}}</ref><ref>{{Cite web|url=https://syncedreview.com/2017/10/22/tree-boosting-with-xgboost-why-does-xgboost-win-every-machine-learning-competition/|title=Tree Boosting With XGBoost – Why Does XGBoost Win "Every" Machine Learning Competition?|date=2017-10-22|website=Synced|language=en-US|access-date=2020-01-04|archive-date=2020-03-28|archive-url=https://web.archive.org/web/20200328204421/https://syncedreview.com/2017/10/22/tree-boosting-with-xgboost-why-does-xgboost-win-every-machine-learning-competition/|url-status=live}}</ref><ref name="paper"/>

* Clever penalization of trees
* A proportional shrinking of leaf nodes
* [[Newton's method in optimization|Newton Boosting]]
* Extra [[randomization]] parameter
* Implementation on single, [[Distributed computing|distributed]] systems and [[out-of-core]] computation
* Automatic [[Feature selection]] {{citation needed|date=May 2023}}
* 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's method in optimization|Newton–Raphson]] in function space unlike [[gradient boosting]] that works as gradient descent in function space, a second order [[Taylor series|Taylor approximation]] is used in the loss function to make the connection to Newton–Raphson method.

A generic unregularized XGBoost algorithm is:
{{framebox|blue}}
Input: training set <math>\{(x_i, y_i)\}_{i=1}^N</math>, a differentiable loss function <math>L(y, F(x))</math>, a number of weak learners <math>M</math> and a learning rate <math>\alpha</math>.

Algorithm:

* Initialize model with a constant value: <math display="block">\hat{f}_{(0)}(x) = \underset{\theta}{\arg\min} \sum_{i=1}^N L(y_i, \theta).</math>{{explain|reason=If f-hat_(0)(x) is a model, then how can it be equal to the optimal value for θ? Isn't the model and the optimal value for θ two different things?|date=September 2024}}
:: Note that this is the initialization of the model and therefore we set a constant value for all inputs. So even if in later iterations we use optimization to find new functions, in step 0 we have to find the value, equals for all inputs, that minimizes the loss functions. 

# For {{mvar|m}} = 1 to {{mvar|M}}:
## Compute the 'gradients' and 'hessians':{{clarify|reason=Is g a vector, like the gradient, and h a matrix, like the Hessian matrix? Or are both g and h vectors? Or are they both scalars? Please specify which of those cases holds.|date=September 2024}} <math display="block">\begin{align}
\hat{g}_m(x_i) &= \left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_{f(x)=\hat{f}_{(m-1)}(x)}. \\
\hat{h}_m(x_i) &= \left[\frac{\partial^2 L(y_i,f(x_i))}{\partial f(x_i)^2} \right]_{f(x)=\hat{f}_{(m-1)}(x)}.
\end{align}</math>
## Fit a base learner (or weak learner, e.g. tree) using the training set <math>\left\{x_i,\dfrac{\hat{g}_m(x_i)}{\hat{h}_m(x_i)}\right\}_{i=1}^{N}</math>{{clarify|reason=What do we mean by g-hat_m divided by h-hat_m, since h-hat_m is a matrix? Should it be interpreted as g-hat_m h-hat_m^(-1), or as h-hat_m^(-1) g-hat_m, or doesn't it matter? Or is h-hat_m a vector? What in that case does the division mean? Or is even g-hat_m and h-hat_m scalars? I'm struggling to understand what is going on here.|date=September 2024}} by solving the optimization problem below: <math display="block">\hat{\phi}_m=\underset{\phi \in \mathbf{\Phi}}{\arg\min}\sum_{i=1}^{N}\frac{1}{2}\hat{h}_m(x_i)\left[\phi(x_i) - \frac{\hat{g}_m(x_i)}{\hat{h}_m(x_i)}\right]^2.</math>{{clarify|reason=What is ϕ and Φ?|date=September 2024}} <math display="block"> \hat{f}_m(x)=\alpha \hat{\phi}_m(x).</math>
## Update the model: <math display="block">\hat{f}_{(m)}(x) = \hat{f}_{(m-1)}(x) - \hat{f}_m(x).</math>
# Output <math>\hat{f}(x)=\hat{f}_{(M)}(x)=\sum_{m=0}^{M}\hat{f}_m(x).</math>
{{frame-footer}}

==Awards==
* [[John Chambers (statistician)|John Chambers]] Award <small>(2016)</small><ref name="john-chambers">{{Cite web|url=http://stat-computing.org/awards/jmc/winners.html|title=John Chambers Award Previous Winners|access-date=2016-08-01|archive-date=2017-07-31|archive-url=https://web.archive.org/web/20170731231612/http://stat-computing.org/awards/jmc/winners.html|url-status=live}}</ref>
* High Energy Physics meets Machine Learning award (HEP meets ML) <small>(2016)</small><ref name="hep-meets-ml">{{Cite web|url=https://higgsml.lal.in2p3.fr/prizes-and-award/award/|title=HEP meets ML Award|access-date=2016-08-01|archive-date=2018-05-08|archive-url=https://web.archive.org/web/20180508185553/https://higgsml.lal.in2p3.fr/prizes-and-award/award/|url-status=live}}</ref>

==See also==
* [[LightGBM]]
* [[CatBoost]]

==References==
{{Reflist}}

[[Category:Data mining and machine learning software]]
[[Category:Free data analysis software]]
[[Category:Software using the Apache license]]
[[Category:Big data products]]
[[Category:Free software programmed in C++]]
[[Category:2014 software]]