En el aprendizaje automático , el impulso es un metaalgoritmo conjunto para reducir principalmente el sesgo y la varianza. [1] Se utiliza en el aprendizaje supervisado y en una familia de algoritmos de aprendizaje automático que convierten a los alumnos débiles en alumnos fuertes. [2]
El concepto de impulso se basa en la pregunta planteada por Kearns y Valiant (1988, 1989): [3] [4] "¿Puede un conjunto de alumnos débiles crear un único alumno fuerte?" Un alumno débil se define como un clasificador que está sólo ligeramente correlacionado con la clasificación verdadera (puede etiquetar ejemplos mejor que las conjeturas aleatorias). Por el contrario, un buen alumno es un clasificador que está arbitrariamente bien correlacionado con la clasificación verdadera.
Robert Schapire respondió afirmativamente a la pregunta planteada por Kearns y Valiant en un artículo publicado en 1990 [5] . Esto ha tenido ramificaciones significativas en el aprendizaje automático y la estadística , sobre todo conduciendo al desarrollo del impulso. [6]
Cuando se presentó por primera vez, el problema del impulso de hipótesis simplemente se refería al proceso de convertir a un alumno débil en un alumno fuerte. "Informalmente, el problema [de refuerzo de hipótesis] pregunta si un algoritmo de aprendizaje eficiente [...] que genera una hipótesis cuyo rendimiento es sólo ligeramente mejor que la adivinación aleatoria [es decir, un alumno débil] implica la existencia de un algoritmo eficiente que genera una hipótesis de aprendizaje arbitrario". precisión [es decir, un buen estudiante]". [3] Los algoritmos que logran reforzar las hipótesis rápidamente pasaron a ser conocidos 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]
Si bien el impulso no está restringido algorítmicamente, la mayoría de los algoritmos de impulso consisten en aprender de forma iterativa 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 alumnos 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 mayor peso y los ejemplos clasificados correctamente pierden peso. [nota 1] Por lo tanto, los futuros alumnos débiles se centran más en los ejemplos que los alumnos débiles anteriores clasificaron erróneamente.
Hay muchos algoritmos de impulso. Los originales, propuestos por Robert Schapire (una formulación recursiva de puerta mayoritaria), [5] y Yoav Freund (impulso por mayoría), [9] no eran adaptativos y no podían aprovechar al máximo a los alumnos débiles. Schapire y Freund desarrollaron entonces AdaBoost , un algoritmo de refuerzo adaptativo que ganó el prestigioso Premio Gödel .
Sólo los algoritmos que son algoritmos de refuerzo demostrables en la formulación de aprendizaje probablemente aproximadamente correcta pueden denominarse con precisión algoritmos de refuerzo . Otros algoritmos que son similares en espíritu [ se necesita aclaración ] a los algoritmos de impulso a veces se denominan "algoritmos de aprovechamiento", aunque a veces también se les llama incorrectamente algoritmos de impulso. [9]
La principal variación entre muchos algoritmos de impulso es su método de ponderar las hipótesis y los puntos de datos de entrenamiento . AdaBoost es muy popular y el más importante históricamente, ya que fue el primer algoritmo que pudo adaptarse a los alumnos 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 .
Dadas 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 creados en función de alguna característica de la imagen del objeto tienden a tener un rendimiento de categorización débil. 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. [ cita necesaria ]
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 la 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, a partir de 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 su ubicación en las imágenes también se pueden descubrir sin supervisión . [11]
El reconocimiento de categorías de objetos en imágenes es un problema desafiante en 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 generalización entre variaciones de objetos dentro de la misma categoría. Los objetos dentro de una categoría pueden verse bastante diferentes. Incluso el mismo objeto puede parecer diferente bajo diferentes puntos de vista, escala e iluminación . El desorden del fondo y la oclusión parcial también añaden dificultades al reconocimiento. [12] Los 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 solo unos pocos, [ cuantificar ] por ejemplo, rostros humanos , automóviles , objetos simples, etc. [13] [ ¿necesita actualización? ] La investigación ha sido muy activa para abordar 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 hasta cientos o miles de categorías [14] ). Un medio es compartir y mejorar funciones .
AdaBoost se puede utilizar para la detección de rostros como ejemplo de categorización binaria . Las dos categorías son rostros versus fondo. El algoritmo general es el siguiente:
Después del impulso, un clasificador construido a partir de 200 características podría producir una tasa de detección del 95 % con una tasa de falsos positivos . [15]
Otra aplicación del refuerzo para la categorización binaria es un sistema que detecta peatones mediante patrones de movimiento y apariencia. [16] Este trabajo es el primero en combinar información de movimiento e 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 de Viola-Jones .
En comparación con la categorización binaria, la categorización de clases múltiples busca características comunes que se puedan compartir entre las categorías al mismo tiempo. Se vuelven características más genéricas tipo borde . Durante el aprendizaje, los detectores de cada categoría se pueden entrenar de forma conjunta. 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. La diferencia es que se debe definir de antemano una medida del error de entrenamiento conjunto. Durante cada iteración, el algoritmo elige un clasificador de una sola característica (se fomentarán las características que puedan ser compartidas por más categorías). Esto se puede hacer convirtiendo la clasificación de clases múltiples en una binaria (un conjunto de categorías versus el 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 funciones compartidas 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 clases, 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 utilizando un alfabeto de formas visual", aunque los autores utilizaron AdaBoost para impulsar.
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 aprendibles 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 optimización no convexa, como BrownBoost , pueden aprender de conjuntos de datos ruidosos y pueden aprender específicamente el clasificador subyacente del conjunto de datos Long-Servedio.
El arco [impulso] tiene más éxito que el embolsado en la reducción de la variación
El término impulso se refiere a una familia de algoritmos que pueden convertir a los estudiantes débiles en estudiantes fuertes.
Schapire (1990) demostró que el refuerzo es posible. (Página 823)
