Provably Explaining Neural Additive Models

1. Il Problema

Le tecniche di spiegazione post-hoc per le reti neurali (come LIME, SHAP o Anchors) sono spesso euristico e mancano di garanzie formali. Un approccio promettente per ottenere spiegazioni con garanzie provabili è identificare un sottoinsieme cardinalmente minimale di caratteristiche di input che, da sole, sono sufficienti a determinare la previsione del modello indipendentemente dai valori delle altre caratteristiche (entro una certa regione di perturbazione).

Tuttavia, per le reti neurali standard, calcolare tali spiegazioni è computazionalmente intrattabile. Nel caso peggiore, richiede un numero esponenziale di query di verifica della rete neurale, ciascuna delle quali è un problema NP-hard. Di conseguenza, gli algoritmi esistenti si limitano spesso a trovare spiegazioni "subset-minimali" (che non sono necessariamente le più piccole in termini di numero di feature) o si affidano a metodi di campionamento probabilistico che non offrono garanzie di sufficienza.

2. Metodologia

Gli autori propongono un algoritmo specifico per i Neural Additive Models (NAM), una famiglia di modelli che combinano l'interpretabilità dei modelli additivi generalizzati (GAM) con la potenza espressiva delle reti neurali. Un NAM è definito come una somma di funzioni univariate:
$$f(x) = \beta_0 + \sum_{i=1}^k f_i(x_i)$$
dove ogni $f_i$ è una piccola rete neurale univariata.

Sfruttando questa struttura additiva, gli autori sviluppano un algoritmo in due fasi che riduce la complessità da esponenziale a logaritmica rispetto al numero di feature di input:

Fase 1: Ordinamento Parallelizzato per Importanza (Alg. 2)

Prima di selezionare le feature, l'algoritmo determina un ordinamento totale delle feature in base alla loro "importanza".

• Concetto: Una feature $i$ è più importante di $j$ se una perturbazione su $i$ causa un cambiamento maggiore nella previsione finale rispetto a una perturbazione su $j$.
• Implementazione: Grazie alla struttura additiva, questo calcolo può essere eseguito in parallelo su ogni componente univariato $f_i$.
• Tecnica: Per ogni componente, viene eseguita una ricerca binaria (usando un verificatore di reti neurali) per trovare i limiti inferiori e superiori del valore minimo della funzione $f_i$ all'interno di una sfera di perturbazione $\epsilon$.
• Risultato: Si ottengono intervalli di importanza non sovrapposti che permettono di ordinare le feature. La complessità di questa fase è $O(\frac{n}{p} \log(\dots))$ con $p$ processori, ovvero logaritmica nella precisione richiesta.

Fase 2: Selezione delle Feature tramite Ricerca Binaria (Alg. 4)

Una volta ottenuta l'ordinazione delle feature, l'algoritmo non procede con una ricerca lineare (che richiederebbe $O(n)$ query), ma utilizza una ricerca binaria sul sottoinsieme ordinato.

• Logica: Poiché le feature sono ordinate per importanza decrescente, se un sottoinsieme delle prime $k$ feature è sufficiente, allora qualsiasi sottoinsieme più grande lo sarà anch'esso (grazie alla proprietà di monotonia garantita dall'ordinamento).
• Efficienza: Questo permette di trovare il punto di transizione esatto (il minimo $k$ tale che le prime $k$ feature siano sufficienti) con solo $O(\log n)$ query di verifica sul modello completo.

3. Contributi Chiave

1. Algoritmo Provabilmente Minimale: È il primo metodo che genera spiegazioni cardinalmente-minimali (le più piccole possibili in termini di numero di feature) per le reti neurali, garantendo che nessun sottoinsieme più piccolo sia sufficiente.
2. Riduzione della Complessità: Dimostrano che per i NAM, il problema intrattabile per le reti generiche diventa risolvibile in tempo logaritmico (in termini di query di verifica), sfruttando la decomposizione in componenti univariate.
3. Superiorità rispetto agli approcci esistenti:
   • Rispetto agli algoritmi subset-minimali (che usano ricerche lineari), il loro metodo produce spiegazioni più piccole e più informative.
   • Rispetto ai metodi basati sul campionamento (tipici per i NAM), le loro spiegazioni sono provabilmente corrette e non soggette a errori dovuti alla mancata cattura di estremi locali o picchi nelle funzioni univariate.
4. Analisi di Complessità Teorica: Forniscono prove formali che il problema di trovare spiegazioni minimali per i NAM rientra nella classe di complessità $FP_{NP}$ e richiede al massimo un numero lineare di query rispetto alla dimensione del modello, ma solo un numero logaritmico in pratica grazie all'ordinamento.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su dataset tabellari critici per la sicurezza (Breast Cancer, CREDIT, FICO HELOC) utilizzando il verificatore di stato dell'arte $\alpha$-$\beta$-CROWN.

• Dimensione della Spiegazione: Il metodo proposto produce spiegazioni significativamente più piccole. Ad esempio, su FICO HELOC, la dimensione media è di 5.59 feature contro 15.60 per l'approccio Lexicographic e 9.45 per l'approccio Sensitivity.
• Tempo di Calcolo: Nonostante il compito sia più difficile (trovare la minimialità cardinale invece che quella di sottoinsieme), il metodo è molto più veloce. Su FICO HELOC, il tempo è di 317s contro 146s (Lexicographic) e 250s (Sensitivity), ma con una qualità della spiegazione nettamente superiore. In altri dataset (es. Breast Cancer), il guadagno di velocità è ancora più marcato (35s contro 634s).
• Affidabilità: Il 100% delle spiegazioni generate dal metodo proposto è stato verificato come sufficiente. Al contrario, le spiegazioni generate da metodi basati sul campionamento hanno mostrato un tasso di sufficienza verificata inferiore al 32% (CREDIT) e al 25% (FICO), evidenziando il rischio di interpretazioni errate con metodi euristici.

5. Significato e Impatto

Questo lavoro rappresenta un passo fondamentale verso l'XAI (Explainable AI) formale e scalabile.

• Fiducia nei Sistemi Critici: Dimostra che è possibile ottenere garanzie matematiche di correttezza e minimalità su modelli complessi (NAM) in tempi pratici, rendendoli adatti per domini sensibili come la sanità e la finanza.
• Nuova Direzione di Ricerca: Apre la strada all'idea che architetture neurali con strutture interpretabili intrinseche (come l'additività) possano essere progettate specificamente per bilanciare espressività e verificabilità formale.
• Superamento dei Limiti Attuali: Supera il collo di bottiglia computazionale che ha finora impedito l'uso di spiegazioni provabili su reti neurali, dimostrando che con la giusta architettura, la complessità può essere ridotta drasticamente.

In sintesi, il paper dimostra che i Neural Additive Models non sono solo interpretabili per visualizzazione, ma possono essere spiegati formalmente in modo efficiente, offrendo spiegazioni più concise e garantite rispetto a qualsiasi metodo esistente per reti neurali generiche o approcci euristici.