AdaBoost

AdaBoost (abreviatura de Ada ptive Boosting ) es un metaalgoritmo de clasificación estadística formulado por Yoav Freund y Robert Schapire en 1995, quienes ganaron el Premio Gödel en 2003 por su trabajo. Puede utilizarse junto con muchos tipos de algoritmos de aprendizaje para mejorar el rendimiento. La salida de múltiples clasificadores débiles se combina en una suma ponderada que representa la salida final del clasificador potenciado. Generalmente, AdaBoost se presenta para la clasificación binaria , aunque puede generalizarse a múltiples clases o intervalos acotados de valores reales . ^{[ 1 ] [ 2 ]}

AdaBoost es adaptativo en el sentido de que los modelos (aprendices) débiles subsiguientes se ajustan para corregir las instancias mal clasificadas por los modelos anteriores. En algunos problemas, puede ser menos propenso al sobreajuste que otros algoritmos de aprendizaje. Los aprendices individuales pueden ser débiles, pero siempre que el rendimiento de cada uno sea ligeramente superior al de una elección aleatoria, se puede demostrar que el modelo final converge hacia un aprendiz robusto.

Aunque AdaBoost se usa normalmente para combinar clasificadores base débiles (como árboles de decisión simples ), se ha demostrado que también combina eficazmente clasificadores base fuertes (como árboles de decisión más profundos ), produciendo un modelo aún más preciso. ^{[ 3 ]}

Cada algoritmo de aprendizaje tiende a adaptarse mejor a ciertos tipos de problemas que a otros, y normalmente tiene muchos parámetros y configuraciones diferentes que ajustar antes de lograr un rendimiento óptimo en un conjunto de datos . A AdaBoost (con árboles de decisión como aprendices débiles) se suele considerar el mejor clasificador listo para usar. ^{[ 4 ] [ 5 ]} Cuando se utiliza con el aprendizaje de árboles de decisión, la información recopilada en cada etapa del algoritmo AdaBoost sobre la "dificultad" relativa de cada muestra de entrenamiento se introduce en el algoritmo de crecimiento del árbol, de modo que los árboles posteriores tienden a centrarse en los ejemplos más difíciles de clasificar.

AdaBoost se refiere a un método particular de entrenamiento de un clasificador potenciado. Un clasificador potenciado es un clasificador de la forma $${\displaystyle F_{T}(x)=\sum _{t=1}^{T}f_{t}(x)}$$ donde cada${\displaystyle f_{t}}$es un aprendiz débil que toma un objeto${\displaystyle x}$Recibe como entrada un valor que indica la clase del objeto. Por ejemplo, en el problema de dos clases, el signo de la salida del clasificador débil identifica la clase del objeto predicha y el valor absoluto indica la confianza en esa clasificación.

Cada aprendiz débil produce una hipótesis de salida${\displaystyle h}$que fija una predicción${\displaystyle h(x_{i})}$para cada muestra en el conjunto de entrenamiento. En cada iteración${\displaystyle t}$Se selecciona un aprendiz débil y se le asigna un coeficiente.${\displaystyle \alpha _{t}}$de tal manera que el error total de entrenamiento${\displaystyle E_{t}}$del resultado${\displaystyle t}$-El clasificador potenciado de etapa se minimiza.

$${\displaystyle E_{t}=\sum _{i}E[F_{t-1}(x_{i})+\alpha _{t}h(x_{i})]}$$

Aquí${\displaystyle F_{t-1}(x)}$es el clasificador potenciado que se ha construido hasta la etapa anterior de entrenamiento y${\displaystyle f_{t}(x)=\alpha _{t}h(x)}$es el clasificador débil que se está considerando para su adición al clasificador final.

Esta derivación sigue a Rojas (2009): ^{[ 6 ]}

Supongamos que tenemos un conjunto de datos${\displaystyle \{(x_{1},y_{1}),\ldots ,(x_{N},y_{N})\}}$donde cada artículo${\displaystyle x_{i}}$tiene una clase asociada${\displaystyle y_{i}\in \{-1,1\}}$y un conjunto de clasificadores débiles${\displaystyle \{k_{1},\ldots ,k_{L}\}}$cada uno de los cuales produce una clasificación${\displaystyle k_{j}(x_{i})\in \{-1,1\}}$para cada artículo. Después del${\displaystyle (m-1)}$En la iteración -a, nuestro clasificador potenciado es una combinación lineal de los clasificadores débiles de la forma: $${\displaystyle C_{(m-1)}(x_{i})=\alpha _{1}k_{1}(x_{i})+\cdots +\alpha _{m-1}k_{m-1}(x_{i}),}$$ donde la clase será el signo de${\displaystyle C_{(m-1)}(x_{i})}$. En el${\displaystyle m}$-en la iteración queremos extender esto a un clasificador potenciado mejor agregando otro clasificador débil.${\displaystyle k_{m}}$, con otro peso${\displaystyle \alpha _{m}}$: $${\displaystyle C_{m}(x_{i})=C_{(m-1)}(x_{i})+\alpha _{m}k_{m}(x_{i})}$$

Por lo tanto, queda por determinar qué clasificador débil es la mejor opción para${\displaystyle k_{m}}$y cuál es su peso${\displaystyle \alpha _{m}}$debería ser. Definimos el error total.${\displaystyle E}$de${\displaystyle C_{m}}$como la suma de su pérdida exponencial en cada punto de datos, dada de la siguiente manera: $${\displaystyle E=\sum _{i=1}^{N}e^{-y_{i}C_{m}(x_{i})}=\sum _{i=1}^{N}e^{-y_{i}C_{(m-1)}(x_{i})}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}}$$

Alquiler${\displaystyle w_{i}^{(1)}=1}$y${\displaystyle w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}}$para${\displaystyle m>1}$, tenemos: $${\displaystyle E=\sum _{i=1}^{N}w_{i}^{(m)}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}}$$

Podemos dividir esta suma entre aquellos puntos de datos que están correctamente clasificados por${\displaystyle k_{m}}$(entonces${\displaystyle y_{i}k_{m}(x_{i})=1}$) y aquellos que están mal clasificados (por lo tanto${\displaystyle y_{i}k_{m}(x_{i})=-1}$): $${\displaystyle {\begin{aligned}E&=\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}}\\&=\sum _{i=1}^{N}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}\left(e^{\alpha _{m}}-e^{-\alpha _{m}}\right)\end{aligned}}}$$

Dado que la única parte del lado derecho de esta ecuación que depende de${\displaystyle k_{m}}$es${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$, vemos que el${\displaystyle k_{m}}$que minimiza${\displaystyle E}$es el que está en el conjunto${\displaystyle \{k_{1},\ldots ,k_{L}\}}$que minimiza${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$[suponiendo que${\displaystyle \alpha _{m}>0}$], es decir, el clasificador débil con el menor error ponderado (con pesos${\displaystyle w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}}$).

Para determinar el peso deseado${\displaystyle \alpha _{m}}$que minimiza${\displaystyle E}$con el${\displaystyle k_{m}}$que acabamos de determinar, diferenciamos: $${\displaystyle {\frac {dE}{d\alpha _{m}}}={\frac {d(\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}})}{d\alpha _{m}}}}$$

El valor de${\displaystyle \alpha _{m}}$que minimiza la expresión anterior es: $${\displaystyle \alpha _{m}={\frac {1}{2}}\ln \left({\frac {\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}}\right)}$$

Calculamos que la tasa de error ponderada del clasificador débil es${\displaystyle \epsilon _{m}={\frac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{i=1}^{N}w_{i}^{(m)}}}}$, por lo tanto, se deduce que: $${\displaystyle \alpha _{m}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{m}}{\epsilon _{m}}}\right)}$$ que es la función logit negativa multiplicada por 0,5. Debido a la convexidad de${\displaystyle E}$como función de${\displaystyle \alpha _{m}}$, esta nueva expresión para${\displaystyle \alpha _{m}}$proporciona el mínimo global de la función de pérdida.

Nota: Esta derivación solo se aplica cuando${\displaystyle k_{m}(x_{i})\in \{-1,1\}}$, aunque puede ser una buena suposición inicial en otros casos, como cuando el aprendiz débil está sesgado (${\displaystyle k_{m}(x)\in \{a,b\},a\neq -b}$), tiene múltiples hojas (${\displaystyle k_{m}(x)\in \{a,b,\dots ,n\}}$) o es alguna otra función${\displaystyle k_{m}(x)\in \mathbb {R} }$.

Así hemos derivado el algoritmo AdaBoost: En cada iteración, elija el clasificador.${\displaystyle k_{m}}$, lo que minimiza el error ponderado total${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$, utilice esto para calcular la tasa de error${\displaystyle \epsilon _{m}={\frac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{i=1}^{N}w_{i}^{(m)}}}}$, utilice esto para calcular el peso${\displaystyle \alpha _{m}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{m}}{\epsilon _{m}}}\right)}$y, finalmente, utilizar esto para mejorar el clasificador potenciado.${\displaystyle C_{m-1}}$a${\displaystyle C_{m}=C_{(m-1)}+\alpha _{m}k_{m}}$.

Boosting es una forma de regresión lineal en la que las características de cada muestra${\displaystyle x_{i}}$son los resultados de algún aprendiz débil${\displaystyle h}$aplicado a${\displaystyle x_{i}}$.

Mientras que la regresión intenta ajustar${\displaystyle F(x)}$a${\displaystyle y(x)}$con la mayor precisión posible sin pérdida de generalización, utilizando típicamente el método de mínimos cuadrados.${\displaystyle E(f)=(y(x)-f(x))^{2}}$, mientras que la función de error de AdaBoost${\displaystyle E(f)=e^{-y(x)f(x)}}$tiene en cuenta el hecho de que solo se utiliza el signo del resultado final, por lo tanto${\displaystyle |F(x)|}$puede ser mucho mayor que 1 sin aumentar el error. Sin embargo, el aumento exponencial del error para la muestra${\displaystyle x_{i}}$como${\displaystyle -y(x_{i})f(x_{i})}$aumentan, lo que provoca que se asignen ponderaciones excesivas a los valores atípicos.

Una característica de la elección de la función de error exponencial es que el error del modelo aditivo final es el producto del error de cada etapa, es decir,${\displaystyle e^{\sum _{m}-y_{i}f_{m}(x_{i})}=\prod _{m}e^{-y_{i}f_{m}(x_{i})}}$. Por lo tanto, se puede ver que la actualización de peso en el algoritmo AdaBoost es equivalente a recalcular el error en${\displaystyle F_{t}(x)}$después de cada etapa.

Existe mucha flexibilidad en la elección de la función de pérdida. Siempre que la función de pérdida sea monótona y continuamente diferenciable , el clasificador siempre se orientará hacia soluciones más puras. ^{[ 7 ]} Zhang (2004) proporciona una función de pérdida basada en mínimos cuadrados, una función de pérdida de Huber modificada : $${\displaystyle \phi (y,f(x))={\begin{cases}-4yf(x)&{\text{if }}yf(x)<-1,\\(yf(x)-1)^{2}&{\text{if }}-1\leq yf(x)\leq 1.\\0&{\text{if }}yf(x)>1\end{cases}}}$$

Esta función se comporta mejor que LogitBoost para${\displaystyle f(x)}$Cercano a 1 o -1, no penaliza las predicciones "excesivamente confiadas" (${\displaystyle yf(x)>1}$), a diferencia de los mínimos cuadrados no modificados, y solo penaliza linealmente las muestras mal clasificadas con una confianza mayor que 1, en lugar de cuadráticamente o exponencialmente, y por lo tanto es menos susceptible a los efectos de los valores atípicos.

El boosting puede verse como la minimización de una función de pérdida convexa sobre un conjunto convexo de funciones. ^{[ 8 ]} Específicamente, la pérdida que minimiza AdaBoost es la pérdida exponencial. $${\displaystyle \sum _{i}\phi (i,y,f)=\sum _{i}e^{-y_{i}f(x_{i})},}$$ mientras que LogitBoost realiza una regresión logística, minimizando $${\displaystyle \sum _{i}\phi (i,y,f)=\sum _{i}\ln \left(1+e^{-y_{i}f(x_{i})}\right).}$$

En la analogía del descenso de gradiente, la salida del clasificador para cada punto de entrenamiento se considera un punto${\displaystyle \left(F_{t}(x_{1}),\dots ,F_{t}(x_{n})\right)}$en un espacio n-dimensional, donde cada eje corresponde a una muestra de entrenamiento, cada aprendiz débil${\displaystyle h(x)}$corresponde a un vector de orientación y longitud fijas, y el objetivo es alcanzar el punto objetivo.${\displaystyle (y_{1},\dots ,y_{n})}$(o cualquier región donde el valor de la función de pérdida${\displaystyle E_{T}(x_{1},\dots ,x_{n})}$es menor que el valor en ese punto), en el menor número de pasos. Por lo tanto, los algoritmos AdaBoost realizan Cauchy (encontrar${\displaystyle h(x)}$con la pendiente más pronunciada, elige${\displaystyle \alpha }$para minimizar el error de prueba) o Newton (elegir algún punto objetivo, encontrar${\displaystyle \alpha h(x)}$que trae${\displaystyle F_{t}}$más cercano a ese punto) optimización del error de entrenamiento.

Con:

• Muestras${\displaystyle x_{1}\dots x_{n}}$
• Resultados deseados${\displaystyle y_{1}\dots y_{n},y\in \{-1,1\}}$
• pesos iniciales${\displaystyle w_{1,1}\dots w_{n,1}}$empezar a${\displaystyle {\frac {1}{n}}}$
• Función de error${\displaystyle E(f(x),y_{i})=e^{-y_{i}f(x_{i})}}$
• alumnos con dificultades${\displaystyle h\colon x\rightarrow \{-1,1\}}$

Para${\displaystyle t}$en${\displaystyle 1\dots T}$:

• Elegir${\displaystyle h_{t}(x)}$:
  • Encuentra alumnos con dificultades de aprendizaje${\displaystyle h_{t}(x)}$que minimiza${\displaystyle \epsilon _{t}}$, el error de suma ponderada para puntos mal clasificados${\displaystyle \epsilon _{t}=\sum _{\stackrel {i=1}{h_{t}(x_{i})\neq y_{i}}}^{n}w_{i,t}}$
  • Elegir${\displaystyle \alpha _{t}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{t}}{\epsilon _{t}}}\right)}$
• Agregar al conjunto:
  • ${\displaystyle F_{t}(x)=F_{t-1}(x)+\alpha _{t}h_{t}(x)}$
• Actualizar pesos:
  • ${\displaystyle w_{i,t+1}=w_{i,t}e^{-y_{i}\alpha _{t}h_{t}(x_{i})}}$para${\displaystyle i}$en${\displaystyle 1\dots n}$
  • Renormalizar${\displaystyle w_{i,t+1}}$de tal manera que${\displaystyle \sum _{i}w_{i,t+1}=1}$
  • (Nota: Se puede demostrar que${\displaystyle {\frac {\sum _{h_{t}(x_{i})=y_{i}}w_{i,t+1}}{\sum _{h_{t}(x_{i})\neq y_{i}}w_{i,t+1}}}={\frac {\sum _{h_{t}(x_{i})=y_{i}}w_{i,t}}{\sum _{h_{t}(x_{i})\neq y_{i}}w_{i,t}}}}$en cada paso, lo que puede simplificar el cálculo de los nuevos pesos.)

• Agregación Bootstrap
• CoBoosting
• BrownBoost
• Potenciación de gradiente
• Método de actualización de peso multiplicativo §  Algoritmo AdaBoost