AnyBoost: el algoritmo perfecto que no funciona
Los métodos de Boosting son uno de los grandes logros en Machine Learning tanto desde el punto de vista práctico como desde el punto de vista teórico, sus ventajas estadísticas y computacionales los hacen una herramienta indispensable en el día a día de los científicos de datos.
Es muy probable que un científico de datos joven solo conozca las implementaciones de Boosting más recientes como LightGBM, XGBoost o CatBoost sin embargo existe muchos otros algoritmos de boosting, algunos de ellos ni siquiera están implementados debido a la complejidad computacional.
En esta edición de nuestro Bourbakisme vamos a hablar sobre un algoritmo de Boosting el cual en un inicio fue muy prometedor debido a las garantías matemáticas que otorga sin embargo su implementación es muy complicada en la práctica y es por eso que no es utilizado.
Breve historia de Boosting
Además de su importancia práctica, su desarrollo histórico es muy interesante pues en aproximadamente 15 años únicamente, se puede contar la vertiginosa historia desde una pregunta puramente teórica hasta la elaborada implementación en las bibliotecas actuales.
En esta primera sección vamos a repasar la historia de Boosting mencionando algunos de los artículos más emblemáticos, desafortunadamente este texto no recorre exhaustivamente la riquísima historia de estos métodos. Vale la pena mencionar que durante sus inicios, los métodos de boosting eran conocidos como Arcing: Adaptative Resampling and Combining.
La historia de Boosting nace en el célebre artículo Thoughts on Hypothesis Boosting del científico de la computación Michael Kearns en el que se pregunta si existe algún método para combinar modelos matemáticos débiles que juntos den un resultado estrictamente superior a cualquiera de ellos. Es por eso que este método se le conoce como un meta-algoritmo y no necesariamente un algoritmo.
Pasaron algunos años hasta que los científicos de la computación Yoav Freund y Robert E Schapire publicaron el artículo A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting el cual es la base de las implementaciones que hoy en día conocemos como AdaBoost. Este es uno de los trabajos más importantes en Machine Learning e inclusive recibió el famoso Gödel Prize gracias a su originalidad.
A pesar de que AdaBoost es muy poderoso, su desempeño es bastante limitado comparado con las técnicas modernas de Boosting, fue necesario combinar la idea general de boosting con los métodos del gradiente para construir los modelos que conocemos hoy en día. En el artículo Greedy function approximation: A gradient boosting machine el científico de la computación Jerome H. Friedman introdujo la versión más moderna de boosting la cual llamó Gradient Boosting Machine.
En este texto hablaremos sobre un artículo publicado al rededor del mismo momento llamado Boosting Algorithms as Gradient Descent en el cual se propone el algoritmo AnyBoost el cual propone una interpretación del método de boosting como un algoritmo de gradiente en el espacio de combinaciones lineales de funciones objetivo.
AnyBoost: la idea intuitiva
La explicación más intuitiva para comprender cómo funciona boosting es mediante la actualización de la distribución empírica de los datos, es decir modificando el espacio de probabilidad de nuestros registros iterativamente para construir modelos débiles con estos muestreos y después proponer una combinación lineal entre los modelos débiles.
En el último artículo mencionado en la sección anterior se propone una interpretación diferencial detrás de la idea anterior sin hacer referencia explícita a las modificaciones de la distribución sobre nuestra base de datos.
Supongamos que en el instante T de nuestro algoritmo iterativo, hemos entrenado a una función F la cual tiene un error L en nuestra base de datos. La idea intuitiva es encontrar una nueva función f de tal manera que el error de alguna combinación lineal entre F y f reduzcan el error en el conjunto de datos:
Notemos que la combinación lineal que estamos proponiendo en la ecuación anterior es muy particular pues sus coeficientes son el uno y épsilon (donde este es un número pequeño). La razón por la que se está haciendo esto es porque nuestra intención es que este algoritmo se itere numerosas veces y por lo tanto el aporte de las f deberá ser pequeño comparado a lo entrenado hasta ese momento.
Para cualquier científico de datos con alguna preparación matemática el siguiente paso evidente sería utilizar el gradiente de la función L, esta idea motivada por el célebre método de gradiente descendente propuesto por el francés Cauchy.
Por el otro lado, todos los científicos de datos notarán que para que lo anterior funcione correctamente, es necesario que el espacio de funciones donde se buscan a las f durante el entrenamiento esté acotado, de lo contrario pronto tendremos que afrontar un grave problema de overfitting.
Para remediar el problema anterior se utilizará al producto exterior de una manera muy similar a como los científicos de datos utilizan a la medida del coseno pero esta vez para calcular la cercanía entre funciones, a diferencia del cálculo entre registros como normalmente hacen los científicos de datos. Concretamente la intención es maximizar la siguiente cantidad para un conjunto restringido de funciones f, a saber nuestros modelos débiles.
Bien entendido, estamos buscando dentro del conjunto de modelos débiles, aquel que se parece más al modelo en el que se minimiza el gradiente de la función de pérdida. Desafortunadamente este es el paso clave pues la búsqueda podría resultar muy complicada y esta es la principal razón por la que este meta-algoritmo es difícil de implementar. En lo personal no conozco ninguna implementación en Python de lo anterior.
AnyBoost: los teoremas
Desafortunadamente muchos de los algoritmos utilizados en Machine Learning no tienen ninguna garantía teórica de convergencia y por lo tanto su uso está basado en resultados empíricos positivos.
De acuerdo a lo que yo conozco, no existen resultados que prueben que los algoritmos implementados en LightGBM, CatBoost o XGBoost converjan o que no se atoren en mínimos locales. El caso de AdaBoost puede demostrarse que es un caso particular de AnyBoost por lo cual es posible utilizar los teoremas de convergencia para este algoritmo.
Para el caso de AnyBoost en el artículo Functional Gradient Techniques for Combining Hypotheses se demuestra que bajo condiciones no muy restrictivas para la función de pérdida y la familia de hipótesis donde se busca a f, es posible garantizar la convergencia en el límite de este algoritmo y además cualquier punto de acumulación del algoritmo será un mínimo global.
¿Dónde aprender Machine Learning?
En el Colegio de Matemáticas Bourbaki enseñamos con detalle las matemáticas y los usos de las redes neuronales profundas, les invirtamos a revisar nuestra oferta académica para elegir el curso adecuado.
- Track de Ciencia de Datos. (49 semanas).
- Machine Learning & AI for the Working Analyst ( 12 semanas).
- Matemáticas para Ciencia de Datos ( 24 semanas).
- Especialización en Deep Learning. (12 semanas).
- Track de Finanzas Cuantitativas (49 semanas)
- Aplicaciones Financieras De Machine Learning E IA ( 12 semanas).
- Las matemáticas de los mercados financieros (24 semanas).
- Deep Learning for Finance (12 semanas).
