Un árbol de decisión es un clasificador con forma de cuestionario: en cada nodo hace una pregunta sobre un atributo del caso («¿cómo está el cielo?»), sigue la rama que corresponde a la respuesta y, al llegar a una hoja, entrega una clase. Lo interesante no es el cuestionario sino que nadie lo escribe: el algoritmo lo induce a partir de una tabla de ejemplos etiquetados. Es el primer tipo Simbólico de esta Pokédex que aprende de datos.
Cómo funciona
El ejemplo canónico son los datos del clima que Witten et al. (2017) usan a lo largo de todo su libro: catorce días descritos por cuatro atributos (cielo, temperatura, humedad y viento) y una clase, si se jugó o no a un juego que nunca se especifica (2017, pp. 10–11). El ejemplo viene de Quinlan (1986), donde los objetos eran «mañanas de sábado» y las clases se llamaban P y N (1986, pp. 85–86).
El algoritmo es recursivo: elige un atributo para la raíz, abre una rama por cada valor y repite el procedimiento en cada rama, solo con los ejemplos que llegan hasta ella; se detiene cuando un nodo es puro, es decir, cuando todos sus ejemplos tienen la misma clase (Witten et al., 2017, pp. 105–106). La cuestión decisiva es qué atributo elegir. ID3 usa la entropía de Shannon: la información, en bits, que falta para saber la clase de un caso que llegó a ese nodo. En la raíz hay 9 «sí» y 5 «no», lo que equivale a 0,940 bits; si se divide por cielo, la información esperada baja a 0,693 bits. La diferencia, 0,247 bits, es la ganancia de información de cielo, mayor que la de humedad (0,152), viento (0,048) y temperatura (0,029) (Witten et al., 2017, p. 107). Se pregunta primero por el cielo; en la rama «soleado» gana la humedad, y el resultado es el árbol del diagrama (2017, p. 109).
Leído con ojos de lógico, el árbol es una fórmula en forma normal disyuntiva: se juega si y solo si (cielo = nublado) ∨ (cielo = soleado ∧ humedad = normal) ∨ (cielo = lluvioso ∧ viento = falso). Cada camino de la raíz a una hoja «sí» es una conjunción; el concepto aprendido es la disyunción de esos caminos. Se puede experimentar con esto en el laboratorio de árboles.
Qué cambió
En los sistemas expertos las reglas se obtenían entrevistando especialistas; acá se inducen de los datos. ID3 nació, de hecho, de un desafío de Donald Michie: decidir, solo a partir de rasgos del tablero, si una posición de un final de ajedrez (rey y torre contra rey y caballo) estaba perdida en cierta cantidad de jugadas (Quinlan, 1986, p. 84). Casi al mismo tiempo, cuatro estadísticos de universidades californianas (Breiman, Friedman, Olshen y Stone) desarrollaron CART sin conocer el trabajo de Quinlan: un caso de invención paralela entre la estadística y el aprendizaje automático (Witten et al., 2017, p. 30).
C4.5, el sucesor de ID3, agregó la razón de ganancia, atributos numéricos, valores faltantes, poda y la conversión de árboles en reglas (Witten et al., 2017, pp. 113, 210). Desde los años 2000 los árboles volvieron en manada: los bosques aleatorios hacen votar a muchos árboles aleatorizados (2017, p. 485), y el gradient boosting sobre árboles es, según Chollet (2021), quizás el mejor algoritmo disponible para datos no perceptuales (2021, sec. 1.2.4).
Límites
- Sobreajuste. Un árbol que crece hasta que todas las hojas son puras se ajusta de más al conjunto de entrenamiento. Por eso casi todos los sistemas lo construyen entero y después lo podan, reemplazando subárboles por hojas (Witten et al., 2017, pp. 210, 213–214).
- Atributos con muchos valores. Un código de identificación por día obtiene la máxima ganancia posible (0,940 bits) y no generaliza nada; C4.5 corrige ese sesgo con la razón de ganancia (Witten et al., 2017, pp. 110–111).
- Inestabilidad. Un cambio pequeño en los datos puede alterar el atributo elegido en un nodo, y con él todo el subárbol (Witten et al., 2017, p. 481).
- Fronteras rectas. Con atributos numéricos, un árbol solo traza fronteras de decisión paralelas a los ejes; una diagonal se aproxima con una escalera de rectángulos (Witten et al., 2017, p. 251).
- Transparencia que se evapora. Un árbol de cinco hojas se lee de un vistazo; uno de miles de nodos, o un bosque de quinientos árboles, ya no.