Proxy-Based Approximation of Shapley and Banzhaf Interactions

Technische Samenvatting: Proxy-gebaseerde Benadering van Shapley- en Banzhaf-interacties

Probleemstelling
Moderne machine learning-toepassingen vertrouwen steeds vaker op coöperatieve speltheorie om modelgedrag te interpreteren, met name door het gebruik van Shapley- en Banzhaf-waarden om bijdragen toe te schrijven aan individuele kenmerken. Het begrijpen van complexe, niet-lineaire dynamiek vereist echter vaak de analyse van hogere-orde interacties (subsets van kenmerken) in plaats van alleen singleton-effecten. Het exacte berekenen van kardinaal-probabilistische interactie-indicatoren is voor grote aantallen kenmerken ($n$) computationeel onuitvoerbaar vanwege de exponentiële groei van de coalitiestruktuur ($2^n$).

Bestaande schatters staan voor een kritieke afweging tussen snelheid en nauwkeurigheid:

• Op steekproeven gebaseerde methoden (bijv. SHAP-IQ, KernelSHAP-IQ) zijn vaak nauwkeurig, maar vereisen onpraktische steekproefbudgetten om het grote aantal hogere-orde termen te schatten, en lijden onder een hoge variantie die slecht schaalt met de orde van de interactie.
• Proxy-gebaseerde methoden (bijv. ProxySPEX) bieden snelheid, maar vertrouwen op Fourier-gebaseerde extractie uit boom-surrogaten. Deze aanpak lijdt onder exponentiële complexiteit ten opzichte van de boomdiepte en vereist vaak agressieve truncatie die de nauwkeurigheid in gevaar brengt. Bovendien leveren bestaande proxy-methoden doorgaans interacties van de proxy op in plaats van van de onderliggende waardenfunctie, wat bias introduceert.

Methodologie: ProxySHAP
De auteurs stellen ProxySHAP voor, een raamwerk dat de steekproefefficiëntie van op bomen gebaseerde proxy-modellen verzoent met een principiële weg naar consistentie via residualcorrectie. De methode decomposeert de doelinteractie-indicator $\phi^p_S(\nu)$ in twee componenten:
$$\phi^p_S(\nu) = \underbrace{\phi^p_S(\hat{\nu}_T)}_{\text{Exacte Proxy}} + \underbrace{\phi^p_S(\nu - \hat{\nu}_T)}_{\text{Residu}}$$

1. Proxy-aanpassing (Fase 1): Een op bomen gebaseerd model (bijv. XGBoost, LightGBM) of een lineair model met interactiekenmerken wordt getraind op gesamplede coalities om de onderliggende waardenfunctie $\nu$ te benaderen.
2. Exacte Proxy-extractie (Fase 2): In tegenstelling tot eerdere methoden die Fourier-coëfficiënten extraheren, introduceert ProxySHAP een polynomiale generalisatie van interventionele TreeSHAP. Dit maakt de exacte berekening van elke kardinaal-probabilistische interactie-indicator (inclusief Shapley en Banzhaf) direct uit de boomstructuur mogelijk.
   • De methode maakt gebruik van de Möbius-representatie van indicator-spellen gedefinieerd door boombladeren.
   • Het vermijdt de exponentiële $O(4^d)$ complexiteit van Fourier-gebaseerde extractie (waarbij $d$ de boomdiepte is), en bereikt een runtime van $O(n_{nodes})$ per interactie.
3. Residualaanpassing: Om de bias te corrigeren die ontstaat doordat de proxy niet perfect overeenkomt met $\nu$, schat de methode de interacties van het residuspel $(\nu - \hat{\nu}_T)$ met behulp van Maximum Sample Reuse (MSR).
   • Het artikel biedt een theoretische analyse die aantoont dat de variantie van de MSR-schatting voor interacties van orde $k$ schaalt als $O(n^{k-1}/|T|)$.
   • Derhalve leiden de auteurs voorwaarden af waaronder MSR-aanpassing voordelig is: voornamelijk voor laagdimensionale settings ($n < 30$) of wanneer het steekproefbudget $|T|$ voldoende groot is ten opzichte van $n^{k-1}$. Voor hogere-orde interacties in grote spellen kan de variantie van de correctie de biasreductie tenietdoen.

Belangrijkste Bijdragen

1. ProxySHAP-raamwerk: Een nieuwe schattingsstrategie die een op bomen gebaseerde proxy combineert met residualcorrectie, waardoor een efficiënte en nauwkeurige benadering van hogere-orde interacties mogelijk wordt.
2. Theoretische Vooruitgang:
   • Afleiding van een gesloten-formule, polynomiale algoritme om exacte kardinaal-probabilistische interactie-indicatoren uit boomensembles te extraheren, waarbij de exponentiële diepte-afhankelijkheid van eerdere Fourier-gebaseerde methoden wordt omzeild.
   • Formele karakterisering van de variantiegroei van MSR voor hogere-orde interacties, waarbij expliciete voorwaarden worden vastgesteld (in termen van $n$, budget en interactieorde $k$) waaronder residualaanpassing de prestaties verbetert of verslechtert.
3. Empirische Prestaties: Uitgebreide benchmarking over 47 datasets (tabellair, visie, taal, grafiek en visie-taal) toont aan dat ProxySHAP een nieuwe state-of-the-art standaard zet. Het bereikt de laagste fout in zowel kleine-budgetregimes (waar het ProxySPEX overtreft) als grote-budgetregimes (waar het KernelSHAP-IQ overtreft).

Resultaten

• Nauwkeurigheid: ProxySHAP presteert consistent beter dan baselines (KernelSHAP-IQ, ProxySPEX, SHAP-IQ) wat betreft de Relatieve Gemiddelde Kwant Fout (MSE). In grootschalige toepassingen met duizenden kenmerken (bijv. Bioresponse met $n=1776$) blijft ProxySHAP effectief waar andere methoden computationeel onuitvoerbaar of onnauwkeurig worden.
• Efficiëntie: Het polynomiale extractie-algoritme biedt snelheidswinsten van ordes van grootte (10x tot 1000x) ten opzichte van Fourier-gebaseerde extractie, vooral naarmate de boomdiepte toeneemt.
• Downstream-taken: In een specifieke toepassing om het SigLIP-2 visie-taalmodel te verklaren (FIxLIP-spel), toonde ProxySHAP superieure trouw (gemeten door het Oppervlak onder de Invoeging-Verwijdering-curve) in vergelijking met lineaire regressie-baselines en ProxySPEX.
• Hyperparametergevoeligheid: De studie benadrukt dat de kwaliteit van de proxy cruciaal is. Hyperparameteroptimalisatie (HPO) verbetert de prestaties aanzienlijk, en een "HPO-informeerd" standaardconfiguratie (met veel ondiepe bomen) wordt voorgesteld om kosten en nauwkeurigheid in evenwicht te brengen.

Betekenis en Claims
Het artikel claimt dat ProxySHAP de langdurige afweging tussen snelheid en nauwkeurigheid in interactieschatting oplost. Door een exacte extractiemechanisme voor boomproxies te bieden en een theoretisch onderbouwde strategie voor residualcorrectie, maakt het de schaalbare kwantificatie van complexe afhankelijkheden in moderne AI-systemen mogelijk. De auteurs benadrukken dat hun methode bijzonder waardevol is voor:

• Grootschalige toepassingen: Het verwerken van datasets met duizenden kenmerken waar exacte berekening onmogelijk is.
• Hogere-orde interacties: Het leveren van betrouwbare schattingen voor interacties die verder gaan dan paarsgewijze effecten, wat cruciaal is voor het begrijpen van cross-modale afhankelijkheden (bijv. in visie-taalmodellen) en complexe kenmerksynergieën.
• Praktische implementatie: Het bieden van een "state-of-the-art" schatter die robuust is onder variërende budgetbeperkingen en modeltypen, ondersteund door een schaalbare C++-implementatie.

De auteurs merken bescheiden beperkingen op, specifiek dat de benaderingskwaliteit afhankelijk is van de aangepaste proxy (waarvoor zorgvuldige hyperparameterafstelling vereist is) en dat de variantie van residualcorrectie de bruikbaarheid beperkt in zeer hoogdimensionale settings voor hogere-orde interacties. Toekomstig werk wordt voorgesteld om alternatieve proxyklassen en residualschatters te verkennen die schalerender zijn.