Random Forests as Statistical Procedures: Design, Variance, and Dependence

Diese Arbeit entwickelt eine endliche Stichproben-Theorie für Random Forests, die eine exakte Varianzzerlegung in Monte-Carlo-Fehler und eine durch Datenwiederverwendung sowie Partitionsausrichtung bedingte Kovarianzuntergrenze ermöglicht, und führt einen synthetischen Resampling-Ansatz (PASR) zur Schätzung dieser Untergrundvarianz und zur Konstruktion zuverlässiger Konfidenzintervalle für Vorhersagen ein.

Das Wesentliche

Stellen Sie sich vor, Sie haben eine Gruppe von 100 Experten, die gemeinsam eine schwierige Frage beantworten sollen. Jeder Experte ist ein bisschen verrückt: Er schaut sich nur eine zufällige Auswahl von Daten an, ignoriert einige Details und trifft seine Entscheidung basierend auf seiner eigenen, leicht chaotischen Logik. Wenn Sie nun den Durchschnitt aller 100 Meinungen nehmen, erhalten Sie eine sehr stabile und genaue Antwort. Das ist im Grunde, wie ein Random Forest (ein Zufallswald) funktioniert.

Aber hier kommt das Problem, das diese neue Studie aufdeckt: Selbst wenn Sie unendlich viele Experten hinzufügen, wird die Antwort nie zu 100 % perfekt werden. Es bleibt immer ein kleiner, unvermeidbarer „Fehler" oder eine Unsicherheit übrig.

Hier ist die einfache Erklärung der Forschung von Nathaniel O'Connell, warum das so ist und wie man dieses Problem löst.

1. Das Problem: Der „unsichtbare Boden" der Unsicherheit

Bisher dachten viele, dass man die Unsicherheit eines Random Forests einfach durch das Hinzufügen von mehr Bäumen (Experten) eliminieren kann. Wenn man 10.000 Bäume hat, sollte die Antwort doch perfekt sein, oder?

Die Studie sagt: Nein.

Stellen Sie sich vor, Sie werfen einen Ball in einen Raum voller Spiegel.

• Monte-Carlo-Fehler (Das Rauschen): Wenn Sie nur wenige Spiegel haben, ist das Bild des Balls unscharf. Wenn Sie mehr Spiegel hinzufügen, wird das Bild klarer. Das ist der Fehler, der durch die begrenzte Anzahl der Bäume entsteht. Dieser Fehler verschwindet, wenn Sie mehr Bäume hinzufügen.
• Der Kovarianz-Boden (Der feste Untergrund): Aber es gibt noch etwas anderes. Alle Spiegel im Raum hängen an derselben Wand. Wenn die Wand wackelt, wackeln alle Spiegel gleichzeitig. Auch wenn Sie 1.000.000 Spiegel haben, wackeln sie alle synchron. Das Bild wird nicht schärfer, es wackelt nur gemeinsam.

Dieses gemeinsame Wackeln nennt die Studie den Kovarianz-Boden. Er entsteht durch zwei Mechanismen:

1. Wiederverwendung von Daten: Verschiedene Bäume schauen sich oft dieselben Datenpunkte an. Wenn diese Datenpunkte „falsch" sind, machen alle Bäume denselben Fehler.
2. Partitions-Ausrichtung (Der wichtigere Teil): Selbst wenn Bäume völlig unterschiedliche Daten sehen, finden sie oft die gleichen Muster. Wenn die Datenstruktur sagt „Wenn X groß ist, dann ist Y klein", dann finden das alle Bäume unabhängig voneinander. Sie landen alle in denselben „Schubladen" (Terminalknoten) und treffen ähnliche Entscheidungen. Sie sind also nicht wirklich unabhängig, sondern wie Schulkinder, die alle die gleiche Antwort auf eine Mathe-Aufgabe geben, weil die Logik der Aufgabe sie alle in die gleiche Richtung lenkt.

Das Ergebnis: Es gibt eine untere Grenze für die Unsicherheit. Egal wie viele Bäume Sie pflanzen, diese Unsicherheit verschwindet nie ganz. Bisher wusste niemand, wie groß dieser „Boden" genau ist oder wie man ihn misst.

2. Die Lösung: PASR (Der synthetische Testlauf)

Wie misst man etwas, das man nicht direkt sehen kann? Die Autoren entwickeln eine Methode namens PASR (Procedure-Aligned Synthetic Resampling).

Stellen Sie sich vor, Sie haben einen fertigen Random Forest, der eine Vorhersage trifft. Sie wollen wissen: „Wie sicher ist diese Vorhersage wirklich?"

Anstatt neue echte Daten zu sammeln (was teuer und unmöglich ist), macht die Methode folgendes:

1. Der Klon: Sie nehmen Ihren fertigen Wald und Ihre vorhandenen Daten.
2. Die Simulation: Sie erfinden künstliche, „synthetische" Ergebnisse für Ihre Daten. Das ist, als würden Sie sagen: „Was wäre, wenn die Welt heute so aussähe, wie mein Wald es erwartet?"
3. Der Test: Sie lassen Ihren Wald diese künstlichen Daten durchlaufen. Da der Wald zufällig ist, wird er bei jedem Durchlauf leicht andere Ergebnisse liefern.
4. Die Analyse: Sie wiederholen diesen Prozess viele Male. Wenn die Ergebnisse stark schwanken, wissen Sie: „Aha, mein Wald ist unsicher." Wenn sie stabil sind, ist er sicher.

Der Clou dabei: Diese Methode trennt den Fehler, der durch die begrenzte Anzahl der Bäume kommt, von dem Fehler, der durch die Struktur des Waldes selbst kommt (den Boden).

3. Warum ist das wichtig?

Bisher hatten Praktiker zwei Probleme:

• Bei kontinuierlichen Zahlen (z. B. Hauspreise): Sie wussten nicht, wie breit ihre Vorhersageintervalle sein sollten. Oft waren sie zu eng und trafen die Realität nicht.
• Bei Klassifikation (z. B. „Krank" oder „Gesund"): Das war noch schlimmer. Bisher gab es keine seriöse Methode, um die Unsicherheit einer Wahrscheinlichkeitsvorhersage (z. B. „80 % Chance auf Krankheit") zu berechnen. Wenn ein Wald sagt „80 %", ist das dann 79 % oder 81 %? Oder vielleicht nur 60 %? Man wusste es nicht.

Mit der neuen Methode (PASR) können Sie endlich sagen:

• „Wir sagen, der Preis ist 300.000 €, und wir sind zu 95 % sicher, dass er zwischen 280.000 € und 320.000 € liegt."
• „Wir sagen, die Wahrscheinlichkeit für Krankheit ist 80 %, und das Intervall liegt zwischen 75 % und 85 %."

4. Die Metapher: Der Koch und das Rezept

Stellen Sie sich einen Koch vor, der ein Rezept für eine Suppe hat (der Random Forest).

• Das alte Denken: Wenn der Koch 100 Mal kocht und wir den Durchschnitt nehmen, ist die Suppe perfekt.
• Die neue Erkenntnis: Der Koch benutzt immer dieselben Zutaten (die Daten) und dieselben Gewürzmengen (die Hyperparameter). Selbst wenn er 1.000 Mal kocht, wird die Suppe immer leicht nach demselben „Fehler" schmecken, weil er immer dieselben Zutaten mischt.
• Die neue Methode (PASR): Wir lassen den Koch 1.000 Mal mit leicht veränderten, aber realistischen Zutaten kochen (synthetische Daten). So messen wir genau, wie sehr der Geschmack schwanken würde, wenn er das Rezept morgen nochmal kochen würde. Wir erkennen, dass es einen „Grundgeschmack" gibt, der sich nie ändert, egal wie oft er kocht.

Zusammenfassung

Diese Studie verwandelt den Random Forest von einem „Black-Box-Algorithmus" in ein verstandenes statistisches Werkzeug.

1. Sie beweist, dass es eine unvermeidbare Unsicherheit gibt, die durch die Struktur des Waldes selbst entsteht (nicht durch mangelnde Rechenleistung).
2. Sie bietet einen Messstab (PASR), um diese Unsicherheit zu berechnen.
3. Sie liefert zuverlässige Intervalle für Vorhersagen, sowohl für Zahlen als auch für Wahrscheinlichkeiten.

Das bedeutet: Wenn Sie in Zukunft einen Random Forest nutzen, können Sie endlich sagen: „Wir sind uns nicht nur sicher, sondern wir wissen genau, wie sicher wir sind." Das ist ein riesiger Schritt für die Zuverlässigkeit von KI in der Medizin, Finanzwelt und Wissenschaft.

Technische Zusammenfassung

1. Problemstellung und Motivation

Random Forests (RF) sind seit ihrer Einführung durch Breiman (2001) ein Standardwerkzeug für Vorhersagen in der Statistik und im maschinellen Lernen. Bisher wurden sie jedoch primär als Algorithmen betrachtet, deren theoretische Analyse oft auf asymptotischen Argumenten (große Stichproben) oder auf der Untersuchung der Stichprobenvariabilität (wie sich der Vorhersager ändert, wenn neue Trainingsdaten gezogen werden) basiert.

Das Paper identifiziert eine entscheidende Lücke in der bestehenden Theorie:

• Fehlende prozedurale Variabilität: Es gibt keine Methode, um die Unsicherheit eines bereits trainierten Random Forests für eine spezifische, feststehende Trainingsstichprobe zu quantifizieren. Die aktuelle Theorie ignoriert die Variabilität, die durch den zufälligen Konstruktionsprozess des Waldes (z. B. Bootstrap-Stichproben, zufällige Merkmalsauswahl) bei festen Daten entsteht.
• Das „Covariance Floor" (Kovarianzboden): Selbst wenn die Anzahl der Bäume ($B$) gegen unendlich geht, verschwindet die Varianz der Vorhersage nicht vollständig. Es bleibt eine irreduzible Varianz übrig, die durch strukturelle Abhängigkeiten zwischen den Bäumen verursacht wird. Bisherige Methoden (wie der infinitesimale Jackknife oder U-Statistiken) quantifizieren nur die Variabilität des Ziels bei wiederholter Datenerhebung, nicht die Unsicherheit der konkreten Vorhersage eines installierten Modells.
• Fehlende Intervalle für Klassifikation: Für Klassifikationswälder (die Wahrscheinlichkeiten vorhersagen) existieren keine theoretisch fundierten, punktweisen Konfidenzintervalle für die geschätzten bedingten Wahrscheinlichkeiten $\hat{p}(x)$.

2. Methodischer Ansatz: Design-basierte Theorie

Der Autor stellt einen Paradigmenwechsel vor: Random Forests werden als endliche Stichproben-Statistische Verfahren betrachtet, die auf einer festen Konfiguration von Kovariaten ($X$) operieren.

2.1 Variance Decomposition (Varianzzerlegung)

Das Paper leitet eine exakte Varianzidentität für die Vorhersage $\hat{f}_B(x)$ eines Waldes mit $B$ Bäumen ab, bedingt auf die realisierten Kovariaten $X$:

$$\text{Var}(\hat{f}_B(x) | X) = \frac{1}{B}\sigma^2_T(x) + \frac{B-1}{B}C_T(x)$$

Dabei sind:

• $\sigma^2_T(x)$: Die Varianz eines einzelnen Baumes (bedingt auf $X$). Dieser Term geht mit $1/B$ gegen Null.
• $C_T(x)$: Die Kovarianz zwischen den Bäumen. Dieser Term bleibt auch bei $B \to \infty$ bestehen und bildet den Covariance Floor.

2.2 Quellen der Abhängigkeit (Dependence Mechanisms)

Das Paper identifiziert zwei Mechanismen, die $C_T(x) > 0$ verursachen:

1. Observation Reuse (Wiederverwendung von Beobachtungen): Gleiche Trainingsdatenpunkte fließen in die Vorhersagen mehrerer Bäume ein (z. B. durch Bootstrap).
2. Partition Alignment (Ausrichtung der Partitionen): Selbst wenn Bäume auf disjunkten Teilmengen der Daten trainiert werden, können sie aufgrund der gleichen Datenstruktur und Split-Kriterien zu ähnlichen Partitionen und Terminalknoten für einen Punkt $x$ gelangen. Dies führt zu ähnlichen bedingten Vorhersageregeln.
   • Wichtig: Das Paper beweist, dass $C_T(x)$ strikt positiv ist, selbst wenn Observation Overlap eliminiert wird (z. B. durch Honest Forests), solange die Partition Alignment-Mechanismen wirken.

2.3 Schätzung des Covariance Floors: PASR

Um $C_T(x)$ zu schätzen, wird das Verfahren PASR (Procedure-Aligned Synthetic Resampling) eingeführt:

1. Modellspezifikation: Ein Modell für die bedingte Verteilung $P(Y|X)$ wird basierend auf den Trainingsdaten geschätzt (z. B. mittels Kreuzvalidierung für den Mittelwert und die Varianz bei kontinuierlichen Zielen).
2. Synthetische Resampling: Es werden synthetische Zielvektoren $Y^{(r)}$ aus diesem geschätzten Modell generiert.
3. Zwei unabhängige Wälder: Für jede synthetische Realisierung werden zwei unabhängige Random Forests (mit unterschiedlichen Zufallszahlen für die Baumgenerierung, aber gleichen Daten $X$ und $Y^{(r)}$) trainiert.
4. Kovarianzschätzung: Die Kovarianz der Vorhersagen dieser beiden Wälder über viele Replicates hinweg schätzt $C_T(x)$ unverzerrt, da der Monte-Carlo-Fehler durch die Unabhängigkeit der Wälder herausfällt.

Für kontinuierliche Outcomes wird ein konservativer Bias nachgewiesen (die Schätzung überschätzt tendenziell die Varianz, was zu konservativen Intervallen führt). Für binäre Outcomes wird gezeigt, dass der Schätzer asymptotisch unverzerrt ist (Bias der Ordnung $O(n^{-2})$).

3. Schlüsselbeiträge

1. Theoretische Fundierung: Erste endliche-Stichproben-Theorie für Random Forests, die prozedurale Variabilität (Design-Variabilität) von Stichprobenvariabilität trennt.
2. Nachweis des Covariance Floors: Mathematischer Beweis, dass eine irreduzible Varianz unter unendlicher Aggregation existiert und strikt positiv ist, verursacht durch Observation Reuse und Partition Alignment.
3. PASR-Verfahren: Entwicklung eines praktikablen Schätzers für diesen Boden, der keine asymptotischen Annahmen benötigt und für installierte Wälder anwendbar ist.
4. Unsicherheitsquantifizierung:
   • Für kontinuierliche Outcomes: Vorhersageintervalle, die die gesamte Unsicherheit (inkl. Covariance Floor) abdecken.
   • Für Klassifikation: Erstmals punktweise Konfidenzintervalle für die geschätzten bedingten Wahrscheinlichkeiten $\hat{p}(x)$ eines installierten Random Forests.
5. Design-Parameter-Analyse: Analyse, wie Hyperparameter (Subsampling-Rate $p_{obs}$, Anzahl der Kandidatenmerkmale $q$, minimale Knotengröße $s$) die Auflösung (Resolution) und die Abhängigkeit (Dependence) steuern. Es wird ein Trade-off zwischen Auflösung und Varianzreduktion durch Dekorrelation aufgezeigt.

4. Ergebnisse der Simulationsstudie

Die Studie evaluierte PASR über 36 Szenarien (verschiedene $n$, $p$, $q$, Sampling-Strategien) für kontinuierliche und binäre Outcomes:

• Schätzgenauigkeit:
  • Bei kontinuierlichen Outcomes ist PASR konsistent konservativ (Bias > 0), was durch die Theorie vorhergesagt wird. Die Schätzung folgt dem wahren Boden sehr genau (Korrelation $r \approx 0.997$).
  • Bei binären Outcomes ist der Bias nahe Null (asymptotisch unverzerrt), auch in hochdimensionalen Szenarien ($n=p$).
• Abdeckung (Coverage):
  • PASR-basierte Intervalle erreichen die nominale Abdeckung (ca. 95 %) für beide Outcomes-Typen.
  • Vergleich mit Infinitesimal Jackknife (IJ): Herkömmliche Methoden (IJ) unterschätzen die Unsicherheit massiv, da sie den Covariance Floor ignorieren.
    • Bei kontinuierlichen Outcomes: IJ-Abdeckung ca. 90 % (Unterschätzung um 5 %).
    • Bei binären Outcomes: IJ-Abdeckung ca. 78–79 % (Unterschätzung um 16 %). Dies zeigt, dass der Covariance Floor für Klassifikationswälder einen dominanten Anteil der Gesamtvarianz ausmacht.
• Robustheit: PASR funktioniert auch in hochdimensionalen Stress-Tests ($n=p=200$) stabil, wobei die Intervalle bei kontinuierlichen Outcomes konservativ bleiben und bei binären Outcomes die nominale Abdeckung halten.

5. Signifikanz und Implikationen

• Praktische Anwendbarkeit: Das Paper liefert das erste Werkzeug, um die Unsicherheit einer tatsächlichen Vorhersage eines trainierten Random Forests zu quantifizieren, ohne neue Daten ziehen zu müssen. Dies ist entscheidend für den Einsatz in kritischen Bereichen (z. B. Medizin, Risikomanagement).
• Neues Verständnis von Random Forests: Die Arbeit zeigt, dass Random Forests nicht nur als Black-Box-Algorithmen, sondern als statistische Verfahren mit definierten Eigenschaften (Auflösung vs. Abhängigkeit) verstanden werden können.
• Erweiterbarkeit: Der theoretische Rahmen lässt sich auf andere baumbasierte Ensembles übertragen (z. B. Honest Forests, Causal Forests, Survival Forests), solange die Bäume durch einen austauschbaren Mechanismus generiert werden.
• Lösung eines offenen Problems: Die Bereitstellung von Konfidenzintervallen für Vorhersagewahrscheinlichkeiten schließt eine lange bestehende Lücke in der Inferenz für Klassifikationswälder.

Zusammenfassend bietet das Paper einen rigorosen, design-basierten Rahmen, der die Unsicherheit von Random Forests vollständig charakterisiert und praktische Methoden zur korrekten Quantifizierung dieser Unsicherheit bereitstellt.