Experiments with Optimal Model Trees

Questo studio presenta formulazioni di programmazione lineare intera mista per costruire alberi modello globalmente ottimali con macchine a vettori di supporto lineari nelle foglie, dimostrando che tali alberi raggiungono un'accuratezza competitiva con strutture molto più compatte rispetto agli algoritmi greedy e ad altri metodi standard.

L'essenziale

Immagina di dover insegnare a un computer a prendere decisioni, come un medico che deve diagnosticare una malattia o un meccanico che deve capire perché un'auto non parte.

Il modo più classico per farlo è usare un albero decisionale. Pensa a un albero come a un gioco di "Indovina Chi" o a un albero genealogico: fai una domanda (es. "Ha la febbre?"), e in base alla risposta (Sì/No) vai a un ramo successivo, fino a raggiungere una foglia che ti dà la risposta finale.

Il problema è che gli alberi tradizionali sono un po' "stupidi" alle foglie: quando arrivi alla fine, ti dicono solo un valore fisso (es. "Diagnosi: Influenza"). È come se un medico, dopo aver fatto tutte le domande, ti dicesse solo "Malato" senza spiegarti quanto sei malato o perché.

Gli alberi modello (Model Trees) sono una versione più intelligente: alle foglie non mettono solo un valore fisso, ma una piccola formula matematica (una linea retta). È come se il medico, alla fine dell'interrogatorio, ti dicesse: "Hai la febbre, quindi la tua diagnosi è influenzale, ma la gravità dipende da quanto hai mangiato e dormito". Questo li rende più precisi e spesso più piccoli.

Il Problema: La fretta fa sbagliare

Di solito, i computer costruiscono questi alberi in modo "avido" (greedy). È come se dovessi costruire una casa e, stanza per stanza, scegliessi sempre la porta che sembra migliore in quel momento, senza guardare il progetto completo.

• Risultato: La casa viene costruita velocemente, ma spesso è piena di corridoi inutili, scale che portano al nulla e stanze troppo piccole. L'albero diventa enorme e confuso, anche se la previsione è decente.

La Soluzione: Il "Progettista Perfetto" (MILP)

Gli autori di questo articolo hanno detto: "E se invece di costruire stanza per stanza, usassimo un super-calcolatore per disegnare l'intero albero perfetto in un colpo solo?".
Hanno usato una tecnica chiamata MILP (Programmazione Lineare Intera Mista).
Immagina il MILP come un architetto geniale che, invece di costruire l'albero pezzo per pezzo, prova milioni di combinazioni diverse di domande e formule matematiche contemporaneamente per trovare l'unica struttura perfetta che sia:

1. Piccola (facile da capire per un umano).
2. Precisa (fa pochi errori).

Cosa hanno scoperto?

Hanno fatto esperimenti su molti problemi reali (classificare email come spam, prevedere il prezzo delle case, ecc.) e hanno trovato cose interessanti:

1. Piccoli ma potenti: Gli alberi costruiti con questo metodo "perfetto" sono molto più piccoli di quelli costruiti velocemente, ma fanno le stesse previsioni (o addirittura migliori). È come avere una mappa del tesoro di due pagine invece di un libro di 500 pagine: trovi il tesoro più velocemente e capisci meglio il percorso.
2. La complessità ha un prezzo: Questo metodo è molto potente, ma richiede molto tempo di calcolo. È come cercare di risolvere un cubo di Rubik guardando ogni possibile mossa possibile: trovi la soluzione perfetta, ma ci metti ore. Per alberi molto grandi, il computer si blocca (va in "timeout") prima di finire.
3. Il compromesso: Se sei disposto ad aspettare che il computer lavori (magari di notte), puoi ottenere modelli piccolissimi e facilissimi da spiegare a chiunque. Se hai fretta, i metodi classici vanno bene, ma i tuoi alberi saranno più grandi e confusi.

In sintesi

Questo articolo ci dice che, grazie a nuovi strumenti matematici potenti, possiamo creare "esperti" artificiali che sono piccoli, precisi e facili da spiegare. Non sono più solo scatole nere che lanciano numeri, ma alberi logici dove ogni ramo ha una sua piccola regola matematica che spiega il mondo.

È come passare da un manuale di istruzioni di 1000 pagine scritto in codice incomprensibile a un semplice diagramma di flusso di 3 pagine che chiunque può seguire per prendere la decisione giusta.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "Experiments with Optimal Model Trees" di Sabino Francesco Roselli ed Eibe Frank, presentata in italiano.

1. Problema e Contesto

Il paper affronta il compromesso tra accuratezza predittiva e interpretabilità nell'apprendimento automatico (Machine Learning).

• Decision Tree Classici: Offrono alta interpretabilità ma, quando crescono in modo "greedy" (avido), tendono a diventare troppo grandi e complessi per mantenere un'alta accuratezza. Inoltre, usano valori costanti nelle foglie, il che limita la loro capacità di modellare relazioni complesse all'interno di sottogruppi di dati.
• Model Trees: Sono una variante che utilizza modelli lineari (es. regressione lineare o SVM) nelle foglie invece di valori costanti. Questo permette di ottenere alberi più piccoli con la stessa o maggiore accuratezza.
• Il Gap: Gli algoritmi attuali per costruire alberi (sia classici che modello) sono prevalentemente greedy (top-down). Questo significa che ogni split è scelto per essere localmente ottimale senza considerare l'impatto globale sulla struttura dell'albero, portando spesso a soluzioni sub-ottimali.
• Obiettivo: Investigare se l'uso della Programmazione Lineare Intera Mista (MILP) per costruire alberi di decisione globalmente ottimali, combinati con modelli lineari nelle foglie, possa produrre alberi più compatti e accurati rispetto agli approcci greedy o dinamici esistenti.

2. Metodologia

Gli autori propongono una formulazione MILP per apprendere Optimal Model Trees (OMT) sia per la classificazione che per la regressione.

• Struttura dell'Albero: Viene considerata una struttura ad albero perfetto di profondità $D$. Le variabili decisionali binarie determinano se un nodo si divide (split) o meno.
• Modelli nelle Foglie:
  • Regressione: Vengono utilizzati Support Vector Machines (SVM) lineari con perdita a errore assoluto (equivalente a $\epsilon=0$) e regolarizzazione L1.
  • Classificazione Binaria: Vengono utilizzati SVM lineari per la classificazione.
  • Classificazione Multi-classe: Vengono implementati SVM multi-classe (uno per classe) in ogni foglia.
• Formulazione MILP:
  • L'obiettivo è minimizzare la somma degli errori di previsione (residui) e la norma L1 dei pesi dei modelli lineari (per favorire la sparsità), soggetta a vincoli sulla struttura dell'albero.
  • Vengono definiti vincoli per garantire che ogni punto dati finisca in una sola foglia, che gli split siano significativi (entrambi i rami non vuoti) e che la struttura dell'albero sia coerente (un nodo non può dividersi se il genitore non si è diviso).
  • Vengono considerate due varianti:
    1. Univariate: Gli split sono basati su una singola feature (più interpretabile).
    2. Multivariate: Gli split sono basati su combinazioni lineari di feature (potenzialmente più accurate ma meno interpretabili).
• Ottimizzazione degli Iperparametri: Poiché la soluzione MILP dipende dal coefficiente di regolarizzazione $C$ e dal numero massimo di split $S$, gli autori utilizzano un approccio iterativo con validazione incrociata per trovare la combinazione ottimale, limitando la profondità massima dell'albero (tipicamente $D=2$ o $D=3$).

3. Contributi Chiave

1. Nuova Formulazione MILP per Classificazione: Mentre la formulazione per la regressione esisteva già in lavori precedenti (es. [14]), gli autori presentano una nuova formulazione basata su SVM per la classificazione, che sembra essere la prima del suo genere.
2. Valutazione Empirica Estesa: Il paper fornisce una delle valutazioni empiriche più complete degli alberi modello ottimali, confrontandoli su 20 dataset di classificazione binaria, 5 multi-classe e 20 dataset di regressione.
3. Confronto con lo Stato dell'Arte: I modelli proposti (OCMT per classificazione, ORMT per regressione) sono confrontati contro:
   • Decision Tree ottimali classici (OCT/OR T).
   • Algoritmi greedy (CART, M5P, LMT).
   • Metodi basati su Dynamic Programming (DL8.5, SRT-L).
   • Metodi con ricerca locale (LS-OMT).
   • Random Forest e SVM lineari.
4. Analisi della Scalabilità: Un'analisi dettagliata dei tempi di calcolo e del compromesso tra complessità computazionale e qualità della soluzione.

4. Risultati Sperimentali

• Accuratezza vs. Dimensione:
  • Gli Optimal Model Trees (OMT) raggiungono un'accuratezza significativamente superiore rispetto agli alberi ottimali classici (OCT) della stessa dimensione, a volte con margini superiori al 30%.
  • Rispetto agli algoritmi greedy (come CART o M5P), gli OMT sono competitivi in termini di accuratezza ma producono alberi costantemente più piccoli (meno foglie).
  • In regressione, ORMT (con SVM) supera ORT (senza SVM) e altri metodi in 9 casi su 20, mostrando errori (RAE) inferiori.
• Interpretabilità: Grazie alla loro piccola dimensione (spesso meno di 10 foglie), gli alberi ottimali sono molto più interpretabili rispetto agli alberi greedy che possono crescere fino a centinaia di foglie pur avendo prestazioni simili.
• Univariate vs. Multivariate: Contrariamente alle aspettative, gli alberi multivariati (OCMT-H e ORMT-H) non hanno mostrato un miglioramento sistematico rispetto a quelli univariati in termini di accuratezza, sebbene abbiano ottenuto guadagni su dataset specifici (es. "Parity" e "Long"). Tuttavia, gli alberi multivariati sono meno interpretabili.
• Tempi di Calcolo:
  • Il calcolo è computazionalmente oneroso. Con un limite di tempo di 3600 secondi, il solver (Gurobi) spesso non trova la soluzione ottima globale per alberi con più di uno o due split, fermandosi con un "gap di ottimalità" elevato.
  • Tuttavia, anche le soluzioni trovate prima del timeout sono competitive con gli algoritmi greedy.
  • Il tempo di calcolo scala male con il numero di feature e punti dati, rendendo il metodo adatto principalmente a dataset di dimensioni moderate dove l'interpretabilità è critica.

5. Significato e Conclusioni

Il lavoro dimostra che l'approccio basato su MILP per gli alberi modello è una via praticabile per ottenere modelli "glass-box" (trasparenti) che bilanciano efficacemente accuratezza e complessità.

• Impatto Pratico: Sebbene i tempi di calcolo siano elevati, il metodo è ideale per applicazioni in cui l'interpretabilità è fondamentale (es. sanità, finanza, produzione industriale) e i dataset non sono massivi.
• Limiti: La scalabilità è la principale limitazione. Per dataset molto grandi o con molte feature, il tempo di risoluzione diventa proibitivo.
• Prospettive Future: Gli autori suggeriscono l'uso di tecniche di decomposizione per accelerare il calcolo e l'applicazione di queste formulazioni agli alberi di policy ottimali.

In sintesi, il paper conferma che abbandonare l'approccio greedy a favore di un'ottimizzazione globale (MILP) per gli alberi modello permette di costruire modelli più piccoli, più accurati e quindi più affidabili e interpretabili, a patto di accettare un costo computazionale più elevato.