Boosting

Boosting es un meta-algoritmo de aprendizaje automático que reduce el sesgo y varianza en un contexto de aprendizaje supervisado.^[1]​^[2]​ Boosting está basado en el cuestionamiento planteado por Kearns y Valiant (1988, 1989): ¿Puede un conjunto de clasificadores débiles crear un clasificador robusto?^[3]​^[4]​ 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.^[5]​^[6]​

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. 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 prontofueron 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 débiles 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.^[7]​ Sin embargo, Schapire y Freund luego desarrollaron AdaBoost, un algoritmo adaptativo que ganó el prestigioso Premio 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 de 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 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 específado. 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, modelos de bolsa de palabras, o descriptivos locales como CRIBAR, etc. Ejemplos de clasificadores supervisados son el Naive Bayes, SVM, 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.^[8]​

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 cuándo 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.^[9]​ 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.^[10]​ 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:

1. Forma un conjunto grande de características sencillas
2. Inicializa pesos para entrenar imágenes
3. Para T iteracionesː
   1. Normalizar los pesos
   2. Para características disponibles del conjunto, se entrena un clasificador utilizando solo una característica y se evalúa el error de formación
   3. Escoger el classifier con el error más bajo
   4. Actualización los pesos de las imágenes de formación: aumenta el peso si el clasificador clasifica de forma errónea el obeto, disminuye si lo hace correctamente
4. 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 % bajo un índice de falso positivo del ${\displaystyle 10^{-5}}$ .^[11]​

Otra aplicación del boosting para la categorización binaria es un sistema qué detecta peatones utilizando patrones de movimiento y aspecto.^[12]​ 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 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 qué 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.^[13]​^[14]​

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.^[15]​ 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

1. Leo Breiman (1996). . TECHNICAL REPORT. Archivado desde el original el 19 de enero de 2015. Consultado el 19 de enero 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 are able to convert weak learners to strong learners». 
3. Michael Kearns(1988); Thoughts on Hypothesis Boosting, Unpublished manuscript (Machine Learning class project, December 1988)
4. Michael Kearns; Leslie Valiant (1989). «Crytographic limitations on learning Boolean formulae and finite automata». Symposium on Theory of computing (ACM) 21: 433-444. doi:10.1145/73007.73049. Consultado el 18 de enero de 2015. 
5. Schapire, Robert E. (1990). . Machine Learning (Boston, MA: Kluwer Academic Publishers) 5 (2): 197-227. doi:10.1007/bf00116037. citeseerx: 10.1.1.20.723. Archivado desde el original el 10 de octubre de 2012. 
6. Leo Breiman (1998). «Arcing classifier (with discussion and a rejoinder by the author)». Ann. Stat. 26 (3): 801-849. doi:10.1214/aos/1024691079. Consultado el 17 de noviembre de 2015. «Schapire (1990) proved that boosting is possible. (Page 823)». 
7. 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. 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-time 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.
15. Long, Philip M.; Servedio, Rocco A. (March 2010). «Random classification noise defeats all convex potential boosters». Machine Learning (Springer US) 78 (3): 287-304. doi:10.1007/s10994-009-5165-z. Consultado el 17 de noviembre de 2015. 

•   Datos: Q466303