🤖 AI

PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression

Dieser Beitrag stellt PolySHAP vor, eine Methode, die KernelSHAP durch die Verwendung einer Regression höherer Polynomgrade erweitert, um Feature-Interaktionen besser zu erfassen, und die zugleich den ersten theoretischen Beweis liefert, dass gepaartes Sampling äquivalent zu PolySHAP zweiter Ordnung ist, wodurch deren empirischer Erfolg gerechtfertigt wird.

Ursprüngliche Autoren: Fabian Fumagalli, R. Teal Witter, Christopher Musco

Veröffentlicht 2026-05-14

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Fabian Fumagalli, R. Teal Witter, Christopher Musco

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 Ganze: Warum brauchen wir das?

Stellen Sie sich vor, Sie haben eine komplexe Maschine (wie ein maschinelles Lernmodell), die eine Vorhersage trifft, zum Beispiel: „Dieser Kredit sollte genehmigt werden" oder „Dieses Bild zeigt eine Katze". Sie wollen wissen, warum. Welche spezifischen Merkmale (wie Einkommen, Alter oder Pixelfarben) haben am meisten zu dieser Entscheidung beigetragen?

In der Welt der KI verwenden wir ein mathematisches Werkzeug namens Shapley-Werte, um dies zu beantworten. Denken Sie an Shapley-Werte als eine Möglichkeit, einen „Belohnung" (die Vorhersage) fair unter einem Team von Spielern (den Merkmalen) aufzuteilen, basierend darauf, wie sehr jeder einzelne dem Team zum Sieg verholfen hat.

Das Problem:
Die exakte Berechnung des Shapley-Werts ist wie der Versuch, jede einzelne mögliche Kombination von Spielern in einem Sportteam zu zählen, um zu sehen, wer am wichtigsten ist. Wenn Sie 10 Merkmale haben, gibt es über 1.000 Kombinationen. Wenn Sie 20 Merkmale haben, gibt es über eine Million. Es dauert zu lange, sie alle zu überprüfen.

Die aktuelle Lösung (KernelSHAP):
Die derzeit populäre Methode, genannt KernelSHAP, ist wie ein intelligenter Shortcut. Anstatt jede Kombination zu überprüfen, wählt sie einige zufällige Gruppen von Spielern aus, sieht, wie sie performen, und zieht dann eine gerade Linie durch die Daten, um den Rest zu erraten. Sie geht davon aus, dass die Beziehung zwischen den Merkmalen einfach und additiv ist (wie das Hinzufügen von Zutaten zu einem Kuchen: 1 Tasse Zucker + 2 Tassen Mehl = ein bestimmter Geschmack).

Die Einschränkung:
Das echte Leben ist nicht immer eine gerade Linie. Manchmal interagieren Zutaten auf seltsame Weise. Vielleicht ergeben Zucker und Mehl zusammen einen Kuchen, aber Zucker allein bewirkt nichts, und Mehl allein ist nur Staub. Eine gerade Linie kann diese „magische Kombination" (Interaktion) nicht erfassen.

Die neue Lösung: PolySHAP

Die Autoren stellen PolySHAP vor. Anstatt eine gerade Linie durch die Daten zu ziehen, zieht PolySHAP eine gekrümmte, wellige Linie (ein Polynom).

Die Analogie: Stellen Sie sich vor, Sie versuchen, die Höhe einer Pflanze basierend auf Sonnenlicht und Wasser vorherzusagen.
- KernelSHAP (Linear): Geht davon aus, dass mehr Sonne immer mehr Höhe bedeutet und mehr Wasser immer mehr Höhe bedeutet, und sie addieren sich einfach.
- PolySHAP (Polynomial): Erkennt, dass die Pflanze vielleicht nur dann groß wird, wenn sie sowohl Sonne als auch Wasser zusammen bekommt. Es erfasst diese „Interaktion".

Durch die Verwendung dieser gekrümmten Linien kann PolySHAP verstehen, dass Merkmale manchmal besser zusammenarbeiten als getrennt. Das Papier beweist, dass diese Methode eine genauere „faire Aufteilung" der Vorhersage liefert als die alte geradlinige Methode.

Der „Magische Trick": Paired Sampling

Das Papier untersucht auch einen beliebten Trick, der in der alten Methode verwendet wird, genannt Paired Sampling.

Der Trick: Anstatt nur zufällige Gruppen von Spielern auszuwählen, wählen Sie eine Gruppe aus (z. B. {Sonne, Wasser}) und wählen sofort ihr Gegenteil aus (z. B. {Keine Sonne, Kein Wasser}). Sie betrachten sie immer in Paaren.
Das Rätsel: Jeder wusste, dass dieser Trick die Ergebnisse verbessert, aber niemand wusste, warum er mathematisch so gut funktioniert.

Die Entdeckung des Papiers:
Die Autoren bewiesen eine überraschende Verbindung: Paired Sampling macht tatsächlich genau dasselbe wie PolySHAP mit einer bestimmten Art von Kurve (ein Polynom zweiten Grades), obwohl es die Kurve nie tatsächlich zeichnet.

Die Metapher: Es ist wie ein Zauberer, der ein Kaninchen erscheinen lässt. Jeder dachte, der Zauberer würde einfach ein Kaninchen aus einem Hut ziehen (ein glücklicher Zufall). Die Autoren bewiesen, dass der Zauberer tatsächlich eine versteckte mechanische Falltür (die Logik des Polynoms zweiten Grades) verwendete, um das Kaninchen erscheinen zu lassen.
Das Ergebnis: Dies erklärt, warum der „Paired Sampling"-Trick seit Jahren so erfolgreich war. Er hat diese „Interaktions"-Effekte die ganze Zeit heimlich erfasst, nur ohne die zusätzlichen mathematischen Kosten des Zeichnens der Kurve.

Was haben sie eigentlich gefunden?

Bessere Genauigkeit: Als sie PolySHAP an verschiedenen Datensätzen testeten (wie bei der Vorhersage von Hauspreisen, der Diagnose von Krankheiten oder der Identifizierung von Bildern), lieferte es konsistent genauere Erklärungen als die Standardmethode, insbesondere wenn sie der Mathematik erlaubten, komplexere Interaktionen zu betrachten (wie 3-Wege- oder 4-Wege-Kombinationen von Merkmalen).
Das „kostenlose" Upgrade: Sie zeigten, dass wenn Sie den „Paired Sampling"-Trick mit der alten Methode verwenden, Sie die gleiche Genauigkeit wie die neue „Polynom zweiten Grades"-PolySHAP-Methode erhalten, aber Sie müssen nicht die zusätzliche Arbeit des Anpasstens der Kurve leisten.
Wann man was verwendet:
- Wenn Sie nur eine schnelle, anständige Antwort wollen, ist die alte Methode mit Paired Sampling großartig.
- Wenn Sie die genaueste Antwort benötigen und über die Rechenleistung verfügen, ist die Verwendung von PolySHAP mit Kurven höheren Grades (die 3 oder 4 Merkmale betrachten, die gleichzeitig interagieren) der Gewinner.

Zusammenfassung

Das Papier stellt PolySHAP vor, eine neue Art, KI-Entscheidungen zu erklären, die nach „Teamwork" zwischen Merkmalen sucht, nicht nur nach individuellen Beiträgen. Es beweist, dass ein beliebter Shortcut namens Paired Sampling die ganze Zeit heimlich die schwere Arbeit dieser neuen Methode verrichtet hat. Im Wesentlichen haben sie uns eine bessere Karte gegeben, um die komplexen Interaktionen innerhalb von KI-Modellen zu navigieren, und erklärt, warum ein bestimmter Kompass (Paired Sampling) die ganze Zeit in die richtige Richtung zeigte.

Technischer Zusammenfassung: PolySHAP – Erweiterung von KernelSHAP durch interaktionsinformierte polynomiale Regression

Problemstellung

Shapley-Werte sind ein zentrales spieltheoretisches Werkzeug im Bereich der erklärbaren Künstlichen Intelligenz (XAI), um die Vorhersage eines Modells auf seine Eingabemerkmale zurückzuführen. Die exakte Berechnung von Shapley-Werten erfordert jedoch die Auswertung des Modells auf allen $2^d$ möglichen Merkmalsuntergruppen, was bei Modellen mit einer großen Anzahl von Merkmalen $d$ rechnerisch nicht durchführbar ist.

KernelSHAP (Lundberg & Lee, 2017) hat sich als führende Methode zur effizienten Approximation von Shapley-Werten etabliert. Es formuliert das Problem als gewichtete Kleinste-Quadrate-Regression, bei der das kooperative Spiel $\nu$ durch eine lineare Funktion angenähert wird, die an eine Stichprobe zufälliger Merkmalsuntergruppen angepasst wird. Obwohl effektiv, geht diese lineare Approximation inhärent von der Additivität der Merkmale aus und erfasst keine nichtlinearen Interaktionen zwischen Merkmalen. Folglich kann KernelSHAP suboptimale Schätzwerte liefern, wenn das zugrundeliegende Spiel signifikante Interaktionen höherer Ordnung aufweist.

Methodik: PolySHAP

Die Autoren schlagen PolySHAP vor, eine Verallgemeinerung von KernelSHAP, die das Spiel $\nu$ mittels Polynomen höheren Grades anstelle einer linearen Funktion approximiert. Dieser Ansatz modelliert nichtlineare Merkmalsinteraktionen explizit.

Kernmechanismus

Interaktionsinformierte Darstellung: Anstatt ein lineares Modell $\sum \phi_i \mathbb{1}[i \in S]$ anzupassen, passt PolySHAP ein Polynom vom Grad $k$ über den binären Merkmalsindikatoren $\mathbb{1}[i \in S]$ an. Die Approximation umfasst eine „Interaktionsgrenze" $\mathcal{I}$ , eine Teilmenge von Interaktionstermen (Teilmengen von Merkmalen mit Größe $\ge 2$ ).
$\hat{\nu}(S) \approx \sum_{T \in \mathcal{D} \cup \mathcal{I}} \phi_T \prod_{j \in T} \mathbb{1}[j \in S]$
wobei $\mathcal{D}$ einzelne Merkmale und $\mathcal{I}$ Interaktionsterme repräsentiert.
Regressionsformulierung: PolySHAP löst ein gewichtetes Kleinste-Quadrate-Problem ähnlich wie KernelSHAP, jedoch mit einer erweiterten Designmatrix, die Spalten sowohl für Haupteffekte als auch für ausgewählte Interaktionsterme enthält. Das Ziel ist die Minimierung des gewichteten $\ell_2$ -Fehlers zwischen den stichprobenartig ermittelten Spielwerten $\nu(S_\ell)$ und der polynomialen Approximation.
Extraktion von Shapley-Werten: Ein zentrales theoretisches Ergebnis (Satz 4.3) zeigt, dass die Shapley-Werte des ursprünglichen Spiels direkt aus den Koeffizienten der polynomialen Approximation gewonnen werden können. Spezifisch ist der Shapley-Wert für Merkmal $i$ die Summe des Koeffizienten für den Haupteffekt $\phi_i$ und der Koeffizienten aller Interaktionsterme, die $i$ enthalten, dividiert durch die Größe dieser Interaktionsmengen:
$\phi_i^{SV} = \phi_i + \sum_{S \in \mathcal{I}: i \in S} \frac{\phi_S}{|S|}$
Stichprobenstrategien: Die Methode unterstützt die Standardstichprobenziehung und gepaarte Stichprobenziehung (Stichprobenziehung von Untergruppen $S$ und ihren Komplementen $D \setminus S$ ). Die Autoren nutzen Leverage-Score-Stichprobenziehung, um die Schätzqualität zu verbessern, und stellen fest, dass für Interaktionen höherer Ordnung Leverage-Scores der Ordnung 1 (uniform über Untergruppengrößen) in der Praxis gut funktionieren.

Hauptbeiträge

1. Theoretische Konsistenz und Erweiterung

Die Arbeit beweist, dass PolySHAP konsistente Schätzwerte für Shapley-Werte liefert. Wenn die Anzahl der Stichproben $m$ gegen die Gesamtzahl der Untergruppen $2^d$ strebt, konvergieren die PolySHAP-Schätzwerte exakt zu den wahren Shapley-Werten (Satz 4.3). Dies steht im Gegensatz zu einigen baumbasierten Approximationsmethoden (z. B. RegressionMSR), die zusätzliche Regressionsanpassungsschritte benötigen, um Konsistenz zu erreichen.

2. Theoretische Äquivalenz von gepaarter Stichprobenziehung und 2-PolySHAP

Ein wesentlicher theoretischer Beitrag ist der Beweis, dass KernelSHAP mit gepaarter Stichprobenziehung mathematisch äquivalent zu 2-PolySHAP ist (Satz 5.1).

Wenn Untergruppen paarweise ( $S$ und $D \setminus S$ ) gestichproben werden, liefert die lineare Regressionslösung von KernelSHAP exakt dieselben Shapley-Wert-Approximationen wie eine Polynomregression zweiten Grades (2-PolySHAP).
Diese Erkenntnis liefert die erste starke theoretische Rechtfertigung für den empirischen Erfolg der gepaarten Stichprobenziehung und erklärt, dass sie implizit alle Interaktionen zweiter Ordnung erfasst, ohne explizit ein Polynom zweiten Grades anzupassen.

3. Empirische Leistung

Umfangreiche Experimente über 15 lokale Erklärungsspiele (abdeckend tabellarische, Bild- und Sprachdomänen) zeigen, dass:

Genauigkeit höherer Ordnung: Die Erhöhung des Polynomgrades (z. B. 3-PolySHAP) die Approximationsqualität (gemessen durch MSE, Precision@5 und Spearman-Korrelation) im Vergleich zu KernelSHAP (1-PolySHAP) und Permutationsstichprobenziehung konsistent verbessert, sofern das Stichprobenbudget ausreichend ist.
Effizienz gepaarter Stichprobenziehung: Unter gepaarter Stichprobenziehung erreicht KernelSHAP eine Leistung, die mit 2-PolySHAP vergleichbar ist, was die theoretische Äquivalenz validiert.
State-of-the-art-Ergebnisse: In Umgebungen mit niedriger bis moderater Dimensionalität übertrifft PolySHAP (insbesondere 3-PolySHAP) oft andere Baselines, einschließlich RegressionMSR (das auf XGBoost-Approximationen basiert) und SVARM.

Bedeutung und Behauptungen

Die Arbeit behauptet, eine prinzipielle Erweiterung des weit verbreiteten KernelSHAP-Rahmens zu bieten. Durch den Übergang von linearen zu polynomialen Approximationen adressiert PolySHAP die Einschränkung, Merkmalsinteraktionen zu ignorieren, und führt zu genaueren Erklärungen für komplexe Modelle.

Entscheidend überbrückt die Arbeit eine Lücke zwischen heuristischen Praktiken und Theorie. Indem sie beweist, dass die populäre „gepaarte Stichprobenziehung"-Heuristik äquivalent zur Modellierung von Interaktionen zweiter Ordnung ist, bieten die Autoren eine rigorose Grundlage dafür, warum diese Stichprobenstrategie in der Praxis so gut funktioniert. Die Autoren vermerken bescheiden, dass, obwohl Interaktionen höherer Ordnung die Genauigkeit verbessern, sie größere Stichprobenbudgets erfordern, und in Umgebungen mit sehr hoher Dimensionalität ( $d \ge 60$ ) die Gewinne aufgrund der kombinatorischen Explosion der Interaktionsterme bescheidener ausfallen.

Die Arbeit schließt, dass PolySHAP eine robuste, konsistente und empirisch überlegene Methode zur Schätzung von Shapley-Werten ist, insbesondere wenn das zugrundeliegende Spiel nichtlineare Merkmalsinteraktionen beinhaltet.