🤖 machine learning

Tractable Shapley Values and Interactions via Tensor Networks

Dieses Paper führt TN-SHAP ein, eine auf Tensornetzwerken basierende Methode, die Shapley-Werte und Interaktionsindizes mit polynomieller Komplexität approximiert, indem sie die erschöpfende Aufzählung von Koalitionen durch eine faktorisierte multilineare Abbildung ersetzt und dadurch signifikante Beschleunigungen gegenüber bestehenden Ansätzen bei gleichbleibender Genauigkeit erzielt.

Ursprüngliche Autoren: Farzaneh Heidari, Chao Li, Guillaume Rabusseau

Veröffentlicht 2026-06-02

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Farzaneh Heidari, Chao Li, Guillaume Rabusseau

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 ein hochentwickeltes KI-Modell), die Vorhersagen trifft. Sie möchten wissen: „Welche spezifischen Knöpfe und Regler (Features) haben diese spezifische Vorhersage verursacht, und wie haben sie zusammengewirkt?“

In der Welt der KI wird dies als Shapley-Werte bezeichnet. Es ist eine Methode, um den „Anteil“ an einer Vorhersage fair auf alle Eingangsmerkmale aufzuteilen.

Es gibt jedoch ein massives Problem mit der herkömmlichen Art und Weise, dies zu tun: Es ist zu langsam.

Die alte Art: Das „Kekskrugl-Problem“

Stellen Sie sich vor, Sie haben ein Glas mit 50 verschiedenen Arten von Keksen (Features). Um genau herauszufinden, wie viel jeder einzelne Keks zur Geschmacksgebung einer Charge beiträgt, sagt die alte Methode, dass Sie jede einzelne mögliche Kombination von Keksen probieren müssen.

Bei 10 Keksen sind das 1.024 Kombinationen.
Bei 50 Keksen sind das mehr Kombinationen, als es Atome im Universum gibt ( $2^{50}$ ).

Jede einzelne Kombination zu probieren, ist unmöglich. Es dauert ewig, weshalb wir meistens nur raten oder einige zufällige Handvoll probieren, was jedoch nicht besonders genau ist.

Die neue Art: TN-SHAP (Das „Magische Rezeptblatt“)

Das Paper stellt eine neue Methode namens TN-SHAP vor. Anstatt jede mögliche Keks-Kombination zu probieren, nutzt sie einen cleveren Trick mit Tensornetzwerken (einer Art mathematischer Struktur) und Polynomen (mathematischen Kurven).

Hier ist die Analogie:

1. Das „Magische Rezeptblatt“ (Der Surrogat)

Zuerst erstellt die Methode eine vereinfachte, „magische“ Version der komplexen Maschine. Denken Sie an dies als ein Rezeptblatt, das das Verhalten der Maschine perfekt nachahmt, aber auf eine sehr strukturierte, organisierte Weise.

Das Paper nennt dies einen Tensor Network Surrogate.
Es bricht die komplexe Maschine in eine Serie von kleineren, verbundenen Blöcken herunter (ähnlich einer Kette aus Lego-Steinen). Diese Struktur ist effizient und leicht lesbar.

2. Der „Regler“-Trick (Diagonale Selektoren)

Anstatt jede Keks-Kombination zu testen, verwendet die Methode einen speziellen Regler (eine mathematische Funktion namens Selektormatrix).

Stellen Sie sich vor, Sie haben einen Regler, der steuert, wie viel von jedem Keks in der Mischung enthalten ist.
Sie drehen den Regler auf Position 0 (kein Keks), Position 0,5 (halber Kisk), Position 1 (ganzer Keks) usw.
Da das „Magische Rezeptblatt“ auf eine spezielle mathematische Weise aufgebaut ist (genannt multilinear), erzeugt das Drehen dieses Reglers eine glatte Kurve (ein Polynom), die alle Informationen über die Interaktionen der Kekse gleichzeitig offenbart.

3. Der „Mathematische Detektiv“ (Polynom-Interpolation)

Anstatt 1.000.000 Kombinationen zu probieren, muss die Methode nur 50 spezifische Punkte auf dieser Regler-Kurve probieren.

Sie nimmt diese 50 Punkte und nutzt eine Standard-Mathematiktechnik (genannt Polynom-Interpolation), um die gesamte Kurve zu rekonstruieren.
Sobald sie die Kurve hat, kann sie sofort berechnen, wie viel Anteil jeder Keks (und jede Gruppe von Keksen) verdient.

Warum ist das eine große Sache?

Das Paper beansprucht drei wesentliche Siege für sich:

Geschwindigkeit:
- Die alte Art: Benötigt exponentielle Zeit. Wenn man ein Merkmal hinzufügt, verdoppelt sich die Zeit. Für 50 Merkmale könnte es Jahre dauhalten.
- TN-SHAP: Benötigt lineare Zeit. Es skaliert sanft nach oben. Für 50 Merkmale dauert es Millisekunden.
- Das Ergebnis: Das Paper zeigt, dass es 25- bis 1.000-mal schneller ist als die derzeit besten Methoden (wie KernelSHAP-IQ), während es das gleiche Maß an Genauigkeit beibehält.
Genauigkeit:
- Da es nicht auf zufälligem Raten (Sampling) basiert, liefert es das exakte Ergebnis für das „Magische Rezeptblatt“.
- Das Paper beweist: Wenn das „Magische Rezeptblatt“ eine gute Kopie der echten Maschine ist, wird die Erklärung der Wahrheit sehr nahe kommen.
Gruppen-Anteil (Interaktionen):
- Es sagt Ihnen nicht nur, welcher einzelne Keks wichtig ist. Es sagt Ihnen auch, wie Gruppen von Keksen zusammenwirken (z. B. „Schokolade und Vanille schmecken toll zusammen, aber Schokolade und Salz schmecken schlecht zusammen“).
- Es kann diese Gruppen-Interaktionen genauso schnell berechnen wie einzelne Merkmale.

Die Kehrseite (Einschränkungen)

Das Paper ist ehrlich darüber, wo dies am besten funktioniert:

Lokale Nachbarschaften: Das „Magische Rezeptblatt“ wird für einen spezifischen Bereich erstellt. Wenn Sie die Maschine nach einer Keks-Kombination fragen, die sie noch nie gesehen hat, könnte das Blatt nicht perfekt sein. Die Methode arbeitet am besten, wenn man eine spezifische Vorhersage und deren unmittelbare Nachbarn betrachtet.
Komplexität: Wenn die Maschine völlig chaotisch ist und kein strukturiertes Muster aufweist, muss das „Magische Rezeptblatt“ eventuell sehr groß sein, um genau zu sein. Das Paper stellte jedoch fest, dass selbst für komplexe reale Daten (wie die Vorhersage von Diabetes oder Betonfestigkeit) ein relativ kleines Blatt perfekt funktionierte.

Zusammenfassung

TN-SHAP ist wie das Anheuern eines Meisterchefs, der nicht jeden einzelnen möglichen Gang kochen muss, um das Rezept zu kennen. Stattdessen analysiert er die Zutaten, nutzt einen speziellen mathematischen Shortcut, um das Geschmacksprofil zu verstehen, und sagt Ihnen sofort, welche Zutaten die Hauptarbeit leisten und welche davon zusammenwirken. Es verwandelt eine Aufgabe, die früher Jahre dauerte, in eine, die nur einen Augenblick benötigt.

Technisches Resümee: Traktierbare Shapley-Werte und Interaktionen via Tensornetzwerke

Problemstellung

Die Erklärung von Vorhersagen maschineller Lernmodelle mittels Shapley-Werten und deren höherwertigen Verallgemeinerungen (Shapley Interaction Indices, SII) ist grundlegend für die Entscheidungsunterstützung und Interpretierbarkeit. Die Berechnung dieser Indizes ist jedoch für Modelle mit $n$ Merkmalen rechentechnisch prohibitiv, da sie traditionell die Enumeration von $O(2^n)$ Koalitionen erfordert. Bestehende Lösungen stehen vor erheblichen Trade-offs:

Strukturelle Annahmen: Methoden wie TreeSHAP oder solche für Generalisierte Additive Modelle (GAMs) sind nur für spezifische Architekturen (z. B. Bäume, lineare Modelle) exakt.
Sampling-basierte Approximationen: Ansätze wie KernelSHAP oder SHAP-IQ stützen sich auf massives Sampling, was eine präzise Varianzabstimmung erfordert und oft daran scheitert, ohne massiven Rechenaufwand auf höhere Interaktionsordnungen zu skalieren.
Amortisierte Schätzung: Methoden, die Hilfsmodelle trainieren, verursachen oft einen erheblichen Trainingsaufwand und können keine theoretischen Garantien hinsichtlich der Treue (Fidelity) der Erklärung liefern.

Die zentrale Herausforderung besteht darin, Shapley-Werte und Interaktionen exakt (oder mit kontrolliertem Fehler) für allgemeine Prädiktoren zu berechnen, ohne eine exponentielle Enumeration oder übermäßiges Sampling durchzuführen.

Methodik: TN-SHAP

Die Autoren schlagen TN-SHAP vor, eine Methode, die die erschöpfende Koalitions-Enumeration durch ein Few-Evaluation-Schema auf einem Tensornetzwerk (TN)-Surrogat ersetzt. Der Ansatz nutzt drei zentrale Erkenntnisse, um die Komplexität von $O(2^n)$ auf $O(n \cdot \text{poly}(\chi))$ zu reduzieren, wobei $\chi$ die maximale Bindungsdimension des Tensornetzwerks ist.

1. Multilineare Repräsentation und Koeffizientenextraktion

Die Methode setzt voraus, dass der Prädiktor $f$ durch eine multilineare Funktion $g$ in einem gehobenen Merkmalsraum (Lifted Feature Space) gut approximiert werden kann. In einer multilinearen Expansion gilt $f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$ , wobei die Koalitionswerte den linearen Kombinationen der Tensor-Koeffizienten entsprechen. Entscheidend ist, dass Shapley-Werte nur von größenaggregierten marginalen Beiträgen (Summen der Beiträge für Koalitionen der Größe $s$ ) abhängen und nicht von spezifischen Koalitionsmitgliedschaften.

2. Diagonale Selektoren und polynomielle Interpolation

Anstatt $2^n$ Koalitionen abzufragen, verwendet TN-SHAP diagonale Selektormatrizen $S_r(t) = \text{Diag}(t, 1)$ , die auf die gehobenen Merkmale $\tilde{x}_r = [\phi(x_r), 1]^\top$ angewendet werden.

Durch die Evaluierung des Surrogats $g$ an Punkten, an denen die Merkmale mit einem Parameter $t$ skaliert werden, aggregiert die Methode alle Koalitionen der Größe $s$ in den Koeffizienten von $t^s$ eines resultierenden Polynoms $P(t)$ .
Speziell wird für ein Zielmerkmal $i$ eine Sondierfunktion (Probe Function) $G_i(t)$ konstruiert, um den marginalen Beitrag von $i$ über alle Teilmengen anderer Merkmale hinweg zu isolieren.
Dies transformiert das kombinatorische Problem in eine polynomielle Interpolation. Durch die Evaluierung von $G_i(t)$ an $n$ distinkten Punkten (z. B. Chebyshev-Gauss-Knoten) löst das System ein Vandermonde-Linearsystem, um die größenaggregierten marginalen Beiträge $\{m_s^{(i)}\}$ zu rekonstruieren.
Der Shapley-Wert wird anschließend als gewichtete Summe dieser rekonstruierten Koeffizienten berechnet.

3. Tensornetzwerk-Surrogate

Um die Evaluierung der multilinearen Abbildung bei großem Maßstab handhabbar zu machen, wird der Koeffiziententensor in ein Tensornetzwerk (TN) (z. B. Tensor Train oder Hierarchical Tree) mit der Bindungsdimension $\chi$ faktorisiert.

Feature Maps: Um nicht-lineare Realdaten zu verarbeiten, werden skalare Merkmale mittels gelernter oder handgefertigter Abbildungen $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$ gehoben, bevor sie in das TN eintreten. Dies bewahrt die Multilinearität im gehobenen Raum und ermöglicht es dem Surrogat gleichzeitig, Nicht-Linearitäten im ursprünglichen Eingangsraum zu modellieren.
Effizienz: Jeder Vorwärtspass durch das TN kostet $O(\text{poly}(\chi))$ . Da für die Interpolation nur $O(n)$ Evaluierungen erforderlich sind, wird die Gesamtkomplexität für die Berechnung von Interaktionen der Ordnung $k$ zu einem Polynom in $n$ .

Zentrale Beiträge

Vereintes Probe-Interpolations-Schema: Ein exakter Algorithmus zur Berechnung von Shapley-Werten und $k$ -Wege-Interaktionen auf einem multilinearen TN-Surrogat unter Verwendung von nur $O(n)$ strukturierten Vorwärts-Passagen, wodurch die $O(2^n)$ Abfragen vermieden werden.
Feature-Map-erweiterte Surrogate: Ein Framework, das demonstriert, wie gelernte Feature-Lifts die erforderliche Multilinearität für exakte Berechnungen bewahren und gleichzeitig die Treue des Surrogats für nicht-lineare Modelle verbessern.
Theoretische Garantien:
- Exaktheit: Die Methode berechnet die Shapley-Werte exakt auf dem angepassten multilinearen Surrogat.
- Approximationsfehler: Der Fehler relativ zum Originalmodell ist durch den Worst-Case-Koalitions-Approximationsfehler ( $\epsilon$ ) des Surrogats begrenzt. Für Shapley-Werte gilt: $|\phi^g_i - \phi^f_i| \leq 2\epsilon$ .
- Handhabbarkeit: Nachgewiesene Reduktion der Komplexität von exponentiell auf polynomielle Zeit $O(n \cdot \text{poly}(\chi) + n^2)$ .

Experimentelle Ergebnisse

Die Autoren evaluierten TN-SHAP auf synthetischen multilinearen Funktionen sowie auf realen UCI-Regressionsdatensätzen (Concrete, Diabetes, Energy) mit MLP-Lehrern (Teachers).

Synthetische Validierung: Bei exakt multilinearen Funktionen erreichte TN-SHAP die theoretische Exaktheit mit Laufzeiten im Millisekundenbereich und übertraf KernelSHAP-IQ um Größenordnungen (z. B. 3,5 ms vs. 18,7 ms für $n=10$ ; 19,7 ms vs. 447,3 ms für $n=50$ ).
Reale Genauigkeit: Auf UCI-Datensätzen mit MLP-Lehrern:
- TN-SHAP erzielte 25–1000-fache Beschleunigungen gegenüber KernelSHAP-IQ bei vergleichbarer Genauigkeit.
- Für Attributions der ersten Ordnung ( $k=1$ ) erreichte TN-SHAP eine nahezu perfekte Kosinus-Ähnlichkeit (0,994) mit der Grundwahrheit (Ground Truth).
- Für höhere Interaktionen ( $k=2, 3$ ) behielt TN-SHAP eine wettbewerbsfähige Genauigkeit bei, während sampling-basierte Baselines mit Varianz zu kämpfen hatten oder signifikant mehr Rechenzeit benötigten, um eine ähnliche Treue zu erreichen.
Rang-Ablation: Experimente zeigten, dass ein Student-TN-Rang von $r=5-6$ ausreichte, um alle Interaktionsordnungen mit einem $R^2 > 0,99$ zu rekonstruieren, wenn der Teacher einen Rang von 16 hatte. Niedrigere Ränge führten zu einem Underfitting höherer Interaktionen.
Hochdimensionale Stabilität: In hochdimensionalen synthetischen Settings ( $D=50, 100$ ) behielt TN-SHAP eine hohe Surrogat-Treue ( $R^2 > 0,95$ ) und eine starke Top- $k$ -Merkmalsrekonstruktion unter linearen Kosten-Abfragebudgets bei.

Bedeutung und Ansprüche

Das Paper behauptet, dass TN-SHAP die Lücke zwischen der theoretischen Strenge der exakten Shapley-Berechnung und der praktischen Notwendigkeit der Effizienz schließt. Durch die Nutzung der algebraischen Struktur multilinearer Funktionen und der Effizienz von Tensornetzwerken ermöglicht die Methode:

Die Transformation eines exponentiellen Enumerationsproblems in eine geringe Anzahl strukturierter Evaluierungen.
Die Bereitstellung struktureller Garantien (via Rang-Grenzen), die die Probleme der Treue adressieren, welche bei unbeschränkten lokalen Surrogat-Methoden wie LIME häufig vorkommen.
Die Vereinigung lokaler Shapley-Erklärungen mit globalen additiven Strukturen (GAMs), da das Anpassen eines Ordnung- $k$ -Surrogats exakte $k$ -SII-Koeffizienten liefert, die den entsprechenden GAM-Termen entsprechen.
Einen skalierbaren Alternativansatz zu Sampling-basierten Methoden, insbesondere für höhere Interaktionen, bei denen die Sampling-Varianz typischerweise hoch ist.

Die Autoren merken an, dass die Performance der Methode von der Qualität des TN-Surrogats und der Wahl der Feature-Maps abhängt, empirische Ergebnisse jedoch nahelegen, dass selbst moderate Feature-Lifts und Tensor-Ränge ausreichen, um komplexe koalitionale Strukturen in der Praxis zu erfassen.