El árbol de decisión

Un árbol de decisión (en inglés, decision tree) es un modelo que clasifica haciendo preguntas de sí o no, una detrás de otra, como un médico de urgencias que decide a quién atender primero o como el juego de adivinar un personaje. Cada pregunta mira un solo dato y lo compara con un umbral (threshold): ¿tiene la tensión por debajo de 91?, ¿más de 62 años? Según la respuesta se baja por una rama (branch) o por otra hasta llegar a una hoja (leaf), que da el veredicto. Lo que tiene de aprendizaje automático es que nadie escribe las preguntas: el algoritmo las elige mirando ejemplos ya clasificados, y la manera en que lo hace explica a la vez su éxito y su defecto principal.

La figura de esta página entrena uno delante del lector. Los puntos son ejemplos de dos clases, azul y naranja, repartidos por un plano según dos datos, x e y. Cada pregunta del árbol corta el plano con una línea recta paralela a uno de los ejes, y cada hoja es un rectángulo pintado del color que el árbol predice para todo lo que caiga dentro. Con profundidad cero no hay ninguna pregunta y el árbol responde siempre la clase más frecuente; con uno, parte el plano en dos; con tres, en ocho rectángulos como mucho. A la derecha, las primeras preguntas aparecen escritas, y la gráfica mide cuántos puntos acierta el árbol según la profundidad, con dos curvas que conviene mirar juntas.

El algoritmo elige cada pregunta por fuerza bruta y sin mirar adelante. Prueba todos los cortes posibles en los dos ejes, entre cada par de puntos consecutivos, y se queda con el que deja los dos lados más puros, es decir, más cerca de tener una sola clase. La medida de pureza de la figura es el índice de Gini (Gini impurity), la probabilidad de equivocarse si se etiqueta un punto al azar según las proporciones del grupo: vale cero en un grupo de un solo color y 0,5 en uno mitad y mitad. Una vez elegido el corte, el algoritmo repite lo mismo en cada mitad por separado, y así hasta que los grupos son puros o se alcanza la profundidad fijada. Encontrar el mejor árbol posible, el que acierta más con menos preguntas, es un problema intratable: Laurent Hyafil y Ronald Rivest demostraron en 1976 que pertenece a la familia de los NP-completos, para los que no se conoce un método eficiente. Por eso todos los algoritmos prácticos son voraces y deciden cada pregunta como si fuera la última.

El conjunto llamado tablero enseña lo que cuesta esa miopía. Los naranjas están en dos cuadrantes opuestos y los azules en los otros dos, de modo que ninguna pregunta sola, sobre x o sobre y, mejora nada: cada mitad sigue siendo mitad y mitad. El árbol voraz elige un primer corte casi al azar, empujado por el ruido de la muestra, y es la segunda pregunta la que ordena el plano. El conjunto de la frontera diagonal enseña el otro límite: una recta inclinada, que un modelo lineal como el perceptrón traza de una vez, el árbol solo puede imitarla con una escalera de rectángulos, más fina cuanto más profundo es.

Y en la profundidad está el problema. La curva negra de la figura, la de los puntos de entrenamiento, sube siempre: con suficientes preguntas, el árbol puede aislar cada punto en su propio rectángulo y acertarlos todos, incluidos los que el ruido cambió de color. La curva naranja, que mide los aciertos sobre cuatrocientos puntos que el árbol no ha visto, sube al principio, llega a un máximo y después baja o se estanca, porque los rectángulos diminutos dibujados alrededor de puntos ruidosos no dicen nada sobre los puntos nuevos. La distancia entre las dos curvas es el sobreajuste, y en un árbol de decisión es especialmente fácil de ver, porque cada error de más es un rectángulo que se puede señalar. Subir el ruido de la figura separa las curvas antes.

El árbol nació en la estadística de encuestas. James Morgan y John Sonquist, del Centro de Investigación de Encuestas de la Universidad de Michigan, propusieron en 1963 un procedimiento que llamaron AID, detección automática de interacciones, para partir a los encuestados en grupos cada vez más homogéneos según su renta o su consumo, en lugar de ajustar una ecuación con todas las variables a la vez. Veinte años después, cuatro estadísticos californianos, Leo Breiman, Jerome Friedman, Richard Olshen y Charles Stone, publicaron Classification and Regression Trees, el libro que dio al método sus reglas: el índice de Gini, la poda (pruning), que deja crecer el árbol entero y después corta las ramas que no mejoran sobre datos separados, y el nombre CART con que aún se conoce. El libro abre con un ejemplo médico: pacientes ingresados por un infarto, a los que tres preguntas sobre la tensión mínima, la edad y el ritmo cardiaco bastaban para separar a los de alto riesgo. En 1986, el australiano Ross Quinlan publicó ID3, que medía la pureza con la entropía de la teoría de la información y que dio lugar a una familia paralela de algoritmos.

Lo que convirtió al árbol en una de las herramientas más usadas del aprendizaje automático fue renunciar a su mejor cualidad. Un árbol solo, con sus pocas preguntas legibles, se puede explicar a un médico o a un juez, pero es inestable: una muestra un poco distinta da un primer corte distinto y un árbol entero diferente. Leo Breiman propuso en 2001 los bosques aleatorios (random forests): cientos de árboles profundos, cada uno entrenado con una muestra distinta de los datos y obligado a elegir cada pregunta entre unas pocas variables sorteadas, que votan el resultado. Cada árbol sobreajusta a su manera, y los errores, al no coincidir, se compensan. Las variantes que añaden árboles uno a uno para corregir los errores de los anteriores, el llamado gradient boosting, suelen ser hoy lo que mejor funciona con datos en forma de tabla, como los de un banco o un hospital, por encima de las redes neuronales que dominan con imágenes y texto. Se paga en legibilidad: un bosque de quinientos árboles ya no se puede leer, y la ventaja del modelo que hacía preguntas que cualquiera entendía se queda en cada uno de sus árboles por separado.