Nicht jedes Machine Learning Modell liefert auf Anhieb zufriedenstellende Ergebnisse. Training und Implementierung können in vielen Fällen zwar schnell vonstattengehen, allerdings liegt der Preis dafür in einer entsprechenden Ungenauigkeit. Das kann besonders bei der prädiktiven Datenanalyse zu Fehlern führen. Gefragt sind daher Methoden, die der Einfachheit und Generalisierbarkeit dieser “schwachen Lerner” nahekommen, aber zugleich eine erhöhte Performance zulassen. Eine weit verbreitete Herangehensweise ist es, mehrere Modelle miteinander zu kombinieren; man spricht dabei von Ensemble Learning.

Die individuellen Lösungswege aus der KI-Trickkiste verteilen sich überwiegend auf die Konzepte von Bagging, Stacking und Boosting, die jeweils verschiedene Lernverfahren umfassen. Gemeinsam haben sie alle, dass sie durch Kombinationstechniken “starke Lerner” bilden, die zusammen im Sinne einer Schwarmintelligenz die Irrtumswahrscheinlichkeit erheblich verringern.

Boosting zeichnet sich im Vergleich zu den anderen Ensemble-Methoden dadurch aus, dass die einzelnen Modelle nacheinander trainiert und üblicherweise bei hoher Verzerrung und geringer Varianz angewendet werden. Besonders populär und leistungsstark ist das sogenannte “adaptive Boosting” (kurz AdaBoost), das für Klassifikatoren eine beispiellose Genauigkeit verspricht.

Inhaltsverzeichnis

Adaptive Boosting – Definition und Grundlagen

definition and essentials of the adaboost algorithm

AdaBoost ist ein Ensemble-Lernalgorithmus, der sich auf sequentiell aufeinander folgende Trainingsverfahren mehrerer Decision Trees oder ähnlicher Klassifikatoren spezialisiert. Die Technik hat daher Ähnlichkeiten mit Random Forest, bei dem die Modelle jedoch durch Bagging parallel lernen. AdaBoost trainiert hingegen, wie beim Boosting üblich, nacheinander einzelne schwache Lerner. Diese können relativ einfach gehalten sein – bis hin zu Decision Stumps, die durch ihre Einstufigkeit ausschließlich binäre Klassen vorhersagen. AdaBoost wendet dabei ein überwachtes Lernverfahren (supervised learning) an, das durch die Strukturiertheit aufbereiteter Trainingsdaten definiert ist.

Aus Daten zu lernen, Fehler zu minimieren und fundierte Entscheidungen zu treffen sind Grundprinzipien von Machine Learning.

Hier gelingt das, indem jeder Klassifikator mit den gleichen Daten trainiert wird, nur dass die jeweils unterlaufenen Fehler künftig stärker gewichtet werden. In der sequentiellen Abfolge lernt also jeder schwache Lerner aus den Ungenauigkeiten seines Vorgängers, sodass am Ende in Summe eine möglichst genaue Klassifikation, Entscheidung oder Prognose steht. Von besonderer Bedeutung ist zudem die iterative Wiederholung dieses Prozesses, bis die gewünschte Vorhersagegenauigkeit erreicht ist.

Funktionsweise von AdaBoost

Wie bei Machine Learning üblich, nimmt die Anpassung von (neuronalen) Gewichten eine Schlüsselrolle ein, um einen Lernprozess zu modellieren. Die Verkettung verschiedener Modelle erlaubt es AdaBoost dieses Prinzip auszuweiten, indem auch die einzelnen Klassifikatoren unterschiedliche Relevanz für die Gesamtprognose erhalten. Man spricht dabei von Soft Voting. Um die optimale Gewichtung zu erreichen, sind zunächst einige Einzelschritte durchzuführen. Vorausgesetzt ist die Aufbereitung eines passenden Datensatzes.

Basisalgorithmus aufsetzen
Anfangs ist ein geeigneter schwacher Lerner notwendig, der einfache Prognosen über Datenpunkte liefern kann. Besonders gängig sind Decision Stumps – einstufige Decision Trees. Sie zerlegen den Datensatz in einzelne Entscheidungsknoten. Der Vergleich der Gini-Koeffizienten in Anwendung auf ein einzelnes (binäres) Feature hilft, den Stump mit der besten Performance zu identifizieren. Dieser bildet nun für das Ensemble-Modell den Basisalgorithmus, auf den weitere folgen.
Fehlerrechnung
Anschließend werden Gewichtungen für jede Instanz des Datensatzes eingeführt, sodass davon Stichproben genommen und jeweils die Korrektheit der klassifizierten Zielvariable bestimmt werden kann. Die so ermittelten fehlerhaften Datenpunkte können daher für den weiteren Prozess eine höhere Gewichtung erhalten.
Gewichtung des Klassifikators
Anhand der Fehlerquote kann AdaBoost die neue Bedeutung einzelner Klassifikatoren für das Ensemble-Modell berechnen. Je höher die Genauigkeit bzw. je weniger Fehler, desto höher ist das “Mitspracherecht” bei der Gesamtprognose. Dieses bildet zudem eine wichtige mathematische Grundlage für den folgenden Schritt.
Stichprobengewichte aktualisieren
Auch die ursprünglich ausgewogenen Samplegewichte durchlaufen nun eine Anpassung, die auf den fehlerhaften Datenpunkten des ersten Klassifikators basiert. Diese werden beim weiteren Prozedere stärker berücksichtigt, während korrekte Vorhersagen eine geringere Gewichtung erhalten und somit ebenfalls den Trainingseffekt intensivieren und die Fehlerfunktion zunehmend minimieren.
Iteration
Unter Verwendung eines durch diese Fehlerminimierung optimierten Klassifikators und/oder durch einen mithilfe der Samplegewichte überarbeiteten Datensatz können die Schritte mehrfach wiederholt werden. Dadurch entstehen zunehmend effektive Modelle von erhöhter Genauigkeit, die abschließend unter Berücksichtigung ihrer Gewichtungen bzw. des Mitspracherechts zu einem Ensemble-Modell aggregiert werden. Dieses kann AdaBoost nun auf neuartige Daten anwenden und somit bis dahin unbekannte Datenpunkte klassifizieren.

adaboost schema for weak classifiers — Dieses Schema erklärt in aller Kürze, wie Adaptive Boosting funktioniert. Quelle: Wikipedia

Beispiel nach Schema

Problemstellung: In diesem Beispiel sind die KI-Modelle als ein Ensemble von Modellen {h1, h2, h3, h4} und ihre Vorhersagen als eine Menge von Rechtecken dargestellt. Die Größe der Rechtecke (Vorhersagen) ist proportional zu ihren entsprechenden Gewichten (d.h. ihrer Wichtigkeit).

So funktioniert AdaBoost in diesem Beispiel: h1 macht eine Reihe von Vorhersagen. Den Fehlern von h1 (mit Fehlern sind die Vorhersagen gemeint, die von der Grundwahrheit abweichen) wird ein größeres Gewicht gegeben. h2 muss sich dann mehr darauf konzentrieren, die Fehler von h1 richtig vorherzusagen. (und so weiter für h3, h4…)

Am Ende liegen 4 KI-Modelle vor, die sich gegenseitig ihre Fehler korrigieren. Der endgültige Ensemble-Klassifikator wird „h“ genannt.

Mathematischer Hintergrund

Die mathematische Schwierigkeit hinter AdaBoost liegt in erster Linie in der Anpassung der Gewichte, die zu Beginn für alle Datenpunkte der Anzahl N gleichgesetzt sind.

Der Wert entspricht dabei der Wahrscheinlichkeit, dass dieser Datenpunkt für eine Stichprobe gezogen wird. Erst dadurch entsteht das verwendete Trainingsset für jede Iteration.

Zur Fehlerrechnung dient eine exponentielle Verlustfunktion, die einen konvexen Graphen ergibt und für negative Werte exponentiell wächst.

error function — y: Werte des Features
e: Eulersche Zahl
Cm(xi): Vorhersage

Sie modelliert die Differenz zwischen vorhergesagten und gewünschten Zielwerten, die somit die Ungenauigkeit des Modells abbildet. Ziel von Machine Learning wie auch Boosting ist immer die Minimierung dieser Funktion. Hier hilft der festgestellte Fehler, der als Summe der Sample-Gewichte aller falsch prognostizierten Datenpunkte zu verstehen ist, zudem bei der Priorisierung einzelner Decision Trees – also deren Mitspracherecht für das Gesamtmodell. Dieses nimmt Werte zwischen 0 und 1 an.

amount of say of the single classifiers — Der Anteil eines schwachen Lerners an der Gesamtprognose nach seiner Fehleranfälligkeit

Auch die Umgewichtung der Samples basiert auf festgestellten (Un-)genauigkeiten, die jedoch allein schon durch falsche Vorhersagen anstelle aufwändiger Berechnungen hervorgehen. Für jedes fehlerhaft klassifizierte Sample multipliziert AdaBoost dessen Gewicht mit der Eulerschen Zahl, die mit dem Mitspracherecht des Klassifikators potenziert wird: Neues Sample Gewicht = Altes Sample Gewicht x e^(Mitspracherecht). Für jedes korrekte Sample wird das negative Mitspracherecht eingesetzt.

Beispiel: Das Mitspracherecht eines Decision Stumps beträgt zu Anfang 0,96 bei insgesamt 8 Samples, die somit 1/N=⅛=0,125 gewichtet werden. Ein Sample wurde falsch klassifiziert. Dessen neues Gewicht ist damit 0,125 x e^(0,96) ≈ 0,33. Das ist höher als zuvor.

Für ein korrekt klassifiziertes Sample ergibt sich durch das negative Mitspracherecht hingegen ein neues Gewicht von etwa 0,05. Damit lernt AdaBoost also aus begangenen Fehlern, während korrekte Prognosen zunehmend vernachlässigt werden.

AdaBoost-Varianten

In der individuellen mathematischen Herangehensweise sind feine Unterschiede zwischen verschiedenen Varianten von AdaBoost begründet.

Real AdaBoost zeichnet sich durch die Verwendung von Decision Trees mit Klassenwahrscheinlichkeit als Output sowie die Anwendung des gewichteten Fehlers der kleinsten Quadrate aus.
Gentle AdaBoost ist eine Weiterentwicklung, die mithilfe einer begrenzten Schrittweite die Oszillationen des Algorithmus’ reguliert.
AdaBoostRegressor, auch AdaBoost.R2, wendet auf den ursprünglichen Datensatz mehrere Regressionen an, die nach jeder Fehlerrechnung angepasst werden.
Logitboost unterscheidet sich durch die Minimierung des logistischen anstelle des exponentiellen Verlustes.

Herausforderungen und Lösungsansätze

Trotz seiner hohen Genauigkeit ist auch AdaBoost kein ideales Modell. Durch das intensive Training auf fehlerhafte Datenpunkte und den daher souveränen Umgang mit unterrepräsentierten Klassen eignet es sich zwar gut für verzerrte Daten. Allerdings reicht diese Fähigkeit nur bis zu einem bestimmten Grad.

Niedrige Datenqualität

Bei starkem Ungleichgewicht in der Sample Verteilung kann selbst das eigentlich robuste Adaptive Boosting zu einer Überanpassung neigen, sogenanntem Overfitting. Dazu trägt aus mathematischer Sicht die verwendete Verlustfunktion bei, die durch ihre exponentielle Empfindlichkeit gegenüber negativen Werten anfällig für Ausreißer ist. Auch “rauschende Daten” können zum Problem werden, wenn bedeutungslose Zusatzinformationen die Prognosen beeinflussen.

Lösungsansatz: Feature Engineering

Bereits vor der Ausführung von AdaBoost lassen sich viele Schwächen in den verwendeten Daten bereinigen. Feature Engineering ist ein Oberbegriff für solche Optimierungen und umfasst verschiedene Techniken, die auf eine möglichst sinnvolle Strukturierung von Klassen und Merkmalen abzielen. Das erhöht die spätere Performance des Machine Learning Modells, erfordert jedoch ein hohes Maß an Expertise.

Zu schwache Lerner

Durch die Auswahl von Klassifikatoren von zu geringer Performance, beispielsweise bei Vernachlässigung des Gini-Koeffizienten, kann es ebenfalls zu Fehlern kommen. Auch der Einsatz von zu ähnlichen schwachen Lernern kann die Genauigkeit des Ensembles verringern. Dieses lebt schließlich von den diversifizierten Entscheidungen einzelner Teilnehmer.

Lösungsansatz: Pruning

Darunter kann man sich gewissermaßen die Heckenschere für Decision Trees vorstellen. So erlaubt diese Technik die Reduktion um zu schwache Teile bis hin zu ganzen Bäumen, wenn deren Performance unter einen kritischen Schwellenwert fällt. Das mindert in einigen Fällen zunächst die Genauigkeit für die Trainingsdaten; Gleiches gilt damit aber auch für ein mögliches Overfitting, sodass die spätere Prognose unbekannter Datenpunkte an Qualität zunimmt.

Anwendung und Entwicklung

Prinzipiell lässt sich Adaptive Boosting als Ensemble-Methode auf diverse Machine Learning Modelle wie z. B. Naive Bayes anwenden. Decision Trees sind die häufigste Wahl, weil selbst für komplexe Anwendungen eine Irrtumswahrscheinlichkeit der schwachen Lerner von knapp unter 50% ausreicht. Automatisierte Klassifikationen spielen bei vielen Analyseprozessen, aber auch in Endanwendungen eine Rolle.

Gesichtserkennung

Bereits 2001, nur wenige Jahre nach der Entstehung, wurde AdaBoost erstmals für die Gesichtserkennung nutzbar gemacht. Das betrifft allerdings nur die binäre Entscheidung, ob ein Gesicht erkennbar ist oder nicht. Zur Identifikation von Personen sind bedeutend komplexere Technologien notwendig, denen AdaBoost aber zumindest die erkannten Gesichter vorlegen könnte. Bedeutend ist dafür eine zusätzliche Testphase, die zu weiteren Iterationen bis zur notwendigen sehr hohen Genauigkeit führen kann.

face detection — Zur Identifikation individueller Gesichter kommt inzwischen Computer Vision zum Einsatz.

Bioinformatik

Die ausgeprägten Stärken in der treffsicheren Klassifikation selbst bei verzerrter Datengrundlage bringt Adaptive Boosting auch in interdisziplinären Gebieten zur Geltung: Beispielsweise den subzellulären Standort von Proteinen zu bestimmen, ist eine Aufgabe, die eine derart hohe Genauigkeit erfordert. Dafür haben die Forscher Fan und Wang (2011) den Algorithmus um eine Mehrklassigkeit erweitert und mit der Pseudoaminosäurezusammensetzung, der bis dahin üblichen Berechnungsmethode, kombiniert. Das Ergebnis: Eine signifikant gesteigerte Vorhersagegenauigkeit.

Boosting und Deep Learning

Neueste KI-Entwicklungen konzentrieren sich hauptsächlich auf Deep Learning, einen Teilbereich von Machine Learning, der durch den Einsatz vielschichtiger neuronaler Netze definiert ist. Natürlich versucht man aber auch, dadurch bisherige Techniken weiter zu verbessern. Das gilt auch für Adaptive Boosting. Inzwischen ist anstelle von Decision Trees unter anderem die Anwendung auf Convolutional Neural Networks möglich. Das erlaubt eine Skalierung auf sehr große Datensätze, sodass die Vorzüge beider Ansätze für Big Data und Enterprise AI nutzbar werden. Denn inzwischen spiegelt die Wirtschaft immer den aktuellsten KI-Entwicklungsstand wieder, der selbst in singulären Geschäftsprozessen sichtbar wird:

Das Ensemble für intelligentes Dokumentenmanagement

Die Aggregation eines leistungsstarken Ensembles funktioniert nicht nur für einfache Boosting-Modelle. Sie lässt sich bis hin zu darauf aufbauenden High-End-Technologien ausweiten, die jeweils von AdaBoost profitieren können. Der Beweis: Konfuzio. Diese Software für intelligentes Dokumentenmanagement umfasst KI-Technologien mit sehr unterschiedlichen technischen Ansätzen. Erst durch deren kombinierte Anwendung wird ein ganzheitliches Document Understanding bis ins Detail ermöglicht:

Computer Vision: Diese KI-Technologie ermöglicht mithilfe von Machine und Deep Learning die maschinelle Analyse von visuellen Inhalten. Das betrifft bei Dokumenten Bild- und Layout-Informationen. AdaBoost kann bei der Bildklassifikation helfen.
Optical Character Recognition: Als optische Zeichenerkennung ist sie für die Erfassung von Text verantwortlich. Dass solcher überhaupt vorliegt, ist eine Prognose, die durch AdaBoost optimiert werden kann.
Natural Language Processing: Der extrahierte Text soll am besten auch maschinell verstanden werden, um weitere Entscheidungen zu treffen. Das ist durch NLP auf Basis neuronaler Netze am besten möglich. Auch diese lassen sich inzwischen durch AdaBoost sequentiell verketten, um die Genauigkeit zu erhöhen.

Fazit

Es wird ein weiteres Mal deutlich, wie künstliche Intelligenz sich grundlegende Prinzipien der menschlichen Lebensrealität maschinell zunutze macht: Vier Augen sehen mehr als zwei. Fünf Klassifikatoren treffen eine bessere Entscheidung als nur einer. Auf diese Weise haben es Ensemble-Methoden wie Adaptive Boosting geschafft, jahrzehntelang relevant zu bleiben. Besonders wertvoll ist dabei die Fähigkeit, sequentiell aus festgestellten Ungenauigkeiten zu lernen und diese Fehler iterativ zu minimieren. So formt AdaBoost aus schwachen Lernern wie Decision Trees leistungsstarke Modelle, die sogar bei der Gesichtserkennung oder Bioinformatik hilfreich sind.

Ein Ende der Weiterentwicklungen ist noch nicht in Sicht. Zu rasant sind die Fortschritte im Deep Learning, die Adaptive Boosting auch für große Datenmengen in der Wirtschaft anwendbar machen. Zudem haben die Bereitstellung und die Qualität dieser Daten einen wesentlichen Anteil an der Modellgenauigkeit. Feature Engineering und Data Science sind daher ebenfalls hoch-relevante Einflüsse, die sich wiederum mit Entwicklungen der Dokumentenverarbeitung verschachteln. Aufgrund dieser Multifaktorialität lohnt es sich auch künftig, einen Blick auf Adaptive Boosting zu werfen und sich mit den neuesten Möglichkeiten vertraut zu machen.

Möchten Sie mehr über das Potenzial durch die Aggregation von Klassifikatoren und weiteren KI-Techniken erfahren? Schreiben Sie uns gerne eine Nachricht.