A Polynomial-Time Axiomatic Alternative to SHAP for Feature Attribution

Questo articolo propone ESENSC_rev2, un metodo di attribuzione delle caratteristiche alternativo a SHAP che, fondato sulla teoria dei giochi cooperativi e caratterizzato da un insieme di assiomi, offre un'approssimazione accurata con complessità computazionale polinomiale, rendendolo ideale per scenari di alta dimensionalità.

L'essenziale

Immagina di avere un'auto che guida da sola e prende decisioni: "Devo frenare perché c'è un pedone" oppure "Posso accelerare perché la strada è libera". L'Intelligenza Artificiale (AI) è molto brava a guidare, ma spesso è una "scatola nera": sappiamo che prende la decisione giusta, ma non sappiamo perché o quali fattori hanno pesato di più.

Per capire come pensa l'AI, gli scienziati usano degli strumenti chiamati "metodi di attribuzione delle caratteristiche". È come se chiedessimo all'AI: "Ehi, tra la pioggia, la velocità e il colore dell'auto, quale di questi ha fatto sì che tu frenassi?".

Il metodo più famoso oggi si chiama SHAP. È come un giudice molto preciso che ascolta tutte le possibili combinazioni di fattori (es. "pioggia e velocità", "solo pioggia", "nessun fattore") per decidere quanto ognuno ha contribuito. Il problema? Questo giudice è lento. Se hai pochi fattori, è veloce. Ma se hai centinaia di fattori (come in un'analisi medica complessa o finanziaria), il giudice impiega un tempo infinito per fare i calcoli, diventando inutile per le applicazioni reali.

La soluzione proposta: Un nuovo metodo veloce e intelligente

Gli autori di questo articolo (Hiraki, Ishihara, Kongo e Shino) hanno detto: "C'è un modo per avere un giudice quasi altrettanto preciso, ma che lavora in tempo reale".

Hanno creato un nuovo metodo chiamato ESENSC_rev2. Ecco come funziona, usando un'analogia semplice:

1. Il Problema della "Festa di Compleanno" (Il gioco cooperativo)

Immagina che l'AI sia una festa di compleanno dove gli ospiti sono i "fattori" (pioggia, velocità, ecc.). L'obiettivo è dividere la torta (la decisione finale dell'AI) equamente tra gli ospiti in base a quanto hanno contribuito a renderla divertente.

• SHAP (Il metodo vecchio): Per dividere la torta equamente, calcola quanto ogni singolo ospite ha contribuito in ogni possibile combinazione di gruppi. Se ci sono 100 ospiti, il numero di combinazioni è astronomico. È come se dovessi invitare ogni possibile gruppo di amici a cena per vedere chi porta il vino migliore. Impossibile da fare in tempo utile.
• ESENSC_rev2 (Il nuovo metodo): Invece di invitare tutti i gruppi possibili, guarda solo due cose fondamentali:
  1. Quanto è divertente la festa se arriva solo quell'ospite?
  2. Quanto la festa diventa meno divertente se quell'ospite se ne va?
     Poi, fa una media intelligente di questi due valori e distribuisce il resto della torta in modo equo. È molto più veloce perché non deve calcolare miliardi di combinazioni.

2. Il problema dei "Fattori Nulli" (La regola d'oro)

Un problema dei metodi veloci precedenti era che a volte davano un pezzo di torta anche a chi non aveva fatto nulla (ad esempio, un ospite che era lì ma non ha parlato con nessuno).
Il nuovo metodo ESENSC_rev2 ha una regola ferrea: Se un ospite non ha contribuito a nulla, non riceve nulla. Questo è fondamentale per l'AI: non vogliamo che l'AI ci dica che "il colore del cielo" ha influenzato la decisione di frenare, se in realtà non c'entra nulla.

3. Il problema dei "Segni Contrari" (L'ordine corretto)

In alcuni casi, un fattore può avere un effetto positivo (accelera) e uno negativo (frena) contemporaneamente, creando confusione. I vecchi metodi veloci a volte invertivano l'ordine: dicevano che il fattore "meno importante" era quello "più importante".
Il nuovo metodo è stato progettato per evitare questo errore, mantenendo sempre l'ordine corretto delle priorità, anche quando i numeri sono positivi o negativi.

Cosa dicono i risultati?

Gli autori hanno fatto dei test su dati reali (come il prezzo delle case in California o modelli finanziari):

• Velocità: Il nuovo metodo è esponenzialmente più veloce di SHAP. Mentre SHAP impiega ore o giorni per analizzare molti fattori, il nuovo metodo lo fa in secondi.
• Precisione: Nonostante sia velocissimo, il nuovo metodo è quasi identico a SHAP. La differenza nei risultati è così piccola che per l'utente medio è indistinguibile.
• Affidabilità: Non ha bisogno di "impostazioni magiche" o di essere aggiustato a mano. Funziona così com'è.

In sintesi

Immagina di dover dividere un conto al ristorante tra 100 amici.

• SHAP è come un contabile che chiama ogni singolo amico per chiedere quanto ha ordinato, quanto ha bevuto, chi ha pagato per chi, e fa i calcoli per ogni possibile gruppo di amici. È perfetto, ma ci mette una settimana.
• ESENSC_rev2 è come un amico intelligente che guarda velocemente cosa ha ordinato ognuno, vede chi non ha mangiato nulla (e non gli dà da pagare), e divide il resto in modo equo basandosi su una formula semplice. È quasi perfetto quanto il contabile, ma lo fa in 5 minuti.

Conclusione:
Questo articolo ci dice che non dobbiamo più scegliere tra "essere precisi ma lenti" o "essere veloci ma imprecisi". Con il nuovo metodo ESENSC_rev2, possiamo avere spiegazioni chiare, giuste e veloci per le decisioni delle Intelligenze Artificiali, rendendo l'AI più trasparente e utilizzabile anche nei casi più complessi.

Sommario tecnico

1. Il Problema

L'articolo affronta la sfida computazionale e teorica legata alla spiegabilità dei modelli di Intelligenza Artificiale (XAI), in particolare nel contesto dell'attribuzione delle caratteristiche (Feature Attribution).

• Limiti di SHAP: SHAP (SHapley Additive exPlanations), basato sul valore di Shapley della teoria dei giochi cooperativi, è lo standard de facto per l'attribuzione delle caratteristiche. Tuttavia, il calcolo esatto del valore di Shapley ha una complessità esponenziale rispetto al numero di caratteristiche ($2^n$), rendendolo intrattabile per dataset con molte feature.
• Limiti degli approcci approssimati: Gli algoritmi di approssimazione esistenti (come Permutation SHAP o Kernel SHAP) riducono il costo computazionale ma introducono instabilità, richiedono la regolazione di iperparametri e non garantiscono sempre il soddisfacimento delle proprietà teoriche desiderate.
• Specificità dei giochi XAI: A differenza dei giochi cooperativi classici, i "giochi XAI-TU" (Transferable Utility) presentano caratteristiche uniche: i valori delle coalizioni possono essere sia positivi che negativi all'interno dello stesso gioco, e il valore della coalizione vuota ($v(\emptyset)$) non è necessariamente zero. Le soluzioni tradizionali spesso falliscono in questi contesti, portando a paradossi (es. inversione dell'ordine di attribuzione).

2. Metodologia

Gli autori formulano il problema dell'attribuzione delle caratteristiche come un gioco cooperativo a utilità trasferibile (XAI-TU game) e propongono nuove regole di allocazione basate su concetti della teoria dei giochi che hanno complessità polinomiale.

A. Formulazione del Gioco XAI-TU

Per ogni osservazione $\tau$, definiscono una funzione caratteristica $v_\tau(S)$ come il valore atteso della previsione del modello quando le caratteristiche in $S$ sono note e le altre sono tratte dalla distribuzione empirica. L'obiettivo è allocare il surplus totale $v(N) - v(\emptyset)$ tra le caratteristiche.

B. Sviluppo di Regole di Attribuzione (AFA)

Gli autori esplorano due famiglie di soluzioni:

1. Soluzioni di Tipo "Equal Surplus" (ES):
   • Analizzano la soluzione ES (surplus equo) e ENSC (contributo non separabile egalitario).
   • La semplice media 50-50 di ES e ENSC viola la proprietà del "giocatore nullo" (assegnare attribuzione non nulla a feature che non influenzano la previsione).
   • Proposta: Introducono ESENSC_rev2, una versione modificata che assegna zero alle feature nulle (o che si comportano come tali) ridistribuendo il surplus residuo solo tra le feature con contributi marginali non nulli. Questa regola è calcolabile in tempo polinomiale ($O(n)$ valutazioni della funzione caratteristica).
2. Soluzioni di Tipo "Proportional Allocation" (PA):
   • Analizzano le regole di allocazione proporzionale.
   • Identificano il problema della "inversione dell'ordine" (order-reversal): in presenza di valori di coalizione misti (positivi e negativi), una feature con contributo marginale inferiore potrebbe ricevere un'attribuzione maggiore.
   • Propongono regole ibride (come PARPA e Gately_adj) per mitigare questo problema, ma i risultati empirici mostrano che queste soluzioni soffrono di instabilità intrinseca.

C. Caratterizzazione Assiomatica

Gli autori forniscono una caratterizzazione assiomatica unica per ESENSC_rev2, dimostrando che è l'unica soluzione che soddisfa un insieme specifico di assiomi:

• Efficienza: La somma delle attribuzioni è uguale al surplus totale.
• Proprietà del Giocatore Nullo: Le feature senza impatto ricevono attribuzione zero.
• Marginalità Differenziale Restretta: Una versione indebolita del principio di marginalità differenziale, adattata per ridurre il numero di coalizioni necessarie per il calcolo.
• Gioco Inessenziale Intermedio: Assegna ai giocatori un valore che è la media tra il contributo marginale dalla base e il contributo marginale dal gioco completo.
• Riduzione della Complessità Computazionale: La soluzione dipende solo dai valori delle coalizioni di dimensione 0, 1, $n-1$ e $n$, ignorando le coalizioni intermedie.

3. Risultati Sperimentali

Gli autori hanno condotto estesi esperimenti su dataset tabulari (California Housing) con modelli XGBoost e Reti Neurali, variando il numero di feature fino a 512.

• Accuratezza di Approssimazione:
  • ESENSC_rev2 mostra deviazioni molto piccole rispetto allo SHAP esatto, paragonabili o migliori rispetto a Permutation SHAP e nettamente superiori a Kernel SHAP.
  • Le soluzioni di tipo proporzionale (PA-type) mostrano deviazioni elevate e instabili, confermando la loro inadeguatezza in contesti con valori misti.
• Efficienza Computazionale:
  • Il tempo di calcolo di SHAP esatto cresce esponenzialmente, diventando impraticabile oltre 16-20 feature.
  • ESENSC_rev2 scala linearmente con il numero di feature, rimanendo estremamente veloce anche a 512 dimensioni.
  • È significativamente più veloce delle approssimazioni basate su campionamento (Permutation/Kernel SHAP) e non richiede la regolazione di iperparametri (es. numero di iterazioni).

4. Contributi Chiave

1. Formalizzazione Teorica: Definizione rigorosa dei giochi XAI-TU, evidenziando le differenze strutturali rispetto ai giochi cooperativi classici (es. coesistenza di valori positivi e negativi).
2. Nuovo Algoritmo (ESENSC_rev2): Proposta di una regola di attribuzione a costo polinomiale che combina efficienza, proprietà del giocatore nullo e alta accuratezza nell'approssimare SHAP.
3. Fondamento Assiomatico: Prima caratterizzazione assiomatica di una regola di attribuzione delle feature in tempo polinomiale che approssima SHAP, fornendo una base teorica solida per il suo utilizzo.
4. Analisi Comparativa: Dimostrazione empirica che le soluzioni di tipo proporzionale sono intrinsecamente problematiche in XAI, mentre le soluzioni di tipo Equal Surplus modificate offrono il miglior compromesso tra costo e accuratezza.

5. Significato e Implicazioni

Il lavoro suggerisce che ESENSC_rev2 rappresenta un'alternativa praticabile e teoricamente fondata a SHAP per pipeline di spiegabilità moderne, specialmente in scenari ad alta dimensionalità.

• Praticità: Elimina la necessità di approssimazioni stocastiche con iperparametri da tarare, offrendo un calcolo deterministico e veloce.
• Teoria: Dimostra che è possibile rilassare alcuni assiomi forti del valore di Shapley (come la marginalità differenziale completa) a favore di assiomi legati alla complessità computazionale, ottenendo comunque una soluzione robusta e giustificata teoricamente.
• Futuro: Apre la strada allo sviluppo di ulteriori regole di attribuzione basate sulla teoria dei giochi adattate specificamente alle peculiarità strutturali dei giochi XAI, piuttosto che semplici adattamenti di soluzioni classiche.

In sintesi, il paper propone una soluzione che risolve il collo di bottiglia computazionale di SHAP senza sacrificare l'accuratezza o la coerenza teorica, rendendo l'XAI scalabile per modelli complessi e dataset ad alta dimensionalità.