SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism

Probleemstelling

Shapley Additive Explanations (SHAP) zijn een standaardmethode voor het verklaren van beslissingen van machine learning-modellen. Hoewel SHAP in polynomiale tijd berekend kan worden voor eenvoudige modellen (zoals beslissingsbomen), is het berekenen van exacte SHAP-waarden voor expressievere "black-box" modellen (zoals neurale netwerken) bewezen NP-hard (en zelfs #P-hard). Dit creëert een fundamenteel dilemma: de modellen die het meest behoefte hebben aan uitlegbaarheid (complexe netwerken) zijn ook de moeilijkst te verklaren. Bestaande oplossingen vertrouwen vaak op benaderingen of heuristieken, wat de nauwkeurigheid van de uitleg kan ondermijnen.

Methodologie

De auteurs analyseren het probleem van het berekenen van exacte SHAP-waarden binnen de context van Tensor Networks (TNs), een brede klasse van modellen die veel expressiever is dan traditionele boom-structuren en vaak wordt gebruikt voor het comprimeren en abstracteren van neurale netwerken.

De kern van de methodologie bestaat uit drie stappen:

1. Tensoriële Formulering: De auteurs herschrijven de SHAP-formule naar een getensoriseerde representatie. Ze definiëren een "Marginal SHAP Tensor" ($T^{(M,P)}$) die de volledige SHAP-informatie van een model samenvat. Deze tensor wordt berekend door de contractie van twee componenten:

   • Een gewijzigde "Weighted Coalitional Tensor" ($\tilde{W}$), die de SHAP-coëfficiënten encodeert.
   • Een "Marginal Value Tensor" ($V^{(M,P)}$), die de verwachte modeluitkomsten onder een gegeven verdeling berekent.

2. Focus op Tensor Trains (TTs): Hoewel het berekenen van SHAP voor algemene Tensor Networks #P-hard blijft, tonen de auteurs aan dat dit probleem polynomiaal (en zelfs in de complexiteitsklasse NC) oplosbaar is wanneer de modellen en de data-verdeling zijn beperkt tot Tensor Trains (TTs). Een TT is een specifieke TN-structuur met een lineaire, 1D-topologie.

   • Ze bewijzen dat de Marginal SHAP Tensor voor TTs zelf ook een TT is.
   • Het contracteren van TTs kan efficiënt worden uitgevoerd met parallelle algoritmen (parallel scan), wat leidt tot een polylogarithmische tijdcomplexiteit ($O(\log n)$) met een polynomiaal aantal processoren.

3. Reducties en Parameterized Complexity:

   • Reductie: Ze tonen aan dat veel populaire ML-modellen (beslissingsbomen, ensemble-methoden, lineaire RNNs, lineaire regressie) kunnen worden gereduceerd naar TTs. Hierdoor erven deze modellen de gunstige complexiteitsresultaten van TTs.
   • Binarized Neural Networks (BNNs): Voor BNNs (waarbij gewichten en activaties binair zijn) analyseren ze de complexiteit via parameterized complexity. Ze onderzoeken hoe structuurparameters zoals diepte (depth), breedte (width) en sparsiteit de berekeningsmoeilijkheid beïnvloeden.

Belangrijkste Bijdragen

1. Eerste exacte algoritme voor TNs: Het paper introduceert het eerste framework voor het berekenen van probeerbaar exacte SHAP-waarden voor Tensor Networks met willekeurige structuren.
2. Parallelle Berekenbaarheid (NC): Voor de subclass van Tensor Trains wordt bewezen dat SHAP-berekening niet alleen in polynomiale tijd, maar in de complexiteitsklasse NC valt. Dit betekent dat het probleem efficiënt paralleliseerbaar is en in polylogarithmische tijd kan worden opgelost.
3. Verscherpte Complexiteitsgrenzen: Door het reduceren van andere modellen naar TTs, worden de complexiteitsresultaten voor beslissingsbomen, boom-ensembles, lineaire RNNs en lineaire modellen verscherpt. Deze modellen zijn nu niet alleen als "polynomiaal" bekend, maar ook als "efficiënt paralleliseerbaar" (NC).
4. Bottleneck-analyse voor Neurale Netwerken: Voor Binarized Neural Networks (BNNs) wordt een cruciaal inzicht geleverd:
   • Diepte: Zelfs bij een vaste, constante diepte (bijv. 1 verborgen laag) blijft het berekenen van SHAP NP-hard.
   • Breedte: Als de breedte van het netwerk wordt begrensd, wordt het probleem polynomiaal oplosbaar (in de klasse XP).
   • Breedte + Sparsiteit: Als zowel de breedte als de sparsiteit (via reified cardinality) worden begrensd, wordt het probleem Fixed-Parameter Tractable (FPT). Dit betekent dat SHAP efficiënt berekend kan worden voor zeer grote netwerken, zolang deze maar smal en spaarzaam zijn.

Resultaten

• General TNs: Het berekenen van SHAP voor algemene Tensor Networks is #P-hard (bewezen via reductie van #CNF-SAT).
• Tensor Trains: SHAP voor TTs ligt in NC2, wat betekent dat het met een polynomiaal aantal parallelle processoren in $O(\log^2 n)$ tijd kan worden berekend.
• Andere Modellen: De complexiteit van SHAP voor beslissingsbomen, tree ensembles, lineaire modellen en lineaire RNNs wordt herclassificeerd naar NC2, wat een aanzienlijke verbetering is ten opzichte van eerdere polynomiale schattingen.
• BNNs:
  • Gebonden diepte $\rightarrow$ Para-NP-hard.
  • Gebonden breedte $\rightarrow$ XP (oplosbaar, maar exponentieel in de parameter).
  • Gebonden breedte en sparsiteit $\rightarrow$ FPT (efficiënt oplosbaar).

Betekenis en Impact

Dit werk sluit een significante kloof in de uitlegbaarheid van AI (XAI) door te laten zien dat er een breed scala aan expressieve modellen bestaat waarvoor exacte SHAP-waarden niet alleen theoretisch haalbaar zijn, maar ook efficiënt paralleliseerbaar.

• Theoretische Vooruitgang: Het biedt de eerste diepgaande analyse van de parallelle berekenbaarheid van SHAP en identificeert de netwerkbreedte (in plaats van diepte) als de primaire bottleneck voor neurale netwerken.
• Praktische Toepassing: Voor praktijken die werken met grote datasets of complexe modellen, opent dit de deur tot het gebruik van Tensor Trains en gerelateerde structuren om uitlegbaarheid op schaal te bieden zonder de noodzaak van schadelijke benaderingen.
• Toekomstige Richtingen: Het paper suggereert dat het beperken van de breedte en sparsiteit van neurale netwerken een veelbelovende route is om uitlegbaarheid te garanderen zonder in te leveren op modelcapaciteit.

Samenvattend bewijst dit paper dat door de juiste modelrepresentatie (Tensor Networks) en het benutten van parallelle verwerking, het fundamentele probleem van de onberekenbaarheid van SHAP voor complexe modellen kan worden opgelost voor een belangrijke subklasse van netwerken.