3.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 sólo hay dos categorías y en el que se utiliza como clasificador débil un árbol de decisión con pocos nodos terminales, sólo 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 á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 cuando 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 sólo 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 perdida utilizando predictores débiles (por ejemplo árboles).
Si como función de pérdida se utiliza RSS, entonces la pérdida de utilizar \(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 (y_i - m(x_i))^2\]
Se desea minimizar \(L(m)\) con respecto a \(m\) mediante el método de los gradientes, pero estos son precisamente los residuos: si \(L(m)= \frac{1}{2} (y_i - m(x_i))^2\), entonces \[- \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 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 3 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 órden de interacción entre las variables.
\(0 < \lambda < 1\), parámetro de regularización. Las primeras versiones del algorimo utilizaban un \(\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 es 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 que se utiliza de los datos.
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 incorpora 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 utilizando 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 metodo más complejo que el anterior que, 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 sumas 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”.
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 (si el número de árboles es grande y la tasa de aprendizaje es alta).
Se puede pensar que se ponderan las observaciones iterativamente, se asigna más peso a las que resultaron más difíciles de clasificar.
El modelo final es un modelo aditivo (media ponderada de los árboles).