Boosting

Boosting és un meta-algoritme d'aprenentage automàtic que reduïx el biaix i varianza en un context d'aprenentage supervisat.^[1]^[2] Boosting està basat en el cuestionamiento plantejat per Kearns i Valiant (1988, 1989): ¿Pot un conjunt de classificadors dèbils crear un classificador robust?^[3]^[4] Un classificador dèbil està definit per a ser un classificador el qual està sol débilmente correlacionado en la classificació correcta (el mateix classifica millor que un classificador aleatori). En contrast, un classificador robust és un classificador que té un millor eixercite que el d'un classificador dèbil, ya que les seues classificacions s'aproximen més a les verdaderes classes.

En 1990 Robert Schapire respon afirmativamente al cuestionamiento de Kearns i Valiant en un artícul, dita resposta va tindre repercussions significatives en l'aprenentage automàtic i l'estadística, esta potent influència va dur al desenroll del boosting.^[5]^[6]

Quan va ser introduït per primera volta, el boosting referia simplement al problema de convertir un classificador dèbil en un robust. «Informalmente, el problema pregunta si un algoritme d'aprenentage eficaç […] que produïx una hipòtesis el rendiment de la qual és només llaugerament millor que aleatori endevinant [p. ej. un estudiant dèbil] implica l'existència d'un algoritme eficaç que produïx una hipòtesis d'exactitut arbitrària [i.i. un estudiant fort]». Els algoritmes que alcancen a produir dites hipòtesis pronte varen ser denominats boosting.

Algoritmes de boosting

El boosting consistix en combinar els resultats de varis classificadors dèbils per a obtindre un classificador robust. Quan s'afigen estos classificadors dèbils, li'l fa de modo que estos tinguen diferent pes en funció de l'exactitut de les seues prediccions. Després de que s'afig un classificador dèbil, les senyes canvien la seua estructura de pesos: els casos que són mal classificats guanyen pes i els que són classificats correctament perden pes. Aixina, els classificadors forts se centren de major manera en els casos que varen ser mal classificats pels classificadors dèbils.

Hi ha molts algoritmes de boosting. Els algoritmes originals, proposts per Robert Schapire i Yoav Freund, no va ser adaptiva i no podria prendre ventaja plena dels classificadors dèbils.^[7] No obstant, Schapire i Freund després varen desenrollar AdaBoost, un algoritme adaptatiu que va guanyar el prestigiós Premi Gödel.

AdaBoost és l'algoritme més popular i és potser el més important històricament ya que va ser la primera formulació d'un algoritme que va poder deprendre a partir dels classificadors dèbils . Aixina i tot, hi ha molts algoritmes més recents com LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost que realisen la mateixa tasca. Molts algoritmes de boosting encaixen en el marc de AnyBoost, el qual mostra que els algoritmes de boosting actuen a través del descens del gradient en l'espai funcional, utilisant una funció de cost convexa.

Categorisació d'objectes

Donada una cantitat d'imàgens que contenen varis objectes, un classificador pot deprendre d'ells i aixina categorizar automàticament els objectes en imàgens futures. Els classificadors dèbils són construïts a partir d'alguna característica de l'objecte que tendix a ser débilmente classificat en l'eixercite dels classificadors. Utilisar boosting para categorizar l'objecte és una manera de combinar els classificadors dèbils de manera tal d'aumentar la capacitat global de categorisació.

El problema de la categorisació de l'objecte

La categorisació d'objectes és una tasca típica de la visió artificial que implica determinar si una image conté algun tipo d'objecte especificat. L'idea està estretament relacionada en reconeiximent, identificació, i detecció. La categorisació d'objectes a partir de la seua apariència, típicament conté l'extracció de característiques del mateix, que són depreses per un classificador, que a la seua volta deprén cada volta que són afegitons nous casos. Hi ha moltes maneres de representar una categoria d'objectes, p. eix. a través de l'anàlisis de forma, models de bossa de paraules, o descriptivos locals com CRIBAR, etc. Eixemples de classificadors supervisats són el Naive Bayes, SVM, rets neuronals, etc. Aixina i tot, diversos estudis han mostrat que els tipos d'objecte i les seues ubicacions en les imàgens poden ser descobertes també per mig de métodos d'aprenentage no supervisat.^[8]

Statu quo per a la categorisació d'objectes.

El reconeiximent de categories d'objecte en imàgens és un problema desafiant en la visió artificial, especialment quan el número de categories és gran. Açò es deu a l'alta variabilitat intraclase i a la necessitat de generalisacions a través de les variacions dels objectes dins d'una determinada categoria. Els objectes dins una categoria pot ser prou diferents entre sí. Inclús el mateix objecte pot semblar diferent baix diferents punts de vista, escales, i allumenament.^[9] Els humans són capaços de reconéixer mils de tipos d'objectes, mentres que la majoria dels sistemes de reconeiximent d'objectes estan entrenats per a reconéixer només uns quants, p. eix., cara humana, coche, objectes senzills, etc.^[10] La busca ha segut molt activa tractant més categories i habilitant adició incrementals de categories noves, i a pesar de que el problema general no s'ha resolt, varis detectors multi-categoria d'objecte (número de categories entorn 20) per a escenes agrupades han segut desenrollats.

Boosting per a categorisació binaria

Utilisem AdaBoost per a detecció de cara com un eixemple de categorisació binaria. Les dos categories són cares versus fondo. L'algoritme general és com seguix:

Forma un conjunt gran de característiques senzilles
Inicializa pesos per a entrenar imàgens
Per a T iteracionesː
1. Normalisar els pesos
2. Per a característiques disponibles del conjunt, s'entrena un classificador utilisant solament una característica i s'evalua l'error de formació
3. Triar el classifier en l'error més baix
4. Actualisació els pesos de les imàgens de formació: aumenta el pes si el classificador classifica de forma errònea l'objecte, disminuïx si ho fa correctament
Forma classificador final robust com la combinació llineal dels T classificadors.

Despuix d'aplicar boosting, un classificador construït a partir de 200 característiques pot collir un índex de detecció del 95 % baix un índex de fals positiu de el $1 0^{- 5}$ .^[11]

Una atra aplicació del boosting per a la categorisació binaria és un sistema que detecta peatons utilisant patrons de moviment i aspecte.^[12] Este treball és el primer en combinar abdós informacions, la de moviment i informació d'aspecte com a característiques per a detectar una persona caminant. La mateixa té un enfocament similar al de la detecció de rostres mostrada en el treball de Viola i Jones.

Boosting per a categorisació multi-classe

Comparat en categorisació binaria, la categorisació multi-classe busca característiques comunes que poden ser compartides per les categories al mateix temps. Durant l'aprenentage, els detectors de cada categoria poden ser entrenats conjuntament. Comparat en l'entrenament separat per categories, este generalisa millor, necessita menys senyes d'entrenament, i requerix un número menor de característiques per a conseguir el mateix rendiment.

L'estructura principal de l'algoritme és similar al cas binario. Lo que és diferent és que és necessari definir per avant una mida de l'error conjunt. Durant cada iteración l'algoritme tria un classificador d'una sola característica (a on són més desijables les característiques que poden ser compartides per més categories). Açò pot ser fet convertint la classificació multiclase en una binaria (un conjunt de categories contra el restant), o introduint una penalisació de l'error de les categories que no tenen la característica del classificador.^[13]^[14]

Vore també

Referències

↑ «BIAS, VARIANCE, AND ARCING CLASSIFIERS». TECHNICAL REPORT. Archivat des d'el original, el 19 de giner de 2015. Consultat el 19 de giner de 2015. «Arcing [Boosting] is more successful than bagging in variance reduction»
↑ Zhou Zhi-Hua (2012). Ensemble Methods: Foundations and Algorithms, Chapman and Hall/CRC, p. 23. ISBN 978-1439830031. «The term boosting refers to a family of algorithms that llaure able to convert weak learners to strong learners»
↑ Michael Kearns(1988); Thoughts on Hypothesis Boosting, Unpublished manuscript (Machine Learning class project, December 1988)
↑ Symposium on Theory of computing.ACM.21
433–444.doi:10.1145/73007.73049.Consultat el 18 de giner de 2015.
↑ (1990).Machine Learning.Kluwer Academic Publishers.Boston, MA:5(2)
197–227.doi:10.1007/bf00116037.
↑ Ann. Stat..26(3)
801–849.doi:10.1214/aos/1024691079.Consultat el 17 de novembre de 2015.
↑ Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean (2000); Boosting Algorithms as Gradient Descent, in S. A. Solla, T. K. Lligen, and K.-R. Muller, editors, Advances in Neural Information Processing Systems 12, pp. 512-518, MIT Press.
↑ Sivic, Russell, Efros, Freeman & Zisserman, "Discovering objects and their location in images", ICCV, 2005.
↑ A. Opelt, A. Pinz, et al., "Generic Object Recognition with Boosting", IEEE Transactions on PAMI, 2006.
↑ M. Marszalek, "Semantic Hierarchies for Visual Object Recognition", 2007.
↑ P. Viola, M. Jones, "Robust Real-clave Object Detection", 2001.
↑ P. Viola, et al., "Detecting Pedestrians Using Patterns of Motion and Appearance", ICCV 2003.
↑ A. Torralba, K. P. Murphy, et al., "Sharing visual features for multiclass and multiview object detection", IEEE Transactions on PAMI 2006
↑ A. Opelt, et al., "Incremental learning of object detectors using a visual shape alphabet", CVPR 2006.

Referències

Este artícul conté una traducció derivada de «Boosting» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] «BIAS, VARIANCE, AND ARCING CLASSIFIERS». TECHNICAL REPORT. Archivat des d'el original, el 19 de giner de 2015. Consultat el 19 de giner de 2015. «Arcing [Boosting] is more successful than bagging in variance reduction»

[2] Zhou Zhi-Hua (2012). Ensemble Methods: Foundations and Algorithms, Chapman and Hall/CRC, p. 23. ISBN 978-1439830031. «The term boosting refers to a family of algorithms that llaure able to convert weak learners to strong learners»

[Kearns88-3] Michael Kearns(1988); Thoughts on Hypothesis Boosting, Unpublished manuscript (Machine Learning class project, December 1988)

[4] Symposium on Theory of computing.ACM.21
433–444.doi:10.1145/73007.73049.Consultat el 18 de giner de 2015.

[Schapire90-5] (1990).Machine Learning.Kluwer Academic Publishers.Boston, MA:5(2)
197–227.doi:10.1007/bf00116037.

[6] Ann. Stat..26(3)
801–849.doi:10.1214/aos/1024691079.Consultat el 17 de novembre de 2015.

[Mason00-7] Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean (2000); Boosting Algorithms as Gradient Descent, in S. A. Solla, T. K. Lligen, and K.-R. Muller, editors, Advances in Neural Information Processing Systems 12, pp. 512-518, MIT Press.

[8] Sivic, Russell, Efros, Freeman & Zisserman, "Discovering objects and their location in images", ICCV, 2005.

[9] A. Opelt, A. Pinz, et al., "Generic Object Recognition with Boosting", IEEE Transactions on PAMI, 2006.

[10] M. Marszalek, "Semantic Hierarchies for Visual Object Recognition", 2007.

[11] P. Viola, M. Jones, "Robust Real-clave Object Detection", 2001.

[12] P. Viola, et al., "Detecting Pedestrians Using Patterns of Motion and Appearance", ICCV 2003.

[13] A. Torralba, K. P. Murphy, et al., "Sharing visual features for multiclass and multiview object detection", IEEE Transactions on PAMI 2006

[14] A. Opelt, et al., "Incremental learning of object detectors using a visual shape alphabet", CVPR 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]