Technische Samenvatting: Benadering van de Shapley-waarde op basis van k-additieve spellen

Probleemstelling

De Shapley-waarde is de standaardoplossing voor eerlijke verdelingsproblemen en wordt breed toegepast in Explainable AI (XAI) om de individuele bijdrage van kenmerken of datapunten aan de prestaties van een model te kwantificeren. De exacte berekening vereist echter het evalueren van alle $2^n$ mogelijke coalities van $n$ spelers, wat resulteert in een exponentiële computationele complexiteit. Dit maakt een exacte berekening onhaalbaar voor modellen met een gemiddeld aantal kenmerken of bij het evalueren van complexe, hulpbronnenintensieve modellen. Bijgevolg zijn benaderingsmethoden noodzakelijk, maar bestaande benaderingen worstelen vaak met het vinden van een evenwicht tussen computationele efficiëntie en de nauwkeurigheid van de resulterende belangrijkheidsscores.

Methodologie: SVAkADD

De auteurs stellen SVAkADD (Shapley Value Approximation under k-additivity) voor, een nieuwe methode die Shapley-waarden benadert door een gestructureerd k-additief surrogaatspel aan te passen aan een bemonsterde subset van coalitiewaarden.

Kernconcept: k-Additiviteit

In plaats van de Shapley-waarde direct te schatten via Monte Carlo-bemonstering van marginale bijdragen, gaat SVAkADD ervan uit dat het onderliggende spel kan worden benaderd door een k-additief spel. In een dergelijk spel worden interactie-indices (Shapley-interacties) voor coalities groter dan grootte $k$ verondersteld nul te zijn.

• Representatie: De waardefunctie $\nu_k$ van het surrogaatspel wordt uitgedrukt als een lineaire transformatie van Shapley-interactie-indices $I(B)$ voor alle coalities $B$ waarbij $|B| \leq k$.
• Parameterreductie: Deze aanname reduceert het aantal parameters dat nodig is om het spel te definiëren drastisch van $2^n$ naar een polynoomiaal aantal (bijvoorbeeld $O(n^k)$), waardoor de optimalisatie hanteerbaar wordt.

Optimalisatiekader

De methode formuleert de benadering als een geconstrueerd gewogen kleinste-kwadratenprobleem:

1. Doel: Minimaliseer de gewogen kwadratische fout tussen de waargenomen coalitiewaarden $\nu(A)$ uit het oorspronkelijke spel en de waarden voorspeld door het k-additieve surrogaat $\nu_k(A)$.
2. Beperkingen: De optimalisatie handhaaft het efficiëntieaxioma, waarbij wordt gegarandeerd dat de som van de Shapley-waarden van het surrogaat gelijk is aan het verschil tussen de waarde van de grote coalitie en die van de lege verzameling ($\nu(N) - \nu(\emptyset)$).
3. Gewichtsbepaling: De auteurs leiden analytisch specifieke gewichten af $w^*_A = \binom{n-2}{|A|-1}^{-1}$ voor het kleinste-kwadratenprobleem. Ze bewijzen dat, als alle coalities worden waargenomen, het oplossen van deze specifieke optimalisatie de exacte Shapley-waarden oplevert, ongeacht of het oorspronkelijke spel werkelijk k-additief is.

Algorithmus

Het SVAkADD-algoritme werkt als volgt:

1. Bemonstering: Het evalueert op deterministische wijze de lege verzameling $\emptyset$ en de grote coalitie $N$. Vervolgens worden $T-2$ aanvullende coalities bemonsterd uit de machtsverzameling (exclusief $\emptyset$ en $N$) op basis van een kansverdeling die evenredig is met de afgeleide gewichten $w^*_A$.
2. Aanpassing: Het lost het geconstrueerde gewogen kleinste-kwadratenprobleem op met behulp van de bemonsterde data om de interactie-indices $I(B)$ te schatten voor $|B| \leq k$.
3. Extrahering: De Shapley-waarden voor het surrogaatspel worden direct verkregen als de singleton-interactie-indices ($I(\{i\})$), die dienen als schattingen voor het oorspronkelijke spel.

Belangrijkste Bijdragen

1. Nieuwe Benaderingsmethode: Introductie van SVAkADD, dat een k-additief surrogaatspel aanpast aan bemonsterde data, en een gestructureerd alternatief biedt voor directe bemonstering van marginale bijdragen.
2. Theoretische Fundamenten: Analytisch bewijs dat voor $k=1, 2, 3$ de voorgestelde gewogen kleinste-kwadratenoptimalisatie de exacte Shapley-waarden oplevert wanneer de volledige set coalities wordt waargenomen. Dit vestigt dat k-additiviteit een hulpmiddel is voor benadering en geen restrictieve aanname over de structuur van het spel.
3. Model- en Domeinonafhankelijkheid: De methode vereist geen specifieke structurele eigenschappen van de waardefunctie, waardoor deze toepasbaar is op elk coöperatief spel, inclusief zowel lokale als globale kenmerkenverklaringen in machine learning.
4. Empirische Evaluatie: Uitgebreide vergelijking met state-of-the-art baselines (KernelSHAP, Stratified SVARM, Stratified sampling) over diverse datasets en verklaringstypen (globaal, lokaal, onbeheerd).

Experimentele Resultaten

De auteurs hebben SVAkADD geëvalueerd op datasets variërend van 9 tot 14 kenmerken voor globale, lokale en onbeheerde taken.

• Convergentie: De methode toont concurrerende prestaties. Hoewel het bij zeer lage bemonsteringsbudgetten mogelijk een hogere fout vertoont dan sommige baselines, convergeert het sneller naar de exacte Shapley-waarden naarmate het budget toeneemt, met name voor lokale toewijzingstaken op de Adult- en ImageNet-datasets.
• Keuze van $k$: De experimenten benadrukken een afweging tussen flexibiliteit en convergentiesnelheid.
  • Een lage $k$ (1 of 2) convergeert vaak traag vanwege onvoldoende flexibiliteit om complexe kenmerkinteracties te modelleren.
  • Een hogere $k$ (3 of 4) convergeert over het algemeen aanzienlijk sneller en presteert na enkele bemonsteringen beter dan modellen van lagere orde.
  • De auteurs suggereren $k=3$ als een voorkeursstandaard, die een goede balans biedt tussen foutreductie en het aantal benodigde parameters.
• Vergelijking: SVAkADD concurreert consequent met of overtreft KernelSHAP en Stratified SVARM, met name in scenario's die hoge precisie vereisen met gemiddelde bemonsteringsbudgetten.

Betekenis en Claims

Het artikel claimt dat SVAkADD een theoretisch onderbouwde en praktisch effectieve aanpak biedt voor de benadering van Shapley-waarden. Door gebruik te maken van de structuur van k-additieve spellen, transformeert de methode het schattingsprobleem naar een optimalisatie in polynoomiale tijd die exacte herstel garandeert onder specifieke wegingsvoorwaarden.

De auteurs benadrukken dat hun aanpak model-agnostisch en domeinonafhankelijk is en elk coöperatief spel kan verwerken. Ze concluderen dat hoewel geen enkele benaderingsmethode in alle scenario's domineert (afhankelijk van dataset, taak en budget), SVAkADD een robuust alternatief biedt dat gebruikmaakt van de theoretische eigenschappen van Shapley-interacties om hoge nauwkeurigheid te bereiken. Het artikel merkt ook op dat de methode op natuurlijke wijze schattingen biedt voor interactie-effecten (redundantie of complementariteit) wanneer $k \geq 2$, wat aanvullende interpreteerbaarheid biedt naast individuele kenmerkenbelang.