Approximation-Free Differentiable Oblique Decision Trees

Riepilogo Tecnico: Alberi di Decisione Obliqui Differenziabili Senza Approssimazioni

Enunciato del Problema
Gli Alberi di Decisione (DT) sono altamente apprezzati in domini critici per la sicurezza (ad esempio, diagnosi medica) per la loro interpretabilità e efficacia sui dati tabellari. Tuttavia, l'addestramento di DT obliqui accurati (dove le divisioni sono combinazioni lineari di caratteristiche anziché allineate agli assi) è computazionalmente impegnativo a causa della natura NP-difficile dello spazio di ricerca. Sebbene recenti approcci differenziabili consentano l'addestramento basato sul gradiente, essi si affidano ad approssimazioni che compromettono l'integrità del processo di apprendimento:

1. DT "Soft": Utilizzano confini probabilistici "soft" (ad esempio, attivazioni Sigmoid) per rendere gli alberi differenziabili, ma la conversione in decisioni "hard" degrada spesso l'accuratezza.
2. Stimatori Straight-Through (STE): Utilizzati in metodi come DGT e ICCT per approssimare i gradienti attraverso decisioni hard non differenziabili. Ciò crea una discrepanza semantica tra il passaggio in avanti (valutazione) e il passaggio all'indietro (ottimizzazione). Nei task di regressione, questa discrepanza porta a aggiornamenti di gradiente distorti, instabilità strutturale e sottoutilizzo dei nodi foglia, poiché i parametri interni vengono aggiornati basandosi su tutti i regressori mentre ne viene selezionato solo uno.

Metodologia: DTSemNet
Gli autori propongono DTSemNet, una nuova architettura di rete neurale che fornisce una rappresentazione invertibile e semanticamente equivalente di DT obliqui hard. A differenza dei lavori precedenti, DTSemNet consente un addestramento end-to-end utilizzando la discesa del gradiente standard senza approssimazioni.

• Architettura: DTSemNet codifica un DT con $m$ nodi interni e $n$ foglie in una rete neurale utilizzando attivazioni ReLU e operazioni lineari.
  • Nodi Interni: Rappresentati da layer lineari che calcolano $\langle A_i, x \rangle + b_i$.
  • Diramazione: Utilizza attivazioni ReLU per separare gli esiti positivi ($\top$) e negativi ($\bot$), garantendo che esattamente un ramo sia attivo per qualsiasi input (eccetto sui confini di misura zero).
  • Foglie: Un layer lineare a pesi fissi aggrega i rami attivi per produrre i logit per ogni foglia.
• Equivalenza Semantica: Il Teorema 1 dimostra che per qualsiasi input $x$, la foglia selezionata dal DT hard è identica alla foglia con il logit di output massimo nella rete DTSemNet. Pertanto, la funzione di valutazione (passaggio in avanti) e la funzione di ottimizzazione (passaggio all'indietro) sono semanticamente identiche.

Strategia di Regressione: Annealed Top-k
Mentre la classificazione si allinea naturalmente a questa formulazione (tramite argmax), la regressione richiede l'ottimizzazione congiunta dell'instradamento (nodi interni) e dei regressori delle foglie. Gli autori identificano che l'uso di un singolo STE (come nel loro precedente lavoro da conferenza) causa instabilità perché aggiorna i nodi interni basandosi su tutti i regressori, aggiornando però solo uno dei regressori per passo.

Per risolvere ciò, il paper introduce un metodo Annealed Top-k:

1. Meccanismo: Invece di una selezione Top-1 hard durante l'addestramento, il modello utilizza inizialmente un selettore Top-$k$ ($k \ge 2$) combinato con una Softmax scalata per temperatura. Ciò permette al modello di instradare gli input a più esperti (foglie) simultaneamente, fornendo gradienti informativi.
2. Annealing: Il valore di $k$ viene gradualmente ridotto da $k \ge 2$ a $k=1$ nel corso delle epoche di addestramento.
3. Vantaggi:
   • Coerenza del Gradiente: A differenza dello STE, i passaggi in avanti e all'indietro condividono la stessa semantica a ogni passo $k$.
   • Aggiornamenti Bilanciati: I parametri dei nodi interni vengono aggiornati basandosi solo sui regressori top-$k$ selezionati, prevenendo l'influenza destabilizzante di foglie distanti non selezionate.
   • Esplorazione: Più regressori vengono aggiornati per un singolo campione, permettendo al modello di adattarsi se la decisione di instradamento cambia in seguito durante l'addestramento.
4. Fine-tuning: Una volta raggiunto $k=1$, i nodi interni vengono congelati e i regressori delle foglie vengono affinati utilizzando campioni aumentati per prevenire l'overfitting.

Contributi Chiave

1. Architettura DTSemNet: Una codifica differenziabile di DT obliqui semanticamente equivalente all'albero hard, che consente un addestramento esatto tramite discesa del gradiente senza approssimazioni per la classificazione.
2. Annealed Top-k per la Regressione: Una procedura di addestramento innovativa che elimina l'approssimazione e il bias intrinseci nei metodi basati su STE per la regressione, garantendo un'ottimizzazione congiunta stabile e accurata dei parametri di instradamento e delle foglie.
3. Policy RL Programmatiche: Dimostrazione di DTSemNet come policy programmatica nell'Apprendimento per Rinforzo (RL), sostituendo le Reti Neurali (NN) standard sia negli spazi di azione discreti che continui.

Risultati Sperimentali
Gli autori hanno valutato DTSemNet rispetto a metodi dello stato dell'arte (TAO, DGT, CRO-DT, CART, ICCT, VIPER) su benchmark di classificazione, regressione e RL.

• Classificazione: DTSemNet ha ottenuto le migliori prestazioni su ogni dataset testato, inclusi alberi concisi e densi. Ha superato significativamente i metodi non basati su gradienti (ad esempio, TAO, CRO-DT) e le approssimazioni basate su gradienti (DGT), riducendo l'errore di classificazione fino al 10% su benchmark impegnativi come il Riconoscimento Ottico. I tempi di addestramento sono stati comparabili a DGT ma significativamente più veloci rispetto ai metodi di ricerca globale.
• Regressione: DTSemNet con Top-k ha superato tutti i competitor su quasi tutti i dataset. Ha ottenuto un miglioramento medio dell'RMSE del 3% rispetto a TAO-Linear e ha superato significativamente DTSemNet-STE (che utilizzava STE). Studi di ablazione hanno confermato che Top-k porta a un utilizzo più bilanciato delle foglie e a un'evoluzione stabile dei pesi rispetto allo STE, che tende a sottoutilizzare le foglie.
• Apprendimento per Rinforzo:
  • Azioni Discrete: DTSemNet ha eguagliato o superato le prestazioni delle NN e ha superato significativamente altre policy basate su DT (DGT, ICCT, VIPER) su ambienti come LunarLander e Zerglings.
  • Azioni Continue: Utilizzando la strategia di annealing Top-k con SAC, DTSemNet ha superato le baseline NN e i DT basati su STE su Continuous LunarLander e BipedalWalker, dimostrando che l'addestramento senza approssimazioni produce policy superiori anche nel controllo continuo.

Significato e Affermazioni
Il paper afferma che DTSemNet è la prima architettura a realizzare un addestramento senza approssimazioni per DT obliqui sia in contesti di classificazione che di regressione. Rimuovendo la discrepanza semantica tra valutazione e ottimizzazione, supera l'instabilità e il bias degli approcci basati su STE. Gli autori sostengono che ciò colma il divario tra l'interpretabilità dei modelli simbolici (DT) e la scalabilità dell'addestramento basato su gradienti, rendendo modelli ad alte prestazioni e interpretabili fattibili per applicazioni critiche per la sicurezza e ambienti RL complessi.

Limitazioni e Lavori Futuri
Gli autori riconoscono che, in quanto DT, DTSemNet non è adatto per input ad alta dimensionalità come le immagini, dove fatica con forme complesse. I lavori futuri si concentreranno sullo sviluppo di metodi differenziabili per la crescita e la potatura adattiva degli alberi, allontanandosi dalle altezze fisse degli alberi come iperparametri.