Aumento de gradiente - Gradient boosting

Parte de una serie sobre
Aprendizaje automático y minería de datos
Problemas Clasificación Agrupación Regresión Detección de anomalías Limpieza de datos AutoML reglas de asociación Aprendizaje reforzado Predicción estructurada Ingeniería de características Aprendizaje de funciones Aprender en línea Aprendizaje semi-supervisado Aprendizaje sin supervisión Aprendiendo a clasificar Inducción gramatical
Aprendizaje supervisado ( clasificación  • regresión ) Árboles de decisión Conjuntos Harpillera Impulsando Bosque aleatorio k -NN Regresión lineal Bayes ingenuo Redes neuronales artificiales Regresión logística Perceptrón Máquina de vectores de relevancia (RVM) Máquina de vectores de soporte (SVM)
Agrupación ABEDUL CURA Jerárquico k -significa Expectativa-maximización (EM) DBSCAN ÓPTICA Cambio medio
Reducción de dimensionalidad Análisis factorial CCA ICA LDA NMF PCA PGD t-SNE
Predicción estructurada Modelos graficos Red de Bayes Campo aleatorio condicional Markov oculto
Detección de anomalías k -NN Factor de valor atípico local
Red neuronal artificial Autoencoder Computación cognitiva Aprendizaje profundo DeepDream Perceptrón multicapa RNN LSTM GRU ESN Máquina de Boltzmann restringida GAN SOM Red neuronal convolucional U-Net Transformador Red neuronal en aumento Memtransistor RAM electroquímica (ECRAM)
Aprendizaje reforzado Q-aprendizaje SARSA Diferencia temporal (TD)
Teoría Compensación entre sesgo y varianza Teoría del aprendizaje computacional Minimización de riesgos empíricos Aprendizaje de Occam Aprendizaje PAC Aprendizaje estadístico Teoría de VC
Lugares de aprendizaje automático NeurIPS ICML ML JMLR ArXiv: cs.LG
Artículos relacionados Glosario de inteligencia artificial Lista de conjuntos de datos para la investigación de aprendizaje automático Esquema del aprendizaje automático
v t mi

El aumento de gradiente es una técnica de aprendizaje automático para regresión , clasificación y otras tareas, que produce un modelo de predicción en forma de un conjunto de modelos de predicción débiles, generalmente árboles de decisión . Cuando un árbol de decisión es el alumno débil, el algoritmo resultante se denomina árboles potenciados por gradiente, que generalmente supera al bosque aleatorio . Construye el modelo por etapas como lo hacen otros métodos de impulso , y los generaliza al permitir la optimización de una función de pérdida diferenciable arbitraria .

Historia

La idea del aumento de gradiente se originó en la observación de Leo Breiman de que el impulso se puede interpretar como un algoritmo de optimización en una función de costo adecuada. Jerome H. Friedman desarrolló posteriormente algoritmos de impulso de gradiente de regresión explícita , simultáneamente con la perspectiva más general de impulso de gradiente funcional de Llew Mason, Jonathan Baxter, Peter Bartlett y Marcus Frean. Los dos últimos artículos introdujeron la visión de impulsar los algoritmos como algoritmos iterativos de descenso de gradientes funcionales . Es decir, algoritmos que optimizan una función de costo sobre el espacio funcional eligiendo iterativamente una función (hipótesis débil) que apunta en la dirección del gradiente negativo. Esta vista de gradiente funcional del impulso ha llevado al desarrollo de algoritmos de impulso en muchas áreas del aprendizaje automático y las estadísticas más allá de la regresión y la clasificación.

Introducción informal

(Esta sección sigue la exposición del aumento de gradiente por Li).

Al igual que otros métodos de refuerzo, el refuerzo de gradiente combina "aprendices" débiles en un único alumno fuerte de forma iterativa. Es más fácil de explicar en la configuración de regresión de mínimos cuadrados , donde el objetivo es "enseñar" a un modelo a predecir los valores de la forma minimizando el error cuadrático medio , donde los índices sobre algún conjunto de entrenamiento del tamaño de los valores reales de la salida variable : ${\ Displaystyle F}$${\ Displaystyle {\ hat {y}} = F (x)}$ ${\ Displaystyle {\ tfrac {1} {n}} \ sum _ {i} ({\ hat {y}} _ {i} -y_ {i}) ^ {2}}$${\ Displaystyle i}$${\ Displaystyle n}$${\ Displaystyle y}$

• ${\ Displaystyle {\ hat {y}} _ {i} =}$ el valor predicho ${\ Displaystyle F (x)}$
• ${\ Displaystyle y_ {i} =}$ el valor observado
• ${\ Displaystyle n}$ el número de muestras en ${\ Displaystyle y}$

Ahora, consideremos un algoritmo de aumento de gradiente con etapas. En cada etapa ( ) de aumento de gradiente, suponga algún modelo imperfecto (para bajo , este modelo simplemente puede regresar , donde el RHS es la media de ). Con el fin de mejorar , nuestro algoritmo debe agregar algo nuevo estimador, . Por lo tanto, ${\ Displaystyle M}$${\ Displaystyle m}$${\ Displaystyle 1 \ leq m \ leq M}$${\ Displaystyle F_ {m}}$${\ Displaystyle m}$${\ Displaystyle {\ hat {y}} _ {i} = {\ bar {y}}}$${\ Displaystyle y}$${\ Displaystyle F_ {m}}$${\ Displaystyle h_ {m} (x)}$

${\ Displaystyle F_ {m + 1} (x) = F_ {m} (x) + h_ {m} (x) = y}$

o equivalente,

${\ Displaystyle h_ {m} (x) = y-F_ {m} (x)}$.

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

${\ Displaystyle L _ {\ rm {MSE}} = {\ frac {1} {n}} \ left (yF (x) \ right) ^ {2}}$

${\ Displaystyle - {\ frac {\ parcial L _ {\ rm {MSE}}} {\ parcial F}} = {\ frac {2} {n}} (yF (x)) = {\ frac {2} { n}} h_ {m} (x)}$.

Por lo tanto, el aumento de gradiente podría especializarse en un algoritmo de descenso de gradiente , y generalizarlo implica "conectar" una pérdida diferente y su gradiente.

Algoritmo

En muchos problemas de aprendizaje supervisado hay una variable de salida y y un vector de variables de entrada x , relacionados entre sí con alguna distribución probabilística. El objetivo es encontrar alguna función que se aproxime mejor 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 y minimizándola: ${\ Displaystyle {\ hat {F}} (x)}$ ${\ Displaystyle L (y, F (x))}$

${\ Displaystyle {\ hat {F}} = {\ underset {F} {\ arg \ min}} \, \ mathbb {E} _ {x, y} [L (y, F (x))]}$.

El método del gradiente impulsar asume un valor real- Y y busca una aproximación en forma de una suma ponderada de las funciones de alguna clase , llamada base (o débil ) alumnos: ${\ Displaystyle {\ hat {F}} (x)}$${\ Displaystyle h_ {i} (x)}$${\ Displaystyle {\ mathcal {H}}}$

${\ Displaystyle {\ hat {F}} (x) = \ sum _ {i = 1} ^ {M} \ gamma _ {i} h_ {i} (x) + {\ mbox {const}}}$.

Por lo general, se nos proporciona un conjunto de entrenamiento de valores muestrales conocidos de x y los valores correspondientes de y . De acuerdo con el principio de minimización del riesgo empírico , el método intenta encontrar una aproximación que minimice el valor promedio de la función de pérdida en el conjunto de entrenamiento, es decir, minimice el riesgo empírico. Lo hace comenzando con un modelo, que consta de una función constante , y lo expande incrementalmente de una manera codiciosa : ${\ Displaystyle \ {(x_ {1}, y_ {1}), \ dots, (x_ {n}, y_ {n}) \}}$${\ Displaystyle {\ hat {F}} (x)}$${\ Displaystyle F_ {0} (x)}$

${\ Displaystyle F_ {0} (x) = {\ underset {\ gamma} {\ arg \ min}} {\ sum _ {i = 1} ^ {n} {L (y_ {i}, \ gamma)} }}$,

${\ Displaystyle F_ {m} (x) = F_ {m-1} (x) + {\ 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}))}} \Derecha]}$,

donde es una función de aprendizaje base. ${\ Displaystyle h_ {m} \ in {\ mathcal {H}}}$

Desafortunadamente, elegir la mejor función h en cada paso para una función de pérdida arbitraria L es un problema de optimización computacionalmente inviable en general. 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 funcional del gradiente).

La idea básica detrás del descenso más empinado es encontrar un mínimo local de la función de pérdida iterando en . De hecho, se puede demostrar que la dirección de descenso máximo (derivada negativa más fuerte) de la función de pérdida al mínimo local a lo largo de es la función en sí misma sustraída por el gradiente de la función de pérdida en sí. Por eso: ${\ Displaystyle F_ {m} (x)}$${\ Displaystyle F_ {m} (x)}$

${\ 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}))}}$

Donde . Esto implica: . ${\ Displaystyle \ gamma> 0}$${\ Displaystyle L (y_ {i}, F_ {m} (x_ {i})) \ leq L (y_ {i}, F_ {m-1} (x_ {i}))}$

Además, podemos optimizar encontrando el valor para el cual la Función de Pérdida tiene un mínimo: ${\ Displaystyle \ gamma}$${\ Displaystyle \ gamma}$

${\ Displaystyle \ gamma _ {m} = {\ underset {\ gamma} {\ arg \ min}} {\ sum _ {i = 1} ^ {n} {L \ left (y_ {i}, F_ {m }) \ right)}} = {\ 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 consideráramos el caso continuo, es decir, dónde está el conjunto de funciones diferenciables arbitrarias , actualizaríamos el modelo de acuerdo con las siguientes ecuaciones ${\ Displaystyle {\ mathcal {H}}}$${\ Displaystyle \ mathbb {R}}$

${\ 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} = {\ 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)}},}$$

donde las derivadas se toman con respecto a las funciones para , y es la longitud del paso. Sin embargo, en el caso discreto, es decir, cuando el conjunto 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 la búsqueda de líneas en las ecuaciones anteriores. Tenga en cuenta que este enfoque es heurístico y, por lo tanto, no produce una solución exacta al problema dado, sino más bien una aproximación. En pseudocódigo, el método genérico de aumento de gradiente es: ${\ Displaystyle F_ {i}}$${\ Displaystyle i \ in \ {1, .., m \}}$${\ Displaystyle \ gamma _ {m}}$${\ Displaystyle {\ mathcal {H}}}$

Aumento del árbol de degradado

El aumento de gradiente se usa típicamente con árboles de decisión (especialmente árboles CART ) de un tamaño fijo como aprendices base. Para este caso especial, Friedman propone una modificación al método de aumento de gradiente que mejora la calidad de ajuste de cada alumno base.

El aumento de gradiente genérico en el m -ésimo paso encajaría un árbol de decisión en pseudo-residuales. Sea el número de sus hojas. El árbol divide el espacio de entrada en regiones separadas y predice un valor constante en cada región. Usando la notación del indicador , la salida de para la entrada x se puede escribir como la suma: ${\ Displaystyle h_ {m} (x)}$${\ Displaystyle J_ {m}}$${\ Displaystyle J_ {m}}$${\ Displaystyle R_ {1m}, \ ldots, R_ {J_ {m} m}}$${\ Displaystyle h_ {m} (x)}$

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

donde es el valor predicho en la región . ${\ Displaystyle b_ {jm}}$${\ Displaystyle R_ {jm}}$

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

${\ 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 para cada una de las regiones del árbol, en lugar de uno solo para todo el árbol. Él llama al algoritmo modificado "TreeBoost". Los coeficientes del procedimiento de ajuste de árbol pueden simplemente descartarse y la regla de actualización del modelo se convierte en: ${\ Displaystyle \ gamma _ {jm}}$${\ Displaystyle \ gamma _ {m}}$${\ Displaystyle b_ {jm}}$

${\ 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).}$

Tamaño de los árboles

${\ Displaystyle J}$, el número de nodos terminales en los árboles, es el parámetro del método que se puede ajustar para un conjunto de datos disponible. Controla el nivel máximo permitido de interacción entre variables en el modelo. Con ( tocones de decisión ), no se permite la interacción entre variables. Con el modelo se pueden incluir efectos de la interacción entre hasta dos variables, etc. ${\ Displaystyle J = 2}$${\ Displaystyle J = 3}$

Hastie y col. comentario que normalmente funciona bien para impulsar y los resultados son bastante insensibles a la elección de este rango, es insuficiente para muchas aplicaciones y es poco probable que sea necesario. ${\ Displaystyle 4 \ leq J \ leq 8}$${\ Displaystyle J}$${\ Displaystyle J = 2}$${\ Displaystyle J> 10}$

Regularización

Ajustar el conjunto de entrenamiento demasiado de cerca puede conducir a la degradación de la capacidad de generalización del modelo. Varias de las denominadas 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 aumento de gradiente M (es decir, el número de árboles en el modelo cuando el alumno base es un árbol de decisiones). Aumentar M reduce el error en el conjunto de entrenamiento, pero establecerlo demasiado alto puede provocar un sobreajuste. A menudo, se selecciona un valor óptimo de M supervisando el error de predicción en un conjunto de datos de validación separado. Además de controlar M , se utilizan varias otras técnicas de regularización.

Otro parámetro de regularización es la profundidad de los árboles. Cuanto mayor sea este valor, más probable es que el modelo se sobreajuste a los datos de entrenamiento.

Contracción

Una parte importante del método de aumento de gradiente es la regularización por contracción, que consiste en modificar la regla de actualización de la siguiente manera:

${\ Displaystyle F_ {m} (x) = F_ {m-1} (x) + \ nu \ cdot \ gamma _ {m} h_ {m} (x), \ quad 0 <\ nu \ leq 1,}$

donde el parámetro se denomina "tasa de aprendizaje". ${\ Displaystyle \ nu}$

Empíricamente se ha encontrado que el uso de pequeñas tasas de aprendizaje (como ) produce mejoras dramáticas en la capacidad de generalización de los modelos sobre el aumento de gradiente sin contraerse ( ). Sin embargo, tiene el precio de aumentar el tiempo de cálculo tanto durante el entrenamiento como durante las consultas : una tasa de aprendizaje más baja requiere más iteraciones. ${\ Displaystyle \ nu <0,1}$${\ Displaystyle \ nu = 1}$

Impulso del gradiente estocástico

Poco después de la introducción de gradiente de impulsar, Friedman propuso una modificación menor para el algoritmo, motivado por Breiman 's agregación bootstrap método ( 'ensacado'). Específicamente, propuso que en cada iteración del algoritmo, un alumno base debería encajar en una submuestra del conjunto de entrenamiento extraído al azar sin reemplazo. Friedman observó una mejora sustancial en la precisión del aumento de gradiente con esta modificación.

El tamaño de la submuestra es una fracción constante del tamaño del conjunto de entrenamiento. Cuando , el algoritmo es determinista e idéntico al descrito anteriormente. Los valores más pequeños de introducen aleatoriedad en el algoritmo y ayudan a prevenir el sobreajuste , actuando como una especie de regularización . El algoritmo también se vuelve más rápido, porque los árboles de regresión deben ajustarse a conjuntos de datos más pequeños en cada iteración. Friedman obtuvo que conduce a buenos resultados para series de entrenamiento de tamaño pequeño y moderado. Por lo tanto, generalmente se establece en 0.5, lo que significa que la mitad del conjunto de capacitación se usa para construir cada alumno base. ${\ Displaystyle f}$${\ Displaystyle f = 1}$${\ Displaystyle f}$${\ Displaystyle 0.5 \ leq f \ leq 0.8}$${\ Displaystyle f}$

Además, al igual que en el ensacado, el submuestreo permite definir un error fuera de bolsa de la mejora del rendimiento de la predicción al evaluar las predicciones en aquellas observaciones que no se utilizaron en la construcción del siguiente alumno base. Las estimaciones listas para usar ayudan a evitar la necesidad de un conjunto de datos de validación independiente, pero a menudo subestiman la mejora del rendimiento real y el número óptimo de iteraciones.

Número de observaciones en hojas

Las implementaciones de refuerzo de árboles de gradiente a menudo también utilizan la regularización al limitar el número mínimo de observaciones en los nodos terminales de los árboles. Se utiliza en el proceso de construcción del árbol al ignorar cualquier división que conduzca a nodos que contengan menos instancias de conjuntos de entrenamiento que esta cantidad.

La imposición de este límite ayuda a reducir la variación en las predicciones en las hojas.

Penalizar la complejidad del árbol

Otra técnica de regularización útil para árboles potenciados por gradientes es penalizar la complejidad del modelo aprendido. La complejidad del modelo se puede definir como el número proporcional de hojas en los árboles aprendidos. La optimización conjunta de la pérdida y la complejidad del modelo corresponde a un algoritmo posterior a la poda para eliminar las ramas que no logran reducir la pérdida en un umbral. También se pueden agregar otros tipos de regularización, como una penalización en los valores de la hoja, para evitar el sobreajuste . ${\ Displaystyle \ ell _ {2}}$

Uso

El aumento de gradiente se puede utilizar en el campo de aprender a clasificar . Los motores de búsqueda web comerciales Yahoo y Yandex utilizan variantes de aumento de gradiente en sus motores de clasificación de 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 redes neuronales profundas (DNN) de impulso de gradiente lograron reproducir los resultados de métodos de análisis sin aprendizaje automático en conjuntos de datos utilizados para descubrir el bosón de Higgs .

Nombres

El método tiene una variedad de nombres. Friedman introdujo su técnica de regresión como una "máquina de aumento de gradiente" (GBM). Mason, Baxter y col. describió la clase abstracta generalizada de algoritmos como "aumento funcional del gradiente". Friedman y col. describir un avance de los modelos impulsados ​​por gradientes como Árboles de regresión aditiva múltiple (MART); Elith y col. describen ese enfoque como "árboles de regresión potenciados" (BRT).

Una implementación popular de código abierto para R lo llama un "Modelo de impulso generalizado", sin embargo, los paquetes que amplían este trabajo utilizan BRT. Otro nombre más es TreeNet, después de una implementación comercial temprana de Dan Steinberg de Salford System, uno de los investigadores que fueron pioneros en el uso de métodos basados ​​en árboles. XGBoost es otra implementación moderna popular del método con algunas extensiones, como la optimización de segundo orden.

Desventajas

Si bien el impulso puede aumentar la precisión de un alumno básico, como un árbol de decisiones o una regresión lineal, sacrifica la inteligibilidad y la interpretabilidad . Además, su implementación puede resultar más difícil debido a la mayor demanda computacional.

Ver también

• AdaBoost
• Bosque aleatorio
• Catboost
• LightGBM
• XGBoost
• Aprendizaje del árbol de decisiones

Referencias

Otras lecturas

• Boehmke, Bradley; Greenwell, Brandon (2019). "Aumento de gradiente". El aprendizaje práctico de la máquina con R . Chapman y Hall. págs. 221–245. ISBN 978-1-138-49568-5.

enlaces externos

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