Riassunto Tecnico: Stima Approssimativa del Valore di Shapley Utilizzando il Campionamento Senza Reintegro e Nuovi Stimatori della Varianza Bootstrap

1. Definizione del Problema

Il classico framework KernelSHAP (Lundberg e Lee, 2017) mira a ridurre il costo computazionale della stima del valore di Shapley campionando un sottoinsieme di coalizioni anziché valutare la funzione di contributo per tutte le $2^p$ possibili sottinsieme. Tuttavia, le implementazioni esistenti tipicamente campionano le coalizioni con reintegro. Questo approccio introduce sfide statistiche specifiche:

1. Inefficienza del Campionamento: Il campionamento con reintegro porta a una versione pesata del Problema del Collezionista di Coupon, dove ottenere coalizioni uniche diventa sempre più difficile all'aumentare della dimensione del campione, particolarmente per le coalizioni a basso peso.
2. Limitazioni della Stima della Varianza: I metodi bootstrap tradizionali assumono campioni indipendenti e identicamente distribuiti (i.i.d.). Tale assunzione è violata quando si campiona senza reintegro da una popolazione finita (l'insieme di tutte le possibili coalizioni). Di conseguenza, le tecniche bootstrap standard possono produrre stime della varianza errate, non riuscendo a tenere conto del vincolo della popolazione finita, dove la varianza dovrebbe teoricamente tendere a zero se venissero valutate tutte le coalizioni.

Il documento affronta questi problemi proponendo un framework che utilizza il campionamento senza reintegro e introduce nuove metodologie bootstrap compatibili con la teoria delle popolazioni finite per stimare accuratamente la varianza dei valori di Shapley approssimati.

2. Metodologia

2.1 Campionamento Senza Reintegro tramite la Distribuzione di Wallenius

L'algoritmo proposto modifica la procedura KernelSHAP per campionare le coalizioni senza reintegro. Il processo prevede due fasi principali:

1. Stratificazione: Le coalizioni sono raggruppate in base al numero di caratteristiche (dimensione) che contengono.
2. Determinazione delle Dimensioni del Campione: Invece di campionare le coalizioni una alla volta in modo stocastico, l'algoritmo calcola il numero atteso di coalizioni da estrarre da ciascun gruppo utilizzando la distribuzione ipergeometrica non centrale di Wallenius. Questa distribuzione modella il campionamento distorto senza reintegro dove gli elementi hanno pesi differenti.
   • L'algoritmo utilizza i valori attesi di questa distribuzione, arrotondati all'intero più vicino, per determinare il numero di coalizioni da campionare da ogni strato.
   • Una volta determinati i conteggi, le coalizioni vengono campionate senza reintegro all'interno di ogni gruppo.
   • Strategia di Accoppiamento: Per ridurre ulteriormente la varianza, il metodo impiega una strategia di accoppiamento (Kroese et al., 2013). Se una coalizione $S$ viene campionata, anche il suo complemento $S^c$ viene incluso nel calcolo, garantendo che la somma delle caratteristiche nei gruppi accoppiati rimanga costante.

2.2 Stima della Varianza tramite Metodi Bootstrap

Il documento valuta tre approcci per stimare la deviazione standard dei valori di Shapley sotto il nuovo design di campionamento:

1. Metodo Intuitivo Non Valido: Uno standard stimatore della varianza di Horvitz-Thompson applicato direttamente al problema dei minimi quadrati pesati. L'autore dimostra che questo è non valido perché non tiene conto delle specifiche dipendenze introdotte dalla strategia di accoppiamento e dalla struttura della matrice $Z^T W Z$ nel contesto di KernelSHAP.
2. Doubled Half Bootstrap (Antal e Tillé, 2014): Un metodo noto per popolazioni finite in cui le unità sono selezionate tramite campionamento di Bernoulli e le unità non selezionate sono selezionate casualmente due volte. Questo metodo è implementato per confronto.
3. Symmetric Bootstrap (Nuovo Contributo): Un nuovo metodo bootstrap sviluppato specificamente per questo contesto.
   • Meccanismo: In ogni campione bootstrap, ogni unità del campione originale può apparire 0, 1 o 2 volte.
   • Simmetria: Il metodo assicura che il numero totale di unità che appaiono 0 volte sia uguale al numero totale di unità che appaiono 2 volte.
   • Probabilità: Le probabilità per un'unità $k$ di apparire $S_k$ volte sono definite come:
     • $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
     • $Pr(S_k = 1) = \frac{n}{N}$
   • Proprietà: Questa costruzione assicura che il valore atteso $E(S_k) = 1$ e la varianza $Var(S_k) = 1 - \frac{n}{N}$, soddisfacendo le condizioni necessarie per una stima valida della varianza nel campionamento di popolazioni finite (coerenza di Horvitz-Thompson).
   • Gestione dei Non-Interi: Quando il numero atteso di occorrenze "0" o "2" non è un intero, viene introdotta una variabile aleatoria di Bernoulli per alternare tra i valori interi adiacenti, garantendo che la procedura rimanga completamente automatica.

2.3 Implementazione Computazionale

La funzione di contributo $v(S)$ è stimata tramite regressione sulle coalizioni campionate. L'implementazione sfrutta matrici sparse e la decomposizione di Cholesky (pacchetto Matrix) per gestire i modelli lineari in modo efficiente, essendo capace di stimare medie su 65.000 modelli lineari su un singolo core in pochi minuti (Aanes, 2025).

3. Contributi Chiave

1. Framework di Campionamento: Integrazione della distribuzione ipergeometrica non centrale di Wallenius nel framework KernelSHAP per consentire un campionamento efficiente senza reintegro, evitando le inefficienze del Problema del Collezionista di Coupon inerenti al campionamento con reintegro.
2. Symmetric Bootstrap: L'introduzione di un nuovo metodo bootstrap, computazionalmente efficiente, progettato per il campionamento senza reintegro in popolazioni finite. Esso soddisfa le necessarie condizioni di momento (media e varianza) per una stima non viesata della varianza in questo contesto.
3. Analisi della Stima della Varianza: Un confronto rigoroso tra stimatori della varianza, che dimostra come il bootstrapping standard sia non valido per questo specifico design e come il nuovo Symmetric bootstrap superi o eguagli il Doubled half bootstrap (Antal e Tillé, 2014).

4. Risultati

Sono stati condotti due studi di simulazione utilizzando il dataset "Life Expectancy" da Kaggle, confrontando il nuovo metodo con lo stato dell'arte del pacchetto R shapr (versione 1.0.7), che campiona con reintegro.

• Piccolo Studio di Simulazione (5 caratteristiche, 16 coalizioni):
  • Il nuovo metodo di campionamento ha prodotto stime dei valori di Shapley con deviazioni standard comparabili a shapr.
  • Il bootstrap Antal-Tillé ha performato male, producendo frequentemente matrici a rango non pieno ($Z^T W Z$) e stime della varianza imprecise.
  • Il Symmetric bootstrap ha performato significativamente meglio di Antal-Tillé, sebbene abbia occasionalmente prodotto deviazioni standard leggermente "liberali" (più piccole) rispetto alla verità fondamentale (ricampionamento di tutte le coalizioni).
• Grande Studio di Simulazione (16 caratteristiche, 402 coalizioni):
  • I metodi Symmetric bootstrap e Antal-Tillé hanno prodotto stime della deviazione standard indistinguibili.
  • Entrambi i nuovi metodi bootstrap hanno performato leggermente meglio della procedura bootstrap integrata in shapr, che tendeva a sottostimare le deviazioni standard per diverse variabili.
  • Il nuovo algoritmo di campionamento (senza reintegro) ha performato in modo simile al metodo shapr (con reintegro) in termini di accuratezza delle stime dei valori di Shapley stessi.

5. Significato e Conclusione

Il documento conclude che l'algoritmo proposto, che combina il campionamento senza reintegro tramite la distribuzione di Wallenius con il nuovo Symmetric bootstrap, offre un'alternativa robusta alle implementazioni esistenti di KernelSHAP.

• Performance: Il nuovo metodo performa "similmente" al metodo KernelSHAP migliorato nel pacchetto shapr per quanto riguarda le stime puntuali.
• Stima della Varianza: Il Symmetric bootstrap è evidenziato come un metodo "molto veloce dal punto di vista computazionale e facile da comprendere" che funziona bene, particolarmente negli studi di simulazione più grandi. Esso colma la lacuna nella letteratura per un metodo bootstrap "di riferimento" per il campionamento casuale senza reintegro in popolazioni finite.
• Limitazioni: L'autore nota con modestia che nello studio più piccolo, il Symmetric bootstrap ha occasionalmente prodotto deviazioni standard leggermente troppo piccole (liberali) per alcune variabili, pur catturando costantemente le deviazioni standard più elevate.
• Applicabilità: Il metodo è progettato per scenari in cui la funzione di contributo è stimata tramite modelli lineari o modelli lineari generalizzati (dove le predizioni sono lineari su una scala trasformata), sfruttando tecniche di calcolo rapido.

Il lavoro stabilisce che la teoria delle popolazioni finite può essere applicata con successo alla stima dei valori di Shapley per migliorare l'efficienza del campionamento e fornire stime della varianza valide, superando i limiti teorici delle tradizionali assunzioni di campionamento i.i.d. bootstrap in questo dominio.