Una suave introducción al algoritmo Gradient Boosting para el aprendizaje automático

Última actualización el 15 de agosto de 2020

El gradient boosting es una de las técnicas más potentes para construir modelos predictivos.

En este post descubrirás el algoritmo de aprendizaje automático gradient boosting y obtendrás una suave introducción sobre su origen y funcionamiento.

Después de leer este post, sabrás:

• El origen de boosting desde la teoría del aprendizaje y AdaBoost.
• Cómo funciona gradient boosting incluyendo la función de pérdida, los aprendices débiles y el modelo aditivo.
• Cómo mejorar el rendimiento sobre el algoritmo base con varios esquemas de regularización.

Empiece su proyecto con mi nuevo libro XGBoost With Python, que incluye tutoriales paso a paso y los archivos de código fuente de Python para todos los ejemplos.

Comencemos.

• ¿Necesita ayuda con XGBoost en Python?
• El origen del refuerzo
• AdaBoost el Primer Algoritmo de Boosting
• Generalización de AdaBoost como Gradient Boosting
• Cómo funciona el Gradient Boosting
• Función de pérdida
• Aprendiz débil
• Modelo aditivo
• Mejoras al Gradient Boosting básico
• Tree Constraints
• 2. Actualizaciones ponderadas
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Recursos de gradient boosting
• Vídeos de Gradient Boosting
• Gradient Boosting in Textbooks
• Gradient Boosting Papers
• Diapositivas de Gradient Boosting
• Páginas web de Gradient Boosting
• Summary
• ¡Descubre el algoritmo ganador de concursos!
• Desarrolla tus propios modelos XGBoost en minutos
• Traiga el poder de XGBoost a sus propios proyectos

¿Necesita ayuda con XGBoost en Python?

Tome mi curso gratuito de 7 días por correo electrónico y descubra xgboost (con código de ejemplo).

Haga clic para inscribirse ahora y también obtenga una versión gratuita del curso en formato PDF Ebook.

¡Comience su minicurso gratuito ahora!

El origen del refuerzo

La idea del refuerzo surgió de la idea de si un alumno débil puede ser modificado para ser mejor.

Michael Kearns articuló el objetivo como el «Problema de refuerzo de hipótesis» estableciendo el objetivo desde un punto de vista práctico como:

… un algoritmo eficiente para convertir hipótesis relativamente pobres en hipótesis muy buenas

– Thoughts on Hypothesis Boosting , 1988

Una hipótesis débil o un aprendiz débil se define como uno cuyo rendimiento es al menos ligeramente mejor que el azar.

Estas ideas se basan en el trabajo de Leslie Valiant sobre el aprendizaje sin distribución o probablemente correcto (PAC), un marco para investigar la complejidad de los problemas de aprendizaje automático.

El refuerzo de hipótesis fue la idea de filtrar las observaciones, dejando aquellas observaciones que el aprendiz débil puede manejar y centrándose en el desarrollo de nuevos aprendizajes débiles para manejar las observaciones difíciles restantes.

La idea es utilizar el método de aprendizaje débil varias veces para obtener una sucesión de hipótesis, cada una reenfocada en los ejemplos que los anteriores encontraron difíciles y clasificaron mal. … Obsérvese, sin embargo, que no es nada obvio cómo se puede hacer esto

-Probablemente Aproximadamente Correcto: Algoritmos de la Naturaleza para Aprender y Prosperar en un Mundo Complejo, página 152, 2013

AdaBoost el Primer Algoritmo de Boosting

La primera realización de boosting que vio un gran éxito de aplicación fue el Adaptive Boosting o AdaBoost para abreviar.

El Boosting se refiere a este problema general de producir una regla de predicción muy precisa mediante la combinación de reglas aproximadas y moderadamente inexactas.

– Una generalización teórica de la decisión del aprendizaje en línea y una aplicación al boosting , 1995

Los aprendices débiles en AdaBoost son árboles de decisión con una sola división, llamados muñones de decisión por su brevedad.

AdaBoost funciona ponderando las observaciones, poniendo más peso en las instancias difíciles de clasificar y menos en las que ya se manejan bien. Se añaden secuencialmente nuevos aprendices débiles que centran su entrenamiento en los patrones más difíciles.

Esto significa que las muestras que son difíciles de clasificar reciben pesos cada vez mayores hasta que el algoritmo identifica un modelo que clasifica correctamente estas muestras

– Applied Predictive Modeling, 2013

Las predicciones se realizan por voto mayoritario de las predicciones de los aprendices débiles, ponderadas por su precisión individual. La forma más exitosa del algoritmo AdaBoost fue para problemas de clasificación binaria y se llamó AdaBoost.M1.

Puedes aprender más sobre el algoritmo AdaBoost en el post:

• Boosting y AdaBoost para el aprendizaje automático.

Generalización de AdaBoost como Gradient Boosting

AdaBoost y algoritmos relacionados fueron refundidos en un marco estadístico primero por Breiman llamándolos algoritmos ARCing.

Arcing es un acrónimo de Adaptive Reweighting and Combining. Cada paso en un algoritmo de arqueo consiste en una minimización ponderada seguida de un recálculo de y.

– Juegos de predicción y algoritmos de arqueo , 1997

Este marco fue desarrollado posteriormente por Friedman y llamado Gradient Boosting Machines. Más tarde se llamó simplemente gradient boosting o gradient tree boosting.

El marco estadístico planteó el boosting como un problema de optimización numérica en el que el objetivo es minimizar la pérdida del modelo añadiendo aprendices débiles mediante un procedimiento similar al del descenso de gradiente.

Esta clase de algoritmos se describió como un modelo aditivo por etapas. Esto se debe a que un nuevo aprendiz débil se añade a la vez y los aprendices débiles existentes en el modelo se congelan y se dejan sin cambios.

Nótese que esta estrategia por etapas es diferente de los enfoques por etapas que reajustan los términos introducidos previamente cuando se añaden otros nuevos.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

La generalización permitió utilizar funciones de pérdida diferenciables arbitrarias, ampliando la técnica más allá de los problemas de clasificación binaria para soportar la regresión, la clasificación multiclase y más.

Cómo funciona el Gradient Boosting

El Gradient Boosting implica tres elementos:

1. Una función de pérdida a optimizar.
2. Un aprendiz débil para hacer predicciones.
3. Un modelo aditivo para añadir aprendices débiles para minimizar la función de pérdida.

Función de pérdida

La función de pérdida utilizada depende del tipo de problema que se resuelva.

Debe ser diferenciable, pero se admiten muchas funciones de pérdida estándar y se puede definir la propia.

Por ejemplo, la regresión puede utilizar un error al cuadrado y la clasificación puede utilizar la pérdida logarítmica.

Una ventaja del marco de refuerzo de gradiente es que no hay que derivar un nuevo algoritmo de refuerzo para cada función de pérdida que se quiera utilizar, sino que es un marco lo suficientemente genérico como para que se pueda utilizar cualquier función de pérdida diferenciable.

Aprendiz débil

Los árboles de decisión se utilizan como aprendiz débil en el refuerzo de gradiente.

Específicamente se utilizan árboles de regresión que emiten valores reales para las divisiones y cuya salida puede sumarse, permitiendo añadir las salidas de los modelos posteriores y «corregir» los residuos en las predicciones.

Los árboles se construyen de manera codiciosa, eligiendo los mejores puntos de división basados en puntuaciones de pureza como Gini o para minimizar la pérdida.

Inicialmente, como en el caso de AdaBoost, se utilizaban árboles de decisión muy cortos que sólo tenían una única división, llamada muñón de decisión. Generalmente se pueden utilizar árboles más grandes con 4 a 8 niveles.

Es común restringir los aprendices débiles de maneras específicas, como un número máximo de capas, nodos, divisiones o nodos de hoja.

Esto es para asegurar que los aprendices sigan siendo débiles, pero aún pueden ser construidos de manera codiciosa.

Modelo aditivo

Los árboles se añaden de uno en uno, y los árboles existentes en el modelo no se modifican.

Se utiliza un procedimiento de descenso de gradiente para minimizar la pérdida al añadir árboles.

Tradicionalmente, el descenso de gradiente se utiliza para minimizar un conjunto de parámetros, como los coeficientes en una ecuación de regresión o los pesos en una red neuronal. Después de calcular el error o la pérdida, los pesos se actualizan para minimizar ese error.

En lugar de parámetros, tenemos submodelos de aprendizaje débil o, más concretamente, árboles de decisión. Después de calcular la pérdida, para realizar el procedimiento de descenso de gradiente, debemos añadir un árbol al modelo que reduzca la pérdida (es decir, que siga el gradiente). Esto lo hacemos parametrizando el árbol, luego modificamos los parámetros del árbol y nos movemos en la dirección correcta al (reducir la pérdida residual.

Generalmente este enfoque se llama descenso de gradiente funcional o descenso de gradiente con funciones.

Una forma de producir una combinación ponderada de clasificadores que se optimiza es mediante el descenso de gradiente en el espacio de funciones

– Boosting Algorithms as Gradient Descent in Function Space , 1999

La salida del nuevo árbol se añade entonces a la salida de la secuencia de árboles existente en un esfuerzo por corregir o mejorar la salida final del modelo.

Se añade un número fijo de árboles o el entrenamiento se detiene una vez que la pérdida alcanza un nivel aceptable o ya no mejora en un conjunto de datos de validación externa.

Mejoras al Gradient Boosting básico

El Gradient Boosting es un algoritmo codicioso y puede sobreajustar un conjunto de datos de entrenamiento rápidamente.

Puede beneficiarse de los métodos de regularización que penalizan varias partes del algoritmo y generalmente mejoran el rendimiento del algoritmo reduciendo el sobreajuste.

En esta sección veremos 4 mejoras al gradient boosting básico:

1. Tree Constraints
2. Shrinkage
3. Random sampling
4. Penalized Learning

Tree Constraints

Es importante que los aprendices débiles tengan habilidad pero sigan siendo débiles.

Hay un número de maneras en que los árboles pueden ser restringidos.

Una buena heurística general es que cuanto más restringida sea la creación de árboles, más árboles se necesitarán en el modelo, y lo contrario, donde menos árboles individuales restringidos, menos árboles se necesitarán.

A continuación se presentan algunas restricciones que se pueden imponer en la construcción de árboles de decisión:

• Número de árboles, generalmente añadir más árboles al modelo puede ser muy lento para el sobreajuste. El consejo es seguir añadiendo árboles hasta que no se observe ninguna mejora.
• Profundidad del árbol, los árboles más profundos son árboles más complejos y se prefieren los árboles más cortos. Generalmente, se observan mejores resultados con 4-8 niveles.
• Número de nodos o número de hojas, al igual que la profundidad, esto puede restringir el tamaño del árbol, pero no está restringido a una estructura simétrica si se utilizan otras restricciones.
• El número de observaciones por división impone una restricción mínima en la cantidad de datos de entrenamiento en un nodo de entrenamiento antes de que se pueda considerar una división
• La mejora mínima a la pérdida es una restricción en la mejora de cualquier división añadida a un árbol.

2. Actualizaciones ponderadas

Las predicciones de cada árbol se suman secuencialmente.

La contribución de cada árbol a esta suma puede ser ponderada para ralentizar el aprendizaje por parte del algoritmo. Esta ponderación se denomina contracción o tasa de aprendizaje.

Cada actualización es simplemente escalada por el valor del «parámetro de tasa de aprendizaje v»

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

El efecto es que el aprendizaje se ralentiza, requiriendo a su vez que se añadan más árboles al modelo, tardando a su vez más tiempo en entrenarse, proporcionando una compensación de configuración entre el número de árboles y la tasa de aprendizaje.

Disminuir el valor de v aumenta el mejor valor de M .

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Es común tener valores pequeños en el rango de 0,1 a 0,3, así como valores menores a 0,1.

Similar a una tasa de aprendizaje en la optimización estocástica, la contracción reduce la influencia de cada árbol individual y deja espacio para que futuros árboles mejoren el modelo.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

Una gran idea de los conjuntos de bolsas y los bosques aleatorios fue permitir que los árboles se crearan con avidez a partir de submuestras del conjunto de datos de entrenamiento.

Esta misma ventaja puede utilizarse para reducir la correlación entre los árboles de la secuencia en los modelos de refuerzo de gradiente.

Esta variación del refuerzo se denomina refuerzo de gradiente estocástico.

En cada iteración se extrae una submuestra de los datos de entrenamiento al azar (sin reemplazo) del conjunto de datos de entrenamiento completo. La submuestra seleccionada aleatoriamente se utiliza entonces, en lugar de la muestra completa, para ajustar el aprendiz base.

– Stochastic Gradient Boosting , 1999

Algunas variantes de boosting estocástico que se pueden utilizar:

• Submuestra filas antes de crear cada árbol.
• Submuestra columnas antes de crear cada árbol
• Submuestra columnas antes de considerar cada división.

En general, el submuestreo agresivo, como la selección de sólo el 50% de los datos, ha demostrado ser beneficioso.

Según los comentarios de los usuarios, el uso del submuestreo de columnas evita el sobreajuste incluso más que el submuestreo de filas tradicional

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Se pueden imponer restricciones adicionales a los árboles parametrizados además de su estructura.

Los árboles de decisión clásicos como CART no se utilizan como aprendices débiles, en su lugar se utiliza una forma modificada llamada árbol de regresión que tiene valores numéricos en los nodos de las hojas (también llamados nodos terminales). Los valores en las hojas de los árboles pueden ser llamados pesos en alguna literatura.

Como tal, los valores de peso de las hojas de los árboles pueden ser regularizados usando funciones de regularización populares, tales como:

• L1 regularización de pesos.
• L2 regularización de pesos.

El término de regularización adicional ayuda a suavizar los pesos finales aprendidos para evitar el sobre ajuste. Intuitivamente, el objetivo regularizado tenderá a seleccionar un modelo que emplee funciones simples y predictivas.

– XGBoost: A Scalable Tree Boosting System, 2016

Recursos de gradient boosting

El gradient boosting es un algoritmo fascinante y seguro que quieres profundizar en él.

En esta sección se enumeran varios recursos que puedes utilizar para aprender más sobre el algoritmo de gradient boosting.

Vídeos de Gradient Boosting

• Gradient Boosting Machine Learning, Trevor Hastie, 2014
• Gradient Boosting, Alexander Ihler, 2012
• GBM, John Mount, 2015
• Learning: Boosting, MIT 6.034 Artificial Intelligence, 2010
• xgboost: An R package for Fast and Accurate Gradient Boosting, 2016
• XGBoost: A Scalable Tree Boosting System, Tianqi Chen, 2016

Gradient Boosting in Textbooks

• Sección 8.2.3 Boosting, página 321, An Introduction to Statistical Learning: with Applications in R.
• Sección 8.6 Boosting, página 203, Applied Predictive Modeling.
• Sección 14.5 Stochastic Gradient Boosting, página 390, Applied Predictive Modeling.
• Sección 16.4 Boosting, página 556, Machine Learning: A Probabilistic Perspective
• Capítulo 10 Boosting and Additive Trees, página 337, The Elements of Statistical Learning: Data Mining, Inference, and Prediction

Gradient Boosting Papers

• Thoughts on Hypothesis Boosting , Michael Kearns, 1988
• A decision-theoretic generalization of on-line learning and an application to boosting , 1995
• Arcing the edge , 1998
• Stochastic Gradient Boosting , 1999
• Boosting Algorithms as Gradient Descent in Function Space , 1999

Diapositivas de Gradient Boosting

• Introducción a los árboles boosted, 2014
• Una suave introducción al Gradient Boosting, Cheng Li

Páginas web de Gradient Boosting

• Boosting (machine learning)
• Gradient boosting
• Gradient Tree Boosting in scikit-learn

Summary

En este post se descubrió el algoritmo de gradient boosting para el modelado predictivo en machine learning.

Específicamente, aprendiste:

• La historia del boosting en la teoría del aprendizaje y AdaBoost.
• Cómo funciona el algoritmo de boosting de gradiente con una función de pérdida, aprendices débiles y un modelo aditivo.
• Cómo mejorar el rendimiento del gradient boosting con regularización.

¿Tienes alguna pregunta sobre el algoritmo de gradient boosting o sobre este post? Haz tus preguntas en los comentarios y haré lo posible por responderlas.