Boosting
Boosting es un meta-algoritmo de aprendizaje automático que reduce el sesgo y varianza en un contexto de aprendizaje supervisado. Boosting está basado en el cuestionamiento planteado por Kearns y Valiant (1988, 1989): ¿Puede un conjunto de clasificadores débiles crear un clasificador robusto? 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.
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.
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. 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.
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.
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.
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. 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. 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.
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:
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 .
Otra aplicación del boosting para la categorización binaria es un sistema qué detecta peatones utilizando patrones de movimiento y aspecto. 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.
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.
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. 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.