Boosting ist eine Ensemble-Lernmethode im maschinellen Lernen, die eine Reihe von weniger genauen Modellen, sogenannten schwachen Lernern, kombiniert, um ein einziges hochgenaues Modell zu erstellen, das als starker Lerner bekannt ist. Im Gegensatz zu parallelen Ensemble-Methoden wie Bagging bauen Boosting-Algorithmen Modelle sequenziell auf. Jedes neue Modell in der Sequenz wird trainiert, um die Fehler seiner Vorgänger zu korrigieren. Dieser iterative Prozess verbessert die Gesamtgenauigkeit, insbesondere durch die Reduzierung von Bias. Boosting ist eine beliebte und effektive Technik, die im überwachten Lernen sowohl für Klassifikations- als auch für Regressionsaufgaben verwendet wird.
Die theoretische Grundlage für Boosting stammt aus einer Frage, die Kearns und Valiant 1988 und 1989 stellten: ob eine Reihe von schwachen Lernern einen einzigen starken Lerner erzeugen kann. Ein schwacher Lerner wird als ein Klassifikator definiert, der nur geringfügig besser als zufälliges Raten abschneidet, während ein starker Lerner stark mit der wahren Klassifikation korreliert. Robert Schapires bejahende Antwort in einem Papier von 1990 führte zur Entwicklung praktischer Boosting-Algorithmen. Der erste derartige Algorithmus wurde von Schapire entwickelt, wobei Freund und Schapire später AdaBoost entwickelten, das bis heute ein grundlegendes Beispiel für Boosting bleibt.
Kernmechanismus
Obwohl Boosting algorithmisch nicht eingeschränkt ist, bestehen die meisten Boosting-Algorithmen darin, iterativ schwache Klassifikatoren in Bezug auf eine Verteilung zu lernen und sie zu einem endgültigen starken Klassifikator hinzuzufügen. Beim Hinzufügen werden sie auf eine Weise gewichtet, die mit der Genauigkeit der schwachen Lerner zusammenhängt. Nachdem ein schwacher Lerner hinzugefügt wurde, werden die Daten Gewichte neu angepasst, ein Prozess, der als Neugewichtung bezeichnet wird. Falsch klassifizierte Eingabedaten erhalten ein höheres Gewicht, während Beispiele, die korrekt klassifiziert wurden, an Gewicht verlieren. Somit konzentrieren sich zukünftige schwache Lerner mehr auf die Beispiele, die frühere schwache Lerner falsch klassifiziert haben.
Dieser sequenzielle Fokus auf schwierige Beispiele unterscheidet Boosting von anderen Ensemble-Methoden. Der Neugewichtungsmechanismus stellt sicher, dass jedes nachfolgende Modell in der Sequenz die Restfehler des kombinierten Ensembles adressiert. Über viele Runden hinweg reduziert das Ensemble fortschreitend seinen Trainings-Bias und erreicht oft hohe Genauigkeit, selbst wenn einzelne schwache Lerner nur geringfügig besser als zufälliges Raten sind.
Historische Entwicklung
Es gibt viele Boosting-Algorithmen. Die ursprünglichen, vorgeschlagen von Robert Schapire (eine rekursive Mehrheits-Gate-Formulierung) und Yoav Freund (Boost by Majority), waren nicht adaptiv und konnten die schwachen Lerner nicht voll ausnutzen. Schapire und Freund entwickelten dann AdaBoost, einen adaptiven Boosting-Algorithmus, der den prestigeträchtigen Gödel-Preis gewann. AdaBoost war der erste Algorithmus, der sich an die schwachen Lerner anpassen konnte, was ihn historisch bedeutsam macht und oft die Grundlage für die einführende Behandlung von Boosting in universitären Maschinenlernkursen bildet.
Nur Algorithmen, die beweisbare Boosting-Algorithmen im wahrscheinlich ungefähr korrekten Lernformalismus sind, können genau als Boosting-Algorithmen bezeichnet werden. Andere Algorithmen, die im Geiste ähnlich sind, werden manchmal als Leveraging-Algorithmen bezeichnet, obwohl sie auch fälschlicherweise manchmal als Boosting-Algorithmen bezeichnet werden. Die Hauptvariation zwischen vielen Boosting-Algorithmen liegt in ihrer Methode zur Gewichtung von Trainingsdatenpunkten und Hypothesen.
Hauptalgorithmen
AdaBoost bleibt historisch am bedeutendsten, aber viele neuere Algorithmen wurden entwickelt. Dazu gehören LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost und CatBoost, unter anderem. Viele Boosting-Algorithmen passen in das AnyBoost-Framework, das zeigt, dass Boosting einen Gradientenabstieg in einem Funktionsraum unter Verwendung einer konvexen Kostenfunktion durchführt.
Moderne Implementierungen wie xgboost und CatBoost sind in der Industrie und im wettbewerbsorientierten maschinellen Lernen aufgrund ihrer Skalierbarkeit und Leistung weit verbreitet. Diese Algorithmen integrieren Regularisierung, effiziente baumbasierte schwache Lerner und Optimierungen für sparse Daten und kategoriale Merkmale. Sie werden häufig in Bereichen von Finanzen bis Gesundheitswesen angewendet und übertreffen oft andere Methoden bei tabellarischen Daten.
Objektkategorisierung in der Computer Vision
Angesichts von Bildern, die verschiedene bekannte Objekte in der Welt enthalten, kann ein Klassifikator aus ihnen gelernt werden, um die Objekte in zukünftigen Bildern automatisch zu klassifizieren. Einfache Klassifikatoren, die auf einem Bildmerkmal des Objekts basieren, neigen dazu, in der Kategorisierungsleistung schwach zu sein. Die Verwendung von Boosting-Methoden für die Objektkategorisierung ist eine Möglichkeit, die schwachen Klassifikatoren auf besondere Weise zu vereinen, um die Gesamtfähigkeit der Kategorisierung zu verbessern.
Problem der Objektkategorisierung
Objektkategorisierung ist eine typische Aufgabe der künstlichen Intelligenz und der Computer Vision, die darin besteht, zu bestimmen, ob ein Bild eine bestimmte Kategorie von Objekten enthält. Die Idee ist eng mit Erkennung, Identifikation und Detektion verwandt. Erscheinungsbasierte Objektkategorisierung umfasst typischerweise Merkmalsextraktion, das Lernen eines Klassifikators und die Anwendung des Klassifikators auf neue Beispiele. Es gibt viele Möglichkeiten, eine Kategorie von Objekten darzustellen, von Formanalyse, Bag-of-Words-Modellen oder lokalen Deskriptoren wie SIFT. Beispiele für überwachte Klassifikatoren sind Naive-Bayes-Klassifikatoren, Support Vector Machines, Gaußsche Mischungen und neuronale Netze. Die Forschung hat jedoch gezeigt, dass Objektkategorien und ihre Positionen in Bildern auch unüberwacht entdeckt werden können.
Status quo für Objektkategorisierung
Die Erkennung von Objektkategorien in Bildern ist ein herausforderndes Problem in der Computer Vision, insbesondere wenn die Anzahl der Kategorien groß ist. Dies ist auf hohe Intra-Klassen-Variabilität und die Notwendigkeit der Generalisierung über Variationen von Objekten innerhalb derselben Kategorie zurückzuführen. Objekte innerhalb einer Kategorie können sehr unterschiedlich aussehen. Selbst dasselbe Objekt kann unter verschiedenen Blickwinkeln, Maßstäben und Beleuchtungen unähnlich erscheinen. Hintergrundrauschen und partielle Okklusion erschweren die Erkennung ebenfalls. Menschen sind in der Lage, Tausende von Objekttypen zu erkennen, während die meisten bestehenden Objekterkennungssysteme nur wenige erkennen, wie menschliche Gesichter, Autos oder einfache Objekte. Die Forschung ist sehr aktiv im Umgang mit mehr Kategorien und ermöglicht inkrementelle Ergänzungen neuer Kategorien. Obwohl das allgemeine Problem ungelöst bleibt, wurden mehrere Multi-Kategorien-Objektdetektoren (für bis zu Hunderten oder Tausenden von Kategorien) entwickelt, teilweise durch Merkmalsfreigabe und Boosting.
Boosting für binäre Kategorisierung
AdaBoost kann für die Gesichtserkennung als Beispiel für binäre Kategorisierung verwendet werden. Die beiden Kategorien sind Gesichter versus Hintergrund. Der allgemeine Algorithmus ist wie folgt: Bilde eine große Menge einfacher Merkmale; initialisiere Gewichte für Trainingsbilder; für T Runden normalisiere die Gewichte, trainiere einen Klassifikator mit einem einzelnen Merkmal aus der verfügbaren Menge, bewerte den Trainingsfehler, wähle den Klassifikator mit dem niedrigsten Fehler und aktualisiere die Gewichte der Trainingsbilder (erhöhe, wenn falsch klassifiziert, verringere, wenn korrekt); bilde schließlich den starken Klassifikator als lineare Kombination der T Klassifikatoren, mit größeren Koeffizienten für Klassifikatoren mit kleinerem Trainingsfehler. Nach dem Boosting konnte ein aus 200 Merkmalen konstruierter Klassifikator eine Erkennungsrate von 95 Prozent bei einer Falsch-Positiv-Rate von 10 hoch minus 5 erzielen.
Eine weitere Anwendung von Boosting für binäre Kategorisierung ist ein System, das Fußgänger mithilfe von Bewegungs- und Erscheinungsmustern erkennt. Diese Arbeit war die erste, die sowohl Bewegungsinformationen als auch Erscheinungsinformationen als Merkmale kombinierte, um eine gehende Person zu erkennen. Sie verfolgt einen ähnlichen Ansatz wie das Viola-Jones-Objekterkennungsframework.
Boosting für Multi-Klassen-Kategorisierung
Im Vergleich zur binären Kategorisierung beinhaltet die Multi-Klassen-Kategorisierung die Zuordnung eines Bildes zu einer von mehreren möglichen Objektkategorien. Boosting-Methoden für Multi-Klassen-Probleme erweitern typischerweise binäre Ansätze durch Strategien wie One-versus-All- oder One-versus-One-Dekomposition oder durch direkte Modifikation des Boosting-Algorithmus, um mehrere Klassen zu behandeln. Diese Methoden haben es Objekterkennungssystemen ermöglicht, Hunderte oder Tausende von Kategorien zu erkennen, wenn auch mit erhöhten Rechenkosten und Komplexität.
Anwendungen und Auswirkungen
Boosting wurde in vielen Bereichen über die Computer Vision hinaus angewendet. In Deep-Learning-Kontexten haben Boosting-Ideen Ensemble-Techniken und gradientenbasierte Optimierung beeinflusst. In der Verarbeitung natürlicher Sprache wird Boosting für Textklassifikation und Sentimentanalyse verwendet. Im Finanzwesen wird es für Kredit-Scoring und Betrugserkennung eingesetzt. In der Bioinformatik hilft Boosting bei der Genexpressionsklassifikation und der Vorhersage von Proteinfunktionen. Die Fähigkeit der Methode, einfache Modelle zu hochgenauen Prädiktoren zu kombinieren, hat sie zu einem festen Bestandteil sowohl der akademischen Forschung als auch der industriellen Praxis gemacht.
Theoretische Bedeutung
Die theoretische Bedeutung von Boosting liegt in seiner Demonstration, dass schwache Lernbarkeit starke Lernbarkeit impliziert. Dieses Ergebnis, von Schapire 1990 bewiesen, beantwortete die von Kearns und Valiant gestellte Frage und etablierte eine Grundlage für das Verständnis der Macht von Ensemble-Methoden. Das wahrscheinlich ungefähr korrekte Lernframework bietet formale Garantien für Boosting-Algorithmen und stellt sicher, dass das Ensemble mit genügend schwachen Lernern einen beliebig niedrigen Fehler auf der Trainingsverteilung erreichen kann. Diese theoretische Grundlage unterscheidet Boosting von vielen heuristischen Ensemble-Methoden und hat umfangreiche Forschung zu den Bedingungen inspiriert, unter denen Boosting erfolgreich ist.
Einschränkungen und Überlegungen
Boosting ist nicht ohne Einschränkungen. Es kann empfindlich auf verrauschte Daten und Ausreißer reagieren, da der Neugewichtungsmechanismus dazu führen kann, dass das Ensemble auf falsch beschriftete Beispiele überanpasst. Die sequenzielle Natur von Boosting macht es auch weniger für die Parallelisierung geeignet als Bagging, obwohl moderne Implementierungen Näherungen eingeführt haben, um das Training zu beschleunigen. Darüber hinaus können die Wahl des schwachen Lerners und die Anzahl der Runden die Leistung erheblich beeinflussen, was eine sorgfältige Abstimmung erfordert. Trotz dieser Herausforderungen bleibt Boosting eine der effektivsten und am weitesten verbreiteten Techniken im überwachten Lernen.