Impulsar

Boosting es un  meta-algoritmo de aprendizaje automático compositivo  que se utiliza principalmente para reducir el sesgo (error de estimación), así como la varianza [1] en el aprendizaje supervisado . También se define como una familia de algoritmos de aprendizaje automático que transforman algoritmos de aprendizaje débiles en fuertes [2] .

El impulso se basa en la pregunta planteada por Kearns y Valiant (1988, 1989) [3] [4] : ​​"¿Puede un conjunto de algoritmos de aprendizaje débiles producir un algoritmo de aprendizaje fuerte?". Un algoritmo de aprendizaje débil se define como un clasificador que está débilmente correlacionado con la clasificación correcta (puede etiquetar ejemplos mejor que adivinar aleatoriamente). A diferencia del algoritmo débil, el algoritmo de aprendizaje fuerte es un clasificador que se correlaciona bien con la clasificación correcta.

La respuesta positiva de Robert Shapire en un artículo de 1990 [5] a la pregunta de Kearns y Valiant fue de gran importancia para la teoría y las estadísticas del aprendizaje automático y condujo a la creación de una amplia gama de algoritmos de impulso [6] .

La hipótesis de impulso se refiere al proceso de ajuste de un algoritmo de aprendizaje débil para obtener un aprendizaje fuerte. Informalmente, uno se pregunta si la existencia de un algoritmo de aprendizaje eficiente cuyo resultado es una hipótesis cuyo desempeño es solo ligeramente mejor que las conjeturas aleatorias (es decir, aprendizaje débil) implica la existencia de un algoritmo eficiente que produce una hipótesis de precisión arbitraria (es decir, aprendizaje fuerte). aprendizaje) [3] . Los algoritmos que llegan a tal hipótesis rápidamente se conocen simplemente como "boosting". El algoritmo de "arcing" de Freund y Shapire (Adaptive Resampling and Combining) [7] como técnica general es más o menos sinónimo de boosting [8]

Impulsando algoritmos

Si bien el impulso no está restringido algorítmicamente, la mayoría de los algoritmos de impulso consisten en un entrenamiento iterativo de clasificadores débiles para ensamblarlos en un clasificador fuerte. Cuando se agregan, generalmente se les asignan pesos de alguna manera, que generalmente están relacionados con la precisión del entrenamiento. Después de agregar el clasificador débil, se vuelven a calcular los pesos, lo que se conoce como "recalculo de peso" . Las entradas mal clasificadas ganan más peso, mientras que las instancias correctamente clasificadas pierden peso [nb 1] . Por lo tanto, el aprendizaje débil subsiguiente se enfoca más en ejemplos donde los aprendizajes débiles anteriores se clasificaron incorrectamente.

Hay muchos algoritmos de impulso. Los algoritmos originales propuestos por Robert Shapire ( formulación de puerta de mayoría  recursiva ) [5] y Yoav Freund (potenciación de dominancia) [9] no eran adaptativos y no podían aprovechar al máximo el aprendizaje débil. Shapire y Freund luego desarrollaron AdaBoost (Adaptive Boosting), un algoritmo de impulso adaptativo que ganó el prestigioso Premio Gödel .

Solo los algoritmos para los que se puede demostrar que son algoritmos de refuerzo en la formulación de un aprendizaje aproximadamente correcto pueden llamarse con precisión algoritmos de refuerzo . Otros algoritmos que son similares en espíritu a los algoritmos de refuerzo a veces se denominan algoritmos de aprovechamiento , aunque a veces también se denominan incorrectamente algoritmos de impulso [ 9] . 

La principal divergencia entre muchos algoritmos de impulso radica en los métodos para determinar los pesos de los puntos de datos de entrenamiento y las hipótesis . El algoritmo AdaBoost es muy popular e históricamente el más importante, ya que fue el primer algoritmo que pudo adaptarse al aprendizaje débil. El algoritmo se usa a menudo como una introducción básica para impulsar algoritmos en cursos de aprendizaje automático en universidades [10] . Hay muchos algoritmos desarrollados recientemente, como LPBoost [ , TotalBoost, BrownBoost , xgboost en , MadaBoost , [ en ] otros .

Clasificación de características en visión artificial

Dadas las imágenes que contienen varios objetos conocidos en el mundo, se puede entrenar un clasificador en función de ellas para clasificar automáticamente los objetos en futuras imágenes desconocidas. Los clasificadores simples, construidos sobre la base de algunas características de la imagen del objeto, suelen resultar ineficaces para clasificar. El uso de métodos de refuerzo para clasificar objetos es una forma de combinar clasificadores débiles de una manera específica para mejorar la capacidad de clasificación general.

La tarea de clasificar objetos

La clasificación de características es una tarea típica de la visión artificial , donde se determina si una imagen contiene una determinada categoría de objetos o no. La idea está estrechamente relacionada con el reconocimiento, la identificación y la detección. La clasificación por detección de objetos generalmente contiene extracción de características , entrenamiento de un clasificador y aplicación del clasificador a nuevos datos. Hay muchas formas de representar una categoría de objetos, como analizar la forma , usar el modelo de bolsa de palabras , usar descriptores locales como SIFT , etc. Ejemplos de clasificadores supervisados ​​son los clasificadores naive bayes , las máquinas de vectores de soporte , gaussianas y las redes neuronales . Sin embargo, los estudios han demostrado que las categorías de objetos y su posición en las imágenes también se pueden detectar mediante el aprendizaje no supervisado [11] .

Status quo para la clasificación de objetos

Reconocer categorías de objetos en imágenes es una tarea difícil en visión artificial , especialmente si el número de categorías es grande. Esto es consecuencia de la alta variabilidad interna de las clases y de la necesidad de generalizar diferentes conceptos dentro de una clase. Los objetos en la misma categoría pueden verse completamente diferentes. Incluso el mismo objeto puede verse diferente desde diferentes puntos de vista, escala o iluminación . El ruido de fondo y las superposiciones parciales también aumentan la complejidad del reconocimiento [12] . Los seres humanos son capaces de reconocer miles de tipos de objetos, mientras que la mayoría de los sistemas de reconocimiento de objetos existentes están capacitados para reconocer solo unos pocos, como rostros humanos , automóviles , objetos simples, etc. [13] . Se está investigando activamente el aumento del número de categorías y la posibilidad de añadir nuevas categorías, y aunque el problema general aún no se ha resuelto, se han desarrollado detectores para un gran número de categorías (hasta cientos y miles [14] ) . . Esto se logra, en particular, compartiendo las características y potenciando.

Impulso para la clasificación binaria

El paquete AdaBoost se puede utilizar para el reconocimiento facial como ejemplo de clasificación binaria . Las dos categorías son caras y fondo. El algoritmo general se ve así:

  1. Formamos un gran conjunto de características.
  2. Inicializar los pesos para el conjunto de imágenes de entrenamiento
  3. Haciendo carreras en T
    1. Normalizar pesos
    2. Para las funciones disponibles del conjunto, entrenamos el clasificador usando una de las funciones y calculamos el error de entrenamiento
    3. Elegir un clasificador con el error más pequeño
    4. Actualice los pesos de la imagen de entrenamiento: aumente si se clasifica incorrectamente y disminuya si es correcto
  4. Formamos el clasificador fuerte final como una combinación lineal de clasificadores T (el coeficiente es mayor si el error de entrenamiento es menor)

Después de impulsar, un clasificador creado a partir de 200 características puede alcanzar el 95 % de reconocimientos exitosos con errores de reconocimiento positivos [15] .

Otra aplicación de impulso para la clasificación binaria es un sistema que reconoce a los peatones utilizando patrones de movimiento y apariencia [16] . Este trabajo combina información de movimiento y apariencia como características para detectar a una persona en movimiento por primera vez. Tomamos un enfoque similar al modelo de detección de objetos de Viola-Jones .

Impulso de clasificación multiclase

En comparación con la clasificación binaria, la clasificación multiclase características comunes que puedan compartirse entre categorías al mismo tiempo. Resultan ser más generales, como la característica de " límite " . Durante el entrenamiento, los clasificadores de cada categoría pueden entrenarse conjuntamente. En comparación con el entrenamiento por separado, dicho entrenamiento tiene una mejor generalización , requiere menos datos de entrenamiento y se necesitan menos características para lograr el resultado deseado.

El funcionamiento básico del algoritmo es similar al caso binario. La diferencia es que la medida del error de entrenamiento conjunto se puede determinar de antemano. Durante cada iteración, el algoritmo selecciona un único clasificador de características (se recomiendan las características que se pueden clasificar de forma conjunta). Esto se puede hacer convirtiendo la clasificación multiclase a binaria (conjunto de categorías/otras categorías) [17] o penalizando categorías que no tienen características reconocidas por el clasificador [18] .

En Compartir funciones visuales para la detección de objetos multiclase y vista múltiple, A. Torralba y otros utilizaron GentleBoost para potenciar y demostraron que si los datos de entrenamiento son limitados, el aprendizaje con características usadas compartidas funciona mucho mejor que sin compartir. Además, para un nivel de rendimiento determinado, el número total de características necesarias (y, por lo tanto, el tiempo de ejecución del clasificador) para detectar características compartidas crece aproximadamente logarítmicamente con el número de clases, es decir, más lento que el lineal que se produce en el caso de sin compartir Resultados similares se muestran en el artículo “Aprendizaje incremental de detección de objetos usando el alfabeto de imágenes visuales”, sin embargo, los autores usaron AdaBoost para potenciar .

Algoritmos de refuerzo convexos y no convexos

Los algoritmos de refuerzo pueden basarse en algoritmos de optimización convexos o no convexos. Los algoritmos convexos como AdaBoost y LogitBoost pueden colapsar debido al ruido aleatorio porque no pueden enseñar combinaciones básicas y aprendibles de hipótesis débiles [19] [20] . Esta limitación fue señalada por Long y Servedo en 2008. Sin embargo, en 2009 varios autores demostraron que los algoritmos de refuerzo basados ​​en optimización no convexa como BrownBoost pueden entrenarse a partir de datos ruidosos y el clasificador Long-Servedio subyacente para el conjunto de datos puede entrenarse .

Véase también

Implementación

Notas

  1. ↑ . Algunos algoritmos de clasificación basados ​​en impulsos en realidad reducen el peso de las instancias clasificadas incorrectamente. Por ejemplo, dominance boosting ( impulso en inglés  por mayoría ) y BrownBoost
  1. ↑ Breiman, 1996 .
  2. ↑ Zhi-Hua, 2012 , pág. 23
  3. ↑ 12 Kearns , 1988 .
  4. ↑ Kearns, Valiant, 1989 , pág. 433–444.
  5. ↑ 1 2 Schapire, 1990 , p. 197–227.
  6. ↑ Breiman, 1998 , pág. 801–849.
  7. ↑ Freund y Schapire 1997 , p. 119-139.
  8. ↑ Leo Briman ( Breiman 1998 ) escribe: “El concepto de aprendizaje débil fue introducido por Kearns y Valiant ( 1988 , Kearns, Valiant, 1989 ), quienes plantearon la cuestión de si el aprendizaje fuerte y el débil son equivalentes. La pregunta se ha llamado problema de impulso , ya que la solución es aumentar la precisión débil del aprendizaje débil a la precisión alta del aprendizaje fuerte. Shapire (1990) demostró que el refuerzo es posible. El algoritmo boosting es un método que toma un método de aprendizaje débil y lo transforma en un método fuerte. Freund y Shapire (1997) demostraron que un algoritmo como arc-fs está potenciando".
  9. ↑ 1 2 3 Mason, Baxter, Bartlett, Frean, 2000 , p. 512-518.
  10. ↑ Emer, Eric Boosting (algoritmo AdaBoost) (enlace no disponible) . MIT . Consultado el 10 de octubre de 2018. Archivado desde el original el 15 de febrero de 2020. 
  11. ↑ Sivic, Russell, Efros, Zisserman, Freeman, 2005 , pág. 370-377.
  12. ↑ Opelt, Pinz, Fussenegger, Auer, 2006 , pág. 416-431.
  13. ↑ Marszalek, Schmid, 2007 .
  14. ↑ Desafío de reconocimiento visual a gran escala (diciembre de 2017). Consultado el 6 de noviembre de 2018. Archivado desde el original el 2 de noviembre de 2018.
  15. ↑ Viola, Jones, 2001 .
  16. ↑ Viola, Jones, Snow, 2003 .
  17. ↑ Torralba, Murphy, Freeman, 2007 , p. 854-869.
  18. ↑ Opelt, Pinz, Zisserma, 2006 , pág. 3-10.
  19. ↑ Largo, Servedio, 2008 , p. 608-615.
  20. ↑ Largo, Servedio, 2010 , p. 287–304.

Literatura

Enlaces