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 x
i corresponde a un cierto dominio ó espacio X, y cada etiqueta y
i 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 D
1(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 Z
t es un factor de normalización.( Escojido para que D
t+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: D
t(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 h
t, el siguiente paso es calcular el parámetro a
t, como se explicó arriba. a
t mide la importancia que se le asignará a la hipotesis h
t.
Nótese que a
t >=0 cuando E
t<= ½, asimismo a
t 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 D
t, 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 h
t, 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 a
t 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 =)
