📊 statistics

Proxy-Based Approximation of Shapley and Banzhaf Interactions

Dieser Beitrag stellt ProxySHAP vor, eine neuartige Methode, die baumbasierte Proxy-Modelle mit Residuenkorrektur und einer exakten Berechnung in polynomialer Zeit für Baum-Ensembles kombiniert, um eine State-of-the-Art-Genauigkeit und Effizienz bei der Schätzung von Shapley- und Banzhaf-Interaktionen zu erreichen und dabei bestehende Schätzer wie ProxySPEX und KernelSHAP-IQ erheblich zu übertreffen.

Ursprüngliche Autoren: Santo M. A. R. Thies, Hubert Baniecki, R. Teal Witter, Eyke Hüllermeier, Maximilian Muschalik, Fabian Fumagalli

Veröffentlicht 2026-05-22

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Santo M. A. R. Thies, Hubert Baniecki, R. Teal Witter, Eyke Hüllermeier, Maximilian Muschalik, Fabian Fumagalli

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 komplexe Maschine, wie eine ausgefeilte KI, die entscheidet, ob ein Kredit bewilligt werden soll, oder die das Wetter vorhersagt. Sie möchten wissen, warum sie eine bestimmte Entscheidung getroffen hat. Verließ sie sich hauptsächlich auf das Einkommen des Antragstellers? War es die Kreditwürdigkeit? Oder war es eine seltsame Kombination aus beidem?

In der Welt der KI verwenden wir Mathematik, um diese Entscheidungen in „Beiträge" aufzuschlüsseln. Die bekannteste Methode heißt Shapley-Werte (benannt nach einem mit dem Nobelpreis ausgezeichneten Ökonomen). Stellen Sie es sich wie ein Teamprojekt vor: Wenn das Team erfolgreich ist, wie viel Anerkennung verdient dann jede einzelne Person?

Aber hier liegt das Problem: Moderne KI-Modelle sind so komplex, dass sie sich nicht nur auf einzelne Faktoren verlassen. Sie verlassen sich auf Interaktionen. Vielleicht bewilligt die KI den Kredit nur, wenn das Einkommen hoch ist UND die Kreditwürdigkeit hoch ist. Betrachtet man sie separat, wirken sie schwach. Betrachtet man sie zusammen, sind sie mächtig.

Die Berechnung dieser „Team-up"-Interaktionen ist unglaublich schwierig. Es ist wie der Versuch, jede mögliche Kombination von Spielern in einer Sportmannschaft zu zählen, um zu sehen, wer gewinnt. Für ein kleines Team ist das einfach. Für ein Team von 1.000 Spielern (was in der KI üblich ist) ist die Anzahl der Kombinationen so riesig, dass selbst die schnellsten Supercomputer länger als das Alter des Universums benötigen würden, um sie exakt zu berechnen.

Das Problem: Geschwindigkeit vs. Genauigkeit

Wissenschaftler haben versucht, dies mit zwei Hauptansätzen zu lösen, aber beide haben Mängel:

Die „Rat"-Methode: Sie nehmen einige zufällige Stichproben und raten den Rest. Es ist schnell, aber oft ungenau. Es ist wie der Versuch, den Geschmack einer riesigen Suppe zu erraten, indem man einen einzigen Löffel probiert.
Die „Exakte"-Methode: Sie versuchen, alles präzise zu berechnen. Es ist genau, aber so langsam, dass es für große Probleme unbrauchbar ist.

Die Lösung: ProxySHAP

Die Autoren dieses Papiers stellen eine neue Methode namens ProxySHAP vor. Stellen Sie es sich als eine clevere zweistufige Detektivstrategie vor, die das Beste aus beiden Welten vereint.

Schritt 1: Der „Zeichner" (Der Proxy)

Zuerst wirft die KI einen Blick auf die komplexe Maschine und zeichnet eine vereinfachte Skizze davon. Diese Skizze ist ein „Proxy"-Modell.

Analogie: Stellen Sie sich einen Meisterkoch (die komplexe KI) vor, der einen Eintopf mit 100 Zutaten zubereitet. Anstatt zu versuchen, jede einzelne Zutat im riesigen Topf zu probieren, bereitet der Koch schnell eine kleine, einfache Suppe zu, die ähnlich schmeckt wie der große Eintopf.
Der Trick: Die Autoren verwenden eine bestimmte Art von Skizze (ein „baumgestütztes" Modell, wie ein Flussdiagramm), die leicht zu analysieren ist. Da die Skizze einfach ist, können sie sofort exakt berechnen, wie die Zutaten interagieren, ohne die unmögliche Mathematik am riesigen Eintopf durchzuführen.

Schritt 2: Die „Korrektur" (Der Residual)

Die Skizze ist nicht perfekt. Sie ist nah dran, aber sie verpasst einige winzige Details.

Analogie: Die kleine Suppe schmeckt zu 95 % wie der große Eintopf, aber vielleicht fehlt ihr eine Prise Salz oder ein Hauch von Gewürz.
Die Lösung: Die Methode betrachtet dann den Unterschied (den „Residual") zwischen dem echten Eintopf und der Skizze. Sie verwendet eine intelligente Stichprobenmethode, um nur diese fehlenden Details zu schätzen.
Die Innovation: Das Papier zeigt, dass es bei sehr komplexen Interaktionen (wie 3 oder 4 Zutaten, die zusammenarbeiten) versuchen kann, die Skizze mit zufälliger Stichprobenbildung zu „reparieren", was die Dinge tatsächlich schlimmer machen kann (wie zu viel Salz hinzufügen). Daher ist ProxySHAP intelligent genug zu wissen, wann die Korrektur angewendet werden soll und wann man sich einfach auf die Skizze verlassen kann.

Warum das wichtig ist

Das Papier behauptet, ProxySHAP sei der neue „Goldstandard" aus drei Gründen:

Es ist schnell: Es kann KI-Modelle mit Tausenden von Merkmalen (Zutaten) in angemessener Zeit bewältigen.
Es ist genau: Es ist viel präziser als frühere „Rat"-Methoden, insbesondere wenn man kein riesiges Budget an Computerzeit hat.
Es ist vielseitig: Es funktioniert bei verschiedenen KI-Typen, von denen, die Bilder und Texte betrachten (wie das Erkennen einer Giraffe in einem Fluss), bis zu denen, die finanzielle Risiken vorhersagen.

Das Fazit

Bevor dies der Fall war, musste man, wenn man verstehen wollte, wie eine komplexe KI eine Entscheidung traf, die viele interagierende Faktoren beinhaltete, zwischen einer schnellen, schlampigen Antwort oder einer langsamen, unmöglichen wählen. ProxySHAP liefert Ihnen eine schnelle, hochgenaue Antwort durch eine clevere „Skizze und Korrektur"-Strategie. Es ist wie ein Meisterkoch, der Ihnen sofort genau sagen kann, welche Zutaten das Gericht so lecker gemacht haben, selbst wenn das Rezept Tausende von Schritten hat.

Technischer Zusammenfassung: Proxy-basierte Approximation von Shapley- und Banzhaf-Interaktionen

Problemstellung
Moderne Machine-Learning-Anwendungen stützen sich zunehmend auf die kooperative Spieltheorie, um das Modellverhalten zu interpretieren, wobei speziell Shapley- und Banzhaf-Werte verwendet werden, um Beiträge einzelner Merkmale zuzuordnen. Das Verständnis komplexer, nichtlinearer Dynamiken erfordert jedoch oft die Analyse von Interaktionen höherer Ordnung (Teilmengen von Merkmalen) und nicht nur von Singleton-Effekten. Die Berechnung exakter kardinal-probabilistischer Interaktionsindizes ist für eine große Anzahl von Merkmalen ( $n$ ) aufgrund des exponentiellen Wachstums des Koalitionsraums ( $2^n$ ) rechnerisch nicht handhabbar.

Bestehende Schätzer stehen vor einem kritischen Zielkonflikt zwischen Geschwindigkeit und Genauigkeit:

Stichprobenbasierte Methoden (z. B. SHAP-IQ, KernelSHAP-IQ) sind oft genau, erfordern jedoch unpraktische Stichprobenbudgets, um die große Anzahl von Termen höherer Ordnung zu erfassen, und leiden unter einer hohen Varianz, die sich mit der Interaktionsordnung schlecht skaliert.
Proxy-basierte Methoden (z. B. ProxySPEX) bieten Geschwindigkeit, beruhen jedoch auf einer Fourier-basierten Extraktion aus Baum-Surrogaten. Dieser Ansatz leidet unter einer exponentiellen Komplexität in Bezug auf die Baumbreite und erfordert oft eine aggressive Truncierung, die die Genauigkeit beeinträchtigt. Darüber hinaus liefern bestehende Proxy-Methoden typischerweise Interaktionen des Proxy anstelle der zugrunde liegenden Wertefunktion, was zu einer Verzerrung führt.

Methodik: ProxySHAP
Die Autoren schlagen ProxySHAP vor, ein Framework, das die Stichprobeneffizienz baumbasierter Proxy-Modelle mit einem prinzipiellen Weg zur Konsistenz durch Residualkorrektur vereint. Die Methode zerlegt den Ziel-Interaktionsindex $\phi^p_S(\nu)$ in zwei Komponenten:
$\phi^p_S(\nu) = \underbrace{\phi^p_S(\hat{\nu}_T)}_{\text{Exakter Proxy}} + \underbrace{\phi^p_S(\nu - \hat{\nu}_T)}_{\text{Residual}}$

Proxy-Anpassung (Phase 1): Ein baumbasiertes Modell (z. B. XGBoost, LightGBM) oder ein lineares Modell mit Interaktionsmerkmalen wird auf abgetasteten Koalitionen trainiert, um die zugrunde liegende Wertefunktion $\nu$ zu approximieren.
Exakte Proxy-Extraktion (Phase 2): Im Gegensatz zu früheren Methoden, die Fourier-Koeffizienten extrahieren, führt ProxySHAP eine polynomielle Verallgemeinerung der interventiven TreeSHAP ein. Dies ermöglicht die exakte Berechnung jedes kardinal-probabilistischen Interaktionsindex (einschließlich Shapley und Banzhaf) direkt aus der Baumstruktur.
- Die Methode nutzt die Möbius-Darstellung von Indikatorspielen, die durch Baumblätter definiert sind.
- Sie vermeidet die exponentielle Komplexität $O(4^d)$ der Fourier-basierten Extraktion (wobei $d$ die Baumbreite ist) und erreicht eine Laufzeit von $O(n_{nodes})$ pro Interaktion.
Residualanpassung: Um die durch den Proxy eingeführte Verzerrung zu korrigieren, da dieser $\nu$ $ν$ nicht perfekt abbildet, schätzt die Methode die Interaktionen des Residualspiels $(\nu - \hat{\nu}_T)$ $(ν - \overset{ν}{^}_{T})$ unter Verwendung von Maximum Sample Reuse (MSR).
- Die Arbeit liefert eine theoretische Analyse, die zeigt, dass die Varianz des MSR-Schätzers für Interaktionen der Ordnung $k$ als $O(n^{k-1}/|T|)$ skaliert.
- Folglich leiten die Autoren Bedingungen ab, unter denen eine MSR-Anpassung vorteilhaft ist: vor allem für niedrigdimensionale Settings ( $n < 30$ ) oder wenn das Stichprobenbudget $|T|$ im Verhältnis zu $n^{k-1}$ ausreichend groß ist. Für Interaktionen höherer Ordnung in großen Spielen kann die Varianz der Korrektur die Reduktion der Verzerrung überwiegen.

Hauptbeiträge

ProxySHAP-Framework: Eine neuartige Schätzstrategie, die einen baumbasierten Proxy mit einer Residualkorrektur kombiniert und eine effiziente und genaue Approximation von Interaktionen höherer Ordnung ermöglicht.
Theoretischer Fortschritt:
- Herleitung eines geschlossenen, polynomiellen Algorithmus zur Extraktion exakter kardinal-probabilistischer Interaktionsindizes aus Baumensembles, der die exponentielle Abhängigkeit von der Tiefe bei früheren Fourier-basierten Methoden umgeht.
- Formale Charakterisierung des Varianzwachstums von MSR für Interaktionen höherer Ordnung und Etablierung expliziter Bedingungen (in Bezug auf $n$ , Budget und Interaktionsordnung $k$ ), unter denen eine Residualanpassung die Leistung verbessert oder verschlechtert.
Empirische Leistung: Umfassende Benchmarks über 47 Datensätze (tabellarisch, Vision, Sprache, Graph und Vision-Sprache) zeigen, dass ProxySHAP einen neuen State-of-the-Art-Standard setzt. Es erzielt den niedrigsten Fehler sowohl in Regimen mit kleinem Budget (wo es ProxySPEX übertrifft) als auch in Regimen mit großem Budget (wo es KernelSHAP-IQ übertrifft).

Ergebnisse

Genauigkeit: ProxySHAP übertrifft Baselines (KernelSHAP-IQ, ProxySPEX, SHAP-IQ) konsistent in Bezug auf den relativen mittleren quadratischen Fehler (MSE). In großskaligen Anwendungen mit Tausenden von Merkmalen (z. B. Bioresponse mit $n=1776$ ) bleibt ProxySHAP effektiv, wo andere Methoden rechnerisch nicht durchführbar oder ungenau werden.
Effizienz: Der polynomielle Extraktionsalgorithmus bietet Beschleunigungen um Größenordnungen (10x bis 1000x) im Vergleich zur Fourier-basierten Extraktion, insbesondere mit zunehmender Baumbreite.
Downstream-Aufgaben: In einer spezifischen Anwendung zur Erklärung des Vision-Sprache-Modells SigLIP-2 (FIxLIP-Spiel) zeigte ProxySHAP eine überlegene Glaubwürdigkeit (gemessen durch die Fläche unter der Insertion-Deletion-Kurve) im Vergleich zu linearen Regressionsbaselines und ProxySPEX.
Hyperparameter-Sensitivität: Die Studie hebt hervor, dass die Qualität des Proxies entscheidend ist. Die Hyperparameteroptimierung (HPO) verbessert die Leistung erheblich, und eine „HPO-informierte" Standardkonfiguration (unter Verwendung vieler flacher Bäume) wird vorgeschlagen, um Kosten und Genauigkeit auszubalancieren.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass ProxySHAP den langjährigen Zielkonflikt zwischen Geschwindigkeit und Genauigkeit bei der Interaktionsschätzung löst. Durch die Bereitstellung eines exakten Extraktionsmechanismus für Baum-Proxy und einer theoretisch fundierten Strategie für die Residualkorrektur ermöglicht es die skalierbare Quantifizierung komplexer Abhängigkeiten in modernen KI-Systemen. Die Autoren betonen, dass ihre Methode besonders wertvoll ist für:

Großskalige Anwendungen: Die Handhabung von Datensätzen mit Tausenden von Merkmalen, bei denen eine exakte Berechnung unmöglich ist.
Interaktionen höherer Ordnung: Die Bereitstellung zuverlässiger Schätzungen für Interaktionen jenseits von Paarwirkungen, die für das Verständnis von cross-modalen Abhängigkeiten (z. B. in Vision-Sprache-Modellen) und komplexen Merkmals-Synergien entscheidend sind.
Praktischer Einsatz: Angebot eines „State-of-the-Art"-Schätzers, der über verschiedene Budgetbeschränkungen und Modelltypen hinweg robust ist, unterstützt durch eine skalierbare C++-Implementierung.

Die Autoren vermerken bescheiden Einschränkungen, insbesondere dass die Approximationsqualität vom angepassten Proxy abhängt (was eine sorgfältige Hyperparameter-Tuning erfordert) und dass die Varianz der Residualkorrektur ihren Nutzen in sehr hochdimensionalen Settings für Interaktionen höherer Ordnung begrenzt. Als zukünftige Arbeit wird vorgeschlagen, alternative Proxy-Klassen und Residualschätzer zu erforschen, die sich besser skalieren lassen.