Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret

Diese Arbeit führt mit Blatt- und Struktur-Reue zwei komplementäre Maße ein, um die beobachtete Mehrdeutigkeit bei Entscheidungsbäumen zu zerlegen, wobei sie zeigt, dass die Instabilität der Baumstruktur der Haupttreiber dieser Variabilität ist und diese Maße zur Verbesserung der Modellsicherheit durch selektive Vorhersage genutzt werden können.

Das Wesentliche

Das Problem: Warum zwei kluge Computer unterschiedliche Ratschläge geben

Stellen Sie sich vor, Sie gehen zu zwei verschiedenen Ärzten, die beide super ausgebildet sind und die gleichen Daten über Ihre Gesundheit haben. Beide wollen Ihnen eine Diagnose stellen.

• Arzt A sagt: „Sie sind gesund."
• Arzt B sagt: „Sie brauchen eine Behandlung."

Beide Ärzte haben die gleichen Regeln gelernt, aber sie kamen zu einem anderen Ergebnis. In der Welt der künstlichen Intelligenz (KI) nennen wir das Vorhersage-Multiplizität. Es gibt viele Modelle, die alle fast gleich gut funktionieren, aber bei einzelnen Personen völlig unterschiedliche Entscheidungen treffen. Das ist gefährlich, besonders bei Dingen wie Kreditvergaben oder medizinischen Diagnosen.

Warum passiert das? Oft liegt es nicht daran, dass das Modell „dumm" ist, sondern daran, dass die Daten selbst ein bisschen verrückt sind.

Die zwei Hauptverdächtigen: Das „Blatt" und die „Struktur"

Die Autoren dieses Papers haben sich gefragt: Woher kommt diese Unsicherheit genau? Bei Entscheidungsbäumen (eine Art KI, die wie ein Flussdiagramm funktioniert) haben sie das Problem in zwei Teile zerlegt. Man kann sich das wie einen Wald mit Bäumen vorstellen.

1. Das „Blatt"-Reue (Leaf Regret) – Das Rauschen im Zimmer

Stellen Sie sich vor, Sie haben einen Baum, der in viele Äste und kleine Blätter (Endknoten) unterteilt ist. Jedes Blatt ist wie ein kleines Zimmer, in dem eine Gruppe von Leuten steht.

• Das Problem: In einem dieser kleinen Zimmer stehen vielleicht nur 10 Leute. Wenn Sie zufällig eine Person hinzufügen oder entfernen, ändert sich der Durchschnitt der Gruppe ein wenig. Das ist wie Rauschen im Radio.
• Die Metapher: Es ist, als würden Sie versuchen, die Durchschnittstemperatur in einem kleinen Raum zu messen. Wenn Sie das Thermometer nur einmal ablesen, kann es durch einen kleinen Luftzug (Zufall) leicht verfälscht sein. Das nennt man Blatt-Reue. Es ist das unvermeidliche Rauschen, das passiert, weil wir nicht unendlich viele Daten haben.

2. Die „Struktur"-Reue (Structural Regret) – Der wackelige Baum

Jetzt stellen Sie sich vor, Sie bauen den ganzen Wald neu auf. Aber jedes Mal, wenn Sie ein neues Set von Daten nehmen (vielleicht ein bisschen mehr Regen, ein bisschen mehr Sonne), wächst der Baum anders.

• Das Problem: Ein Ast, der gestern noch links war, ist heute rechts. Ein ganzer Zweig fehlt vielleicht. Das Modell hat sich komplett anders „strukturiert".
• Die Metapher: Das ist wie ein Wackelkuchen. Wenn Sie den Tisch ein bisschen schütteln (neue Daten), kippt der ganze Kuchen um und sieht ganz anders aus. Das nennt man Struktur-Reue. Es ist die Unsicherheit, die entsteht, weil der Baum selbst nicht stabil ist.

Die große Entdeckung: Der Baum wackelt mehr als das Rauschen

Die Forscher haben jetzt viele echte Datensätze (z. B. Kreditanträge aus der Türkei, Deutschland und Polen) analysiert. Das Ergebnis war überraschend und sehr wichtig:

• Das Rauschen im kleinen Zimmer (Blatt-Reue) ist klein.
• Das Wackeln des ganzen Baumes (Struktur-Reue) ist riesig.

In manchen Fällen war die Unsicherheit durch den wackeligen Baum über 15-mal größer als die Unsicherheit durch das kleine Rauschen in den Blättern.
Die Lehre: Wenn wir uns Sorgen um die Stabilität einer KI machen müssen, sollten wir nicht nur auf die kleinen Details schauen, sondern darauf, wie stabil der ganze Baum ist. Wenn der Baum wackelt, ist die Vorhersage für den einzelnen Menschen nicht vertrauenswürdig.

Die Lösung: „Ich weiß es nicht" sagen (Selective Prediction)

Was können wir tun, wenn wir merken, dass der Baum wackelt? Die Autoren schlagen eine clevere Methode vor: Abstinenz (also das Unterlassen einer Entscheidung).

Stellen Sie sich vor, Sie sind ein Richter. Wenn Sie unsicher sind, ob der Angeklagte schuldig ist, weil die Beweislage (die Daten) zu wackelig ist, sagen Sie nicht einfach „Schuldig" oder „Unschuldig". Sie sagen: „Ich kann das heute nicht entscheiden, wir brauchen einen menschlichen Richter."

In der KI-Forschung nennen wir das Selektive Vorhersage.

• Das System berechnet, wie stark es wackelt (die Reue).
• Wenn es stark wackelt, sagt die KI: „Ich trau mir das nicht zu."
• Wenn es stabil ist, trifft sie die Entscheidung.

Das Ergebnis: In Tests konnte die KI dadurch ihre Zuverlässigkeit (Recall) von 92 % auf 100 % steigern! Sie hat einfach die Fälle, bei denen sie unsicher war, aussortiert und an Menschen weitergegeben. Das macht das System sicherer und ehrlicher.

Zusammenfassung in einem Satz

Die Forscher haben gezeigt, dass bei Entscheidungsbäumen die größte Unsicherheit nicht durch kleine Datenfehler entsteht, sondern weil der ganze Baum bei neuen Daten umkippt; und wenn wir diese wackeligen Fälle erkennen und aussortieren, werden unsere KI-Entscheidungen viel sicherer und fairer.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret" auf Deutsch:

1. Problemstellung: Beobachtete Multiplizität und Entscheidungsbäume

Das Paper adressiert das Phänomen der vorhersagenden Multiplizität (Predictive Multiplicity), bei dem mehrere Modelle nahezu identische Gesamtleistung erzielen, aber für dieselben Individuen widersprüchliche Vorhersagen treffen. Ein spezifischer, oft unterschätzter Ursprung hierfür ist die beobachtete Multiplizität (Observational Multiplicity).

• Ursache: Trainingslabels sind stochastische Realisierungen zugrunde liegender Ground-Truth-Wahrscheinlichkeiten. Unterschiedliche, aber gleich plausible Ziehungen von Labels aus derselben Verteilung führen zu unterschiedlich trainierten Modellen.
• Lücke in der Forschung: Bisherige theoretische Rahmenwerke für beobachtete Multiplizität konzentrierten sich hauptsächlich auf glatte Modelle (wie die logistische Regression). Die Implikationen für nicht-glatte, partitionsbasierte Modelle wie Entscheidungsbäume sind kaum erforscht.
• Spezifisches Problem bei Bäumen: Entscheidungsbäume sind bekanntermaßen instabil gegenüber kleinen Datenstörungen (ähnlich wie k-NN-Klassifikatoren). Es fehlt eine Unterscheidung zwischen der Unsicherheit innerhalb eines festen Baums (durch Label-Rauschen) und der Unsicherheit, die durch die Instabilität der Baumstruktur selbst entsteht.

2. Methodik: Zerlegung in Blatt- und Struktur-Regret

Die Autoren führen eine formale Zerlegung der gesamten beobachteten Multiplizität in zwei komplementäre Komponenten ein:

A. Blatt-Regret (Leaf Regret)

• Definition: Misst die intrinsische Variabilität der Vorhersagen innerhalb eines festen Blattes $L$, bedingt auf eine gegebene Baumstruktur.
• Ursache: Endliche Stichprobengröße und stochastische Realisierung der Labels innerhalb eines Partitionszells.
• Mathematische Formulierung: $R_{leaf}^L := \text{Var}(\hat{p}_L | L) = \frac{p^*_L(1-p^*_L)}{n_L}$, wobei $n_L$ die Anzahl der Beobachtungen im Blatt ist.
• Eigenschaften:
  • Es ist eine wohldefinierte statistische Größe mit einer geschlossenen Form.
  • Es gilt eine obere Schranke von $\frac{1}{4n_L}$.
  • Es verschwindet asymptotisch, wenn die Blattgröße $n_L \to \infty$ wächst (Theorem 1).
  • Kann durch einen Plug-in-Schätzer oder Monte-Carlo-Resampling (Algorithmus 1) konsistent geschätzt werden.

B. Struktur-Regret (Structural Regret)

• Definition: Misst die zusätzliche Variabilität, die durch die Instabilität der gelernten Baumstruktur selbst entsteht, wenn die Trainingslabels variiert werden.
• Ursache: Zufälligkeit bei der Auswahl der Split-Punkte und der induzierten Partitionierung des Raumes.
• Mathematische Formulierung: $R_{struct}(x) := \text{Var}_T(\hat{p}(x; T))$, wobei die Varianz über die Zufälligkeit des Lernalgorithmus (verschiedene Bäume $T$) genommen wird.
• Zerlegungssatz (Lemma 6): Die gesamte Vorhersagevarianz lässt sich exakt zerlegen:
  $$\text{Var}(\hat{p}(x)) = \mathbb{E}_T[R_{leaf}^{L(x;T)}] + R_{struct}(x)$$
  (Erwarteter Blatt-Regret + Struktur-Regret).
• Schätzung: Da die Verteilung oft analytisch nicht handhabbar ist, wird Struktur-Regret durch Bootstrap-Resampling und erneutes Training von Bäumen approximiert (Algorithmus 2).

3. Wichtige Beiträge

1. Formale Zerlegung: Erstmals wird die beobachtete Multiplizität bei Entscheidungsbäumen in lokale (Blatt) und globale (Struktur) Komponenten zerlegt.
2. Theoretische Garantien: Bereitstellung von Konvergenzungleichungen und Konsistenzbeweisen für die Schätzung des Blatt-Regrets.
3. Identifikation der Hauptursache: Empirische und theoretische Analyse zeigt, dass die Instabilität der Partitionsgrenzen (Struktur-Regret) der dominante Faktor ist, nicht das Rauschen innerhalb der Blätter.
4. Anwendung auf Selektive Vorhersage: Nutzung der Regret-Metriken als Mechanismus zur Abstention (Zurückhaltung von Vorhersagen), um die Sicherheit in Hochrisiko-Szenarien zu erhöhen.

4. Ergebnisse und Experimente

Die Studie wurde an mehreren realen Datensätzen im Bereich Kreditrisiko (z. B. taiwan_credit, german_credit, bank_marketing) durchgeführt.

• Validierung der Zerlegung: In einer semi-synthetischen Studie (200 Realisierungen von Labels) zeigte sich eine nahezu perfekte Übereinstimmung zwischen der theoretisch zerlegten Varianz (Summe aus Blatt- und Struktur-Regret) und der empirisch beobachteten Gesamtvarianz (Abbildung 1).
• Dominanz des Struktur-Regrets:
  • Der Struktur-Regret ist der primäre Treiber der Multiplizität.
  • In einigen Datensätzen (z. B. taiwan_credit) ist der Struktur-Regret über 15-mal größer als der Blatt-Regret (Tabelle 1).
  • Dies bedeutet, dass die Unsicherheit weniger vom Rauschen innerhalb eines Blattes kommt, sondern davon, dass sich die Grenzen der Blätter bei kleinen Änderungen der Trainingsdaten verschieben.
• Einfluss der Blattgröße: Eine Erhöhung der minimalen Blattgröße ($n_L$) reduziert den Blatt-Regret stark (Bestätigung von Lemma 2), führt aber zu einem Anstieg des Log-Loss (Underfitting), was einen Trade-off zwischen lokaler Stabilität und globaler Vorhersagegüte aufzeigt.
• Selektive Vorhersage (Safety):
  • Durch Abstention bei hohen Regret-Werten (basierend auf der Rangfolge der Unsicherheit) konnte die Recall-Rate in stabilen Subpopulationen von 92 % auf 100 % gesteigert werden (z. B. im german_credit-Datensatz).
  • Das Modell zeigt „Ehrlichkeit": In Regionen, wo die Recall-Rate bei geringer Abdeckung stark einbricht, signalisiert das Modell, dass Vorhersagen dort rein zufällig (arbiträr) und nicht durch Signale gestützt sind.
  • Der Struktur-Regret erwies sich als robusterer Filter zur Identifizierung schwer zu treffender Positivfälle als der Blatt-Regret.

5. Bedeutung und Schlussfolgerung

Das Paper liefert einen rigorosen Rahmen, um die Unvermeidbarkeit von Label-Unsicherheit von der Instabilität der Modellstruktur zu trennen.

• Für die Praxis: In Hochrisiko-Bereichen (Kreditvergabe, Gesundheit, Recht) sollte die Fokussierung nicht nur auf die Erhöhung der Stichprobengröße in Blättern liegen, sondern primär auf der Stabilisierung der Baumstruktur (z. B. durch stärkere Regularisierung, Pruning oder Ensemble-Methoden).
• Algorithmische Sicherheit: Die vorgeschlagenen Regret-Metriken ermöglichen es, Individuen zu identifizieren, bei denen das Modell „rät". Dies erlaubt eine Eskalation zu manueller Überprüfung anstelle automatisierter, arbiträrer Entscheidungen.
• Zukunftsausblick: Der Ansatz legt den Grundstein für sicherere, interpretierbare Entscheidungsbäume und muss zukünftig auf Mehrklassen-Probleme und Ensemble-Architekturen erweitert werden.

Zusammenfassend beweist das Paper, dass bei Entscheidungsbäumen die Instabilität der Partitionsgrenzen das Hauptproblem für Vorhersage-Arbitrarität ist, und bietet ein quantitatives Werkzeug, um dieses Risiko zu messen und zu managen.