📊 statistics

ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation

Das Paper stellt ShaplEIG vor, eine Methode des Bayesschen Versuchsdesigns, die Gauß-Prozess-Surrogate und geschlossene Erwartungsgewinn-Formeln nutzt, um Koalitionen adaptiv auszuwählen und dadurch die Stichprobeneffizienz der Shapley-Wert-Schätzung in kostspieligen Szenarien mit geringem Budget signifikant zu verbessern.

Ursprüngliche Autoren: David Rundel, Fabian Fumagalli, Maximilian Muschalik, Bernd Bischl, Matthias Feurer

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: David Rundel, Fabian Fumagalli, Maximilian Muschalik, Bernd Bischl, Matthias Feurer

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

Das große Problem: Das Dilemma der „zu vielen Auswahlmöglichkeiten“

Stellen Sie sich vor, Sie versuchen herauszufinden, wie viel jeder einzelne Spieler zum Sieg eines Teams beigetragen hat. In der Welt des Maschinellen Lernens sind diese „Spieler“ Merkmale (wie das Alter eines Patienten oder die Quadratmeterzahl eines Hauses) oder Datenpunkte. Das mathematische Werkzeug, das diesen Beitrag misst, wird als Shapley-Wert bezeichnet.

Um den exakten Shapley-Wert zu berechnen, müssen Sie jede mögliche Kombination der Spieler testen.

Wenn Sie 10 Spieler haben, gibt es 1.024 Kombinationen.
Wenn Sie 20 Spieler haben, sind es über 1 Million Kombinationen.
Wenn Sie 50 Spieler haben, ist die Zahl so gewaltig, dass sie die Anzahl der Atome im Universum übersteigt.

Darüber hinaus ist das Testen jeder Kombination teuer. Es kann erfordern, ein komplexes KI-Modell von Grund auf neu zu trainieren, was Stunden dauert oder Geld kostet. Das ist so, als würde man versuchen, das perfekte Rezept zu finden, indem man jede mögliche Kombination von Zutten weltweit nacheinander backt. Man geht schlichtweg die Zeit und das Geld aus, bevor man fertig ist.

Die aktuelle Lösung: Raten und Prüfen

Da wir nicht alles testen können, wählen aktuelle Methoden Kombinationen meist zufällig aus oder folgen einem festen Muster (wie „teste immer erst kleine Gruppen“).

Die Analogie: Stellen Sie sich vor, Sie sind ein Detektiv, der versucht, ein Verbrechen aufzuklären, indem er Verdächtige befragt. Aktuelle Methoden sind wie Detektive, die Verdächtige alphabetisch sortiert befragen oder Namen aus einem Hut ziehen. Sie befragen vielleicht die falschen Leute, während Sie den entscheidenden Hinweis verpassen, den die eine Person hält, mit der Sie noch gar nicht gesprochen haben.

Die neue Lösung: ShaplEIG (Der smarte Detektiv)

Die Autoren schlagen eine neue Methode namens ShaplEIG vor. Anstatt blind zu raten, nutzt diese Methode einen „smarten Detektiv“-Ansatz basierend auf dem Bayesianischen Versuchsdesign (Bayesian Experimental Design).

So funktioniert es, Schritt für Schritt:

1. Die „Surrogat“-Karte (Die Kristallkugel)

Da das Testen jeder Kombination zu teuer ist, baut ShaplEIG ein Surrogatmodell (eine vereinfachte, schnelle Annäherung) des Spiels auf.

Die Analogie: Stellen Sie sich vor, Sie versuchen, ein riesiges, nebliges Gebirge zu kartieren. Anstatt jeden einzelnen Zentimeter zu durchwandern, bauen Sie ein kleines, schnelles 3D-Modell des Geländes basierend auf einigen ersten Wanderungen. Dieses Modell ist nicht perfekt, aber es gibt Ihnen eine gute Vorstellung davon, wo sich Gipfel und Täler befinden.

2. Der „Erwartete Informationsgewinn“ (Der Kompass)

Dies ist die eigentliche Magie der Arbeit. Die Methode fragt: „Welche einzelne Kombination sollte ich als Nächstes testen, um am meisten über die endgültige Antwort zu erfahren?“

Die Analogie: Ein normaler Detektiv fragt vielleicht: „Wer sieht verdächtig aus?“ (Unsicherheitssampling). ShaplEIG fragt: „Wenn ich diese spezifische Person befrage, wie sehr wird das das gesamte Rätsel für alle anderen klären?“
Es berechnet den Erwarteten Informationsgewinn (Expected Information Gain, EIG). Es betrachtet die gebaute 3D-Karte und sagt: „Das Testen dieser spezifischen Koalition wird unsere Unsicherheit über die Endergebnisse aller Spieler am stärksten reduzieren.“

3. Die „Closed-Form“-Abkürzung (Die Superkraft)

Normalerweise ist die Berechnung dessen, „wie viel Information wir gewinnen werden“, unglaublich schwer und langsam (als würde man versuchen, ein Puzzle zu lösen, während sich die Teile bewegen).

Der Durchbruch der Arbeit: Die Autoren haben entdeckt, dass Shapley-Werte, da sie auf eine spezifische lineare Weise berechnet werden, eine mathematische Abkürzung (einen „geschlossenen Ausdruck“ oder „Closed-Form Expression“) nutzen können, um diesen Informationsgewinn sofort zu berechnen.
Die Analogie: Normalerweise müssten Sie die gesamte Untersuchung erneut simulieren, um zu wissen, wie sehr ein neuer Hinweis hilft. ShaplEIG hat eine Formel gefunden, die die Antwort in einem Bruchteil einer Sekunde liefert – wie ein GPS, das sofort die beste Route neu berechnet, ohne die ganze Welt neu kartieren zu müssen.

4. Die „Polynomielle“ Beschleunigung (Der Aufzug)

Selbst mit der Abkürzung wäre die Berechnung für Millionen von Kombinationen immer noch zu langsam.

Der Durchbruch der Arbeit: Sie verwendeten einen cleveren mathematischen Trick unter Verwendung von elementarsymmetrischen Polynomen (einer Art mathematisches Muster), um eine Berechnung, die exponentiell wächst (1, 10, 100, 1000...), in eine, die polynomiell wächst (1, 10, 100, 1000... aber viel langsamer), umzuwandeln.
Die Analogie: Anstatt den Berg Schritt für Schritt zu Fuß zu erklimmen (exponentiell), bauen sie einen Aufzug (polynomiell), der einen selbst bei sehr großen Bergen schnell nach oben bringt.

Die Ergebnisse: Bessere Antworten, weniger Arbeit

Die Autoren haben ShaplEIG bei verschiedenen schwierigen Aufgaben getestet, wie zum Beispiel:

Herauszufinden, welche Merkmale am wichtigsten für ein medizinisches Diagnosemodell sind.
Den Wert spezifischer Datenpunkte in einem Datensatz zu bestimmen.
Zu verstehen, welche Einstellungen (Hyperparameter) ein KI-Modell am besten funktionieren lassen.

Das Ergebnis:
In fast allen Tests fand ShaplEIG die richtigen Antworten schneller und mit weniger teuren Tests als die besten existierenden Methoden.

Die Analogie: Wenn andere Methoden 400 Verdächtige befragen mussten, um den Fall mit 90 % Genauigkeit zu lösen, löste ShaplEIG ihn oft mit nur 200 Befragungen – und das bei höherer Genauigkeit.

Zusammenfassung

ShaplEIG ist eine intelligente Art und Weise, abzuschätzen, wie viel die einzelnen Teile eines KI-Modells zu seinen Entscheidungen beitragen. Anstatt blind verschiedene Kombinationen zu testen, nutzt es einen mathematischen „Kompass“, um den informativsten Test auszuwählen, der als Nächstes durchgeführt werden sollte. Durch eine clevere mathematische Abkürzung erledigt es dies schnell und spart Zeit und Geld, wenn es um teure KI-Modelle geht.

Technisches Resümee: ShaplEIG

Problemstellung

Shapley-Werte (SVs) dienen als fundiertes Attributionsmaß im Bereich des interpretierbaren maschinellen Lernens, doch ihre exakte Berechnung ist oft unpraktikabel. Die Rechenlast ergibt sich aus zwei Faktoren: dem exponentiellen Wachstum der Koalitionen ( $2^p$ ) mit der Anzahl der Spieler $p$ und den hohen Kosten für die Evaluierung der Wertfunktion $\nu$ für jede Koalition. In Anwendungen wie dem trainingsbasierten Feature-Importance, der Datenbewertung (Data Valuation) und der Hyperparameter-Wichtigkeit kann die Evaluierung der Wertfunktion das vollständige Nachtrainieren von Modellen oder aufwendige Inferenzschritte beinhalten, was das Evaluierungsbudget drastisch einschränkt.

Bestehende Approximationsmethoden, einschließlich Monte-Carlo-Sampling und surrogate-basierter Ansätze (z. B. Kernel SHAP, Regression MSR), verlassen sich typischerweise auf feste, nicht-adaptive Sampling-Verteilungen. Dies wirft die Frage auf, ob die Approximationsgenauigkeit verbessert werden kann, indem Koalitionen zur Evaluierung adaptiv basierend auf vorangegangenen Beobachtungen ausgewählt werden, insbesondere in Regimes mit geringem Budget. Obwohl das Bayesian Experimental Design (BED) einen Rahmen für sequenzielles Design mittels Expected Information Gain (EIG) bietet, ist dessen Anwendung in der SV-Schätzung aufgrund fehlender geschlossener EIG-Ausdrücke und der rechnerischen Unpraktikabilität der EIG-Schätzung für hochdimensionale diskrete Räume begrenzt.

Methodik

Die Autoren schlagen ShaplEIG vor, einen Bayesian Experimental Design-Ansatz, der Koalitionen adaptiv auswählt, um den Informationsgewinn hinsichtlich der Shapley-Werte zu maximieren.

1. Gauß-Prozess-Surrogat mit Hamming-Kernel

ShaplEIG modelliert die Wertfunktion $\nu$ mithilfe eines Gauß-Prozess (GP) Surrogats. Um den binären Eingaberaum der Koalitionen (repräsentiert als Indikatorvektoren $z \in \{0, 1\}^p$ ) zu handhaben, verwendet die Methode einen Hamming-Distanz-Kernel. Dieser Kernel quantifiziert die Ähnlichkeit zwischen Koalitionen basierend auf gewichteten Hamming-Distanzen mit lernbaren Längenskala-Hyperparametern $\xi$ . Der GP liefert eine Posterior-Verteilung über die Wertfunktion über alle $2^p$ Koalitionen gegeben einen Datensatz $D_t$ beobachteter Evaluierungen.

2. Konsistente SV-Schätzung durch Linearität

Eine zentrale theoretische Erkenntnis ist die Linearität der Shapley-Werte in Bezug auf die Wertfunktion. Die SVs $\phi$ können als lineare Transformation des Wertfunktionsvektors $\nu$ ausgedrückt werden: $\phi = A\nu$ , wobei $A$ eine bekannte Matrix ist, die aus der Shapley-Formel abgeleitet wurde. Folglich ist die Posterior-Verteilung über die SVs unter dem GP-Surrogat ebenfalls gaußförmig und in geschlossener Form verfügbar:
$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$
Die Autoren extrahieren SV-Schätzungen aus dem Posterior-Mittelwert, $\hat{\phi} = A\mu_{\nu|D_t}$ . Entscheidend ist, dass dieser Schätzer für rauschfreie (oder quasi-rauschfreie) GPs konsistent ist: Wenn alle $2^p$ Koalitionen evaluiert werden, konvergieren die Schätzungen exakt gegen die wahren Shapley-Werte.

3. Geschlossener Ausdruck des Expected Information Gain (EIG)

Der Kernbeitrag besteht in der Ableitung eines geschlossenen Ausdrucks für den EIG einer Kandidaten-Koalition $z^{(i)}$ hinsichtlich der SVs. Durch die Rahmung des sequenziellen Designs als bayesianisches lineares Inverses Problem, bei dem die SVs ein lineares Endziel darstellen, wird gezeigt, dass der EIG nur von der Posterior-Kovarianz der SVs abhängt:
$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$
Dies vermeidet die verschachtelten Erwartungswerte, die typischerweise in BED erforderlich sind, da der EIG ausschließlich vom experimentellen Design (der ausgewählten Koalition) und nicht vom spezifischen Ergebnis $y(x)$ abhängt.

4. Effiziente Berechnung mittels elementarsymmetrischer Polynome

Die direkte Berechnung des EIG beinhaltet Operationen auf Matrizen der Größe $2^p \times 2^p$ , was zu einer exponentiellen Komplexität führt. Die Autoren schlagen ein effizientes Berechnungsschema vor, das die Komplexität auf Polynomzeit ( $O(p^4 + t^3)$ ) reduziert, indem die multiplikative Struktur des Hamming-Kernels ausgenutzt wird.

Die für den EIG erforderlichen Terme (speziell $A\Sigma_{\nu|D_t}e_i$ und $A\Sigma_{\nu|D_t}A^\top$ ) werden als gewichtete Summen von Kernel-Evaluierungen umgeschrieben.
Diese Summen werden mit skalierten elementarsymmetrischen Polynomen (ESPs) identifiziert.
Durch die effiziente Berechnung dieser Polynome (unter Verwendung von Dynamischer Programmierung und Präfix-/Suffix-Tabellen) vermeidet die Methode die explizite Enumeration aller Koalitionen.

5. Algorithmus

Der Algorithmus verläuft gierig (greedy):

Initialisierung mit einem kleinen Design (z. B. Leverage Score Sampling).
Anpassung des GP-Surrogats und Optimierung der Hyperparameter.
Berechnung des EIG für alle Kandidaten-Koalitionen unter Verwendung des effizienten Polynom-Schemas.
Auswahl der Koalition mit dem maximalen EIG, Evaluierung der Wertfunktion und Aktualisierung des Datensatzes.
Wiederholung, bis das Budget erschöpft ist.

Zentrale Beiträge

ShaplEIG-Framework: Einführung einer neuartigen, BED-basierten Methode zur SV-Schätzung, die ein GP-Surrogat mit Hamming-Kernel verwendet und Koalitionen adaptiv basierend auf dem EIG auswählt.
Geschlossener EIG: Nachweis, dass der EIG für Shapley-Werte unter einem GP-Surrogat einen geschlossenen Ausdruck besitzt, indem die Linearität der SVs in der Wertfunktion genutzt wird.
Polynomielle Komplexität: Vorschlag eines effizienten Berechnungsschemas für den EIG, das die Komplexität von exponentiell auf polynomiel in Bezug auf die Anzahl der Spieler ( $p$ ) reduziert, mittels elementarsymmetrischer Polynome.
Konsistente Schätzung: Bereitstellung eines konsistenten SV-Schätzers, der gegen exakte Werte konvergiert, wenn alle Koalitionen evaluiert werden, im Gegensatz zu einigen baumbasierten Surrogat-Methoden, die zusätzliche Anpassungsschritte erfordern.

Experimentelle Ergebnisse

Die Autoren evaluieren ShaplEIG über diverse, kostspielige Anwendungen mit kleinen bis moderat großen Spielen ( $8 \le p \le 101$ ):

Aufgaben: Globale Feature-Wichtigkeit (TabPFN), Datenbewertung (Random Forest, Gradient Boosting), Hyperparameter-Wichtigkeit (XGBoost, LCBench) und lokale Erklärungen (ResNet, ViT, Random Forest).
Baselines: Vergleich gegen Kernel SHAP, Leverage SHAP, Permutation Sampling und den aktuellen Stand der Technik, Regression MSR (gekoppelt mit XGBoost).
Ablationen: Vergleich mit Varianten, die dasselbe GP-Surrogat, aber unterschiedliche Selektionsstrategien verwenden (Random, Uncertainty Sampling, Leverage Score Sampling).

Ergebnisse:

Sample-Effizienz: ShaplEIG erreicht über die meisten Aufgaben hinweg im Low-Budget-Regime konsistent die beste Gesamtgenauigkeit (niedrigster mittlerer quadratischer Fehler). Es dominiert Wettbewerber oft strikt, insbesondere in asymmetrischen Spielen, in denen Spielerinteraktionen nicht uniform sind.
Ablations-Erkenntnisse: Die starke Leistung wird primlich dem EIG-basierten Selektionsverfahren zugeschrieben und nicht nur der Verwendung eines GP-Surrogats. Uncertainty Sampling (US) schnitt oft schlechter ab als Random Sampling, was verdeutlicht, dass die Maximierung der marginalen Varianz nicht gleichbedeutend mit der Maximierung der Information über die linear transformierten SVs ist.
Skalierbarkeit: Für größere Spiele ( $p > 16$ ) bleibt die Methode effektiv, selbst wenn das Refitting der Hyperparameter nach einem Zeitplan statt in jeder Iteration erfolgt.
Rechenaufwand: Während die EIG-Berechnung effizient ist (Sekundenbereich), kann das Anpassen der Hyperparameter für große $p$ (bis zu 25 Minuten pro Iteration für $p \approx 100$ ) zum Engpass werden. Die Autoren merken an, dass ShaplEIG am besten geeignet ist, wenn die Evaluierungen der Wertfunktion tatsächlich sehr teuer sind, was den Overhead rechtfertigt.

Bedeutung und Behauptungen

Das Paper behauptet, dass ShaplEIG einen fundierten Rahmen zur Verbesserung der Stichproben-Effizienz in der SV-Schätzung für kostspielige Spiele bietet. Durch die Ableitung eines geschlossenen EIG und eines effizienten polynomiellem Berechnungsschemas überwinden die Autoren die primären Barrieren für die Anwendung von Bayesian Experimental Design in diesem Bereich.

Die Autoren stellen bescheiden fest, dass die Methode zwar einen Rechenaufwand durch wiederholte GP-Optimierung verursacht, aber substantielle Gewinne in der Schätzgenauigkeit bietet, wenn die Evaluierungsbudgets begrenzt sind. Sie räumen ein, dass der Overhead für sehr große Spiele oder weniger kostspielige Wertfunktionen prohibitiv sein kann, und schlagen vor, dass zukünftige Arbeiten auf weitere Verbesserungen der Rechenleistung abzielen sollten, um die Anwendbarkeit zu erweitfend. Die Arbeit beansprucht nicht, die SV-Schätzung für alle Szenarien zu lösen, sondern zielt spezifisch auf das Regime teurer Wertfunktionen ab, in dem eine adaptive Selektion entscheidend ist.