AdaBoost

Algoritmo de clasificación basado en impulso 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 otros tipos de algoritmos de aprendizaje para mejorar el rendimiento. El resultado de los otros algoritmos de aprendizaje ("alumnos débiles") se combina en una suma ponderada que representa el resultado final del clasificador potenciado. Por lo general, AdaBoost se presenta para clasificación binaria , aunque se puede generalizar a múltiples clases o intervalos acotados en la línea real. ^{[1] [2]}

AdaBoost es adaptativo en el sentido de que los alumnos débiles posteriores se modifican a favor de aquellas instancias mal clasificadas por clasificadores anteriores. En algunos problemas, puede ser menos susceptible al problema de sobreajuste que otros algoritmos de aprendizaje. Los alumnos individuales pueden ser débiles, pero siempre que el desempeño de cada uno sea ligeramente mejor que las conjeturas aleatorias, se puede demostrar que el modelo final converge hacia un alumno fuerte.

Aunque AdaBoost se utiliza normalmente para combinar alumnos de base débiles (como los fragmentos de decisión ), se ha demostrado que también puede combinar de manera efectiva alumnos de base sólida (como los árboles de decisión profundos ), produciendo 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, por lo general, 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 estudiantes débiles) a menudo se conoce como el mejor clasificador listo para usar. ^{[4] [5]} Cuando se utiliza con el aprendizaje del árbol 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 del árbol, de modo que los árboles posteriores tienden a centrarse en los más difíciles de -clasificar ejemplos.

Capacitación

AdaBoost se refiere a un método particular para entrenar un clasificador potenciado. Un clasificador potenciado es un clasificador de la forma

$${\displaystyle F_{T}(x)=\sum _{t=1}^{T}f_{t}(x)}$$

${\displaystyle f_{t}}$ ${\displaystyle x}$ ${\displaystyle t}$

Cada alumno 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 alumno débil y se le asigna un coeficiente tal que se minimice el error de entrenamiento total del clasificador potenciado en 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 potenciado que se ha desarrollado 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 en el conjunto de entrenamiento igual al error actual en esa muestra. Estos pesos se pueden utilizar en el entrenamiento del alumno débil. Por ejemplo, se pueden cultivar árboles de decisión que favorezcan la división de conjuntos de muestras con pesos grandes. ${\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 enésima iteración, nuestro clasificador potenciado es una combinación lineal de los clasificadores débiles de la forma: ${\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 por determinar qué clasificador débil es la mejor opción 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, como se muestra a continuación: ${\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 por , 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 clasificados correctamente por (so ) y aquellos que están mal clasificados (so ): ${\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 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}$ ${\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 cuando se establece esto en cero y luego se resuelven los rendimientos: ${\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: ${\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 suposición inicial en otros casos, como cuando el alumno débil está sesgado ( ), 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} }$

Por lo tanto, 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 . ${\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 impulso 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, normalmente utilizando el error de mínimos cuadrados , mientras que la función de error 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 error creciente. Sin embargo, el aumento exponencial del error de la muestra aumenta , lo que da lugar a que se asignen ponderaciones excesivas 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 ,. Por lo tanto, se puede ver que la actualización del peso en el algoritmo AdaBoost equivale a volver a calcular 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 mucha 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 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 valores cercanos a 1 o -1, no penaliza las predicciones "excesivas de confianza" ( ), a diferencia de los mínimos cuadrados no modificados, y solo penaliza las muestras mal clasificadas con una confianza mayor que 1 de forma lineal, en lugar de cuadrática o exponencialmente. y, por tanto, es menos susceptible a los efectos de los valores atípicos. ${\displaystyle f(x)}$ ${\displaystyle yf(x)>1}$

Impulsando como descenso de gradiente

El impulso 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 AdaBoost minimiza es la pérdida exponencial

$${\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 alumno débil corresponde a un vector de orientación y longitud fijas, y el objetivo es llegar al 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 la optimización del error de entrenamiento de Cauchy (busque con el gradiente más pronunciado, elija minimizar el error de prueba) o Newton (elija algún punto objetivo, encuentre el que se acerque más a ese punto). ${\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})}}$
• Alumnos 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 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 manera que ${\displaystyle w_{i,t+1}}$ ${\displaystyle \sum _{i}w_{i,t+1}=1}$
  • (Nota: se puede demostrar que 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

Real AdaBoost

El resultado de los árboles de decisión es una estimación de probabilidad de clase , la probabilidad que está en la clase positiva. ^[7] Friedman, Hastie y Tibshirani derivan un minimizador analítico para algunos fijos (normalmente elegidos 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)}$.

Por lo tanto, en lugar de multiplicar la salida de todo el árbol por algún valor fijo, cada nodo hoja se cambia para generar la mitad de la transformación logit de su valor anterior.

LogitBoost

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 elige a los estudiantes débiles para minimizar el error (mínimos cuadrados ponderados) de con respecto a ${\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}}.}$$

Es decir , la aproximación de Newton-Raphson del minimizador del error de probabilidad logarítmica en la etapa , y se elige al alumno débil como el 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}))}$

Suave AdaBoost

Mientras que los algoritmos de impulso anteriores eligen con avidez, minimizando el error general de la prueba tanto como sea posible en cada paso, GentleBoost presenta un tamaño de paso limitado. Se elige minimizar y no se aplica ningún coeficiente adicional. Por lo tanto, en el caso de que un alumno débil exhiba un rendimiento de clasificación perfecto, GentleBoost elige exactamente igual a , mientras que los algoritmos de descenso más pronunciados intentan establecer . Las observaciones empíricas sobre el buen desempeño de GentleBoost parecen respaldar la observación de Schapire y Singer de que permitir valores excesivamente grandes de puede llevar a un desempeño deficiente de la generalización. ^{[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

La terminación temprana, una técnica para acelerar el procesamiento de clasificadores mejorados, se refiere a probar solo cada objeto potencial con tantas capas del clasificador final necesarias para alcanzar algún umbral de confianza, acelerando el cálculo en los casos en los que la clase del objeto se puede determinar fácilmente. Uno de esos 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 de refuerzo separados, y la salida de cada etapa está sesgada de tal manera que una fracción aceptablemente pequeña de Las muestras positivas se etiquetan erróneamente como negativas y todas las muestras marcadas como negativas después de cada etapa se descartan. Si cada etapa filtra el 50% de las muestras negativas, solo una cantidad muy pequeña de objetos pasaría por todo el clasificador, lo que reduciría el esfuerzo de cálculo. Desde entonces, este método se ha generalizado, 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 la estadística, donde AdaBoost se aplica más comúnmente a problemas de dimensionalidad moderada, la detención temprana se utiliza como estrategia para reducir el sobreajuste . ^[13] Un conjunto de muestras de validación se separa del conjunto de entrenamiento, el rendimiento del clasificador en las muestras utilizadas para el entrenamiento se compara con el rendimiento de 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 que se elija un alumno débil t+1 que sea similar al alumno t . Sin embargo, sigue existiendo 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 sean siempre máximamente independientes de cada capa anterior. Esto se puede lograr mediante retroadaptación, programación lineal o algún otro método. ${\displaystyle \alpha _{t}}$

Poda

La poda es el proceso de eliminar clasificadores débiles con bajo rendimiento para mejorar la memoria y el costo del 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 margen: cuando el coeficiente, o la contribución al error total de la prueba, de algún clasificador débil cae por debajo de un cierto umbral, ese clasificador es abandonó. 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 alumnos débiles producen resultados muy similares, la eficiencia se puede mejorar eliminando a uno de ellos y aumentando el coeficiente del alumno débil restante. ^[dieciséis]

Ver también

• Agregación de arranque
• Coimpulso
• MarrónBoost
• 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 la decisión [sic] del aprendizaje en línea y una aplicación al impulso, 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, recuperado 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, Mateo; Bleich, Justin; Mease, David (2017). "Explicando el éxito de AdaBoost y Random Forests como clasificadores de interpolación". Revista de investigación sobre aprendizaje automático . 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 - blog de Sachin Joglekar". codesachin.wordpress.com . Consultado el 3 de agosto de 2016 .
6. Rojas, Raúl (2009). "AdaBoost y el super bowl de clasificadores: un tutorial de introducción al impulso adaptativo" (Representante técnico) . Universidad Freie, Berlín.
7. Friedman, Jerome; Hastie, Trevor; Tibshirani, Robert (1998). "Regresión logística aditiva: una visión estadística del impulso". Anales de Estadística . 28 : 2000. CiteSeerX 10.1.1.51.9525 . 
8. Zhang, T. (2004). "Comportamiento estadístico y consistencia de métodos de clasificación basados ​​en minimización de riesgos convexos". Anales de Estadística . 32 (1): 56–85. doi : 10.1214/aos/1079120130 . JSTOR  3448494.
9. Schapire, Robert; Cantante, Yoram (1999). "Algoritmos de impulso mejorados mediante predicciones calificadas de confianza": 80–91. CiteSeerX 10.1.1.33.4002 .  {{cite journal}}: Citar diario requiere |journal=( ayuda )
10. Freund; Schapire (1999). "Una breve introducción al impulso" (PDF) :
11. Viola, Pablo; Jones, Robert (2001). "Detección rápida de objetos mediante una cascada mejorada de funciones simples". CiteSeerX 10.1.1.10.6807 .  {{cite journal}}: Citar diario requiere |journal=( ayuda )
12. McCane, Brendan; Novins, Kevin; Alberto, Michael (2005). "Optimización de clasificadores en cascada". {{cite journal}}: Citar diario requiere |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, enero; Matas, Jiří (2004). Adaboost con actualizaciones totalmente correctivas para una rápida detección de rostros . ISBN 978-0-7695-2122-0.
15. Margineantu, Dragos; Dietterich, Thomas (1997). "Poda de refuerzo adaptativo". CiteSeerX 10.1.1.38.7017 .  {{cite journal}}: Citar diario requiere |journal=( ayuda )
16. Tamón, Christina; Xiang, Jie (2000). "Sobre el problema del impulso de la poda". {{cite journal}}: Citar diario requiere |journal=( ayuda )

Otras lecturas

• Freund, Yoav; Schapire, Robert E. (1997). "Una generalización teórica de decisiones del aprendizaje en línea y una aplicación al 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 impulso" (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 sobre la explicación del margen del impulso" (PDF) . Inteligencia artificial . 203 (2013): 1–18. arXiv : 1009.3613 . Código Bib : 2010arXiv1009.3613G. doi :10.1016/j.artint.2013.07.002. S2CID  2828847.Sobre la duda sobre la explicación del margen del impulso.