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 . [1] [2] 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 . [1] [2] [3] Construye el modelo de una manera por etapas como lo hacen otros métodos de impulso , y los generaliza al permitir la optimización de un diferenciable arbitrario función de pérdida .
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. [4] Jerome H. Friedman desarrolló posteriormente algoritmos de aumento de gradiente de regresión explícita , [5] [6] simultáneamente con la perspectiva de aumento de gradiente funcional más general de Llew Mason, Jonathan Baxter, Peter Bartlett y Marcus Frean. [7] [8] Los dos últimos artículos introdujeron el punto de vista de los algoritmos de impulso como algoritmos de descenso de gradientes funcionales iterativos . 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. [9] )
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" un modelo para predecir valores de la forma minimizando el error cuadrático medio , dónde índices sobre algún conjunto de entrenamiento de tamaño de los valores reales de la variable de salida :
- el valor predicho
- el valor observado
- el número de muestras en
Ahora, consideremos un algoritmo de aumento de gradiente con etapas. En cada etapa () de aumento de gradiente, suponga algún modelo imperfecto (por bajo , este modelo simplemente puede regresar , donde el RHS es la media de). Para mejorar, nuestro algoritmo debería agregar un estimador nuevo, . Por lo tanto,
o equivalente,
- .
Por lo tanto, el aumento de gradiente ajustará h al residuo . Como en otras variantes de impulso, cada intenta corregir los errores de su predecesor . Una generalización de esta idea a las funciones de pérdida distintas del error al cuadrado, y a los problemas de clasificación y clasificación , se sigue de la observación de que los residuospara un modelo dado son los gradientes negativos de la función de pérdida del error cuadrático medio (MSE) (con respecto a):
- .
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ónque mejor se aproxima a la variable de salida a partir de los valores de las variables de entrada. Esto se formaliza mediante la introducción de alguna función de pérdida. y minimizándolo:
- .
El método del gradiente impulsar asume un valor real- Y y busca una aproximación en forma de suma ponderada de funciones de alguna clase , llamados aprendices básicos (o débiles ):
- .
Por lo general, nos dan un conjunto de entrenamiento de valores muestrales conocidos de x y valores correspondientes de y . De acuerdo con el principio empírico de minimización de riesgos , el método intenta encontrar una aproximaciónque minimiza el valor medio de la función de pérdida en el conjunto de entrenamiento, es decir, minimiza el riesgo empírico. Lo hace partiendo de un modelo, que consta de una función constantey lo expande gradualmente de una manera codiciosa :
- ,
- ,
dónde es una función básica de aprendizaje.
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 de gradiente funcional). Si consideramos el caso continuo, es decir, donde es el conjunto de funciones diferenciables arbitrarias en , actualizaríamos el modelo de acuerdo con las siguientes ecuaciones
donde se toman las derivadas con respecto a las funciones por , y es la longitud del paso. Sin embargo, en el caso discreto, es decir, cuando el conjuntoes finito, elegimos la función candidata h más cercana al gradiente de L para la cual el coeficiente γ se puede calcular 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: [5] [2]
Entrada: conjunto de entrenamiento una función de pérdida diferenciable número de iteraciones M .
Algoritmo:
- Inicialice el modelo con un valor constante:
- Para m = 1 a M :
- Calcule los llamados pseudo-residuales :
- Encajar en un alumno básico (o alumno débil, por ejemplo, árbol) a pseudo-residuales, es decir, entrenarlo usando el conjunto de entrenamiento .
- Calcular multiplicador resolviendo el siguiente problema de optimización unidimensional :
- Actualiza el modelo:
- Calcule los llamados pseudo-residuales :
- Producción
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 del 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 en un árbol de decisióna pseudo-residuales. Dejarsea el número de sus hojas. El árbol divide el espacio de entrada en regiones disjuntas y predice un valor constante en cada región. Usando la notación del indicador , la salida depara la entrada x se puede escribir como la suma:
dónde es el valor predicho en la región . [10]
Entonces los coeficientes se multiplican por algún valor , elegido usando la búsqueda de línea para minimizar la función de pérdida, y el modelo se actualiza de la siguiente manera:
Friedman propone modificar este algoritmo para que elija un valor óptimo separado para cada una de las regiones del árbol, en lugar de una sola para todo el árbol. Él llama al algoritmo modificado "TreeBoost". Los coeficientes del procedimiento de ajuste de árbol puede simplemente descartarse y la regla de actualización del modelo se convierte en:
Tamaño de los árboles
, 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 puede incluir efectos de la interacción entre hasta dos variables y así sucesivamente.
Hastie y col. [2] comenta que normalmente funcionan bien para impulsar y los resultados son bastante insensibles a la elección de en este rango, es insuficiente para muchas aplicaciones, y es poco probable que sea necesario.
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 probabilidades habrá de 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:
donde parámetro se llama "tasa de aprendizaje".
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 encoger (). [2] 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.
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'). [6] 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. [11] 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. Cuándo, el algoritmo es determinista e idéntico al descrito anteriormente. Valores más pequeños deintroducir aleatoriedad en el algoritmo y ayudar 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 [6] obtuvo queconduce 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.
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. [12] [13]
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. [14] 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. Otros tipos de regularización comoTambién se puede agregar una penalización en los valores de la hoja para evitar un ajuste excesivo .
Uso
El aumento de gradiente se puede utilizar en el campo de aprender a clasificar . Los motores de búsqueda web comerciales Yahoo [15] y Yandex [16] 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 . [17]
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). [5] Mason, Baxter y col. describió la clase abstracta generalizada de algoritmos como "aumento funcional del gradiente". [7] [8] Friedman y col. describir un avance de los modelos impulsados por gradientes como Árboles de regresión aditiva múltiple (MART); [18] Elith y col. describen ese enfoque como "árboles de regresión potenciados" (BRT). [19]
Una implementación popular de código abierto para R lo llama un "Modelo de impulso generalizado", [12] sin embargo, los paquetes que amplían este trabajo utilizan BRT. [20] 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. [21] XGBoost es otra implementación moderna y 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 . [1] [22] Además, su implementación puede ser 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
- ^ a b c Piryonesi, S. Madeh; El-Diraby, Tamer E. (1 de marzo de 2020). "Análisis de datos en la gestión de activos: predicción rentable del índice de condición del pavimento" . Revista de sistemas de infraestructura . 26 (1): 04019036. doi : 10.1061 / (ASCE) IS.1943-555X.0000512 . ISSN 1943-555X .
- ^ a b c d e Hastie, T .; Tibshirani, R .; Friedman, JH (2009). "10. Árboles potenciadores y aditivos" . Los elementos del aprendizaje estadístico (2ª ed.). Nueva York: Springer. págs. 337–384. ISBN 978-0-387-84857-0. Archivado desde el original el 10 de noviembre de 2009.
- ^ Piryonesi, S. Madeh; El-Diraby, Tamer E. (1 de febrero de 2021). "Uso del aprendizaje automático para examinar el impacto del tipo de indicador de rendimiento en el modelado de deterioro de pavimento flexible" . Revista de sistemas de infraestructura . 27 (2): 04021005. doi : 10.1061 / (ASCE) IS.1943-555X.0000602 . ISSN 1076-0342 .
- ^ Breiman, L. (junio de 1997). "Arqueando el borde" (PDF) . Informe técnico 486 . Departamento de Estadística, Universidad de California, Berkeley.
- ^ a b c Friedman, JH (febrero de 1999). "Aproximación de función codiciosa: una máquina de aumento de gradiente" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ a b c Friedman, JH (marzo de 1999). "Impulso de gradiente estocástico" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ a b Mason, L .; Baxter, J .; Bartlett, PL; Frean, Marcus (1999). "Impulsar algoritmos como descenso de gradiente" (PDF) . En SA Solla y TK Leen y K. Müller (ed.). Avances en los sistemas de procesamiento de información neuronal 12 . Prensa del MIT. págs. 512–518.
- ^ a b Mason, L .; Baxter, J .; Bartlett, PL; Frean, Marcus (mayo de 1999). "Aumento de algoritmos como descenso de gradiente en el espacio funcional" (PDF) . Archivado desde el original (PDF) el 22 de diciembre de 2018. Cite journal requiere
|journal=
( ayuda ) - ^ Cheng Li. "Una suave introducción al aumento de gradiente" (PDF) .
- ^ Nota: en el caso de los árboles CART habituales, los árboles se ajustan utilizando la pérdida por mínimos cuadrados, por lo que el coeficiente para la región es igual al valor de la variable de salida, promediado sobre todas las instancias de entrenamiento en .
- ^ Tenga en cuenta que esto es diferente del ensacado, que muestra con reemplazo porque usa muestras del mismo tamaño que el conjunto de entrenamiento.
- ↑ a b Ridgeway, Greg (2007). Modelos reforzados generalizados: una guía del paquete gbm.
- ^ Aprenda el algoritmo de aumento de gradiente para obtener mejores predicciones (con códigos en R)
- ^ Tianqi Chen. Introducción a los árboles potenciados
- ^ Cossock, David y Zhang, Tong (2008). Análisis estadístico de la clasificación de subconjuntos óptimos de Bayes Archivado el 7 de agosto de 2010 en la Wayback Machine , página 14.
- ^ Entrada del blog corporativo de Yandex sobre el nuevo modelo de clasificación "Snezhinsk" (en ruso)
- ^ Lalchand, Vidhi (2020). "Extraer más de árboles de decisión impulsados: un estudio de caso de física de alta energía". arXiv : 2001.06033 [ stat.ML ].
- ^ Friedman, Jerome (2003). "Árboles de regresión aditiva múltiple con aplicación en epidemiología". Estadística en Medicina . 22 (9): 1365-1381. doi : 10.1002 / sim.1501 . PMID 12704603 .
- ^ Elith, Jane (2008). "Una guía de trabajo para árboles de regresión potenciados" . Revista de Ecología Animal . 77 (4): 802–813. doi : 10.1111 / j.1365-2656.2008.01390.x . PMID 18397250 .
- ^ Elith, Jane. "Árboles de regresión potenciados para el modelado ecológico" (PDF) . CRAN . CRAN . Consultado el 31 de agosto de 2018 .
- ^ https://www.kdnuggets.com/2013/06/exclusive-interview-dan-steinberg-salford-systems-data-mining-solutions-provider.html
- ^ Wu, Xindong; Kumar, Vipin; Ross Quinlan, J .; Ghosh, Joydeep; Yang, Qiang; Motoda, Hiroshi; McLachlan, Geoffrey J .; Ng, Angus; Liu, Bing; Yu, Philip S .; Zhou, Zhi-Hua (1 de enero de 2008). "Top 10 algoritmos en minería de datos". Sistemas de conocimiento e información . 14 (1): 1–37. doi : 10.1007 / s10115-007-0114-2 . hdl : 10983/15329 . ISSN 0219-3116 . S2CID 2367747 .
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