# XGBoost

XGBoost (eXtreme Gradient Boosting) ist eine Open-Source-Softwarebibliothek, die ein Gradient-Boosting-Verfahren für die Programmiersprachen C++, Java, Python, R, Julia, Perl und Scala zur Verfügung stellt. Es funktioniert mit den Betriebssystemen Linux, Windows und macOS sowohl auf einer einzelnen Maschine als auch auf verteilten Verarbeitungsframeworks wie Apache Hadoop, Apache Spark, Apache Flink und Dask. Das Framework stellt eine „skalierbare, portierbare und verteilte Gradient Boosting (GBM, GBRT oder GBDT) Bibliothek“ bereit.
XGBoost hat im Jahr 2016 viel Popularität und Aufmerksamkeit erlangt, da es der Algorithmus der Wahl für viele Siegerteams von Wettbewerben für maschinelles Lernen ist.

## Geschichte

XGBoost wurde ursprünglich als Forschungsprojekt von Tianqi Chen im Rahmen der Distributed-(Deep) Machine-Learning-Common (DMLC)-Gruppe gestartet. Anfänglich war es eine Terminalanwendung, die mithilfe einer libsvm-Konfigurationsdatei konfiguriert werden konnte. Es wurde in den Kreisen der ML-Wettbewerbe bekannt, nachdem es in der Siegerlösung der Higgs Machine Learning Challenge verwendet worden war. Bald darauf wurden die Python- und R-Pakete erstellt, und XGBoost hat nun Paketimplementierungen für Java, Scala, Julia, Perl und andere Sprachen. Dies machte die Bibliothek für mehr Entwickler zugänglich und trug zu ihrer Popularität in der Kaggle-Gemeinschaft bei, wo sie bisher für eine große Anzahl von Wettbewerben verwendet wurde.
Es wurde bald in eine Reihe anderer Pakete integriert, um die Nutzung in den jeweiligen Communities zu erleichtern. Für Python-Nutzer wurde es nun in scikit-learn und für R-Nutzer in das caret-Paket integriert. Es kann auch in Datenfluss-Frameworks wie Apache Spark, Apache Hadoop und Apache Flink unter Verwendung der abstrahierten Rabit und XGBoost4J integriert werden. XGBoost ist auch auf OpenCL für FPGAs verfügbar. Eine effiziente, skalierbare Implementierung von XGBoost wurde von Tianqi Chen und Carlos Guestrin veröffentlicht.
Mit dem XGBoost-Modell wird zwar oft eine höhere Genauigkeit als mit einem einzelnen Entscheidungsbaum erreicht, aber die eigentliche Interpretierbarkeit von Entscheidungsbäumen geht dabei verloren. So ist es beispielsweise trivial, den Weg eines Entscheidungsbaums zu verfolgen, aber es ist viel schwieriger, die Wege von Hunderten oder Tausenden von Bäumen zu verfolgen. Um sowohl Leistung als auch Interpretierbarkeit zu erreichen, ermöglichen einige Modellkomprimierungstechniken die Umwandlung eines XGBoost in einen einzigen „wiedergeborenen“ Entscheidungsbaum, der dieselbe Entscheidungsfunktion approximiert.

## Merkmale

Zu den wichtigsten Merkmalen von XGBoost, die es von anderen Gradient-Boosting-Algorithmen unterscheiden, gehören:
* clevere „Bestrafung“ von Bäumen
* proportionale Schrumpfung der Blattknoten
* Newton-Boosting
* zusätzlicher Randomisierungsparameter
* Implementierung auf einzelnen, verteilten Systemen und Out-of-Core-Berechnungen
* automatische Auswahl von Merkmalen

## Algorithmus

XGBoost arbeitet als Newton-Raphson-Verfahren im Funktionsraum, im Gegensatz zum Gradient Boosting, das als Gradientenabstieg im Funktionsraum arbeitet. In der Verlustfunktion wird eine Taylor-Approximation zweiter Ordnung verwendet, um die Verbindung zum Newton-Raphson-Verfahren herzustellen.
Ein allgemeiner unregulierter XGBoost-Algorithmus ist:
Eingabe: Trainingsmenge $\{(x_{i},y_{i})\}_{i=1}^{N}$, eine differenzierbare Verlustfunktion $L(y,F(x))$, eine Anzahl von schwachen Lernern $M$ und eine Lernrate $\alpha$.
Algorithmus:
* Modell mit einem konstanten Wert initialisieren:
    ${\hat {f}}_{(0)}(x)={\underset {\theta }{\arg \min }}\sum _{i=1}^{N}L(y_{i},\theta ).$
* Für m = 1 zu M:
** Berechnung des Gradienten (1. Ableitung) und der Hesse-Matrix (2. Ableitung):
    ${\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)}.$
** Anpassen eines Basis-Learners (oder schwachen Lerners, z. B. Baum) unter Verwendung der Trainingsmenge $\displaystyle \left\{x_{i},-{\frac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}\right\}_{i=1}^{N}$ durch Lösen des nachstehenden Optimierungsproblems:
    ${\hat {\phi }}_{m}={\underset {\phi \in \mathbf {\Phi } }{\arg \min }}\sum _{i=1}^{N}{\frac {1}{2}}{\hat {h}}_{m}(x_{i})\left[-{\frac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}-\phi (x_{i})\right]^{2}.$
    ${\hat {f}}_{m}(x)=\alpha {\hat {\phi }}_{m}(x).$
** Modell updaten:
    ${\hat {f}}_{(m)}(x)={\hat {f}}_{(m-1)}(x)+{\hat {f}}_{m}(x).$
* Ergebnis ${\hat {f}}(x)={\hat {f}}_{(M)}(x)=\sum _{m=0}^{M}{\hat {f}}_{m}(x).$

## Auszeichnungen

* John Chambers Award (2016)
* HEP meets ML Award (2016)