Technische Samenvatting: Quadrature-TreeSHAP

Probleemstelling

Verklaring voor ensemble-modellen op basis van bomen (bijv. XGBoost, Random Forests) is sterk afhankelijk van Shapley-waarden. Hoewel Path-Dependent SHAP de standaardbenadering is vanwege de efficiëntie, lopen bestaande methoden tegen aanzienlijke afwegingen aan wat betreft diepte-afhankelijke uitvoeringstijd, numerieke stabiliteit en ondersteuning voor interacties van hogere orde.

Huidige state-of-the-art methoden vertonen specifieke beperkingen:

• TreeSHAP en GPUTreeSHAP werken met een tijdscomplexiteit van $O(MTLD^2)$ (waarbij $M$ het aantal steekproeven is, $T$ het aantal bomen, $L$ het aantal bladeren en $D$ de diepte).
• FastTreeSHAP v2 en Woodelf reduceren de complexiteit tot $O(MTLD)$, maar introduceren voorverwerkingsstappen die exponentieel zijn in de diepte, waardoor ze onpraktisch zijn voor diepe bomen.
• Linear TreeSHAP bereikt $O(MTND)$ maar lijdt aan numerieke instabiliteit door bewerkingen in de monomiale basis.
• TreeGrad-Shap verbetert de stabiliteit via gradiëntformuleringen, maar is beperkt tot attributies van de eerste orde.
• TreeSHAP-IQ breidt uit naar interacties van hogere orde, maar heeft een complexiteit van $O(MTLD \binom{F-1}{s-1})$, wat slecht schaalt naarmate het aantal kenmerken ($F$) en de orde van interactie ($s$) toenemen.

Methodologie

De auteurs stellen Quadrature-TreeSHAP voor, een herformulering van Path-Dependent TreeSHAP gebaseerd op Gauss-Legendre-kwadratuur en een gewogen-Banzhaf-interactiepolynoom.

1. Theoretische Grondslag

De methode maakt gebruik van de relatie tussen Shapley-waarden en gewogen Banzhaf-waarden.

• Gewogen Banzhaf-polynoom: Voor een blad $v$ van een beslissingsboom wordt de Path-Dependent gewogen Banzhaf-interactiewaarde voor een subset van kenmerken $S$ bij opnamekans $p$ uitgedrukt als een polynoom $B^{(S)}_{p,v}$. Dit polynoom is afgeleid uit de padstructuur van het blad en de gewichten van de randen.
• Integraalherstel: Shapley-interactiewaarden worden hersteld door deze Banzhaf-polynomen te integreren over de participatiekans $p \in [0, 1]$:
  $$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$$
• Kwadratuurbenadering: In plaats van symbolische integratie evalueren de auteurs deze integraal met behulp van Gauss-Legendre-kwadratuur. De integraal wordt benaderd als een gewogen som van het polynoom, geëvalueerd op vaste knopen $t_m$:
  $$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$$

2. Algorithmische Implementatie

• Vastpuntformulering: Het algoritme voert één diepte-eerst-doorloop (DFS) van de boom uit. Tijdens de doorloop worden de waarden van het padpolynoom voortgeplant op een vaste set Gauss-Legendre-knopen (doorgaans 8) in plaats van polynomen symbolisch uit te breiden.
• Complexiteitsreductie:
  • Theoretisch is de graad van de integrand voor interacties van orde-$s$ maximaal $d-s$ (waarbij $d$ het maximum aantal unieke kenmerken op een pad is).
  • Praktisch tonen de auteurs aan dat 8 vaste kwadratuurpunten voldoende zijn om machineprecisie (float32) te bereiken, zelfs voor zeer diepe bomen.
  • Dit verwijdert de afhankelijkheid van de boomdiepte $d$ uit de binnenste berekening, waardoor de effectieve complexiteit daalt van $O(MTN \lceil d/2 \rceil)$ naar $O(MTN)$ voor de eerste orde, en van $O(MTN d^s)$ naar $O(MTN d^{s-1})$ voor interacties van orde-$s$.
• Hardwareversnelling: Omdat de berekening het evalueren van dezelfde vaste set punten voor elk pad omvat, is de rekenkunde regelmatig. Dit maakt efficiënte SIMD-uitvoering (Single Instruction, Multiple Data) op CPU's en SIMT-uitvoering (Single Instruction, Multiple Threads) op GPU's mogelijk, waardoor de overhead voor bin-packing en planning die door GPUTreeSHAP wordt vereist, wordt geëlimineerd.

Belangrijkste Bijdragen

1. Algoritme voor interacties van elke orde: Het artikel presenteert een algoritme voor het berekenen van Shapley-interactiewaarden van elke orde dat de state-of-the-art complexiteit van TreeSHAP-IQ verbetert van $O(MTLD \binom{F-1}{s-1})$ naar $O(MTN d^s)$. Dit levert aanzienlijke winst op wanneer het aantal kenmerken de boomdiepte overschrijdt ($F > D \ge d$).
2. Herformulering op basis van kwadratuur: De auteurs leveren een theoretische en empirische analyse die aantoont dat 8 Gauss-Legendre-punten voldoende zijn om machineprecisie te bereiken voor Shapley-waarden en interacties, waardoor de uitvoeringstijd in de praktijk effectief wordt ontkoppeld van de boomdiepte.
3. Numerieke stabiliteit: Door het samenvattende polynoom te evalueren op begrenste, positieve knopen in plaats van coëfficiënten uit te breiden in een monomiale basis, vermijdt de methode catastrofale annulering. De auteurs beweren dat Quadrature-TreeSHAP numeriek stabieler is dan TreeSHAP, met name voor diepe ensembles.
4. Hardware-efficiënte implementatie: De methode is geïmplementeerd in C++ voor CPU en geïntegreerd in XGBoost voor GPU. Het maakt gebruik van vectorisatie (4 punten op CPU, 32 op GPU) om aanzienlijke snelheidswinst te bereiken ten opzichte van bestaande implementaties.
5. Open-source integratie: De implementatie is open-source gemaakt en geïntegreerd in de XGBoost-bibliotheek (als vervanging van de TreeSHAP-backend), toegankelijk via standaard API-aanroepen (pred_contribs=True en pred_interactions=True).

Experimentele Resultaten

De auteurs hebben Quadrature-TreeSHAP geëvalueerd op 12 XGBoost-benchmark-ensembles (Adult, CalHousing, CovType, Fashion-MNIST) in kleine, grote en schaarse regimes.

• Eerste orde (Shapley-waarden):
  • CPU: 1,06× tot 10,59× sneller dan TreeSHAP (mediaan 3,84×).
  • GPU: 1,84× tot 6,95× sneller dan GPUTreeSHAP.
• Tweede orde (paarsgewijze interacties):
  • CPU: 3,80× tot 58,11× sneller dan TreeSHAP (mediaan 12,86×).
  • GPU: Tot 6,65× sneller dan GPUTreeSHAP (hoewel GPUTreeSHAP concurrerend bleef op specifieke werklasten met kleine diepte).
• Interacties van hogere orde (Python-benchmarks):
  • In vergelijking met TreeSHAP-IQ voor interacties van de derde orde was Quadrature-TreeSHAP 18,73× tot 26,49× sneller.
  • Op het schaarse CovType-dataset nam de snelheidswinst ten opzichte van TreeSHAP-IQ toe met de orde van interactie, en bereikte 1209,37× bij orde 6.
• Numerieke stabiliteit:
  • Op de Fashion-MNIST-schaarse benchmark met toenemende boomdiepte werd TreeSHAP instabiel na diepte 32. Quadrature-TreeSHAP bleef stabiel, waarbij 6–8 punten hoge nauwkeurigheid bereikten.

Betekenis

Het artikel beweert dat Quadrature-TreeSHAP een numeriek stabiele, hardware-efficiënte en interactie-bewuste herformulering van Path-Dependent SHAP biedt. Door over te stappen van symbolische polynoomrekenkunde naar vastpunt-kwadratuur, lost de methode de afweging op tussen diepte-afhankelijkheid en numerieke stabiliteit. Het maakt de efficiënte berekening van interacties van hoge orde op diepe bomen mogelijk, een taak die eerder werd gehinderd door de exponentiële complexiteit of instabiliteit van eerdere methoden. De integratie in XGBoost zorgt voor directe praktische bruikbaarheid voor gebruikers van de bibliotheek en het bredere shap-pakket.