Alberi decisionali scalabili in MLlib

Gli alberi decisionali e i relativi insiemi sono cavalli di battaglia del settore per le attività di apprendimento automatico di classificazione e regressione. Gli alberi decisionali sono facili da interpretare, gestiscono caratteristiche categoriche e continue, si estendono alla classificazione multiclasse, non richiedono la scalabilità delle caratteristiche e sono in grado di acquisire le non linearità e le interazioni tra caratteristiche.

Data la loro popolarità, quasi tutte le librerie di apprendimento automatico forniscono un'implementazione dell'algoritmo dell'albero decisionale. Tuttavia, la maggior parte sono progettate per elaborazioni su singola macchina e raramente scalano elegantemente in un ambiente distribuito. Apache Spark è una piattaforma ideale per un'implementazione scalabile di alberi decisionali distribuiti, poiché l'elaborazione in-memory di Spark ci consente di eseguire in modo efficiente più passaggi sul set di dati di formazione.

Circa un anno fa, gli sviluppatori open source hanno unito le forze per creare un'implementazione rapida e distribuita di albero decisionale che fa parte della libreria MLlib di Spark dalla versione 1.0. Da allora la comunità Spark ha migliorato attivamente il codice dell'albero decisionale. Questo post del blog descrive l'implementazione, evidenziando alcune delle ottimizzazioni più importanti e presentando i risultati dei test che dimostrano la scalabilità.

Novità di Spark 1.1: gli alberi decisionali MLlib ora supportano la classificazione multiclasse e includono diverse ottimizzazioni delle prestazioni. Ora ci sono API per Python, oltre a Scala e Java.

Anteprima dell'algoritmo

A livello generale, un modello ad albero decisionale può essere considerato come istruzioni gerarchiche if-else che testano i valori delle caratteristiche per prevedere un'etichetta. Di seguito è riportato un modello di esempio per un'attività di classificazione binaria. Si basa sui dati sul chilometraggio delle auto degli anni '70! Predice il chilometraggio del veicolo (alto/basso) in base al peso (pesante/leggero) e alla potenza.

Un modello viene appreso da un set di dati di addestramento creando un albero dall'alto verso il basso. Le istruzioni if-else, note anche come criteri di divisione, vengono scelte per massimizzare la nozione di guadagno di informazioni, ovvero riducono la variabilità delle etichette nei (due) nodi figli sottostanti rispetto al nodo padre. Il modello ad albero decisionale appreso può essere utilizzato successivamente per prevedere le etichette per le nuove istanze.

Questi modelli sono interpretabili e spesso funzionano bene nella pratica. Gli alberi possono anche essere combinati per creare modelli ancora più potenti, utilizzando algoritmi ad albero di insieme. Insiemi di alberi, come foreste casuali e alberi potenziati, sono spesso i più performanti nel settore sia per le attività di classificazione che di regressione.

API semplice

L'esempio seguente mostra come un albero decisionale in MLlib possa essere facilmente addestrato utilizzando poche righe di codice utilizzando la nuova API Python in Spark 1.1. Legge un set di dati, addestra un modello ad albero decisionale e quindi misura l'errore di addestramento del modello. Esempi Java e Scala sono disponibili nella documentazione di Spark su DecisionTree.

Implementazione ottimizzata

Spark è una piattaforma di calcolo ideale per un'implementazione scalabile di alberi decisionali distribuiti grazie al suo sofisticato motore di esecuzione DAG e alla memorizzazione cache in memoria per il calcolo iterativo. Abbiamo menzionato alcune ottimizzazioni chiave.

Formazione per livello: selezioniamo le divisioni per tutti i nodi allo stesso livello dell'albero contemporaneamente. Questa ottimizzazione per livello riduce esponenzialmente il numero di passaggi sul set di dati: viene eseguito un passaggio per ogni livello, anziché un passaggio per ogni nodo nell'albero. Ciò comporta risparmi significativi in termini di I/O, calcolo e comunicazione.

Quantili approssimativi: le implementazioni a singolo computer utilizzano in genere valori di oggetto univoci ordinati per gli oggetti continui come candidati di divisione per il miglior calcolo di suddivisione. Tuttavia, trovare valori univoci ordinati è un'operazione costosa in un set di dati distribuito. L'albero decisionale MLlib utilizza quantili per ogni caratteristica come candidati divisi. Si tratta di un compromesso standard per migliorare le prestazioni dell'albero decisionale senza una perdita significativa di precisione.

Evitare l'operazione di mappatura: le prime implementazioni prototipo dell'albero decisionale utilizzavano sia operazioni di mappatura che di riduzione per selezionare le divisioni migliori per i nodi dell'albero. Il codice corrente utilizza notevolmente meno calcoli e comunicazioni sfruttando la struttura nota dei candidati divisi precalcolati per evitare la fase di mappatura.

Calcolo binario: il calcolo diviso migliore discretizza le caratteristiche in binari e tali binari vengono utilizzati per calcolare statistiche sufficienti per la divisione. Pre-calcoliamo le rappresentazioni binate di ogni istanza, risparmiando calcoli su ogni iterazione.

Scalabilità

Dimostriamo la scalabilità degli alberi decisionali MLlib con risultati empirici su vari set di dati e dimensioni di cluster.

Scalabilità in base alle dimensioni del set di dati

Le due figure seguenti mostrano i tempi di addestramento degli alberi decisionali man mano che si ridimensiona il numero di istanze e funzionalità nel set di dati. I tempi di formazione sono aumentati in modo lineare, evidenziando la scalabilità dell'implementazione.

Questi test sono stati eseguiti su un cluster EC2 con un nodo master e 15 nodi worker, utilizzando istanze r3.2xlarge (8 CPU virtuali, 61 GB di memoria). Gli alberi sono stati costruiti su 6 livelli e i set di dati sono stati generati dalla libreria spark-perf.

Spark 1.1 più veloci

Le due figure successive mostrano i miglioramenti apportati in Apache Spark 1.1 rispetto all'implementazione originale di Apache Spark 1.0. Sugli stessi set di dati e cluster, la nuova implementazione è 4-5 volte più veloce su molti set di dati!

Cosa succede ora?

Lo sviluppo di algoritmi basati su alberi oltre la versione 1.1 si concentrerà principalmente su algoritmi ensemble come foreste casuali e potenziamento. Continueremo inoltre a ottimizzare il codice dell'albero decisionale per le prestazioni e prevediamo di aggiungere il supporto per più opzioni nelle prossime versioni.

Per iniziare a utilizzare gli alberi decisionali, scarica subito Spark 1.1!

Ulteriori letture

• Vedere esempi e API nella documentazione sull'albero decisionale MLlib.
• Guarda la presentazione dell'albero decisionale dello Spark Summit 2014.
• Guarda il video e le diapositive di un altro discorso sugli alberi decisionali tenutosi a settembre 2014 a SF Scala/Bay Area Meeting sull'apprendimento automatico.

Ringraziamenti

Il lavoro sull'albero decisionale di Spark MLlib è stato inizialmente svolto in collaborazione con Hirakendu Das (Yahoo Labs), Evan Sparks (UC Berkeley AMPLab) e Ameet Talwalkar e Xiangrui Meng (Databricks). Da allora altri collaboratori si sono uniti e accogliamo con favore anche il vostro contributo!

(Questo post sul blog è stato tradotto utilizzando strumenti basati sull'intelligenza artificiale) Post originale