Zufallswald

Zufallswälder (Random Forests) sind eine Ensemble-Lernmethode, die für Klassifikation, Regression und andere Aufgaben verwendet wird. Sie konstruieren während des Trainings eine große Anzahl von Entscheidungsbäumen und kombinieren deren Ausgaben: Bei der Klassifikation wird die Klasse zurückgegeben, die von den meisten Bäumen gewählt wurde; bei der Regression wird der Durchschnitt der Vorhersagen der einzelnen Bäume gebildet. Die Methode korrigiert die Tendenz von tiefen Entscheidungsbäumen, ihre Trainingsdaten zu überanpassen, indem sie die Varianz reduziert, während die Verzerrung niedrig bleibt.

Der erste Zufallswald-Algorithmus wurde 1995 von Tin Kam Ho entwickelt, basierend auf dem Zufalls-Unterraum-Verfahren, das den von Eugene Kleinberg vorgeschlagenen stochastischen Diskriminationsansatz umsetzt. Leo Breiman und Adele Cutler erweiterten den Ansatz später, indem sie Bagging mit zufälliger Merkmalsauswahl kombinierten, und meldeten „Random Forests“ 2006 als Marke an; seit 2019 gehört die Marke Minitab, Inc.

Hintergrund: Entscheidungsbäume und ihre Grenzen

Entscheidungsbäume sind eine weit verbreitete Methode im maschinellen Lernen. Sie partitionieren den Merkmalsraum durch eine Reihe binärer Splits, was sie skalierbar und leicht interpretierbar macht. Allerdings neigen tiefe Bäume dazu, sehr unregelmäßige Muster zu lernen, was zu einer geringen Verzerrung, aber einer sehr hohen Varianz führt. In der Praxis kann ein auf einem bestimmten Datensatz trainierter Baum drastisch anders ausfallen, wenn nur wenige Trainingspunkte verändert werden, und seine Vorhersagen sind oft nur für die Trainingsdaten genau. Auf ungesehenen Daten sind sie selten präzise, wie Trevor Hastie und Kollegen anmerken. Zufallswälder begegnen diesem Problem, indem sie viele Bäume mitteln, die jeweils auf verschiedenen Teilmengen der Daten trainiert werden, um die Varianz erheblich zu reduzieren.

Die Schwierigkeit bei Baummethoden besteht darin, dass das Trainieren zu vieler Bäume auf denselben Daten zu korrelierten Vorhersagen führt. Um die Korrelation zu verringern, verwenden Zufallswälder Bootstrapping und zufällige Merkmalsauswahl, wodurch die einzelnen Bäume vielfältig, aber dennoch stark werden.

Geschichte und Entwicklung

Die allgemeine Idee zufälliger Entscheidungswälder taucht 1993 in Arbeiten von Salzberg und Heath auf, die einen randomisierten Entscheidungsbaum-Algorithmus vorschlugen, um mehrere Bäume zu erzeugen und sie per Mehrheitsentscheidung zu kombinieren. 1995 erweiterte Tin Kam Ho diesen Ansatz und zeigte, dass Wälder aus Bäumen, die auf schrägen Hyperebenen splitten, mit zunehmender Größe an Genauigkeit gewinnen, ohne zu übertrainieren, sofern die Wälder zufällig auf eine Teilmenge der Merkmale beschränkt werden. Ho’s Methode, das Zufalls-Unterraum-Verfahren, konstruierte Bäume, indem die Trainingsdaten in zufällig ausgewählte Merkmalsunterräume projiziert wurden. Dies war ein wichtiger Schritt in der Entwicklung der Zufallswälder.

Spätere Arbeiten von Amit und Geman führten unabhängig die Idee ein, bei jedem Split eine zufällige Teilmenge der verfügbaren Entscheidungen zu durchsuchen, allerdings wandten sie dies auf einen einzelnen Baum an. Unabhängig davon führte Thomas Dietterich die Idee der randomisierten Knotenoptimierung ein, bei der das Attribut an jedem Knoten durch ein Zufallsverfahren statt durch ein deterministisches Optimalitätskriterium gewählt wird. Diese Ideen, kombiniert mit Leo Breimans früheren Arbeiten zum Bagging, führten zur modernen Formulierung der Zufallswälder. Breimans einflussreiche Arbeit von 2001, eine der am häufigsten zitierten im maschinellen Lernen, vereinte diese Ansätze und lieferte eine theoretische Obergrenze für den Generalisierungsfehler, basierend auf der Stärke und der Korrelation der Bäume im Wald.

Breimans Arbeit etablierte auch praktische Werkzeuge: den Out-of-Bag-Fehler zur Schätzung des Generalisierungsfehlers ohne separates Validierungsset sowie die permutationsbasierte Variablenwichtigkeit, die misst, wie stark sich die Leistung verschlechtert, wenn die Werte eines Merkmals zufällig durchgemischt werden. Diese Werkzeuge sind bis heute zentrale Bestandteile von Zufallswäldern.

Bagging und Ensemble-Lernen

Die grundlegende Technik beim Training von Zufallswäldern ist das Bootstrap-Aggregieren, auch Bagging genannt. Bei einem Trainingssatz mit Merkmalen X und Antworten Y samplet der Algorithmus B-mal mit Zurücklegen aus den Trainingsdaten und erstellt so jeweils einen neuen Datensatz derselben Größe. Auf jedem Bootstrap-Sample wird ein Entscheidungsbaum trainiert, der typischerweise tief wächst und nicht beschnitten wird. Nach dem Training werden Vorhersagen für einen neuen Punkt entweder durch Mittelung (bei Regression) oder durch Mehrheitsentscheidung (bei Klassifikation) über alle Bäume getroffen. Diese Meta-Algorithmus reduziert die Varianz, ohne die Verzerrung zu erhöhen, da der Durchschnitt vieler unkorrelierter Bäume stabiler ist als ein einzelner Baum.

Das Bootstrap-Sampling dekorreliert die Bäume, indem es ihnen unterschiedliche Trainingssätze zeigt. Würden alle Bäume auf denselben Originaldaten trainiert, wären sie sehr ähnlich und anfällig für dieselben Fehler. Durch das Bootstrap-Sampling erfasst jeder Baum unterschiedliche Variationen der Daten. Die Varianzreduktion nimmt mit der Anzahl der Bäume B zu, aber nach einigen hundert Bäumen wird die Verbesserung marginal. In der Praxis wird B oft auf 500 oder 1000 gesetzt, wobei moderne Implementierungen automatisch stoppen, sobald sich der Out-of-Bag-Fehler stabilisiert.

Ein entscheidender Aspekt von Zufallswäldern ist, dass jeder Baum typischerweise auf einem anderen Datensatz trainiert wird, der durch Sampling mit Zurücklegen entsteht: Ungefähr zwei Drittel der Beobachtungen erscheinen in jedem Bootstrap-Sample, während das verbleibende Drittel Out-of-Bag bleibt. Die Out-of-Bag-Vorhersagen können zur Schätzung des Generalisierungsfehlers verwendet werden, ohne dass ein separates Validierungsset benötigt wird – basierend auf den aggregierten Vorhersagen für jede Beobachtung unter Verwendung der Bäume, die diese Beobachtung nicht im Training hatten.

Zufällige Merkmalsauswahl

Die zentrale Innovation der Zufallswälder ist die zufällige Auswahl von Merkmalen bei jedem Knotensplit. Traditionelle Entscheidungsbäume optimieren bei jedem Knoten den Split über alle Merkmale, um etwa die Gini-Unreinheit (bei Klassifikation) oder den quadratischen Fehler (bei Regression) zu minimieren. Zufallswälder hingegen betrachten bei jedem Split nur eine zufällig gewählte Teilmenge der Merkmale, deren Größe oft etwa der Quadratwurzel der Gesamtzahl der Merkmale entspricht. Dies zwingt die Bäume zu unterschiedlichen Strukturen und reduziert die Korrelation zwischen ihnen. Manchmal werden alternative Splits gewählt, weil einige globale Merkmale sonst dominieren würden, was zu nahezu identischen Bäumen führen könnte. Durch die zufällige Beschränkung der Kandidatenmerkmale kann der Wald eine größere Vielfalt an Mustern erkunden und so robustere Vorhersagen erzielen.

Dieser Ansatz des zufälligen Unterraums wurde von Ho eingeführt und später von Amit und Geman sowie durch die Knotenrandomisierung von Dietterich weiterentwickelt. Breimans endgültige Formulierung verwendete die zufällige Merkmalsauswahl bei jedem Knoten, während einige Varianten die Zufallsauswahl nur vor dem Training jedes Baumes vornehmen. Moderne Implementierungen unterscheiden sich in den Details; viele Bibliotheken unterstützen sowohl die Variante mit zufälliger Merkmalsauswahl pro Knoten als auch die mit zufälliger Auswahl pro Baum. Üblicherweise wird die Merkmalsanzahl d verwendet, wobei bei Klassifikation eine Teilmenge der Größe sqrt(d) und bei Regression d/3 gewählt wird.

Modellverhalten und Überanpassungsresistenz

Zufallswälder sind bekannt für ihre Robustheit gegenüber Überanpassung. Jeder einzelne Baum mag tief wachsen und überanpassen, aber das Ensemble mittelt diese Effekte und reduziert so die Varianz. Tiefere Bäume neigen dazu, die Leistung zu verbessern, solange die Anzahl der Bäume ausreichend groß ist, da die Randomisierung die Korrelation begrenzt. Breimans theoretische Ergebnisse zeigen eine Obergrenze für den Generalisierungsfehler, die mit zunehmender Stärke der Bäume und abnehmender Korrelation sinkt. Wenn die Anzahl der Bäume jedoch zu groß wird, verbessert sich der Fehler nicht weiter, bleibt aber stabil und überanpasst nicht, da die Out-of-Bag-Schätzung eine unverzerrte Bewertung liefert. Wenn die Merkmalsauswahl nicht zufällig erfolgt, können die Bäume stark korreliert sein, was den Vorteil des Ensembles zunichte macht. Mit zufälliger Merkmalsauswahl bleibt der Wald auch bei komplexen Datenstrukturen genau, im Gegensatz zu einem einzelnen tiefen Baum, der schnell überanpasst.

Bei Klassifikationsproblemen ist die Ausgabe des Waldes die Klasse mit den meisten Stimmen über alle Bäume. Bei Regressionsproblemen ist die Vorhersage der Durchschnitt der einzelnen Baumvorhersagen, und die Standardabweichung dieser Vorhersagen kann als natürliches Unsicherheitsmaß dienen.

Praktische Anwendungen und Erweiterungen

Zufallswälder werden in vielen Bereichen eingesetzt, darunter Fernerkundung, Bioinformatik, Finanzwesen und Computer Vision. Sie sind robust gegenüber irrelevanten Merkmalen, können nichtlineare Zusammenhänge modellieren und bieten eine gewisse Interpretierbarkeit, auch wenn sie weniger transparent sind als ein einzelner Entscheidungsbaum. Variablenwichtigkeitsmaße ermöglichen es Forschern, relevante Merkmale zu identifizieren. Zufallswälder werden auch im maschinellen Lernen als grundlegender Algorithmus verwendet und dienen als Basis für viele moderne Ansätze, neben Deep Learning und neuronale Netze.

Erweiterungen umfassen Extremely Randomized Trees (Extra Trees), die noch zufälligere Split-Schwellen verwenden, sowie Anwendungen von Zufallswäldern für Anomalieerkennung, Ranking und die Imputation fehlender Werte. Sie werden auch als Bausteine in maschinellen Lern Pipelines eingesetzt.

Vergleich mit anderen Modellen

Zufallswälder unterscheiden sich von Deep Learning-Modellen wie neuronale Netze dadurch, dass sie interpretierbarer sind, weniger Daten benötigen und einfacher zu trainieren sind. Sie können auf CPUs trainiert werden, während tiefe neuronale Netze oft spezielle Beschleuniger erfordern. Allerdings haben Zufallswälder Schwierigkeiten mit sehr hochdimensionalen Daten und sind bei unstrukturierten Daten wie Bildern oder Text weniger effektiv, wo Deep Learning überlegen ist. Der Trade-off besteht darin, dass Zufallswälder eine robuste und recheneffiziente Baseline bieten, aber nicht die hierarchische Merkmalslernfähigkeit tiefer Netze besitzen.

An der Spitze der modernen Forschung zu künstlicher Intelligenz dominieren Architekturen wie Large Language Models und Transformer die Verarbeitung natürlicher Sprache, aber Zufallswälder und andere Baum-Ensembles bleiben in Bereichen wie tabellarischen Daten und erklärbarer KI weit verbreitet.

Siehe auch

• Maschinelles Lernen
• Künstliche Intelligenz
• Entscheidungsbaum

Referenzen

Die ursprünglichen Quellen sind im Artikel zitiert, aber keine externen URLs sind relevant.