Riepilogo Tecnico: WOODELF++

Enunciato del Problema

Gli ensemble di alberi decisionali sono onnipresenti nelle applicazioni del mondo reale, ma l'interpretazione delle loro previsioni rimane una sfida critica per la fiducia e il processo decisionale. Tre strumenti principali per interpretare questi modelli sono i Grafici di Dipendenza Parziale (PDP), i Grafici di Dipendenza Parziale Congiunta (Joint-PDP) e i Valori di Interazione di Dipendenza Parziale (PDIV).

• I PDP visualizzano come una singola caratteristica influisce sulla previsione media del modello.
• I Joint-PDP estendono questo concetto a coppie di caratteristiche per rivelare gli effetti combinati.
• I PDIV (in particolare il compito "Any-Order") quantificano gli effetti di interazione su tutti i possibili sottoinsiemi di caratteristiche per ogni riga in un dataset.

I metodi attuali all'avanguardia, come quelli presenti in scikit-learn e l'algoritmo FastPD (implementato nel pacchetto GLEX), soffrono di una complessità computazionale proibitiva. Gli approcci ingenui scalano linearmente con il numero di campioni e caratteristiche, ma esponenzialmente con la profondità dell'albero e il numero di caratteristiche coinvolte nelle interazioni. Per dataset di grandi dimensioni (ad esempio, 400.000 righe) e compiti di interazione complessi (Any-Order-PDIV), i metodi esistenti sono o impraticabilmente lenti (richiedendo giorni o anni) o si basano su approssimazioni che potrebbero non cogliere comportamenti critici del modello, come le discontinuità nette.

Metodologia

Gli autori introducono WOODELF++, un framework unificato ed efficiente per il calcolo di PDP, Joint-PDP e Any-Order-PDIV su ensemble di alberi decisionali. L'approccio si basa sul lavoro precedente degli autori, WOODELF, che calcola efficientemente i valori SHAP modellando gli ensemble di alberi decisionali come funzioni Pseudo-Booleane (PB) rappresentate in Forma Normale Disgiuntiva Pesata (WDNF).

Le innovazioni tecniche fondamentali includono:

1. Unificazione tramite WDNF e Linearità:
   Gli autori formulano i compiti PDP, Joint-PDP e PDIV come metriche di gioco cooperativo su formule WDNF. Sfruttando la proprietà di linearità di queste metriche, è possibile calcolare spiegazioni globali complesse aggregando i risultati dai singoli "cubi" (congiunzioni di letterali) all'interno della rappresentazione WDNF. Questo evita la necessità di rivalutare il modello per ogni combinazione campione-caratteristica individualmente.

2. Costruzione Efficiente del Dataset di Consumo:
   Per calcolare efficientemente PDP e Joint-PDP, gli autori costruiscono dataset "di consumo" ($C$) compatti che permettono agli algoritmi di attribuzione locale di calcolare grafici di dipendenza globali.

   • Per i PDP, costruiscono un dataset con $k$ righe che rappresentano i valori campionati delle caratteristiche.
   • Per i Joint-PDP, introducono una costruzione innovativa che riduce la dimensione del dataset da $O(k^2 f)$ a $O(k^2 \log f)$ codificando gli indici delle caratteristiche in binario e utilizzando le operazioni np.tile e np.repeat per garantire che tutte le combinazioni di valori a coppie siano rappresentate senza righe ridondanti.

3. PDP Completi:
   Riconoscendo che i PDP standard con valori campionati ($k$) possono perdere picchi stretti o effetti di singoli valori (ad esempio, un modello di frode che segnala uno stipendio specifico per default), gli autori propongono i Full PDP. Invece di un campionamento arbitrario, i Full PDP utilizzano tutte le soglie di divisione dai nodi dell'albero come valori sull'asse x. Poiché le previsioni degli alberi decisionali sono costanti a tratti tra le soglie, questo metodo cattura il comportamento esatto dell'ensemble con punti di valutazione minimi.

4. Riduzione della Complessità per Any-Order-PDIV:
   Il contributo teorico più significativo è la riduzione della complessità per Any-Order-PDIV.

   • Naive/FastPD: FastPD elabora gli alberi indipendentemente, risultando in una dipendenza di complessità di $2^{2D}$ (dove $D$ è la profondità dell'albero) nel caso peggiore.
   • WOODELF++: Elaborando separatamente ogni percorso dalla radice alla foglia e sfruttando la struttura specifica della metrica PDIV su WDNF, la dipendenza di complessità viene ridotta a $4^D$. Questo rappresenta un miglioramento esponenziale rispetto allo stato dell'arte.

5. Approssimazione e Supporto GPU:
   Il framework supporta naturalmente le approssimazioni Path-Dependent (equivalenti all'impostazione del dataset di sfondo su vuoto) ed è implementato in Python puro con supporto per l'accelerazione GPU.

Contributi Chiave

1. Accelerazione in PDP e Joint-PDP: WOODELF++ ottiene un'accelerazione di circa 6 volte rispetto a FastPD e fino a cinque ordini di grandezza rispetto a scikit-learn per i compiti PDP e Joint-PDP su dataset di grandi dimensioni.
2. Miglioramento Esponenziale della Complessità per Any-Order-PDIV: Gli autori dimostrano che per alberi bilanciati, la complessità passa da esponenziale nella dimensione dell'input ($2^{2D}$ di FastPD) a polinomiale nella dimensione dell'input ($4^D$ di WOODELF++). Sperimentalmente, questo riduce il tempo di esecuzione per Any-Order-PDIV su 400.000 campioni da un stimato 1.000.000 di anni (FastPD) a 5 minuti (WOODELF++).
3. Introduzione dei Full PDP: Un metodo innovativo per catturare la struttura completa a tratti costante degli ensemble di alberi, consentendo il rilevamento di overfitting e violazioni di monotonia che i PDP campionati non colgono.
4. Framework Unificato: Il documento stabilisce una semplice connessione tra PDP approssimati, PDP esatti e SHAP Path-Dependent, unificandoli sotto un singolo framework algoritmico.

Risultati Sperimentali

Gli autori hanno valutato WOODELF++ su due grandi dataset ampiamente utilizzati: IEEE-CIS (472k righe, 397 caratteristiche) e KDD Cup 1999 (4,9M righe, 127 caratteristiche). I modelli sono stati addestrati utilizzando HistGradientBoostingRegressor con 100 alberi e una profondità massima di 6.

• Prestazioni PDP: Su IEEE-CIS, WOODELF++ ha calcolato PDP Esatti (k=5) in 13,1 secondi (GPU) rispetto a 99 secondi per FastPD e 58,5 minuti per scikit-learn.
• Prestazioni Joint-PDP: Per Joint-PDP (k=5), WOODELF++ ha impiegato 25 secondi (GPU) contro 130 secondi per FastPD e una stima di 35 giorni per scikit-learn.
• Any-Order-PDIV: Su IEEE-CIS con 10.000 campioni, WOODELF++ ha completato il compito in 22,6 secondi (GPU). FastPD avrebbe richiesto una stima di 60.000 anni.
• Correttezza: Gli autori hanno verificato che gli output di WOODELF++ corrispondono a scikit-learn e ai calcoli PDIV diretti con una differenza massima di 0,00001.

Significato

Il documento afferma che WOODELF++ cambia fondamentalmente la fattibilità dell'interpretazione degli ensemble di alberi decisionali. Riducendo la complessità di Any-Order-PDIV da intrattabile a pratica, permette l'analisi di interazioni di caratteristiche di ordine superiore che erano precedentemente computazionalmente impossibili. Inoltre, l'introduzione dei Full PDP consente ai professionisti di visualizzare i confini decisionali esatti dei modelli ad albero, superando i limiti delle approssimazioni campionate. Gli autori posizionano WOODELF++ come uno strumento necessario per un'IA scalabile e affidabile in domini che richiedono una profonda comprensione del modello, come sanità, finanza ed ecologia.