GBDT: Árbol de decisión potenciado por gradiente
? El árbol de GBDT es un árbol de regresión (no un árbol de clasificación). GBDT se utiliza para la predicción de regresión y también se puede utilizar para la clasificación ajustada.
? La idea de GBDT le da una ventaja natural y puede encontrar una variedad de características distintivas y combinaciones de características. En la industria, Facebook lo utiliza para descubrir automáticamente funciones efectivas y combinaciones de funciones como funciones en el modelo LR para mejorar la precisión de la predicción de la tasa de clics del CTR (consulte las Referencias 5 y 6 para obtener más detalles). GBDT también desempeña un papel importante en el negocio de búsqueda y predicción de Taobao (consulte la Referencia 7 para obtener más detalles).
El proceso general del árbol de regresión es similar al del árbol de clasificación. La diferencia es que cada nodo del árbol de regresión obtendrá un valor predicho. Tomando la edad como ejemplo, el valor predicho es igual a la edad promedio de todas las personas que pertenecen a este nodo. Al bifurcar, cada umbral de cada característica se enumera exhaustivamente para encontrar el mejor punto de división, pero la mejor métrica ya no es la entropía máxima, sino el error cuadrático mínimo. En otras palabras, cuantas más personas cometen errores de predicción, más escandalosos serán los errores y mayor será el error al cuadrado. Al minimizar el error al cuadrado, se puede encontrar la base de rama más confiable. Ramifica hasta que la edad de la persona en cada nodo de hoja sea única o alcance una condición de terminación preestablecida (como el límite superior del número de hojas). Si la edad de la persona en el nodo de la hoja final no es única, la edad promedio de todas las personas en el nodo se utiliza como la edad prevista del nodo de la hoja. (Citado de un blog, consulte la referencia 3 para obtener más detalles)
? El algoritmo del árbol de regresión se muestra en la siguiente figura (captura de pantalla generada por el Método de aprendizaje estadístico 5.5.1 CART):
Impulsar el árbol consiste en iterar varios árboles de regresión para tomar la misma decisión. Cuando se utiliza la función de pérdida de error al cuadrado, cada árbol de regresión aprende las conclusiones y residuos de todos los árboles anteriores, y el árbol de regresión residual actual se obtiene mediante ajuste. El significado de residual es el siguiente: residual = valor verdadero - valor previsto. Un árbol impulsado es la acumulación de árboles de regresión generados a lo largo del proceso iterativo.
? Por ejemplo, refiriéndose a un blog (Ref. 4), el ejemplo citado en este blog demuestra de manera más intuitiva el proceso de suma lineal de múltiples árboles de decisión y la importancia de los residuos.
? Entrenar un modelo de árbol mejorado para predecir la edad;
? Hay cuatro personas en el conjunto de entrenamiento. Las edades de A, B, C y D son 14, 16, 24 y 26 años respectivamente. Las muestras tienen características como cantidad de compras, tiempo en línea y visitas frecuentes a Baidu para hacer preguntas. El proceso de mejora del árbol de Navidad es el siguiente:
En este ejemplo se puede ver intuitivamente que el valor predicho es igual a la acumulación de todos los valores del árbol. Por ejemplo, el valor predicho de A = el nodo izquierdo. El valor del árbol 1 es 15 y el nodo izquierdo del árbol 2 -1 = 14.
? Por lo tanto, dado el modelo actual fm-1(x), simplemente ajuste los residuos del modelo actual. El algoritmo de árbol impulsado actual para problemas de regresión se describe a continuación:
El árbol impulsado utiliza un modelo aditivo y un algoritmo paso a paso hacia adelante para realizar el proceso de optimización del aprendizaje. Cuando la función de pérdida es una función de pérdida cuadrada y una función de pérdida exponencial, la optimización en cada paso es simple, como usar una función de pérdida cuadrada para aprender un árbol de regresión residual.
? Pero para las funciones de pérdida generales, a menudo no es fácil optimizar cada paso, como la función de pérdida absoluta y la función de pérdida de Huber en la figura anterior. En respuesta a este problema, Freidman propuso el algoritmo de aumento de gradiente: utilizando el método de aproximación de descenso más pronunciado, es decir, utilizando el valor del gradiente negativo de la función de pérdida en el modelo actual como el valor aproximado del residual del algoritmo de árbol de impulso. en el problema de regresión para ajustarlo a un árbol de regresión.
(Nota: personalmente creo que el residual es un caso especial de gradiente negativo en lugar de una aproximación del residual). El algoritmo es el siguiente (captura de pantalla de "Elementos de aprendizaje estadístico"):
Explicación del algoritmo pasos:
profundidad recomendada del árbol GBDT: 6 (Comparación horizontal: el árbol de decisión/RandomForest necesita ajustar la profundidad del árbol a 15 o más)
? Lo siguiente es un extracto de una sesión de preguntas y respuestas sobre Zhihu (consulte la Referencia 8 para obtener más detalles). Las preguntas y respuestas explican muy bien las matemáticas de la configuración de este parámetro.
? ¿Por qué xgboost/gbdt puede lograr una alta precisión al ajustar los parámetros?
? Usar xgboost/gbdt para ajustar la profundidad máxima del árbol a 6 tiene una alta precisión. Pero cuando se utiliza DecisionTree/RandomForest, la profundidad del árbol debe ajustarse a 15 o más. Puedo entender que la profundidad del árbol requerida para usar RandomForest es la misma que la del árbol de decisión, porque combina árboles de decisión mediante embolsado, lo que equivale a hacer árboles de decisión varias veces. Sin embargo, xgboost/gbdt puede lograr una alta precisión de predicción de profundidades de 6 nodos usando solo el método de ascenso de gradiente. Me sorprendió y sospeché que era una tecnología negra. ¿Cómo lo hace xgboost/gbdt? ¿Son sus nodos diferentes de los árboles de decisión generales?
? ¿Respuesta
? Esta es una muy buena pregunta. El interrogador ha estudiado cada algoritmo con mucha atención y profundidad, y las preguntas formuladas también están relacionadas con la esencia de estos dos algoritmos. En realidad, esta pregunta no es muy simple. Estoy tratando de responder esta pregunta utilizando mi conocimiento superficial de aprendizaje automático.
? Una explicación de una oración proviene del libro de texto de aprendizaje automático de Zhou Zhihua: Boosting se enfoca principalmente en reducir el sesgo, por lo que Boosting puede construir una fuerte integración basada en estudiantes con bajo rendimiento de generalización. Bagging se enfoca en reducir la varianza, por lo que en árboles de decisión y árboles de decisión Más eficiente en; aprendices como las redes neuronales, no se requiere poda.
? Tanto el bosque aleatorio como el GBDT pertenecen a la categoría de aprendizaje conjunto. Hay dos estrategias importantes en el aprendizaje integrado: embolsar y empujar.
? El algoritmo Bagging hace esto: cada clasificador toma muestras aleatorias de muestras originales, luego entrena un clasificador en estas muestras muestreadas y luego combina estos clasificadores. Generalmente basta con una mayoría simple de votos. Su algoritmo representativo es el bosque aleatorio. Boosting entrena iterativamente una serie de clasificadores, y la distribución de muestra utilizada por cada clasificador está relacionada con los resultados de aprendizaje de la ronda anterior. Sus algoritmos representativos incluyen AdaBoost y GBDT.
? De hecho, en lo que respecta a los algoritmos de aprendizaje automático, su error de generalización se puede descomponer en dos partes: sesgo y varianza. Esto se puede deducir de la fórmula de la siguiente figura (aquí se utiliza la fórmula de probabilidad D(X)= E(X ^ 2)-[E(X)]2). La desviación se refiere al grado de desviación entre la predicción esperada del algoritmo y la predicción real, lo que refleja la capacidad de ajuste del modelo en sí. La varianza mide el cambio en el rendimiento del aprendizaje causado por cambios en el conjunto de entrenamiento del mismo tamaño y describe el impacto; causado por la alteración de los datos. Esta es una forma un poco indirecta, pero hay que saber cuál encaja.
? Como se muestra en la figura siguiente, cuanto más complejo sea el modelo, mayor será el grado de ajuste y menor será la desviación de entrenamiento del modelo. Pero en este momento, si cambia un conjunto de datos, el modelo puede cambiar mucho, es decir, la varianza del modelo es muy grande. Entonces, cuando el modelo es demasiado complejo, se producirá un sobreajuste.
? Cuando el modelo es más simple, incluso si cambiamos otro conjunto de datos, la diferencia entre el alumno final y el alumno anterior no es tan grande, y la varianza del modelo también es pequeña. O como el modelo es simple, la desviación será grande.
? En otras palabras, cuando entrenamos un modelo, se deben tener en cuenta tanto el sesgo como la varianza, y ninguno de los dos puede faltar.
? Para el algoritmo Bagging, debido a que entrenaremos muchos clasificadores diferentes en paralelo, el propósito es reducir esta varianza, porque después de usar más clasificadores base independientes, el valor de h se acercará naturalmente. Entonces, para cada clasificador base, el objetivo es cómo reducir este sesgo, por lo que usaremos un árbol de decisión que sea muy profundo o incluso no podado.
? Para Boosting, ajustaremos mejor los datos originales en función de la última ronda de cada paso, para garantizar el sesgo. Entonces, para cada clasificador base, la pregunta es cómo elegir un clasificador con una varianza más pequeña, que es un clasificador más simple, por lo que elegimos un árbol de decisión de menor profundidad.
Recientemente, xgboost, un algoritmo de aumento de gradiente que ha llamado la atención, ha mejorado significativamente la velocidad de cálculo y la precisión en comparación con GBDT. El nombre completo de xgboost es Extreme Gradient Boosting, que es una implementación en C de la máquina de aumento de gradiente. El autor es Chen Qicheng Tianqi, que estudia aprendizaje automático en la Universidad de Washington. La característica más importante de xgboost es que puede utilizar automáticamente subprocesos múltiples de la CPU para la paralelización, al tiempo que mejora el algoritmo para aumentar la precisión. Su primera aparición fue la competencia de identificación de señales de Higgs de Kaggle. Debido a su excelente eficiencia y alta precisión de predicción, atrajo una gran atención de los concursantes en el foro de la competencia. GBDT merece nuestra mayor exploración e investigación.
Referencia
1. "Principios de aprendizaje estadístico"
2 Métodos de aprendizaje estadístico
3, / 2010/12/an-. enlace de introducción al árbol .html
8.