En el aprendizaje automático , el impulso es un metaalgoritmo conjunto para reducir principalmente el sesgo y también la varianza [1] en el aprendizaje supervisado , y una familia de algoritmos de aprendizaje automático que convierten a los estudiantes débiles en fuertes. [2] El impulso se basa en la pregunta planteada por Kearns y Valiant (1988, 1989): [3] [4] "¿Puede un grupo de estudiantes débiles crear un solo estudiante fuerte?" Un alumno débil se define como un clasificador.eso está solo ligeramente correlacionado con la clasificación verdadera (puede etiquetar ejemplos mejor que adivinar al azar). En contraste, un alumno fuerte es un clasificador que está arbitrariamente bien correlacionado con la clasificación verdadera.
La respuesta afirmativa de Robert Schapire en un artículo de 1990 [5] a la pregunta de Kearns y Valiant ha tenido ramificaciones significativas en el aprendizaje automático y las estadísticas , sobre todo conduciendo al desarrollo del impulso. [6]
Cuando se presentó por primera vez, el problema de impulso de hipótesis simplemente se refería al proceso de convertir a un alumno débil en un alumno fuerte. "De manera informal, el problema [de refuerzo de hipótesis] pregunta si un algoritmo de aprendizaje eficiente [...] que genera una hipótesis cuyo rendimiento es solo un poco mejor que la suposición aleatoria [es decir, un alumno débil] implica la existencia de un algoritmo eficiente que genera una hipótesis de precisión [es decir, un alumno fuerte] ". [3] Los algoritmos que logran el impulso de hipótesis rápidamente se conocieron simplemente como "impulso". El arco de Freund y Schapire (Adapt [at] ive Resampling and Combining), [7] como técnica general, es más o menos sinónimo de refuerzo. [8]
Impulsar algoritmos
Si bien el impulso no está restringido algorítmicamente, la mayoría de los algoritmos de impulso consisten en aprender iterativamente clasificadores débiles con respecto a una distribución y agregarlos a un clasificador fuerte final. Cuando se agregan, se ponderan de una manera que se relaciona con la precisión de los estudiantes débiles. Después de agregar un alumno débil, las ponderaciones de los datos se reajustan, lo que se conoce como " reponderación ". Los datos de entrada mal clasificados ganan un peso mayor y los ejemplos clasificados correctamente pierden peso. [nota 1] Por lo tanto, los futuros aprendices débiles se centran más en los ejemplos que los aprendices débiles anteriores clasificaron erróneamente.
Hay muchos algoritmos de impulso. Los originales, propuestos por Robert Schapire (una formulación de puerta de mayoría recursiva ) [5] y Yoav Freund (impulso por mayoría), [9] no eran adaptables y no podían aprovechar al máximo a los estudiantes débiles. Schapire y Freund desarrollaron AdaBoost , un algoritmo de impulso adaptativo que ganó el prestigioso premio Gödel .
Solo los algoritmos que son algoritmos de impulso demostrables en la formulación de aprendizaje probablemente aproximadamente correcta pueden denominarse con precisión algoritmos de impulso . Otros algoritmos que son similares en espíritu [ aclaración necesaria ] a los algoritmos de impulso a veces se denominan "algoritmos de apalancamiento", aunque a veces también se denominan incorrectamente algoritmos de impulso. [9]
La principal variación entre muchos algoritmos de impulso es su método de ponderar los puntos de datos de entrenamiento y las hipótesis . AdaBoost es muy popular y el más significativo históricamente, ya que fue el primer algoritmo que pudo adaptarse a los estudiantes débiles. A menudo es la base de la cobertura introductoria del impulso en los cursos universitarios de aprendizaje automático. [10] Hay muchos algoritmos más recientes como LPBoost , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost y otros. Muchos algoritmos de impulso encajan en el marco AnyBoost, [9] que muestra que el impulso realiza un descenso de gradiente en un espacio funcional utilizando una función de costo convexa .
Categorización de objetos en visión artificial
Dadas las imágenes que contienen varios objetos conocidos en el mundo, se puede aprender un clasificador de ellas para clasificar automáticamente los objetos en imágenes futuras. Los clasificadores simples construidos en base a alguna característica de la imagen del objeto tienden a ser débiles en el desempeño de la categorización. El uso de métodos de refuerzo para la categorización de objetos es una forma de unificar los clasificadores débiles de una manera especial para aumentar la capacidad general de categorización.
Problema de categorización de objetos
La categorización de objetos es una tarea típica de la visión por computadora que implica determinar si una imagen contiene o no alguna categoría específica de objeto. La idea está estrechamente relacionada con el reconocimiento, la identificación y la detección. La categorización de objetos basada en apariencia generalmente contiene extracción de características , aprendizaje de un clasificador y aplicación del clasificador a nuevos ejemplos. Hay muchas formas de representar una categoría de objetos, por ejemplo, desde análisis de forma , modelos de bolsa de palabras o descriptores locales como SIFT , etc. Ejemplos de clasificadores supervisados son clasificadores Naive Bayes , máquinas de vectores de soporte , mezclas de gaussianos y redes neuronales. . Sin embargo, la investigación [ ¿cuál? ] ha demostrado que las categorías de objetos y sus ubicaciones en las imágenes también se pueden descubrir sin supervisión . [11]
Status quo para la categorización de objetos
El reconocimiento de categorías de objetos en imágenes es un problema desafiante en la visión por computadora , especialmente cuando el número de categorías es grande. Esto se debe a la alta variabilidad intraclase y a la necesidad de generalizar las variaciones de objetos dentro de la misma categoría. Los objetos dentro de una categoría pueden tener un aspecto bastante diferente. Incluso el mismo objeto puede parecer diferente bajo diferentes puntos de vista, escala e iluminación . El desorden de fondo y la oclusión parcial también añaden dificultades al 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 entrenados para reconocer sólo unos pocos, [ cuantificar ], por ejemplo , rostros humanos , coches , objetos simples, etc. [13] [¿ necesita actualización? ] La investigación ha sido muy activa para tratar con más categorías y permitir adiciones incrementales de nuevas categorías, y aunque el problema general sigue sin resolverse, se han desarrollado varios detectores de objetos multicategoría (para cientos o miles de categorías [14] ). Un medio es compartir y potenciar funciones .
Impulso para la categorización binaria
AdaBoost se puede utilizar para la detección de rostros como ejemplo de categorización binaria . Las dos categorías son caras versus fondo. El algoritmo general es el siguiente:
- Forme un gran conjunto de características simples
- Inicializar pesos para imágenes de entrenamiento
- Para rondas en T
- Normalizar los pesos
- Para conocer las características disponibles del conjunto, entrene un clasificador usando una sola característica y evalúe el error de entrenamiento
- Elija el clasificador con el menor error
- Actualizar los pesos de las imágenes de entrenamiento: aumentar si este clasificador clasifica incorrectamente, disminuir si es correcto
- Forme el clasificador fuerte final como la combinación lineal de los clasificadores T (coeficiente mayor si el error de entrenamiento es pequeño)
Después del impulso, un clasificador construido a partir de 200 características podría producir una tasa de detección del 95% bajo un tasa de falsos positivos . [15]
Otra aplicación del impulso para la categorización binaria es un sistema que detecta peatones usando patrones de movimiento y apariencia. [16] Este trabajo es el primero en combinar tanto la información de movimiento como la información de apariencia como características para detectar a una persona que camina. Adopta un enfoque similar al marco de detección de objetos Viola-Jones .
Impulso para la categorización de clases múltiples
En comparación con la categorización binaria, la categorización de varias clases busca características comunes que se puedan compartir entre las categorías al mismo tiempo. Se convierten en características más genéricas similares a las de los bordes . Durante el aprendizaje, los detectores de cada categoría se pueden entrenar conjuntamente. En comparación con el entrenamiento por separado, se generaliza mejor, necesita menos datos de entrenamiento y requiere menos funciones para lograr el mismo rendimiento.
El flujo principal del algoritmo es similar al caso binario. Lo que es diferente es que una medida del error de entrenamiento conjunto debe definirse de antemano. Durante cada iteración, el algoritmo elige un clasificador de una sola característica (se fomentarán las características que pueden ser compartidas por más categorías). Esto se puede hacer mediante la conversión de la clasificación multiclase en una binaria (un conjunto de categorías frente al resto), [17] o introduciendo un error de penalización de las categorías que no tienen la característica del clasificador. [18]
En el artículo "Compartir características visuales para la detección de objetos multiclase y multivista", A. Torralba et al. usó GentleBoost para impulsar y demostró que cuando los datos de entrenamiento son limitados, aprender a través de las funciones de uso compartido hace un trabajo mucho mejor que no compartir, dadas las mismas rondas de impulso. Además, para un nivel de rendimiento dado, se observa que el número total de características requeridas (y por lo tanto el costo de tiempo de ejecución del clasificador) para los detectores de características compartidas, escala aproximadamente logarítmicamente con el número de clase, es decir, más lento que el crecimiento lineal en el caso de no compartir. Se muestran resultados similares en el artículo "Aprendizaje incremental de detectores de objetos usando un alfabeto de formas visuales", sin embargo, los autores utilizaron AdaBoost para impulsar.
Algoritmos de impulso convexos frente a no convexos
Los algoritmos de impulso pueden basarse en algoritmos de optimización convexos o no convexos. Los algoritmos convexos, como AdaBoost y LogitBoost , pueden ser "derrotados" por ruido aleatorio de modo que no puedan aprender combinaciones básicas y fáciles de aprender de hipótesis débiles. [19] [20] Esta limitación fue señalada por Long & Servedio en 2008. Sin embargo, en 2009, varios autores demostraron que los algoritmos de impulso basados en la optimización no convexa, como BrownBoost , pueden aprender de conjuntos de datos ruidosos y pueden aprender específicamente clasificador subyacente del conjunto de datos Long-Servedio.
Ver también
- AdaBoost
- Bosque aleatorio
- Árbol de decisión alterno
- Bootstrap aggregating (ensacado)
- En cascada
- BrownBoost
- CoBoosting
- LPBoost
- Regresión logística
- Métodos de máxima entropía
- Redes neuronales
- Máquinas de vectores de soporte
- Aumento de gradiente
- Clasificadores de margen
- Validación cruzada
- Aprendizaje automático
- Lista de conjuntos de datos para la investigación del aprendizaje automático
Implementaciones
- Scikit-learn , una biblioteca de aprendizaje automático de código abierto para python
- Orange , un paquete de software de minería de datos gratuito, módulo Orange.ensemble
- Weka es un conjunto de herramientas de aprendizaje automático que ofrece diversas implementaciones de algoritmos de impulso como AdaBoost y LogitBoost.
- El paquete R GBM (Modelos de regresión potenciados generalizados) implementa extensiones al algoritmo AdaBoost de Freund y Schapire y la máquina de aumento de gradiente de Friedman.
- jboost ; AdaBoost, LogitBoost, RobustBoost, Boostexter y árboles de decisión alternos
- Paquete R adabag : Aplica Multiclass AdaBoost.M1, AdaBoost-SAMME y Bagging
- Paquete R xgboost : una implementación de aumento de gradiente para modelos lineales y basados en árboles.
Notas
- ^ Algunos algoritmos de clasificación basados en potenciadores en realidad reducen el peso de ejemplos repetidamente mal clasificados; por ejemplo, boost por mayoría y BrownBoost .
Referencias
- ^ Leo Breiman (1996). "CLASIFICADORES DE SESGO, VARIANZA Y ARCO" (PDF) . REPORTE TÉCNICO. Archivado desde el original (PDF) el 19 de enero de 2015 . Consultado el 19 de enero de 2015 .
El arco [Boosting] es más exitoso que el embolsado en la reducción de varianza
- ^ Zhou Zhi-Hua (2012). Métodos de conjunto: fundamentos y algoritmos . Chapman y Hall / CRC. pag. 23. ISBN 978-1439830031.
El término impulso se refiere a una familia de algoritmos que pueden convertir a los estudiantes débiles en estudiantes fuertes.
- ↑ a b Michael Kearns (1988); Reflexiones sobre el impulso de hipótesis , manuscrito no publicado (proyecto de clase de aprendizaje automático, diciembre de 1988)
- ^ Michael Kearns ; Leslie Valiant (1989). Limitaciones critográficas [ sic ] sobre el aprendizaje de fórmulas booleanas y autómatas finitos . Simposio de Teoría de la Computación . 21 . ACM. págs. 433–444. doi : 10.1145 / 73007.73049 . ISBN 978-0897913072. S2CID 536357 .
- ^ a b Schapire, Robert E. (1990). "La fuerza de la capacidad de aprendizaje débil" (PDF) . Aprendizaje automático . 5 (2): 197–227. CiteSeerX 10.1.1.20.723 . doi : 10.1007 / bf00116037 . S2CID 53304535 . Archivado desde el original (PDF) el 10 de octubre de 2012 . Consultado el 23 de agosto de 2012 .
- ^ Leo Breiman (1998). "Clasificador de arco (con discusión y réplica del autor)" . Ana. Stat . 26 (3): 801–849. doi : 10.1214 / aos / 1024691079 .
Schapire (1990) demostró que el impulso es posible. (Página 823)
- ^ Yoav Freund y Robert E. Schapire (1997); Una generalización teórica de decisiones del aprendizaje en línea y una aplicación para impulsar , Journal of Computer and System Sciences, 55 (1): 119-139
- ^ Leo Breiman (1998); Clasificador de arco (con discusión y una réplica del autor) , Annals of Statistics, vol. 26, no. 3, págs. 801-849: "El concepto de aprendizaje débil fue introducido por Kearns y Valiant (1988, 1989), quienes dejaron abierta la cuestión de si la capacidad de aprendizaje débil y fuerte son equivalentes. La cuestión se denominó el problema de impulso ya que [un La solución debe] aumentar la precisión baja de un alumno débil a la alta precisión de un alumno fuerte. Schapire (1990) demostró que el impulso es posible. Un algoritmo de impulso es un método que toma a un alumno débil y lo convierte en un alumno fuerte. Freund y Schapire (1997) demostraron que un algoritmo similar a arc-fs está impulsando.
- ↑ a b c Llew Mason, Jonathan Baxter, Peter Bartlett y Marcus Frean (2000); Aumento de algoritmos como gradiente descendente , en SA Solla, TK Leen y K.-R. Muller, editores, Advances in Neural Information Processing Systems 12, págs. 512-518, MIT Press
- ^ Emer, Eric. "Impulso (algoritmo AdaBoost)" (PDF) . MIT . Consultado el 10 de octubre de 2018 .
- ^ Sivic, Russell, Efros, Freeman & Zisserman, "Descubrimiento de objetos y su ubicación en imágenes", ICCV 2005
- ^ A. Opelt, A. Pinz, et al., "Reconocimiento de objetos genéricos con impulso", Transacciones IEEE en PAMI 2006
- ^ M. Marszalek, "Jerarquías semánticas para el reconocimiento de objetos visuales", 2007
- ^ "Desafío de reconocimiento visual a gran escala" . Diciembre de 2017.
- ^ P. Viola, M. Jones, "Detección robusta de objetos en tiempo real", 2001
- ^ Viola, P .; Jones, M .; Nieve, D. (2003). Detección de peatones mediante patrones de movimiento y apariencia (PDF) . ICCV.
- ^ A. Torralba, KP Murphy, et al., "Compartir características visuales para la detección de objetos multiclase y multivista", Transacciones IEEE en PAMI 2006
- ^ A. Opelt, et al., "Aprendizaje incremental de detectores de objetos mediante un alfabeto de formas visuales", CVPR 2006
- ^ P. Long y R. Servedio. 25a Conferencia Internacional sobre Aprendizaje Automático (ICML), 2008, págs.
- ^ Long, Philip M .; Servedio, Rocco A. (marzo de 2010). "El ruido de clasificación aleatoria derrota a todos los potenciadores potenciales convexos" (PDF) . Aprendizaje automático . 78 (3): 287-304. doi : 10.1007 / s10994-009-5165-z . S2CID 53861 . Consultado el 17 de noviembre de 2015 .
Otras lecturas
- Yoav Freund y Robert E. Schapire (1997); Una generalización teórica de decisiones del aprendizaje en línea y una aplicación al impulso , Journal of Computer and System Sciences, 55 (1): 119-139
- Robert E. Schapire y Yoram Singer (1999); Algoritmos de impulso mejorados mediante predictores con calificación de confianza , aprendizaje automático, 37 (3): 297-336
enlaces externos
- Robert E. Schapire (2003); El enfoque de impulso al aprendizaje automático: una descripción general , taller del MSRI (Instituto de Investigación de Ciencias Matemáticas) sobre estimación y clasificación no lineal
- Zhou Zhi-Hua (2014) Impulsando 25 años , CCL 2014 Keynote.
- 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.
- Zhou, Zhihua (2013). "Sobre la duda sobre el margen de explicación del impulso" (PDF) . Inteligencia artificial . 203 : 1–18. arXiv : 1009,3613 . doi : 10.1016 / j.artint.2013.07.002 . S2CID 2828847 .