Boosting (engl. „Verstärken“) ist ein Ensemble-learning-Algorithmus, der mehrere aufeinander aufbauende Klassifikations- oder Regressionsmodelle zu einem einzigen Modell verschmilzt. Die Idee des Boosting wurde 1990 von Robert Schapire eingeführt. 1997 veröffentlichten Yoav Freund und Schapire den AdaBoost-Algorithmus. Der Name kommt von der Art, wie der Algorithmus mit den Fehlern der schwächeren Klassifizierer umgeht: Er passt sich diesen an (engl. „adjusts adaptively“), indem jedes nachfolgende Modell das vorhergehende Modell verbessert.
Bedeutung Bearbeiten
Die Technik liefert akzeptable Ergebnisse und lässt sich einfach in ein Computerprogramm umsetzen, das sparsam im Speicherbedarf und schnell in der Laufzeit ist.
Funktionsweise Bearbeiten
Vorgegeben ist eine Reihe von Objekten und eine Reihe schwacher Klassifikatoren. Gesucht ist ein Klassifikator, der die Objekte möglichst fehlerfrei in zwei Klassen einteilt. Boosting kombiniert die vorhandenen schwachen Klassifikatoren so, dass der entstehende neue Klassifikator möglichst wenige Fehler macht.
Schwache Klassifikatoren, auch base classifiers (engl. „Basisklassifikatoren“) oder weak learners (engl. „schwache Lerner“) genannt, sind sehr einfach aufgebaut und berücksichtigen meist nur ein einziges Merkmal der Objekte. Für sich genommen liefern sie deswegen einerseits schlechte Ergebnisse, können aber andererseits sehr schnell ausgewertet werden. Boosting führt alle schwachen Klassifikatoren so mit einer Gewichtung zusammen, dass die stärkeren unter den schwachen Klassifikatoren besonders berücksichtigt, die wirklich schwachen hingegen ignoriert werden.
Grundlagen Bearbeiten
Gegeben ist ein Merkmalsraum beliebiger Dimension und darin eine Trainingsstichprobe der Größe , also eine Menge von Mustervektoren . Von jedem dieser Mustervektoren ist bekannt, in welche Klasse er gehört, das heißt zu jedem ist ein gegeben, das angibt, in welche der beiden Klassen +1 oder −1 der Mustervektor gehört. Ferner sind primitive Klassifikatoren gegeben, die jeweils den Merkmalsraum in die beiden Klassen und aufspalten.
Gesucht sind die m Gewichtungsfaktoren des Klassifikators , der über die Vorzeichenfunktion durch
gegeben ist. Die Gewichtungsfaktoren sollen so optimiert werden, dass möglichst wenige Fehler macht.
Für die Optimierung bietet sich eine über die Exponentialfunktion definierte, sogenannte „exponentielle Verlustfunktion“ L als Optimierungskriterium an:
wird umso kleiner, je weniger Objekte falsch klassifiziert. Das Ziel ist also, die Gewichtungsfaktoren so zu wählen, dass minimal wird.
Diese Optimierung wird schrittweise über ausgeführt, das heißt zunächst wird nur optimiert, dann , dann und so weiter, bis alle Gewichtungsfaktoren optimal sind. Die Optimierung wird im nächsten Abschnitt erläutert.
Schrittweise Optimierung Bearbeiten
Die schrittweise Optimierung benötigt m Durchläufe, um alle Gewichtungsfaktoren für F zu optimieren. In jedem Durchlauf wird ein Klassifikator Fs erzeugt, indem zum bisher erzeugten Klassifikator Fs−1 ein schwacher Klassifikator hinzugenommen wird. Das bedeutet, dass der Benutzer die Berechnung nach jedem Durchlauf abbrechen kann, falls das Zwischenergebnis bereits seinen Ansprüchen genügt.
Vor jedem Durchlauf wird beurteilt, welche Mustervektoren mit dem bislang erstellten Klassifikator gut eingeordnet werden können und welche nicht. Diejenigen Mustervektoren, die noch nicht gut klassifiziert werden, werden im nächsten Durchlauf besonders stark berücksichtigt. Dazu werden in jedem Durchlauf s n Hilfsvariablen ts,1, …, ts,n benötigt. Je höher der Wert von ts,i, desto stärker geht der Mustervektor xi in den aktuellen Durchgang ein.
Die Nummer des Durchgangs ist s:
1. Gewichte aktualisieren.
2. Gewichteten Trainingsfehler bestimmen.
3. Nächsten Gewichtungsfaktor optimieren.
4. Zwischenergebnis aufstellen.
Diese Schritte werden in dieser Reihenfolge wiederholt, bis alle schwachen Klassifikatoren berücksichtigt wurden, also s = m ist, oder der Benutzer den Fortgang abbricht.
Schwache Klassifikatoren Bearbeiten
Typische schwache Klassifikatoren sind sogenannte decision stumps (engl. „Entscheidungsstümpfe“). Diese Funktionen vergleichen den Wert einer einzelnen Koordinate j mit einem Schwellwert l und begründen damit ihre Entscheidung für +1 oder −1. Ist x:= (x1, …, xd) ∈ M ein Mustervektor im d-dimensionalen Merkmalsraum M, so hat ein solcher primitiver Klassifikator f im Allgemeinen die Form:
Genauer gesagt unterteilt f den Merkmalsraum mit einer Hyperebene in zwei Klassen.
Der Name spielt auf die Analogie zu Entscheidungsbäumen an: Der erzeugte Gesamtklassifikator F kann als Entscheidungsbaum angesehen werden. Jeder schwache Klassifikator ist ein innerer Knoten dieses Baumes, an dem ein Unterbaum (vgl. engl. stump, „(Baum)Stumpf“) hängt. Die endgültige Klassifizierung in einem der Blätter des Baums wird als Folge binärer Entscheidungen (engl. decision) erreicht.
Solche decision stumps sind als Grundlage für Boosting sehr beliebt, denn sie sind einfach zu handhaben und können extrem schnell ausgewertet werden. Zudem müssen sie nicht von Anfang an vorgegeben sein, sondern können erstellt werden, während der Algorithmus läuft.
Unterarten von Boosting Bearbeiten
- AdaBoost
- AsymBoost
- BrownBoost
- DiscreteAB
- FloatBoost
- GentleAB
- GloBoost
- KLBoost
- LogitBoost
- RealAB
- WeightBoost
- GradientBoost (zum Beispiel XGBoost)
Siehe auch Bearbeiten
Einzelnachweise Bearbeiten
- Robert Schapire: The strength of weak learnability. In: Machine Learning. Band 5, Nr. 2, 1990, S. 197–227, doi:10.1007/BF00116037.
- Yoav Freund, Robert E Schapire: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. In: Journal of Computer and System Sciences. Band 55, Nr. 1, 1997, S. 119–139, doi:10.1006/jcss.1997.1504.