Technische Samenvatting: Een Afwijkende Schatter voor Shapley-waarden

Probleemstelling

De Shapley-waarde is het standaardkader voor attributie in machine learning, gebruikt voor feature-belangrijkheid, datavalutatie en causale inferentie. De exacte berekening ervan is echter over het algemeen onhandelbaar vanwege het exponentiële aantal coalities ($2^d$) die vereist zijn voor evaluatie. Hoewel er benaderingsmethoden bestaan, vertrouwen de meest effectieve schatters vaak op "gepaarde sampling" (het samplen van een coalitie $S$ en haar complement $S^c$), een heuristiek die de nauwkeurigheid empirisch verbetert maar die een rigoureuze theoretische rechtvaardiging mist voor waarom dit werkt, met name met betrekking tot hogere-orde interacties. Bovendien kampen bestaande hogere-orde polynoomregressiemethoden (bijv. PolySHAP) met een schaalbaarheidsprobleem waarbij de computationele kosten kwadratisch groeien met de omvang van de polynoombasis, wat hun toepassing in hoogdimensionale instellingen beperkt.

Methodologie

De auteurs stellen OddSHAP voor, een nieuwe schatter die gebruikmaagt van een fundamentele structurele eigenschap van de Shapley-waarde: deze hangt uitsluitend af van het oneven component van de waardefunctie $f$.

Theoretische Fundering

1. Oneven-Even Decompositie: Elke verzamlingsfunctie $f$ kan uniek worden gedecomposeerd in een oneven component ($f_{odd}$) en een even component ($f_{even}$), waarbij $f_{odd}(S) = -f_{odd}(S^c)$ en $f_{even}(S) = f_{even}(S^c)$.
2. Eigenschap van de Shapley-waarde: De auteurs bewijzen dat $\phi_i(f) = \phi_i(f_{odd})$ voor alle spelers $i$. De even component draagt nul bij aan de Shapley-waarde.
3. Mechanisme van Gepaarde Sampling: Het artikel biedt de eerste algemene theoretische rechtvaardiging voor gepaarde sampling. Door paren $(S, S^c)$ te samplen met symmetrische gewichten, wordt het gewogen kleinste kwadraten-regressieprobleem orthogonaliseert (ontkoppelt) in onafhankelijke optimalisatieproblemen voor de oneven en even componenten. Omdat de even component irrelevant is, isoleert gepaarde sampling effectief het signaal dat nodig is voor Shapley-waarden. Dit lost een vermoeden op dat gepaarde sampling met een orde-$k$ fit (voor oneven $k$) gelijk is aan een orde-$(k+1)$ fit.

Algoritme Ontwerp: OddSHAP

Om dit inzicht uit te buiten zonder de combinatorische explosie van het fitten van alle hogere-orde termen te veroorzaken, opereert OddSHAP in de Fourier-basis in plaats van de unanimiteitsbasis.

• Voordeel van de Fourier-basis: In de Fourier-basis is een basisfunctie $\chi_T$ alleen oneven als de cardinaliteit $|T|$ oneven is. Dit maakt een zuivere scheiding tussen oneven en even termen mogelijk, in tegenstelling tot de unanimiteitsbasis.
• Tweefasig Proces:
  1. Interactie Screening: Een Gradient Boosted Tree (GBT) proxy-model wordt gefit op de gesamplede coalities. Met een methode zoals ProxySPEX extraheert het algoritme een ijle (sparse) verzameling van hoog-impactvolle oneven-orde Fourier-coëfficiënten. Dit voorkomt de noodzaak om alle mogelijke interacties te fitten.
  2. Oneven Regressie: Een gewogen kleinste kwadraten-regressie wordt strikt uitgevoerd op de geselecteerde oneven-orde Fourier-termen (plus lineaire termen), begrensd door overeen te komen met de waardefunctie op de lege en volledige verzamelingen.
• Efficiëntie: Door de regressie te beperken tot de oneven subspace en een proxy te gebruiken voor termselectie, bereikt de methode een polynomiale tijdcomplexiteit relatief aan de sampling-budget, waarmee de $O(d^k)$ schaling van vaste-orde polynoommethoden wordt omzeild.

Belangrijkste Bijdragen

1. Theoretische Unificatie van Gepaarde Sampling: Het artikel bewijst dat gepaarde sampling impliciet de regressie-objectieven ontkoppelt in oneven en even componenten, wat een rigoureuze verklaring biedt voor het empirische succes en eerdere bevindingen generaliseert die beperkt waren tot lage-orde interacties.
2. De OddSHAP-schatter: Een consistente schatter die uitsluitend polynoomregressie uitvoert op een ijle selectie van oneven-orde Fourier-basisfuncties. Het filtert irrelevante even componenten eruit en identificeert hoog-impactvolle interacties via een proxy-model.
3. State-of-the-Art Prestaties: Uitgebreide benchmarks tonen aan dat OddSHAP een superieure schattingsnauwkeurigheid bereikt vergeleken met bestaande methoden (inclusief RegressionMSR, LeverageSHAP en PolySHAP) onder grotere sampling-budgetten, met name in hoogdimensionale instellingen.

Experimentele Resultaten

De auteurs evalueerden OddSHAP op acht waardefuncties variërend van $d=14$ (DistilBERT) tot $d=101$ (Crime dataset), die deep learning (beeld en tekst) en tabulaire domeinen dekken.

• Nauwkeurigheid: OddSHAP behaalde consistent de laagste Mean Squared Error (MSE) en de beste gemiddelde rang over de benchmarks, vooral wanneer het sampling-budget $m$ voldoende was om interacties te detecteren ($m > \eta \cdot d$).
• Vergelijking met FFD: OddSHAP presteerde beter dan de Fixed-Budget Fractional Factorial Design (FFD-RD) op deep learning architecturen (ViT, DistilBERT), waar hogere-orde interacties significant zijn. Omgekeerd presteerde FFD-RD iets beter op boom-gebaseerde tabulaire datasets waar hogere-orde interacties snel afnemen, wat de domeinspecifieke trade-offs valideert.
• Ablatie-studies:
  • Gepaard vs. Niet-gepaard: Gepaarde sampling presteerde consequent beter dan niet-gepaarde sampling.
  • Oneven vs. Alle Interacties: Onder gepaarde sampling bood het opnemen van even interacties geen voordeel en verslechterde de prestaties licht door het verbruik van het interactie-budget met wiskundig compenserende termen.
  • Sparsity (IJlheid): Het opnemen van een matig aantal oneven interacties (gecontroleerd door de regressievariabele factor $\eta$) verminderde de fout aanzienlijk vergeleken met lineaire baselines, hoewel overfitting optrad bij te veel interacties.

Betekenis en Claims

Het artikel claimt dat OddSHAP een flexibel-budget-framework biedt dat robuust aanpasbaar is over diverse interactiestructuren. De primaire betekenis ligt in:

1. Het Oplossen van een Open Vermoeden: Het biedt het fundamentele theoretische mechanisme dat verklaart waarom gepaarde sampling werkt, waarbij het verder gaat dan empirische observatie naar structurele bewijsvoering.
2. Schaalbaarheid: Het behoudt de expressieve kracht van hogere-orde benaderingen zonder de prohibitieve combinatorische kosten te dragen door de focus te leggen op de oneven subspace.
3. Robuustheid: In tegen afhankelijk van methoden die steunen op rigide afkap-aannames (zoals FFD), blijft OddSHAP effectief in complexe deep learning-domeinen waar hogere-orde interacties niet verwaarloosbaar zijn, terwijl het concurrerend blijft in ijle tabulaire domeinen.

De auteurs merken beperkingen op, specifelijk dat de runtime van het algoritme cum cubisch schaalt met het budget vanwege de kwadratische regressiekosten op geselecteerde interacties, en dat gepaarde sampling het effectieve aantal onafhankelijke samples vermindert, wat de variantie potentieel kan verhogen. Ze concluderen echter dat de methode een state-of-the-art benadering vormt voor Shapley-waarde schatting in model-agnostische settings.