Edición de «Boosting»

'''Boosting''' es un meta-algoritmo de aprendizaje automático que reduce el sesgo y varianza en un contexto de [[aprendizaje supervisado]].<ref>{{cita web|url=http://oz.berkeley.edu/~breiman/arcall96.pdf|título=BIAS, VARIANCE, AND ARCING CLASSIFIERS|apellido1=Leo Breiman|nombre1=|apellido2=|nombre2=|fecha=1996|website=|publisher=TECHNICAL REPORT|cita=Arcing [Boosting] is more successful than bagging in variance reduction|fechaacceso=19 de enero de 2015|urlarchivo=https://web.archive.org/web/20150119081741/http://oz.berkeley.edu/~breiman/arcall96.pdf|fechaarchivo=19 de enero de 2015}}</ref><ref>{{cita libro|apellido=Zhou Zhi-Hua|nombre=|fecha=2012|título=Ensemble Methods: Foundations and Algorithms|url=|ubicación=|publisher=Chapman and Hall/CRC|page=23|isbn=978-1439830031|cita=The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners}}</ref> Boosting está basado en el cuestionamiento planteado por Kearns y [[Leslie Valiant|Valiant]] (1988, 1989): ¿Puede un conjunto de clasificadores débiles crear un clasificador robusto?<ref name="Kearns88">Michael Kearns(1988); [http://www.cis.upenn.edu/~mkearns/papers/boostnote.pdf ''Thoughts on Hypothesis Boosting''], Unpublished manuscript (Machine Learning class project, December 1988)</ref><ref>{{cita publicación|apellido=Michael Kearns|nombre=|apellido2=Leslie Valiant|nombre2=|fecha=1989|título=Crytographic limitations on learning Boolean formulae and finite automata|url=http://dl.acm.org/citation.cfm?id=73049|publicación=Symposium on Theory of computing|publisher=ACM|volumen=21|número=|pages=433–444|doi=10.1145/73007.73049|cita=|fechaacceso=18 de enero de 2015}}</ref> Un clasificador débil está definido para ser un clasificador el cual está solo débilmente correlacionado con la clasificación correcta (el mismo clasifica mejor que un clasificador aleatorio). En contraste, un clasificador robusto es un clasificador que tiene un mejor desempeño que el de un clasificador débil, ya que sus clasificaciones se aproximan más a las verdaderas clases.

En 1990 Robert Schapire responde afirmativamente al cuestionamiento de Kearns y Valiant en un artículo, dicha respuesta tuvo repercusiones significativas en el aprendizaje automático y la estadística, esta potente influencia llevó al desarrollo del boosting.<ref name="Schapire90">{{cita publicación|nombre=Robert E.|apellido=Schapire|año=1990|id=citeseerx: 10.1.1.20.723|url=http://www.cs.princeton.edu/~schapire/papers/strengthofweak.pdf|título=The Strength of Weak Learnability|publicación=Machine Learning|volumen=5|número=2|pages=197–227|ubicación=Boston, MA|publisher=Kluwer Academic Publishers|doi=10.1007/bf00116037|urlarchivo=https://web.archive.org/web/20121010030839/http://www.cs.princeton.edu/~schapire/papers/strengthofweak.pdf|fechaarchivo=10 de octubre de 2012}}</ref><ref>{{cita publicación|apellido=[[Leo Breiman]]|nombre=|apellido2=|nombre2=|fecha=1998|título=Arcing classifier (with discussion and a rejoinder by the author)|url=https://projecteuclid.org/euclid.aos/1024691079|publicación=Ann. Stat.|publisher=|volumen=26|número=3|pages=801–849|doi=10.1214/aos/1024691079|cita=Schapire (1990) proved that boosting is possible. (Page 823)|fechaacceso=17 de noviembre de 2015}}</ref>

Cuando fue introducido por primera vez, ''el boosting refería simplemente al'' problema de convertir un clasificador débil en uno robusto. «Informalmente, el problema pregunta si un algoritmo de aprendizaje eficaz […] que produce una hipótesis cuyo rendimiento es sólo ligeramente mejor que aleatorio adivinando [p.{{esd}}ej. un estudiante débil] implica la existencia de un algoritmo eficaz que produce una hipótesis de exactitud arbitraria [i.e. un estudiante fuerte]». Los algoritmos que alcanzan a producir dichas hipótesis pronto fueron denominados ''boosting''.

== Algoritmos de boosting ==
El boosting consiste en combinar los resultados de varios clasificadores débiles para obtener un clasificador robusto. Cuando se añaden estos clasificadores débiles, se lo hace de modo que estos tengan diferente peso en función de la exactitud de sus predicciones. Luego de que se añade un clasificador débil, los datos cambian su estructura de pesos: los casos que son mal clasificados ganan peso y los que son clasificados correctamente pierden peso. Así, los clasificadores fuertes se centran de mayor manera en los casos que fueron mal clasificados por los clasificadores débiles.

Hay muchos algoritmos de boosting. Los algoritmos originales, propuestos por Robert Schapire y Yoav Freund, no fue adaptiva y no podría tomar ventaja llena de los clasificadores débiles.<ref name="Mason00">Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean (2000); ''Boosting Algorithms as Gradient Descent'', in S. A. Solla, T. K. Leen, and K.-R. Muller, editors, ''Advances in Neural Information Processing Systems'' 12, pp.{{esd}}512-518, MIT Press.</ref> Sin embargo, Schapire y Freund luego desarrollaron AdaBoost, un algoritmo adaptativo que ganó el prestigioso Premio [[Premio Gödel|Gödel]].

AdaBoost es el algoritmo más popular y es quizá el más importante históricamente ya que fue la primera formulación de un algoritmo que pudo aprender a partir de los clasificadores débiles . Aun así, hay muchos algoritmos más recientes como LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost que realizan la misma tarea. Muchos algoritmos de boosting encajan en el marco de AnyBoost, el cual muestra que los algoritmos de boosting actúan a través del descenso del gradiente en el espacio funcional, utilizando una función de coste [[función convexa|convexa]].

== Categorización de objetos ==
Dada una cantidad de imágenes que contienen varios objetos, un clasificador puede aprender de ellos y así categorizar automáticamente los objetos en imágenes futuras. Los clasificadores débiles son construidos a partir de alguna característica del objeto que tiende a ser débilmente clasificado en el desempeño de los clasificadores. Utilizar boosting para categorizar el objeto es una manera de combinar los clasificadores débiles de manera tal de aumentar la capacidad global de categorización.

=== El problema de la categorización del objeto ===
La categorización de objetos es una tarea típica de la [[visión artificial]] que implica determinar si una imagen contiene algún tipo de objeto especificado. La idea está estrechamente relacionada con reconocimiento, identificación, y detección. 
La categorización de objetos a partir de su apariencia, típicamente contiene la extracción de características del mismo, que son aprendidas por un clasificador, que a su vez aprende cada vez que son añadidos nuevos casos. Hay muchas maneras de representar una categoría de objetos, p. ej. a través del análisis de forma, [[modelo bolsa de palabras|modelos de bolsa de palabras]], o descriptivos locales como [[scale-invariant feature transform|CRIBAR]], etc. Ejemplos de clasificadores supervisados son el [[clasificador bayesiano ingenuo|Naive Bayes]], [[máquinas de vectores de soporte|SVM]], [[red neuronal artificial|redes neuronales]], etc. Aun así, diversos estudios han mostrado que los tipos de objeto y sus ubicaciones en las imágenes pueden ser descubiertas también mediante métodos de [[aprendizaje no supervisado]].<ref>Sivic, Russell, Efros, Freeman & Zisserman, "Discovering objects and their location in images", ICCV, 2005.</ref>

=== ''Statu quo'' para la categorización de objetos. ===
El reconocimiento de categorías de objeto en imágenes es un problema desafiante en la visión artificial, especialmente cuando el número de categorías es grande. Esto se debe a la alta variabilidad intraclase y a la necesidad de generalizaciones a través de las variaciones de los objetos dentro de una determinada categoría. Los objetos dentro una categoría puede ser bastante diferentes entre sí. Incluso el mismo objeto puede parecer diferente bajo diferentes puntos de vista, escalas, e iluminación.<ref>A. Opelt, A. Pinz, et{{esd}}al., "Generic Object Recognition with Boosting", IEEE Transactions on PAMI, 2006.</ref> Los humanos son capaces de reconocer miles de tipos de objetos, mientras que la mayoría de los sistemas de [[reconocimiento de objetos]] están entrenados para reconocer sólo unos cuantos, p. ej., cara humana, coche, objetos sencillos, etc.<ref>M. Marszalek, "Semantic Hierarchies for Visual Object Recognition", 2007.</ref> La búsqueda ha sido muy activa tratando más categorías y habilitando adiciones incrementales de categorías nuevas, y a pesar de que el problema general no se ha resuelto, varios detectores multi-categoría de objeto (número de categorías alrededor 20) para escenas agrupadas han sido desarrollados.

=== ''Boosting'' para categorización binaria ===
Utilizamos AdaBoost para detección de cara como un ejemplo de categorización binaria. Las dos categorías son caras versus fondo. El algoritmo general es como sigue:
# Forma un conjunto grande de características sencillas
# Inicializa pesos para entrenar imágenes
# Para T iteracionesː
## Normalizar los pesos
## Para características disponibles del conjunto, se entrena un clasificador utilizando solo una característica y se evalúa el error de formación
## Escoger el classifier con el error más bajo
## Actualización los pesos de las imágenes de formación: aumenta el peso si el clasificador clasifica de forma errónea el objeto, disminuye si lo hace correctamente
# Forma clasificador final robusto como la [[combinación lineal]] de los T clasificadores.
Después de aplicar boosting, un clasificador construido a partir de 200 características puede cosechar un índice de detección del 95{{esd}}% bajo un índice de falso positivo del <math>10^{-5}</math>.<ref>P. Viola, M. Jones, "Robust Real-time Object Detection", 2001.</ref>

Otra aplicación del boosting para la categorización binaria es un sistema que detecta peatones utilizando [[Patrón (estructura)|patrones]] de movimiento y aspecto.<ref>P. Viola, et al., "Detecting Pedestrians Using Patterns of Motion and Appearance", ICCV 2003.</ref> Este trabajo es el primer en combinar ambas informaciones, la de movimiento e información de aspecto como características para detectar una persona caminando. La misma tiene un enfoque similar al de la detección de rostros mostrada en el trabajo de Viola y Jones.

=== Boosting para categorización multi-clase ===
Comparado con categorización binaria, la categorización multi-clase busca características comunes que pueden ser compartidas por las categorías al mismo tiempo. Durante el aprendizaje, los detectores de cada categoría pueden ser entrenados conjuntamente. Comparado con el entrenamiento separado por categorías, este [[generalización|generaliza]] mejor, necesita menos datos de entrenamiento, y requiere un número menor de características para conseguir el mismo rendimiento.

La estructura principal del algoritmo es similar al caso binario. Lo que es diferente es que es necesario definir por adelantado una medida del error conjunto. Durante cada iteración el algoritmo escoge un clasificador de una sola característica (donde son más deseables las características que pueden ser compartidas por más categorías). Esto puede ser hecho convirtiendo la clasificación multiclase en una binaria (un conjunto de categorías contra el resto), o introduciendo una penalización del error de las categorías que no tienen la característica del clasificador.<ref>A. Torralba, K. P. Murphy, et al., "Sharing visual features for multiclass and multiview object detection", IEEE Transactions on PAMI 2006</ref><ref>A. Opelt, et al., "Incremental learning of object detectors using a visual shape alphabet", CVPR 2006.</ref>

== Crítica ==
En 2008 Phillip Long (en Google) y Rocco A. Servedio (Universidad de Columbia) publican un artículo en la 25.ª Conferencia internacional de aprendizaje automático que sugiere que muchos de estos algoritmos son probablemente defectuosos.<ref name="long-criticism">{{cita publicación|apellido=Long|nombre=Philip M.|apellido2=Servedio|nombre2=Rocco A.|fecha=March 2010|título=Random classification noise defeats all convex potential boosters|url=https://www.cs.columbia.edu/~rocco/Public/mlj9.pdf|publicación=Machine Learning|publisher=Springer US|volumen=78|número=3|pages=287–304|doi=10.1007/s10994-009-5165-z|fechaacceso=17 de noviembre de 2015}}</ref> Concluyen que «''boosters'' potencialmente convexos no pueden resistir el ruido de la clasificación aleatoria», por ello la aplicabilidad de tales algoritmos para datos del mundo real (por tanto ruidosos) es cuestionable. El artículo muestra que si cualquier fracción del dato de formación es mal clasificado, el algoritmo de boosting encuentra extremadamente difícil de clasificar correctamente los datos, y no produce resultados con una precisión mayor a 1/2. Este resultado no aplica a los boosters basados en programas ramificados pero sí aplica a AdaBoost, LogitBoost, y otros.

== Véase también ==
* ''[[Random forest]]''
* [[Árbol de decisión alternativo]]
* [[Agregación de bootstrap]]
* [[Regresión logística]]
* [[Principio de máxima entropía]]
* [[Red neuronal artificial]]
* [[Máquinas de vectores de soporte]]
* [[Validación cruzada]]
* [[Aprendizaje automático]]

== Referencias ==
{{Listaref}}

{{Control de autoridades}}
[[Categoría:Algoritmos de clasificación]]
[[Categoría:Visión por computadora]]
[[Categoría:Reconocimiento de patrones]]