Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach

Riepilogo Tecnico: Quantificazione della Sensibilità per Ensemble di Alberi

Enunciato del Problema
Gli Ensemble di Alberi Decisionali (DTE), come XGBoost e Random Forest, sono ampiamente utilizzati in domini critici per la sicurezza ma pongono sfide per la verifica formale. Sebbene il lavoro esistente abbia affrontato l'esistenza di sensibilità (trovare una singola "coppia sensibile" di input che differisce solo per le caratteristiche protette ma produce output diversi), questo articolo sostiene che i controlli binari di esistenza siano insufficienti per una comprensione quantitativa dell'equità del modello. Il problema centrale affrontato è la quantificazione della sensibilità: determinare il volume o il conteggio delle regioni di input in un DTE dove piccole perturbazioni nelle caratteristiche sensibili portano a una classificazione errata o a cambiamenti significativi dell'output. Questo problema è distinto dalla robustezza locale (che verifica un intorno di un input specifico) ed è computazionalmente più difficile, rientrando nella classe di complessità #P-hard, poiché richiede la ricerca dell'intero spazio di input per contare le assegnazioni soddisfacenti anziché trovarne semplicemente una.

Metodologia
Gli autori propongono XCount, un nuovo framework algoritmico che combina compilazione della conoscenza, decomposizione composizionale e conteggio approssimato di modelli per stimare il numero di regioni sensibili con garanzie formali.

1. Discretizzazione e Codifica Simbolica:
   Lo spazio di input continuo viene discretizzato in base ai predicati di guardia (coppie caratteristica-soglia) del DTE. Questo mappa lo spazio di input su un insieme finito di vettori booleani. Il comportamento del modello viene codificato utilizzando i Diagrammi di Decisione Algebrica (ADD), un'estensione quantitativa dei Diagrammi di Decisione Binaria (BDD). Gli ADD consentono la rappresentazione efficiente della struttura additiva dell'ensemble ($T(x) = \sum T_i(x)$).

2. Decomposizione Composizionale:
   Compilare direttamente un grande DTE in un ADD monolitico è intensivo in termini di memoria e spesso intrattabile. Per superare questo ostacolo, l'algoritmo impiega una strategia divide et impera:

   • Il problema viene suddiviso in sottoproblemi basati su coppie di maschere di bit (assegnazioni alle caratteristiche sensibili) che differiscono per al più $d$ bit (distanza di Hamming).
   • Per ogni coppia, le caratteristiche sensibili vengono fissate e gli alberi decisionali vengono "potati" per rimuovere i rami irraggiungibili, risultando in sottoproblemi più piccoli e trattabili.
   • Ogni sottoproblema calcola la differenza negli output tra le due assegnazioni fisse.

3. Conteggio Approssimato con Garanzie PAC:
   Invece di eseguire un conteggio esatto sull'unione di tutte le soluzioni dei sottoproblemi (il che reintrodurrebbe la complessità degli insiemi sovrapposti), gli autori adattano una tecnica dalla teoria dei database per approssimare il volume di un'unione di insiemi in un modello di streaming.

   • L'algoritmo campiona assegnazioni soddisfacenti dai sottoproblemi (rappresentati come BDD) utilizzando un approccio probabilistico.
   • Mantiene un insieme di campioni e aggiorna dinamicamente la probabilità di campionamento per garantire che la stima finale $\hat{C}$ soddisfi le garanzie Probabilmente Correttamente Approssimate (PAC): $Pr[(1-\epsilon)C \leq \hat{C} \leq (1+\epsilon)C] \geq 1-\delta$.

Contributi Chiave

1. Formulazione Quantitativa: L'articolo definisce una nozione discretizzata e quantitativa di sensibilità che conta il numero di regioni di input che ammettono una coppia sensibile, andando oltre i semplici controlli di esistenza.
2. Algoritmo Composizionale: Introduce una strategia di suddivisione e fusione che scompone il problema globale di conteggio in sottoproblemi parallelizzabili, affrontando i problemi di scalabilità della compilazione ADD monolitica.
3. Solidità Teorica: Il metodo fornisce forti garanzie teoriche, assicurando che il conteggio approssimato rientri in un margine di errore definito dall'utente ($\epsilon$) con un livello di confidenza specificato ($1-\delta$).
4. Implementazione e Validazione: Gli autori hanno implementato lo strumento XCount e lo hanno validato contro i contatori di modelli esatti all'avanguardia (Ganak) e i contatori approssimati (ApproxMC), nonché contro una baseline ADD monolitica.

Risultati Sperimentali
Gli autori hanno valutato XCount su 3.194 istanze di benchmark derivate da 10 dataset reali (ad esempio, Adult, Diabetes, Higgs) con dimensioni dell'ensemble variabili (10–100 alberi) e profondità (3–6).

• Prestazioni: XCount ha superato significativamente tutte le baseline. Ha risolto 1.552 istanze, rispetto a 721 per Ganak e 579 per ApproxMC. Ha raggiunto un Tempo di Esecuzione Medio Penalizzato (PAR2) di 1.937 secondi, rappresentando un miglioramento del 33% rispetto all'approccio successivo migliore e un miglioramento del 43% rispetto alla baseline ADD.
• Accuratezza: Per le istanze in cui erano disponibili conteggi esatti, XCount ha mantenuto un'alta fedeltà, con il 99% delle stime rientranti nel margine di errore prescritto del 10% ($\epsilon=0.1$).
• Scalabilità: Lo strumento ha dimostrato una scalabilità superiore all'aumentare della dimensione e della profondità dell'ensemble, mentre l'approccio ADD monolitico non è riuscito a scalare oltre le istanze piccole.

Significato e Applicazioni
L'articolo afferma che XCount fornisce un metodo scalabile, solido e completo per quantificare la sensibilità nei DTE, un compito precedentemente considerato intrattabile per modelli di grandi dimensioni.

• Validazione della Regularizzazione: Come applicazione specifica, gli autori hanno utilizzato XCount per validare l'efficacia della regolarizzazione L1. Hanno dimostrato che l'aumento del parametro di regolarizzazione $\alpha$ è correlato a una diminuzione del numero di regioni sensibili, suggerendo che il conteggio della sensibilità possa servire come metrica per valutare l'overfitting del modello e la generalizzazione senza accesso ai parametri interni di addestramento.
• Equità e Sicurezza: Quantificando il "volume" dell'ingiustizia, l'approccio offre una metrica più sfumata per l'equità individuale e la discriminazione causale rispetto alla verifica binaria, consentendo ai praticanti di sintonizzare i modelli per soddisfare soglie regolamentari specifiche (ad esempio, assicurando che la sensibilità sia inferiore all'1% dello spazio di input).

Gli autori concludono che, sebbene il loro lavoro si concentri sui DTE, le tecniche composizionali e probabilistiche sono generalizzabili, e il lavoro futuro esplorerà l'applicazione di questi conteggi di sensibilità per classificare i modelli e estendere l'approccio ad altre classi di modelli di apprendimento automatico.