Boosting

[[Hilfe:Cache|Fehler beim Thumbnail-Erstellen]]:

Klassifizierung in fünf Klassen. Der durch Boosting erzeugte Klassifikator klassifiziert nur in zwei Klassen.

Boosting (engl. „Verstärken“) ist ein Algorithmus der automatischen Klassifizierung, der mehrere schwache Klassifikatoren zu einem einzigen guten Klassifikator verschmilzt.

Die zum Verständnis benötigten Grundbegriffe werden im Artikel Klassifizierung erläutert.

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").

Anwendungsgebiete

Boosting kann überall dort verwendet werden, wo eine automatische Klassifikation in zwei Klassen benötigt wird, beispielsweise um Bilder von Gesichtern in „bekannt“ und „unbekannt“ oder Produkte auf einem Fließband als „in Ordnung“ oder „fehlerhaft“ einzustufen. Die Anwendungsgebiete sind damit nahezu ebenso vielfältig wie die der automatischen Klassifizierung an sich.

Bedeutung

Obwohl es weitaus raffiniertere Methoden gibt, Klassifikatoren zu entwerfen, bildet Boosting in vielen Fällen eine annehmbare Alternative: 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

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

Gegeben ist ein Merkmalsraum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} beliebiger Dimension und darin eine Trainingsstichprobe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} der Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} , also eine Menge von Mustervektoren $x_{1},\dots ,x_{n}$. Von jedem dieser Mustervektoren ist bekannt, in welche Klasse er gehört, das heißt zu jedem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} ist ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_i \in {+1, -1}} gegeben, das angibt, in welche der beiden Klassen +1 oder −1 der Mustervektor gehört. Ferner sind m primitive Klassifikatoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_1, f_2, \dots, f_m: M \rightarrow {+1, -1}} gegeben, die jeweils den Merkmalsraum in die beiden Klassen +1 und −1 aufspalten.

Gesucht sind die m Gewichtungsfaktoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_1, \dots, w_m} des Klassifikators Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F: M \rightarrow {+1, -1}} , der über die Vorzeichenfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sgn} durch

$F(x):=\operatorname {sgn} \left(\sum _{i=1}^{m}w_{i}f_{i}(x)\right)$

gegeben ist. Die Gewichtungsfaktoren sollen so optimiert werden, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F} möglichst wenige Fehler macht.

Für die Optimierung bietet sich eine über die Exponentialfunktion e definierte, sogenannte „exponentielle Verlustfunktion“ L als Optimierungskriterium an:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L := \frac{1}{n} \sum_{i=1}^n \mathrm{e}^{-y_i F(x_i)} \rightarrow \text{min}}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} wird umso kleiner, je weniger Objekte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F} falsch klassifiziert. Das Ziel ist also, die Gewichtungsfaktoren so zu wählen, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} minimal wird.

Diese Optimierung wird schrittweise über m ausgeführt, das heißt zunächst wird nur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_1} optimiert, dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_2} , dann $w_{3}$ und so weiter, bis alle Gewichtungsfaktoren optimal sind. Die Optimierung wird im nächsten Abschnitt erläutert.

Schrittweise Optimierung

Die schrittweise Optimierung benötigt m Durchläufe, um alle Gewichtungsfaktoren für F zu optimieren. In jedem Durchlauf wird ein Klassifikator F_s erzeugt, indem zum bisher erzeugten Klassifikator F_s−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 t_s,1, …, t_s,n benötigt. Je höher der Wert von t_s,i, desto stärker geht der Mustervektor x_i in den aktuellen Durchgang ein.

Die Nummer des Durchgangs ist s:

1. Gewichte aktualisieren.

Im ersten Durchlauf (s = 1) werden alle Hilfsvariablen auf den Wert 1/n gesetzt: t_1,1, …, t_1,n:= 1/n; somit werden im ersten Durchgang alle Mustervektoren gleich stark berücksichtigt. In allen folgenden Durchläufen (s > 1) werden die Hilfsvariablen wie folgt gesetzt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_{s,i} := t_{s-1,i} \mathrm{e}^{-y_i w_{s-1} f_{s-1}(x_i) }}

Damit werden alle Mustervektoren, die vom eben betrachteten schwachen Klassifikator f_s−1 falsch klassifiziert wurden, in diesem Durchlauf mit einem besonders hohen Hilfsgewicht versehen, alle anderen mit einem besonders geringen.

2. Gewichteten Trainingsfehler bestimmen.

In diesem Durchgang wird der schwache Klassifikator f_s hinzugenommen. Der „gewichtete Trainingsfehler“ ist ein Maß dafür, wie schlecht dieser primitive Klassifikator für sich genommen abschneidet. Für jeden von f_s falsch klassierten Mustervektor x_i summiert er die zugehörige Hilfsvariable t_s,i auf:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle err_{s}:=\sum _{i:f_{s}(x_{i})\neq y_{i}}t_{s,i}}

Ist der gewichtete Trainingsfehler 0, so klassifiziert f_s alle Mustervektoren richtig, ist er 1, so klassifiziert f_s alles falsch. Ist err_s = 1/2, so klassifiziert f_s genauso gut, als würde er bei jedem Mustervektor bloß raten oder eine Münze werfen.

3. Nächsten Gewichtungsfaktor optimieren.

Der Gewichtungsfaktor w_s des in diesem Durchgang hinzugenommenen primitiven Klassifikators f_s wird aus der folgenden Formel bestimmt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w_s = \frac{1}{2} \log \left( \frac{1-err_s}{err_s} \right)}

Nach der Formel wird f_s genau dann mit positivem Gewicht zum Endergebnis hinzugenommen, wenn err_s < ½ gilt, das heißt der schwache Klassifikator besser ist als bloßes Raten. Gilt exakt err_s = ½, so folgt w_s = 0, das heißt f_s wird ignoriert. Gilt hingegen err_s > ½, so ist der schwache Klassifikator durchaus brauchbar, er ist nur „falsch gepolt“, das heißt, er klassifiziert genau falsch herum; indem er mit einem negativen Gewicht hinzugenommen wird, kann dieser Formfehler ausgeglichen werden und der umgedrehte Klassifikator mit verstärkendem Effekt hinzugenommen werden.

4. Zwischenergebnis aufstellen.

Das Zwischenergebnis F_s ergibt sich aus der Formel:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F_s(x) := \sum_{i=1}^s w_i f_i(x)}

Es wird also genauso berechnet wie das eigentliche Ziel F, nur dass statt aller m schwachen Klassifikatoren nur die ersten s bereits optimierten berücksichtigt werden.

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

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:= (x₁, …, x_d) ∈ M ein Mustervektor im d-dimensionalen Merkmalsraum M, so hat ein solcher primitiver Klassifikator f im Allgemeinen die Form:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x) = f((x_1, x_2, \dots, x_d)) := \begin{cases} +1 & \text{falls } x_j \geqslant l \\ -1 & \text{falls } x_j < l \end{cases}}

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

• AdaBoost
• AsymBoost
• BrownBoost
• DiscreteAB
• FloatBoost
• GentleAB
• GloBoost
• KLBoost
• LogitBoost
• RealAB
• WeightBoost
• GradientBoost

Siehe auch

• Bagging