Sintesi Tecnica: Un Estimatore "Dispari" per i Valori di Shapley

Definizione del Problema

Il valore di Shapley è il framework standard per l'attribuzione nel machine learning, utilizzato per l'importanza delle feature, la valutazione dei dati e l'inferenza causale. Tuttavia, la sua computazione esatta è generalmente intrattabile a causa del numero esponenziale di coalizioni ($2^d$) richieste per la valutazione. Sebbene esistano metodi di approssimazione, gli stimatori più efficaci si basano spesso sul "campionamento a coppie" (campionando una coalizione $S$ e il suo complemento $S^c$), un'euristica che migliora empiricamente l'accuratezza ma che manca di una rigorosa giustificazione teorica sul perché funzioni, in particolare riguardo alle interazioni di ordine superiore. Inoltre, gli esistenti metodi di regressione polinomiale di ordine superiore (ad esempio, PolySHAP) affrontano un collo di bottiglia di scalabilità in cui il costo computazionale cresce quadraticamente con la dimensione della base polinomiale, limitandone l'applicazione in contesti ad alta dimensionalità.

Metodologia

Gli autori propongono OddSHAP, un nuovo stimatore che sfrutta una proprietà strutturale fondamentale del valore di Shapley: esso dipende esclusivamente dalla componente dispari della funzione di valore $f$.

Fondamento Teorico

1. Decomposizione Pari-Dispari: Qualsiasi funzione di insieme $f$ può essere unicamente decomposta in una componente dispari ($f_{odd}$) e una componente pari ($f_{even}$), dove $f_{odd}(S) = -f_{odd}(S^c)$ e $f_{even}(S) = f_{even}(S^c)$.
2. Proprietà del Valore di Shapley: Gli autori dimostrano che $\phi_i(f) = \phi_i(f_{odd})$ per tutti i giocatori $i$. La componente pari contribuisce con zero al valore di Shapley.
3. Meccanismo del Campionamento a Coppie: Il documento fornisce la prima giustificazione teorica generale per il campionamento a coppie. Campionando coppie $(S, S^c)$ con pesi simmetrici, il problema di regressione dei minimi quadrati pesati si ortogonalizza (decouple) in problemi di ottimizzazione indipendenti per le componenti dispari e pari. Poiché la componente pari è irrilevante, il campionamento a coppie isola efficacemente il segnale necessario per i valori di Shapley. Ciò risolve una congettura secondo cui il campionamento a coppie con un fit di ordine-$k$ (per $k$ dispari) è equivalente a un fit di ordine-$(k+1)$.

Design dell'Algoritmo: OddSHAP

Per sfruttare questa intuizione evitando l'esplosione combinatoria del fitting di tutti i termini di ordine superiore, OddSHAP opera nella base di Fourier piuttosto che nella base di unanimità.

• Vantaggio della Base di Fourier: Nella base di Fourier, una funzione di base $\chi_T$ è dispari se e solo se la cardinalità $|T|$ è dispari. Ciò consente una separazione netta tra i termini dispari e pari, a differenza della base di unanimità.
• Processo in Due Fasi:
  1. Screening delle Interazioni: Viene adattato un modello proxy basato su Gradient Boosted Tree (GBT) alle coalizioni campionate. Utilizzando un metodo come ProxySPEX, l'algoritmo estrae un insieme sparso di coefficienti di Fourier di ordine dispari ad alto impatto. Questo evita la necessità di calcolare tutte le possibili interazioni.
  2. Regressione Dispare: Una regressione dei minimi quadrati pesati viene eseguita strettamente sui termini selezionati della base di Fourier di ordine dispari (più i termini lineari), con il vincolo di corrispondere alla funzione di valore sugli insiemi vuoto e completo.
• Efficienza: Limitando la regressione allo spazio sottostante dispari e utilizzando un proxy per selezionare i termini, il metodo raggiunge una complessità temporale polinomiale rispetto al budget di campionamento, superando la scalabilità $O(d^k)$ dei metodi polinomiali a ordine fisso.

Contributi Chiave

1. Unificazione Teorica del Campionamento a Coppie: Il documento dimostra che il campionamento a coppie decupla implicitamente l'obiettivo di regressione nelle componenti dispari e pari, fornendo una spiegazione rigorosa del successo empirico e generalizzando i risultati precedenti limitati a basse interazioni di ordine.
2. Lo Stimatore OddSHAP: Un estimatore consistente che esegue la regressione polinomiale esclusivamente su una selezione sparsa di funzioni della base di Fourier di ordine dispari. Esso filtra i componenti pari irrilevanti e identifica le interazioni ad alto impatto tramite un modello proxy.
3. Prestazioni allo Stato dell'Arte: Benchmark estesi dimostrano che OddSHAP raggiunge un'accuratezza di stima superiore rispetto ai metodi esistenti (inclusi RegressionMSR, LeverageSHAP e PolySHAP) sotto budget di campionamento maggiori, particolarmente in contesti ad alta dimensionalità.

Risultati Sperimentali

Gli autori hanno valutato OddSHAP su otto funzioni di valore che vanno da $d=14$ (DistilBERT) a $d=101$ (dataset Crime), coprendo domini di deep learning (immagini e testo) e tabulari.

• Accuratezza: OddSHKAP ha costantemente ottenuto l'errore quadratico medio (MSE) più basso e il miglior rango medio tra i benchmark, specialmente quando il budget di campionamento $m$ è sufficiente per rilevare le interazioni ($m > \eta \cdot d$).
• Confronto con FFD: OddSHAP ha superato il design fattoriale frazionario a budget fisso (FFD-RD) sulle architetture di deep learning (ViT, DistilBERT), dove le interazioni di ordine superiore sono significative. Al contrario, FFD-RD è stato leggermente migliore sui dataset tabulari basati su alberi, dove le interazioni di ordine superiore decadono rapidamente, validando i trade-off specifici del dominio.
• Studi di Ablazione:
  • Campionamento a Coppie vs. Non a Coppie: Il campionamento a coppie ha costantemente superato il campionamento non a coppie.
  • Interazioni Dispari vs. Tutte le Interazioni: Sotto campionamento a coppie, l'inclusione di interazioni pari non ha fornito alcun beneficio e ha leggermente degradato le prestazioni consumando il budget delle interazioni con termini matematicamente annullanti.
  • Sparsità: L'incorporazione di un numero moderato di interazioni dispari (controllato dal fattore di variabile di regressione $\eta$) ha ridotto significativamente l'errore rispetto ai baseline lineari, sebbene si sia verificato overfitting con troppe interazioni.

Significato e Rivendicazioni

Il paper sostiene che OddSHAP offre un framework a budget flessibile che si adatta robustamente attraverso diversi tipi di strutture di interazione. Il suo significato primario risiede in:

1. Risoluzione di una Congettura Aperta: Fornisce il meccanismo teorico fondamentale che spiega perché il campionamento a coppie funzioni, andando oltre l'osservazione empirica verso una prova strutturale.
2. Scalabilità: Mantiene il potere espressivo delle approssimazioni di ordine superiore senza incorrere nei loro proibitivi costi combinatori, limitandosi allo spazio sottostante dispari.
3. Robustezza: A differenza dei metodi che si affidano a rigidi assunti di troncamento (come FFD), OddSHAP rimane efficace in domini complessi di deep learning dove le interazioni di alto ordine non sono trascurabili, mantenendo al contempo la competitività nei domini tabulari sparsi.

Gli autori notano dei limiti, nello specifico che il tempo di esecuzione dell'algoritmo scala cubicamente con il budget a causa del costo quadratico della regressione sulle interazioni selezionate, e che il campionamento a coppie riduce il numero effettivo di campioni indipendenti, potenzialmente gonfiando la varianza. Tuttavia, concludono che il metodo rappresenta un approccio allo stato dell'arte per la stima del valore di Shapley in contesti agnostici rispetto al modello.