Riepilogo Tecnico: PolySHAP – Estensione di KernelSHAP con Regressione Polinomiale Informata dalle Interazioni

Enunciato del Problema

I valori di Shapley sono uno strumento centrale della teoria dei giochi nell'Explainable AI (XAI) per attribuire la previsione di un modello alle sue feature di input. Tuttavia, il calcolo esatto dei valori di Shapley richiede la valutazione del modello su tutti i $2^d$ possibili sottoinsiemi di feature, il che è computazionalmente non fattibile per modelli con un elevato numero di feature $d$.

KernelSHAP (Lundberg & Lee, 2017) si è affermato come un metodo leader per approssimare efficientemente i valori di Shapley. Inquadra il problema come una regressione ai minimi quadrati pesata, approssimando il gioco cooperativo $\nu$ con una funzione lineare adattata a un campione di sottoinsiemi casuali di feature. Sebbene efficace, questa approssimazione lineare assume intrinsecamente l'additività delle feature, fallendo nel catturare le interazioni non lineari tra le stesse. Di conseguenza, KernelSHAP può produrre stime subottimali quando il gioco sottostante presenta interazioni di ordine superiore significative.

Metodologia: PolySHAP

Gli autori propongono PolySHAP, una generalizzazione di KernelSHAP che approssima il gioco $\nu$ utilizzando polinomi di grado superiore anziché una funzione lineare. Questo approccio modella esplicitamente le interazioni non lineari tra le feature.

Meccanismo Principale

1. Rappresentazione Informata dalle Interazioni: Invece di adattare un modello lineare $\sum \phi_i \mathbb{1}[i \in S]$, PolySHAP adatta un polinomio di grado $k$ sugli indicatori binari delle feature $\mathbb{1}[i \in S]$. L'approssimazione include una "frontiera di interazione" $\mathcal{I}$, un sottoinsieme di termini di interazione (sottoinsiemi di feature con dimensione $\ge 2$).
   $$\hat{\nu}(S) \approx \sum_{T \in \mathcal{D} \cup \mathcal{I}} \phi_T \prod_{j \in T} \mathbb{1}[j \in S]$$
   dove $\mathcal{D}$ rappresenta le singole feature e $\mathcal{I}$ rappresenta i termini di interazione.

2. Formulazione della Regressione: PolySHAP risolve un problema ai minimi quadrati pesati simile a KernelSHAP, ma con una matrice di progetto espansa contenente colonne sia per gli effetti principali che per i termini di interazione selezionati. L'obiettivo minimizza la perdita $\ell_2$ pesata tra i valori del gioco campionati $\nu(S_\ell)$ e l'approssimazione polinomiale.

3. Estrazione dei Valori di Shapley: Un risultato teorico chiave (Teorema 4.3) dimostra che i valori di Shapley del gioco originale possono essere recuperati direttamente dai coefficienti dell'approssimazione polinomiale. Nello specifico, il valore di Shapley per la feature $i$ è la somma del coefficiente per l'effetto principale $\phi_i$ e dei coefficienti di tutti i termini di interazione contenenti $i$, divisi per la dimensione di tali insiemi di interazione:
   $$\phi_i^{SV} = \phi_i + \sum_{S \in \mathcal{I}: i \in S} \frac{\phi_S}{|S|}$$

4. Strategie di Campionamento: Il metodo supporta il campionamento standard e il campionamento accoppiato (campionamento di sottoinsiemi $S$ e dei loro complementi $D \setminus S$). Gli autori utilizzano il campionamento basato sul punteggio di leva (leverage score) per migliorare la qualità della stima, notando che per le interazioni di ordine superiore, i punteggi di leva di ordine 1 (uniformi sulle dimensioni dei sottoinsiemi) funzionano bene nella pratica.

Contributi Chiave

1. Coerenza Teorica ed Estensione

Il documento dimostra che PolySHAP fornisce stime coerenti dei valori di Shapley. Man mano che il numero di campioni $m$ si avvicina al numero totale di sottoinsiemi $2^d$, le stime di PolySHAP convergono esattamente ai veri valori di Shapley (Teorema 4.3). Ciò contrasta con alcuni metodi di approssimazione basati su alberi (ad esempio RegressionMSR) che richiedono passaggi aggiuntivi di aggiustamento della regressione per raggiungere la coerenza.

2. Equivalenza Teorica tra Campionamento Accoppiato e 2-PolySHAP

Un contributo teorico maggiore è la dimostrazione che KernelSHAP con campionamento accoppiato è matematicamente equivalente a 2-PolySHAP (Teorema 5.1).

• Quando i sottoinsiemi sono campionati in coppie ($S$ e $D \setminus S$), la soluzione di regressione lineare di KernelSHAP produce le stesse approssimazioni dei valori di Shapley di una regressione polinomiale di secondo ordine (2-PolySHAP).
• Questa scoperta fornisce la prima forte giustificazione teorica per il successo empirico del campionamento accoppiato, spiegando che cattura implicitamente tutte le interazioni di secondo ordine senza adattarsi esplicitamente a un polinomio di grado 2.

3. Prestazioni Empiriche

Estesi esperimenti su 15 giochi di spiegazione locale (che coprono domini tabulari, immagini e linguaggio) dimostrano che:

• Accuratezza di ordine superiore: Aumentare il grado del polinomio (ad esempio, 3-PolySHAP) migliora costantemente la qualità dell'approssimazione (misurata tramite MSE, Precision@5 e correlazione di Spearman) rispetto a KernelSHAP (1-PolySHAP) e al Campionamento per Permutazione, a condizione che il budget di campionamento sia sufficiente.
• Efficienza del Campionamento Accoppiato: Sotto campionamento accoppiato, KernelSHAP raggiunge prestazioni comparabili a 2-PolySHAP, validando l'equivalenza teorica.
• Risultati all'avanguardia: In contesti a dimensionalità da bassa a moderata, PolySHAP (in particolare 3-PolySHAP) supera spesso altre linee di base, inclusi RegressionMSR (che si basa su approssimazioni XGBoost) e SVARM.

Significato e Affermazioni

Il documento afferma di offrire un'estensione razionale del framework ampiamente utilizzato KernelSHAP. Passando da approssimazioni lineari a polinomiali, PolySHAP affronta il limite di ignorare le interazioni tra le feature, portando a spiegazioni più accurate per modelli complessi.

Crucialmente, il lavoro colma un divario tra pratiche euristica e teoria. Dimostrando che la popolare euristica del "campionamento accoppiato" è equivalente alla modellazione delle interazioni di secondo ordine, gli autori forniscono una base rigorosa per spiegare perché questa strategia di campionamento funziona così bene nella pratica. Gli autori notano con modestia che, sebbene le interazioni di ordine superiore migliorino l'accuratezza, richiedono budget di campionamento più ampi e, in contesti a dimensionalità molto elevata ($d \ge 60$), i guadagni sono più modesti a causa dell'esplosione combinatoria dei termini di interazione.

Il documento conclude che PolySHAP è un metodo robusto, coerente e empiricamente superiore per la stima dei valori di Shapley, in particolare quando il gioco sottostante coinvolge interazioni non lineari tra le feature.