Como funciona Gradient Boosting

Publicado por @Javii el April 10, 2019, 4:16 p.m.
Introducción ------------ El número de técnicas de aprendizaje automático es muy grande. Últimamente se han popularizado la redes neuronales debido a su alta precisión y parece que se han dejado de lado el resto de técnicas de ML. Pero lo cierto es que existen muchas otras técnicas muy potentes como random forest que está basado en árboles de decisión. La idea general de random forest es la construcción de muchos árboles de decisión independientes y tomar el “promedio” como resultado final. Pero existen otras técnicas de agrupación de árboles como el boosting que propone “encadenar” varios árboles de decisión para crear un clasificador más robusto. Adaboost -------- Probablemente el algoritmo de boosting más conocido es Adaboost (Adaptive boosting). El funcionamiento de este algoritmo es muy sencillo: - Creamos un clasificador sencillo (árbol de decisión de profundidad 1) y clasificamos la primera iteración t=1 - Aquellas muestras que hemos clasificado mal (3 puntos azules), le damos un mayor peso para la siguiente clasificación. - Y volvemos a crear un árbol para la siguiente iteración. Y así sucesivamente. <img src="https://hsto.org/web/d28/78f/7ba/d2878f7bad0340fc8002e5ba6d0879a5.jpg" width="550"/> Finalmente promediamos todas las clasificaciones por unos pesos y obtenemos la clasificación final. (Los pesos se corresponden de forma inversamente-proporcional al error de cada clasificador). <img src="https://hsto.org/web/b2b/029/d89/b2b029d898f64bbbb158e15d29595969.png" width="550"/> [Aquí](https://www.youtube.com/watch?v=k4G2VCuOMMg) se puede ver el algoritmo en acción con un dataset mayor. Y se aprecia como varía el peso que se le asigna a cada punto.) Este algoritmo es muy potente pero tiene desventajas como: - Puede producir overfitting (el peso a los outliers va creciendo) - No es interpretable - No es multiclase (existen variantes como Adaboost.M1 que sí lo son) Gradient boosting ----------------- La diferencia con adaboost es que ya no pesamos cada punto independientemente, sino que proponemos una función de error cuyo gradiente tenemos que minimizar. Como hemos dicho, boosting es la creación de un clasificador fuerte a partir de muchos débiles. Por ejemplo si tenemos 2 árboles, la predicción sería la suma de las clasificaciones: <img src="https://raw.githubusercontent.com/dmlc/web-data/master/xgboost/model/twocart.png" width="550"/> Matemáticamente se expresa de la siguiente forma: Si tenemos 2 árboles, se suman las predicciones. Pero tambíen se puede expresar como la suma del último árbol a lo que ya teníamos sumado. <img src="https://i.imgur.com/jSWD89X.jpg" width="400"/> Esta función **ŷ** es nuestra predicción y tenemos que optimizarla. Para ello creamos una función objetivo (basada en el error cuadrático por ejemplo) que tenemos que minimizar: <img src="https://i.imgur.com/5mWRtKw.jpg" width="200"/> Ejemplo práctico: Regresión --------------------------- Supongamos un ejemplo práctico para entender mejor Gradient boosting. Supongamos un dataset donde debemos predecir la edad de una persona en función de si le gusta la jardinería, los videojuegos y los sombreros. De forma intuitiva sabemos que a las personas mayores les gusta la jardinería y a los jóvenes los videojuegos. El gusto por los sombreros es más aleatorio. <img src="https://i.imgur.com/ZCKXClr.png" width="550"/> Lo primero es implementar un árbol de de profundidad 1 y clasificar, por ejemplo el gusto por la jardinería: <img src="https://i2.wp.com/blog.kaggle.com/wp-content/uploads/2017/01/blog_gb_tree1_3.png" width="550"/> Con esta primera clasificación ya podemos calcular el error de la función objetivo. Definamos la función objetivo como el error absoluto en lugar del error cuadrático para simplificar. <img src="https://i.imgur.com/YL83clu.png" width="550"/> **Ahora usamos esos errores** (también llamados residuals) para crear el segundo árbol de decisión. Se escoge la variable juega a videojuegos: <img src="https://i2.wp.com/blog.kaggle.com/wp-content/uploads/2017/01/blog_gb_tree2_3.png" width="550"/> Se calculan los residuals medios de cada nodo: 7.133 y -3.567. Porque modificarán nuestra predicción final. Calculamos la predicción final en esta segunda iteración de gradient boosting con 2 árboles: <img src="https://i.imgur.com/1ydMMuD.png" width="550"/> Como hemos definido antes, la predicción final es la suma de las predicciones de los árboles. Volvemos a calcular el error, que ahora es menor, y podríamos seguir con más iteraciones. Notas finales sobre Gradient Boosting ------------------------------------- Ahora que entendemos el funcionamiento básico de gradient boosting, vamos a aclarar un par de cosas: - Ese error o residual que calculamos en cada iteración, es el “gradiente” de gradient boosting, que indica cómo tenemos que construir el siguiente clasificador. - La función de error puede ser cualquiera, como el error absoluto o el error cuadrático para regresión. - Si fuera clasificación, sería el error logarítmico que indica el grado de pertenencia de la instancia a la clase. Implementaciones en software ---------------------------- Las implementaciones de gradient boosting añaden ciertas heurísticas que mejoran el algoritmo básico descrito anteriormente. Mejoras como: - La optimización de 2o orden en la función de error. - Añadir un término de regularización (L2) en la función objetivo. - Hacer subsampling de los datos en algunas iteraciones (como random forest). La primera implementación (2014) y probablemente la más conocida es XGBoost. Dicho framework se popularizó en la plataforma de competiciones Kaggle en 2016 por su alta precisión y velocidad de entrenamiento. Posteriormente en 2017, surgieron otros 2 frameworks como LightGBM creado por Microsoft y CatBoost creado por una comunidad rusa mejorando el manejo de variables categóricas. <img src="https://i.imgur.com/bfoItfy.png" width="550"/> Referencias ----------- - [Explicación de Gradient boosting por un competidor de Kaggle](http://blog.kaggle.com/2017/01/23/a-kaggle-master-explains-gradient-boosting) - [Funcionamiento de gradient boosting](https://xgboost.readthedocs.io/en/latest/tutorials/model.html) - [Comparativa de Implementaciones](https://towardsdatascience.com/catboost-vs-light-gbm-vs-xgboost-5f93620723db)