Amortized Linear-time Exact Shapley Value for Product-Kernel Methods

Riassunto Tecnico: Valore di Shapley Esatto in Tempo Lineare Ammortizzato per Metodi a Kernel Prodotto

Enunciato del Problema
I metodi a kernel sono ampiamente adottati nell'apprendimento automatico e nella statistica per la loro flessibilità e potenza espressiva, eppure la loro natura "scatola nera" ostacola l'adozione in applicazioni ad alto rischio. Sebbene i metodi di attribuzione basati sul valore di Shapley (ad es. SHAP, RKHS-SHAP) offrano un quadro teorico solido per l'interpretabilità, il calcolo esatto dei valori di Shapley è generalmente intrattabile a causa del numero esponenziale di sottoinsiemi di caratteristiche ($2^d$). Gli approcci esistenti si basano su approssimazioni (ad es. campionamento Monte Carlo, stimatori basati su regressione) che comportano errori di stima inevitabili, i quali crescono con la dimensionalità. Inoltre, le funzioni di valore standard richiedono spesso il campionamento da distribuzioni marginali o condizionate o la stima della densità, introducendo oneri computazionali aggiuntivi e dipendenze dai dati di sfondo.

Metodologia
Il documento introduce PKeX-Shapley, un algoritmo progettato per calcolare i valori di Shapley esatti per tutte le $d$ caratteristiche dei metodi a kernel prodotto (ad es. Macchine a Vettori di Supporto, Regressione a Ridge a Kernel) in tempo quadratico rispetto al numero di caratteristiche ($O(d^2)$), o in tempo lineare ammortizzato per caratteristica.

La metodologia si fonda su tre componenti fondamentali:

1. Operatore di Rimozione Indipendente dalla Distribuzione: Gli autori si concentrano sulla sottoclasse di modelli che impiegano kernel prodotto, dove la funzione kernel si fattorizza come $k(x, x') = \prod_{j=1}^d k_j(x_j, x'_j)$. Essi identificano un operatore di rimozione naturale intrinseco a questa struttura: rimuovere una caratteristica $j$ corrisponde a sostituire il suo fattore di kernel $k_j$ con l'identità moltiplicativa ($1$). Questa scelta preserva la struttura prodotto, non richiede alcuna distribuzione di sfondo e induce una funzione di valore priva di parametri.

   • A differenza delle funzioni di valore interventiste o osservative che richiedono campionamento, questa funzione di valore è definita tramite decomposizione funzionale.
   • La funzione di valore per una coalizione $S$ è data da $v_x(S) = \alpha^\top k_S(X_S, x_S) - f_\emptyset$, dove $f_\emptyset$ è un termine costante che si annulla nei contributi marginali. Questa formulazione non richiede campionamento né stima della densità.

2. Decomposizione Funzionale: Sfruttando l'operatore di rimozione, il modello $f(x)$ viene decomposto univocamente in una somma di componenti indicizzate per sottoinsiemi di caratteristiche: $f(x) = \sum_{S \subseteq D} f_S(x_S)$. Le componenti sono derivate tramite inversione di Möbius sul reticolo dei sottoinsiemi, ottenendo una forma chiusa: $f_S(x_S) = \sum_{i=1}^n \alpha_i \prod_{j \in S} (k_j(x_j, x^{(i)}_j) - 1)$.

3. Calcolo Ricorsivo tramite Polinomi Simmetrici Elementari (ESPs):

   • Il valore di Shapley per una singola caratteristica è espresso come una somma pesata di contributi marginali, che si fattorizza in termini che coinvolgono i Polinomi Simmetrici Elementari (ESPs) delle valutazioni del kernel.
   • Il calcolo diretto degli ESPs per ogni caratteristica sarebbe inefficiente. Gli autori derivano una formulazione ricorsiva basata sulle identità di Newton.
   • Per calcolare congiuntamente tutti i $d$ valori di Shapley, essi impiegano una costruzione prefisso-suffisso. Definiscono polinomi generatori per il prefisso (caratteristiche prima di $j$) e il suffisso (caratteristiche dopo $j$) dell'insieme delle caratteristiche. Moltiplicando questi polinomi, recuperano gli ESPs per l'insieme leave-one-out $Z_{-j}$.
   • Ciò consente il calcolo di tutti i valori di Shapley in tempo $O(d^2 n)$, dove $n$ è il numero di campioni. L'algoritmo è numericamente stabile, basandosi solo su addizioni e moltiplicazioni elemento per elemento, evitando l'instabilità numerica associata ai metodi di interpolazione polinomiale (ad es. interpolazione di Chebyshev o Fourier) utilizzati in altri metodi esatti come TreeSHAP quando applicati ad alte dimensionalità.

Estensione alle Discrepanze Statistiche
Il framework è esteso oltre la modellazione predittiva alle discrepanze statistiche basate su kernel, specificamente:

• Discrepanza Massima del Mezzo (MMD): Utilizzata per misurare la vicinanza distribuzionale. L'operatore di rimozione produce una funzione di valore che alloca la discrepanza complessiva tra due distribuzioni alle singole variabili.
• Criterio di Indipendenza di Hilbert–Schmidt (HSIC): Utilizzato per misurare la dipendenza tra variabili casuali. Il metodo fornisce una decomposizione funzionale dell'HSIC, consentendo l'attribuzione della dipendenza a specifiche caratteristiche.

Risultati
Il documento convalida PKeX-Shapley attraverso esperimenti su dataset sintetici e reali:

• Accuratezza vs. Approssimazione: Nelle spiegazioni locali, PKeX-Shapley (esatto) supera significativamente le approssimazioni basate sul campionamento (ad es. Kernel SHAP, RKHS-SHAP). All'aumentare della dimensionalità (ad es. $d=50$), i metodi basati sul campionamento richiedono dimensioni di coalizione proibitivamente grandi per ottenere un errore basso, whereas PKeX-Shapley fornisce risultati esatti indipendentemente dalla dimensionalità.
• Selezione delle Caratteristiche: Nell'analisi di sensibilità globale utilizzando HSIC, PKeX-Shapley identifica efficacemente le caratteristiche attive in compiti di regressione sintetica con funzioni target polinomiali ed esponenziali, superando o eguagliando le linee di base come RKHS-SHAP, GEMFIX e BiSHAP.
• Efficienza Computazionale: L'algoritmo scala fino a 1.000 caratteristiche in pochi secondi, mentre il calcolo brute-force è limitato a circa 20 caratteristiche. È costantemente più veloce dei metodi basati sul campionamento, anche quando tali metodi utilizzano un numero ridotto di campioni di coalizione.
• Stabilità Numerica: Esperimenti che confrontano diverse strategie di aggregazione degli ESPs (ricorsione quadratica vs. interpolazione FFT/Chebyshev) mostrano che, sebbene i metodi di interpolazione siano veloci, soffrono di instabilità numerica catastrofica a dimensionalità moderate ($d \approx 50$). La ricorsione quadratica proposta rimane stabile fino a $d=1000$.

Significato e Affermazioni
Il documento afferma che PKeX-Shapley affronta le due sfide principali del calcolo del valore di Shapley per i metodi a kernel:

1. Esattezza senza Approssimazione: Fornisce una funzione di valore in forma chiusa e priva di parametri che elimina la necessità di campionamento e stima della densità, rimuovendo così l'errore di stima.
2. Scalabilità: Raggiunge un tempo lineare ammortizzato per caratteristica ($O(dn)$) per il calcolo esatto, un miglioramento significativo rispetto al costo esponenziale del brute-force o all'alta varianza dei metodi di campionamento in contesti ad alta dimensionalità.

Gli autori sottolineano che, sebbene il metodo sia limitato ai kernel prodotto, questo vincolo strutturale è necessario per un calcolo esatto trattabile. L'estensione del framework a MMD e HSIC fornisce nuovi strumenti per l'analisi statistica interpretabile, consentendo l'attribuzione di differenze distribuzionali e dipendenze a variabili specifiche senza fare affidamento su approssimazioni euristiche. Gli autori notano che il metodo non si estende naturalmente all'attribuzione stocastica (ad es. varianza dei valori di Shapley nei Processi Gaussiani) nello stesso modo in cui lo fanno i metodi per i GP FANOVA, poiché l'ortogonalità non vale generalmente per i kernel prodotto.