AdaBoost

Nachdem bisher nur generelle Funktionsweise des Boosting’s erklärt wurde soll sich im Folgenden eine formale Beschreibung anschließen. Der hier beschriebene Algorithmus ist der bereits erwähnte AdaBoost Algorithmus von Schapire und Freund. Die Betrachtung erfolgt dabei lediglich für eine Klassifizierung in zwei unterschiedliche Klassen.

 

Abbildung 5: Pseudocode des Adaboost-Algorithmus

 

 

Als Ausgangsbasis für den Algorithmus liegen Trainingsdaten vor, die durch eine Anzahl von m Wertepaaren x,y definiert sind. Hierbei stellt xi den Wert des Merkmals dar anhand dessen klassifiziert werden soll. yi hingegen ist die bereits vorhandene korrekte Klasse die vom Algorithmus später vorausgesagt werden soll. Um die späteren mathematischen Berechnungen einfacher zu gestalten sind die beiden unterschiedlichen Klassen als -1 und 1 definiert. Bevor der eigentliche Algorithmus anfängt, wird zuvor noch die Verteilung D initialisiert. D ist eine Funktion welche die Gewichtung der einzelnen Werte (xi) beschreibt. Zu Beginn erhalten alle Werte die gleiche Gewichtung weshalb die Funktion mit 1/m initialisiert wird. Der nächste Schritt des Algorithmus läuft mehrmalig hintereinander ab. Die Anzahl der Durchläufe wird dabei durch den Parameter T bestimmt, der beliebig gewählt werden kann. Als erster Teilschritt eines solchen Durchlaufs wird die Verteilung D inklusive der Werte dem Algorithmus des schwachen Lerners übergeben um einen Basisklassifikator zu erzeugen. Dieser Basisklassifikator ist eine Voraussage die allen Elementen der Wertemenge X eine der beiden Klassen (-1 oder 1) zuweist. Der Fehler der Voraussage wird als εt bezeichnet und wird, wie in der oberen Abbildung dargestellt, mittels der Wahrscheinlichkeit für die Misklassifizierung eines Wertes der Funktion Dt (PrDT[ht(xi)]<>yi) berechnet. Oder anders ausgedrückt als die Summe der Gewichte der falsch klassifizierten Werte. Der Fehler gibt dabei gleichzeitig die Güte des Klassifikators an und soll deshalb möglichst minimal sein.

 

Danach wird der Faktor αt bestimmt (s. Abbildung 5), welcher zur Berechnung der neuen Gewichtsverteilung benutzt wird. Diese wird wie folgt berechnet:

Ein Wert der neuen Verteilung berechnet sich also aus dem alten Wert multipliziert mit einem exponentiellen Wert. Da αt ein positiver Wert ist wird das Gewicht bei Übereinstimmung der Voraussage mit der korrekten Klasse verringert, da ein negativer Exponent eine Zahl kleiner 1 generiert. Andernfalls wird das Gewicht vergrößert. Zum Schluss wird das ganze durch einen Konstante Zt geteilt um die erhaltenen Werte zu normalisieren. Da die Klassen als -1 und 1 definiert sind kann die ganze Rechnung folgendermaßen vereinfacht werden:

 

Das Produkt der Voraussage und korrekten Klasse multipliziert mit dem negativen αt bildet bei Nichtübereinstimmung einen positiver, bei Übereinstimmung einen negativer Exponenten.

 

Nachdem die Schleife T-mal durchlaufen wurde wird der starke Klassifikator durch die Kombination der vorher erzeugten Basisklassifikatoren erstellt. Die Kombination kann als gewichtete Mehrheitsentscheidung angesehen werden. Die Klassifizierung eines neuen Beispiels x kann wie folgt berechnet werden:

Das neue Beispiel wird dabei jedem Basisklassifikator übergeben der eine Voraussage für -1 oder 1 zurückliefert. Diese wird dann mit dem entsprechenden αt gewichtet. Die erzeugten Werte werden anschließend aufsummiert. Entsteht dabei ein negativer Wert wird durch die Signum-Funktion eine -1 zurückgeliefert, entsteht ein positiver Wert wird eine 1 zurückgeliefert. Dieses Ergebnis entspricht dann der finalen Klasseneinteilung.