Eine sanfte Einführung in den Gradient-Boosting-Algorithmus für maschinelles Lernen

Last Updated on August 15, 2020

Gradient-Boosting ist eine der leistungsfähigsten Techniken zur Erstellung von Vorhersagemodellen.

In diesem Beitrag entdecken Sie den Gradient-Boosting-Algorithmus für maschinelles Lernen und erhalten eine sanfte Einführung in seine Herkunft und Funktionsweise.

Nach der Lektüre dieses Beitrags werden Sie wissen:

• Der Ursprung von Boosting aus der Lerntheorie und AdaBoost.
• Wie Gradient-Boosting funktioniert, einschließlich der Verlustfunktion, schwacher Lerner und des additiven Modells.
• Wie man mit verschiedenen Regularisierungsschemata die Leistung gegenüber dem Basisalgorithmus verbessern kann.

Starten Sie Ihr Projekt mit meinem neuen Buch XGBoost With Python, das Schritt-für-Schritt-Tutorials und die Python-Quellcode-Dateien für alle Beispiele enthält.

Lassen Sie uns loslegen.

• Brauchen Sie Hilfe bei XGBoost in Python?
• Der Ursprung des Boosting
• AdaBoost the First Boosting Algorithm
• Verallgemeinerung von AdaBoost als Gradient Boosting
• Wie Gradient Boosting funktioniert
• Verlustfunktion
• Weak Learner
• Additives Modell
• Verbesserungen des grundlegenden Gradient Boosting
• Tree Constraints
• 2. gewichtete Aktualisierungen
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Ressourcen für Gradient Boosting
• Gradient Boosting Videos
• Gradient Boosting in Lehrbüchern
• Gradient Boosting Papers
• Gradient Boosting Slides
• Gradient Boosting Webseiten
• Zusammenfassung
• Entdecken Sie den Algorithmus, der Wettbewerbe gewinnt!
• Entwickeln Sie Ihre eigenen XGBoost-Modelle in wenigen Minuten
• Bringen Sie die Leistung von XGBoost in Ihre eigenen Projekte

Brauchen Sie Hilfe bei XGBoost in Python?

Machen Sie meinen kostenlosen 7-Tage-E-Mail-Kurs und entdecken Sie xgboost (mit Beispielcode).

Klicken Sie jetzt, um sich anzumelden und auch eine kostenlose PDF-Ebook-Version des Kurses zu erhalten.

Starten Sie jetzt Ihren kostenlosen Mini-Kurs!

Der Ursprung des Boosting

Die Idee des Boosting entstand aus der Überlegung, ob ein schwacher Lerner verändert werden kann, um besser zu werden.

Michael Kearns formulierte das Ziel als „Hypothesis-Boosting-Problem“ und formulierte das Ziel vom praktischen Standpunkt aus wie folgt:

… ein effizienter Algorithmus zur Umwandlung relativ schlechter Hypothesen in sehr gute Hypothesen

– Thoughts on Hypothesis Boosting , 1988

Eine schwache Hypothese oder ein schwacher Lerner ist definiert als eine, deren Leistung zumindest geringfügig besser als der Zufall ist.

Diese Ideen bauten auf Leslie Valiants Arbeit über verteilungsfreies oder wahrscheinlich annähernd korrektes (PAC) Lernen auf, einem Rahmen für die Untersuchung der Komplexität von maschinellen Lernproblemen.

Hypothesenverstärkung war die Idee des Filterns von Beobachtungen, wobei diejenigen Beobachtungen belassen werden, mit denen der schwache Lerner umgehen kann, und man sich darauf konzentriert, neue schwache Lerner zu entwickeln, um mit den verbleibenden schwierigen Beobachtungen umzugehen.

Die Idee besteht darin, die schwache Lernmethode mehrmals zu verwenden, um eine Reihe von Hypothesen zu erhalten, die sich jeweils auf die Beispiele konzentrieren, die von den vorherigen als schwierig und falsch klassifiziert wurden. … Beachten Sie jedoch, dass es überhaupt nicht offensichtlich ist, wie dies geschehen kann

– Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World, Seite 152, 2013

AdaBoost the First Boosting Algorithm

Die erste Umsetzung des Boosting, die in der Anwendung großen Erfolg hatte, war Adaptive Boosting oder kurz AdaBoost.

Boosting bezieht sich auf das allgemeine Problem, durch Kombination von groben und mäßig ungenauen Faustregeln eine sehr genaue Vorhersageregel zu erstellen.

– Eine entscheidungstheoretische Verallgemeinerung des Online-Lernens und eine Anwendung auf Boosting , 1995

Die schwachen Lerner in AdaBoost sind Entscheidungsbäume mit einer einzigen Teilung, die wegen ihrer Kürze Entscheidungsstümpfe genannt werden.

AdaBoost funktioniert durch Gewichtung der Beobachtungen, wobei schwer zu klassifizierende Instanzen stärker gewichtet werden und solche, die bereits gut behandelt wurden, weniger. Es werden nacheinander neue schwache Lerner hinzugefügt, die sich beim Training auf die schwierigeren Muster konzentrieren.

Das bedeutet, dass schwer zu klassifizierende Muster zunehmend größere Gewichte erhalten, bis der Algorithmus ein Modell identifiziert, das diese Muster korrekt klassifiziert

– Applied Predictive Modeling, 2013

Die Vorhersagen werden durch eine Mehrheitsabstimmung der Vorhersagen der schwachen Lerner getroffen, die nach ihrer individuellen Genauigkeit gewichtet werden. Die erfolgreichste Form des AdaBoost-Algorithmus war für binäre Klassifizierungsprobleme und wurde AdaBoost.M1 genannt.

Mehr über den AdaBoost-Algorithmus erfahren Sie im Beitrag:

• Boosting und AdaBoost für maschinelles Lernen.

Verallgemeinerung von AdaBoost als Gradient Boosting

AdaBoost und verwandte Algorithmen wurden zuerst von Breiman in einen statistischen Rahmen umgewandelt und als ARCing-Algorithmen bezeichnet.

Arcing ist ein Akronym für Adaptive Reweighting and Combining. Jeder Schritt in einem Arcing-Algorithmus besteht aus einer gewichteten Minimierung, gefolgt von einer Neuberechnung von und.

– Prediction Games and Arching Algorithms , 1997

Dieser Rahmen wurde von Friedman weiter entwickelt und Gradient Boosting Machines genannt. Später wurde es einfach Gradient Boosting oder Gradient Tree Boosting genannt.

Der statistische Rahmen stellt Boosting als numerisches Optimierungsproblem dar, bei dem das Ziel darin besteht, den Verlust des Modells zu minimieren, indem schwache Lerner unter Verwendung eines gradientenabstiegsähnlichen Verfahrens hinzugefügt werden.

Diese Klasse von Algorithmen wurde als stufenweises additives Modell beschrieben. Dies liegt daran, dass jeweils ein neuer schwacher Lerner hinzugefügt wird und die vorhandenen schwachen Lerner im Modell eingefroren und unverändert gelassen werden.

Diese stufenweise Strategie unterscheidet sich von schrittweisen Ansätzen, bei denen zuvor eingegebene Terme neu angepasst werden, wenn neue hinzugefügt werden.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Die Verallgemeinerung ermöglichte die Verwendung beliebiger differenzierbarer Verlustfunktionen und erweiterte die Technik über binäre Klassifizierungsprobleme hinaus, um Regression, Mehrklassen-Klassifizierung und mehr zu unterstützen.

Wie Gradient Boosting funktioniert

Gradient Boosting umfasst drei Elemente:

1. Eine zu optimierende Verlustfunktion.
2. Ein schwacher Lerner, der Vorhersagen macht.
3. Ein additives Modell zum Hinzufügen schwacher Lerner, um die Verlustfunktion zu minimieren.

Verlustfunktion

Die verwendete Verlustfunktion hängt von der Art des zu lösenden Problems ab.

Sie muss differenzierbar sein, aber viele Standardverlustfunktionen werden unterstützt, und Sie können Ihre eigenen definieren.

Zum Beispiel kann bei der Regression ein quadratischer Fehler und bei der Klassifikation ein logarithmischer Verlust verwendet werden.

Ein Vorteil des Gradient-Boosting-Rahmens ist, dass nicht für jede Verlustfunktion, die verwendet werden soll, ein neuer Boosting-Algorithmus abgeleitet werden muss, sondern dass der Rahmen so allgemein ist, dass jede differenzierbare Verlustfunktion verwendet werden kann.

Weak Learner

Entscheidungsbäume werden beim Gradient-Boosting als Weak Learner verwendet.

Speziell werden Regressionsbäume verwendet, die reale Werte für Splits ausgeben und deren Ausgaben addiert werden können, so dass die Ausgaben nachfolgender Modelle hinzugefügt werden können und die Residuen in den Vorhersagen „korrigieren“.

Die Bäume werden auf gierige Weise konstruiert, wobei die besten Splitpunkte auf der Grundlage von Reinheitswerten wie Gini oder zur Minimierung des Verlusts ausgewählt werden.

Anfänglich wurden, wie im Fall von AdaBoost, sehr kurze Entscheidungsbäume verwendet, die nur einen einzigen Split, einen so genannten Entscheidungsstumpf, aufweisen. Größere Bäume können im Allgemeinen mit 4 bis 8 Ebenen verwendet werden.

Es ist üblich, die schwachen Lerner auf bestimmte Weise einzuschränken, z. B. durch eine maximale Anzahl von Schichten, Knoten, Splits oder Blattknoten.

Damit soll sichergestellt werden, dass die Lerner schwach bleiben, aber dennoch auf gierige Weise konstruiert werden können.

Additives Modell

Bäume werden einzeln hinzugefügt, und bestehende Bäume im Modell werden nicht verändert.

Ein Gradientenabstiegsverfahren wird verwendet, um den Verlust beim Hinzufügen von Bäumen zu minimieren.

Traditionell wird der Gradientenabstieg verwendet, um eine Reihe von Parametern zu minimieren, z. B. die Koeffizienten in einer Regressionsgleichung oder die Gewichte in einem neuronalen Netz. Nach der Berechnung des Fehlers oder Verlustes werden die Gewichte aktualisiert, um diesen Fehler zu minimieren.

Anstelle von Parametern haben wir schwache Lernsubmodelle oder genauer gesagt Entscheidungsbäume. Nach der Berechnung des Verlustes müssen wir, um das Gradientenabstiegsverfahren durchzuführen, dem Modell einen Baum hinzufügen, der den Verlust reduziert (d. h. dem Gradienten folgt). Dazu parametrisieren wir den Baum, ändern dann die Parameter des Baums und bewegen uns in die richtige Richtung, indem wir den Restverlust reduzieren.

Gemeinsam wird dieser Ansatz funktionaler Gradientenabstieg oder Gradientenabstieg mit Funktionen genannt.

Eine Möglichkeit, eine gewichtete Kombination von Klassifikatoren zu erzeugen, die sich optimiert, ist der Gradientenabstieg im Funktionsraum

– Boosting Algorithms as Gradient Descent in Function Space , 1999

Die Ausgabe für den neuen Baum wird dann zur Ausgabe der bestehenden Baumfolge hinzugefügt, um die endgültige Ausgabe des Modells zu korrigieren oder zu verbessern.

Eine feste Anzahl von Bäumen wird hinzugefügt oder das Training wird beendet, sobald der Verlust ein akzeptables Niveau erreicht oder sich nicht mehr auf einem externen Validierungsdatensatz verbessert.

Verbesserungen des grundlegenden Gradient Boosting

Gradient Boosting ist ein gieriger Algorithmus und kann einen Trainingsdatensatz schnell überfordern.

Es kann von Regularisierungsmethoden profitieren, die verschiedene Teile des Algorithmus bestrafen und allgemein die Leistung des Algorithmus verbessern, indem sie die Überanpassung reduzieren.

In diesem Abschnitt betrachten wir 4 Erweiterungen des grundlegenden Gradient Boosting:

1. Tree Constraints
2. Shrinkage
3. Random Sampling
4. Penalized Learning

Tree Constraints

Es ist wichtig, dass die schwachen Lerner Fähigkeiten haben, aber schwach bleiben.

Es gibt eine Reihe von Möglichkeiten, die Bäume einzuschränken.

Eine gute allgemeine Heuristik ist, dass man umso mehr Bäume im Modell braucht, je stärker man die Baumbildung einschränkt, und umgekehrt, je weniger man die einzelnen Bäume einschränkt, desto weniger Bäume werden benötigt.

Nachfolgend sind einige Einschränkungen aufgeführt, die bei der Erstellung von Entscheidungsbäumen gemacht werden können:

• Anzahl der Bäume, im Allgemeinen kann das Hinzufügen von mehr Bäumen zum Modell sehr langsam zu einem Overfit führen. Es wird empfohlen, so lange Bäume hinzuzufügen, bis keine weitere Verbesserung mehr zu beobachten ist.
• Baumtiefe, tiefere Bäume sind komplexere Bäume und kürzere Bäume werden bevorzugt. Im Allgemeinen werden bessere Ergebnisse mit 4-8 Ebenen erzielt.
• Anzahl der Knoten oder Anzahl der Blätter, wie die Tiefe, kann dies die Größe des Baums einschränken, ist aber nicht auf eine symmetrische Struktur beschränkt, wenn andere Einschränkungen verwendet werden.
• Die Anzahl der Beobachtungen pro Teilung stellt eine Mindestbeschränkung für die Menge der Trainingsdaten an einem Trainingsknoten dar, bevor eine Teilung in Betracht gezogen werden kann
• Die minimale Verbesserung des Verlustes ist eine Beschränkung für die Verbesserung jeder einem Baum hinzugefügten Teilung.

2. gewichtete Aktualisierungen

Die Vorhersagen jedes Baums werden nacheinander addiert.

Der Beitrag jedes Baums zu dieser Summe kann gewichtet werden, um das Lernen durch den Algorithmus zu verlangsamen. Diese Gewichtung wird als Schrumpfung oder Lernrate bezeichnet.

Jede Aktualisierung wird einfach durch den Wert des „Lernratenparameters v“

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Der Effekt ist, dass das Lernen verlangsamt wird, was wiederum erfordert, dass dem Modell mehr Bäume hinzugefügt werden, was wiederum länger dauert, um zu trainieren, was einen Konfigurationskompromiss zwischen der Anzahl der Bäume und der Lernrate darstellt.

Eine Verringerung des Wertes von v erhöht den besten Wert für M.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Gängig sind kleine Werte im Bereich von 0,1 bis 0,3 sowie Werte unter 0,1.

Ähnlich wie bei einer Lernrate in der stochastischen Optimierung verringert die Schrumpfung den Einfluss jedes einzelnen Baums und lässt Raum für künftige Bäume zur Verbesserung des Modells.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

Eine wichtige Erkenntnis bei Bagging-Ensembles und Random Forest war die Möglichkeit, Bäume aus Teilproben des Trainingsdatensatzes gierig zu erstellen.

Dieser Vorteil kann genutzt werden, um die Korrelation zwischen den Bäumen in der Sequenz in Gradient-Boosting-Modellen zu reduzieren.

Diese Variante des Boosting wird stochastisches Gradient-Boosting genannt.

Bei jeder Iteration wird eine Teilstichprobe der Trainingsdaten nach dem Zufallsprinzip (ohne Ersatz) aus dem vollständigen Trainingsdatensatz gezogen. Die zufällig ausgewählte Teilstichprobe wird dann anstelle der vollständigen Stichprobe verwendet, um den Basis-Learner anzupassen.

– Stochastic Gradient Boosting , 1999

Einige Varianten des stochastischen Boosting, die verwendet werden können:

• Teilstichprobenzeilen vor der Erstellung jedes Baums.
• Teilstichprobenspalten vor der Erstellung jedes Baums
• Teilstichprobenspalten vor der Berücksichtigung jedes Splits.

Im Allgemeinen hat sich ein aggressives Sub-Sampling, bei dem nur 50 % der Daten ausgewählt werden, als vorteilhaft erwiesen.

Nach den Rückmeldungen der Benutzer verhindert die Verwendung von Spalten-Subsampling eine Überanpassung noch mehr als das traditionelle Zeilen-Subsampling

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Zusätzlich zu ihrer Struktur können den parametrisierten Bäumen weitere Beschränkungen auferlegt werden.

Klassische Entscheidungsbäume wie CART werden nicht als schwache Lerner verwendet, stattdessen wird eine modifizierte Form, ein sogenannter Regressionsbaum, verwendet, der numerische Werte in den Blattknoten (auch Endknoten genannt) hat. Die Werte in den Blättern der Bäume werden in der Literatur als Gewichte bezeichnet.

Die Blattgewichtswerte der Bäume können daher mit Hilfe gängiger Regularisierungsfunktionen reguliert werden, z. B.:

• L1-Regularisierung von Gewichten.
• L2-Regularisierung von Gewichten.

Der zusätzliche Regularisierungsterm hilft, die endgültigen gelernten Gewichte zu glätten, um eine Überanpassung zu vermeiden. Intuitiv wird das regulierte Ziel dazu neigen, ein Modell auszuwählen, das einfache und vorhersagende Funktionen verwendet.

– XGBoost: A Scalable Tree Boosting System, 2016

Ressourcen für Gradient Boosting

Gradient Boosting ist ein faszinierender Algorithmus, und ich bin mir sicher, dass Sie ihn vertiefen möchten.

In diesem Abschnitt werden verschiedene Ressourcen aufgelistet, die Sie nutzen können, um mehr über den Gradient-Boosting-Algorithmus zu erfahren.

Gradient Boosting Videos

• Gradient Boosting Machine Learning, Trevor Hastie, 2014
• Gradient Boosting, Alexander Ihler, 2012
• GBM, John Mount, 2015
• Learning: Boosting, MIT 6.034 Artificial Intelligence, 2010
• xgboost: An R package for Fast and Accurate Gradient Boosting, 2016
• XGBoost: A Scalable Tree Boosting System, Tianqi Chen, 2016

Gradient Boosting in Lehrbüchern

• Abschnitt 8.2.3 Boosting, Seite 321, An Introduction to Statistical Learning: with Applications in R.
• Abschnitt 8.6 Boosting, Seite 203, Applied Predictive Modeling.
• Abschnitt 14.5 Stochastic Gradient Boosting, Seite 390, Applied Predictive Modeling.
• Abschnitt 16.4 Boosting, Seite 556, Machine Learning: A Probabilistic Perspective
• Kapitel 10 Boosting and Additive Trees, Seite 337, The Elements of Statistical Learning: Data Mining, Inference, and Prediction

Gradient Boosting Papers

• Thoughts on Hypothesis Boosting , Michael Kearns, 1988
• Eine entscheidungstheoretische Verallgemeinerung des Online-Lernens und eine Anwendung auf Boosting , 1995
• Arcing the edge , 1998
• Stochastic Gradient Boosting , 1999
• Boosting-Algorithmen als Gradientenabstieg im Funktionsraum , 1999

Gradient Boosting Slides

• Introduction to Boosted Trees, 2014
• A Gentle Introduction to Gradient Boosting, Cheng Li

Gradient Boosting Webseiten

• Boosting (maschinelles Lernen)
• Gradient Boosting
• Gradient Tree Boosting in scikit-learn

Zusammenfassung

In diesem Beitrag wurde der Gradient Boosting Algorithmus für prädiktive Modellierung im maschinellen Lernen vorgestellt.

Im Einzelnen haben Sie gelernt:

• Die Geschichte des Boosting in der Lerntheorie und AdaBoost.
• Wie der Gradient-Boosting-Algorithmus mit einer Verlustfunktion, schwachen Lernern und einem additiven Modell funktioniert.
• Wie man die Leistung von Gradient Boosting mit Regularisierung verbessern kann.

Haben Sie Fragen zum Gradient Boosting Algorithmus oder zu diesem Beitrag? Stellen Sie Ihre Fragen in den Kommentaren und ich werde mein Bestes tun, um sie zu beantworten.