Hispanopedia Wiki
Articulo de referencia

Impulso (aprendizaje automático)

En aprendizaje automático (ML), el boosting es un método de aprendizaje conjunto que combina un conjunto de modelos menos precisos (llamados "aprendices débiles") para crear un ...

Hispanopedia WikiContenido en espanolLectura gratuita

En aprendizaje automático (ML), el boosting es un método de aprendizaje conjunto que combina un conjunto de modelos menos precisos (llamados "aprendices débiles") para crear un único modelo altamente preciso (un "aprendice fuerte"). A diferencia de otros métodos de conjunto que construyen modelos en paralelo (como el bagging ), los algoritmos de boosting construyen modelos secuencialmente. Cada nuevo modelo en la secuencia se entrena para corregir los errores cometidos por sus predecesores. Este proceso iterativo permite que el modelo general mejore su precisión, particularmente al reducir el sesgo . [ 1 ] El boosting es una técnica popular y eficaz utilizada en el aprendizaje supervisado tanto para tareas de clasificación como de regresión . [ 2 ]

La base teórica del boosting surgió de una pregunta planteada por Kearns y Valiant (1988, 1989): [ 3 ] [ 4 ] "¿Puede un conjunto de clasificadores débiles crear un único clasificador fuerte?" Un clasificador débil se define como un clasificador que se desempeña solo ligeramente mejor que la adivinación aleatoria, mientras que un clasificador fuerte es un clasificador que está altamente correlacionado con la clasificación verdadera. La respuesta afirmativa de Robert Schapire a esta pregunta en un artículo de 1990 condujo al desarrollo de algoritmos prácticos de boosting. [ 5 ] [ 6 ] El primer algoritmo de este tipo fue desarrollado por Schapire, y Freund y Schapire posteriormente desarrollaron AdaBoost , que sigue siendo un ejemplo fundamental de boosting. [ 7 ]

Algoritmos

Aunque el boosting no está restringido algorítmicamente, la mayoría de los algoritmos de boosting consisten en aprender iterativamente clasificadores débiles con respecto a una distribución y agregarlos a un clasificador fuerte final. Al agregarlos, se les asigna un peso relacionado con la precisión de los clasificadores débiles. Después de agregar un clasificador débil, se reajustan los pesos de los datos, 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 clasificadores débiles futuros se centran más en los ejemplos que los clasificadores débiles anteriores clasificaron erróneamente.

Una ilustración que presenta la intuición detrás del algoritmo de boosting, que consta de aprendices paralelos y un conjunto de datos ponderado.

Existen numerosos algoritmos de boosting. Los originales, propuestos por Robert Schapire (una formulación recursiva de puerta de mayoría) [ 8 ] y Yoav Freund (boost por mayoría) [ 9 ] , no eran adaptativos y no podían aprovechar al máximo las capacidades de los aprendices débiles. Posteriormente, Schapire y Freund desarrollaron AdaBoost , un algoritmo de boosting adaptativo que ganó el prestigioso Premio Gödel .

Solo los algoritmos que son algoritmos de potenciación demostrables en la formulación de aprendizaje probablemente aproximadamente correcta pueden denominarse con precisión algoritmos de potenciación . Otros algoritmos que son similares en espíritu a los algoritmos de potenciación a veces se denominan "algoritmos de apalancamiento", aunque también a veces se les denomina incorrectamente algoritmos de potenciación. [ 9 ]

La principal variación entre muchos algoritmos de boosting es su método de ponderación de puntos de datos de entrenamiento e hipótesis . AdaBoost es muy popular y el más significativo históricamente, ya que fue el primer algoritmo que pudo adaptarse a aprendices débiles. A menudo es la base de la cobertura introductoria de boosting en cursos universitarios de aprendizaje automático. [ 10 ] Hay muchos algoritmos más recientes como LPBoost , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost , CatBoost y otros. Muchos algoritmos de boosting se ajustan al marco AnyBoost, [ 9 ] que muestra que boosting realiza descenso de gradiente en un espacio de funciones usando una función de costo convexa .

Categorización de objetos en visión artificial

A partir de imágenes que contienen diversos objetos conocidos del mundo, se puede entrenar un clasificador para clasificar automáticamente los objetos en imágenes futuras. Los clasificadores simples, basados ​​en alguna característica de la imagen del objeto, suelen tener un rendimiento de categorización deficiente. El uso de métodos de potenciación para la categorización de objetos permite unificar los clasificadores débiles de una manera especial para mejorar 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 una 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 incluye la extracción de características , el aprendizaje de un clasificador y la aplicación del clasificador a nuevos ejemplos. Existen muchas maneras de representar una categoría de objetos, por ejemplo, mediante análisis de formas , modelos de bolsa de palabras o descriptores locales como SIFT , etc. Ejemplos de clasificadores supervisados ​​son los clasificadores Naive Bayes , las máquinas de vectores de soporte , las mezclas de gaussianas y las redes neuronales . Sin embargo, la investigación ha demostrado que las categorías de objetos y sus ubicaciones en las imágenes también pueden descubrirse de manera no supervisada . [ 11 ]

Situación actual para la categorización de objetos

El reconocimiento de categorías de objetos en imágenes es un problema complejo en visión artificial , especialmente cuando el número de categorías es elevado. Esto se debe a la alta variabilidad intraclasa 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 tener un aspecto muy diferente. Incluso el mismo objeto puede parecer distinto bajo diferentes puntos de vista, escalas e iluminación . El ruido de fondo y la oclusión parcial también dificultan el 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, por ejemplo, rostros humanos , automóviles , objetos simples, etc. [ 13 ] La investigación ha sido muy activa en el manejo de más categorías y en la habilitación de 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 método consiste en compartir características y potenciarlas.

Mejora de 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 rostros frente a fondo. El algoritmo general es el siguiente:

  1. Forman un gran conjunto de características simples
  2. Inicializar pesos para imágenes de entrenamiento
  3. Para las rondas T
    1. Normalizar los pesos
    2. Para las características disponibles del conjunto, entrene un clasificador utilizando una sola característica y evalúe el error de entrenamiento.
    3. Elija el clasificador con el menor error.
    4. Actualizar los pesos de las imágenes de entrenamiento: aumentar si este clasificador las clasifica incorrectamente, disminuir si las clasifica correctamente.
  4. El clasificador fuerte final se forma como la combinación lineal de los T clasificadores (el coeficiente es mayor si el error de entrenamiento es pequeño).

Después de potenciar, un clasificador construido a partir de 200 características podría producir una tasa de detección del 95% en un10−5{\displaystyle 10^{-5}}tasa de falsos positivos . [ 15 ]

Otra aplicación del boosting para la categorización binaria es un sistema que detecta peatones utilizando 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 caminando. Adopta un enfoque similar al marco de detección de objetos de Viola-Jones .

Optimización para la categorización multiclase

En comparación con la categorización binaria, la categorización multiclase busca características comunes que puedan compartirse entre las categorías simultáneamente. Estas características se convierten en rasgos más genéricos , similares a bordes. Durante el aprendizaje, los detectores de cada categoría pueden entrenarse conjuntamente. En comparación con el entrenamiento por separado, generaliza mejor, requiere menos datos de entrenamiento y menos características para lograr el mismo rendimiento.

El flujo principal del algoritmo es similar al del caso binario. La diferencia radica en que se debe definir de antemano una medida del error de entrenamiento conjunto. En cada iteración, el algoritmo elige un clasificador de una sola característica (se deben fomentar las características que puedan ser compartidas por varias categorías). Esto se puede lograr convirtiendo la clasificación multiclase en binaria (un conjunto de categorías frente al resto) [ 17 ] o introduciendo un error de penalización para las categorías que no poseen la característica del clasificador [ 18 ] .

En el artículo "Sharing visual features for multiclass and multiview object detection", A. Torralba et al. utilizaron GentleBoost para el boosting y demostraron que, cuando los datos de entrenamiento son limitados, el aprendizaje mediante el uso compartido de características ofrece un rendimiento mucho mejor que sin compartir, con el mismo número de rondas de boosting. Además, para un nivel de rendimiento dado, se observa que el número total de características requeridas (y, por lo tanto, el coste computacional del clasificador) para los detectores que comparten características, escala aproximadamente de forma logarítmica con el número de clases, es decir, con un crecimiento más lento que el lineal en el caso sin compartir. Resultados similares se muestran en el artículo "Incremental learning of object detectors using a visual shape alphabet", aunque los autores utilizaron AdaBoost para el boosting.

Algoritmos de boosting convexos frente a no convexos

Los algoritmos de boosting pueden basarse en algoritmos de optimización convexos o no convexos. Los algoritmos convexos, como AdaBoost y LogitBoost , pueden ser "derrotados" por el ruido aleatorio, de modo que no pueden aprender combinaciones básicas y aprendibles de hipótesis débiles. [ 19 ] [ 20 ] Esta limitación fue señalada por Long y Servedio en 2008. Sin embargo, en 2009, varios autores demostraron que los algoritmos de boosting 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 de Long-Servedio.

Véase también

Implementaciones

  • scikit-learn , una biblioteca de aprendizaje automático de código abierto para Python
  • Orange , un paquete de software gratuito para minería de datos, módulo Orange.ensemble
  • Weka es un conjunto de herramientas de aprendizaje automático que ofrece diversas implementaciones de algoritmos de boosting como AdaBoost y LogitBoost.
  • El paquete de R GBM (Generalized Boosted Regression Models) implementa extensiones al algoritmo AdaBoost de Freund y Schapire y a la máquina de potenciación de gradiente de Friedman.
  • jboost ; AdaBoost, LogitBoost, RobustBoost, Boostexter y árboles de decisión alternados
  • Paquete R adabag : Aplica AdaBoost.M1 multiclase, AdaBoost-SAMME y Bagging.
  • Paquete R xgboost : Una implementación de potenciación de gradiente para modelos lineales y basados ​​en árboles.

Notas

  1. ↑ Algunos algoritmos de clasificación basados ​​en boosting en realidad disminuyen el peso de los ejemplos clasificados erróneamente de forma repetida; por ejemplo, boost by majority y BrownBoost .

Referencias

  1. ↑ Leo Breiman (1996). "CLASIFICADORES DE SESGO, VARIANZA Y ARCING" (PDF) . INFORME TÉCNICO. Archivado del original (PDF) el 19 de enero de 2015. Consultado el 19 de enero de 2015. El método Arcing [Boosting] es más eficaz que el método Bagging en la reducción de la varianza.
  2. ↑ Zhou Zhi-Hua (2012). Métodos de conjunto: Fundamentos y algoritmos . Chapman and Hall/CRC. pág. 23. ISBN  978-1439830031El término boosting se refiere a una familia de algoritmos que son capaces de convertir aprendices débiles en aprendices fuertes .
  3. ↑ Michael Kearns (1988); Reflexiones sobre el impulso de hipótesis , manuscrito inédito (proyecto de clase de aprendizaje automático, diciembre de 1988)
  4. ↑ Michael Kearns ; Leslie Valiant (1989). «Limitaciones criptográficas en el aprendizaje de fórmulas booleanas y autómatas finitos». Actas del vigésimo primer simposio anual de la ACM sobre Teoría de la Computación - STOC '89 . Vol. 21. ACM. págs. 433–444 . doi : 10.1145/73007.73049 . ISBN   978-0897913072. S2CID 536357 . 
  5. ↑ Schapire, Robert E. (1990). "The Strength of Weak Learnability" (PDF) . Machine Learning . 5 (2): 197– 227. CiteSeerX 10.1.1.20.723 . doi : 10.1007/bf00116037 . S2CID 53304535. Archivado del original (PDF) el 10 de octubre de 2012. Consultado el 23 de agosto de 2012 .  
  6. ↑ Leo Breiman (1998). "Clasificador de arco (con discusión y réplica del autor)" . Ann. Stat . 26 (3): 801–849 . doi : 10.1214/aos/1024691079 . Schapire (1990) demostró que el boosting es posible. (Página 823)
  7. ↑ Yoav Freund y Robert E. Schapire (1997); Una generalización de la teoría de la decisión del aprendizaje en línea y una aplicación al boosting , Journal of Computer and System Sciences, 55(1):119-139
  8. ↑ Schapire, Robert E. (1990). "The Strength of Weak Learnability" (PDF) . Machine Learning . 5 (2): 197– 227. CiteSeerX 10.1.1.20.723 . doi : 10.1007/bf00116037 . S2CID 53304535. Archivado del original (PDF) el 10 de octubre de 2012. Consultado el 23 de agosto de 2012 .  
  9. 1 2 3 Llew Mason, Jonathan Baxter, Peter Bartlett y Marcus Frean (2000); Boosting Algorithms as Gradient Descent , en SA Solla , TK Leen y K.-R. Muller, editores, Advances in Neural Information Processing Systems 12, pp. 512-518, MIT Press
  10. ↑ Emer, Eric. "Boosting (algoritmo AdaBoost)" (PDF) . MIT . Archivado (PDF) del original el 9 de octubre de 2022. Recuperado el 10 de octubre de 2018 .
  11. ↑ Sivic, Russell, Efros, Freeman y Zisserman, "Descubriendo objetos y su ubicación en imágenes", ICCV 2005
  12. ↑ A. Opelt, A. Pinz, et al., "Reconocimiento genérico de objetos con Boosting", IEEE Transactions on PAMI 2006
  13. ↑ M. Marszalek, "Jerarquías semánticas para el reconocimiento visual de objetos", 2007
  14. ↑ "Desafío de reconocimiento visual a gran escala" . Diciembre de 2017.
  15. ↑ P. Viola, M. Jones, "Detección robusta de objetos en tiempo real", 2001
  16. ↑ Viola, P.; Jones, M.; Snow, D. (2003). Detección de peatones mediante patrones de movimiento y apariencia (PDF) . ICCV. Archivado (PDF) del original el 9 de octubre de 2022.
  17. ↑ A. Torralba, KP Murphy, et al., "Compartir características visuales para la detección de objetos multiclase y multivista", IEEE Transactions on PAMI 2006
  18. ↑ A. Opelt, et al., "Aprendizaje incremental de detectores de objetos mediante un alfabeto de formas visuales", CVPR 2006
  19. ↑ P. Long y R. Servedio. 25ª Conferencia Internacional sobre Aprendizaje Automático (ICML), 2008, págs. 608-615.
  20. ↑ Long, Philip M.; Servedio, Rocco A. (marzo de 2010). "El ruido de clasificación aleatorio derrota a todos los potenciadores de potencial convexo" (PDF) . Machine Learning . 78 (3): 287–304 . doi : 10.1007/s10994-009-5165-z . S2CID 53861. Archivado (PDF) del original el 9 de octubre de 2022. Recuperado el 17 de noviembre de 2015 . 

Lecturas adicionales

  • 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 boosting" (PDF) . Journal of Computer and System Sciences . 55 (1): 119– 139. doi : 10.1006/jcss.1997.1504 .
  • Schapire, Robert E. (1990). "La fuerza de la débil capacidad de aprendizaje" . Machine Learning . 5 (2): 197– 227. doi : 10.1007/BF00116037 . S2CID 6207294 . 
  • Schapire, Robert E.; Singer, Yoram (1999). "Algoritmos de boosting mejorados mediante predictores con índice de confianza" . Machine Learning . 37 (3): 297– 336. doi : 10.1023/A:1007614523901 . S2CID 2329907 . 
  • Zhou, Zhihua (2008). "Explicación marginal del algoritmo de boosting" (PDF) . En: Actas de la 21.ª Conferencia Anual sobre Teoría del Aprendizaje (COLT'08) : 479–490 .
  • Zhou, Zhihua (2013). "Sobre la duda acerca de la explicación del margen de boosting" (PDF) . Inteligencia Artificial . 203 : 1–18 . arXiv : 1009.3613 . doi : 10.1016/j.artint.2013.07.002 . S2CID 2828847 . 
  • Robert E. Schapire (2003); El enfoque de potenciación para el aprendizaje automático: una visión general , Taller del MSRI (Instituto de Investigación en Ciencias Matemáticas) sobre estimación y clasificación no lineales.
  • Boosting: Fundamentos y algoritmos, por Robert E. Schapire y Yoav Freund
Lecturas relacionadas
6 articulos
Aprendizaje automáticoAprendizaje automáticoEl aprendizaje automático ( ML ) es un campo de estudio en inteligencia artificial que se ocupa del desarrollo y estudio de algoritmos estadísticos...Aprendizaje en conjuntoAprendizaje en conjuntoEn estadística y aprendizaje automático , los métodos de conjunto utilizan múltiples algoritmos de aprendizaje para obtener un mejor rendimiento pr...{\estilo de visualización D}Agregación de BootstrapLa agregación bootstrap , también llamada bagging (de bootstrap agg regat ing ) , es un metaalgoritmo de conjunto de aprendizaje automático diseñad...Relación entre sesgo y varianzaRelación entre sesgo y varianzaEn estadística y aprendizaje automático , el equilibrio entre sesgo y varianza describe la relación entre la complejidad de un modelo, la precisión...Aprendizaje supervisadoEl aprendizaje supervisado ( SL ) es un paradigma en el aprendizaje automático donde los objetos de entrada (por ejemplo, un vector de variables pr...{\displaystyle \operatorname {puntaje} (\mathbf {X} _{i},k)={\boldsymbol {\beta }}_{k}\cdot \mathbf {X} _{i},}Clasificación estadísticaCuando la clasificación la realiza una computadora, normalmente se utilizan métodos estadísticos para desarrollar el algoritmo.