Riepilogo Tecnico: PINE – Potatura di Ensemble di Alberi Potenziati con Equivalenza di Predizione Conformale In-Distribution

1. Enunciazione del Problema

I metodi di ensemble ad albero, come Random Forest, Gradient-Boosted Decision Trees (GBDT) e XGBoost, sono ampiamente utilizzati per dati tabellari grazie alle loro elevate prestazioni predittive e all'interpretabilità. Tuttavia, ensemble di grandi dimensioni comportano costi di inferenza elevati e ingombri di memoria, complicando attività a valle come la verifica della robustezza e i controlli di equità.

La potatura post-hoc degli ensemble è una soluzione standard, ma i metodi esistenti affrontano un compromesso tra compressione e fedeltà (equivalenza di predizione):

• Potatura orientata all'accuratezza: I metodi che ottimizzano i compromessi tra accuratezza e compressione alterano spesso un sottoinsieme di predizioni. Questa mancanza di fedeltà può interrompere la coerenza decisionale in domini ad alto rischio (es. medicina, finanza) dove i flussi di lavoro a valle dipendono da specifici output del modello.
• Potatura fedele: Metodi come FIPE (Emine et al., 2025) e Born-Again Tree Ensembles (Vidal & Schiffer, 2020) garantiscono un'equivalenza esatta di predizione per tutti gli input nell'intero spazio degli input. Sebbene ciò assicuri la coerenza decisionale, la necessità di preservare le predizioni anche per input rari o fuori distribuzione (OOD) limita severamente il rapporto di compressione raggiungibile.

Il problema centrale affrontato è come ottenere tassi di compressione più elevati mantenendo un'alta fedeltà, senza l'onere restrittivo di garantire l'equivalenza su input OOD che raramente si osservano nella pratica.

2. Metodologia: PINE

Gli autori propongono PINE (Pruning with In-distribution Equivalence), un framework di potatura che garantisce l'equivalenza di predizione solo all'interno di una regione in-distribution (ID) calibrata, $X_{ID}(\alpha)$.

Concetto Chiave

PINE rilassa il vincolo della potatura fedele limitando la garanzia di equivalenza agli input che sono "plausibili" secondo la distribuzione dei dati. Introduce un singolo iperparametro, $\alpha$ (livello di mancata copertura), che controlla la dimensione di questa regione. Il metodo garantisce che, per un futuro input campionato dalla stessa distribuzione, la probabilità che il modello potato corrisponda alla predizione del modello originale sia almeno $1-\alpha$.

Pipeline Algoritmica

PINE si basa sul framework iterativo Pruner-Oracle utilizzato da FIPE, ma modifica lo spazio di ricerca dell'Oracle:

1. Definizione del Punteggio di Plausibilità: Viene definita una funzione di punteggio $s(x)$ tale che punteggi più bassi indicano una plausibilità (probabilità) maggiore secondo la distribuzione dei dati. La regione in-distribution è definita come $X_{ID}(\alpha) = \{x \in \mathcal{X} \mid s(x) \leq \tau(\alpha)\}$.
2. Punteggio dell'Albero di Chow-Liu: Il documento adotta il log-verosimiglianza negativa di un albero di Chow-Liu come punteggio di plausibilità. Le caratteristiche continue vengono discretizzate in bin, e l'albero di Chow-Liu approssima la distribuzione congiunta come una struttura ad albero. Questa scelta è critica perché il log-verosimiglianza negativa si scompone in una forma additiva (marginalità della radice + termini condizionali degli archi), permettendo al vincolo $s(x) \leq \tau(\alpha)$ di essere codificato efficientemente come vincolo di Programmazione Lineare Intera Mista (MILP).
3. Calibrazione Conformale: Utilizzando un set di calibrazione $D_{cal}$, la soglia $\tau(\alpha)$ è determinata tramite predizione conformale split. Ciò garantisce che, sotto l'assunzione di scambiabilità, la regione $X_{ID}(\alpha)$ copra i futuri input con una probabilità di almeno $1-\alpha$.
4. Potatura Iterativa:
   • Pruner: Aggiorna i pesi dell'albero per soddisfare l'equivalenza di predizione su un insieme crescente di vincoli.
   • Oracle: Cerca controesempi (input in cui le predizioni differiscono) ma restringe la sua ricerca solo alla regione $X_{ID}(\alpha)$.
   • Il processo si ripete fino a quando non vengono trovati controesempi all'interno della regione ID.

Garanzie Teoriche

• Equivalenza Probabilistica: Sotto l'assunzione di scambiabilità, PINE fornisce un limite inferiore di $1-\alpha$ sulla probabilità che la predizione del modello potato corrisponda a quella del modello originale per un futuro input.
• Complessità: Il numero di stati discreti che l'Oracle deve esplorare è limitato superiormente da $e^{\tau(\alpha)}$. Poiché $\tau(\alpha)$ è monotono in $\alpha$, aumentare $\alpha$ (consentendo un tasso di mancata copertura maggiore) riduce esponenzialmente lo spazio di ricerca, facilitando una compressione più elevata.

3. Contributi Chiave

1. Framework PINE: Un metodo di potatura innovativo che scambia la fedeltà globale rigorosa per una fedeltà in-distribution ad alta probabilità, consentendo rapporti di compressione significativamente più elevati rispetto alle linee di base della potatura fedele.
2. Integrazione Conformale: La prima applicazione della predizione conformale split per definire una regione garantita in-distribution per la potatura degli ensemble, fornendo un limite probabilistico rigoroso sull'equivalenza di predizione.
3. Punteggio Incorporabile in MILP: La proposta di utilizzare il log-verosimiglianza negativa dell'albero di Chow-Liu come punteggio di plausibilità, che è sia espressivo per catturare le dipendenze tra le caratteristiche sia computazionalmente efficiente per la codifica MILP.
4. Controllo Sistematico del Compromesso: Un meccanismo per regolare sistematicamente il compromesso fedeltà-compressione tramite il singolo parametro $\alpha$.

4. Risultati Sperimentali

Gli autori hanno valutato PINE su 12 dataset tabellari pubblici (es. Adult, COMPAS, Pima-Diabetes) utilizzando ensemble XGBoost ($M=30$ alberi, profondità $D=2$).

• Compressione vs Fedeltà: PINE supera significativamente le linee di base della potatura fedele (FIPE). Mentre $\alpha$ aumenta da 0.05 a 0.8, il tasso medio di potatura aumenta da ~45% a ~68%, mantenendo un'alta fedeltà media (99.15%–99.96%). Al contrario, FIPE raggiunge un tasso medio di potatura di ~44% con il 100% di fedeltà.
• Confronto con Metodi Orientati all'Accuratezza: Sebbene i metodi orientati all'accuratezza (IC, DREP, MDEP) possano mantenere l'accuratezza di test, mostrano cali sostanziali di fedeltà (spesso <90%) anche all'interno della regione in-distribution. PINE mantiene una fedeltà quasi perfetta all'interno della regione calibrata.
• Validazione della Copertura: La copertura empirica di test $\hat{\pi}_{ID}$ segue da vicino l'obiettivo $1-\alpha$, validando l'efficacia della calibrazione conformale split.
• Scalabilità: Il metodo è più sensibile alla profondità dell'albero ($D$) che al numero di alberi ($M$). Alberi più profondi riducono la compressione ottenibile a causa di regioni decisionali più localizzate, mentre ensemble più grandi aumentano principalmente il tempo di esecuzione dell'ottimizzazione.

5. Significato e Affermazioni

Il documento afferma che PINE colma una lacuna critica nella compressione dei modelli: l'incapacità dei metodi fedeli esistenti di comprimere efficacemente i modelli senza sacrificare la coerenza decisionale e l'incapacità dei metodi di potatura standard di garantire tale coerenza.

• Impatto Pratico: PINE consente ai praticanti di comprimere i modelli fino al 30% in più rispetto alle linee di base fedeli, preservando la coerenza decisionale su futuri input probabili. Questo è particolarmente prezioso in domini ad alto rischio dove gli output del modello attivano flussi di lavoro a valle o richiedono auditabilità.
• Limitazioni: Gli autori riconoscono modestamente che la garanzia si basa sull'assunzione di scambiabilità (nessun cambiamento di distribuzione). Se la distribuzione dei dati cambia, la garanzia potrebbe indebolirsi. Inoltre, il costo computazionale è legato alla risoluzione di problemi MILP, che può essere elevato per impostazioni multi-classe o alberi molto profondi.
• Conclusione: PINE offre un approccio verificabile e probabilistico alla potatura che bilancia gli obiettivi concorrenti di efficienza e affidabilità, superando la scelta binaria tra "accurato ma incoerente" e "coerente ma non compresso".