Potenciación de gradiente

El gradient boosting es una técnica de aprendizaje automático basada en boosting en un espacio funcional, donde el objetivo son los pseudoresiduos en lugar de los residuos como en el boosting tradicional. Proporciona un modelo de predicción en forma de un conjunto de modelos de predicción débiles, es decir, modelos que hacen muy pocas suposiciones sobre los datos, que son típicamente árboles de decisión simples . ^{[ 1 ] [ 2 ]} Cuando un árbol de decisión es el aprendiz débil, el algoritmo resultante se llama árboles potenciados por gradiente; generalmente supera al bosque aleatorio . ^{[ 1 ]} Al igual que con otros métodos de boosting , un modelo de árboles potenciados por gradiente se construye en etapas, pero generaliza los otros métodos al permitir la optimización de una función de pérdida diferenciable arbitraria .

La idea del gradient boosting se originó en la observación de Leo Breiman de que boosting puede interpretarse como un algoritmo de optimización sobre una función de coste adecuada. ^{[ 3 ]} Posteriormente, Jerome H. Friedman desarrolló algoritmos explícitos de gradient boosting de regresión , ^{[ 4 ] [ 2 ]} (en 1999 y más tarde en 2001) simultáneamente con la perspectiva más general del gradient boosting funcional de Llew Mason, Jonathan Baxter, Peter Bartlett y Marcus Frean. ^{[ 5 ] [ 6 ]} Los dos últimos artículos introdujeron la visión de los algoritmos de boosting como algoritmos iterativos de descenso de gradiente funcional . Es decir, algoritmos que optimizan una función de coste sobre el espacio de funciones eligiendo iterativamente una función (hipótesis débil) que apunta en la dirección del gradiente negativo. Esta visión del gradiente funcional del boosting ha llevado al desarrollo de algoritmos de boosting en muchas áreas del aprendizaje automático y la estadística más allá de la regresión y la clasificación.

(Esta sección sigue a la exposición de Cheng Li. ^{[ 7 ]} )

Al igual que otros métodos de boosting, el gradient boosting combina iterativamente "aprendices" débiles en un único aprendiz fuerte. Es más fácil de explicar en el contexto de la regresión por mínimos cuadrados , donde el objetivo es entrenar un modelo.${\displaystyle F}$para predecir valores de la forma${\displaystyle {\hat {y}}=F(x)}$minimizando el error cuadrático medio${\displaystyle {\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}}$, dónde${\displaystyle i}$índices sobre algún conjunto de entrenamiento de tamaño${\displaystyle n}$de valores reales de la variable de salida${\displaystyle y}$:

• ${\displaystyle {\sombrero {y}}_{i}=}$el valor previsto${\displaystyle F(x_{i})}$
• ${\displaystyle y_{i}=}$el valor observado
• ${\displaystyle n=}$el tamaño de la muestra, es decir, el número de observaciones en${\displaystyle y}$

Si el algoritmo tiene${\displaystyle M}$etapas, en cada etapa${\displaystyle m}$(${\displaystyle 1\leq m\leq M}$), supongamos algún modelo imperfecto${\displaystyle F_{m}}$(para bajo${\displaystyle m}$, este modelo puede simplemente predecir${\displaystyle {\sombrero {y}}_{i}}$ser ${\displaystyle {\bar {y}}}$, la media de${\displaystyle y}$). Para mejorar${\displaystyle F_{m}}$, nuestro algoritmo debería agregar algún nuevo estimador,${\displaystyle h_{m}(x)}$. De este modo,

${\displaystyle F_{m+1}(x_{i})=F_{m}(x_{i})+h_{m}(x_{i})=y_{i}}$

o, equivalentemente,

${\displaystyle h_{m}(x_{i})=y_{i}-F_{m}(x_{i}).}$

Por lo tanto, el aumento de gradiente se ajustará${\displaystyle h_{m}}$al residuo${\displaystyle y_{i}-F_{m}(x_{i})}$. Como en otras variantes de potenciación, cada${\displaystyle F_{m+1}}$intenta corregir los errores de su predecesor${\displaystyle F_{m}}$. Una generalización de esta idea a funciones de pérdida distintas del error cuadrático, y a problemas de clasificación y ordenación , se deriva de la observación de que los residuos${\displaystyle h_{m}(x_{i})}$para un modelo dado son proporcionales a los gradientes negativos de la función de pérdida de error cuadrático medio (MSE) (con respecto a${\displaystyle F(x_{i})}$):

${\displaystyle L_{\rm {MSE}}={\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-F(x_{i})\right)^{2}}$

${\displaystyle -{\frac {\partial L_{\rm {MSE}}}{\partial F(x_{i})}}={\frac {2}{n}}(y_{i}-F(x_{i}))={\frac {2}{n}}h_{m}(x_{i}).}$

Por lo tanto, el algoritmo de potenciación de gradiente podría generalizarse a un algoritmo de descenso de gradiente simplemente introduciendo una función de pérdida diferente y su gradiente.

Muchos problemas de aprendizaje supervisado involucran una variable de salida y y un vector de variables de entrada x , relacionadas entre sí con alguna distribución de probabilidad. El objetivo es encontrar alguna función${\displaystyle {\hat {F}}(x)}$que mejor se aproxima a la variable de salida a partir de los valores de las variables de entrada. Esto se formaliza introduciendo alguna función de pérdida.${\displaystyle L(y,F(x))}$y minimizándolo en la expectativa:

${\displaystyle {\hat {F}}=\operatorname {argmin} \limits _{F}\mathbb {E} _{x,y}[L(y,F(x))].}$

El método de potenciación de gradiente asume que y es un valor real . Busca una aproximación.${\displaystyle {\hat {F}}(x)}$en forma de una suma ponderada de M funciones${\displaystyle h_{m}(x)}$de alguna clase${\displaystyle {\mathcal {H}}}$, denominados aprendices base (o débiles ):

${\displaystyle {\hat {F}}(x)=\sum _{m=1}^{M}\gamma _{m}h_{m}(x)+{\mbox{const}},}$

dónde${\displaystyle \gamma _{m}}$es el peso en la etapa${\displaystyle m}$Normalmente se nos proporciona un conjunto de entrenamiento.${\displaystyle \{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$de valores conocidos de x y valores correspondientes de y . De acuerdo con el principio de minimización del riesgo empírico , el método intenta encontrar una aproximación.${\displaystyle {\hat {F}}(x)}$que minimiza el valor promedio de la función de pérdida en el conjunto de entrenamiento, es decir, minimiza el riesgo empírico. Lo hace comenzando con un modelo, que consiste en una función constante.${\displaystyle F_{0}(x)}$y lo expande gradualmente de forma voraz :

${\displaystyle F_{0}(x)={\underset {h_{m}\in {\mathcal {H}}}{\arg \min }}\sum _{i=1}^{n}{L(y_{i},h_{m}(x_{i}))},}$

${\displaystyle F_{m}(x)=F_{m-1}(x)+\left({\underset {h_{m}\in {\mathcal {H}}}{\operatorname {arg\,min} }}\left[\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))\right]\right)(x),}$

para${\displaystyle m\geq 1}$, dónde${\displaystyle h_{m}\in {\mathcal {H}}}$es una función de aprendizaje base.

Desafortunadamente, elegir la mejor función${\displaystyle h_{m}}$En cada paso para una función de pérdida arbitraria L, se trata en general de un problema de optimización computacionalmente inviable. Por lo tanto, restringimos nuestro enfoque a una versión simplificada del problema. La idea es aplicar un paso de descenso más pronunciado a este problema de minimización (descenso de gradiente funcional). La idea básica es encontrar un mínimo local de la función de pérdida iterando sobre${\displaystyle F_{m-1}(x)}$De hecho, la dirección de descenso del máximo local de la función de pérdida es el gradiente negativo. ^{[ 8 ]} Por lo tanto, mover una pequeña cantidad${\displaystyle \gamma }$de tal manera que la aproximación lineal siga siendo válida:

${\displaystyle F_{m}(x)=F_{m-1}(x)-\gamma \sum _{i=1}^{n}\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}$

dónde${\displaystyle \gamma >0}$Para pequeños${\displaystyle \gamma }$, esto implica que${\displaystyle L(y_{i},F_{m}(x_{i}))\leq L(y_{i},F_{m-1}(x_{i}))}$.

Además, podemos optimizar${\displaystyle \gamma }$al encontrar el${\displaystyle \gamma }$valor para el cual la función de pérdida tiene un mínimo:

${\displaystyle \gamma _{m}={\underset {\gamma }{\operatorname {argmin} }}\sum _{i=1}^{n}L(y_{i},F_{m}(x_{i}))={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}.}$

Si consideramos el caso continuo, es decir, donde${\displaystyle {\mathcal {H}}}$es el conjunto de funciones diferenciables arbitrarias en${\displaystyle \mathbb {R} }$, actualizaríamos el modelo de acuerdo con las siguientes ecuaciones

${\displaystyle F_{m}(x)=F_{m-1}(x)-\gamma _{m}\sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}}$

dónde${\displaystyle \gamma _{m}}$es la longitud del paso, definida como $${\displaystyle \gamma _{m}={\underset {\gamma }{\arg \min }}\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right).}$$ En el caso discreto, sin embargo, es decir, cuando el conjunto${\displaystyle {\mathcal {H}}}$es finito , elegimos la función candidata h más cercana al gradiente de L para la cual el coeficiente γ puede calcularse con la ayuda de una búsqueda lineal en las ecuaciones anteriores. Nótese que este enfoque es heurístico y, por lo tanto, no proporciona una solución exacta al problema dado, sino una aproximación. En pseudocódigo, el método genérico de potenciación de gradiente es: ^{[ 4 ] [ 1 ]}

El método de potenciación de gradiente se suele utilizar con árboles de decisión (especialmente CART ) de tamaño fijo como clasificadores base. Para este caso particular, Friedman propone una modificación del método de potenciación de gradiente que mejora la calidad del ajuste de cada clasificador base.

El aumento de gradiente genérico en el paso m se ajustaría a un árbol de decisión.${\displaystyle h_{m}(x)}$a pseudoresiduos. Dejemos${\displaystyle J_{m}}$sea ​​el número de sus hojas. El árbol divide el espacio de entrada en${\displaystyle J_{m}}$regiones disjuntas${\displaystyle R_{1m},\ldots ,R_{J_{m}m}}$y predice un valor constante en cada región. Usando la notación de indicadores , la salida de${\displaystyle h_{m}(x)}$para la entrada x se puede escribir como la suma:

${\displaystyle h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x),}$

dónde${\displaystyle b_{jm}}$es el valor previsto en la región${\displaystyle R_{jm}}$. ^{[ 9 ]}

Luego los coeficientes${\displaystyle b_{jm}}$se multiplican por algún valor${\displaystyle \gamma _{m}}$, elegido mediante búsqueda lineal para minimizar la función de pérdida, y el modelo se actualiza de la siguiente manera:

${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x),\quad \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})).}$

Friedman propone modificar este algoritmo para que elija un valor óptimo separado.${\displaystyle \gamma _{jm}}$para cada una de las regiones del árbol, en lugar de una sola${\displaystyle \gamma _{m}}$para todo el árbol. Llama al algoritmo modificado "TreeBoost". Los coeficientes${\displaystyle b_{jm}}$El procedimiento de ajuste de árbol se puede descartar simplemente y la regla de actualización del modelo queda así:

${\displaystyle F_{m}(x)=F_{m-1}(x)+\sum _{j=1}^{J_{m}}\gamma _{jm}\mathbf {1} _{R_{jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma ).}$

Cuando la pérdida${\displaystyle L(\cdot ,\cdot )}$es el error cuadrático medio (ECM) los coeficientes${\displaystyle \gamma _{jm}}$coinciden con los coeficientes del procedimiento de ajuste de árboles${\displaystyle b_{jm}}$.

Ajustar demasiado el conjunto de entrenamiento puede degradar la capacidad de generalización del modelo, es decir, su rendimiento con ejemplos no vistos. Varias técnicas de regularización reducen este efecto de sobreajuste al restringir el procedimiento de ajuste.

Un parámetro de regularización natural es el número de iteraciones de potenciación de gradiente M (es decir, el número de modelos base). Aumentar M reduce el error en el conjunto de entrenamiento, pero incrementa el riesgo de sobreajuste. El valor óptimo de M se suele seleccionar monitorizando el error de predicción en un conjunto de datos de validación independiente.

Otro parámetro de regularización para el boosting de árboles es la profundidad del árbol. Cuanto mayor sea este valor, mayor será la probabilidad de que el modelo se sobreajuste a los datos de entrenamiento.

El aumento de gradiente se puede utilizar en el campo del aprendizaje para la clasificación . Los motores de búsqueda web comerciales Yahoo ^{[ 16 ]} y Yandex ^{[ 17 ]} utilizan variantes de aumento de gradiente en sus motores de clasificación basados ​​en aprendizaje automático. El aumento de gradiente también se utiliza en física de altas energías en el análisis de datos. En el Gran Colisionador de Hadrones (LHC), las variantes de aumento de gradiente de redes neuronales profundas (DNN) lograron reproducir los resultados de métodos de análisis que no se basan en aprendizaje automático en conjuntos de datos utilizados para descubrir el bosón de Higgs . ^{[ 18 ]} El árbol de decisión de aumento de gradiente también se aplicó en estudios terrestres y geológicos, por ejemplo, en la evaluación de la calidad de un yacimiento de arenisca. ^{[ 19 ]}

El método recibe varios nombres. Friedman introdujo su técnica de regresión como una "Máquina de Impulso de Gradiente" (GBM). ^{[ 4 ]} Mason, Baxter et al. describieron la clase abstracta generalizada de algoritmos como "impulso de gradiente funcional". ^{[ 5 ] [ 6 ]} Friedman et al. describen un avance de los modelos de impulso de gradiente como Árboles de Regresión Aditiva Múltiple (MART); ^{[ 20 ]} Elith et al. describen ese enfoque como "Árboles de Regresión Impulsados" (BRT). ^{[ 21 ]}

Una implementación popular de código abierto para R la denomina "Modelo de Impulso Generalizado" ^{[ 12 ]} , sin embargo, los paquetes que amplían este trabajo utilizan BRT ^{[ 22 ]} . Otro nombre es TreeNet, en honor a una implementación comercial temprana de Dan Steinberg, de Salford Systems, uno de los investigadores pioneros en el uso de métodos basados ​​en árboles ^{[ 23 ] .}

El aumento de gradiente se puede utilizar para la clasificación de la importancia de las características, que generalmente se basa en la agregación de la función de importancia de los aprendices base. ^{[ 24 ]} Por ejemplo, si se desarrolla un algoritmo de árboles de aumento de gradiente utilizando árboles de decisión basados ​​en entropía , el algoritmo de conjunto clasifica la importancia de las características también en función de la entropía, con la salvedad de que se promedia sobre todos los aprendices base. ^{[ 24 ] [ 1 ]}

Si bien el boosting puede aumentar la precisión de un aprendiz base, como un árbol de decisión o una regresión lineal, sacrifica la inteligibilidad y la interpretabilidad . ^{[ 24 ] [ 25 ]} Por ejemplo, seguir la ruta que toma un árbol de decisión para tomar su decisión es trivial y autoexplicativo, pero seguir las rutas de cientos o miles de árboles es mucho más difícil. Para lograr tanto rendimiento como interpretabilidad, algunas técnicas de compresión de modelos permiten transformar un XGBoost en un único árbol de decisión "renacido" que aproxima la misma función de decisión. ^{[ 26 ]} Además, su implementación puede ser más difícil debido a la mayor demanda computacional.

• AdaBoost
• Bosque aleatorio
• Catboost
• LightGBM
• XGBoost
• Aprendizaje mediante árboles de decisión

• Boehmke, Bradley; Greenwell, Brandon (2019). «Gradient Boosting». Hands-On Machine Learning with R. Chapman & Hall. pp. 221–245 . ISBN  978-1-138-49568-5.

• Cómo explicar el aumento de gradiente
• Árboles de regresión potenciados por gradiente
• LightGBM