Arbres de décision évolutifs dans MLlib

Les arbres de décision et leurs ensembles sont des chevaux de bataille du secteur pour les tâches de classification et de régression en apprentissage automatique. Les arbres de décision sont faciles à interpréter, gèrent les objets catégoriels et continus, s'étendent à la classification multiclasse, ne nécessitent pas de mise à l'échelle des objets et sont capables de capturer les non-linéarités et les interactions entre objets.

En raison de leur popularité, presque toutes les bibliothèques d'apprentissage automatique fournissent une implémentation de l'algorithme d'arbre de décision. Cependant, la plupart sont conçus pour le calcul sur une seule machine et évoluent rarement de manière élégante dans un environnement distribué. Apache Spark est une plate-forme idéale pour une implémentation évolutive d'arbre de décision distribué, car le calcul en mémoire de Spark nous permet d'effectuer efficacement plusieurs passages sur le jeu de données de formation.

Il y a environ un an, des développeurs open source ont uni leurs forces pour mettre au point une implémentation rapide d'arbre de décision distribuée qui fait partie de la bibliothèque Spark MLlib depuis la version 1.0. La communauté Spark a activement amélioré le code de l'arbre de décision depuis. Cet article de blog décrit la mise en œuvre, met en évidence certaines des optimisations importantes et présente les résultats des tests démontrant l'évolutivité.

Nouveauté de Spark 1.1 : les arbres de décision MLlib prennent désormais en charge la classification multiclasses et incluent plusieurs optimisations des performances. Il existe désormais des API pour Python, en plus de Scala et Java.

Contexte de l'algorithme

À un niveau élevé, un modèle d'arbre de décision peut être considéré comme des instructions hiérarchiques si-else qui testent les valeurs des caractéristiques afin de prédire une étiquette. Un exemple de modèle de tâche de classification binaire est présenté ci-dessous. Il est basé sur les données de kilométrage des voitures des années 1970 ! Il prédit le kilométrage du véhicule (élevé/faible) en fonction du poids (lourd/léger) et de la puissance.

Un modèle est appris à partir d'un jeu de données d'apprentissage en construisant une arborescence descendante. Les instructions if-else, également appelées critères de division, sont choisies pour maximiser la notion de gain d'informations : elles réduisent la variabilité des étiquettes dans les (deux) noeuds enfants sous-jacents par rapport au noeud parent. Le modèle d'arbre de décision appris peut ensuite être utilisé pour prédire les étiquettes des nouvelles instances.

Ces modèles sont interprétables et fonctionnent souvent bien dans la pratique. Les arbres peuvent également être combinés pour créer des modèles encore plus puissants, à l'aide d'algorithmes d'arborescence d'ensemble. Les ensembles d'arbres tels que les forêts aléatoires et les arbres renforcés sont souvent les plus performants dans l'industrie pour les tâches de classification et de régression.

API simple

L'exemple ci-dessous montre comment un arbre de décision dans MLlib peut être facilement formé à l'aide de quelques lignes de code à l'aide de la nouvelle API Python de Spark 1.1. Il lit un jeu de données, forme un modèle d'arbre de décision, puis mesure l'erreur d'apprentissage du modèle. Des exemples Java et Scala sont disponibles dans la documentation Spark sur DecisionTree.

Mise en œuvre optimisée

Spark est une plate-forme de calcul idéale pour une implémentation évolutive d'arbres de décision distribués grâce à son moteur d'exécution DAG sophistiqué et à sa mise en cache en mémoire pour le calcul itératif. Nous mentionnons quelques optimisations clés.

Formation par niveau : nous sélectionnons les divisions pour tous les nœuds du même niveau de l'arborescence simultanément. Cette optimisation niveau par niveau réduit exponentiellement le nombre de passes sur le jeu de données : nous effectuons une passe pour chaque niveau, plutôt qu'une pour chaque nœud de l'arborescence. Cela permet de réaliser des économies significatives en E/S, en calcul et en communication.

Quantiles approximatifs : les implémentations sur machine unique utilisent généralement des valeurs d'objet uniques triées pour les objets continus comme candidats de fractionnement pour le meilleur calcul de fractionnement. Toutefois, la recherche de valeurs uniques triées est une opération coûteuse sur un jeu de données distribué. L'arbre de décision MLlib utilise des quantiles pour chaque fonction en tant que candidats divisés. Il s'agit d'un compromis standard pour améliorer les performances de l'arbre de décision sans perte significative de précision.

Éviter l'opération de cartographie : les premières implémentations prototypes de l'arbre de décision utilisaient à la fois des opérations de cartographie et de réduction lors de la sélection des meilleures divisions pour les noeuds de l'arbre. Le code actuel utilise nettement moins de calcul et de communication en exploitant la structure connue des candidats divisés pré-calculés pour éviter l'étape de cartographie.

Calcul par tranche : le meilleur calcul fractionné discrétise les objets en tranches, et ces tranches sont utilisées pour calculer suffisamment de statistiques pour la fractionnement. Nous précalculons les représentations binaires de chaque instance, ce qui permet d'économiser le calcul à chaque itération.

Évolutivité

Nous démontrons l'évolutivité des arbres de décision MLlib avec des résultats empiriques sur différents jeux de données et tailles de clusters.

Mise à l'échelle en fonction de la taille du jeu de données

Les deux figures ci-dessous montrent les temps d'apprentissage des arbres de décision lorsque nous faisons évoluer le nombre d'instances et d'éléments dans le jeu de données. Les temps de formation ont augmenté linéairement, soulignant l'évolutivité de l'implémentation.

Ces tests ont été exécutés sur un cluster EC2 avec un nœud maître et 15 nœuds travailleurs, à l'aide d'instances r3.2xlarge (8 CPU virtuels, 61 Go de mémoire). Les arbres ont été construits sur 6 niveaux et les jeux de données ont été générés par la bibliothèque spark-perf.

Accélérations de Spark 1.1

Les deux figures suivantes montrent les améliorations apportées à Apache Spark 1.1 par rapport à l'implémentation d'origine d'Apache Spark 1.0. Sur les mêmes jeux de données et cluster, la nouvelle implémentation est 4 à 5 fois plus rapide sur de nombreux jeux de données.

Quelle est la prochaine étape ?

Le développement d'algorithmes arborescents après la version 1.1 se concentrera principalement sur les algorithmes d'ensemble tels que les forêts aléatoires et le boosting. Nous allons également continuer à optimiser le code de l'arbre de décision pour améliorer les performances et prévoir d'ajouter la prise en charge de nouvelles options dans les prochaines versions.

Pour commencer à utiliser vous-même les arbres de décision, téléchargez Spark 1.1 dès aujourd'hui !

Lectures complémentaires

• Voir des exemples et l'API dans la documentation sur l'arbre de décision MLlib.
• Visionnez la présentation de l'arbre de décision du sommet Spark 2014.
• Regardez la vidéo et les diapositives d'une autre présentation sur les arbres de décision lors d'une rencontre sur le machine learning à SF Scala/Bay Area en septembre 2014.

Remerciements

Le travail sur l'arbre de décision de Spark MLlib a initialement été réalisé conjointement avec Hirakendu Das (Yahoo Labs), Evan Sparks (UC Berkeley AMPLab), Ameet Talwalkar et Xiangrui Meng (Databricks). D'autres contributeurs se sont joints depuis, et nous apprécions également vos commentaires!

(Cet article de blog a été traduit à l'aide d'outils basés sur l'intelligence artificielle) Article original