Sintesi Tecnica: Valori di Shapley e Interazioni Trattabili tramite Reti Tensoriali

Definizione del Problema

Spiegare le predizioni di modelli di apprendimento automatico tramite i valori di Shapley e le loro generalizzazioni di ordine superiore (Indici di Interazione di Shapley, SII) è fondamentale per il supporto decisionale e l'interpretabilità. Tuttavia, calcolare questi indici è computazionalmente proibitivo per modelli con $n$ caratteristiche, poiché richiede tradizionalmente l'enumerazione di $O(2^n)$ coalizioni. Le soluzioni esistenti affrontano scambi significativi (trade-off):

• Assunzioni Strutturali: Metodi come TreeSHAP o quelli per i Modelli Additivi Generalizzati (GAM) sono esatti solo per architetture specifiche (ad es., alberi, modelli lineari).
• Approssimazioni Basate sul Campionamento: Approcci come KernelSHAP o SHAP-IQ si affidano a un pesante campionamento, richiedendo una delicata calibrazione della varianza e spesso fallendo nel scalare verso interazioni di ordine superiore senza costi computazionali massicci.
• Stima Ammortizzata: I metodi che addestrano modelli ausiliari spesso comportano un overhead di addestramento significativo e possono mancare di garanzie teoriche sulla fedeltà della spiegazione.

La sfida centrale è calcolare i valori di Shapley e le interazioni in modo esatto (o con errore controllato) per predittori generali senza enumerazione esponenziale o eccessivo campionamento.

Metodologia: TN-SHAP

Gli autori propongono TN-SHAP, un metodo che sostituisce l'enumerazione esaustiva delle coalizioni con uno schema di poche valutazioni su un surrogato a Rete Tensoriale (TN). L'approccio sfrutta tre intuizioni chiave per ridurre la complessità da $O(2^n)$ a $O(n \cdot \text{poly}(\chi))$, dove $\chi$ è la dimensione massima del legame (bond dimension) della rete tensoriale.

1. Rappresentazione Multilineare ed Estrazione dei Coefficienti

Il metodo assume che il predittore $f$ possa essere ben approssimato da una funzione multilineare $g$ in uno spazio di caratteristiche elevato (lifted feature space). In un'espansione multilineare, $f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$, i valori delle coalizioni corrispondono a combinazioni lineari di coefficienti tensoriali. Fondamentalmente, i valori di Shapley dipendono solo dai contributi marginali aggregati per dimensione (somme di contributi per coalizioni di dimensione $s$), piuttosto che sulle specifiche appartenenze alle coalizioni.

2. Selettori Diagonali e Interpolazione Polinomiale

Invece di interrogare $2^n$ coalizioni, TN-SHAP utilizza matrici selettrici diagonali $S_r(t) = \text{Diag}(t, 1)$ applicate alle caratteristiche elevate $\tilde{x}_r = [\phi(x_r), 1]^\top$.

• Valutando il surrogato $g$ in punti in cui le caratteristiche sono scalate da un parametro $t$, il metodo aggrega tutte le coalizioni di dimensione $s$ nel coefficiente di $t^s$ in un polinomio risultante $P(t)$.
• Nello specifico, per una caratteristica target $i$, viene costruita una funzione sonda $G_i(t)$ per isolare il contributo marginale di $i$ attraverso tutti i sottoinsiemi di altre caratteristiche.
• Questo trasforma il problema combinatorio in interpolazione polinomiale. Valutando $G_i(t)$ in $n$ punti distinti (ad es., nodi di Chebyshev-Gauss), il sistema risolve un sistema lineare di Vandermonde per recuperare i contributi marginali aggregati per dimensione $\{m_s^{(i)}\}$.
• Il valore di Shapley viene quindi calcolato come una somma pesata di questi coefficienti recuperati.

3. Surrogati a Rete Tensoriale (Tensor Network)

Per rendere trattabile la valutazione della mappa multilineare su larga scala, il tensore dei coefficienti viene fattorizzato in una Rete Tensoriale (TN) (ad es., Tensor Train o Albero Gerarchico) con dimensione del legame $\chi$.

• Mappe di Caratteristiche: Per gestire dati reali non lineari, le caratteristiche scalari vengono elevate tramite mappe apprese o artigianali $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$ prima di entrare nella TN. Ciò preserva la multilinearità nello spazio elevato pur permettendo al surrogato di modellare le non linearità nello spazio di input originale.
• Efficienza: Ogni passaggio in avanti (forward pass) attraverso la TN costa $O(\text{poly}(\chi))$. Poiché sono necessarie solo $O(n)$ valutazioni per l'interpolazione, la complessità totale per calcolare le interazioni di ordine $k$ diventa polinomiale in $n$.

Contributi Chiave

1. Schema Unificato Prova-Interpolazione: Un algoritmo esatto per calcolare i valori di Shapley e le interazioni a $k$-vie su un surrogato multilineare TN utilizzando solo $O(n)$ passaggi in avanti strutturati, evitando $O(2^n)$ query.
2. Surrogati Potenziati da Mappe di Caratteristiche: Un framework che dimostra come gli elevamenti (lifts) delle caratteristiche appresi preservino la multilinearità necessaria per il calcolo esatto migliorando al contempo la fedeltà del surrogato.
3. Garanzie Teoriche:
   • Esattezza: Il metodo calcola i valori di Shapley esattamente sul surrogato multilineare adattato.
   • Errore di Approssimazione: L'errore rispetto al modello originale è limitato dall'errore di approssimazione delle coalizioni worst-case del surrogato ($\epsilon$). Per i valori di Shapley, $|\phi^g_i - \phi^f_i| \leq 2\epsilon$.
   • Trattabilità: Riduzione provata dalla complessità esponenziale a quella polinomiale $O(n \cdot \text{poly}(\chi) + n^2)$.

Risultati Sperimentali

Gli autori hanno valutato TN-SHAP su funzioni multilineari sintetiche e dataset di regressione UCI reali (Concrete, Diabetes, Energy) utilizzando insegnanti (teacher) MLP.

• Validazione Sintetica: Su funzioni esattamente multilineari, TN-SHAP ha raggiunto l'esattezza teorica con tempi di esecuzione nell'ordine dei millisecondi, superando KernelSHAP-IQ di ordini di grandezza (ad es., 3,5 ms vs 18,7 ms per $n=10$; 19,7 ms vs 447,3 ms per $n=50$).
• Accuratezza nel Mondo Reale: Sui dataset UCI con insegnanti MLP:
  • TN-SHAP ha ottenuto accelerazioni di wall-clock da 25 a 1000 volte rispetto a KernelSHAP-IQ a parità di accuratezza.
  • Per le attribuzioni di primo ordine ($k=1$), TN-SHAP ha raggiunto una similitudine del coseno quasi perfetta (0,994) con la verità fondamentale (ground truth).
  • Per le interazioni di ordine superiore ($k=2, 3$), TN-SHAP ha mantenuto un'accuratezza competitiva mentre i baselines basati sul campionamento faticavano con la varianza o richiedevano molto più tempo di calcolo per raggiungere una fedeltà simile.
• Ablazione del Rank: Gli esperimenti hanno mostrato che un rank dello studente TN di $r=5-6$ era sufficiente per recuperare tutte le interazioni con $R^2 > 0,99$ quando l'insegnante aveva un rank di 16. Rank inferiori sottostimavano le interazioni di ordine superiore.
• Stabilità ad Alta Dimensionalità: In contesti sintetici ad alta dimensionalità ($D=50, 100$), TN-SHAP ha mantenuto un'alta fedeltà del surrogato ($R^2 > 0,95$) e un forte recupero delle caratteristiche Top-$k$ sotto budget di query a costo lineare.

Significato e Rivendicazioni

L'articolo sostiene che TN-SHAP colmi il divario tra il rigore teorico del calcolo esatto di Shapley e la necessità pratica di efficienza. Sfruttando la struttura algebrica delle funzioni multilineari e l'efficienza delle reti tensoriali, il metodo:

• Trasforma un problema di enumerazione esponenziale in un piccolo numero di valutazioni strutturate.
• Fornisce garanzie strutturali (tramite limiti di rank) che affrontano i problemi di fedeltà comuni nei metodi surrogati locali non vincolati come LIME.
• Unifica le spiegazioni di Shapley locali con le strutture additive globali (GAM), poiché l'adattamento di un surrogato di ordine $k$ produce coefficienti $k$-SII esatti che corrispondono ai termini GAM corrispondenti.
• Offre un'alternativa scalabile ai metodi basati sul campionamento, in particolare per le interazioni di ordine superiore dove la varianza del campionamento è tipicamente elevata.

Gli autori osservano che le prestazioni del metodo dipendono dalla qualità del fit del surrogato TN e dalla scelta delle mappe di caratteristiche, ma i risultati empirici suggeriscono che anche modesti elevamenti delle caratteristiche e rank tensoriali sono sufficienti per catturare strutture coalizionali complesse nella pratica.