El discreto encanto de los árboles olvidadizos

I.

A mediados de los ochenta, hubo un momento fundacional en la historia del aprendizaje automático: la aparición de los árboles de decisión. El artículo de Breiman sobre las dos culturas puede entenderse así: existe —o existía en esa época— la cultura de los que usan métodos estadísticos tradicionales y la de los que usan árboles de todo tipo.

Herramientas de minería de datos de entonces, tales como las que vendían SAS o IBM, no encerraban debajo del capó otra cosa —u otra cosa novedosa— que árboles de decisión propietarios. Por todo lo anterior había mucho interés en conseguir mejores árboles, árboles que permitiesen crear mejores modelos —en el sentido, claro está, de cometer errores pequeños—.

Pero las limitaciones de los árboles son sistémicas: son modelos demasiado pequeños como para poder almacenar toda la información necesaria para resolver un problema: apenas almacenan unos cuantos bits. El mundo del aprendizaje automático derivó por tanto hacia modelos grandes, más memoriosos, capaces de combinar la información de múltiples modelos flojos (típicamente, árboles). El resultado es conocido: random forests, diversas versiones del boosting, etc.

II.

Pero una vez que combinas modelos flojos ya no es estrictamente necesario que tu modelo flojo sea el menos flojo de entre todos ellos. Además, otras propiedades de segundo orden de los árboles comienzan a cobrar importancia.

Por ejemplo, supongamos que tenemos dos tipos de árboles, el A y el B. Sistemáticamente, se ha demostrado que el A tiene un error (pensemos en el RMSE) ligeramente mejor que el B en una amplia clase de problemas. Supongamos también que el A tarda un 50% más de tiempo en ajustar que el B, que es más simple. Entonces, en un mundo sin boosting, el modelo A sería preferible al B. Pero puede que modelos de boosting basados en B funcionen mejor que los basados en A: efectivamente, el boosting se encarga de mejorar la capacidad predictiva de los modelos, mientras que el coste computacional adicional de A se traslada al modelo global con creces.

Dicho de otra manera:

• En un mundo sin boosting (o random forests, etc.), el factor limitante es el error.
• En un mundo con boosting (y random forests, etc.), los factores limitantes son otros, como la velocidad, el tamaño del modelo, la simplicidad (que permita algunas optimizaciones ad hoc en el modelo superior), etc.

III.

Cuando la pura minimización del error deja de ser el condicionante único (como pasaba, por otros motivos con los árboles frugales) surgen muchas opciones que pueden ser más o menos adecuadas para un fin concreto.

Y aquí entra catboost, una de las variantes del boosting más populares. catboost usa árboles olvidadizos que funcionan más o menos así:

0. Se parte de un conjunto de datos D y unas variables $x_i$.
1. Para el primer corte, se selecciona una variable (como en los árboles normales) y un punto de corte; con ellos se crean las subramas $D_1$ y $D_2$.
2. Para el segundo corte, se selecciona una única variable (¡no una en cada subrama!), un punto de corte y este se aplica a las subramas $D_1$ y $D_2$ (aunque existe una variante, que no es la que usa catboost, en la que los puntos de corte dependen de la subrama).
3. Se elige una única variable y un único punto de corte para partir las cuatro subramas del punto anterior.
4. Etc.

Obviamente, este algoritmo es mucho más simple que CART, por ejemplo. Es necesario, además, que funcione peor en términos de la minimización del error: es el mismo salvo que con restricciones —en cada nivel se usa una única variable de corte— adicionales. Y habría caído necesariamente en lo que su nombre indica —el olvido— de no haber sido rescatado para conformar el motor de catboost.

IV.

¿Por qué es todo esto relevante? Entre otros motivos, por el interés en entender este algoritmo, catboost, tan popular. Hay cosas escritas sobre él, como el tratamiento que hace de las variables categóricas, que no tienen sentido salvo que se entienda que se aplican a árboles olvidadizos y no a los habituales.