Las técnicas de ensamble estiman el target \(y\) con una suma de \(M\) estimadores base \(b\) que dependen de \(\mathbf{x} \in \mathbb{R}^p\) tal que para cada observación \(i\):
\[\hat{y}_i = f(\mathbf{x}_i) = \sum_{m=1}^{M} b_m(\mathbf{x}_i)\]
En boosting en particular, los modelos \(b_m\) son modelos “débiles” (weak learners) que se entrenan secuencialmente con versiones continuamente alteradas de los datos, de modo que la predicción general vaya mejorando lentamente en áreas donde no ajusta bien. Los modelos son débiles en el sentido en que son simples y reducen la pérdida \(J\) en una magnitud levemente por encima de lo que lo haría una estimación al azar. Es necesario que sean poco complejos para evitar el sobreajuste.
El problema de optimización general
\[\min J(y,\hat{y}) = J(y,\sum_{m=1}^{M} b_m(\mathbf{x}_i))\]
se resuelve en boosting mediante una simplificación: en cada iteración \(m\) se resuelve el problema más simple
\[\min J(y,b_m(\mathbf{x}))\]
Es decir que en cada iteración se ajusta el estimador base \(b_m\) y se agrega a la estimación general \(f(\mathbf{x})\) tomando como dadas las estimaciones anteriores –los \(b_m\) no se modifican una vez que se pasa a las iteraciones subsiguientes. Esta solución se conoce como forward stagewise additive modeling.
Si la primera ronda de boosting comienza en \(m=1\), decimos entonces que \(f\) se inicializa con un valor constante \(b_0\) tal que \(b_0 = \arg\min_b J(y,b)\) –es decir, se usa la constante que minimiza la pérdida en las instancias de entrenamiento (por ejemplo, la media de \(y\) cuando la función de pérdida es el error cuadrático medio).
La técnica de gradient boosting ajusta la función \(f\) usando descenso por el gradiente en el espacio funcional.
En el caso más tradicional de descenso por el gradiente, el descenso se hace en el espacio de los parámetros. Por ejemplo, si la predicción \(\hat{y}=f(\mathbf{x},\mathbf{\theta})\) dependiera de un vector de parámetros \(\mathbf{\theta} \in \mathbb{R}^p\), se puede ajustar \(f\) ajustando \(\mathbf{\theta}\) secuencialmente desciendendo por el gradiente de la pérdida \(J\) con respecto a \(\theta\):
\[ \mathbf{\theta}^{(m)} = \mathbf{\theta}^{(m-1)} - \eta \frac{\partial J}{\partial \mathbf{\theta}^{(m-1)}} \]
donde \(\eta\) representa la tasa de aprendizaje –es decir, el tamaño del ajuste que se realiza en la dirección del gradiente– y \(\theta\) se inicializa en valores al azar. Desde luego, la forma específica que tome la derivada \(\frac{\partial J}{\partial \mathbf{\theta}^{(m)}}\) dependerá de la función de pérdida elegida –que asumimos es diferenciable con respecto a \(\mathbf{\theta}\)– y de la forma de \(f(\mathbf{x},\mathbf{\theta})\). El vector \(\mathbf{\theta}\) que se obtiene luego de las \(M\) iteraciones puede usarse para predecir \(y\) cualquier set de observaciones.
Es posible usar descenso por el gradiente en el espacio de los parámetros solamente para ciertas configuraciones del problema –por ejemplo, si \(f\) fuera una proyección lineal \(f(\mathbf{x},\mathbf{\theta})=\mathbf{x}^T\mathbf{\theta}\).
En algunos contextos esto no es posible y podemos recurrir al descenso por el gradiente en el espacio funcional: el objetivo \(J\) se optimiza secuencialmente usando el gradiente de \(J\) con respecto a las predicciones \(\hat{y}\) tal que:
\[ \hat{y}^{(m)} = \hat{y}^{(m-1)} - \eta \frac{\partial J}{\partial \hat{y}^{(m-1)}} \]
donde \(\hat{y}\) se iniciliza en valores al azar.
Sin embargo esta forma de descender por el gradiente no devuelve ninguna forma funcional que se pueda aplicar a nuevas observaciones. Solo nos permite obtener predicciones \(\hat{y}_i\) para las mismas observaciones \(i\) con las que se realiza la optimización. De hecho, lo único que estamos haciendo es corregir \(\hat{y}\) iterativamente para que se acerque a \(y\), haciendo tender la pérdida a 0 en los datos de entrenamiento.
Este problema se puede resolver de la siguiente manera:
En lugar de actualizar las predicciones con el verdadero valor del gradiente según las datos de entrenamiento, se puede entrenar un modelo en cada iteración que estime esta dirección. Estos modelos son los estimadores base \(b_m\) de boosting.
Definiendo \(r^{(m-1)}=-\frac{\partial J}{\partial \hat{y}^{(m-1)}}\) podemos redefinir la ecuación de ajuste como:
\[ \hat{y}^{(m)} = \hat{y}^{(m-1)} + \eta b_m(\mathbf{x}) \]
donde cada estimador \(b_m\) de aprende un mapping de \({\mathbf{x}}\) hacia \(r^{(m-1)}\). La magnitud de las predicciones de \(b_m\) en cada iteración dependerá entonces de la magnitud de los gradientes \(r^{(m-1)}\) durante el entrenamiento, que decrece tendencialmente a medida que crece \(m\). De hecho, los gradientes negativos \(r\) pueden entenderse como residuos generalizados entre \(y\) y \(\hat{y}\) que aplican a cualquier función de pérdida.
Este abordaje nos permite usar boosting con estimadores base CART y con cualquier función de pérdida diferenciable. En particular, podemos usar funciones de pérdida robustas a observaciones atípicas (como la deviance o log-loss en el contexto de clasificación, o absolute loss para regresión). La inducción de árboles es particularmente difícil para estas funciones de pérdida, y justamente la motivación del gradient boosting es superar esta dificultad.
Los Gradient Boosted Trees usan CART como estimadores base para resolver un problema de optimización con gradient boosting. Los CART particionan el espacio de los predictores \(\mathbf{x}\) en \(T\) regiones disjuntas \(R_t\) –las hojas–, y le asignan a cada una un score \(w_t\). De esta manera se genera una predicción para \(y\) según la regla
\[ \hat{y} = tree(\mathbf{x},\theta) = \sum_{t=1}^{T} w_tI(\mathbf{x} \in R_t) \]
Se puede definir el conjunto de parámetros a estimar durante el ajuste del modelo como \(\theta = \{R_t,w_t\}_{t=1}^T\). Es decir, es necesario definir (a) qué variables usar para particionar el espacio, (b) con qué puntos de corte y (c) qué score asignar a cada región del espacio. En particular buscamos encontrar \(\theta\) tal que se minimice la pérdida \(J\) en los datos de entrenamiento.
Desde luego se trata un problema complejo que requiere recorrer muchas soluciones posibles para encontrar la óptima, sobre todo cuando el número de predictores \(p\) es muy alto. La estrategia subóptima que usa CART es un algoritmo greedy que va particionando el espacio recursivamente usando las variables con los puntos de corte que optimizan algún criterio adecuado de pérdida –el índice Gini para problemas de clasficación o la suma de residuos al cuadrado para regresión, por ejemplo.
Dadas las regiones \(R_t\), en cada una se computa un score constante \(w_t\) según
\[ w_t = \arg\min_w \sum_{\mathbf{x} \in R_t} J(y,w) \]
de modo tal de minimizar la función de pérdida acorde al problema para las observaciones que pertenecen a la región.
En el contexto de boosting se ajustan \(M\) CARTs \(b_m = tree_m\), que al sumarse dan lugar a la predicción final para cada observación \(i\):
\[\hat{y}_i = f(\mathbf{x}_i) = \sum_{m=1}^{M} tree_m(\mathbf{x}_i, \theta_m)\]
Al tratarse de gradient boosting, los parámetros de cada \(tree_m\) se ajustan para predecir los residuos generalizados \(r\) de la iteración anterior. Una vez ajustado \(tree_m\), la predicción \(\hat{y}\) se corrige según la regla \(\hat{y}^{(m)} = \hat{y}^{(m-1)} + \eta tree_{m}\).