Árboles de decisiones escalables en MLlib

Los árboles de decisión y sus conjuntos son caballos de batalla del sector para las tareas de aprendizaje automático de clasificación y regresión. Los árboles de decisión son fáciles de interpretar, manejan elementos categóricos y continuos, se extienden a la clasificación de varias clases, no requieren escalado de elementos y pueden capturar no linealidades e interacciones de elementos.

Debido a su popularidad, casi todas las bibliotecas de aprendizaje automático proporcionan una implementación del algoritmo de árbol de decisiones. Sin embargo, la mayoría están diseñados para computación de una sola máquina y rara vez se escalan de forma elegante a un entorno distribuido. Apache Spark es una plataforma ideal para una implementación de árbol de decisiones distribuido escalable, ya que la informática en memoria de Spark nos permite realizar múltiples pasadas de manera eficiente sobre el conjunto de datos de entrenamiento.

Hace aproximadamente un año, los desarrolladores de código abierto unieron fuerzas para crear una implementación rápida de árbol de decisiones distribuido que forma parte de la biblioteca MLlib de Spark desde la versión 1.0. La comunidad de Spark ha mejorado activamente el código del árbol de decisiones desde entonces. En esta entrada de blog se describe la implementación, se destacan algunas de las optimizaciones importantes y se presentan los resultados de las pruebas que demuestran la escalabilidad.

Nuevo en Spark 1.1: los árboles de decisión MLlib ahora admiten la clasificación multiclases e incluyen varias optimizaciones de rendimiento. Ahora hay API para Python, además de Scala y Java.

Antecedentes del algoritmo

En un nivel alto, un modelo de árbol de decisiones puede considerarse como sentencias jerárquicas si-else que prueban valores de características para predecir una etiqueta. A continuación se muestra un modelo de ejemplo para una tarea de clasificación binaria. ¡Se basa en datos de kilometraje de automóviles de la década de 1970! Predice el kilometraje del vehículo (alto/bajo) en función del peso (pesado/ligero) y la potencia.

Un modelo se aprende de un conjunto de datos de entrenamiento mediante la creación de un árbol de arriba hacia abajo. Las sentencias if-else, también conocidas como criterios de división, se eligen para maximizar la noción de ganancia de información: reducen la variabilidad de las etiquetas en los (dos) nodos hijos subyacentes en comparación con el nodo padre. El modelo de árbol de decisiones aprendido se puede utilizar posteriormente para predecir las etiquetas de las instancias nuevas.

Estos modelos son interpretables y a menudo funcionan bien en la práctica. Los árboles también se pueden combinar para crear modelos aún más potentes, utilizando algoritmos de árbol de conjunto. Los conjuntos de árboles, como bosques aleatorios y árboles potenciados, suelen ser los que mejor se desempeñan en la industria tanto para tareas de clasificación como de regresión.

API sencilla

El ejemplo siguiente muestra cómo se puede entrenar fácilmente un árbol de decisiones en MLlib con unas pocas líneas de código utilizando la nueva API de Python de Spark 1.1. Lee un conjunto de datos, entrena un modelo de árbol de decisiones y, a continuación, mide el error de entrenamiento del modelo. Puede encontrar ejemplos de Java y Scala en la documentación de Spark en DecisionTree.

Implementación optimizada

Spark es una plataforma informática ideal para una implementación escalable de árboles de decisiones distribuidos gracias a su sofisticado motor de ejecución DAG y almacenamiento en caché en memoria para el cálculo iterativo. Mencionamos algunas optimizaciones clave.

Entrenamiento por niveles: seleccionamos las divisiones para todos los nodos del mismo nivel del árbol simultáneamente. Esta optimización por niveles reduce exponencialmente el número de pasadas sobre el conjunto de datos: hacemos una por cada nivel, en lugar de una por cada nodo del árbol. Esto permite ahorros significativos en E/S, computación y comunicación.

Cuantiles aproximados: las implementaciones de una sola máquina suelen utilizar valores de elemento únicos ordenados para elementos continuos como candidatos a división para el mejor cálculo de división. Sin embargo, encontrar valores únicos ordenados es una operación costosa en un conjunto de datos distribuidos. El árbol de decisiones MLlib utiliza cuantiles para cada elemento como candidatos divididos. Es una opción estándar para mejorar el rendimiento del árbol de decisiones sin una pérdida significativa de precisión.

Evitar la operación de mapa: las primeras implementaciones prototipo del árbol de decisiones utilizaban operaciones de mapa y reducción al seleccionar las mejores divisiones para los nodos del árbol. El código actual utiliza significativamente menos cálculo y comunicación al explotar la estructura conocida de los candidatos a división precalculados para evitar la etapa de mapeo.

Cálculo por binos: el mejor cálculo dividido discretiza los elementos en compartimentos, y estos compartimentos se utilizan para calcular estadísticas suficientes para la división. Calculamos previamente las representaciones agrupadas de cada instancia, ahorrando el cálculo en cada iteración.

Escalabilidad

Demostramos la escalabilidad de los árboles de decisión MLlib con resultados empíricos en varios conjuntos de datos y tamaños de clúster.

Escalado con tamaño de conjunto de datos

Las dos figuras siguientes muestran los tiempos de entrenamiento de los árboles de decisión a medida que escalamos el número de instancias y características del conjunto de datos. Los tiempos de formación aumentaron linealmente, lo que pone de relieve la escalabilidad de la implementación.

Estas pruebas se ejecutaron en un clúster de EC2 con un nodo maestro y 15 nodos de trabajo, utilizando instancias r3.2xlarge (8 CPU virtuales y 61 GB de memoria). Los árboles se construyeron en 6 niveles y los conjuntos de datos se generaron mediante la biblioteca spark-perf.

Spark 1.1 aumenta la velocidad

Las dos figuras siguientes muestran las mejoras en Apache Spark 1.1 en comparación con la implementación original de Apache Spark 1.0. En los mismos conjuntos de datos y clúster, la nueva implementación es 4-5 veces más rápida en muchos conjuntos de datos.

¿Qué sigue?

El desarrollo de algoritmos basados en árboles después de la versión 1.1 se centrará principalmente en algoritmos de conjunto, como bosques aleatorios y potenciación. También seguiremos optimizando el código del árbol de decisiones para mejorar el rendimiento y planeamos añadir soporte para más opciones en las próximas versiones.

Para empezar a usar árboles de decisión tú mismo, descarga Spark 1.1 hoy mismo.

Lectura adicional

• Consulte ejemplos y la API en la documentación del árbol de decisiones de MLlib.
• Vea la presentación del árbol de decisiones de la Cumbre Spark 2014.
• Vea el video y las diapositivas de otra charla sobre árboles de decisiones en una reunión de aprendizaje automático en SF Scala/Bay Area en septiembre de 2014.

Agradecimientos

El trabajo del árbol de decisiones de Spark MLlib se realizó inicialmente conjuntamente con Hirakendu Das (Yahoo Labs), Evan Sparks (UC Berkeley AMPLab) y Ameet Talwalkar y Xiangrui Meng (Databricks). Desde entonces se han unido más colaboradores, ¡y agradecemos su aportación también!

(Esta entrada del blog ha sido traducida utilizando herramientas basadas en inteligencia artificial) Publicación original