Una breve introducción al Boosting

NOTA:recomiendo que para entender varios de los conceptos que uso en este post, se debe tener un antescedente en la materia de Aprendizaje. En lo personal, yo aprendí con el libro de Machine Learning de Tom Mitchel, Quien no tenga el libro puede utilizar estos apuntes que encontré en línea de la Universidad de Standford, los apuntes están en la parte donde dice Lecture Notes, están en inglés, pero ni pexsi, están padres.

Un tema que ha llamado recientemente mi atención en el área de Aprendizaje, es el tema de Boosting. Decidí hacer esta entrada, debido a que NO he encontrada nada de información sobre el tema, en español. Y siempre es agradable poder leer los temas que nos interesan en nuestra lengua madre.
Así que aqui va : Boosting explicado en Español!


Es importante primero entender a que se refiere la palabra Boost en inglés. To boost es empujar hacia arriba, fomentar, aumentar, mejorar algo. Cuando se utiliza la palabra Boosting en el área de Aprendizaje se refiere a un método para mejorar la precisión que tiene un algoritmo de aprendizaje X.

Historia

Este método surgió, cuando se hizo la pregunta sobre si era o no posible mejorar un algoritmo de aprendizaje, el cual tenía un rendimiento ligeramente mejor al de una proceso en el cual se llevaba acabo una adivinanza aleatoria para llegar a la solución. Se cuestionó si era posible convertir a este algorimto inicialmente debil en uno arbitrariamente fuerte y exacto.
En 1989 Schapire fue el primero en encontrar un algoritmo que cumplía con esto, un año más tarde Freund de la Universidad de San Diego, desarrolló un algoritmo de Boosting mucho más eficiente, aunque sufría de ciertos inconvenientes.
En 1995, Freund y Schapire presentaron un nuevo algoritmo de boosting llamado AdaBoost, el cual resolvía muchos de los problemas prácticos que se habían presentado anteriormente.

Algoritmo de AdaBoost

El algoritmo toma coma entrada una serie de ejemplos de entrenamiento (x1,y1),...,(xm,ym) donde xi corresponde a un cierto dominio ó espacio X, y cada etiqueta yi está dentro de un conjunto de etiquetas Y. AdaBoost llama reptidamente a un algoritmo de aprendizaje debil, lo llama en ciclos repetidos de t=1, . . .,T.
Dados: (x1,y1), . . ., (xm,ym)
donde xi pertence a X, yi pertence a Y={-1,+1}
Inicializa D1(i)=1/m
para t=1, . . .,T:

• Entrena al débil aprendiz usando la distribución Dt.
• Obtén la hipótesis débi ht:X->{-1,+1} con error
  Et=Pri[ht(xi)!=yi]
• Escoja at=1/2 ln(1-Et/Et)
• Actualice:

donde Zt es un factor de normalización.( Escojido para que Dt+1 sea una distribución)
La salida de la hipótesis final es:
Cuya sumatoria va de t=1 a T.

Idea principal del algoritmo

Una de las ideas principales del algoritmo es mantener una conjunto de pesos sobre el conjunto de entrenamiento. El peso que tiene el ejemplo de entrenamiento i en el momento t se denota por: Dt(i)

En primera instancia se ponen a todos los pesos con los mismos valores, pero en cada vuelta, los pesos de ejemplos que se hayan clasificado errónemente se incrementan, de este modo se forza al aprendiz débil a tenerse que concentrar en los ejemplos que se le dificultan que pertencen al conjunto de entrenamiento .

El trabajo del aprendiz débil radica en encontrar una hipótesis débil ht apropiada para el peso Dt.
La fuerza ó que tan correcta es una hipótesis débil se mide mediante su error:

Es importante notar que el error se mide con base al conjunto de pesos Dt, conjunto en el cual el aprendiz débil fue entrenado.
Una vez que se tiene una hipótesis débil ht, el siguiente paso es calcular el parámetro at, como se explicó arriba. at mide la importancia que se le asignará a la hipotesis ht.
Nótese que at >=0 cuando Et<= ½, asimismo at se hace más grande al hacerse el error más pequeño.
Una vez que se ha llevado esto acabo, se actualiza la distribución Dt, usando la regla que se mostró anteriormente. El effecto de esta actualización es incrementar los pesos que poseen los ejemplos que fueron clasificados erroneamente por la hipótesis ht, y decrementar los pesos de los ejemplos que fueron clasificados correctamente .
Con esto el aprendiz se concentrará en los ejemplos difíciles, en los ejemplos que se le dificultó clasificar.

La hipótesis final H, la hipótesis triunfadora, es una hipótesis que posee el mayor valor de at dentro del conjunto de hipótesis débiles T.

Así que eso fue una breve introducción al Boosting en Español!

A quien le interse leer más del tema, aquí puede encontrar muchos más artículos interesantes, es de hecho una recopilación que hizo la Universidad de Princeton sobre el tema, están en inglés, pero viene todo explicado bastante padre =)