Boosting

trainiere mehrere schwache Klassifikatoren (einziges Kriterium: besser als Zufall) und kombiniere sie zu einem starken Klassifikator

• beliebtester Boosting-Algorithmus

• Startpunkt: begrenzte Anzahl gelabelter Daten (xi,yi), i=1,…p

  • labels: -1 oder 1

• Reihe von schwachen Klassifikatoren wird in T Runden (t=1,…,T) trainiert (einer pro Runde)

• alle Datenpunkte xi werden gewichtet (durch Gewichte Dti)

  • jedes xi wird ein Gewicht Di zugeordnet

  • Gewichte ändern sich in jeder Runde

• jedes schwache Modell lernt Entscheidungsregel ht: X->{-1,1} unter Verwendung der Gewichte Dti

• Fehler eines schwachen Klassifikators:

  • ε=P(ht(xi)≠yi) = (ΣDti für alle i mit ht(xi)≠yi)

  • Fehler ist größer, wenn Fehler für Samples mit höherem Gewicht gemacht wird

• Fehler eines “weak learners”: normalerweise durch 1/2 - γt beschrieben

  • γt sagt aus, wie viel besser als der Zufall

• obere Schranke für empirical risk (training error) des finalen (starken) Klassifikators H:

  • Ez(H) = Πt √1-4γt^2 ≤ exp(-2Σt γt^2)

• Bedeutung: wenn alle schwachen Klassifikatoren besser als der Zufall sind (γt >0), sinkt training error exponentiell

• obere Schranke für generalization error:

  • E(H) ≤ Ez(H) + O(√Th/p)

  • wird größer mit mehr Klassifikatoren (T) und höherer VC-Dimension

  • sinkt mit steigender Anzahl an Samples

• besagt eigentlich, dass große Anzahl T zu Overfitting führt (ist in praktischen Anwendungen aber kein Problem

• weitere Schranke:

  • basiert auf Margin Δ(x,y) = (yΣαtht(x)) / Σαt

  • E(H) ≤ P(Δ(x,y)≤θ) + O(√h/pθ^2) für θ>0

  • unabhängig von T

  • wächst mit großem h

  • sinkt mit größerer Sample Size und größerem Margin

• in AdaBoost: um Generalization Error zu minimieren, sollte kleinster Margin maximiert werden

  • Margin des Datenpunkts, der den kleinsten Margin liefert

• Generalisierung ist besser, wenn Margin maximiert wird

• Man kann zeigen, dass Boosting auch den Margin maximiert

  • aber mit anderen Normen als SVM

• SVM basiert auf quadratic programming, Boosting auf linear programming (wegen verschiedenen Normen)

• schwierige Beispiele werden stärker gewichtet -> boosting arbeitet v.a. mit den schwierigen Beispielen (wie SVM)

1. Initialisiere Sample Weights Dti = 1/p oder zufällig

Für t=1,…T:

1. Trainiere schwachen Classifier ht für die Gewichte Dti

2. Berechne Error ε=(ΣDti für alle i mit ht(xi)≠yi)

3. Bestimme classifier weight αt = 1/2 ln( (1-εt)/εt)

4. Aktualisiere Sample weights: Dt+1i = Dti*exp(-αtyiht(xi)) und normiere sie auf Summe 1

5. Finaler Klassifikator: H(x) = sign(Σt αt ht(x))