Technische Samenvatting: ShaplEIG

Probleemstelling

Shapley-waarden (SV's) dienen als een principiële attributiemetriek in interpreteerbare machine learning, maar de exacte berekening ervan is vaak onhandelbaar. De computationele last ontstaat door twee factoren: de exponentiële groei van coalities ($2^p$) met het aantal spelers $p$, en de hoge kosten van het evalueren van de waardefunctie $\nu$ voor elke coalitie. In toepassingen zoals retraining-gebaseerde featurebelangrijkheid, datavalutatie en hyperparameterbelangrijkheid, kunnen evaluaties van de waardefunctie volledige model-retraining of dure inferentie impliceren, wat het evaluatiebudget ernstig beperkt.

Bestaande benaderingsmethoden, inclusief Monte Carlo-sampling en surrogaat-gebaseerde benaderingen (bijv. Kernel SHAP, Regression MSR), vertrouwen doorgaans op vaste, niet-adaptieve steekproefverdelingen. Dit roept de vraag op of de benaderingsnauwkeurigheid kan worden verbeterd door coalities voor evaluatie adaptief te selecteren op basis van eerdere observaties, met name in regimes met een laag budget. Hoewel Bayesian Experimental Design (BED) een raamwerk biedt voor sequentiële design met behulp van Expected Information Gain (EIG), is de adoptie van BED bij SV-schatting beperkt vanwege het gebrek aan gesloten vorm EIG-expressies en de computationele onhandelbaarheid van het schatten van EIG voor hoogdimensionale discrete ruimtes.

Methodologie

De auteurs stellen ShaplEIG voor, een Bayesian experimental design-benadering die adaptief coalities selecteert om de informatiewinst met betrekking tot de Shapley-waarden te maximaliseren.

1. Gaussian Process Surrogate met Hamming Kernel

ShaplEIG modelleert de waardefunctie $\nu$ met behulp van een Gaussian Process (GP) surrogaat. Om de binaire inputruimte van coalities (gerepresenteerd als indicatorvectoren $z \in \{0, 1\}^p$) te verwerken, gebruikt de methode een Hamming-afstandskernel. Deze kernel kwantificeert de gelijkenis tussen coalities op basis van gewogen Hamming-afstanden, met leerbare lengteschaal-hyperparameters $\xi$. De GP levert een posterieure verdeling over de waardefunctie over alle $2^p$ coalities gegeven een dataset $D_t$ van geobserveerde evaluaties.

2. Consistente SV-schatting via Lineariteit

Een cruciaal theoretisch inzicht is de lineariteit van Shapley-waarden ten opzichte van de waardefunctie. De SV's $\phi$ kunnen worden uitgedrukt als een lineaire transformatie van de waardefunctievector $\nu$: $\phi = A\nu$, waarbij $A$ een bekende matrix is afgeleid van de Shapley-formule. Bijgevolg is de posterieure verdeling over de SV's onder de GP-surrogaat ook Gaussisch en beschikbaar in gesloten vorm:
$$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$$
De auteurs extraheren SV-schattingen uit het posterieure gemiddelde, $\hat{\phi} = A\mu_{\nu|D_t}$. Cruciaal is dat voor ruisloze (of quasi-ruisloze) GP's deze estimator consistent is: als alle $2^p$ coalities worden geëvalueerd, convergeren de schattingen exact naar de ware Shapley-waarden.

3. Closed-Form Expected Information Gain (EIG)

De kernbijdrage is het afleiden van een closed-form expressie voor de EIG van een kandidaat-coalitie $z^{(i)}$ met betrekking tot de SV's. Door de sequentiële selectie te kaderen als een Bayesiaans lineair invers probleem waarbij de SV's een lineair einddoel zijn, wordt aangetoond dat de EIG alleen afhangt van de posterieure covariantie van de SV's:
$$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$$
Dit vermijdt de geneste verwachtingen die doorgaans vereist zijn in BED, aangezien de EIG uitsluitend afhangt van het experimenteel design (de geselecteerde coalitie) en niet van de specifieke uitkomst $y(x)$.

4. Efficiënte Berekening via Elementaire Symmetrische Polynomen

Directe berekening van de EIG omvat operaties op matrices van grootte $2^p \times 2^p$, wat leidt tot exponentiële complexiteit. De auteurs stellen een efficiënt berekeningsschema voor dat de complexiteit reduceert tot polynomiale tijd ($O(p^4 + t^3)$) door gebruik te maken van de multiplicatieve structuur van de Hamming-kernel.

• De termen die vereist zijn voor de EIG (specifiek $A\Sigma_{\nu|D_t}e_i$ en $A\Sigma_{\nu|D_t}A^\top$) worden herschreven als gewogen sommen van kernel-evaluaties.
• Deze sommen worden geïdentificeerd met geschaalde elementaire symmetrische polynomen (ESP's).
• Door deze polynomen efficiënt te berekenen (met behulp van dynamisch programmeren en prefix/suffix-tabellen), vermijdt de methode expliciete enumeratie van alle coalities.

5. Algoritme

Het algoritme verloopt greedily:

1. Initialiseer met een klein design (bijv. leverage score sampling).
2. Fit de GP-surrogaat en optimaliseer de hyperparameters.
3. Bereken de EIG voor alle kandidaat-coalities met het efficiënte polynomiale schema.
4. Selecteer de coalitie met de maximale EIG, evalueer de waardefunctie en update de dataset.
5. Herhaal tot het budget is uitgeput.

Belangrijkste Bijdragen

1. ShaplEIG Framework: Introductie van een nieuw, BED-gebaseerd methode voor SV-schatting die een GP-surrogaat met een Hamming-kernel gebruikt en coalities adaptief selecteert op basis van EIG.
2. Closed-Form EIG: Demonstratie dat de EIG voor Shapley-waarden onder een GP-surrogaat een closed-form expressie toelaat, door gebruik te maken van de lineariteit van SV's in de waardefunctie.
3. Polynomiale Complexiteit: Voorstel van een efficiënt berekeningsschema voor de EIG dat de complexiteit van exponentieel naar polynomiaal reduceert in het aantal spelers ($p$) via elementaire symmetrische polynomen.
4. Consistente Schatting: Levering van een consistente SV-estimator die convergeert naar exacte waarden wanneer alle coalities worden geëvalueerd, in contrast met sommige boom-gebaseerde surrogaatmethoden die extra aanpassingsstappen vereisen.

Experimentele Resultaten

De auteurs evalueren ShaplEIG over diverse, kostbare toepassingen met kleine tot matig grote games ($8 \le p \le 101$):

• Taken: Globale feature belangrijkheid (TabPFN), datavalutatie (Random Forest, Gradient Boosting), hyperparameter belangrijkheid (XGBoost, LCBench), en lokale verklaringen (ResNet, ViT, Random Forest).
• Baselines: Vergelijking met Kernel SHAP, Leverage SHAP, Permutation Sampling, en de state-of-the-art Regression MSR (gekoppeld aan XGBoost).
• Ablaties: Vergelijking met varianten die dezelfde GP-surrogaat gebruiken maar verschillende selectiestrategieën (Random, Uncertainty Sampling, Leverage Score Sampling).

Bevindingen:

• Steekproefefficiëntie: ShaplEIG bereikt consistent de beste algehele nauwkeurigheid (laagste Mean Squared Error) in het lage-budgetregime over de meeste taken. Het domineert vaak strikt de concurrenten, met name in asymmetrische games waar interacties tussen spelers niet uniform zijn.
• Ablatie-inzichten: De sterke prestaties worden primair toegeschreven aan de EIG-gebaseerde selectiestrategie in plaats van enkel het gebruik van een GP-surrogaat. Uncertainty Sampling (US) presteerde vaak slechter dan random sampling, wat benadrukt dat het maximaliseren van de marginale variantie niet gelijkstaat aan het maximaliseren van de informatie over de lineair getransformeerde SV's.
• Schaalbaarheid: Voor grotere games ($p > 16$) blijft de methode effectief, zelfs wanneer hyperparameter-refitting op een schema wordt uitgevoerd in plaats van bij elke iteratie.
• Computationele Kosten: Hoewel EIG-berekening efficiënt is (seconden), kan hyperparameter-fitting een bottleneck worden voor grote $p$ (tot 25 minuten per iteratie voor $p \approx 100$). De auteurs merken op dat ShaplEIG het meest geschikt is wanneer evaluaties van de waardefunctie werkelijk duur zijn, wat de overhead rechtvaardigt.

Betekenis en Claims

Het artikel beweert dat ShaplEIG een principieel raamwerk biedt voor het verbeteren van de steekproefefficiëntie in SV-schatting voor kostbare games. Door een closed-form EIG af te leiden en een efficiënt polynomial-time berekeningsschema voor te stellen, overwinnen de auteurs de primaire barrières voor het toepassen van Bayesian Experimental Design in dit domein.

De auteurs stellen bescheiden dat hoewel de methode computationele overhead met zich meebrengt door herhaalde GP-optimalisatie, het substantiële winst oplevert in schattingsnauwkeurigheid wanneer de evaluatiebudgetten beperkt zijn. Ze erkennen dat voor zeer grote games of minder kostbare waardefuncties de overhead prohibitief kan zijn, en suggereren dat toekomstig werk zich moet richten op verdere computationele verbeteringen om de toepasbaarheid van de methode te verbreden. Het werk claimt niet de SV-schatting voor alle scenario's op te lossen, maar richt zich specifief op het regime van dure waardefuncties waar adaptieve selectie cruciaal is.