🤖 machine learning

Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks

Dieser Beitrag stellt einen neuartigen Algorithmus vor, der Techniken zur Verifikation neuronaler Netze nutzt, um nachweisbare, beliebig enge Schranken für exakte Shapley-Werte zu berechnen, wodurch eine skalierbare und präzise SHAP-Berechnung für neuronale Netze mit deutlich größeren Suchräumen als bei bestehenden exakten Methoden ermöglicht wird.

Ursprüngliche Autoren: David Boetius, Shahaf Bassan, Guy Katz, Stefan Leue, Tobias Sutter

Veröffentlicht 2026-05-26

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: David Boetius, Shahaf Bassan, Guy Katz, Stefan Leue, Tobias Sutter

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 eine sehr komplexe, Black-Box-Maschine (ein neuronales Netz), die Entscheidungen trifft, wie etwa die Diagnose einer Krankheit oder die Bewilligung eines Darlehens. Sie möchten exakt wissen, welche Eingangsmerkmale (wie Alter, Einkommen oder Blutdruck) dazu geführt haben, dass die Maschine diese spezifische Entscheidung getroffen hat.

Der Standardweg, um diese Frage zu beantworten, heißt SHAP. Denken Sie an SHAP als ein Spiel, bei dem Sie herausfinden wollen, wie viel jeder Spieler (Merkmal) zum Endergebnis des Teams beigetragen hat. Um die perfekt genaue Antwort zu erhalten, müssten Sie theoretisch jede einzelne mögliche Kombination von Spielern testen.

Das Problem:
Für eine einfache Maschine ist das Testen jeder Kombination einfach. Doch für ein komplexes neuronales Netz mit Hunderten von Merkmalen ist die Anzahl der Kombinationen so riesig, dass es wie der Versuch wäre, jeden einzelnen Sandkorn auf jedem Strand der Erde zu zählen. Es dauert so lange, dass es praktisch unmöglich ist. Aus diesem Grund raten die meisten heutigen Tools die Antwort einfach mithilfe von Abkürzungen. Diese Schätzungen sind zwar meist schnell, können aber falsch sein, und wir haben keine Möglichkeit zu wissen, wie falsch sie sind, da wir die „echte" Antwort nicht berechnen können, um sie damit zu vergleichen.

Die Lösung: Verifiziertes SHAP (VERISHAP)
Die Autoren dieses Papiers haben ein neues Tool namens VERISHAP entwickelt. Sie haben nicht versucht, jedes Sandkorn zu zählen. Stattdessen nutzten sie einen cleveren Trick, der aus dem Bereich der „Neural Network Verification" (Neuronale Netz-Verifizierung) stammt, der normalerweise verwendet wird, um nachzuweisen, dass KI-Systeme sicher und geschützt sind.

Hier ist die Funktionsweise von VERISHAP, erläutert mit einer einfachen Analogie:

Die Analogie der „Raumsuche"

Stellen Sie sich vor, Sie suchen einen bestimmten Schatz, der in einem riesigen, dunklen Lagerhaus versteckt ist, das mit Millionen von Kisten gefüllt ist (der Suchraum).

Alte Methoden (Raten): Sie werfen einen Dartpfeil auf die Karte und sagen: „Der Schatz befindet sich wahrscheinlich in diesem allgemeinen Bereich." Das ist schnell, aber Sie könnten um Meilen danebenliegen.
Alte exakte Methoden (Zählen): Sie versuchen, jede einzelne Kiste nacheinander zu öffnen. Dies garantiert, dass Sie den Schatz finden, aber Sie werden an Altersschwäche sterben, bevor Sie fertig sind.
VERISHAP (Die intelligente Suche):
1. Teilen und Herrschen: Statt Kisten einzeln zu öffnen, teilen Sie das Lagerhaus in große Räume auf.
2. Der „Zaun"-Trick: Sie verwenden einen speziellen mathematischen Zaun (genannt Bound Propagation oder Grenzwertausbreitung), um einen ganzen Raum auf einmal zu überprüfen. Dieser Zaun sagt Ihnen: „Der Schatz in diesem Raum liegt definitiv zwischen 10 $ und 20 $."
3. Hineinzoomen: Wenn die Spanne (10 $ bis 20 $) zu groß ist, teilen Sie diesen Raum in kleinere Räume auf und überprüfen ihn erneut. Der Zaun wird enger: „Jetzt wissen wir, dass er zwischen 14 $ und 16 $ liegt."
4. Das Ergebnis: Sie teilen die Räume weiter auf, bis der Zaun so eng ist, dass die Spanne effektiv null ist. Sie haben den exakten Standort des Schatzes gefunden.

Warum dies eine große Sache ist

Das Papier behauptet drei Hauptvorteile:

Es skaliert nach oben: Bisherige Methoden, die versuchten, die exakte Antwort zu finden, würden abstürzen oder den Speicher erschöpfen, wenn das Problem zu groß wurde. VERISHAP kann Suchräume bewältigen, die um Größenordnungen größer sind (denken Sie an Milliarden- oder Billionenfache) als das, was zuvor möglich war.
Es liefert „gut genug" Antworten schnell: Sie müssen nicht immer warten, bis die Suche zu 100 % abgeschlossen ist. Wenn der „Zaun" eng genug wird (z. B. „Die Antwort liegt zwischen 14,9 und 15,1"), können Sie vorzeitig stoppen und sagen: „Wir sind zu 99,9 % sicher, dass die Antwort 15 ist." Dies liefert Ihnen vertrauenswürdige Erkenntnisse viel schneller als das Warten auf die perfekte Antwort.
Es schafft einen „Goldstandard" zum Testen: Da VERISHAP die echte Antwort für größere Probleme berechnen kann, fungiert es als eine „Wahrheitsmaschine". Forscher können es nun verwenden, um diese ratenden Tools (wie KERNELSHAP) zu testen und zu sehen, wie genau sie tatsächlich bei komplexen, realen neuronalen Netzen sind. Vorher konnten wir ratende Tools nur an winzigen, Spielzeug-Beispielen testen, die die Realität nicht widerspiegelten.

Was das Papier tatsächlich sagt (und was nicht)

Es SAGT: Sie haben erfolgreich exakte SHAP-Werte und enge Schranken für neuronale Netze auf tabellarischen Daten (wie Tabellenkalkulationen) und Bilddaten (wie MNIST-Ziffern) berechnet. Sie zeigten, dass es bei verschiedenen Arten von Netzarchitekturen (wie ResNets) und verschiedenen Aktivierungsfunktionen (wie ReLU, Tanh) funktioniert.
Es SAGT: Es ist derzeit langsamer als die „ratenden" Methoden, aber es ist der einzige Weg, um eine mathematisch bewiesene, exakte Antwort für große Netze zu erhalten.
Es SAGT NICHT: Das Papier behauptet nicht, dass dieses Tool für den unmittelbaren klinischen Einsatz in Krankenhäusern bereit ist oder dass es alle Probleme der KI-Bias löst. Es konzentriert sich strikt auf die mathematische Fähigkeit, diese Werte zu berechnen und zu verifizieren. Es erkennt an, dass es zwar ein großer Schritt vorwärts ist, die zugrunde liegende Mathematik jedoch immer noch sehr schwierig ist und es für einige sehr spezifische, komplexe Netze immer noch sehr lange dauern könnte.

Zusammenfassung:
VERISHAP ist wie der Upgrade von einem Kompass, der „ungefähr Norden" anzeigt, zu einem GPS, das Ihnen Ihren exakten Standort sagen kann, selbst in einem riesigen, unmarkierten Wald. Es beweist, dass wir die exakte Wahrheit für komplexe KI-Entscheidungen erhalten können, und es gibt uns ein Lineal, um zu messen, wie gut unsere anderen, schnelleren Tools wirklich sind.

Technische Zusammenfassung: Verifizierte SHAP (VERISHAP)

Problemstellung

Shapley Additive Explanations (SHAP) sind eine Standardmethode zur post-hoc-Explainability, um Vorhersagen von Machine-Learning-Modellen auf Eingabe-Features zurückzuführen. Die Berechnung exakter SHAP-Werte für neuronale Netze wird jedoch weithin als rechnerisch unlösbar angesehen, da der Suchraum über Feature-Teilmengen exponentiell wächst ( $2^n$ ). Während eine exakte Berechnung für baumbasierte und additive Modelle machbar ist, ist sie für allgemeine neuronale Netze #P-schwer. Folglich stützt sich die Literatur auf statistische Schätzer (z. B. KERNELSHAP, FASTSHAP, LEVERAGESHAP). Diese Schätzer stehen vor zwei grundlegenden Einschränkungen:

Ungenauigkeit: Sie liefern Approximationen, die in stark nichtlinearen Modellen oder Szenarien mit starken Feature-Interaktionen unzuverlässig sein können.
Fehlen einer Ground Truth: Da die Berechnung exakter SHAP-Werte für neuronale Netze prohibitiv teuer ist, werden Schätzer typischerweise an Modellen im Spielzeugformat evaluiert, bei denen eine exakte Berechnung möglich ist. Diese Settings lassen sich oft nicht auf reale, hochdimensionale neuronale Netze verallgemeinern.

Methodik: Verifizierte SHAP (VERISHAP)

Die Arbeit stellt VERISHAP vor, den ersten Algorithmus, der jüngste Fortschritte in der Verifikation neuronaler Netze nutzt, um exakte SHAP-Werte und nachweisbare Schranken für neuronale Netze zu berechnen. Der Ansatz adaptiert Branch-and-Bound-Verifikationstechniken auf die diskrete, probabilistische und summationsintensive Natur von SHAP.

Kernalgorithmus

VERISHAP verwendet eine inkrementelle Branch-and-Bound-Strategie, um den Feature-Raum (die Menge aller Koalitionen $S_i$ für ein Feature $i$ ) rekursiv zu partitionieren.

Partitionierung: Der Algorithmus definiert Zweige $B$ basierend auf Mengen von einbezogenen ( $I$ ) und ausgeschlossenen ( $E$ ) Features. Ein Zweig repräsentiert eine Teilmenge von Koalitionen, bei denen Features in $I$ vorhanden sind und Features in $E$ fehlen.
Schrankenbildung durch Propagation: Für jeden Zweig berechnet der Algorithmus untere und obere Schranken für den marginalen Beitrag $\Delta_i(S) = v(S \cup \{i\}) - v(S)$ $Δ_{i} (S) = v (S \cup {i}) - v (S)$ .
- Um kontinuierliche Schrankenpropagation (z. B. CROWN, IBP) auf diskrete Mengen anzuwenden, relaxiert der Algorithmus boolesche Feature-Masken $m \in \{0, 1\}^n$ auf den kontinuierlichen Bereich $[0, 1]^n$ .
- Er verwendet Lineare Schrankenpropagation (LBP) (speziell CROWN-IBP), um enge Schranken für die Wertefunktion $v(S)$ über dem relaxierten Bereich abzuleiten.
Aggregation: Die Gesamtschranken für SHAP-Werte werden durch Summierung der gewichteten Schranken aller Zweige berechnet:
$\phi_i^{(t)} = \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B \leq \phi_i \leq \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B = \bar{\phi}_i^{(t)}$
wobei $\Lambda_B$ die geschlossene Form der Summe der Shapley-Gewichte für die Koalitionen im Zweig $B$ ist, die kombinatorisch abgeleitet wird.
Verfeinerung: Der Algorithmus wählt iterativ Zweige zum Aufteilen (unter Verwendung von Strategien wie MAXDIAM) und Features, auf die aufgeteilt wird (unter Verwendung von Strategien wie SMEARS), aus, verfeinert die Schranken, bis sie gegen den exakten Wert oder eine gewünschte Präzision konvergieren.

Wichtige theoretische Eigenschaften

Terminierung: Der Algorithmus garantiert, dass er nach einer endlichen Anzahl von Iterationen (höchstens $2^{n-1}$ ) mit exakten SHAP-Werten terminiert, da die Partitionierung schließlich einzelne Koalitionen isoliert.
Frühe Terminierung für lineare Modelle: Bei linearen Modellen terminiert der Algorithmus in der ersten Iteration, da der marginale Beitrag konstant ist und LBP bei linearen Kompositionen keinen Approximationsfehler einführt.
Stückweise Linearität: Für mit ReLU aktivierte Netze kann der Algorithmus frühzeitig terminieren, wenn die Partitionierung die Suche auf Bereiche beschränkt, in denen das Netzwerk linear verhält.

Wichtige Beiträge

Erste exakte SHAP für neuronale Netze: VERISHAP ist der erste Algorithmus, der exakte SHAP-Werte für allgemeine neuronale Netze berechnet und dabei Suchräume um Größenordnungen größer als bei bisherigen exakten Methoden bewältigt.
Nachweisbare Schranken: Die Methode liefert beliebig enge untere und obere Schranken für SHAP-Werte, was vertrauenswürdige erklärende Einblicke ermöglicht, noch bevor eine vollständige Konvergenz erreicht ist.
Ground-Truth-Baseline: Sie etabliert einen prinzipiellen Rahmen zur Evaluierung statistischer SHAP-Schätzer auf größeren, realistischeren Suchräumen, in denen die Ground Truth bisher unerreichbar war.
Effizienz durch Verifikation: Durch die Ausnutzung der Zerlegung neuronaler Netze in nahezu lineare Bereiche vermeidet der Algorithmus in vielen praktischen Fällen die Enumeration aller $2^n$ Koalitionen.

Experimentelle Ergebnisse

Die Autoren evaluierten VERISHAP an Benchmarks für tabellarische Daten (UCI-Datensätze) und Vision (MNIST, FashionMNIST, CIFAR10, GTSRB).

Skalierbarkeit im Vergleich zu ExactSHAP: VERISHAP übertrifft die state-of-the-art-exakte Methode (EXACTSHAP) deutlich. Während EXACTSHAP bei Suchräumen größer als $2^{20}$ den GPU-Speicher erschöpft, berechnet VERISHAP exakte Werte für Instanzen bis zu $2^{25}$ ( $\approx 3 \times 10^7$ Koalitionen) und liefert enge Schranken für Räume bis zu $2^{60}$ ( $\approx 10^{18}$ Koalitionen).
Vergleich mit Schätzern: Im Vergleich zu statistischen Schätzern (KERNELSHAP, TREEMSR, LEVERAGESHAP) zeigt VERISHAP, dass Schätzer oft nicht die gleiche Genauigkeit innerhalb der Speichereinschränkungen erreichen. Darüber hinaus offenbart VERISHAP, dass die Leistung von Schätzern stark zwischen Datensätzen variiert (z. B. zeigt TREEMSR im Vergleich zu baumbasierten Modellen eine volatile Leistung bei neuronalen Netzen).
Architekturvielfalt: Der Algorithmus berechnet erfolgreich exakte SHAP-Werte für verschiedene Architekturen, einschließlich vollständig verbundener Netze mit ReLU-, tanh- und Swish-Aktivierungen sowie ResNets.
Konvergenz: In Experimenten (z. B. MNIST) werden die Schranken lange vor der Berechnung des exakten Wertes aussagekräftig (sie enthüllen Zuordnungsmuster), oft innerhalb von Sekunden, während die exakte Berechnung möglicherweise mehrere zehn Sekunden dauert.

Bedeutung und Behauptungen

Die Arbeit positioniert VERISHAP als ersten Schritt hin zur Skalierung der exakten SHAP-Berechnung für neuronale Netze. Ihre Bedeutung liegt in drei Bereichen:

Skalierbarkeit: Sie überbrückt die Lücke zwischen der theoretischen Unlösbarkeit exakter SHAP und der praktischen Anwendung durch die Nutzung der Verifikation neuronaler Netze.
Vertrauenswürdigkeit: Sie bietet eine Methode, um „Ground-Truth"-Erklärungen mit nachweisbaren Garantien zu erhalten und adressiert die Unsicherheit, die statistischen Approximationen inhärent ist.
Evaluierungsrahmen: Sie liefert einen rigorosen Benchmark zur Evaluierung und Verbesserung von SHAP-Schätzern auf größeren Suchräumen und geht damit über Spielzeugmodelle hinaus.

Die Autoren räumen ein, dass die Berechnung exakter SHAP-Werte weiterhin #P-schwer bleibt und VERISHAP für bestimmte komplexe Netze möglicherweise immer noch langsam sein kann. Sie argumentieren jedoch, dass die Fähigkeit, nachweisbare Schranken zu berechnen, und das Potenzial für kontinuierliche Verbesserungen in der Verifikation neuronaler Netze dies zu einer grundlegenden Weiterentwicklung für vertrauenswürdige KI-Explainability machen.