Circuit Representations of Random Forests with Applications to XAI

Diese Arbeit stellt einen effizienten Ansatz vor, um Random-Forest-Klassifikatoren in logische Schaltkreise zu übersetzen, um darauf aufbauend fundierte, robuste und erklärbare Entscheidungsanalysen wie vollständige Gründe, Kontrasterklärungen und Robustheitsmetriken zu berechnen.

Das Wesentliche

🌳 Der Wald, der denkt: Wie man KI-Entscheidungen endlich versteht

Stellen Sie sich vor, ein Random Forest (ein Zufallswald) ist wie ein riesiges Team von 500 verschiedenen Experten, die gemeinsam eine Entscheidung treffen. Jeder Experte ist ein kleiner Entscheidungsbaum. Wenn Sie eine Frage stellen (z. B. "Ist dieser Patient krank?"), hört sich jeder Experte die Fakten an, trifft seine eigene Meinung und stimmt ab. Die Antwort des Teams ist die Meinung, die die meisten Experten vertreten (Mehrheitsentscheid).

Das Problem: Niemand weiß genau, warum das Team so entschieden hat. Man kann die Entscheidung zwar sehen, aber nicht den Weg dorthin. Es ist wie ein schwarzer Kasten.

Die Autoren dieses Papiers (Chunxi Ji und Adnan Darwiche) haben nun eine Methode entwickelt, um diesen "schwarzen Kasten" in eine klare, durchschaubare Landkarte zu verwandeln. Hier ist, wie sie das gemacht haben, Schritt für Schritt:

1. Die Landkarte bauen: Vom Chaos zur Ordnung

Stellen Sie sich vor, Sie wollen die Entscheidung dieses 500-Mann-Teams in eine einzige, logische Formel packen.

• Das alte Problem: Bisherige Methoden waren wie der Versuch, 500 verschiedene Notizbücher in einen einzigen Haufen zu werfen und dann mit einem Suchgerät (einem "SAT-Solver") zu versuchen, die Antwort zu finden. Das ist langsam, chaotisch und liefert oft nur eine grobe Schätzung.
• Die neue Lösung (Der "Sortier-Algorithmus"): Die Autoren nutzen einen cleveren Trick aus der Informatik, den sie "Sortier-Netzwerk" nennen.
  • Die Analogie: Stellen Sie sich vor, Sie haben 500 Experten, die jeweils eine Ja/Nein-Karte hochhalten. Statt alle Karten einzeln zu zählen, bauen Sie eine Rutsche (das Netzwerk). Die Karten rutschen durch, werden paarweise verglichen und sortiert. Am Ende der Rutsche sehen Sie sofort: "Okay, hier sind die 251 Ja-Stimmen, die für die Entscheidung entscheidend waren."
  • Das Ergebnis: Sie erhalten eine Schaltkreis-Karte (Circuit). Diese Karte ist nicht nur eine Liste von Regeln, sondern eine effiziente Maschine, die genau zeigt, welche Kombination von Fakten zu welcher Entscheidung führt. Und das geht viel schneller als alle bisherigen Methoden.

2. Die "Warum"-Fragen beantworten (XAI)

Sobald wir diese Landkarte haben, können wir die wichtigsten Fragen der KI-Erklärbarkeit (XAI) beantworten. Die Autoren nutzen die Karte, um drei Dinge zu tun:

• A) Der "Mindest-Grund" (Sufficient Reasons):

  • Frage: "Warum wurde ich abgelehnt?"
  • Antwort: Die Karte zeigt Ihnen den kleinsten Satz von Fakten, der ausreicht, um die Entscheidung zu treffen.
  • Beispiel: Vielleicht waren es nur zwei Dinge: "Alter > 50" und "Raucher". Selbst wenn Sie sonst gesund wären, hätten diese zwei Fakten gereicht, um die Entscheidung zu fallen. Die Karte findet diese winzigen, entscheidenden Gründe sofort.

• B) Der "Was-wäre-wenn"-Grund (Necessary Reasons & Contrastive Explanations):

  • Frage: "Was müsste ich ändern, um eine andere Entscheidung zu bekommen?"
  • Antwort: Die Karte zeigt Ihnen die Schwachstellen. "Wenn Sie nicht rauchen würden, hätten Sie eine Chance." Oder: "Wenn Sie jünger als 50 wären."
  • Die Metapher: Es ist wie ein Spiel, bei dem Sie versuchen, die Entscheidung umzudrehen, indem Sie so wenige Steine wie möglich aus dem Mauerwerk entfernen. Die Karte zeigt Ihnen genau, welche Steine Sie herausziehen müssen, damit das ganze Haus (die Entscheidung) einstürzt.

• C) Die "Robustheit" (Wie stabil ist die Entscheidung?):

  • Frage: "Wie sicher ist diese Entscheidung? Wenn ich nur einen kleinen Fehler in meinen Daten mache, kippt die Entscheidung dann sofort?"
  • Antwort: Die Autoren berechnen, wie viele Fakten man ändern müsste, um das Ergebnis zu drehen.
  • Ergebnis der Studie: Bei vielen Datensätzen war die Entscheidung sehr "wackelig". Oft reichte es, nur einen einzigen Faktor (z. B. das Alter um ein Jahr zu ändern), um das Ergebnis komplett zu drehen. Das ist eine wichtige Warnung für Ärzte oder Banker: "Pass auf, diese Entscheidung ist sehr empfindlich!"

3. Warum ist das alles so toll?

Bisher waren diese Erklärungen oft nur Annäherungen (wie eine grobe Schätzung mit einem Lineal). Die Autoren haben jetzt eine Methode, die mathematisch exakt ist.

• Effizienz: Sie können diese Berechnungen für riesige Wälder (Tausende von Entscheidungsbäumen) in Sekundenbruchteilen durchführen.
• Vollständigkeit: Sie finden alle möglichen Gründe, nicht nur einen zufälligen.
• Vertrauen: Da die Methode auf einer exakten mathematischen Karte basiert, gibt es keine "Raten". Man weiß genau, warum die KI so denkt.

Zusammenfassung in einem Satz

Die Autoren haben einen Weg gefunden, den chaotischen "Zufallswald" einer KI in eine perfekte, durchsichtige Landkarte zu verwandeln, die uns sofort sagt, warum eine Entscheidung getroffen wurde, wie man sie ändern könnte und wie stabil sie eigentlich ist – und das alles blitzschnell und ohne Raten.

Technische Zusammenfassung

1. Problemstellung

Die Erklärung von Entscheidungen maschineller Lernmodelle (XAI) gewinnt zunehmend an Bedeutung. Insbesondere baumbasierte Klassifikatoren wie Random Forests sind in der Praxis sehr erfolgreich, oft sogar besser als neuronale Netze. Allerdings bieten gängige modellagnostische Erklärungsmethoden wie LIME oder ANCHOR nur Approximationen ohne formale Garantien für die hinreichende oder notwendige Gültigkeit der Erklärungen.

Ziel ist es, formale Erklärungen zu liefern, darunter:

• Hinreichende Gründe (Sufficient Reasons, SR): Minimale Teilmengen eines Instanzmerkmals, die die Entscheidung garantieren.
• Notwendige Gründe (Necessary Reasons, NR): Minimale Eigenschaften, deren Änderung die Entscheidung umkehren würde.
• Kontrastive Erklärungen (Contrastive Explanations, CE): Wie eine Entscheidung in eine Zielklasse geändert werden kann.
• Robustheit: Die minimale Anzahl an Merkmalen, die geändert werden müssen, um die Entscheidung zu kippen.

Das Hauptproblem besteht darin, Random Forests effizient in eine Form zu überführen, die es erlaubt, diese formalen Konzepte (insbesondere den kompletten Grund und den allgemeinen Grund) exakt und in linearer Zeit zu berechnen. Bestehende Ansätze nutzen oft SAT-Löser mit Hilfsvariablen, was die direkte Berechnung dieser Gründe erschwert, oder erzeugen Entscheidungsgraphen, die nicht die erforderlichen Traktabilitätseigenschaften besitzen.

2. Methodik

Die Autoren schlagen einen zweistufigen Ansatz vor, der Random Forests in traktbare Schaltkreise (Circuits) kompiliert:

A. Kompilierung in NNF-Schaltkreise (Algorithmus 3)

Anstatt Random Forests in CNF-Formeln mit Hilfsvariablen zu übersetzen, nutzen die Autoren Sortier-Netzwerke (Sorting Networks), speziell Odd-Even-Sortier-Netzwerke.

• Prinzip: Ein Sortier-Netzwerk nimmt $n$ Eingaben entgegen und sortiert sie. In diesem Kontext werden die Eingaben als NNF-Schaltkreise (Negation Normal Form) interpretiert, die die Klassenformeln der einzelnen Bäume darstellen.
• Operationen: Ein Komparator im Netzwerk wird so interpretiert, dass er zwei Eingabeschaltkreise $\alpha$ und $\beta$ nimmt und als Ausgaben $\alpha \lor \beta$ (Maximum) und $\alpha \land \beta$ (Minimum) erzeugt.
• Mehrklassen-Problem: Für mehr als zwei Klassen wird eine raffinierte Technik angewendet. Um die Klasse $c_i$ zu bestimmen, wird für jede andere Klasse $c_j$ ein Schaltkreis konstruiert, der Instanzen kodiert, bei denen $c_i$ mindestens so viele Stimmen wie $c_j$ erhält. Die finale Klassenformel ist die Konjunktion aller dieser paarweisen Vergleiche.
• Ergebnis: Dies erzeugt NNF-Schaltkreise, die exakt die Klassenformeln des Random Forests darstellen, ohne Hilfsvariablen.

B. Umwandlung in traktbare Entscheidungsgraphen (Algorithmus 3A/3B)

Um die Berechnung von kompletten und allgemeinen Gründen in linearer Zeit zu ermöglichen, müssen die Schaltkreise bestimmte Eigenschaften erfüllen (insbesondere die weak test-once-Eigenschaft).

• Die Autoren nutzen einen Algorithmus (basierend auf OBDD-Operationen), der zwei schwache test-once-Entscheidungsgraphen (DG) konjunktiv oder disjunktiv verbindet, während die Eigenschaft erhalten bleibt.
• Algorithmus 3B: Erzeugt Klassenformeln als Konjunktionen von schwachen test-once-DGs. Dies ist effizient für die Berechnung von SRs, NRs und Robustheit.
• Algorithmus 3A: Erzeugt Klassenformeln als schwache test-once-DGs (direkt), was für die Berechnung von kontrastiven Erklärungen (CEs) notwendig ist.

C. Berechnung von Erklärungen und Robustheit

Sobald die traktbaren Formeln vorliegen:

• Robustheit: Wird über den kompletten Grund berechnet (Algorithmus 5). Es wird die minimale Länge der prime Implikanten (notwendige Gründe) bestimmt.
• Kürzeste Umkehrungen (Shortest Flips): Über den allgemeinen Grund werden allgemeine notwendige Gründe (GNRs) berechnet (Algorithmus 7). Diese garantieren, dass jede Verletzung dieser Gründe die Entscheidung tatsächlich umkehrt.

3. Schlüsselbeiträge

1. Effiziente Kompilierung: Ein neuer Algorithmus, der Random Forests in NNF-Schaltkreise kompiliert, der empirisch signifikant effizienter ist als bestehende Ansätze (z. B. basierend auf ADDs oder SAT-Encodings).
2. Traktable Repräsentation: Die Umwandlung dieser Schaltkreise in traktbare Entscheidungsgraphen, die die Berechnung von kompletten und allgemeinen Gründen in linearer Zeit zur Größe des Graphen ermöglichen.
3. Algorithmen für Robustheit und Umkehrung: Neue Algorithmen zur Berechnung der Robustheit einer Entscheidung und zur Identifizierung aller kürzesten Wege, um eine Entscheidung umzukehren (Shortest GNRs).
4. Umfassende Erklärungsgenerierung: Die Fähigkeit, alle hinreichenden Gründe, notwendigen Gründe und kontrastiven Erklärungen systematisch und effizient aufzulisten.

4. Ergebnisse (Empirische Evaluation)

Die Autoren testeten ihre Methoden auf einer Vielzahl von Datensätzen (UCI Repository, PMB) mit Random Forests unterschiedlicher Größe (bis zu 100 Bäume, teils bis zu 1000 Bäume in Tests).

• Kompilierungsgeschwindigkeit: Algorithmus 3 (NNF-Schaltkreise) ist deutlich schneller als vergleichbare Ansätze (z. B. ORD/ADD aus [32]). Die Kompilierungszeiten liegen im Bereich von Millisekunden bis wenigen Sekunden, selbst für komplexe Modelle.
• Größe der Schaltkreise: Die generierten NNF-Schaltkreise sind für die meisten Datensätze kleiner als die ADDs oder ORD-Graphen aus der Literatur.
• Effizienz der Erklärungsberechnung:
  • Die Enumeration von SRs und NRs erfolgt extrem schnell (oft < 0,1 Sekunden pro Instanz).
  • Die Berechnung der Robustheit und der kürzesten GNRs (Algorithmus 7) ist ebenfalls sehr effizient.
  • Die durchschnittliche Robustheit war in den getesteten Datensätzen sehr niedrig (oft < 2 Merkmale müssen geändert werden, um die Entscheidung zu kippen).
  • Die Anzahl der kürzesten GNRs pro Entscheidung war meist gering (< 10), was eine kompakte Darstellung aller Umkehrwege ermöglicht.
• Skalierbarkeit: Der Ansatz skaliert gut mit der Anzahl der Bäume im Random Forest.

5. Bedeutung und Fazit

Dieses Paper liefert einen fundamentalen Baustein für die formale XAI bei Random Forests.

• Formale Garantien: Im Gegensatz zu heuristischen Methoden bieten die vorgestellten Erklärungen mathematische Beweise für Hinreichendheit und Notwendigkeit.
• Effizienz: Durch die Nutzung von Sortier-Netzwerken und traktbaren Schaltkreisen wird die Berechnung komplexer Erklärungen (wie aller kürzesten Umkehrwege) praktisch durchführbar, was bisher oft als zu rechenintensiv galt.
• Anwendbarkeit: Die Methode deckt sowohl binäre als auch multiklassen Probleme ab und funktioniert mit diskreten und kontinuierlichen (diskretisierten) Merkmalen.

Zusammenfassend demonstriert die Arbeit, dass Random Forests nicht nur als „Blackbox" behandelt werden müssen, sondern dass ihre interne Logik effizient in eine Form übersetzt werden kann, die eine vollständige, formale und interpretierbare Analyse ihrer Entscheidungen ermöglicht.