BrownBoost

BrownBoost es un algoritmo de boosting que puede ser robusto ante conjuntos de datos ruidosos . BrownBoost es una versión adaptativa del algoritmo boost by major . Como ocurre con todos los algoritmos de boosting, BrownBoost se utiliza junto con otros métodos de aprendizaje automático . BrownBoost fue introducido por Yoav Freund en 2001. ^{[ 1 ]}

AdaBoost funciona bien en una variedad de conjuntos de datos; sin embargo, se puede demostrar que no funciona bien en conjuntos de datos ruidosos. ^{[ 2 ]} Esto se debe a que AdaBoost se centra en ejemplos que se clasifican erróneamente de forma repetida. En contraste, BrownBoost efectivamente "se da por vencido" con los ejemplos que se clasifican erróneamente de forma repetida. La suposición central de BrownBoost es que los ejemplos ruidosos serán etiquetados erróneamente de forma repetida por las hipótesis débiles y los ejemplos no ruidosos serán etiquetados correctamente con la suficiente frecuencia como 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 a partir de los ejemplos no ruidosos, el error de generalización del clasificador final puede ser mucho mejor que si se aprende a partir de ejemplos ruidosos y no ruidosos.

El usuario del algoritmo puede configurar el margen de error tolerable en el conjunto de entrenamiento. Así, si el conjunto de entrenamiento es ruidoso (por ejemplo, si se supone que el 10 % de los ejemplos están mal etiquetados), se puede indicar al algoritmo que acepte un margen de error del 10 %. Dado que los ejemplos ruidosos pueden ignorarse, solo los ejemplos verdaderos contribuirán al proceso de aprendizaje.

BrownBoost utiliza una función de pérdida potencial no convexa , por lo que no se ajusta al marco de AdaBoost . La optimización no convexa proporciona un método para evitar el sobreajuste en conjuntos de datos ruidosos. Sin embargo, a diferencia de los algoritmos de boosting que minimizan analíticamente una función de pérdida convexa (por ejemplo, AdaBoost y LogitBoost ), BrownBoost resuelve un sistema de dos ecuaciones con dos incógnitas mediante métodos numéricos estándar.

El único parámetro de BrownBoost (${\displaystyle c}$en el algoritmo) es el "tiempo" que tarda en ejecutarse el algoritmo. La teoría de BrownBoost establece que cada hipótesis requiere una cantidad variable de tiempo (${\displaystyle t}$en el algoritmo) que está directamente relacionado con el peso dado a la hipótesis${\displaystyle \alpha }$El parámetro de tiempo en BrownBoost es análogo al número de iteraciones.${\displaystyle T}$en AdaBoost.

Un valor mayor de${\displaystyle c}$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${\displaystyle c}$Esto significa que BrownBoost tratará los datos como más ruidosos y descartará más ejemplos.

Durante cada iteración del algoritmo, se selecciona una hipótesis con alguna ventaja sobre la adivinación aleatoria. El peso de esta hipótesis${\displaystyle \alpha }$y el "tiempo transcurrido"${\displaystyle t}$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${\displaystyle \alpha }$y pasó el tiempo${\displaystyle t}$). 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 artículo original de Freund). Una vez resueltas estas ecuaciones, los márgenes de cada ejemplo (${\displaystyle r_{i}(x_{j})}$en el algoritmo) y la cantidad de tiempo restante${\displaystyle s}$se actualizan adecuadamente. Este proceso se repite hasta que no quede tiempo.

El potencial inicial se define como${\displaystyle {\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}({\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})}$. Dado que una restricción de cada iteración es que el potencial se mantenga constante, el potencial final es${\displaystyle {\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}(r_{i}(x_{j})/{\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})}$Por lo tanto, es probable que el error final sea cercano .${\displaystyle 1-{\mbox{erf}}({\sqrt {c}})}$Sin embargo, la función potencial final no es la función de error de pérdida 0-1 . Para que el error final sea exactamente ${\displaystyle 1-{\mbox{erf}}({\sqrt {c}})}$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 boosting. Esto aún no se ha tratado en la literatura ni se incluye en la definición del algoritmo que se presenta 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 demás algoritmos de boosting.

Aporte:

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

Inicializar:

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

Mientras${\displaystyle s>0}$:

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

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

En los resultados experimentales preliminares con conjuntos de datos ruidosos, BrownBoost superó el error de generalización de AdaBoost ; sin embargo, LogitBoost tuvo un rendimiento similar al de BrownBoost. ^{[ 4 ]} Una implementación de BrownBoost se puede encontrar en el software de código abierto JBoost .

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

• JBoost