P$^2$CE: Model-Agnostic Plausible Pareto-Optimal Counterfactual Explanations

Das Papier stellt P$^2$CE vor, einen modellagnostischen Algorithmus, der durch die Kombination einer Isolation Forest zur Einhaltung der Datenverteilung und SHAP-Werten zur Recheneffizienz diverse, plausible und Pareto-optimale kontrafaktische Erklärungen erzeugt und damit bestehende Methoden in Bezug auf Lösungsqualität und Geschwindigkeit übertrifft.

Das Wesentliche

Stellen Sie sich vor, Sie beantragen einen Kredit, einen Job oder eine Hypothek, und der Computer sagt „Nein“. Natürlicherweise wollen Sie wissen: „Was müsste ich in meinem Leben ändern, um ein ‚Ja‘ zu bekommen?“

Hier kommen kontrafaktische Erklärungen ins Spiel. Sie sind wie eine „Was-wäre-wenn“-Karte, die Ihnen die kleinsten, realistischsten Schritte aufzeigt, um eine Ablehnung in eine Annahme umzuwandeln.

Die bestehenden Karten haben jedoch zwei große Probleme:

1. Sie schlagen unmögliche Änderungen vor: Wie zum Beispiel: „Erhöhen Sie Ihr Einkommen um 1000 %“. Das ist nicht hilfreich.
2. Sie schlagen seltsame, unrealistische Änderungen vor: Wie zum Beispiel einem 20-jährigen Studenten plötzlich das Investmentportfolio eines 60-jährigen Milliardärs zu geben. Das ist mathematisch zwar möglich, passt aber nicht in die reale Welt.

Die Autoren dieser Arbeit führen ein neues Werkzeug namens P2CE (Plausible Pareto-Optimal Counterfactual Explanations) ein. Betrachten Sie P2CE als einen intelligenten, realistischen Reiseverkehrsdienst, der Ihnen hilft, die beste Route zu Ihrem Ziel zu finden, ohne dass Sie im Land der Fantasie verloren gehen.

So funktioniert P2CE, erklärt anhand einfacher Analogien:

1. Der „Realitätscheck“ (Der Plausibilitätsfilter)

Stellen Sie sich vor, Sie suchen ein Haus. Ein schlechter Reiseverkehrsdienst könnte sagen: „Kaufen Sie einfach ein Schloss auf dem Mond!“ Es ist ein Haus und es ist eine Veränderung, aber es ist unmöglich.

• Alte Methoden schlagen oft solche „Schlösser auf dem Mond“ vor, weil sie nur auf den mathematischen Abstand zwischen Ihrer aktuellen Situation und dem Ziel schauen.
• P2CE verwendet einen speziellen „Realitätsdetektor“ (einen sogenannten Isolation Forest). Er betrachtet die Nachbarschaft echter Daten. Wenn ein Vorschlag ein „Ausreißer“ ist (wie ein 20-Jähriger mit dem Portfolio eines Milliardärs), markiert der Realitätsdetektor dies als „Nicht real“ und verwirft ihn. P2CE gibt Ihnen nur Vorschläge, die natürlich in die reale Welt passen.

2. Der „Beste-Angebot“-Finder (Das Pareto-optimale Konzept)

Manchmal müssen Sie zwischen zwei guten Optionen wählen:

• Option A: Ändern Sie Ihren Jobtitel (große Änderung, aber nur eine Sache zu tun).
• Option B: Sparen Sie etwas mehr Geld, zahlen Sie einen kleinen Schuldenbetrag zurück und absolvieren Sie einen kurzen Kurs (drei kleine Änderungen).

Welche ist besser? Das hängt von Ihnen ab.

• Alte Methoden zwingen Sie oft dazu, sich nur für eine einzige „beste“ Antwort zu entscheiden, indem sie diese Faktoren in einem einzigen Wert kombinieren, was Ihre persönliche Präferenz übersehen kann.
• P2CE fungiert wie ein Menü aus optimalen Entscheidungen. Es liefert Ihnen eine Liste von „Pareto-optimalen“ Optionen. Das bedeutet: „Hier ist eine Liste der bestmöglichen Kompromisse. Sie können nicht in einem Bereich (wie dem Sparen von Zeit) ein besseres Ergebnis erzielen, ohne den anderen Bereich (wie den Aufwand) zu verschlechtern.“ Es lässt Sie entscheiden, welcher Kompromiss sich richtig für Ihr Leben anfühlt.

3. Der „Black-Box“-Navigator (Modell-agnostisch)

Viele KI-Systeme sind „Black Boxes“ – wir wissen nicht, wie sie im Inneren denken, sondern nur, was sie ausgeben.

• Alte Methoden scheitern oft, wenn die „Black Box“ zu komplex ist (wie ein tiefes neuronales Netzwerk). Sie bleiben stecken oder brauchen ewig für die Berechnung.
• P2CE ist ein universeller Navigator. Es ist ihm egal, wie die „Black Box“ im Inneren funktioniert. Es nutzt eine clevere Abkürzung namens SHAP-Werte (denken Sie an diese als eine Art „Bewertungsbogen“, der dem Algorithmus sagt, welche Merkmale am wichtigsten sind), um den besten Weg zu erraten, ohne die Box öffnen zu müssen. Dies macht es schnell und kompatibel mit jeder Art von KI-Modell.

Die Ergebnisse: Warum es wichtig ist

Die Autoren haben P2CE mit anderen populären Werkzeugen anhand von Realdaten (wie Kreditwürdigkeit und Einkommensdaten) getestet.

• Geschwindigkeit: Es fand gute Antworten viel schneller als die älteren, starreren Methoden, insbesondere bei komplexen KI-Modellen.
• Qualität: Es produzierte weitaig weniger „unrealistische“ Vorschläge (Ausreißer) als die Konkurrenz.
• Vielfalt: Es bot den Nutzern eine vielfältige Auswahl an Möglichkeiten statt nur einer erzwungenen Antwort.

Zusammenfassend: P2CE ist ein neuer Weg, KI-Entscheidungen zu erklären, der sicherstellt, dass der Rat, den Sie erhalten, realistisch ist (zu Ihrem Leben passt), effizient ist (nicht ewig zur Berechnung braucht) und flexibel ist (Ihnen ein Menü der besten Kompromisse zur Auswahl gibt). Es verwandelt ein verwirrendes „Nein“ in ein klares, handlungsorientiertes und glaubwürdiges „Hier ist der Weg, wie Sie ein Ja bekommen können“.

Technische Zusammenfassung

Technisches Resümee: P2CE – Modellagnostische, plausible Pareto-optimale kontrafaktische Erklärungen

Problemstellung

Der zunehmende Einsatz von maschinellem Lernen in hochsensiblen Bereichen (z. B. Kreditwürdigkeitsprüfung, Einstellungsprozesse, medizinische Diagnose) macht Transparenz und Fairness erforderlich. Kontrafaktische Erklärungen (Counterfactual Explanations, CEs) adressieren dies, indem sie minimale Änderungen an den Eingabemerkmalen ($x \to x'$) vorschlagen, die das Ergebnis eines Modells von einem unerwünschten zu einem gewünschten Ausgang ändern würden. Bestehende Methoden stehen jedoch vor drei kritischen Herausforderungen:

1. Plausibilität: Viele Algorithmen generieren Lösungen, die mathematisch nah am Input liegen, aber außerhalb der natürlichen Datenverteilung (Ausreißer) liegen, was sie für Einzelpersonen unrealistisch macht.
2. Machbarkeitstraditionen (Feasibility Trade-offs): Es gibt keine einzelne Metrik für „Machbarkeit“. Nutzer bevorzugen möglicherweise kleine Änderungen an vielen Merkmalen oder moderate Änderungen an wenigen Merkmalen. Die Optimierung eines Einzelziels kann diese vielfältigen Präferenzen nicht erfassen.
3. Modellagnostik und Effizienz: Während einige Methoden modellagnostisch sind, kämpfen sie oft mit der Recheneffizienz oder stützen sich auf Annahmen (wie Modell-Monotonie), die für komplexe nicht-lineare Modelle (z. B. Neuronale Netze, SVMs) nicht gelten.

Methodik

Die Autoren schlagen P2CE vor, einen Algorithmus, der darauf ausgelegt ist, plausible Pareto-optimale kontrafaktische Erklärungen zu generieren. Der Ansatz kombet eine Branch-and-Bound-Suchstrategie mit zwei zentralen Innovationen, um Plausibilität und Effizienz über jedes Black-Box-Modell hinweg zu gewährleisten.

1. Suchstrategie und Multi-Objective Optimization

P2CE durchsucht ein diskretisiertes Gitter möglicher Merkmalsänderungen ($A = A^{(1)} \times \dots \times A^{(d)}$), um eine Menge von Aktionen $a$ zu finden, sodass $f(x+a) \geq \tau$ gilt. Es optimiert gleichzeitig mehrere Ziele:

• Durchschnittliche kontinuierliche Distanz ($c_1$): Die normalisierte durchschnittliche Magnitude der Änderungen in numerischen Merkmalen.
• Maximale kontinuierliche Distanz ($c_2$): Die maximale Magnitude der Änderung in einem einzelnen numerischen Merkmal.
• Anzahl der Änderungen ($c_3$): Die Anzahl der geänderten Merkmale (Sparsity/Dünnbesetztheit).

Der Algorithmus liefert eine Pareto-optimale Menge, die sicherstellt, dass keine andere Lösung existiert, die in allen Zielen besser oder gleichwertig ist.

2. Sicherstellung der Plausibilität durch Ausreißererkennung

Um die Generierung von Ausreißern (Lösungen außerhalb der Datenverteilung) zu verhindern, integriert P2CE einen Isolation Forest Ausreißerdetektor ($u$).

• Während der Suche wird, wann immer eine Kandidatenlösung $x+a$ gefunden wird, $u(x+a)$ evaluiert.
• Wenn $u(x+a)$ einen Ausreißer anzeigt, wird die Lösung verworfen.
• Effizienzgewinn: P2CE nutzt die Fähigkeit des Isolation Forest, mit fehlenden Werten umzugehen. Wenn eine Teilchenlösung (mit einigen noch undefinierten Merkmalen) bereits als Ausreißer klassifiziert wird, beschneidet der Algorithmus den gesamten Zweig des Suchbaums, um unnötige Berechnungen zu vermeiden.

3. Modellagnostische Branch-and-Bound-Beschneidung

Um die Recheneffizienz ohne die Annahme von Modell-Monotonie (was Methoden wie MAPOCAM einschränkt) aufrechtzuerhalten, schätzt P2CE die maximale mögliche Vorhersage ($f_a$), die von einer Teilaktion $a$ aus erreichbar ist.

• SHAP-basierte Schätzung: Der Algorithmus nutzt die additive Eigenschaft von SHAP-Werten: $f(x) = E[f(x)] + \sum \phi_i$.
• Er berechnet eine obere Schranke für die Vorhersage, indem er das „Best-Case“-Szenario für die verbleibenden offenen Merkmale (diejenigen, die im Suchprozess noch nicht fixiert wurden) annimmt.
• Die Schranke ist formuliert als:
  $$\max f(x+\tilde{a}) \leq f(x) - \sum_{i \in O_k} \phi_i(x) + \sum_{i \in O_k} \bar{\phi}_i + R(x, O_k)$$
  Wobei $O_k$ die $k$ Merkmale mit der höchsten potenziellen Attribution darstellt, $\bar{\phi}_i$ die maximale mögliche Attribution für Merkmal $i$ ist und $R$ ein Residuen-Term ist.
• Wenn diese obere Schranke unter dem Entscheidungsschwellenwert $\tau$ liegt, wird der Zweig abgeschnitten. Dies ermöglicht es P2CE, effizient mit nicht-monotonen Modellen wie Neuronalen Netzen zu arbeiten.

Zentrale Beiträge

1. P2CE-Algorithmus: Ein neuartiger, modellagnostischer Algorithmus, der Pareto-optimale kontrafaktische Erklärungen generiert und gleichzeitig die Plausibilität der Datenverteilung strikt durch Ausreißererkennung erzwingt.
2. Exploration der SHAP-Eigenschaft: Die Einführung einer Methode zur Nutzung von SHAP-Werten zur Schätzung maximaler Vorhersagen in einem Branch-and-Bound-Kontext, wodurch die Monotonie-Beschränkung aufgehoben wird, die bisherigen State-of-the-Art-Methoden einschränkte.
3. Umfassende Evaluierung: Eine umfangreiche empirische Studie über drei Datensätze (German Credit, Taiwan Credit, Adult) und drei Klassifikatoren (Logistische Regression, LightGBM, MLP), die P2CE mit MAPOCAM, DiCE und NICE vergleicht.
4. Open Source: Die Veröffentlichung der Implementierung zur Förderung der Reproduzierbarkeit.

Experimentelle Ergebnisse

Die Evaluierung konzentrierte sich auf die Lösungsqualität (Hypervolumen der Pareto-Front), Plausibilität (Prozentsatz der Ausreißer) und Recheneffizienz.

• Plausibilität: P2CE generierte konsistent signifikant weniger Ausreißer-Lösungen als die Wettbewerber. Beispielsweise produzierte P2CE beim Adult-Datensatz mit einem MLP nur 11 % Ausreißer, während DiCE 87 % und MAPOCAM 58 % erzeugte. In einigen Fällen schlugen DiCE unmögliche Szenarien vor (z. B. 97 Arbeitsstunden pro Woche).
• Lösungsqualität: P2CE erreichte Hypervolumen-Scores, die mit MAPOCAM (dem theoretischen Goldstandard für Pareto-Optimalität) vergleichbar waren, und übertraf DiCE und NICE deutlich. Während MAPOCAM gelegentlich etwas höhere Hypervolumina erreichte, geschah dies um den Preis einer extrem hohen Rechenkosten.
• Effizienz: P2CE demonstrierte eine überlegene Recheneffizienz, insbesondere bei komplexen nicht-linearen Modellen.
  • Beim Taiwan-Datensatz mit einem MLP dauerte MAPOCAM im Durchschnitt 118,5 Sekunden, während P2CE 0,81 Sekunden benötigte.
  • Beim Adult-Datensatz mit einem MLP dauerte MAPOCAM 6,24 Sekunden, während P2CE 2,34 Sekunden benötigte.
  • P2CE war langsamer als DiCE und NICE in Bezug auf die reine Zeit, bot aber die entscheidende Garantie der Pareto-Optimalität und Plausibilität, die den schnelleren Methoden fehlte.

Bedeutung und Ansprüche

Das Paper positioniert P2CE als praktische Lösung für reale Anwendungen, in denen kontrafaktische Erklärungen sowohl handlungsorientiert (für den Nutzer machbar) als auch plausibel (konsistent mit realen Daten) sein müssen.

Die Autoren behaupten, dass P2CE erfolgreich die Lücke zwischen theoretischer Optimalität und praktischem Nutzen schließt. Durch die Sicherstellung, dass Lösungen „Inlier“ sind, verhindert der Algorithmus die Generierung irreführender Ratschläge (z. B. einem Nutzer vorzuschlagen, sein Einkommen um 1000 % zu steigern oder unmögliche Arbeitsstunden zu leisten). Darüber hinaus ermöglicht die Nutzung von SHAP-Werten zur Beschneidung die Erweiterung der Fähigkeit zur Generierung optimaler Kontrafaktika auf jedes Black-Box-Modell und überwindet damit die Einschränkungen früherer Methoden, die auf monotone oder spezifische Modelltypen beschränkt waren.

Die Arbeit kommt zu dem Schluss, dass P2CE durch die Bereitstellung eines vielfältigen Sets an hochwertigen, plausiblen Trade-offs ohne die Notwendigkeit modellspezifischer Anpassungen eine schnellere und fundiertere Entscheidungsfindung in realen Anwendungen ermöglicht.

Limitationen und zukünftige Arbeit

Die Autoren räumen zwei primäre Limitationen ein:

1. SHAP-Abhängigkeit: Die Effizienz der Beschneidungsstrategie beruht auf SHAP-Approximationen. Die Berechnung exakter Shapley-Werte ist rechenintensiv (exponentiell zur Anzahl der Merkmale), wobei Approximationen verwendet werden. Fehler in diesen Approximationen könnten theoretisch die Beschneidung beeinflussen, obwohl empirische Ergebnisse zeigen, dass die Auswirkungen im Vergleich zu den Geschwindigkeitsgewinnen minimal sind.
2. Diskretisiertes Gitter: Die Suche ist auf ein diskretes Gitter beschränkt. Während dies für die meisten Anwendungen praktisch ist (z. B. eine Erhöhung des Einkommens um 1.000 Dollar gegenüber 998 Dollar ist funktional ähnlich), erhöht eine extrem feine Granularität die Suchzeit. Die Autoren schlagen zukünftige Arbeiten zu adaptiven Gittern vor, die die Granularität basierend auf der Merkmalsauswirkung anpassen, potenziell geleitet durch SHм-Werte.