Sintesi Tecnica: ShaplEIG

Definizione del Problema

I valori di Shapley (SV) fungono da misura di attribuzione fondata per l'apprendimento automatico interpretabile, tuttavia il loro calcolo esatto è spesso intrattabile. L'onere computazionale deriva da due fattori: la crescita esponenziale delle coalizioni ($2^p$) con il numero di giocatori $p$, e l'elevato costo di valutazione della funzione di valore $\nu$ per ogni coalizione. In applicazioni come l'importanza delle feature basata sul riaddestramento, la valutazione dei dati e l'importanza degli iperparametri, le valutazioni della funzione di valore possono comportare il riaddestramento completo del modello o un'inferenza costosa, limitando severamente il budget di valutazione.

I metodi di approssimazione esistenti, inclusi il campionamento Monte Carlo e gli approcci basati su surrogati (ad esempio, Kernel SHAP, Regression MSR), si affidano tipicamente a distribuzioni di campionamento fisse e non adattive. Ciò solleva la questione se l'accuratezza dell'approssimazione possa essere migliorata selezionando adattivamente le coalizioni per la valutazione sulla base delle osservazioni precedenti, in particolare nei regimi a basso budget. Sebbene il Bayesian Experimental Design (BED) offra un framework per la progettazione sequenziale tramite l'Expected Information Gain (EIG), il suo adozione nella stima degli SV è stata limitata dalla mancanza di espressioni EIG in forma chiusa e dall'intrattabilità computazionale della stima dell'EIG per spazi discreti ad alta dimensionalità.

Metodologia

Gli autori propongono ShaplEIG, un approccio di Bayesian experimental design che seleziona adattivamente le coalizioni per massimizzare il guadagno di informazione riguardo ai valori di Shapley.

1. Processo Gaussiano Surrogato con Kernel di Hamming

ShaplEIG modella la funzione di valore $\nu$ utilizzando un surrogato di Processo Gaussiano (GP). Per gestire lo spazio di input binario delle coalizioni (rappresentate come vettori indicatori $z \in \{0, 1\}^p$), il metodo impiega un kernel della distanza di Hamming. Questo kernel quantifica la somiglianza tra le coalizioni basandosi su distanze di Hamming pesate, con iperparametri di lunghezza scala $\xi$ apprendibili. Il GP fornisce una distribuzione a posteriori sulla funzione di valore attraverso tutte le $2^p$ coalizioni dato un dataset $D_t$ di valutazioni osservate.

2. Stima degli SV Coerente tramite Linearità

Un insight teorico chiave è la linearità dei valori di Shapley rispetto alla funzione di valore. Gli SV $\phi$ possono essere espressi come una trasformazione lineare del vettore della funzione di valore $\nu$: $\phi = A\nu$, dove $A$ è una matrice nota derivata dalla formula di Shapley. Di conseguenza, sotto il surrogato GP, la distribuzione a posteriori sugli SV è anch'essa Gaussiana ed è disponibile in forma chiusa:
$$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$$
Gli autori estraggono le stime degli SV dalla media a posteriori, $\hat{\phi} = A\mu_{\nu|D_t}$. Fondamentalmente, per i GP privi di rumore (o quasi privi di rumore), questo stimatore è coerente: se tutte le $2^p$ coalizioni vengono valutate, le stime convergono esattamente ai veri valori di Shapley.

3. EIG in Forma Chiusa

Il contributo principale è la derivazione di un'espressione in forma chiusa per l'EIG di una coalizione candidata $z^{(i)}$ rispetto agli SV. Inquadrando la selezione sequenziale come un problema inverso lineare bayesiano in cui gli SV sono un obiettivo lineare finale, si dimostra che l'EIG dipende solo dalla covarianza a posteriori degli SV:
$$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$$
Ciò evita le aspettative annidate tipicamente richieste nel BED, poiché l'EIG dipende esclusivamente dal design sperimentale (la coalizione selezionata) e non dal risultato specifico $y(x)$.

4. Computazione Efficiente tramite Polinomi Simmetrici Elementari

La computazione diretta dell'EIG comporta operazioni su matrici di dimensione $2^p \times 2^p$, portando a una complessità esponenziale. Gli autori propongono uno schema di computazione efficiente che riduce la complessità a tempo polinomiale ($O(p^4 + t^3)$) sfruttando la struttura moltiplicativa del kernel di Hamming.

• I termini richiesti per l'EIG (specificamente $A\Sigma_{\nu|D_t}e_i$ e $A\Sigma_{\nu|D_t}A^\top$) vengono risccritti come somme pesate di valutazioni del kernel.
• Queste somme sono identificate con polinomi simmetrici elementari (ESP) scalati.
• Computando questi polinomi in modo efficiente (utilizzando la programmazione dinamica e tabelle di prefisso/suffisso), il metodo evita l'enumerazione esplicita di tutte le coalizioni.

5. Algoritmo

L'algoritmo procede in modo avido (greedy):

1. Inizializzare con un piccolo design (ad esempio, leverage score sampling).
2. Adattare il surrogato GP e ottimizzare gli iperparametri.
3. Computare l'EIG per tutte le coalizioni candidate utilizzando lo schema polinomiale efficiente.
4. Selezionare la coalizione con il massimo EIG, valutare la funzione di valore e aggiornare il dataset.
5. Ripetere fino a esaurimento del budget.

Contributi Chiave

1. Framework ShaplEIG: Introduzione di un nuovo metodo basato su BED per la stima degli SV che utilizza un surrogato GP con un kernel di Hamming e seleziona adattivamente le coalizioni in base all'EIG.
2. EIG in Forma Chiusa: Dimostrazione che l'EIG per i valori di Shapley ammette un'espressione in forma chiusa sotto un surrogato GP, sfruttando la linearità degli SV rispetto alla funzione di valore.
3. Complessità Polinomiale: Proposta di uno schema di computazione efficiente per l'EIG che riduce la complessità da esponenziale a polinomiale rispetto al numero di giocatori ($p$) tramite polinomi simmetrici elementari.
4. Stima Coerente: Fornitura di uno stimatore di SV coerente che converge ai valori esatti quando tutte le coalizioni vengono valutate, contrastando con alcuni metodi di surrogato basati su alberi che richiedono ulteriori passaggi di aggiustamento.

Risultati Sperimentali

Gli autori valutano ShaplEIG attraverso diverse applicazioni costose che coinvolgono giochi piccoli o moderatamente grandi ($8 \le p \le 101$):

• Task: Importanza globale delle feature (TabPFN), valutazione dei dati (Random Forest, Gradient Boosting), importanza degli iperparametri (XGBoost, LCBench) e spiegazioni locali (ResNet, ViT, Random Forest).
• Baseline: Confronto con Kernel SHAP, Leverage SHAP, Permutation Sampling e lo stato dell'arte Regression MSR (accoppiato con XGBoost).
• Ablazioni: Confronto con varianti che utilizzano lo stesso surrogato GP ma diverse strategie di selezione (Random, Uncertainty Sampling, Leverage Score Sampling).

Risultati:

• Efficienza di Campionamento: ShaplEIG raggiunge costantemente la migliore accuratezza complessiva (MSE più basso) nel regime a basso budget nella maggior parte dei task. Spesso domina nettamente i concorrenti, in particolare in giochi asimmetrici dove le interazioni tra i giocatori non sono uniformi.
• Approfondimenti dalle Ablazioni: Le forti prestazioni sono attribuite principalmente alla strategia di selezione basata su EIG piuttosto che al semplice uso di un surrogato GP. L'Uncertainty Sampling (US) ha spesso performato peggio del campionamento casuale, evidenziando che massimizzare la varianza marginale non equivale a massimizzare l'informazione riguardo agli SV linearmente trasformati.
• Scalabilità: Per giochi più grandi ($p > 16$), il metodo rimane efficace anche se il riadattamento degli iperparametri viene eseguito su un programma prestabilito anziché a ogni iterazione.
• Costo Computazionale: Sebbene la computazione dell'EIG sia efficiente (secondi), l'adattamento degli iperparametri può diventare un collo di bottiglia per grandi $p$ (fino a 25 minuti per iterazione per $p \approx 100$). Gli autori notano che ShaplEIG è più appropriato quando le valutazioni della funzione di valore sono genuinamente costose, giustificando l'overhead.

Significato e Rivendicazioni

Il documento afferma che ShaplEIG fornisce un framework fondato per migliorare l'efficienza di campionamento nella stima degli SV per giochi costosi. Derivando un'espressione EIG in forma chiusa e uno schema di computazione efficiente in tempo polinomiale, gli autori superano le principali barriere all'applicazione del Bayesian Experimental Design in questo dominio.

Gli autori dichiarano con modestia che, sebbene il metodo comporti un overhead computazionale dovuto all'ottimizzazione ripetuta del GP, esso offre guadagni sostanziali nell'accuratezza della stima quando i budget di valutazione sono limitati. Riconoscono che per giochi molto grandi o funzioni di valore meno costose, l'overhead potrebbe essere proibitivo, suggerendo che il lavoro futuro dovrebbe concentrarsi su ulteriori miglioramenti computazionali per ampliare l'applicabilità del metodo. Il lavoro non pretende di risolvere la stima degli SV per tutti gli scenari, ma mira specificamente al regime di funzioni di valore costose dove la selezione adattiva è critica.