AdaBoost , abreviatura de Adaptive Boosting , es un meta-algoritmo de clasificación estadística formulado por Yoav Freund y Robert Schapire , quienes ganaron el Premio Gödel 2003 por su trabajo. Se puede utilizar junto con muchos otros tipos de algoritmos de aprendizaje para mejorar el rendimiento. La salida de los otros algoritmos de aprendizaje ("estudiantes débiles") se combina en una suma ponderada que representa la salida final del clasificador reforzado. AdaBoost es adaptativo en el sentido de que los aprendices débiles posteriores se modifican a favor de aquellas instancias mal clasificadas por clasificadores anteriores. En algunos problemas, puede ser menos susceptible al sobreajuste.problema que otros algoritmos de aprendizaje. Los alumnos individuales pueden ser débiles, pero siempre que el rendimiento de cada uno sea un poco mejor que la adivinación aleatoria, se puede demostrar que el modelo final converge en un alumno fuerte.
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 para ajustar antes de lograr un rendimiento óptimo en un conjunto de datos. AdaBoost (con árboles de decisión como los aprendices débiles) a menudo se conoce como el mejor clasificador listo para usar. [1] [2] Cuando se utiliza con el aprendizaje del árbol de decisiones, 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 enfocarse en los más difíciles de -clasificar ejemplos.
Descripción general
Los problemas en el aprendizaje automático a menudo sufren la maldición de la dimensionalidad : cada muestra puede constar de una gran cantidad de características potenciales (por ejemplo, puede haber 162,336 características de Haar , tal como las usa el marco de detección de objetos Viola-Jones , en un formato 24 × 24 ventana de imagen de píxeles), y la evaluación de cada característica puede reducir no solo la velocidad de entrenamiento y ejecución del clasificador, sino que de hecho reduce el poder predictivo . [3] A diferencia de las redes neuronales y las SVM , el proceso de entrenamiento de AdaBoost selecciona solo aquellas características conocidas para mejorar el poder predictivo del modelo, reduciendo la dimensionalidad y potencialmente mejorando el tiempo de ejecución ya que las características irrelevantes no necesitan ser computadas.
Capacitación
AdaBoost se refiere a un método particular de entrenamiento de un clasificador mejorado. Un clasificador de impulso es un clasificador en la forma
donde cada 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 alumno débil identifica la clase de objeto predicha y el valor absoluto da la confianza en esa clasificación. Del mismo modo, elEl clasificador es positivo si la muestra está en una clase positiva y negativa en caso contrario.
Cada alumno débil produce una hipótesis de salida, , para cada muestra del conjunto de formación. En cada iteración, se selecciona un alumno débil y se le asigna un coeficiente tal que la suma del error de entrenamiento de la resultante -se minimiza el clasificador de impulso de etapa.
Aquí es el clasificador potenciado que se ha construido para la etapa anterior de entrenamiento, es alguna función de error y es el alumno débil que se está considerando para agregar al clasificador final.
Ponderación
En cada iteración del proceso de entrenamiento, un peso se asigna a cada muestra en el conjunto de entrenamiento igual al error actual en esa muestra. Estos pesos se pueden utilizar para informar la formación del alumno débil, por ejemplo, se pueden cultivar árboles de decisión que favorezcan la división de conjuntos de muestras con pesos altos.
Derivación
Esta derivación sigue a Rojas (2009): [4]
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 artículo. Después de la-th iteración nuestro clasificador reforzado es una combinación lineal de los clasificadores débiles de la forma:
Donde la clase será el signo de . En el-th iteración queremos extender esto a un clasificador mejor reforzado agregando otro clasificador débil , con otro peso :
Por lo que queda por determinar qué clasificador débil es la mejor opción para , y cual es su peso debiera ser. Definimos el error total de como la suma de su pérdida exponencial en cada punto de datos, dado de la siguiente manera:
Dejando y por , tenemos:
Podemos dividir esta suma entre los puntos de datos que están correctamente clasificados por (entonces ) y aquellos que están mal clasificados (por lo que ):
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 [asumiendo que ], es decir, el clasificador débil con el error ponderado más bajo (con pesos ).
Para determinar el peso deseado que minimiza con el que acabamos de determinar, diferenciamos:
Poniendo esto a cero y resolviendo para rinde:
porque no depende de
Calculamos la tasa de error ponderada del clasificador débil para que sea , por lo que se deduce que:
que es la función logit negativa multiplicada por 0,5.
Por lo tanto, hemos derivado el algoritmo AdaBoost: en cada iteración, elija el clasificador , que minimiza el error ponderado total , use esto para calcular la tasa de error , usa esto para calcular el peso , y finalmente use esto para mejorar el clasificador impulsado a .
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 .
Mientras la regresión intenta encajar a con la mayor precisión posible sin pérdida de generalización, normalmente utilizando el error de mínimos cuadrados, 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 aumentar el error. Sin embargo, el aumento exponencial del error para la muestra como los aumentos dan como resultado la asignación de un peso excesivo 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, . Por lo tanto, se puede ver que la actualización de peso en el algoritmo AdaBoost es equivalente a volver a calcular el error en después de cada etapa.
Se permite 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 orienta hacia soluciones más puras. [5] Zhang (2004) proporciona una función de pérdida basada en mínimos cuadrados, una función de pérdida de Huber modificada :
Esta función se comporta mejor que LogitBoost para cerca de 1 o -1, no penaliza las predicciones de 'exceso de confianza' (), a diferencia de los mínimos cuadrados no modificados, y solo penaliza las muestras mal clasificadas con una confianza mayor que 1 linealmente, en contraposición a cuadráticamente o exponencialmente, y por lo tanto es menos susceptible a los efectos de valores atípicos.
Impulso como descenso de gradiente
El impulso puede verse como la minimización de una función de pérdida convexa sobre un conjunto de funciones convexas . [6] Específicamente, la pérdida que AdaBoost minimiza es la pérdida exponencial, mientras que LogitBoost realiza regresión logística, minimizando .
En la analogía del descenso de gradiente, la salida del clasificador para cada punto de entrenamiento se considera un punto en el 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 alcanzar el punto objetivo (o cualquier región donde el valor de la función de pérdida es menor que el valor en ese punto), en el menor número de pasos. Por lo tanto, los algoritmos AdaBoost realizan Cauchy (encuentre con la pendiente más pronunciada, elija para minimizar el error de prueba) o Newton (elija un punto objetivo, busque eso trae más cercano a ese punto) optimización del error de entrenamiento.
Algoritmo de ejemplo (AdaBoost discreto)
Con:
- Muestras
- Salidas deseadas
- Pesos iniciales ajustado a
- Función de error
- Estudiantes débiles
Para en :
- Escoger :
- Encuentra aprendiz débil que minimiza , el error de suma ponderado para puntos clasificados erróneamente
- Escoger
- Agregar al conjunto:
- Actualizar pesos:
- por en
- Renormalizar tal que
- (Nota: se puede demostrar que en cada paso, lo que puede simplificar el cálculo de los nuevos pesos).
Elegir α t
se elige ya que se puede demostrar analíticamente que es el minimizador de la función de error exponencial para Discrete AdaBoost. [7]
Minimizar:
Usando la convexidad de la función exponencial y asumiendo que tenemos:
Luego diferenciamos esa expresión con respecto a y ajústelo a cero para encontrar el mínimo del límite superior:
Tenga en cuenta que esto solo se aplica cuando , aunque puede ser una buena suposición inicial en otros casos, como cuando el alumno débil está sesgado (), tiene varias hojas () o es alguna otra función . En tales casos, la elección del alumno débil y el coeficiente se puede condensar en un solo paso en el que es elegido entre todos los posibles como minimizador de por alguna rutina de búsqueda numérica.
Variantes
Real AdaBoost
La salida de los árboles de decisión es una estimación de probabilidad de clase , la probabilidad de que está en la clase positiva. [5] Friedman, Hastie y Tibshirani obtienen un minimizador analítico para para algunos arreglados (normalmente elegido usando el error de mínimos cuadrados ponderados):
- .
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 transformada 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 ay, se eligen estudiantes débiles para minimizar el error (mínimos cuadrados ponderados) de con respecto a
dónde
Es decir es la aproximación de Newton-Raphson del minimizador del error logarítmico de verosimilitud en la etapay el aprendiz débil es elegido como el alumno que mejor se aproxima por mínimos cuadrados ponderados.
Cuando 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 en el valor absoluto de z y el valor mínimo de w
AdaBoost suave
Mientras que los algoritmos de impulso anteriores eligen Con avidez, minimizando el error de prueba general tanto como sea posible en cada paso, GentleBoost presenta un tamaño de paso limitado. se elige para minimizar y no se aplica ningún otro coeficiente. Por lo tanto, en el caso de que un alumno débil muestre 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 depuede conducir a un rendimiento deficiente de generalización [7] [8]
Terminación anticipada
Una técnica para acelerar el procesamiento de clasificadores reforzados, la terminación anticipada se refiere a probar solo cada objeto potencial con tantas capas del clasificador final necesarias para cumplir con algún 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: [9] en una aplicación con muestras significativamente más negativas que positivas, se entrena una cascada de clasificadores de refuerzo separados, la salida de cada etapa sesgada de tal manera que una fracción aceptablemente pequeña de las muestras positivas están mal etiquetadas como negativas 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 pequeña cantidad de objetos pasarían 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. [10]
En el campo de la estadística, donde AdaBoost se aplica más comúnmente a problemas de dimensionalidad moderada, la parada anticipada se utiliza como estrategia para reducir el sobreajuste . [11] 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 en las muestras de validación, y el entrenamiento se termina si el rendimiento en la muestra de validación disminuye incluso cuando el rendimiento en el conjunto de entrenamiento sigue 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 : [12] es poco probable que se elija un alumno débil t + 1 que sea similar al alumno 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 son máximamente independientes de cada capa anterior. Esto se puede lograr mediante retroajuste, programación lineal o algún otro método.
Poda
La poda es el proceso de eliminar clasificadores débiles de 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 caído. Margineantu y Dietterich [13] 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, se puede mejorar la eficiencia eliminando uno de ellos y aumentando el coeficiente del alumno débil restante. [14]
Ver también
- Bootstrap agregando
- CoBoosting
- BrownBoost
- Aumento de gradiente
- Método de actualización de peso multiplicativo § Algoritmo AdaBoost
Referencias
- ^ Kégl, Balázs (20 de diciembre de 2013). "El regreso de AdaBoost.MH: árboles Hamming de clases múltiples". arXiv : 1312.6086 [ cs.LG ].
- ^ Joglekar, Sachin. "adaboost - blog de Sachin Joglekar" . codesachin.wordpress.com . Consultado el 3 de agosto de 2016 .
- ^ Hughes, GF (enero de 1968). "Sobre la precisión media de los reconocedores de patrones estadísticos". Transacciones IEEE sobre teoría de la información . 14 (1): 55–63. doi : 10.1109 / TIT.1968.1054102 . S2CID 206729491 .
- ^ Rojas, R. (2009). AdaBoost y el super bowl de clasificadores un tutorial de introducción al impulso adaptativo. Universidad Freie, Berlín, Tech. Reps.
- ^ a b Friedman, Jerome; Hastie, Trevor; Tibshirani, Robert (1998). "Regresión logística aditiva: una visión estadística del impulso". CiteSeerX 10.1.1.51.9525 . Cite journal requiere
|journal=
( ayuda ) - ^ Zhang, T. (2004). "Comportamiento estadístico y coherencia de los métodos de clasificación basados en la minimización del riesgo convexo" . Annals of Statistics . 32 (1): 56–85. doi : 10.1214 / aos / 1079120130 . JSTOR 3448494 .
- ^ a b Schapire, Robert; Cantante, Yoram (1999). "Mejora de los algoritmos de impulso mediante predicciones de confianza". CiteSeerX 10.1.1.33.4002 . Cite journal requiere
|journal=
( ayuda ) - ^ Freund; Schapire (1999). "Una breve introducción al impulso" (PDF) :
- ^ Viola, Paul; Jones, Robert (2001). "Detección rápida de objetos mediante una cascada mejorada de funciones simples". CiteSeerX 10.1.1.10.6807 . Cite journal requiere
|journal=
( ayuda ) - ^ McCane, Brendan; Novins, Kevin; Albert, Michael (2005). "Optimización de clasificadores en cascada". Cite journal requiere
|journal=
( ayuda ) - ^ 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.
- ^ Šochman, Jan; Matas, Jiří (2004). Adaboost con actualizaciones totalmente correctivas para una detección rápida de rostros . ISBN 978-0-7695-2122-0.
- ^ Margineantu, Dragos; Dietterich, Thomas (1997). "Impulso Adaptativo de Poda". CiteSeerX 10.1.1.38.7017 . Cite journal requiere
|journal=
( ayuda ) - ^ Tamon, Christino; Xiang, Jie (2000). "Sobre el problema de la poda de impulso". Cite journal requiere
|journal=
( ayuda )
Otras lecturas
- Freund, Yoav; Schapire, Robert E (1997). "Una generalización de la teoría de la decisión del aprendizaje en línea y una aplicación al impulso". Revista de Ciencias de la Computación y 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 al margen del algoritmo de impulso" (PDF) . En: Actas de la 21ª Conferencia Anual sobre Teoría del Aprendizaje (COLT'08) : 479–490. Al margen de la explicación del algoritmo de impulso.
- Zhou, Zhihua (2013). "Sobre la duda sobre el margen de explicación del impulso" (PDF) . Inteligencia artificial . 203 (2013): 1–18. arXiv : 1009,3613 . Código bibliográfico : 2010arXiv1009.3613G . doi : 10.1016 / j.artint.2013.07.002 . S2CID 2828847 . Sobre la duda sobre la explicación marginal del impulso.