🤖 AI

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

Dieses Paper führt effiziente Algorithmen zur Berechnung asymmetrischer Shapley-Werte unter Ausnutzung kausaler Graphen ein, wobei es zeigt, dass eine exakte Berechnung für gewurzelte gerichtete Bäume in Polynomialzeit möglich ist, und schlägt eine einheitliche Stichproben-basierte Approximationsmethode für beliebige kausale DAGs vor, um die #P-Härte der Standardberechnung von Shapley-Werten zu überwinden.

Ursprüngliche Autoren: Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

Veröffentlicht 2026-06-25

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben ein Team von Spielern (Features), die zusammenarbeiten, um ein Spiel zu gewinnen (eine Vorhersage zu treffen). Sie möchten genau wissen, wie viel Anerkennung jeder einzelne Spieler für den Sieg verdient. In der Welt der KI wird dies als Erklärbarkeit bezeichnet.

Die bekannteste Methode hierfür sind die Shapley-Werte. Denken Sie an einen fairen Schiedsrichter, der sich jede mögliche Reihenfolge ansieht, in der die Spieler in das Spiel eingetreten sein könnten. Wenn Spieler A als Erster, Zweiter oder Letzter eintritt, berechnet der Schiedsrichter, wie sehr sich die Punktzahl des Teams durch ihn verändert hat. Der endgültige Wert für Spieler A ist der Durchschnitt all dieser Veränderungen.

Das Problem mit der alten Methode
Das Problem ist, dass die Berechnung für jede einzelne mögliche Reihenfolge ein Albtraum ist. Wenn Sie 20 Spieler haben, gibt es Milliarden von Reihenfolgen, die überprüft werden müssten. Für komplexe KI-Modelle ist diese Berechnung so schwierig, dass sie praktisch unmöglich exakt durchzuführen ist.

Zudem behandelt die alte Methode alle Spieler als gleichwertig. Wenn Spieler B eine Kopie von Spieler A ist, erhält er denselben Wert. Aber im echten Leben kann es vorkommen, dass ein Spieler die Ursache dafür ist, dass ein anderer handelt. Wenn Spieler A verursacht, dass Spieler B sich bewegt, dann ist Spieler A der wahre Chef. Die alte Methode übersieht diese „Ursache-Wirkungs-Beziehung“.

Die neue Lösung: Asymmetrische Shapley-Werte (ASV)
Dieses Paper stellt einen klügeren Schiedsrichter vor: die Asymmetrischen Shapley-Werte (ASV). Anstatt jede mögliche Reihenfolge zu betrachten, schaut dieser Schiedsrichter nur auf Reihenfolgen, die gemäß einer kausalen Karte (einem Diagramm, das zeigt, wer wen verursacht) Sinn ergeben.

Die Analogie: Stellen Sie sich eine Fließbandfertigung in einer Fabrik vor. Man kann ein Auto nicht lackieren, bevor man den Rahmen gebaut hat. Die kausale Karte besagt: „Erst der Rahmen, dann die Farbe.“ Der ASV-Schiedsrichter ignoriert jede Reihenfolge, in der jemand versucht zu lackieren, bevor der Rahmen gebaut wurde. Er zählt nur die logischen Ursache-Wirkungs-Reihenfolgen.
Der Vorteil: Dies liefert eine ehrlichere Erklärung darüber, wer tatsächlich das Ergebnis verursacht hat. Zudem macht es die Mathematik – überraschenderweise – in einigen Fällen einfacher, in denen die alte Methode unmöglich war.

Wie sie es schnell gemacht haben (Die magischen Tricks)
Selbst mit der kausalen Karte kann das Überprüfen jeder gültigen Reihenfolge immer noch zu langsam sein. Die Autoren haben zwei clevere Tricks entwickelt, um dies zu beschleunigen:

Der „Gruppierungs“-Trick (Äquivalenzklassen):
Stellen Sie sich vor, Sie zählen, auf wie viele Arten Menschen sich aufreihen können. Sie stellen fest, dass es für den Zweck der Berechnung keine Rolle spielt, ob zwei Personen den Platz tauschen, wenn beide nach dem Hauptchef stehen. Sie gehören zur selben „Gruppe“.
Die Autoren haben einen Weg gefunden, tausende ähnlicher Reihenfolgen in einzelne „Eimer“ (genannt Äquivalenzklassen) zusammenzufassen. Anstatt 1.000.000 Reihenfolgen zu prüfen, müssen sie vielleicht nur 500 Gruppen prüfen. Dies verwandelt eine unmögliche Aufgabe in eine schnelle.
Der „Sampling“-Trick (Schätzen mit einer Stichprobe):
Wenn die Karte zu unordentlich ist, um sie ordentlich zu gruppieren, verwenden sie eine Sampling-Methode. Anstatt jede gültige Reihenfolge zu prüfen, wählen sie zufällig ein paar hundert Reihenfolgen aus, die den Regeln folgen, und berechnen den Durchschnitt.

Die Analogie: Anstatt jedes einzelne Reiskorn in einem riesigen Topf zu probieren, um zu sehen, ob er salzig ist, nehmen Sie einen Löffel aus verschiedenen Stellen. Wenn die Löffel salzig schmecken, wissen Sie, dass der ganze Topf salzig ist. Das Paper zeigt, dass diese „Löffel“-Methode schnell ist und eine sehr gute Schätzung liefert.

Was sie getestet haben
Die Autoren haben diese Ideen auf reale Datenstrukturen (wie Netzwerke, die Krebs oder die kindliche Entwicklung vorhersagen) und künstlich erzeugte Baumstrukturen angewendet.

Sie fanden heraus, dass ihre „Gruppierungs“-Methode für baumartige Strukturen unglaublich schnell ist und die Arbeit im Vergleich zur alten Methode um Millionen von Faktoren reduziert.
Für unordentlichere Strukturen war ihre „Sampling“-Methode schnell und genau genug, um nützlich zu sein.

Das Fazit
Dieses Paper beweist, dass wir KI-Modelle genauer erklären und schneller, indem wir die „Ursache-Wirkungs“-Regeln der Daten respektieren. Sie haben gezeigt, dass für bestimmte Arten von Daten eine Methode, die zuvor unmöglich exakt zu berechnen war, nun schnell durchgeführt werden kann, und dass für andere eine schnelle, genaue Schätzung leicht zu erreichen ist.

Technisches Resümee: Jenseits von Shapley: Effiziente Berechnung asymmetrischer Shapley-Werte

Problemstellung

Die Arbeit adressiert die rechnerischen und interpretierbarkeitstechnischen Herausforderungen im Zusammenhang mit der Merkmalsattribution in der erklärbaren KI (Explainable AI, XAI). Während Shapley-Werte (und deren maschinelle Lern-Instanziierung, SHAP) eine theoretisch fundierte Methode zur Verteilung der Vorhersage eines Modells auf die Eingangsmerkmale bieten, leiden sie unter zwei primären Einschränkungen:

Rechentechnische Unbehandbarkeit: Die exakte Berechnung von Shapley-Werten ist oft #P-hart, insbesondere bei expressiven Modellen (z. B. neuronalen Netzen) oder wenn die zugrunde liegende Datenverteilung komplex ist (z. B. Naive-Bayes-Verteilungen).
Defizite in der Interpretierbarkeit: Standard-Shapley-Werte behandeln alle Merkmale symmetrisch. Dies versäumt es, kausale Beziehungen zu erfassen, was dazu führen kann, dass einer Ursache und ihrer deterministischen Wirkung die gleiche Bedeutung beigemessen wird, wodurch der wahre datengenerierende Prozess verschleiert wird.

Um das zweite Problem anzugehen, wurden Asymmetrische Shapley-Werte (ASV) vorgeschlagen, welche die Berechnung auf Permutationen von Merkmalen einschränken, die einen gegebenen kausalen Graphen (einen gerichteten azyklischen Graphen oder DAG) respektieren. Die vorliegende Arbeit untersucht, ob die Einbeziehung kausaler Beschränkungen die Berechnung von Attributionswerten in spezifischen Kontexten tatsächlich handhabbarer als die Standard-Shapley-Werte machen kann.

Methodik

Die Autoren schlagen eine Suite von Algorithmen vor, um ASV exakt und approximativ zu berechnen, indem sie die Struktur des kausalen Graphen und die zugrunde liegende Wahrscheinlichkeitsverteilung (modelliert als Bayessches Netz) nutzen.

1. Theoretische Analyse der Handhabbarkeit

Die Autoren stellen ein theoretisches Ergebnis bezüglich der Komplexität von ASV unter Naive-Bayes-Verteilungen auf. Sie beweisen, dass während die Berechnung von Standard-Shapley-Werten für bestimmte Modellfamilien unter Naive-Bayes-Verteilungen unhandlich ist, die Berechnung von ASV für dieselben Familien polynomiell handhabbar ist, sofern der für ASV verwendete kausale Graph identisch mit der Naive-Bayes-Netzstruktur ist. Dies deutet darauf hin, dass die durch die Verteilung auferlegten kausalen Beschränkungen Symmetrien aufbrechen können, die das Problem andernfalls schwierig machen würden.

2. Exakte Berechnung via Äquivalenzklassen

Um die Handhabbarkeit auf allgemeinere kausale Strukturen, speziell wurzelnde gerichtete Bäume, auszuweiten, führen die Autoren eine Methode zur Reduktion des Suchraums der Permutationen ein:

Äquivalenzklassen: Sie definieren eine Äquivalenzrelation über der Menge der topologischen Ordnungen des kausalen Graphen. Zwei Ordnungen sind in Bezug auf ein Merkmal $x$ äquivalent, wenn die Menge der vor $x$ liegenden Merkmale in beiden Ordnungen identisch ist.
Algorithmus: Anstatt durch alle topologischen Ordnungen zu iterieren (was exponentiell sein kann), berechnet der Algorithmus die Menge der Äquivalenzklassen ( $\Lambda_x^C$ ) und die Größe jeder Klasse. Der ASV wird dann berechnet, indem die marginalen Beiträge gewichtet nach der Größe jeder Äquivalenzklasse summiert werden.
Komplexität: Für wurzelnde gerichtete Bäume ist die Anzahl der Äquivalenzklassen durch $h \cdot l + 1$ beschränkt (wobei $h$ die Tiefe und $l$ die Anzahl der Blätter ist). Die Autoren stellen einen polynomiellen Algorithmus (in Bezug auf die Anzahl der Äquivalenzklassen) bereit, um diese Klassen und deren Größen zu berechnen.

3. Approximative Berechnung via Sampling

Für beliebige kausale DAGs, in denen eine exakte Berechnung unpraktikabel sein kann, schlagen die Autoren ein Sampling-basiertes Approximationsschema vor.

Sampling topologischer Ordnungen: Die Methode beruht auf dem gleichmäßigen Zufallssampling von topologischen Ordnungen. Die Autoren implementieren zwei Ansätze:
1. Einen rekursiven Zählalgorithmus für Polytrees (Graphen mit höchstens einem Pfad zwischen zwei beliebigen Knoten), der topologische Ordnungen zählt, um Quellknoten korrekt zu gewichten.
2. Einen Random-Walk-basierten Algorithmus (basierend auf Bubley & Dyer, 1999) für allgemeine DAGs.
Fehlergrenzen: Sie formalisieren, dass wenn der topologische Ordnungs-Sampler $\epsilon_{samp}$ -nah an der Gleichverteilung ist und die Charakteristische Funktion (erwarteter Modellwert) mit einem Fehler $\epsilon_{\nu}$ approximiert wird, die resultierende ASV-Schätzung einen additiven Fehler von $O(\epsilon_{samp} + \epsilon_{\nu})$ aufweist.

Hauptergebnisse

Die Autoren evaluierten ihre Methoden an realen Bayesschen Netzen (Cancer, Child) und künstlichen Strukturen (balancierte Bäume, Naive Bayes, multiple Pfade).

Reduktion des Suchraums: Der Äquivalenzklassen-Ansatz reduziert die Rechenlast im Vergleich zur Enumeration aller topologischen Ordnungen erheblich. Im "Child"-Netzwerk betrug die Anzahl der topologischen Ordnungen $\approx 7,41 \times 10^{11}$ , während die Anzahl der Äquivalenzklassen im Durchschnitt nur $\approx 2003$ betrug.
Laufzeiteffizienz:
- Die Berechnung von Äquivalenzklassen für praktische Graphgrößen dauerte weniger als eine Sekunde.
- Die Laufzeit des exakten Algorithmus korrelierte stark mit der Anzahl der Äquivalenzklassen, wodurch die Vorberechnung der Klassenzählungen als Prädiktor für die Rechenkosten dienen konnte.
- Die Enumeration aller topologischen Ordnungen wurde für größere Graphen unpraktikabel, während die Äquivalenzklassen-Methode handhabbar blieb.
Sampling-Leistung:
- Der benutzerdefinierte rekursive Sampling-Algorithmus für Polytrees war effizient, mit einer nicht-linearen Skalierung relativ zur Anzahl der Samples aufgrund der parallelen Kandidatengenerierung.
- Die Verwendung von 1.000 Samples ergab einen durchschnittlichen relativen Fehler von etwa 8 % für die ASV-Werte. Der Fehler war bei größeren ASV-Werten niedriger und höher bei sehr kleinen wahren Werten.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass ASV ein lebensfähiger und potenziell überlegener Rahmen für die Erklärbarkeit ist, wenn die kausale Struktur relevant ist, da er Abhängigkeiten erfasst, die der Standard-SHAP übersieht. Der primäre Beitrag besteht darin, zu zeigen, dass kausale Beschränkungen ein unhandliches Problem in ein handhabbares Problem transformieren können (z. B. Entscheidungsbäume unter Naive-Bayes-Verteilungen).

Die Autoren betonen, dass die Skalierbarkeit von ASV stark von der Topologie des kausalen Graphen abhängt:

Für wurzelnde gerichtete Bäume und Polytrees ist eine exakte Berechnung via Äquivalenzklassen machbar.
Für dichte oder große DAGs kann die Anzahl der Äquivalenzklassen dennoch zu groß werden, was die Verwendung von Sampling-basierten Approximationen erforderlich macht.

Die Arbeit schließt mit dem Schluss, dass ASV eine vielversprechende Richtung für XAI darstellt, vorausgesetzt, der kausale Graph ist bekannt und die Graphstruktur ermöglicht eine effiziente Enumeration oder das Sampling topologischer Ordnungen. Als zukünftige Arbeit wird vorgeschlagen, die exakten Algorithmen auf breitere Klassen von Graphen (z. B. allgemeine Polytrees) zu generalisieren und die Sampling-Mechanismen zu optimieren.