BrownBoost es un algoritmo de impulso que puede ser robusto para conjuntos de datos ruidosos. BrownBoost es una versión adaptativa del algoritmo de impulso por mayoría . Como ocurre con todos los algoritmos de impulso , BrownBoost se utiliza junto con otros métodos de aprendizaje automático . BrownBoost fue introducido por Yoav Freund en 2001. [1]
Motivación
AdaBoost funciona bien en una variedad de conjuntos de datos; sin embargo, se puede demostrar que AdaBoost no funciona bien en conjuntos de datos ruidosos. [2] Este es el resultado del enfoque de AdaBoost en ejemplos que se clasifican erróneamente repetidamente. En contraste, BrownBoost efectivamente "se da por vencido" en los ejemplos que se clasifican erróneamente repetidamente. La suposición central de BrownBoost es que los ejemplos ruidosos serán etiquetados erróneamente repetidamente por las hipótesis débiles y los ejemplos no ruidosos se etiquetarán correctamente con la frecuencia suficiente para no "renunciar a ellos". Por lo tanto, sólo se "renunciará" a los ejemplos ruidosos, mientras que los ejemplos no ruidosos contribuirán al clasificador final. A su vez, si el clasificador final se aprende de los ejemplos no ruidosos, el error de generalización del clasificador final puede ser mucho mejor que si se aprende de los ejemplos ruidosos y no ruidosos.
El usuario del algoritmo puede establecer la cantidad de error que se tolerará en el conjunto de entrenamiento. Por lo tanto, si el conjunto de entrenamiento es ruidoso (digamos que se supone que el 10% de todos los ejemplos están mal etiquetados), se le puede decir al amplificador que acepte una tasa de error del 10%. Dado que los ejemplos ruidosos pueden ignorarse, solo los ejemplos verdaderos contribuirán al proceso de aprendizaje.
Descripción del algoritmo
BrownBoost utiliza una función de pérdida potencial no convexa, por lo que no encaja en el marco de AdaBoost . La optimización no convexa proporciona un método para evitar el sobreajuste de conjuntos de datos ruidosos. Sin embargo, a diferencia de los algoritmos de impulso que minimizan analíticamente una función de pérdida convexa (por ejemplo, AdaBoost y LogitBoost ), BrownBoost resuelve un sistema de dos ecuaciones y dos incógnitas utilizando métodos numéricos estándar.
El único parámetro de BrownBoost (en el algoritmo) es el "tiempo" en que se ejecuta el algoritmo. La teoría de BrownBoost establece que cada hipótesis toma una cantidad variable de tiempo ( en el algoritmo) que está directamente relacionado con el peso dado a la hipótesis . El parámetro de tiempo en BrownBoost es análogo al número de iteraciones en AdaBoost.
Un mayor valor de significa que BrownBoost tratará los datos como si fueran menos ruidosos y, por lo tanto, renunciará a menos ejemplos. Por el contrario, un valor menor de significa que BrownBoost tratará los datos como más ruidosos y renunciará a más ejemplos.
Durante cada iteración del algoritmo, se selecciona una hipótesis con alguna ventaja sobre la conjetura aleatoria. El peso de esta hipótesis y la "cantidad de tiempo transcurrido" durante la iteración se resuelven simultáneamente en un sistema de dos ecuaciones no lineales (1. hipótesis no correlacionadas con ponderaciones de ejemplo y 2. mantienen el potencial constante) con dos incógnitas (ponderación de hipótesis y paso el tiempo ). Esto se puede resolver mediante bisección (como se implementa en el paquete de software JBoost ) o el método de Newton (como se describe en el documento original de Freund). Una vez resueltas estas ecuaciones, los márgenes de cada ejemplo ( en el algoritmo) y la cantidad de tiempo restante se actualizan adecuadamente. Este proceso se repite hasta que no queda tiempo.
El potencial inicial se define como . Dado que una restricción de cada iteración es que el potencial se mantenga constante, el potencial final es. Por lo tanto, es probable que el error final esté cerca. Sin embargo, la función de potencial final no es la función de error de pérdida 0-1. Para que el error final sea exactamente, la varianza de la función de pérdida debe disminuir linealmente con el tiempo para formar la función de pérdida 0-1 al final de las iteraciones de impulso. Esto aún no se discute en la literatura y no está en la definición del algoritmo a continuación.
El clasificador final es una combinación lineal de hipótesis débiles y se evalúa de la misma manera que la mayoría de los otros algoritmos de impulso.
Definición del algoritmo de aprendizaje BrownBoost
Aporte:
- ejemplos de entrenamiento dónde
- El parámetro
Inicializar:
- . (El valor de es la cantidad de tiempo que queda en el juego)
- . El valor de es el margen en la iteración por ejemplo .
Tiempo :
- Establezca los pesos de cada ejemplo: , dónde es el margen del ejemplo
- Encuentra un clasificador tal que
- Encuentra valores que satisfacen la ecuación:
.
(Tenga en cuenta que esto es similar a la condiciónestablecido por Schapire y Singer. [3] En esta configuración, estamos encontrando numéricamente el tal que .)
Esta actualización está sujeta a la restricción
,
donde es la pérdida potencial de un punto con margen - Actualice los márgenes para cada ejemplo:
- Actualiza el tiempo restante:
Producción:
Resultados empíricos
En resultados experimentales preliminares con conjuntos de datos ruidosos, BrownBoost superó el error de generalización de AdaBoost ; sin embargo, LogitBoost funcionó tan bien como BrownBoost. [4] Se puede encontrar una implementación de BrownBoost en el software de código abierto JBoost .
Ver también
Referencias
- ^ Yoav Freund. Una versión adaptativa del algoritmo de impulso por mayoría. Machine Learning, 43 (3): 293--318, junio de 2001.
- ^ Dietterich, TG, (2000). Una comparación experimental de tres métodos para construir conjuntos de árboles de decisión: ensacado, refuerzo y aleatorización. Aprendizaje automático, 40 (2) 139-158.
- ^ Robert Schapire y Yoram Singer. Impulso mejorado mediante predicciones con calificación de confianza. Journal of Machine Learning, Vol 37 (3), páginas 297-336. 1999
- ^ Ross A. McDonald, David J. Hand, Idris A. Eckley. Una comparación empírica de tres algoritmos de impulso en conjuntos de datos reales con ruido de clase artificial. Multiple Classifier Systems, En Series Lecture Notes in Computer Science, páginas 35-44, 2003.