🤖 machine learning

Shapley Value Approximation Based on k-Additive Games

Dieser Beitrag stellt SVA $k_{\text{ADD}}$ vor, eine neuartige Näherungsmethode, die Shapley-Werte schätzt, indem ein $k$ -additives Surrogat-Spiel angepasst wird, um die exponentielle rechnerische Komplexität zu überwinden, die bei exakten Berechnungen für faire Aufteilung und Interpretierbarkeit im maschinellen Lernen inhärent ist.

Ursprüngliche Autoren: Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

Veröffentlicht 2026-05-13

📖 5 Min. Lesezeit🧠 Tiefgang

CC0 1.0

Ursprüngliche Autoren: Guilherme Dean Pelegrina, Patrick Kolpaczki, Eyke Hüllermeier

Originalarbeit unter CC0 1.0 der Gemeinfreiheit gewidmet (http://creativecommons.org/publicdomain/zero/1.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: Den Kuchen fair aufteilen

Stellen Sie sich vor, Sie und eine Gruppe von Freunden betreiben einen Limonadenstand. Am Ende des Tages machen Sie Gewinn. Die große Frage lautet: Wer verdient wie viel vom Geld?

Hat die Person, die die Zitronen gepresst hat, die meiste Arbeit geleistet?
Hat die Person, die am Schild stand, die meisten Kunden angelockt?
Hat die Person, die den Zucker mitgebracht hat, dem Getränk einen besseren Geschmack verliehen?

In der Welt des maschinellen Lernens (KI) ist dies das gleiche Problem. Ein KI-Modell trifft eine Vorhersage (wie die Diagnose einer Krankheit oder die Einschätzung, ob eine E-Mail Spam ist). Wir wollen wissen: Welcher spezifische Datenpunkt (Merkmal) war für diese Vorhersage verantwortlich?

Der „Shapley-Wert" ist eine mathematische Formel, die von einem Spieltheoretiker namens Lloyd Shapley erfunden wurde. Er ist der Goldstandard für Fairness. Er berechnet genau, wie viel jeder „Spieler" (Merkmal) zum Endergebnis beigetragen hat, indem er jede mögliche Kombination von Spielern betrachtet.

Das Problem: Die Mathematik ist zu schwer

Hier liegt der Haken: Um den Shapley-Wert perfekt zu berechnen, muss man jede einzelne mögliche Teamkombination überprüfen.

Wenn Sie 10 Freunde haben, gibt es 1.024 Kombinationen.
Wenn Sie 20 Freunde haben, gibt es über eine Million Kombinationen.
Wenn Sie 50 Freunde haben, ist die Zahl so riesig, dass die Berechnung länger dauern würde als das Alter des Universums.

Da moderne KI-Modelle oft Hunderte oder Tausende von Merkmalen haben, ist die Berechnung des exakten Shapley-Werts unmöglich. Es ist wie der Versuch, jedes Sandkorn an einem Strand zu zählen, um den Wert des Strandes fair aufzuteilen. Wir brauchen einen Abkürzungsweg, aber dieser muss genau genug sein, um vertrauenswürdig zu sein.

Die Lösung: SVAkADD (Die „intelligente Surrogat"-Methode)

Die Autoren dieses Papiers schlagen eine neue Methode namens SVAkADD vor. Anstatt jeden Sandkorn zu zählen, bauen sie ein vereinfachtes Modell (ein „Surrogat"), das das echte Spiel nachahmt, aber viel einfacher zu lösen ist.

So gehen sie vor, unter Verwendung einer kreativen Analogie:

1. Die „Teamwork"-Annahme (k-Additivität)

Die Autoren gehen davon aus, dass, obwohl der Beitrag jedes Einzelnen zählt, komplexes Teamwork normalerweise bei einer bestimmten Größe aufhört.

1-additiv: Nur die individuelle Leistung zählt. (Sie sind gut in Ihrem Job, unabhängig davon, mit wem Sie arbeiten).
2-additiv: Paare zählen. (Sie und Ihr bester Freund arbeiten großartig zusammen, aber eine Gruppe von drei könnte chaotisch werden).
3-additiv: Kleine Gruppen zählen. (Ein Trio funktioniert gut, aber ein Komitee aus zehn Personen ist zu unübersichtlich, um einen einzigartigen „magischen" Effekt zu haben).

Das Papier nennt dies k-Additivität. Sie gehen davon aus, dass Interaktionen zwischen 4, 5 oder 10 Personen gleichzeitig so selten oder vernachlässigbar sind, dass wir sie ignorieren können. Dies verwandelt ein mathematisch unmögliches Problem in ein handhabbares.

2. Der „Geschmackstest" (Stichprobenziehung)

Anstatt jede mögliche Limonadenrezeptur (Koalition) zu testen, nehmen die Forscher eine zufällige Stichprobe von Rezepten.

Sie mischen einige spezifische Kombinationen von Zutaten.
Sie probieren das Ergebnis (berechnen den Wert).
Sie verwenden diese wenigen Geschmackstests, um ihr vereinfachtes Modell zu „fitten".

3. Die „magische Formel" (Die Optimierung)

Sobald sie die Geschmackstests haben, lösen sie ein spezifisches mathematisches Rätsel (ein Optimierungsproblem), um die Parameter ihres vereinfachten Modells zu finden.

Der coole Teil: Die Autoren haben mathematisch bewiesen, dass, wenn sie die richtigen „Gewichte" für ihre Geschmackstests wählen, die Antwort, die sie aus diesem vereinfachten Modell erhalten, genau dieselbe ist wie der perfekte Shapley-Wert, wenn sie jede einzelne Kombination getestet hätten.
Obwohl sie komplexe 10-Personen-Interaktionen ignorieren, garantiert die Mathematik, dass die endgültigen „fairen Anteile" für die getesteten Szenarien korrekt herauskommen.

Warum dies besser ist als andere Abkürzungen

Andere Methoden versuchen, die Antwort zu erraten, indem sie zufällig raten und mitteln (wie beim Würfeln viele Male).

Die Methode des Papiers: Es ist wie das Erstellen eines Grundrisses basierend auf ein paar Messungen. Sobald der Grundriss erstellt ist, können Sie die Antwort sofort ablesen.
Das Ergebnis: Das Papier zeigt, dass ihre Methode viel schneller konvergiert (genau wird) als die Methoden des zufälligen Rätens. Sie benötigen weniger „Geschmackstests" (Stichproben), um eine zuverlässige Antwort zu erhalten.

Was sie gefunden haben (Die Ergebnisse)

Die Forscher testeten dies an realen Datensätzen (wie der Vorhersage des Überlebens der Titanic, der Weinqualität oder der Brustkrebsfrüherkennung).

Geschwindigkeit vs. Genauigkeit: Sie fanden heraus, dass die Annahme, dass Interaktionen in Gruppen von 3 auftreten (3-additiv), normalerweise der „Sweet Spot" ist. Sie war komplex genug, um genau zu sein, aber einfach genug, um schnell zu sein.
Die Konkurrenz schlagen: In vielen Tests war ihre Methode (SVAkADD) genauer als die aktuellen Top-Methoden (wie KernelSHAP), wenn die gleiche Rechenzeit oder die gleichen Datenstichproben zur Verfügung standen.
Keine speziellen Regeln erforderlich: Diese Methode funktioniert bei jedem beliebigen Spiel oder KI-Modell. Es ist egal, ob die Daten medizinische Aufzeichnungen, Aktienkurse oder Sportstatistiken betreffen.

Zusammenfassung in einem Satz

Das Papier stellt eine neue Methode vor, um das Verdienst von KI-Merkmalen fair aufzuteilen, indem ein vereinfachtes „Teamwork-Modell" erstellt wird, das übermäßig komplexe Gruppeninteraktionen ignoriert, was es ermöglicht, faire Anteile schnell und genau zu berechnen, ohne jede einzelne Möglichkeit überprüfen zu müssen.

Technische Zusammenfassung: Shapley-Wert-Näherung basierend auf k-additiven Spielen

Problemstellung

Der Shapley-Wert ist die Standardlösung für faire Teilungsprobleme und wird in der erklärbaren Künstlichen Intelligenz (XAI) weit verbreitet eingesetzt, um den individuellen Beitrag von Merkmalen oder Datenpunkten zur Leistung eines Modells zu quantifizieren. Seine exakte Berechnung erfordert jedoch die Auswertung aller $2^n$ möglichen Koalitionen von $n$ Spielern, was zu einer exponentiellen rechnerischen Komplexität führt. Dies macht die exakte Berechnung für Modelle mit einer moderaten Anzahl von Merkmalen oder bei der Auswertung komplexer, ressourcenintensiver Modelle unpraktikabel. Folglich sind Näherungsmethoden erforderlich, doch bestehende Ansätze haben oft Schwierigkeiten, einen Ausgleich zwischen rechnerischer Effizienz und der Genauigkeit der resultierenden Wichtigkeitswerte zu finden.

Methodik: SVAkADD

Die Autoren schlagen SVAkADD (Shapley Value Approximation under k-additivity) vor, eine neuartige Methode, die Shapley-Werte approximiert, indem sie ein strukturiertes k-additives Surrogat-Spiel an eine Stichprobe von Koalitionswerten anpasst.

Kernkonzept: k-Additivität

Anstatt den Shapley-Wert direkt durch Monte-Carlo-Sampling von Randbeiträgen zu schätzen, geht SVAkADD davon aus, dass das zugrunde liegende Spiel durch ein k-additives Spiel approximiert werden kann. In einem solchen Spiel werden Interaktionsindizes (Shapley-Interaktionen) für Koalitionen größer als Größe $k$ als null angenommen.

Darstellung: Die Wertfunktion $\nu_k$ des Surrogat-Spiels wird als lineare Transformation der Shapley-Interaktionsindizes $I(B)$ für alle Koalitionen $B$ mit $|B| \leq k$ ausgedrückt.
Parameterreduktion: Diese Annahme reduziert die Anzahl der Parameter drastisch, die zur Definition des Spiels erforderlich sind, von $2^n$ auf eine polynomielle Anzahl (z. B. $O(n^k)$ ), wodurch die Optimierung handhabbar wird.

Optimierungsrahmen

Die Methode formuliert die Approximation als eingeschränktes gewichtetes Kleinste-Quadrate-Problem:

Ziel: Minimierung des gewichteten quadrierten Fehlers zwischen den beobachteten Koalitionswerten $\nu(A)$ aus dem ursprünglichen Spiel und den vom k-additiven Surrogat $\nu_k(A)$ vorhergesagten Werten.
Nebenbedingungen: Die Optimierung erzwingt das Effizienz-Axiom, wodurch sichergestellt wird, dass die Summe der Shapley-Werte des Surrogats der Differenz zwischen dem Wert der Großkoalition und dem Wert der leeren Menge entspricht ( $\nu(N) - \nu(\emptyset)$ ).
Gewichtung: Die Autoren leiten analytisch spezifische Gewichte $w^*_A = \binom{n-2}{|A|-1}^{-1}$ für das Kleinste-Quadrate-Problem her. Sie beweisen, dass, wenn alle Koalitionen beobachtet würden, die Lösung dieses spezifischen Optimierungsproblems die exakten Shapley-Werte liefert, unabhängig davon, ob das ursprüngliche Spiel tatsächlich k-additiv ist.

Algorithmus

Der SVAkADD-Algorithmus läuft wie folgt ab:

Sampling: Er bewertet deterministisch die leere Menge $\emptyset$ und die Großkoalition $N$ . Anschließend werden $T-2$ zusätzliche Koalitionen aus der Potenzmenge (unter Ausschluss von $\emptyset$ und $N$ ) basierend auf einer Wahrscheinlichkeitsverteilung proportional zu den abgeleiteten Gewichten $w^*_A$ gesampelt.
Anpassung: Er löst das eingeschränkte gewichtete Kleinste-Quadrate-Problem unter Verwendung der gesampelten Daten, um die Interaktionsindizes $I(B)$ für $|B| \leq k$ zu schätzen.
Extraktion: Die Shapley-Werte für das Surrogat-Spiel werden unmittelbar als die Interaktionsindizes für Singletons ( $I(\{i\})$ ) gewonnen, die als Schätzwerte für das ursprüngliche Spiel dienen.

Hauptbeiträge

Neuartige Näherungsmethode: Einführung von SVAkADD, das ein k-additives Surrogat-Spiel an gesampelte Daten anpasst und eine strukturierte Alternative zum direkten Sampling von Randbeiträgen bietet.
Theoretische Fundierung: Analytischer Nachweis, dass für $k=1, 2, 3$ die vorgeschlagene gewichtete Kleinste-Quadrate-Optimierung die exakten Shapley-Werte liefert, wenn die vollständige Menge der Koalitionen beobachtet wird. Dies etabliert, dass k-Additivität ein Werkzeug zur Approximation ist und keine einschränkende Annahme über die Struktur des Spiels darstellt.
Modell- und Domänenunabhängigkeit: Die Methode erfordert keine spezifischen strukturellen Eigenschaften der Wertfunktion, was sie auf jedes kooperative Spiel anwendbar macht, einschließlich lokaler und globaler Merkmals-Erklärungen im maschinellen Lernen.
Empirische Evaluation: Umfassender Vergleich gegen State-of-the-Art-Baselines (KernelSHAP, Stratified SVARM, Stratified sampling) über verschiedene Datensätze und Erklärungsarten (global, lokal, unüberwacht).

Experimentelle Ergebnisse

Die Autoren evaluierten SVAkADD auf Datensätzen mit 9 bis 14 Merkmalen über globale, lokale und unüberwachte Aufgaben hinweg.

Konvergenz: Die Methode zeigt konkurrenzfähige Leistung. Obwohl sie bei sehr geringen Stichprobenbudgets im Vergleich zu einigen Baselines einen höheren Fehler aufweisen kann, konvergiert sie mit steigendem Budget schneller zu den exakten Shapley-Werten, insbesondere bei lokalen Zuordnungsaufgaben auf den Datensätzen Adult und ImageNet.
Wahl von $k$ : Die Experimente verdeutlichen einen Kompromiss zwischen Flexibilität und Konvergenzgeschwindigkeit.
- Niedriges $k$ (1 oder 2) konvergiert oft langsam aufgrund unzureichender Flexibilität zur Modellierung komplexer Merkmalsinteraktionen.
- Höheres $k$ (3 oder 4) konvergiert im Allgemeinen deutlich schneller und übertrifft Modelle niedrigerer Ordnung nach wenigen Stichproben.
- Die Autoren schlagen $k=3$ als bevorzugten Standard vor, der einen guten Ausgleich zwischen Fehlerreduktion und der Anzahl der erforderlichen Parameter bietet.
Vergleich: SVAkADD konkurriert konsistent mit KernelSHAP und Stratified SVARM oder übertrifft diese, insbesondere in Szenarien, die hohe Präzision bei moderaten Stichprobenbudgets erfordern.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass SVAkADD einen theoretisch fundierten und praktisch effektiven Ansatz zur Shapley-Wert-Näherung bietet. Durch die Nutzung der Struktur k-additiver Spiele verwandelt die Methode das Schätzproblem in eine polynomielle Optimierung, die unter spezifischen Gewichtsbedingungen eine exakte Wiederherstellung garantiert.

Die Autoren betonen, dass ihr Ansatz modellagnostisch und domänenunabhängig ist und jede Formulierung eines kooperativen Spiels bewältigen kann. Sie kommen zu dem Schluss, dass zwar keine einzelne Näherungsmethode in allen Szenarien dominiert (abhängig von Datensatz, Aufgabe und Budget), SVAkADD jedoch eine robuste Alternative bietet, die die theoretischen Eigenschaften von Shapley-Interaktionen nutzt, um hohe Genauigkeit zu erreichen. Die Arbeit weist zudem darauf hin, dass die Methode bei $k \geq 2$ natürlicherweise Schätzwerte für Interaktionseffekte (Redundanz oder Komplementarität) liefert und somit über die individuelle Merkmalswichtigkeit hinaus zusätzliche Interpretierbarkeit bietet.