Optimized Sequential Testing for Binary Ensemble Classifiers

Problematica
I classificatori ensemble, come le random forest, combinano le previsioni di più modelli base (ad esempio, alberi decisionali) tramite il voto di maggioranza per ottenere un'elevata accuratezza. Tuttavia, gli ensemble più grandi comportano costi computazionali significativi durante l'inferenza, il che è problematico per i dispositivi a bassa potenza o per le applicazioni ad alta frequenza. Il problema centrale affrontato è come ridurre il costo computazionale del tempo di test dei classificatori ensemble binari senza degradare significativamente la loro accuratezza. Nello specifico, gli autori investigano strategie per interrompere l'esecuzione dei modelli base in modo sequenziale una volta che emerge una "maggioranza netta", piuttosto che eseguire tutti i $N$ modelli. L'obiettivo è minimizzare il numero atteso di modelli base eseguiti (tempo di esecuzione) controllando rigorosamente il "tasso di disaccordo" — ovvero la probabilità che l'ensemble con interruzione anticipata fornisca un risultato diverso rispetto all'ensemble completo.

Metodologia
Il documento formalizza il problema dell'interruzione anticipata (early stopping) come un compito di test sequenziale in cui lo stato è definito da $(i, j)$, che rappresenta $i$ modelli base eseguiti e $j$ voti positivi. Gli autori assumono che i modelli base siano eseguiti in un ordine casuale, consentendo l'uso di una distribuzione ipergeometrica per modellare la probabilità di raggiungere qualsiasi stato, senza assumere l'indipendenza tra i modelli base.

Per trovare strategie di interruzione ottimali, gli autori propongono tre distinti framework di ottimizzazione, tutti formulati come programmi lineari (LP) per garantire l'efficienza computazionale:

1. Minimax: Minimizza il tempo di esecuzione atteso nel caso peggiore, soggetto a un vincolo del tasso di disaccordo nel caso peggiore. Questo approccio non richiede la conoscenza preventiva della distribuzione dei voti positivi ($n$).
2. Minimean: Minimizza il tempo di esecuzione atteso soggetto a un vincolo del tasso di disaccordo atteso, assumendo una distribuzione $\hat{D}$ nota o stimata per $n$.
3. Minimixed: Minimizza il tempo di esecuzione atteso soggetto a un vincolo del tasso di disaccordo nel caso peggiore, assumendo una distribuzione per $n$.

Gli autori dimostrano che i problemi di ottimizzazione non lineari originali possono essere riformulati utilizzando variabili decisionali di probabilità condizionata ($p_{ij}, \pi_{ij}, \bar{\pi}_{ij}$). Questa riformulazione trasforma il problema in un programma lineare con $O(N^3)$ variabili decisionali, risolvibile efficientemente anche per ensemble con centinaia di alberi. Le strategie risultanti sono ampiamente deterministiche e seguono una semplice regola a "involucro" (envelope rule): interrompere se il numero di voti positivi supera una soglia superiore o scende sotto una soglia inferiore a uno specifico step $i$.

Contributi Chiave

• Formulazione Teorica: Il documento fornisce un quadro matematico rigoroso per l'interruzione anticipata negli ensemble a voto di maggioranza, definendo formalmente le strategie di interruzione e le metriche (tempo di esecuzione e tasso di disaccordo).
• Soluzioni Ottimali tramite Programmazione Lineare: Gli autori dimostrano che le strategie di interruzione ottimali per tre diverse nozioni di ottimalità (minimax, minimean, minimixed) possono essere trovate risolvendo programmi lineari. Ciò contrasta con il lavoro precedente che spesso si affidava a euristiche o assumeva l'indipendenza tra i modelli base.
• Assenza di Assunzione di Indipendenza: A differenza dei precedenti metodi di test sequenziale per gli ensemble (ad esempio, Schwing et al., 2011), questo approccio non assume che i modelli base siano indipendenti, rendendolo direttamente applicabile alle random forest dove le previsioni degli alberi sono correlate.
• Strategie Precomputabili: Gli autori hanno precomputato strategie ottimali per varie dimensioni di ensemble e tassi di disaccordo ammissibili (ADR), permettendo l'applicazione immediata senza necessità di ri-ottimizzazione per ogni nuovo dataset (particolarmente per l'approccio minimax).

Risultati Empirici
I metodi sono stati valutati su 27 dataset reali provenienti dal repository UCI Machine Learning e dai benchmark proposti da Grinsztajn et al., utilizzando random forest con $N=101$ alberi.

• Accelerazione (Speed-up): Nella maggior parte dei dataset, i metodi proposti hanno ottenuto accelerazioni di 4 volte o più (riducendo il tempo di esecuzione al 10–20% dell'ensemble completo) mantenendo un tasso di disaccordo dello 0,1% ($10^{-3}$).
• Varianza delle Prestazioni: L'approccio Minimean (utilizzando un set di calibrazione per stimare la distribuzione dei voti) ha generalmente offerto le accelerazioni più elevate, seguito da Minimixed, mentre il Minimax è stato il più conservativo.
• Caratteristiche del Dataset: L'efficacia dell'interruzione anticipata è correlata alla distribuzione dei voti degli alberi. I dataset in cui gli alberi votavano schiacciantemente per una classe (distribuzione bimodale) hanno permesso un'interruzione anticipata aggressiva. Al contrario, i dataset con alti tassi di errore dei modelli base e distribuzioni di voti centralizzate (ad esempio, "Dota2" e "Hospitalization") hanno mostrato accelerazioni minori, poiché il consenso era più difficile da raggiungere precocemente.
• Confronto: I metodi proposti hanno superato il metodo di base di Schwing et al. (2011), che si basa su bande di confidenza binomiali e assunzioni di indipendenza.

Significatività e Rivendicazioni
Il documento sostiene di presentare il primo metodo per ottenere strategie di interruzione anticipata provabilmente ottimali per classificatori ensemble binari basati sulla maggioranza senza assumere l'indipendenza tra i modelli base. Gli autori sottolineano che il loro approccio consente agli utenti di addestrare ensemble più grandi e accurati e di fare affidamento sulla strategia di interruzione per utilizzare solo le risorse computazionali necessarie per ogni specifica inferenza.

Il documento nota modestamente i propri limiti: il metodo è limitato alla classificazione binaria e agli ensemble a voto di maggioranza non pesati. Non può essere applicato direttamente a problemi multiclasse, alla regressione o a ensemble in cui i modelli base hanno pesi specifici o ordini di esecuzione richiesti. Inoltre, gli autori suggeriscono che, sebbene il metodo sia compatibile con la potatura (pruning), i guadagni potrebbero essere meno drammatici per le foresta potate, poiché la potatura mira a ridurre la ridondanza (voti correlati) che rende efficace l'interruzione anticipata. Il lavoro futuro è suggerito per estendere la teoria a ensemble multiclasse e pesati.