Boosting presentación 19 05 14
-
Upload
john-diaz -
Category
Engineering
-
view
99 -
download
2
description
Transcript of Boosting presentación 19 05 14
![Page 1: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/1.jpg)
BOOSTING
John J. Sprockel D. MISyC
Departamento de Ingeniería de Sistemas Facultad de Ingeniería
Pontificia Universidad Javeriana
![Page 2: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/2.jpg)
AGENDA
1. Aspectos históricos 2. Definición de Boosting
a. Proceso del Boosting b. Esquema del algoritmo c. Descripción del algoritmo AdaBoost
3. Minimización exponencial del error 4. Caso de multiples clases 5. Presentación de un artículo 6. Bibliografía
![Page 3: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/3.jpg)
ASPECTOS HISTÓRICOS
1984 Valiant L - Modelo de aprendizaje "PAC"
1988 Kearns M, Valiant L - si aprendices débiles juntos mejoran su rendimiento
1989 Schapire - Primer algoritmo de boosting de tiempo polinomial
1990 Freund desarrolla un algoritmo más eficiente que nunca tuvo una aplicación practica
1995 Freund y Schapire introducen AdaBoost
![Page 4: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/4.jpg)
DEFINICIÓN DE BOOSTING
Combina múltiples clasificadores Produce una forma de comité Con mejor desempeño que el de cada uno por separado
Es una técnica poderosa Aprendices débiles (weak learners)
![Page 5: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/5.jpg)
![Page 6: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/6.jpg)
DEFINICIÓN DE BOOSTING
Diferencia con bagging (comité): -Entrenamiento de clasificadores en secuencia . -Se usa para entrenamiento una forma ponderada del conjunto de datos en el cual el coeficiente de pesos asociado con cada punto de datos depende del desempeño del clasificador anterior.
![Page 7: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/7.jpg)
PROCESO DE BOOSTING
Clasificación con dos casos: los datos de entrada: x1, …,xN variables objetivo binarias t1, …, tN donde tn ∈ {-1, 1}. (original y)
Cada punto de datos tiene un parámetro p o n d e r a d o a s o c i a d o w n ( D t ( i ) ) , inicialmente se fija para todos en 1/N
![Page 8: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/8.jpg)
PROCESO DE BOOSTING
Clasificación con dos casos: Debemos suponer que tenemos un procedimiento disponible para entrenar un clasificador de base usando los datos ponderados para dar una función y(x)∈ {-1, 1}.(Original ht(xi))
![Page 9: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/9.jpg)
PROCESO DE BOOSTING
Los coeficientes ponderados (wn) son ajustados de acuerdo con el desempeño del clasificador entrenado previamente a fin de dar mayor peso a los puntos de datos mal clasificados.
![Page 10: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/10.jpg)
PROCESO DE BOOSTING
Cuando se han entrenado el número deseado de clasificadores base, se combinan para formar un comité mediante coeficientes que dan un peso diferente a diferentes clasificadores base.
![Page 11: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/11.jpg)
ESQUEMA DEL ALGORITMO DE BOOSTING
Bishop CM. Pattern Recognition and Machine Learning. 2006
![Page 12: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/12.jpg)
ALGORITMO AdaBoost
Bishop CM. Pattern Recognition and Machine Learning. 2006
Medición ponderada del error
![Page 13: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/13.jpg)
ALGORITMO AdaBoost
Bishop CM. Pattern Recognition and Machine Learning. 2006
Corrección de los coeficientes ponderados
![Page 14: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/14.jpg)
MINIMIZACIÓN EXPONENCIAL DEL ERROR
Se busca minimizar E, producto de: Donde fm(xn) es un clasificador definido en términos de una combinación lineal de clasificadores de base yl(x) de la forma:
![Page 15: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/15.jpg)
MINIMIZACIÓN EXPONENCIAL DEL ERROR
En vez de una minimización global, se supone que los clasificadores de base y sus coeficientes (α) son fijos. Así:
![Page 16: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/16.jpg)
MINIMIZACIÓN EXPONENCIAL DEL ERROR
Si denotamos con los puntos correctamente clasificados y a los errados, se obtiene:
![Page 17: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/17.jpg)
MINIMIZACIÓN EXPONENCIAL DEL ERROR
Después de haber obtenido αm y ym(x), se actualizan los pesos según: Dado qué
![Page 18: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/18.jpg)
Derivándose de ahí la ecuación 14.19
MINIMIZACIÓN EXPONENCIAL DEL ERROR
![Page 19: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/19.jpg)
Existe una posibilidad escasa de sobre-entrenamiento (overfitting).
Relaciones posibles del Boosting: - S V M ( m á r g e n e s d e l c o n j u n t o d e
entrenamiento) - Teoría de juegos.
- Programación lineal - Aprendizaje en línea
MINIMIZACIÓN EXPONENCIAL DEL ERROR
![Page 20: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/20.jpg)
Relación con SVM: Consideración de ambos de maximizar el m a r g e n m í n i m o e n e l c o n j u n t o d e entrenamiento:
El denominador en: Boosting SVM
MINIMIZACIÓN EXPONENCIAL DEL ERROR
![Page 21: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/21.jpg)
La forma más directa es el AdaBoost.M1, es adecuada cuando el clasificador débil es suficientemente robusto para dar una buena precisión.
Si esta es menor del 50% se requieren métodos más sofisticados como AdaBoost.MH que funciona creando un conjunto de problemas binarios. Otras formas son el LogitBoost y MultiBoost.
CASO DE MÚLTIPLES CLASES
![Page 22: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/22.jpg)
1. Rapidez 2. Simple 3. Fácil de programar
4. No tiene parámetros para afinar (tune, T) 5. No requiere un conocimiento previo del
clasificador débil
6. Viene con ciertas garantías teóricas
VENTAJAS
![Page 23: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/23.jpg)
1. El desempeño en un problema particular depende de los datos y del clasificador débil.
a. Es sensible a datos incompletos
b. Falla con hipótesis débiles complejas o cuando son muy débiles.
2. Es particularmente susceptible al ruido.
DESVENTAJAS
![Page 24: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/24.jpg)
![Page 25: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/25.jpg)
![Page 26: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/26.jpg)
![Page 27: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/27.jpg)
![Page 28: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/28.jpg)
![Page 29: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/29.jpg)
![Page 30: Boosting presentación 19 05 14](https://reader033.fdocumento.com/reader033/viewer/2022061305/549fdd1aac7959aa2d8b4632/html5/thumbnails/30.jpg)
BIBLIOGRAFIA
1. Bishop CM. Chapter 14. Combining Models. In Bishop CM. Pattern Recognition and Machine Learning. Singapur, Springer 2006. pp 653- 676.
2. Freund Y, Schapire R. A Short Introduction to Boosting. Journal of Japanese Society for Artificial Intelligence, 14(5):771-780, September, 1999.
3. Meir R, Ratch G. An Introduction to Boosting and Leveraging. In S. Mendelson, A.J. Smola (Eds.): Advanced Lectures on Machine Learning, LNAI 2600, pp. 118–183, 2003.
4. J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: a statistical view of boosting. The Annals of Statistics, 28(2):337-407, 2000.
5. Mandal I, Sairam N. Accurate Prediction of Coronary Artery Disease Using Reliable Diagnosis System. Journal of Medical Systems. 2012;36(5):3353–73.