Technische Samenvatting: QuadraSHAP

Probleemstelling

Shapley-waarden zijn een fundamenteel hulpmiddel voor het verklaren van machine learning-predicties en bieden feature-toewijzingen die zijn gebaseerd op coöperatieve speltheorie. Echter is de exacte berekening over het algemeen onuitvoerbaar, omdat dit de evaluatie vereist van exponentieel veel feature-coalities ($2^{d-1}$). Hoewel model-specifieke methoden (zoals TreeSHAP, RKHS-SHAP) structurele eigenschappen benutten om polynomiale tijd te bereiken, staan ze vaak voor een aanhoudende afweging tussen numerieke stabiliteit en rekenkundige efficiëntie.

Specifiek lijden methoden die vertrouwen op polynoominterpolatie (zoals Linear TreeSHAP) aan snelle numerieke instabiliteit naarmate de polynoomgraad toeneemt (geleid door boomdiepte of feature-aantal), vanwege de slecht geconditioneerde inversen van Vandermonde-matrices. Omgekeerd bieden algebraïsche recursiemethoden (bijvoorbeeld voor product-kernelmodellen) stabiliteit, maar brengen ze aanzienlijk hogere rekenkosten met zich mee. Dit artikel adresseert de behoefte aan een methode die voor een brede klasse van modellen met een multiplicatieve structuur tegelijkertijd exact (of bijna-exact), numeriek stabiel en rekenkundig efficiënt is.

Methodologie

Het artikel introduceert QuadraSHAP, een methode voor het berekenen van Shapley-waarden voor productspellen – coöperatieve spellen waarbij de coalitiewaarde factoriseert als een product van per-speler termen ($v(S) = \prod_{j \in S} u_j$). Deze structuur komt op natuurlijke wijze voor in op bomen gebaseerde modellen en kernel-methoden met product-kernels.

1. Integraalvoorstelling

De kerntheoretische bijdrage is het herschrijven van de Shapley-waarde van een productspel van een gewogen som over $2^{d-1}$ deelverzamelingen naar een exacte één-dimensionale integraal. Door gebruik te maken van de Beta-functievoorstelling van Shapley-gewichten, leiden de auteurs af:
$$\phi_i(v) = (u_i - 1) \int_0^1 \prod_{j \neq i} \left( (1-t) + t u_j \right) dt$$
Deze transformatie elimineert de noodzaak voor enumeratie van deelverzamelingen of het herwinnen van coëfficiënten op basis van interpolatie.

2. Gauss-Legendre-kwadratuur

De integraal wordt geëvalueerd met behulp van Gauss-Legendre-kwadratuur.

• Exactheid: Als het aantal kwadratuurknooppunten $m_q$ voldoet aan $m_q \ge \lceil d/2 \rceil$, herstelt de methode de exacte Shapley-waarde.
• Benadering: Als $m_q < \lceil d/2 \rceil$, biedt de methode een bijna-exacte benadering. De fout wordt bewezen te vervallen geometrisch met betrekking tot $m_q$, specifiek begrensd door $O(\rho^{-2m_q})$ voor een Bernstein-ellipsparameter $\rho > 1$. Empirisch volstaan enkele honderden knooppunten voor nauwkeurige schattingen met hoge precisie, zelfs bij duizenden features, wat ver onder de theoretische exactheidssdrempel ligt.

3. Numeriek stabiele en efficiënte implementatie

Om praktische rekenkundige uitdagingen aan te pakken, stellen de auteurs specifieke algoritmische optimalisaties voor:

• Log-ruimte-evaluatie: Om overflow en underflow in hoge dimensies te voorkomen, worden producten geëvalueerd in log-ruimte met expliciete teken-tracking. De schatter wordt berekend als:
  $$\hat{\phi}_i(v) = (u_i - 1) \sum_{q=1}^{m_q} \omega_q \cdot \text{sgn}(P_q)\text{sgn}(T_{q,i}) \exp\left( \log|P_q| - \log|T_{q,i}| \right)$$
  waarbij $P_q$ het volledige product van termen is en $T_{q,i}$ de term voor feature $i$.
• Gedeelde berekening: In plaats van het "leave-one-out"-product voor elke feature opnieuw te berekenen, wordt het volledige product één keer berekend en wordt de specifieke factor voor feature $i$ eruit gedeeld. Dit reduceert de complexiteit van $O(d^2 m_q)$ naar $O(d m_q)$.
• Parallelisatie: De berekening maakt gebruik van associatieve scan-primitieven (prefix-sommen) om de log-ruimte-reducties in $O(\log d)$ parallelle tijd te berekenen.

Belangrijkste Bijdragen

1. Exacte integraalformulering: Het artikel stelt vast dat Shapley-waarden voor productspellen een exacte integraalvoorstelling toelaten, waardoor het gebruik van Gauss-Legendre-kwadratuur mogelijk wordt.
2. Stabiliteit en efficiëntie: QuadraSHAP lost de afweging tussen stabiliteit en efficiëntie op. Het vermijdt de numerieke instabiliteit van op interpolatie gebaseerde methoden (zoals Linear TreeSHAP) en is aanzienlijk sneller dan algebraïsche recursiemethoden voor product-kernelmodellen.
3. Theoretische garanties: De methode biedt bewezen exactheid voor $m_q \ge \lceil d/2 \rceil$ en grenzen voor geometrische convergentie voor benaderingsregimes.
4. Schaalbare algoritmen: De auteurs leiden algoritmen af met $O(d m_q)$ sequentieel werk en $O(\log d)$ parallelle tijd, waardoor de methode schaalbaar is naar problemen met hoge dimensies (duizenden features).

Experimentele Resultaten

De auteurs evalueren QuadraSHAP tegen state-of-the-art baselines (TreeSHAP, Linear TreeSHAP, FastTreeSHAP, shapiq en PKeX-Shapley) op synthetische en real-world datasets.

• Boomensembles:
  • Snelheid: QuadraSHAP is de snelste numeriek stabiele methode in alle geteste configuraties. Op grote ensembles ($10^5$ bladeren) presteert het 3–5$\times$ beter dan TreeSHAP en 2–2,7$\times$ beter dan FastTreeSHAP.
  • Stabiliteit: In regimes met diepe bomen (diepte tot 100) vertonen concurrenten zoals Linear TreeSHAP en TreeSHAP catastrofale schendingen van het Shapley-efficiëntieaxioma (fouten die $10^{186}$ of hoger bereiken). QuadraSHAP behoudt precisie op het niveau van drijvende-kommalimieten ($\sim 10^{-13}$).
• Product-kernel-methoden:
  • Schaalbaarheid: Voor Kernel Ridge Regression met product-kernels is QuadraSHAP een orde van grootte sneller dan de huidige exacte baseline (PKeX-Shapley).
  • Hoge dimensies: Waar PKeX-Shapley time-out (limiet van 300s) voor feature-dimensies $d \ge 2000$, voltooit QuadraSHAP verklaringen in seconden (bijvoorbeeld 7,6s voor $d=5000$).
• Kwaliteit van benadering: Experimenten bevestigen dat de benaderingsfout geometrisch vervalt met het aantal knooppunten $m_q$. Voor $d=5000$ levert het gebruik van slechts 400 knooppunten (ver onder de exactheidssdrempel van 2500) nauwkeurigheid op het niveau van machineprecisie op.

Betekenis en Claims

Het artikel claimt dat QuadraSHAP een unificerend, robuust kader biedt voor feature-toewijzing in modellen met multiplicatieve structuren. Door gebruik te maken van de integraalvoorstelling en Gauss-Legendre-kwadratuur, bereikt het:

• Numerieke robuustheid: Het blijft stabiel in situaties met hoge dimensies en diepe bomen waar op interpolatie gebaseerde methoden falen.
• Rekenkundige superioriteit: Het komt overeen met of overtreft de snelheid van de snelste bestaande methoden, terwijl het exactheid of gecontroleerde benadering behoudt.
• Generaliteit: De formulering verenigt boomensembles en product-kernel-methoden onder één enkel rekenkundig paradigma.

De auteurs positioneren QuadraSHAP als de snelste numeriek stabiele methode voor deze specifieke klassen van modellen, en bieden een praktische oplossing voor verklaarbaarheid in complexe, high-dimensional machine learning-systemen.