4.4 Boosting
La metodología boosting es una metodología general de aprendizaje lento en la que se combinan muchos modelos obtenidos mediante un método con poca capacidad predictiva para, impulsados, dar lugar a un mejor predictor. Los árboles de decisión pequeños (construidos con poca profundidad) resultan perfectos para esta tarea, al ser realmente malos predictores (weak learners), fáciles de combinar y generarse de forma muy rápida.
El boosting nació en el contexto de los problemas de clasificación y tardó varios años en poderse extender a los problemas de regresión. Por ese motivo vamos a empezar viendo el boosting en clasificación.
La idea del boosting la desarrollaron Valiant (1984) y Kearns y Valiant (1994), pero encontrar una implementación efectiva fue una tarea difícil que no se resolvió satisfactoriamente hasta que Freund y Schapire (1996) presentaron el algoritmo AdaBoost, que rápidamente se convirtió en un éxito.
Veamos, de forma muy esquemática, en que consiste el algoritmo AdaBoost para un problema de clasificación en el que solo hay dos categorías y en el que se utiliza como clasificador débil un árbol de decisión con pocos nodos terminales, solo marginalmente superior a un clasificador aleatorio. En este caso, resulta más cómodo recodificar la variable indicadora \(Y\) como \(1\) si éxito y \(-1\) si fracaso.
Seleccionar \(B\), número de iteraciones.
Se les asigna el mismo peso a todas las observaciones de la muestra de entrenamiento (\(1/n\)).
Para \(b = 1, 2,\ldots, B\), repetir:
Ajustar el árbol utilizando las observaciones ponderadas.
Calcular la proporción de errores en la clasificación \(e_b\).
Calcular \(s_b = \text{log}((1 - e_b)/e_b)\).
Actualizar los pesos de las observaciones. Los pesos de las observaciones correctamente clasificadas no cambian; se les da más peso a las observaciones incorrectamente clasificadas, multiplicando su peso anterior por \((1 - e_b)/e_b\).
Dada una observación \(\mathbf{x}\), si denotamos por \(\hat y_b ( \mathbf{x} )\) su clasificación utilizando el árbol \(b\)-ésimo, entonces \(\hat y( \mathbf{x} ) = signo \left( \sum_b s_b \hat y_b ( \mathbf{x} ) \right)\) (si la suma es positiva, se clasifica la observación como perteneciente a la clase \(+1\); en caso contrario, a la clase \(-1\)).
Vemos que el algoritmo AdaBoost no combina árboles independientes (como sería el caso de los bosques aleatorios, por ejemplo), sino que estos se van generando en una secuencia en la que cada árbol depende del anterior. Se utiliza siempre el mismo conjunto de datos (de entrenamiento), pero a estos datos se les van poniendo unos pesos en cada iteración que dependen de lo que ha ocurrido en la iteración anterior: se les da más peso a las observaciones mal clasificadas para que en sucesivas iteraciones se clasifiquen bien. Finalmente, la combinación de los árboles se hace mediante una suma ponderada de las \(B\) clasificaciones realizadas. Los pesos de esta suma son los valores \(s_b\). Un árbol que clasifique de forma aleatoria \(e_b = 0.5\) va a tener un peso \(s_b = 0\) y cuanto mejor clasifique el árbol mayor será su peso. Al estar utilizando clasificadores débiles (árboles pequeños) es de esperar que los pesos sean en general próximos a cero.
El siguiente hito fue la aparición del método gradient boosting machine (Friedman, 2001), perteneciente a la familia de los métodos iterativos de descenso de gradientes. Entre otras muchas ventajas, este método permitió resolver no solo problemas de clasificación, sino también de regresión; y permitió la conexión con lo que se estaba haciendo en otros campos próximos como pueden ser los modelos aditivos o la regresión logística. La idea es encontrar un modelo aditivo que minimice una función de pérdida utilizando predictores débiles (por ejemplo árboles).
Se desea minimizar la función de pérdidas mediante el método de los gradientes, algo fácil de hacer si esta función es diferenciable. Si se utiliza RSS, entonces la pérdida de emplear \(m(x)\) para predecir \(y\) en los datos de entrenamiento es \[L(m) = \sum_{i=1}^n L(y_i, m(x_i)) = \sum_{i=1}^n \frac{1}{2} (y_i - m(x_i))^2\] y los gradientes serían precisamente los residuos, ya que \[- \frac{\partial L(y_i, m(x_i))} {\partial m(x_i)} = y_i - m(x_i) = r_i\] Una ventaja de esta aproximación es que puede extenderse a otras funciones de pérdida; por ejemplo, si hay valores atípicos se puede considerar como función de pérdida el error absoluto.
Veamos a continuación el algoritmo para un problema de regresión utilizando árboles de decisión. Es un proceso iterativo en el que lo que se ataca no son los datos directamente, sino los residuos (gradientes) que van quedando con los sucesivos ajustes, siguiendo una idea greedy (la optimización se resuelve en cada iteración, no globalmente).
Seleccionar el número de iteraciones \(B\), el parámetro de regularización \(\lambda\) y el número de cortes de cada árbol \(d\).
Establecer una predicción inicial constante y calcular los residuos de los datos \(i\) de la muestra de entrenamiento: \[\hat m (x) = 0, \ r_i = y_i\]
Para \(b = 1, 2,\ldots, B\), repetir:
Ajustar un árbol de regresión \(\hat m^b\) con \(d\) cortes utilizando los residuos como respuesta: \((X, r)\).
Calcular la versión regularizada del árbol: \[\lambda \hat m^b (x)\]
Actualizar los residuos: \[r_i \leftarrow r_i - \lambda \hat m^b (x_i)\]
Calcular el modelo boosting: \[\hat m (x) = \sum_{b=1}^{B} \lambda \hat m^b (x)\]
Comprobamos que este método depende de tres hiperparámetros: \(B\), \(d\) y \(\lambda\), susceptibles de ser seleccionados de forma óptima:
\(B\) es el número de árboles. Un valor muy grande podría llegar a provocar un sobreajuste (algo que no ocurre ni con bagging ni con bosques aleatorios, ya que estos son métodos en los que se construyen árboles independientes). En cada iteración, el objetivo es ajustar de forma óptima el gradiente (en nuestro caso, los residuos), pero este enfoque greedy no garantiza el óptimo global y puede dar lugar a sobreajustes.
Al ser necesario que el aprendizaje sea lento, se utilizan árboles muy pequeños. Esto consigue que poco a poco se vayan cubriendo las zonas en las que es más difícil predecir bien. En muchas situaciones funciona bien utilizar \(d = 1\), es decir, con un único corte. En este caso, en cada \(\hat m^b\) interviene una única variable y por tanto \(\hat m\) es un ajuste de un modelo aditivo. Si \(d>1\) se puede interpretar como un parámetro que mide el orden de interacción entre las variables.
\(\lambda\) es el parámetro de regularización, \(0 < \lambda < 1\). Las primeras versiones del algoritmo utilizaban \(\lambda = 1\), pero no funcionaba bien del todo. Se mejoró mucho el rendimiento ralentizando aún más el aprendizaje al incorporar al modelo el parámetro \(\lambda\), que se puede interpretar como una proporción de aprendizaje (la velocidad a la que aprende, learning rate). Valores pequeños de \(\lambda\) evitan el problema del sobreajuste, siendo habitual utilizar \(\lambda = 0.01\) o \(\lambda = 0.001\). Como ya se ha dicho, lo ideal es seleccionar su valor utilizando, por ejemplo, validación cruzada. Por supuesto, cuanto más pequeño sea el valor de \(\lambda\), más lento va a ser el proceso de aprendizaje y serán necesarias más iteraciones, lo cual incrementa los tiempos de cómputo.
El propio Friedman propuso una mejora de su algoritmo (Friedman, 2002), inspirado por la técnica bagging de Breiman. Esta variante, conocida como stochastic gradient boosting (SGB), es a día de hoy una de las más utilizadas.
La única diferencia respecto al algoritmo anterior se encuentra en la primera línea dentro del bucle: al hacer el ajuste de \((X, r)\), no se considera toda la muestra de entrenamiento, sino que se selecciona al azar un subconjunto.
Esto incorpora un nuevo hiperparámetro a la metodología, la fracción de datos utilizada.
Lo ideal es seleccionar un valor por algún método automático (tunearlo) tipo validación cruzada; una selección manual típica es 0.5.
Hay otras variantes, como por ejemplo la selección aleatoria de predictores antes de crecer cada árbol o antes de cada corte (ver por ejemplo la documentación de h2o::gbm).
Este sería un ejemplo de un método con muchos hiperparámetros y diseñar una buena estrategia para ajustarlos (tunearlos) puede resultar mucho más complicado (puede haber problemas de mínimos locales, problemas computacionales, etc.).
SGB ofrece dos ventajas importantes: reduce la varianza y reduce los tiempos de cómputo. En terminos de rendimiento, tanto el método SGB como random forest son muy competitivos y, por tanto, son muy utilizados en la práctica. Los bosques aleatorios tienen la ventaja de que, al construir árboles de forma independiente, es paralelizable y eso puede reducir los tiempos de cómputo.
Otro método reciente que está ganando popularidad es extreme gradient boosting, también conocido como XGBoost (Chen y Guestrin, 2016). Es un método más complejo que el anterior; entre otras modificaciones, utiliza una función de pérdida con una penalización por complejidad y, para evitar el sobreajuste, regulariza utilizando la hessiana de la función de pérdida (necesita calcular las derivadas parciales de primer y de segundo orden), e incorpora parámetros de regularización adicionales para evitar el sobreajuste.
Por último, la importancia de las variables se puede medir de forma similar a lo que ya hemos visto en otros métodos: dentro de cada árbol se suman las reducciones del error que consigue cada predictor, y se promedia entre todos los árboles utilizados.
En resumen:
La idea es hacer un aprendizaje lento (gradual).
Los arboles se crecen de forma secuencial: se trata de mejorar la clasificación anterior.
Se utilizan arboles pequeños.
A diferencia de bagging y bosques aleatorios, puede haber problemas de sobreajuste, especialmente si el número de árboles es grande y la tasa de aprendizaje es alta.
Se puede pensar como una ponderación iterativa de las observaciones, asignando más peso a aquellas que resultaron más difíciles de clasificar.
El modelo final es un modelo aditivo: es la media ponderada de los árboles.