AdaBoost

Algoritmo de clasificación basado en refuerzo adaptativo

AdaBoost (abreviatura de Adaptive 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. Se puede utilizar junto con muchos tipos de algoritmos de aprendizaje para mejorar el rendimiento. La salida de múltiples aprendices débiles se combina en una suma ponderada que representa la salida final del clasificador potenciado. Por lo general, AdaBoost se presenta para la clasificación binaria , aunque se puede generalizar a múltiples clases o intervalos acotados de valores reales . ^{[1] [2]}

AdaBoost es adaptativo en el sentido de que los aprendices débiles subsiguientes (modelos) se ajustan en favor de las instancias clasificadas incorrectamente por los modelos anteriores. En algunos problemas, puede ser menos susceptible al sobreajuste que otros algoritmos de aprendizaje. Los aprendices individuales pueden ser débiles, pero siempre que el rendimiento de cada uno sea ligeramente mejor que la suposición aleatoria, se puede demostrar que el modelo final converge hacia un aprendiz fuerte.

Aunque AdaBoost se utiliza normalmente para combinar aprendices de base débiles (como árboles de decisión ), se ha demostrado que también combina de forma eficaz aprendices de base fuertes (como árboles de decisión más profundos ), lo que produce un modelo aún más preciso. ^[3]

Cada algoritmo de aprendizaje tiende a adaptarse mejor a algunos 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 . AdaBoost (con árboles de decisión como aprendices débiles) a menudo se conoce como 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 "dureza" relativa de cada muestra de entrenamiento se introduce en el algoritmo de crecimiento de árboles de modo que los árboles posteriores tienden a centrarse en ejemplos más difíciles de clasificar.

Capacitación

AdaBoost se refiere a un método particular de entrenamiento de un clasificador mejorado. Un clasificador mejorado es un clasificador de la forma donde cada uno es un aprendiz débil que toma un objeto como entrada y devuelve un valor que indica la clase del objeto. Por ejemplo, en el problema de dos clases, el signo de la salida del aprendiz débil identifica la clase de objeto predicha y el valor absoluto brinda la confianza en esa clasificación. De manera similar, el clasificador -ésimo es positivo si la muestra está en una clase positiva y negativo en caso contrario. $${\displaystyle F_{T}(x)=\sum _{t=1}^{T}f_{t}(x)}$$ ${\displaystyle f_{t}}$ ${\displaystyle x}$ ${\displaystyle t}$

Cada aprendiz débil produce una hipótesis de salida que fija una predicción para cada muestra en el conjunto de entrenamiento. En cada iteración , se selecciona un aprendiz débil y se le asigna un coeficiente de modo que se minimice el error de entrenamiento total del clasificador mejorado de la etapa resultante. ${\displaystyle h}$ ${\displaystyle h(x_{i})}$ ${\displaystyle t}$ ${\displaystyle \alpha _{t}}$ ${\displaystyle E_{t}}$ ${\displaystyle t}$

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

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

Ponderación

En cada iteración del proceso de entrenamiento, se asigna un peso a cada muestra del conjunto de entrenamiento igual al error actual de esa muestra. Estos pesos se pueden utilizar en el entrenamiento del alumno débil. Por ejemplo, se pueden crear árboles de decisión que favorezcan la división de conjuntos de muestras con pesos elevados. ${\displaystyle w_{i,t}}$ ${\displaystyle E(F_{t-1}(x_{i}))}$

Derivación

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

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

Por lo tanto, queda determinar qué clasificador débil es la mejor opción para , y cuál debería ser su peso . Definimos el error total de como la suma de su pérdida exponencial en cada punto de datos, dada de la siguiente manera: ${\displaystyle k_{m}}$ ${\displaystyle \alpha _{m}}$ ${\displaystyle E}$ ${\displaystyle C_{m}}$ $${\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})}}$$

Dejando y para , tenemos: ${\displaystyle w_{i}^{(1)}=1}$ ${\displaystyle w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}}$ ${\displaystyle m>1}$ $${\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 (por lo que ) y aquellos que están mal clasificados (por lo que ): ${\displaystyle k_{m}}$ ${\displaystyle y_{i}k_{m}(x_{i})=1}$ ${\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 es , vemos que el que minimiza es el del conjunto que minimiza [suponiendo que ], es decir, el clasificador débil con el error ponderado más bajo (con pesos ). ${\displaystyle k_{m}}$ ${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$ ${\displaystyle k_{m}}$ ${\displaystyle E}$ ${\displaystyle \{k_{1},\ldots ,k_{L}\}}$ ${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$ ${\displaystyle \alpha _{m}>0}$ ${\displaystyle w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}}$

Para determinar el peso deseado que se minimiza con el que acabamos de determinar, diferenciamos: ${\displaystyle \alpha _{m}}$ ${\displaystyle E}$ ${\displaystyle k_{m}}$ $${\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}}}}$$

Afortunadamente, el mínimo se produce al establecerlo en cero y, luego, al resolverlo, se obtiene lo siguiente: ${\displaystyle \alpha _{m}}$ $${\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)}$$

Prueba

$${\displaystyle {\frac {dE}{d\alpha _{m}}}=-\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}}=0}$$porque no depende de ${\displaystyle e^{-\alpha _{m}}}$ ${\displaystyle i}$ $${\displaystyle e^{-\alpha _{m}}\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}=e^{\alpha _{m}}\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$$ $${\displaystyle -\alpha _{m}+\ln \left(\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}\right)=\alpha _{m}+\ln \left(\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}\right)}$$ $${\displaystyle -2\alpha _{m}=\ln \left({\dfrac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}}\right)}$$ $${\displaystyle \alpha _{m}=-{\dfrac {1}{2}}\ln \left({\dfrac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}}\right)}$$ $${\displaystyle \alpha _{m}={\dfrac {1}{2}}\ln \left({\dfrac {\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 , por lo que se deduce que: que es la función logit negativa multiplicada por 0,5. Debido a la convexidad de como función de , esta nueva expresión para da el mínimo global de la función de pérdida. ${\displaystyle \epsilon _{m}={\frac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{i=1}^{N}w_{i}^{(m)}}}}$ $${\displaystyle \alpha _{m}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{m}}{\epsilon _{m}}}\right)}$$ ${\displaystyle E}$ ${\displaystyle \alpha _{m}}$ ${\displaystyle \alpha _{m}}$

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

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

Comprensión estadística del impulso

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

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

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, . De este modo, se puede observar que la actualización de peso en el algoritmo AdaBoost es equivalente a recalcular el error después de cada etapa. ${\displaystyle e^{\sum _{i}-y_{i}f(x_{i})}=\prod _{i}e^{-y_{i}f(x_{i})}}$ ${\displaystyle F_{t}(x)}$

Se permite una gran flexibilidad en la elección de la función de pérdida. Mientras la función de pérdida sea monótona y continuamente diferenciable , el clasificador siempre se orienta 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 valores cercanos a 1 o -1, no penaliza las predicciones "excesivamente confiadas" ( ), a diferencia de los mínimos cuadrados no modificados, y solo penaliza las muestras mal clasificadas con una confianza mayor a 1 de forma lineal, en lugar de cuadrática o exponencial, y por lo tanto es menos susceptible a los efectos de los valores atípicos. ${\displaystyle f(x)}$ ${\displaystyle yf(x)>1}$

Impulso como descenso de gradiente

El impulso se puede ver 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 se minimiza con AdaBoost es la pérdida exponencial , mientras que LogitBoost realiza una regresión logística, minimizando $${\displaystyle \sum _{i}\phi (i,y,f)=\sum _{i}e^{-y_{i}f(x_{i})},}$$ $${\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 en un espacio n-dimensional, donde cada eje corresponde a una muestra de entrenamiento, cada aprendiz débil corresponde a un vector de orientación y longitud fijas, y el objetivo es alcanzar el punto objetivo (o cualquier región donde el valor de la función de pérdida sea menor que el valor en ese punto), en la menor cantidad de pasos. Por lo tanto, los algoritmos AdaBoost realizan una optimización de Cauchy (encuentra con el gradiente más pronunciado, elige minimizar el error de prueba) o Newton (elige un punto objetivo, encuentra el que se acerca más a ese punto) del error de entrenamiento. ${\displaystyle \left(F_{t}(x_{1}),\dots ,F_{t}(x_{n})\right)}$ ${\displaystyle h(x)}$ ${\displaystyle (y_{1},\dots ,y_{n})}$ ${\displaystyle E_{T}(x_{1},\dots ,x_{n})}$ ${\displaystyle h(x)}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha h(x)}$ ${\displaystyle F_{t}}$

Algoritmo de ejemplo (AdaBoost discreto)

Con:

• Muestras ${\displaystyle x_{1}\dots x_{n}}$
• Resultados deseados ${\displaystyle y_{1}\dots y_{n},y\in \{-1,1\}}$
• Pesos iniciales establecidos en ${\displaystyle w_{1,1}\dots w_{n,1}}$ ${\displaystyle {\frac {1}{n}}}$
• Función de error ${\displaystyle E(f(x),y_{i})=e^{-y_{i}f(x_{i})}}$
• Estudiantes débiles ${\displaystyle h\colon x\rightarrow \{-1,1\}}$

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

• Elegir : ${\displaystyle h_{t}(x)}$
  • Encuentre un alumno débil que minimice el error de suma ponderada para los puntos mal clasificados ${\displaystyle h_{t}(x)}$ ${\displaystyle \epsilon _{t}}$ ${\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)}$
• Añadir 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 en ${\displaystyle i}$ ${\displaystyle 1\dots n}$
  • Renormalizar de tal manera que ${\displaystyle w_{i,t+1}}$ ${\displaystyle \sum _{i}w_{i,t+1}=1}$
  • (Nota: Se puede demostrar esto en cada paso, lo que puede simplificar el cálculo de los nuevos pesos). ${\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}}}}$

Variantes

Auténtico AdaBoost

El resultado de los árboles de decisión es una estimación de probabilidad de clase , la probabilidad que se encuentra en la clase positiva. ^[7] Friedman, Hastie y Tibshirani derivan un minimizador analítico para algún error fijo (generalmente elegido utilizando el error de mínimos cuadrados ponderado): ${\displaystyle p(x)=P(y=1|x)}$ ${\displaystyle x}$ ${\displaystyle e^{-y\left(F_{t-1}(x)+f_{t}(p(x))\right)}}$ ${\displaystyle p(x)}$

${\displaystyle f_{t}(x)={\frac {1}{2}}\ln \left({\frac {x}{1-x}}\right)}$.

De este modo, en lugar de multiplicar la salida de todo el árbol por un valor fijo, cada nodo hoja se modifica para generar la mitad de la transformación logit de su valor anterior.

Impulso logístico

LogitBoost representa una aplicación de técnicas de regresión logística establecidas al método AdaBoost. En lugar de minimizar el error con respecto a y, se eligen estudiantes débiles para minimizar el error (mínimos cuadrados ponderados) de con respecto a donde ${\displaystyle f_{t}(x)}$ $${\displaystyle z_{t}={\frac {y^{*}-p_{t}(x)}{2p_{t}(x)(1-p_{t}(x))}},}$$ $${\displaystyle p_{t}(x)={\frac {e^{F_{t-1}(x)}}{e^{F_{t-1}(x)}+e^{-F_{t-1}(x)}}},}$$ $${\displaystyle w_{t}=p_{t}(x)(1-p_{t}(x))}$$ $${\displaystyle y^{*}={\frac {y+1}{2}}.}$$

Esta es la aproximación de Newton-Raphson del minimizador del error de log-verosimilitud en la etapa , y el alumno débil se elige como el alumno que mejor se aproxima mediante mínimos cuadrados ponderados. ${\displaystyle z_{t}}$ ${\displaystyle t}$ ${\displaystyle f_{t}}$ ${\displaystyle z_{t}}$

A medida que p se acerca a 1 o 0, el valor de se vuelve muy pequeño y el término z , que es grande para muestras mal clasificadas, puede volverse numéricamente inestable debido a errores de redondeo de precisión de la máquina. Esto se puede superar imponiendo algún límite al valor absoluto de z y al valor mínimo de  w ${\displaystyle p_{t}(x_{i})(1-p_{t}(x_{i}))}$

AdaBoost suave

Mientras que los algoritmos de boosting anteriores eligen con avidez, minimizando el error general de prueba tanto como sea posible en cada paso, GentleBoost presenta un tamaño de paso acotado. se elige para minimizar , y no se aplica ningún coeficiente adicional. Por lo tanto, en el caso en que un aprendiz débil exhibe un rendimiento de clasificación perfecto, GentleBoost elige exactamente igual a , mientras que los algoritmos de descenso más empinado intentan establecer . Las observaciones empíricas sobre el buen rendimiento de GentleBoost parecen respaldar la observación de Schapire y Singer de que permitir valores excesivamente grandes de puede conducir a un rendimiento de generalización deficiente. ^{[9] [10]} ${\displaystyle f_{t}}$ ${\displaystyle f_{t}}$ ${\textstyle \sum _{i}w_{t,i}(y_{i}-f_{t}(x_{i}))^{2}}$ ${\displaystyle f_{t}(x)=\alpha _{t}h_{t}(x)}$ ${\displaystyle y}$ ${\displaystyle \alpha _{t}=\infty }$ ${\displaystyle \alpha }$

Terminación anticipada

Una técnica para acelerar el procesamiento de clasificadores potenciados, la terminación temprana se refiere a probar cada objeto potencial solo con tantas capas del clasificador final como sea necesario para cumplir con un umbral de confianza, acelerando el cálculo para los casos en los que la clase del objeto se puede determinar fácilmente. Uno de estos esquemas es el marco de detección de objetos introducido por Viola y Jones: ^[11] en una aplicación con significativamente más muestras negativas que positivas, se entrena una cascada de clasificadores potenciados separados, la salida de cada etapa se sesga de tal manera que una fracción aceptablemente pequeña de muestras positivas se etiqueta incorrectamente como negativa, y todas las muestras marcadas como negativas después de cada etapa se descartan. Si el 50% de las muestras negativas se filtran en cada etapa, solo una cantidad muy pequeña de objetos pasaría por todo el clasificador, lo que reduce el esfuerzo de cálculo. Este método se ha generalizado desde entonces, con una fórmula proporcionada para elegir umbrales óptimos en cada etapa para lograr una tasa deseada de falsos positivos y falsos negativos. ^[12]

En el campo de las estadísticas, donde AdaBoost se aplica más comúnmente a problemas de dimensionalidad moderada, la detención temprana se utiliza como una estrategia para reducir el sobreajuste . ^[13] Un conjunto de validación de muestras se separa del conjunto de entrenamiento, el rendimiento del clasificador en las muestras utilizadas para el entrenamiento se compara con el rendimiento en las muestras de validación y el entrenamiento finaliza si se observa que el rendimiento en la muestra de validación disminuye incluso cuando el rendimiento en el conjunto de entrenamiento continúa mejorando.

Algoritmos totalmente correctivos

Para las versiones de descenso más pronunciado de AdaBoost, donde se elige en cada capa t para minimizar el error de prueba, se dice que la siguiente capa agregada es máximamente independiente de la capa t : ^[14] es poco probable elegir un aprendiz débil t+1 que sea similar al aprendiz t . Sin embargo, existe la posibilidad de que t+1 produzca información similar a alguna otra capa anterior. Los algoritmos totalmente correctivos, como LPBoost , optimizan el valor de cada coeficiente después de cada paso, de modo que las nuevas capas agregadas siempre sean máximamente independientes de cada capa anterior. Esto se puede lograr mediante retroajuste, programación lineal o algún otro método. ${\displaystyle \alpha _{t}}$

Poda

La poda es el proceso de eliminar clasificadores débiles de bajo rendimiento para mejorar la memoria y el costo de tiempo de ejecución del clasificador mejorado. Los métodos más simples, que pueden ser particularmente efectivos junto con un entrenamiento totalmente correctivo, son el recorte de peso o de margen: cuando el coeficiente, o la contribución al error total de prueba, de algún clasificador débil cae por debajo de un cierto umbral, ese clasificador se descarta. Margineantu y Dietterich ^[15] sugirieron un criterio alternativo para el recorte: los clasificadores débiles deben seleccionarse de manera que se maximice la diversidad del conjunto. Si dos aprendices débiles producen resultados muy similares, se puede mejorar la eficiencia eliminando uno de ellos y aumentando el coeficiente del aprendiz débil restante. ^[16]

Véase también

• Agregación de Bootstrap
• Impulso conjunto
• Refuerzo marrón
• Aumento de gradiente
• Método de actualización de peso multiplicativo § Algoritmo AdaBoost

Referencias

1. Freund, Yoav; Schapire, Robert E. (1995), Una generalización teórica de decisiones del aprendizaje en línea y una aplicación para impulsar el aprendizaje, Lecture Notes in Computer Science, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 23–37, doi :10.1007/3-540-59119-2_166, ISBN 978-3-540-59119-1, consultado el 24 de junio de 2022
2. Hastie, Trevor; Rosset, Saharon; Zhu, Ji; Zou, Hui (2009). "AdaBoost multiclase". Estadísticas y su interfaz . 2 (3): 349–360. doi : 10.4310/sii.2009.v2.n3.a8 . ISSN  1938-7989.
3. Wyner, Abraham J.; Olson, Matthew; Bleich, Justin; Mease, David (2017). "Explicación del éxito de AdaBoost y los bosques aleatorios como clasificadores de interpolación". Journal of Machine Learning Research . 18 (48): 1–33 . Consultado el 17 de marzo de 2022 .
4. Kégl, Balázs (20 de diciembre de 2013). "El regreso de AdaBoost.MH: árboles Hamming multiclase". arXiv : 1312.6086 [cs.LG].
5. Joglekar, Sachin. "adaboost – Sachin Joglekar's blog". codesachin.wordpress.com . Consultado el 3 de agosto de 2016 .
6. Rojas, Raúl (2009). "AdaBoost y el super bowl de clasificadores: una introducción tutorial al boosting adaptativo" (Tech. Rep.) . Universidad Libre, Berlín.
7. Friedman, Jerome; Hastie, Trevor; Tibshirani, Robert (1998). "Regresión logística aditiva: una visión estadística del boosting". Anales de estadística . 28 : 2000. CiteSeerX 10.1.1.51.9525 . 
8. Zhang, T. (2004). "Comportamiento estadístico y consistencia de los métodos de clasificación basados ​​en la minimización del riesgo convexo". Anales de Estadística . 32 (1): 56–85. doi : 10.1214/aos/1079120130 . JSTOR  3448494.
9. Schapire, Robert; Singer, Yoram (1999). "Algoritmos de refuerzo mejorados mediante predicciones basadas en la confianza": 80–91. CiteSeerX 10.1.1.33.4002 .  {{cite journal}}: Requiere citar revista |journal=( ayuda )
10. Freund; Schapire (1999). "Una breve introducción al boosting" (PDF) :
11. Viola, Paul; Jones, Robert (2001). "Detección rápida de objetos mediante una cascada potenciada de características simples". CiteSeerX 10.1.1.10.6807 .  {{cite journal}}: Requiere citar revista |journal=( ayuda )
12. McCane, Brendan; Novins, Kevin; Albert, Michael (2005). "Optimización de clasificadores en cascada". {{cite journal}}: Requiere citar revista |journal=( ayuda )
13. Trevor Hastie; Robert Tibshirani; Jerome Friedman (2009). Los elementos del aprendizaje estadístico: minería de datos, inferencia y predicción (2.ª ed.). Nueva York: Springer. ISBN 978-0-387-84858-7.
14. Šochman, Jan; Matas, Jiří (2004). Adaboost con actualizaciones totalmente correctivas para la detección rápida de rostros . ISBN 978-0-7695-2122-0.
15. Margineantu, Dragos; Dietterich, Thomas (1997). "Poda de potenciación adaptativa". CiteSeerX 10.1.1.38.7017 .  {{cite journal}}: Requiere citar revista |journal=( ayuda )
16. Tamon, Christino; Xiang, Jie (2000). "Sobre el problema de la poda de refuerzo". {{cite journal}}: Requiere citar revista |journal=( ayuda )

Lectura adicional

• Freund, Yoav; Schapire, Robert E (1997). "Una generalización teórica de decisiones del aprendizaje en línea y una aplicación para el impulso". Revista de Ciencias de la Computación y de Sistemas . 55 : 119–139. CiteSeerX  10.1.1.32.8918 . doi :10.1006/jcss.1997.1504:Artículo original de Yoav Freund y Robert E. Schapire donde se presenta por primera vez AdaBoost.
• Zhou, Zhihua (2008). "Explicación marginal del algoritmo de refuerzo" (PDF) . En: Actas de la 21.ª Conferencia Anual sobre Teoría del Aprendizaje (COLT'08) : 479–490.Explicación al margen del algoritmo de impulso.
• Zhou, Zhihua (2013). "Sobre la duda acerca de la explicación del margen del boosting" (PDF) . Inteligencia Artificial . 203 (2013): 1–18. arXiv : 1009.3613 . Bibcode :2010arXiv1009.3613G. doi :10.1016/j.artint.2013.07.002. S2CID  2828847.Sobre la duda sobre la explicación del margen del boosting.