Refuerzo marrón

Algoritmo de impulso

BrownBoost es un algoritmo de refuerzo que puede ser robusto ante conjuntos de datos ruidosos . BrownBoost es una versión adaptativa del algoritmo de refuerzo por mayoría . Como es el caso de todos los algoritmos de refuerzo, 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] Esto es resultado del enfoque de AdaBoost en ejemplos que se clasifican incorrectamente repetidamente. En contraste, BrownBoost efectivamente "se da por vencido" en los ejemplos que se clasifican incorrectamente repetidamente. El supuesto central de BrownBoost es que los ejemplos ruidosos serán etiquetados incorrectamente repetidamente por las hipótesis débiles y los ejemplos no ruidosos serán etiquetados correctamente con la frecuencia suficiente para no ser "abandonados". Por lo tanto, solo los ejemplos ruidosos serán "abandonados", 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 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 (por ejemplo, se supone que el 10 % de todos los ejemplos están mal etiquetados), se le puede indicar al amplificador que acepte una tasa de error del 10 %. Dado que los ejemplos ruidosos se pueden ignorar, solo los ejemplos verdaderos contribuirán al proceso de aprendizaje.

Descripción del algoritmo

BrownBoost utiliza una función de pérdida de 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 optimización 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" que el algoritmo se ejecuta. La teoría de BrownBoost establece que cada hipótesis toma una cantidad variable de tiempo ( en el algoritmo) que está directamente relacionada 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. ${\displaystyle c}$ ${\displaystyle t}$ ${\displaystyle \alpha }$ ${\displaystyle T}$

Un valor mayor de significa que BrownBoost tratará los datos como si fueran menos ruidosos y, por lo tanto, dejará de lado menos ejemplos. Por el contrario, un valor menor de significa que BrownBoost tratará los datos como si fueran más ruidosos y dejará de lado más ejemplos. ${\displaystyle c}$ ${\displaystyle c}$

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 correlacionada con respecto a los pesos del ejemplo y 2. mantener el potencial constante) con dos incógnitas (peso de la hipótesis y tiempo transcurrido ). Esto se puede resolver por bisección (como se implementa en el paquete de software JBoost) o por el método de Newton (como se describe en el artículo original de Freund). Una vez que se resuelven 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 quede tiempo. ${\displaystyle \alpha }$ ${\displaystyle t}$ ${\displaystyle \alpha }$ ${\displaystyle t}$ ${\displaystyle r_{i}(x_{j})}$ ${\displaystyle s}$

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 de . 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 respecto al tiempo para formar la función de pérdida 0-1 al final de las iteraciones de refuerzo. Esto aún no se analiza en la literatura y no está en la definición del algoritmo a continuación. ${\displaystyle {\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}({\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})}$ ${\displaystyle {\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}(r_{i}(x_{j})/{\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})}$ ${\displaystyle 1-{\mbox{erf}}({\sqrt {c}})}$ ${\displaystyle 1-{\mbox{erf}}({\sqrt {c}})}$

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 demás algoritmos de refuerzo.

Definición del algoritmo de aprendizaje BrownBoost

Aporte:

• ${\displaystyle m}$ejemplos de entrenamiento donde ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})}$ ${\displaystyle x_{j}\in X,\,y_{j}\in Y=\{-1,+1\}}$
• El parámetro ${\displaystyle c}$

Inicializar:

• ${\displaystyle s=c}$. (El valor de es la cantidad de tiempo restante en el juego) ${\displaystyle s}$
• ${\displaystyle r_{i}(x_{j})=0}$   ${\displaystyle \forall j}$. El valor de es el margen en la iteración, por ejemplo . ${\displaystyle r_{i}(x_{j})}$ ${\displaystyle i}$ ${\displaystyle x_{j}}$

Mientras : ${\displaystyle s>0}$

• Establezca los pesos de cada ejemplo: , donde es el margen del ejemplo ${\displaystyle W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}}$ ${\displaystyle r_{i}(x_{j})}$ ${\displaystyle x_{j}}$
• Encuentra un clasificador tal que ${\displaystyle h_{i}:X\to \{-1,+1\}}$ ${\displaystyle \sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0}$
• Encuentre valores que satisfagan la ecuación: . (Tenga en cuenta que esto es similar a la condición establecida por Schapire y Singer. ^[3] En este contexto, estamos encontrando numéricamente el tal que ). Esta actualización está sujeta a la restricción , donde es la pérdida potencial para un punto con margen ${\displaystyle \alpha ,t}$
  ${\displaystyle \sum _{j}h_{i}(x_{j})y_{j}e^{-{\frac {(r_{i}(x_{j})+\alpha h_{i}(x_{j})y_{j}+s-t)^{2}}{c}}}=0}$
  ${\displaystyle E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0}$ ${\displaystyle W_{i+1}=\exp \left({\frac {\cdots }{\cdots }}\right)}$ ${\displaystyle E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0}$
  
  ${\displaystyle \sum \left(\Phi \left(r_{i}(x_{j})+\alpha h(x_{j})y_{j}+s-t\right)-\Phi \left(r_{i}(x_{j})+s\right)\right)=0}$
  ${\displaystyle \Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})}$ ${\displaystyle r_{i}(x_{j})}$
• Actualice los márgenes para cada ejemplo: ${\displaystyle r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}}$
• Actualizar el tiempo restante: ${\displaystyle s=s-t}$

Producción: ${\displaystyle H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)}$

Resultados empíricos

En resultados experimentales preliminares con conjuntos de datos ruidosos, BrownBoost superó el error de generalización de AdaBoost ; sin embargo, LogitBoost tuvo un desempeño tan bueno como BrownBoost. ^[4] Se puede encontrar una implementación de BrownBoost en el software de código abierto JBoost.

Véase también

• Impulsando
• AdaBoost
• Árboles de decisión alternados

Referencias

1. Yoav Freund. Una versión adaptativa del algoritmo Boost by Majority. Machine Learning, 43(3):293--318, junio de 2001.
2. Dietterich, TG, (2000). Una comparación experimental de tres métodos para construir conjuntos de árboles de decisión: bagging, boosting y randomización. Machine Learning, 40 (2) 139-158.
3. Robert Schapire y Yoram Singer. Mejora del impulso mediante predicciones basadas en la confianza. Journal of Machine Learning, vol. 37(3), páginas 297-336. 1999
4. Ross A. McDonald, David J. Hand, Idris A. Eckley. Una comparación empírica de tres algoritmos de refuerzo en conjuntos de datos reales con ruido de clase artificial. Sistemas de clasificación múltiple, en la serie Lecture Notes in Computer Science, páginas 35-44, 2003.

Enlaces externos

• Impulso J