XGBoost: Entscheidungsbaum vs. Lineares Modell
Einführung
Eines der Highlights der diesjährigen H2O World war ein Kaggle Grandmaster Panel. Die Teilnehmer, Gilberto Titericz (Airbnb), Mathias Müller (H2O.ai), Dmitry Larko (H2O.ai), Marios Michailidis (H2O.ai) und Mark Landry (H2O.ai), beantworteten verschiedene Fragen zu Kaggle und Data Science im Allgemeinen.
Eine der Fragen aus dem Publikum war, welche Tools und Algorithmen die Grandmasters häufig verwenden. Wie erwartet, nannte jeder einzelne von ihnen die Gradient-Boosting-Implementierung XGBoost (Chen und Guestrin 2016). Das ist nicht überraschend, da schon lange bekannt ist, dass XGBoost momentan wahrscheinlich der am häufigsten verwendete Algorithmus in der Data Science ist.
Die Popularität von XGBoost zeigt sich in zahlreichen Blogposts. Darunter Tutorials für R und Python, Hyperparameter für XGBoost und sogar die Verwendung von XGBoost mit Nvidias CUDA-GPU-Unterstützung.
Auch bei STATWORX nutzen wir die Leistungsfähigkeit von XGBoost regelmäßig für externe und interne Projekte. Eine Frage, die wir uns in letzter Zeit gestellt haben, war: Wie groß ist eigentlich der Unterschied zwischen den beiden in XGBoost angebotenen Basismodellen (auch Booster genannt)? Dieser Beitrag versucht, diese Frage systematischer zu beantworten.
Weak Learner
Gradient Boosting kann als Kombination einzelner Modelle (sogenannter Base Learner oder Weak Learner) zu einem Ensemblemodell interpretiert werden (Natekin und Knoll 2013).
Theoretisch kann jeder Base Learner im Boosting-Framework verwendet werden, wobei sich einige Base Learner als besonders nützlich erwiesen haben: Lineare und regulierte Modelle (Hastie et al. 2008), (B/P-)Splines (Huang und Yang 2004) und insbesondere Entscheidungsbäume (James et al. 2013). Zu den weniger häufig verwendeten Base Learnern gehören Random Effects (Tutz und Groll 2009), Radial Basis Functions (Gomez-Verdejo et al. 2002), Markov Random Fields (Dietterich et al. 2004) und Wavelets (Dubossarsky et al. 2016).
Chen und Guestrin (2016) beschreiben XGBoost als additive Funktion, gegeben die Daten. $D = left{ left( x_{ i }, y_{ i } right) right}$, in der folgenden Form:
$$hat{y_{ i }} = Phi(x_{ i }) = sum_{ k = 1 }^K{ f_{ k }(x_{ i }), f_{ k } } in F$$
In ihrem ursprünglichen Paper, $f_{ k }(x)forall k = 1, ... , K$ als <em>Klassifikations- oder Regressionsbaum</em> (CART) definiert. Abgesehen davon weiß der aufmerksame Leser der technischen Dokumentation, dass man die funktionale Form von $f_k(x)$ durch Verwendung des Booster-Arguments in R/Python ändern kann
# Example of XGBoost for regression in R with trees (CART)
xgboost(data = train_DMatrix,
obj = "reg:linear".
eval_metric = "rmse",
booster = "gbtree")
Man kann zwischen Entscheidungsbäumen (gbtree und dart) und linearen Modellen (gblinear) wählen. Leider gibt es nur wenig Literatur über den Vergleich verschiedener Basislerner für Boosting (siehe z.B. Joshi et al. 2002). Für den Spezialfall von XGBoost gibt es unseres Wissens nach keinen systematischen Vergleich.
Simulation und Setup
Um lineare und baumbasierte Lerner zu vergleichen, schlagen wir die folgende Monte-Carlo-Simulation vor:
Wiederhole das beschriebene Verfahren $m = 100$ mal.
Für die Simulation verwenden wir die Funktionen twoClassSim(), LPH07_1(), LPH07_2(), SLC14_1() aus dem caret-Paket. Zusätzlich zu den relevanten Merkmalen wurde eine variierende Anzahl (korrelierter) Zufallsmerkmale hinzugefügt. Beachte, dass zur Annäherung an reale Daten alle Datengenerierungsprozesse nichtlineare Komponenten beinhalten. Für weitere Details empfehlen wir einen Blick in die Dokumentation des caret-Pakets.
Für jeden Datensatz wenden wir dieselbe (zufällige) Aufteilungsstrategie an, wobei 70 % der Daten zum Training, 15 % zur Validierung und die letzten 15 % zum Testen verwendet werden. Bezüglich des Hyperparameter-Tunings verwenden wir eine Grid-Search-Strategie in Kombination mit 10-facher Kreuzvalidierung auf den Trainingsdaten. Unabhängig vom Typ des Basislerners wurden $L1$ (alpha) und $L2$ (lambda) Regularisierung unter Verwendung eines gemeinsamen Parameterraums abgestimmt.
Beim Tree Boosting wurde die Lernrate (eta) konstant auf 0{,}3 gehalten, während die optimale Baumtiefe (max_depth) abgestimmt wurde. Schließlich verwendeten wir eine feste Anzahl von 1000 Boosting-Iterationen (nrounds) in Kombination mit zehn frühen Abbruchrunden (early_stopping_rounds) auf dem Validierungs-Set. Die finale Performance wurde bewertet, indem das Modell mit den besten kreuzvalidierten Parametern auf den Testdatensatz angewendet wurde.
Ergebnisse
Abbildung 1 und Abbildung 2 zeigen die Verteilungen der Klassifikationsfehler (AUC) und Regressionsfehler (RMSE) außerhalb der Stichprobe für beide Datensätze. Die zugehörigen zusammenfassenden Statistiken sind in Tabelle 1 zu finden.
Tabelle 1: Zusammenfassung der Fehlermetriken nach Datensätzen und Basislernern
Für den ersten Datensatz sind die Modelle mit Tree-Learnern im Durchschnitt besser als die Modelle mit linearen Lernern. Allerdings weisen die Tree-Modelle eine größere Varianz auf. Beim zweiten Datensatz ist das Verhältnis umgekehrt. Im Durchschnitt sind die linearen Modelle etwas besser und die Tree-Modelle zeigen eine geringere Varianz.
Im Gegensatz zum Klassifikationsfall gibt es bei beiden Regressionsdatensätzen einen deutlichen Leistungsunterschied zugunsten der Tree-Modelle. Beim dritten Datensatz sind die Tree-Modelle im Durchschnitt besser als ihre linearen Gegenstücke. Auch die Varianz der Ergebnisse ist bei den Tree-Modellen deutlich höher. Die Ergebnisse für den vierten Datensatz sind ähnlich. Die Tree-Modelle sind erneut im Durchschnitt besser als die linearen Modelle, weisen jedoch eine höhere Streuung auf.
Zusammenfassung
Die Ergebnisse einer Monte-Carlo-Simulation mit 100 künstlich erzeugten Datensätzen deuten darauf hin, dass XGBoost mit Tree- und linearen Basislernern bei Klassifikationsproblemen vergleichbare Ergebnisse liefert, während Tree-Learner bei Regressionsproblemen überlegen sind. Basierend auf diesem Ergebnis lässt sich keine allgemeingültige Empfehlung aussprechen, welches Modell verwendet werden sollte, um den Modellbias zu minimieren. Darüber hinaus leiden baumbasierte XGBoost-Modelle im Vergleich zu ihren linearen Pendants unter einer höheren Schätzvarianz. Dieser Befund steht wahrscheinlich im Zusammenhang mit dem komplexeren Parameterraum von Tree-Modellen. Der vollständige Code ist auf GitHub zu finden.
Literatur
- Chen, Tianqi, and Carlos Guestrin. 2016. “XGBoost – A Scalable Tree Boosting System.” https://arxiv.org/pdf/1603.02754.pdf.
- Dietrich, Thomas G., Pedro Domingos, Lise Getoor, Stephen Muggleton, and Prasad Tadepalli. 2008. “Structured Machine Learning: The Next Ten Years.” http://www.doc.ic.ac.uk/~shm/Papers/strucml.pdf
- Dubossarsky, E., J.H. Friedman, J.T. Ormerod, and M.P. Wand. 2016. “Wavelet-Based Gradient Boosting.” http://www.matt-wand.utsacademics.info/publicns/Dubossarsky16.pdf
- Gómez-Verdejo, Vanessa, Jerónimo Arenas-García, Manuel Ortega-Moral and Aníbal R. Figueiras-Vidal. 2002. “Designing RBF Classifiers for Weighted Boosting.” http://www.tsc.uc3m.es/~jarenas/papers/international_conferences/2005_IJCNN_RBF_boosting.pdf
- Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. 2008. “The Elements of Statistical Learning.” Springer
- Huang, Juanhua Z., and Lijian Yang. 2004. “Identification of Nonlinear Additive Autoregressive Models.” http://lijianyang.com/mypapers/splinelag.pdf
- James, Gareth, Daniela Witten, Trevor Hastie, and Robert Tibshirani. 2013. “An Introduction to Statistical Learning.” Springer
- Natekin, Alexey, and Alois Knoll. 2013. “Gradient Boosting Machines, a Tutorial.” https://www.frontiersin.org/articles/10.3389/fnbot.2013.00021/full.
- Tut, Gerhard, and Andreas Groll. 2009. “Generalized Linear Mixed Models Based on Boosting.” http://www.fm.mathematik.uni-muenchen.de/download/publications/glmm_boost.pdf
