Technische Samenvatting: Tractabele Shapley-waarden en Interacties via Tensor Netwerken

Probleemstelling

Het verklaren van voorspellingen van machine learning via Shapley-waarden en hun hogere-orde generalisaties (Shapley Interaction Indices, SII) is fundamenteel voor besluitvormingsondersteuning en interpreteerbaarheid. Het berekenen van deze indices is echter computationeel onhaalbaar voor modellen met $n$ kenmerken, omdat dit traditioneel het enumereren van $O(2^n)$ coalities vereist. Bestaande oplossingen kampen met significante afruilproblemen:

• Structurele aannames: Methoden zoals TreeSHAP of die voor Generalized Additive Models (GAMs) zijn alleen exact voor specifieke architecturen (bijv. bomen, lineaire modellen).
• Steekproefgebaseerde benaderingen: Benaderingen zoals KernelSHAP of SHAP-IQ vertrouwen op zware bemonstering, wat delicate variantie-afstemming vereist en vaak niet schaalt naar hogere-orde interacties zonder enorme computationele kosten.
• Geamortiseerde schatting: Methoden die hulpmodellen trainen, brengen vaak aanzienlijke trainingsoverhead met zich mee en missen mogelijk theoretische garanties op de getrouwheid van de verklaring.

De kernuitdaging is het berekenen van Shapley-waarden en interacties exact (of met gecontroleerde fout) voor algemene predictoren zonder exponentiële enumeratie of excessieve bemonstering.

Methodologie: TN-SHAP

De auteurs stellen TN-SHAP voor, een methode die de exhaustieve coalitie-enumeratie vervangt door een "few-evaluation" schema op een Tensor Network (TN) surrogaat. De aanpak maakt gebruik van drie kerninzichten om de complexiteit te verminderen van $O(2^n)$ naar $O(n \cdot \text{poly}(\chi))$, waarbij $\chi$ de maximale bond-dimensie van het tensor netwerk is.

1. Multilineaire Representatie en Coëfficiëntextractie

De methode gaat ervan uit dat de predictor $f$ goed benaderd kan worden door een multilineaire functie $g$ in een verhoogde feature-ruimte (lifted feature space). In een multilineaire expansie is $f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$, waarbij coalitie-waarden overeenkomen met lineaire combinaties van tensor-coëfficiënten. Cruciaal is dat Shapley-waarden alleen afhangen van grootte-geaggregeerde marginale bijdragen (sommen van bijdragen voor coalities van grootte $s$), in plaats van specifieke coalitie-lidmaatschappen.

2. Diagonale Selectoren en Polynomiale Interpolatie

In plaats van $2^n$ coalities te bevragen, gebruikt TN-SHAP diagonale selector-matrices $S_r(t) = \text{Diag}(t, 1)$ toegepast op verhoogde features $\tilde{x}_r = [\phi(x_r), 1]^\top$.

• Door de surrogaat $g$ te evalueren op punten waar features geschaald worden door een parameter $t$, aggregeert de methode alle coalities van grootte $s$ in de coëfficiënt van $t^s$ in een resulterende polynoom $P(t)$.
• Specifiek wordt voor een doel-feature $i$ een probe-functie $G_i(t)$ geconstrueerd om de marginale bijdrage van $i$ over alle deelverzamelingen van andere features te isoleren.
• Dit transformeert het combinatorische probleem in polynomiale interpolatie. Door $G_i(t)$ te evalueren op $n$ verschillende punten (bijv. Chebyshev-Gauss knopen), lost het systeem een Vandermonde lineair systeem op om de grootte-geaggregeerde marginale bijdragen $\{m_s^{(i)}\}$ te herstellen.
• De Shapley-waarde wordt vervolgens berekend als een gewogen som van deze herstelde coëfficiënten.

3. Tensor Network Surrogates

Om de evaluatie van de multilineaire kaart op schaal hanteerbaar te maken, wordt de coëfficiënt-tensor gefactoriseerd in een Tensor Network (TN) (bijv. Tensor Train of Hierarchical Tree) met bond-dimensie $\chi$.

• Feature Maps: Om niet-lineaire real-world data te verwerken, worden scalaire features verhoogd via geleerde of handmatige kaarten $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$ voordat ze de TN ingaan. Dit behoudt de multilineariteit in de verhoogde ruimte terwijl de surrogaat de niet-lineariteiten in de oorspronkelijke inputruimte kan modelleren.
• Efficiëntie: Elke forward pass door de TN kost $O(\text{poly}(\chi))$. Omdat er slechts $O(n)$ evaluaties nodig zijn voor interpolatie, is de totale complexiteit voor het berekenen van orde-$k$ interacties polynomiaal in $n$.

Belangrijkste Bijdragen

1. Verenigd Probe-Interpolatie Schema: Een exact algoritme voor het berekenen van Shapley-waarden en $k$-wij interacties op een multilineaire TN-surrogaat met slechts $O(n)$ gestructureerde forward passes, waardoor $O(2^n)$ queries worden vermeden.
2. Feature-Map-Verbeterde Surrogaten: Een framework dat aantoont hoe geleerde feature-lifts de vereiste multilineariteit behouden voor exacte berekening, terwijl de surrogaat-getrouwheid voor niet-lineaire modellen wordt verbeteren.
3. Theoretische Garanties:
   • Exactheid: De methode berekent Shapale waarden exact op de passende multilineaire surrogaat.
   • Benaderingsfout: De fout ten opzichte van het originele model wordt begrensd door de worst-case coalitie-benaderingsfout ($\epsilon$) van de surrogaat. Voor Shapley-waarden geldt: $|\phi^g_i - \phi^f_i| \leq 2\epsilon$.
   • Tractabiliteit: Bewezen reductie van exponentiële naar polynomiale tijdcomplexiteit $O(n \cdot \text{poly}(\chi) + n^2)$.

Experimentele Resultaten

De auteurs evalueerden TN-SHAP op synthetische multilineaire functies en real-world UCI regressie-datasets (Concrete, Diabetes, Energy) met MLP teachers.

• Synthetische Validatie: Op exact multilineaire functies bereikte TN-SHAP theoretische exactheid met runtimes in de milliseconde-schaal, waarmee het KernelSHAP-IQ met ordes van grootte overtrof (bijv. 3,5 ms vs 18,7 ms voor $n=10$; 19,7 ms vs 447,3 ms voor $n=50$).
• Real-World Accuraatheid: Op UCI-datasets met MLP teachers:
  • TN-SHAP behaalde 25–1000× wall-clock speedups ten opzichte van KernelSHAP-IQ bij vergelijkbare accuraatheid.
  • Voor eerste-orde ($k=1$) attributies bereikte TN-SHAP een bijna perfecte cosinus-gelijkenis (0,994) met de grondwaarheid.
  • Voor hogere-orde interacties ($k=2, 3$) behield TN-SHAP een concurrerende accuraatheid, terwijl sampling-gebaseerde baselines moeite hadden met variantie of aanzienlijk meer rekenkracht vereisten om een vergelijkbare getrouwheid te bereiken.
• Rank Ablatie: Experimenten toonden aan dat een student TN rank van $r=5-6$ voldoende was om alle interactie-ordes te herstellen met $R^2 > 0,99$ wanneer de teacher een rank van 16 had. Lagere ranks leidden tot onderfitting van hogere-orde interacties.
• Hoge-Dimensie Stabiliteit: In hoog-dimensionale synthetische settings ($D=50, 100$) behield TN-SHAP een hoge surrogaat-getrouwheid ($R^2 > 0,95$) en sterke Top-$k$ feature-recovery onder lineaire-kosten query-budgetten.

Betekenis en Claims

Het artikel claimt dat TN-SHAP de kloof overbrugt tussen de theoretische strengheid van exacte Shapley-berekening en de praktische noodzaak van efficiëntie. Door gebruik te maken van de algebraïsche structuur van multilineaire functies en de efficiëntie van tensor netwerken, biedt de methode:

• De transformatie van een exponentieel enumeratieprobleem naar een klein aantal gestructureerde evaluaties.
• Structurele garanties (via rank bounds) die de problemen met getrouwheid aanpakken die gebruikelijk zijn bij onbeperkte lokale surrogaatmethoden zoals LIME.
• Een vereniging van lokale Shapley-verklaringen met globale additieve structuren (GAMs), aangezien het fitten van een orde-$k$ surrogaat exacte $k$-SII coëfficiënten oplevert die overeenkomen met de bijbehorende GAM-termen.
• Een schaalbaar alternatief voor sampling-gebaseerde methoden, met name voor hogere-orde interacties waar de variantie van sampling doorgaans hoog is.

De auteurs merken op dat de prestaties van de methode afhangen van de kwaliteit van de TN-surrogaat fit en de keuze van de feature maps, maar empirische resultaten suggereren dat zelfs bescheiden feature lifts en tensor ranks voldoende zijn om complexe coalitionele structuren in de praktijk te vangen.