Proxy-Based Approximation of Shapley and Banzhaf Interactions

Riepilogo Tecnico: Approssimazione Basata su Proxy delle Interazioni di Shapley e Banzhaf

Enunciato del Problema
Le applicazioni moderne di machine learning fanno sempre più affidamento sulla teoria dei giochi cooperativa per interpretare il comportamento dei modelli, utilizzando specificamente i valori di Shapley e Banzhaf per attribuire i contributi alle singole caratteristiche. Tuttavia, la comprensione di dinamiche complesse e non lineari richiede spesso l'analisi di interazioni di ordine superiore (sottoinsiemi di caratteristiche) piuttosto che dei soli effetti singoli. Il calcolo esatto degli indici di interazione cardinal-probabilistici è computazionalmente intrattabile per un gran numero di caratteristiche ($n$) a causa della crescita esponenziale dello spazio delle coalizioni ($2^n$).

Gli stimatori esistenti affrontano un compromesso critico tra velocità e accuratezza:

• I metodi basati sul campionamento (ad es. SHAP-IQ, KernelSHAP-IQ) sono spesso accurati ma richiedono budget di campionamento impraticabili per adattarsi al vasto numero di termini di ordine superiore, soffrendo di un'alta varianza che scala male con l'ordine dell'interazione.
• I metodi basati su proxy (ad es. ProxySPEX) offrono velocità ma si affidano all'estrazione basata su Fourier da surrogati ad albero. Questo approccio soffre di una complessità esponenziale rispetto alla profondità dell'albero e richiede spesso una troncatura aggressiva che compromette l'accuratezza. Inoltre, i metodi proxy esistenti restituiscono tipicamente le interazioni del proxy piuttosto che della funzione di valore sottostante, introducendo un bias.

Metodologia: ProxySHAP
Gli autori propongono ProxySHAP, un framework che riconcilia l'efficienza del campionamento dei modelli proxy basati su alberi con una via principiale verso la coerenza tramite correzione del residuo. Il metodo scompone l'indice di interazione target $\phi^p_S(\nu)$ in due componenti:
$$\phi^p_S(\nu) = \underbrace{\phi^p_S(\hat{\nu}_T)}_{\text{Proxy Esatto}} + \underbrace{\phi^p_S(\nu - \hat{\nu}_T)}_{\text{Residuo}}$$

1. Adattamento del Proxy (Fase 1): Un modello basato su alberi (ad es. XGBoost, LightGBM) o un modello lineare con caratteristiche di interazione viene addestrato su coalizioni campionate per approssimare la funzione di valore sottostante $\nu$.
2. Estrazione del Proxy Esatto (Fase 2): A differenza dei metodi precedenti che estraggono coefficienti di Fourier, ProxySHAP introduce una generalizzazione in tempo polinomiale di TreeSHAP interventivo. Ciò consente il calcolo esatto di qualsiasi indice di interazione cardinal-probabilistico (inclusi Shapley e Banzhaf) direttamente dalla struttura dell'albero.
   • Il metodo sfrutta la rappresentazione di Möbius dei giochi indicatori definiti dalle foglie dell'albero.
   • Evita la complessità esponenziale $O(4^d)$ dell'estrazione basata su Fourier (dove $d$ è la profondità dell'albero), raggiungendo un tempo di esecuzione $O(n_{nodes})$ per interazione.
3. Regolazione del Residuo: Per correggere il bias introdotto dal fatto che il proxy non corrisponde perfettamente a $\nu$, il metodo stima le interazioni del gioco residuo $(\nu - \hat{\nu}_T)$ utilizzando il Maximum Sample Reuse (MSR).
   • Il documento fornisce un'analisi teorica che mostra come la varianza dello stimatore MSR per interazioni di ordine $k$ scala come $O(n^{k-1}/|T|)$.
   • Di conseguenza, gli autori derivano le condizioni in cui la regolazione MSR è benefica: principalmente per impostazioni a bassa dimensionalità ($n < 30$) o quando il budget di campionamento $|T|$ è sufficientemente grande rispetto a $n^{k-1}$. Per interazioni di ordine elevato in giochi grandi, la varianza della correzione può superare la riduzione del bias.

Contributi Chiave

1. Framework ProxySHAP: Una strategia di stima innovativa che combina un proxy basato su alberi con una correzione del residuo, consentendo un'approssimazione efficiente e accurata delle interazioni di ordine superiore.
2. Avanzamento Teorico:
   • Derivazione di un algoritmo in tempo polinomiale a forma chiusa per estrarre indici di interazione cardinal-probabilistici esatti da ensemble di alberi, aggirando la dipendenza esponenziale dalla profondità dei metodi precedenti basati su Fourier.
   • Caratterizzazione formale della crescita della varianza di MSR per interazioni di ordine superiore, stabilendo condizioni esplicite (in termini di $n$, budget e ordine di interazione $k$) in cui la regolazione del residuo migliora o degrada le prestazioni.
3. Prestazioni Empiriche: Un'ampia valutazione comparativa su 47 dataset (tabellari, visione, linguaggio, grafi e visione-linguaggio) dimostra che ProxySHAP stabilisce un nuovo standard dello stato dell'arte. Raggiunge l'errore più basso sia nei regimi a budget ridotto (dove supera ProxySPEX) sia nei regimi a budget elevato (dove supera KernelSHAP-IQ).

Risultati

• Accuratezza: ProxySHAP supera costantemente le linee di base (KernelSHAP-IQ, ProxySPEX, SHAP-IQ) in termini di Errore Quadratico Medio Relativo (MSE). In applicazioni su larga scala con migliaia di caratteristiche (ad es. Bioresponse con $n=1776$), ProxySHAP rimane efficace dove altri metodi diventano computazionalmente non fattibili o inaccurati.
• Efficienza: L'algoritmo di estrazione in tempo polinomiale offre accelerazioni di ordini di grandezza (da 10x a 1000x) rispetto all'estrazione basata su Fourier, in particolare all'aumentare della profondità dell'albero.
• Compiti a valle: In una specifica applicazione volta a spiegare il modello visione-linguaggio SigLIP-2 (gioco FIxLIP), ProxySHAP ha dimostrato una fedeltà superiore (misurata dall'Area sotto la curva di Inserzione-Cancellazione) rispetto alle linee di base della regressione lineare e a ProxySPEX.
• Sensibilità agli Iperparametri: Lo studio evidenzia che la qualità del proxy è critica. L'ottimizzazione degli iperparametri (HPO) migliora significativamente le prestazioni e viene proposta una configurazione predefinita "informata dall'HPO" (utilizzando molti alberi poco profondi) per bilanciare costo e accuratezza.

Significato e Affermazioni
Il documento afferma che ProxySHAP risolve il compromesso di lunga data tra velocità e accuratezza nella stima delle interazioni. Fornendo un meccanismo di estrazione esatto per i proxy ad albero e una strategia teoricamente fondata per la correzione del residuo, abilita la quantificazione scalabile di dipendenze complesse nei moderni sistemi di intelligenza artificiale. Gli autori sottolineano che il loro metodo è particolarmente prezioso per:

• Applicazioni su larga scala: Gestione di dataset con migliaia di caratteristiche dove il calcolo esatto è impossibile.
• Interazioni di ordine superiore: Fornire stime affidabili per interazioni oltre gli effetti a coppie, cruciali per comprendere le dipendenze cross-modali (ad es. nei modelli visione-linguaggio) e le sinergie complesse delle caratteristiche.
• Implementazione pratica: Offrire uno stimatore "stato dell'arte" robusto attraverso vincoli di budget variabili e tipi di modello, supportato da un'implementazione scalabile in C++.

Gli autori notano con modestia le limitazioni, specificamente che la qualità dell'approssimazione dipende dal proxy adattato (richiedendo una regolazione attenta degli iperparametri) e che la varianza della correzione del residuo ne limita l'utilità in impostazioni ad altissima dimensionalità per interazioni di ordine elevato. Si suggerisce un lavoro futuro per esplorare classi di proxy alternative e stimatori di residui che scalino in modo più elegante.