Der Shapley-Wert ist ein Lösungskonzept in der kooperativen Spieltheorie, das eine Methode zur fairen Verteilung der Gesamtgewinne oder -kosten unter einer Gruppe von Spielern bereitstellt, die zusammengearbeitet haben. Er wurde 1951 von Lloyd Shapley eingeführt und ist seitdem zu einem grundlegenden Werkzeug in der Wirtschaftswissenschaft, der Politikwissenschaft und in jüngerer Zeit auch im maschinellen Lernen zur Interpretation von Modellvorhersagen geworden. Der Wert weist jedem Spieler einen Anteil an der Gesamtauszahlung zu, der auf seiner durchschnittlichen marginalen Beitragsleistung über alle möglichen Koalitionen anderer Spieler basiert. Er ist die einzige Verteilung, die vier Schlüsseleigenschaften erfüllt: Effizienz, Symmetrie, Additivität und die Eigenschaft des Dummy-Spielers, was ihn zu einem weithin akzeptierten Standard für faire Zuteilung macht.
Im Kontext des maschinellen Lernens wird der Shapley-Wert verwendet, um einzelne Vorhersagen zu erklären, indem der Beitrag jedes Merkmals zur Ausgabe des Modells attribuiert wird. Dieser Ansatz, der oft als SHAP (SHapley Additive exPlanations) bezeichnet wird, bietet einen einheitlichen Rahmen für die Merkmalsbedeutung, der sowohl theoretisch fundiert als auch praktisch anwendbar ist. Die rechnerische Komplexität der Berechnung exakter Shapley-Werte wächst exponentiell mit der Anzahl der Merkmale, was zur Entwicklung verschiedener Näherungsmethoden geführt hat.
Definition und Formel
Formal betrachtet man ein kooperatives Spiel mit einer Menge von Spielern \( N \) und einer Wertfunktion \( v \), die jeder Teilmenge (Koalition) \( S \subseteq N \) eine reelle Zahl zuordnet. Der Shapley-Wert für Spieler \( i \) ist definiert als:
\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S)) \]
wobei \( n = |N| \). Diese Formel kann als die durchschnittliche marginale Beitragsleistung von Spieler \( i \) über alle möglichen Reihenfolgen interpretiert werden, in denen die Koalition gebildet werden kann. Eine äquivalente Formulierung summiert über alle \( n! \) Permutationen der Spieler, wobei \( P_i^R \) die Menge der Spieler ist, die \( i \) in der Reihenfolge \( R \) vorausgehen:
\[ \phi_i(v) = \frac{1}{n!} \sum_R \left[ v(P_i^R \cup \{i\}) - v(P_i^R) \right] \]
Die Wertfunktion \( v(S) \) repräsentiert die Gesamtauszahlung, die die Koalition \( S \) durch Zusammenarbeit erreichen kann. Der Shapley-Wert verteilt den Gesamtwert \( v(N) \) unter allen Spielern und stellt sicher, dass jeder Spieler seinen durchschnittlichen Beitrag zum Gesamtergebnis erhält.
Eigenschaften
Der Shapley-Wert ist das einzige Lösungskonzept, das die folgenden vier Axiome erfüllt, die als wesentlich für eine faire Verteilung gelten:
- Effizienz: Die Summe aller Shapley-Werte entspricht dem Gesamtwert der großen Koalition, \( \sum_{i \in N} \phi_i(v) = v(N) \). Dies stellt sicher, dass die gesamte Auszahlung verteilt wird.
- Symmetrie: Wenn zwei Spieler \( i \) und \( j \) gleichermaßen zu allen Koalitionen beitragen (d. h. \( v(S \cup \{i\}) = v(S \cup \{j\}) \) für alle \( S \subseteq N \setminus \{i,j\} \)), dann erhalten sie denselben Shapley-Wert. Dies garantiert Fairness unter identischen Beitragenden.
- Additivität: Für zwei beliebige Spiele \( v \) und \( w \) ist der Shapley-Wert des kombinierten Spiels \( v + w \) die Summe der Shapley-Werte der einzelnen Spiele, \( \phi_i(v + w) = \phi_i(v) + \phi_i(w) \). Diese Eigenschaft ermöglicht die Zerlegung komplexer Spiele.
- Eigenschaft des Dummy-Spielers: Wenn ein Spieler \( i \) keiner Koalition einen Wert hinzufügt (d. h. \( v(S \cup \{i\}) = v(S) \) für alle \( S \subseteq N \setminus \{i\} \)), dann gilt \( \phi_i(v) = 0 \). Dies stellt sicher, dass Spieler, die keinen Beitrag leisten, nichts erhalten.
Diese Eigenschaften machen den Shapley-Wert zu einer einzigartigen und prinzipientreuen Methode zur Zuteilung von Anerkennung oder Kosten unter Teilnehmern.
Anwendungen im maschinellen Lernen
Im maschinellen Lernen wird der Shapley-Wert angewendet, um Modellvorhersagen zu interpretieren, indem jedes Merkmal als Spieler und die Ausgabe des Modells als Wertfunktion behandelt wird. Für eine gegebene Vorhersage quantifiziert der Shapley-Wert eines Merkmals dessen Beitrag zur Differenz zwischen der Modellausgabe und der durchschnittlichen Vorhersage. Dieser Ansatz, bekannt als SHAP, wurde 2017 von Scott Lundberg und Su-In Lee populär gemacht. SHAP-Werte bieten ein einheitliches Maß für die Merkmalsbedeutung, das mit den Axiomen des Shapley-Werts konsistent ist, was sie zu einem zuverlässigen Werkzeug für die Modellinterpretierbarkeit macht.
Die Verwendung von Shapley-Werten im maschinellen Lernen hat erheblich zugenommen, insbesondere in Bereichen, in denen das Verständnis von Modellentscheidungen entscheidend ist, wie Finanzen, Gesundheitswesen und autonome Systeme. Beispielsweise können SHAP-Werte bei der Kreditwürdigkeitsprüfung aufzeigen, welche Faktoren eine Kreditgenehmigungsentscheidung am meisten beeinflussen, was bei der Einhaltung gesetzlicher Vorschriften und Fairness-Audits hilft. In der medizinischen Diagnostik helfen sie Klinikern zu verstehen, warum ein Modell einen bestimmten Zustand vorhersagt, was das Vertrauen in KI-gestützte Entscheidungen erhöht.
Rechnerische Herausforderungen
Die Berechnung exakter Shapley-Werte erfordert die Auswertung der Wertfunktion für alle \( 2^n \) möglichen Koalitionen, was für Modelle mit vielen Merkmalen rechnerisch nicht durchführbar ist. Für ein Modell mit \( n \) Merkmalen beträgt die Komplexität \( O(2^n) \), was eine exakte Berechnung über ein paar Dutzend Merkmale hinaus unpraktisch macht. Um dies zu adressieren, wurden mehrere Näherungsmethoden entwickelt:
- Monte-Carlo-Stichproben: Zufälliges Stichprobenziehen von Permutationen der Merkmale und Mitteln der marginalen Beiträge, was eine unverzerrte Schätzung mit kontrollierbarer Varianz liefert.
- TreeSHAP: Ein Algorithmus, der speziell für baumbasierte Modelle (z. B. Random Forests, Gradient Boosting) entwickelt wurde und exakte Shapley-Werte in polynomieller Zeit berechnet, indem er die Struktur von Entscheidungsbäumen ausnutzt.
- KernelSHAP: Eine modellagnostische Methode, die eine gewichtete lineare Regression zur Näherung von Shapley-Werten verwendet und für jedes Black-Box-Modell geeignet ist.
- Gradientenbasierte Methoden: Für neuronale Netze können Näherungen unter Verwendung von Gradienten oder Aufmerksamkeitsmechanismen schnelle Schätzungen liefern, obwohl sie möglicherweise nicht alle Shapley-Axiome erfüllen.
Diese Näherungen haben es ermöglicht, Shapley-Werte auf große maschinelle Lernmodelle anzuwenden, einschließlich tiefer neuronaler Netze und großer Sprachmodelle, bei denen Interpretierbarkeit zunehmend wichtig ist.
Verwandte Konzepte und Erweiterungen
Der Shapley-Wert wurde auf verschiedene Weise erweitert und angepasst, um unterschiedliche Bedürfnisse zu adressieren. In der kooperativen Spieltheorie sind der Shapley-Shubik-Machtindex und der Banzhaf-Machtindex spezialisierte Anwendungen für Abstimmungsspiele. Im maschinellen Lernen wurde SHAP erweitert, um Interaktionen zwischen Merkmalen zu behandeln, und bietet Attribuierungen zweiter Ordnung, die synergistische Effekte erfassen. Darüber hinaus wurde das Konzept angewendet, um das Verhalten von großen Sprachmodellen zu erklären, wo es hilft zu identifizieren, welche Teile des Eingabetextes die generierte Ausgabe am meisten beeinflussen.
Der Shapley-Wert ist auch mit anderen Attributionsmethoden wie LIME (Local Interpretable Model-agnostic Explanations) verwandt, bietet jedoch stärkere theoretische Garantien aufgrund seiner axiomatischen Grundlage. Während LIME sich auf lokale Treue konzentriert, stellt SHAP Konsistenz und lokale Genauigkeit sicher, was es in vielen praktischen Anwendungen zur bevorzugten Wahl macht.
Historischer Kontext
Lloyd Shapley führte das Konzept in seinem Artikel "A Value for n-Person Games" von 1951 ein, der das Fundament für die kooperative Spieltheorie legte. Seine Arbeit brachte ihm 2012 den Nobelpreis für Wirtschaftswissenschaften ein, den er sich mit Alvin Roth für Beiträge zur Theorie stabiler Allokationen und zur Praxis des Marktdesigns teilte. Der Shapley-Wert ist seitdem zu einem Eckpfeiler der Wirtschaftstheorie geworden und beeinflusst Bereiche wie Kostenallokation, Gewinnverteilung und Netzwerkanalyse.
In den 2010er Jahren brachten der Aufstieg des maschinellen Lernens und der Bedarf an Modellinterpretierbarkeit den Shapley-Wert ins Rampenlicht. Forscher erkannten, dass die Axiome der Fairness in kooperativen Spielen mit den Anforderungen zur Erklärung von Modellvorhersagen übereinstimmen, was zur Entwicklung von SHAP und seiner weit verbreiteten Übernahme führte. Heute ist der Shapley-Wert ein Standardwerkzeug im Werkzeugkasten von Datenwissenschaftlern und KI-Forschern und überbrückt die Lücke zwischen Spieltheorie und moderner künstlicher Intelligenz.
Siehe auch
- Maschinelles Lernen
- Künstliche Intelligenz
- Deep Learning
- Neuronales Netz
- Modellbereinigung
- Datenanreicherung
Referenzen
- Shapley, L. S. (1951). "A Value for n-Person Games." In Contributions to the Theory of Games, volume II.
- Lundberg, S. M., & Lee, S.-I. (2017). "A Unified Approach to Interpreting Model Predictions." Advances in Neural Information Processing Systems.
- Strumbelj, E., & Kononenko, I. (2014). "Explaining Prediction Models and Individual Predictions with Feature Contributions." Knowledge and Information Systems.