Joint Distribution-Informed Shapley Values for Sparse Counterfactual Explanations

Die Arbeit stellt COLA vor, ein generisches Nachbearbeitungsframework, das mithilfe von Optimal Transport und Shapley-Werten bestehende kontrafaktische Erklärungen so verfeinert, dass sie mit 26–45 % weniger Merkmalsänderungen dieselbe Vorhersageänderung erreichen, während die theoretische Nähe zu den ursprünglichen Daten gewahrt bleibt.

Das Wesentliche

Das Grundproblem: Der übertriebe Ratschlag

Stellen Sie sich vor, Sie gehen zu einem Finanzberater, weil Sie einen Kredit beantragt haben, der abgelehnt wurde. Sie wollen wissen: „Was muss ich ändern, damit ich den Kredit bekomme?"

Ein herkömmlicher KI-System könnte Ihnen sagen:

„Um den Kredit zu bekommen, müssen Sie:

1. Ihr Einkommen um 5.000 € erhöhen,
2. Ihre Schulden tilgen,
3. Ihren Wohnort wechseln,
4. Ihren Beruf ändern,
5. Und ein neues Auto kaufen."

Das ist zwar technisch korrekt (wenn Sie das alles tun, bekommen Sie den Kredit), aber es ist unpraktisch und übertrieben. Sie können Ihren Wohnort oder Beruf nicht einfach so ändern. Ein guter Ratschlag sollte nur die wichtigsten, kleinsten Änderungen nennen, die zum Ziel führen.

Das ist genau das Problem, das dieses Paper mit der Methode COLA löst.

---

Die Lösung: COLA – Der sparsame Koch

COLA (Counterfactuals with Limited Actions) ist wie ein sehr sparsamer Koch, der aus einem riesigen, komplizierten Rezept (dem ursprünglichen KI-Vorschlag) nur die absolut notwendigen Zutaten herausfiltert.

1. Der Ausgangspunkt: Der „Übertreiber" (Der ursprüngliche KI-Ratschlag)

Zuerst nimmt COLA einen bestehenden Ratschlag von einer KI. Diese KI sagt oft: „Ändere alles!" (wie in unserem Beispiel oben). Das nennen die Autoren Counterfactuals (Gegenfakten). Das Problem: Diese Ratschläge sind oft zu lang und enthalten unnötige Änderungen.

2. Der Trick: Der perfekte Tanzpartner (Optimal Transport)

Stellen Sie sich vor, Sie haben eine Gruppe von Menschen (Ihre aktuelle Situation) und eine Gruppe von Menschen, die den Kredit bekommen haben (die Ziel-Situation).
Die alte Methode würde einfach zufällig jemanden aus Gruppe A mit jemandem aus Gruppe B vergleichen. Das führt zu chaotischen Ergebnissen.

COLA nutzt eine mathematische Methode namens Optimal Transport (Optimaler Transport).

• Die Analogie: Stellen Sie sich vor, Sie müssen Paare bilden, damit jeder aus Gruppe A den perfekten Partner aus Gruppe B findet, der ihm am ähnlichsten ist.
• Warum? Wenn Sie wissen, wer der genaue Gegenpart ist, können Sie viel präziser sagen: „Du musst nur diese eine Sache ändern, um wie dieser spezielle Partner zu werden."
• COLA berechnet diese perfekten Paare, um den Weg vom „Ich" zum „Ziel" so kurz wie möglich zu halten.

3. Der Detektiv: Shapley-Werte (Wer ist wirklich schuld?)

Jetzt haben wir die perfekten Paare. Aber welche der vielen Unterschiede zwischen den beiden sind eigentlich wichtig?
Hier kommt Shapley ins Spiel (eine Methode aus der Spieltheorie).

• Die Analogie: Stellen Sie sich vor, Sie und Ihr Partner haben ein gemeinsames Konto. Sie wollen herausfinden, wer wie viel zum Erfolg beigetragen hat.
• Die KI prüft: „Was passiert, wenn wir nur das Einkommen ändern? Was, wenn wir nur das Alter ändern?"
• COLA nutzt die perfekten Paare (aus Schritt 2), um diese Prüfung fair durchzuführen. Es identifiziert genau die wenigen Faktoren, die den Unterschied machen.

4. Das Ergebnis: Der sparsame Ratschlag

Am Ende gibt COLA Ihnen einen neuen Ratschlag.

• Alt: „Ändere 5 Dinge."
• Neu (mit COLA): „Ändere nur 1 oder 2 Dinge."

In den Experimenten des Papers hat COLA gezeigt, dass man oft nur 26 % bis 45 % der ursprünglichen Änderungen braucht, um das gleiche Ziel zu erreichen. Das ist wie wenn man statt eines ganzen Hauses nur ein Fenster reparieren muss, um den Raum heller zu machen.

---

Warum ist das wichtig?

1. Handlungsfähigkeit: Niemand kann 10 Dinge gleichzeitig ändern. COLA sagt Ihnen, was Sie wirklich tun können.
2. Fairness: Es verhindert, dass die KI Ihnen unmögliche Dinge vorschlägt (wie „Ändere dein Geburtsdatum").
3. Klarheit: Weniger Informationen bedeuten oft besseres Verständnis.

Zusammenfassung in einem Satz

COLA ist ein cleveres Werkzeug, das die ungenauen, übertriebenen Ratschläge einer KI nimmt, die besten Vergleiche zwischen Ihrer aktuellen Situation und dem Ziel findet und dann nur die allerwichtigsten, kleinsten Schritte herausfiltert, damit Sie Ihr Ziel erreichen können – ohne unnötigen Stress.

Es ist der Unterschied zwischen: „Packen Sie Ihren ganzen Koffer und ziehen Sie um!" und „Nehmen Sie nur diesen einen Schlüssel mit."

Technische Zusammenfassung

1. Problemstellung und Herausforderungen

Hintergrund:
Erklärbare Künstliche Intelligenz (XAI) ist essenziell für transparente und vertrauenswürdige Systeme. Zwei Hauptmethoden sind:

• Feature Attributions (FA): Methoden wie Shapley-Werte, die zeigen, wie stark Eingabemerkmale zur Vorhersage beitragen.
• Counterfactual Explanations (CE): Erklärungen, die aufzeigen, welche kleinen Änderungen an den Eingabedaten notwendig wären, um ein gewünschtes Ergebnis (z. B. eine andere Klassifikation) zu erreichen.

Das Kernproblem:
Bestehende CE-Methoden ändern oft zu viele Merkmale, um das Ziel zu erreichen. Dies reduziert die Klarheit und die Handlungsfähigkeit (Actionability) der Erklärung für den Nutzer. Umgekehrt liefern reine FA-Methoden oft keine konkreten Handlungsschritte.
Die zentrale Frage lautet: Wie kann man für eine gegebene (Gruppe von) Fakteninstanzen einen Aktionsplan entwickeln, der die geringstmögliche Anzahl von Merkmalsänderungen erfordert, um ein gewünschtes kontrafaktisches Ergebnis zu erzielen?

Herausforderungen:

1. Kein universeller Algorithmus: Es gibt keinen einzelnen CE-Algorithmus, der für alle Szenarien (individuell vs. gruppenbasiert, differenzierbare vs. nicht-differenzierbare Modelle) geeignet ist.
2. Modellunabhängigkeit: Die Lösung sollte keine starken Annahmen über das zugrunde liegende Modell (z. B. Differenzierbarkeit) treffen.
3. Inkohärenz zwischen FA und CE: Die bloße Anwendung von Feature-Importance (FA) auf CE ist oft irreführend. Die als „wichtig" eingestuften Merkmale führen nicht zwangsläufig zum effizientesten Pfad zum Ziel, da die Beziehung zwischen Fakten und kontrafaktischen Instanzen oft nicht korrekt abgebildet wird.

2. Methodik: Das COLA-Framework

Die Autoren stellen COLA (COunterfactuals with Limited Actions) vor, ein generisches, nachträgliches (post-hoc) Framework, das beliebige CE-Generatoren verfeinert, um sparsame Erklärungen zu erzeugen.

Kernkomponenten:

1. Optimaler Transport (OT) für das Kopplungsproblem:

   • Anstatt zufällige Baselines oder willkürliche Zuordnungen zu verwenden, nutzt COLA Optimal Transport, um eine optimale Kopplung (Joint Distribution) zwischen den Fakteninstanzen ($x$) und den kontrafaktischen Instanzen ($r$) zu berechnen.
   • Dies minimiert die Transportkosten (d. h. die Distanz zwischen $x$ und $r$) und löst das Problem der Ausrichtung (Alignment) zwischen Fakten und kontrafaktischen Beispielen, selbst wenn diese nicht explizit bekannt sind.

2. p-SHAP (Joint Distribution-Informed Shapley Values):

   • Basierend auf der durch OT ermittelten gemeinsamen Verteilung $p$ wird eine neue Shapley-Attributionsmethode namens p-SHAP definiert.
   • Im Gegensatz zu herkömmlichen Methoden (wie RB-SHAP oder CF-SHAP), die oft unabhängige Verteilungen annehmen, nutzt p-SHAP die optimale Kopplung, um den kausalen Effekt von Merkmalsänderungen präziser zu bewerten.
   • Theoretisch wird gezeigt, dass p-SHAP die obere Schranke der $W_1$-Divergenz (Wasserstein-Abstand) zwischen der aktuellen Vorhersage und dem Ziel minimiert.

3. Algorithmischer Ablauf (Algorithm 1):

   • Schritt 1: Ein beliebiger CE-Algorithmus ($ACE$) generiert zunächst kontrafaktische Instanzen $r$.
   • Schritt 2: Ein Algorithmus $A_{Prob}$ (basierend auf OT) berechnet die gemeinsame Verteilungsmatrix $p$ zwischen $x$ und $r$.
   • Schritt 3: p-SHAP berechnet die Shapley-Werte $\phi$ unter Verwendung von $p$. Diese Werte werden normalisiert, um eine Wahrscheinlichkeitsverteilung für die Auswahl von zu ändernden Merkmalen zu bilden.
   • Schritt 4: Ein Algorithmus $A_{Value}$ wählt basierend auf $p$ die Zielwerte für die Änderungen aus (z. B. den Wert des am besten passenden kontrafaktischen Beispiels).
   • Schritt 5: Basierend auf den Shapley-Werten werden nur die $C$ wichtigsten Merkmale ausgewählt und geändert, um die verfeinerte kontrafaktische Instanz $z$ zu erhalten.

Theoretische Garantien:

• Theorem 4.1: Unter der Annahme einer Lipschitz-Stetigkeit des Modells minimiert der durch OT gefundene Plan die obere Schranke der Divergenz zwischen der tatsächlichen Vorhersage und dem Ziel.
• Theorem 5.1: Die durch COLA verfeinerte Instanz $z$ ist garantiert nicht weiter von der Fakteninstanz $x$ entfernt als die ursprüngliche kontrafaktische Instanz $r$ (unter Verwendung der Frobenius-Norm).

3. Wichtige Beiträge

• Erster systematischer Ansatz: COLA ist die erste Methode, die das Problem der minimalen Aktionen in CE systematisch löst, ohne sich auf einen spezifischen CE-Algorithmus oder ein spezifisches Modell zu beschränken.
• p-SHAP: Einführung einer neuen Shapley-Variante, die die gemeinsame Verteilung via Optimal Transport nutzt, um die Ausrichtung zwischen Fakten und kontrafaktischen Beispielen zu verbessern.
• Modell- und Generator-Unabhängigkeit: Das Framework funktioniert mit beliebigen Black-Box-Modellen und beliebigen CE-Generatoren (z. B. DiCE, AReS, KNN-basierte Methoden).
• Theoretische Fundierung: Beweis, dass die OT-basierte Kopplung die Effizienz der Merkmalsauswahl theoretisch optimiert und die Distanz zur Fakteninstanz nicht erhöht.

4. Experimentelle Ergebnisse

Die Evaluation erfolgte auf 4 Datensätzen (HELOC, German Credit, Hotel Bookings, COMPAS), mit 12 verschiedenen Modellen (von linearen Modellen bis zu Deep Neural Networks) und 5 verschiedenen CE-Generatoren.

• Reduktion der Aktionen: COLA erreicht das gleiche kontrafaktische Ziel mit nur 26–45 % der ursprünglichen Merkmalsänderungen. In einigen Szenarien (80 % Effekt) sogar nur mit 13–25 %.
• Überlegenheit von p-SHAP: Die Methode CF-pOT (COLA mit p-SHAP und OT-Kopplung) übertrifft alle anderen Shapley-Varianten (wie RB-SHAP, CF-SHAP mit zufälliger Zuordnung oder Uniform-Verteilung) signifikant.
  • Erkenntnis: Die reine Nutzung kontrafaktischer Daten reicht nicht aus; die korrekte Zuordnung (Alignment) via OT ist entscheidend.
• Near-Optimalität: Auf einem kleinen Benchmark (German Credit-Datensatz) wurde COLA mit einer Mixed-Integer Linear Programming (MILP)-Optimierung verglichen, die als theoretisches Optimum dient. COLA erreicht nahezu optimale Ergebnisse, wobei der Unterschied gering ist.
• Robustheit: Die Ergebnisse waren über verschiedene Divergenzfunktionen (OT, MMD, Mittelwertdifferenz) und Modelltypen hinweg konsistent.

5. Bedeutung und Fazit

Das Paper adressiert ein kritisches Defizit in der aktuellen XAI-Forschung: Die Lücke zwischen theoretisch wichtigen Merkmalen und praktisch umsetzbaren, minimalen Änderungen.

• Praktische Relevanz: Durch die drastische Reduktion der notwendigen Änderungen werden Erklärungen für Endnutzer (z. B. bei Kreditanträgen oder medizinischen Diagnosen) viel handlungsorientierter und akzeptabler.
• Vermeidung von Bias: Da weniger Merkmale geändert werden müssen, sinkt das Risiko, sensible oder unveränderliche Attribute (wie Geschlecht oder Alter) fälschlicherweise als Änderungspfad vorzuschlagen.
• Generischer Ansatz: Da COLA als Post-Hoc-Framework agiert, kann es sofort auf bestehende CE-Systeme angewendet werden, um deren Ausgabe zu optimieren, ohne die zugrunde liegenden Modelle neu trainieren zu müssen.

Zusammenfassend bietet COLA einen theoretisch fundierten und empirisch bewährten Weg, um kontrafaktische Erklärungen von „zu viel Rauschen" zu befreien und sie in präzise, kosteneffiziente Handlungsempfehlungen zu verwandeln.