ESCUELA SUPERIOR POLITÉCNICA DEL LITORAL

Ensamble de clasificadores utilizando ADABOOST

Andrés G. Abad, Ph.D.

Andrés G. Abad, Ph.D., agabad@[Link] 1 / 48

Agenda
Introducción
Problema de aprendizaje supervisado
Métodos de clasificación
Combinando hipótesis
Motivación
Diversidad
Métodos de ensembles
Algoritmo AdaBoost
Introducción al AdaBoost
Descripción general
Conclusiones
Referencias Bibliográficas

Andrés G. Abad, Ph.D., agabad@[Link] 2 / 48

Combinación de Estimaciones

En la conferencia Predictive Analytics World/Toronto

(PAW) 2012

Método Valor Diferencia

Real 362 -
Ganador (persona) 352 10
Promedio (N = 61) 365 3

[Link]

Andrés G. Abad, Ph.D., agabad@[Link] 3 / 48

Agenda
Introducción
Problema de aprendizaje supervisado
Métodos de clasificación
Combinando hipótesis
Motivación
Diversidad
Métodos de ensembles
Algoritmo AdaBoost
Introducción al AdaBoost
Descripción general
Conclusiones
Referencias Bibliográficas

Andrés G. Abad, Ph.D., agabad@[Link] 4 / 48

Agenda
Introducción
Problema de aprendizaje supervisado
Métodos de clasificación
Combinando hipótesis
Motivación
Diversidad
Métodos de ensembles
Algoritmo AdaBoost
Introducción al AdaBoost
Descripción general
Conclusiones
Referencias Bibliográficas

Andrés G. Abad, Ph.D., agabad@[Link] 5 / 48

Problema de aprendizaje supervisado I
Considere (x1 , y1 ), . . . , (xm , ym ) donde xi ∈ X ⊆ Rn , yi ∈ Y ⊆ R.
Asumimos que existe una función no conocida

f :X→Y

Buscamos una hipótesis

h:X→Y

que tenga un bajo error de generalización

 = P[h(x) , f (x)].

Andrés G. Abad, Ph.D., agabad@[Link] 6 / 48

Problema de aprendizaje supervisado II
Según la naturaleza del conjunto Y tenemos los siguientes tipos de problemas

Y Tipo de problema
R Regresión
{c1 , . . . , cn } Clasificación
{−1, +1} Clasificación binaria

Para problemas de regresión generalmente usamos

1 X
 = MSE(h) = f (x) − h(x) 2


|X|
x∈X

Para problemas de clasificación generalmente usamos

1 X
= [I(h(x) , f (x))]
|X|
x∈X

Andrés G. Abad, Ph.D., agabad@[Link] 7 / 48

Métodos de clasificación I

Algunos de los principales algoritmos para clasificación binaria

I Clasificador bayesiano ingenuo

I Arboles de clasificación (e.g., CART, C4.5)
I Análisis de discriminantes (e.g., lineal,
cuadrático)
I Máquinas de Soporte Vectorial
I Redes Neuronales Artificiales
I Regresión logı́stica
Clasificación Binaria

Andrés G. Abad, Ph.D., agabad@[Link] 8 / 48

Definición del problema de clasificación I
I Un objeto x = [x1 , . . . , xp ], con caracterı́sticas xi , pertenece exactamente a
una clases c ∈ {1, 2, . . . , C}.
I Asumimos que tenemos un conjunto de datos
D = {(x(1) , c(1) ), . . . , (x(n) , c(n) )}
I Buscamos una función f̂ que asigne x(i) a c(i) lo mejor posible:
f̂ = arg mı́n P(x,c) [1(f (x) , c)]
f

I Objeto x pertenece a una de dos clases:

{Basico, Premium}
I Objeto x medidos en dos caracterı́sticas: x1
ingresos anuales, y x2 edad en años
I Dos clasificadores f̂ ’s: convexo-cuadrático (linea
negra) y no-convexo (linea roja)

Andrés G. Abad, Ph.D., agabad@[Link] 9 / 48

Clasificador bayesiano ingenuo I
Considera el criterio de maximo a posteriori (MAP)

c = arg máx P(x1 , . . . , xn |cj )P(cj ).

cj ∈C

Bajo el supuesto de independencia entre variables

n
Y
c = arg máx P(cj ) P(xi |cj ).
cj ∈C
i=1

I No considera interacciones entre variables

I No sufre de la maldición de la dimensionalidad
I Si la clase correcta tiene probabilidad alta es robusto al supuesto de
independencia

Andrés G. Abad, Ph.D., agabad@[Link] 10 / 48

Árboles de clasificación I
Basado en reglas del tipo: Si A1 ∧ · · · ∧ Am entonces cj
I Generalmente condición Al de la forma xi ≥ θ

I Algoritmos
P ID3 [Quinlan, 1986] y C4.5 [Quinlan, 1993] utilizan
H(S) = − x∈X p(x) log p(x)
Algortimo CART utiliza Impureza Gini: IG (x) = m
P
i=1 xi (1 − xi )
I

Andrés G. Abad, Ph.D., agabad@[Link] 11 / 48

Análisis de discriminante lineal I
Modelamos la densidad de cada clase con una gaussiana multivariada

1 1
 
fk (x) = exp − (x − µk ) Σ
T −1
k (x − µk .
)
(2π)p/2 |Σk |1/2 2
Asumiremos que las clases tienen matriz de covarianzas común Σk = Σ

1
δk (x) = xT Σ−1 µk − µk T Σ−1 µk + log πk
2

Andrés G. Abad, Ph.D., agabad@[Link] 12 / 48

Agenda
Introducción
Problema de aprendizaje supervisado
Métodos de clasificación
Combinando hipótesis
Motivación
Diversidad
Métodos de ensembles
Algoritmo AdaBoost
Introducción al AdaBoost
Descripción general
Conclusiones
Referencias Bibliográficas

Andrés G. Abad, Ph.D., agabad@[Link] 13 / 48

Promediando regresiones
Considere
T
1X
H(x) = hi (x).
T
t=1
Se tiene que
MSE(H) ≤ MSE(h)

Z  X T
 2 T Z
 1  1X

T i (x) p(x)dx ≤

 i (x)2 p(x)dx,
T
t=1 t=1

donde hi (x) = f (x) + i (x) para i = 1, . . . , T.

Si Z Z
i (x)p(x)dx = 0 y i (x)j (x)p(x)dx = 0 (i , j)

tenemos
1
MSE(H) = MSE(h)
T
Andrés G. Abad, Ph.D., agabad@[Link] 14 / 48
Sistema de Votación Mayorı́a Absoluta I

Para el problema de clasificación definimos el ensemble

j
si Ti=1 hi (x) >
( P 1 Pl PT k
cj i=1 hi (x)
H(x) = 2 k=1
Rechazo si no.

Si asumimos que los clasificadores son independientes y su precisión individual

es p tenemos la precisión del ensemble dada por

T !
X T k
Pmv = p (1 − p)T−k .
k
k=bT/2+1c

Andrés G. Abad, Ph.D., agabad@[Link] 15 / 48

Sistema de Votación Mayorı́a Absoluta II

I Si p > 0,5 entonces lı́mT→∞ Pmv = 1

I Si p < 0,5 entonces lı́mT→∞ Pmv = 0
I Si p = 0,5 entonces Pmv = 0,5 para cualquier T

Andrés G. Abad, Ph.D., agabad@[Link] 16 / 48

Diversidad I

A través de las siguientes dos descomposiciones del error cuadrático medio de un

ensemble MSE(H)
I Descomposición Error-Ambiguedad [Krogh and Vedelsby, 1995]
I Descomposición Sesgo-Varianza-Covarianza [Ueda and Nakano, 1996]
Ambas dependen de un término relacionado con la diversidad de los
clasificadores.

Andrés G. Abad, Ph.D., agabad@[Link] 17 / 48

Descomposición Error-Ambiguedad I
Se puede demostrar que

MSE(H) = MSE(h) − AMBI(h)

donde
T
Z X
MSE(h) = wi MSE(hi |x)p(x)dx
i=1
Z XT
AMBI(h) = wi AMBI(hi |x)p(x)dx
i=1
Z XT
= wi (hi (x) − H(x))2 p(x)dx
i=1

Andrés G. Abad, Ph.D., agabad@[Link] 18 / 48

Descomposición Sesgo-Varianza-Covarianza I

MSE(h) = sesgo(h)2 + var(h)

E{[h − E(f )]2 } = [E(h) − E(f )]2 + E{[h − E(h)]2 }
Andrés G. Abad, Ph.D., agabad@[Link] 19 / 48
Descomposición Sesgo-Varianza-Covarianza II
Ası́ mismo, se puede demostrar que

1 1
 
MSE(H) = SESGO(H) + VAR(H) + 1 −
2
COV(H)
T T
donde
T
1X
SESGO(H) = (E[hi ] − f )
T
i=1
T
1 X
VAR(H) = E(hi − E[hi ])2
T
i=1
T X
T
1 X
COV(H) = E(hi − E[hi ])E(hj − E[hj ]).
T(T − 1)
i=1 j=1;j,i

Andrés G. Abad, Ph.D., agabad@[Link] 20 / 48

Métodos para Introducir Diversidad I

I Utilizar un conjunto de datos de entrenamiento de alguna manera diferente

I Seleccionar un subconjunto diferente de variables para entrenar a la hipótesis
I Manipular las etiquetas de las clases
I Introducir aleatoriedad en el algoritmo

Andrés G. Abad, Ph.D., agabad@[Link] 21 / 48

Beneficios de combinar hipótesis I

Fuente: [Dietterich, 2000a]

I Problema estadı́stico
I Problema computacional
I Problema representacional

Andrés G. Abad, Ph.D., agabad@[Link] 22 / 48

Principales métodos de ensembles I

Principales métodos de ensembles:

I Clasificador Bayesiano Óptimo
I Bagging (bootstrap aggregating)
I Random forest
I Boosting
I AdaBoost (adaptive boosting)

Andrés G. Abad, Ph.D., agabad@[Link] 23 / 48

Clasificador Bayesiano Óptimo I

Consideramos H como el espacio de todas las hipótesis y D una muestra

X
c = arg máx P(cj |hi )P(hi |D)
cj ∈C
hi ∈H

Es el mejor clasificador en promedio considerando H y conocimiento a priori

Dificultades prácticas
I H generalmente muy grande como para iterar
I Hipótesis h generalmente entregan clase y no probabilidades P(c|h)
I Calcular probabilidades posterior P(h|D) es generalmente no trivial
I Necesitamos P(D|h) y P(h)

Andrés G. Abad, Ph.D., agabad@[Link] 24 / 48

Bagging I
El Bagging (Bootstrap AGGregatING) fue introducido en Breiman [1996]

Considere que tenemos

L = {(x1 , y1 ), . . . , (xm , ym )}

1. Utilizando muestreo aleatorio con

reposición y obtenemos

Lb = {(xb1 , yb1 ), . . . , (xbm , ybm )},

para b = 1, . . . , B.
2. Aprendemos hb utilizando Lb
3. Agregamos hipótesis

Andrés G. Abad, Ph.D., agabad@[Link] 25 / 48

Boosting I

I En Kearns and Valiant [1989] se plantea la pregunta de si las clases de complejidad:

aprendedores débiles y aprendedores fuertes, son iguales
I Schapire [1990] responde a esa pregunta, su prueba es constructiva: Boosting

Andrés G. Abad, Ph.D., agabad@[Link] 26 / 48

Boosting II
Suponga que h1 , . . . , hT son clasificadores débiles utilizados para aproximar una
función f : Rk → {−1, +1}, tal que

ε = P[h(x) , f (x)] = 0,5 − γ para x ∈ X; γ > 0

Clasificadores Débiles ([Viola and Jones, 2001])

Andrés G. Abad, Ph.D., agabad@[Link] 27 / 48

Boosting III

Andrés G. Abad, Ph.D., agabad@[Link] 28 / 48

Agenda
Introducción
Problema de aprendizaje supervisado
Métodos de clasificación
Combinando hipótesis
Motivación
Diversidad
Métodos de ensembles
Algoritmo AdaBoost
Introducción al AdaBoost
Descripción general
Conclusiones
Referencias Bibliográficas

Andrés G. Abad, Ph.D., agabad@[Link] 29 / 48

Introducción al AdaBoost I

I Basados en Schapire [1990], se introduce en Freund and Schapire [1996] el algoritmo

AdaBoost (ADAptive BOOSTing)
I En Freund and Schapire [1997] se realiza la primera extensión del AdaBoost al
problema de regresión

Andrés G. Abad, Ph.D., agabad@[Link] 30 / 48

Reducción del error en AdaBoost I

Sea t = 12 − γt el error de entrenamiento de

ht , entonces se puede demostrar que

Yh p i
H = 2 (t (1 − t )
t
 
 X 2 
≤ exp −2 γt 
t

Andrés G. Abad, Ph.D., agabad@[Link] 31 / 48

Reducción del error en AdaBoost II
Empiricamente se ha evidenciado la superioridad del AdaBoost [Freund and Schapire,
1996; Bauer and Kohavi, 1999; Dietterich, 2000b]

Comparación de error de prueba entre algoritmos C4.5 Vs. Boosting Decision Stumps, y
Boosting C4.5 respectivamente [Freund and Schapire, 1999].

Andrés G. Abad, Ph.D., agabad@[Link] 32 / 48

Descripción general I

El AdaBoost es una forma de optimización gradiente en el espacio de hipótesis

con el objetivo de minimizar la función de pérdida exponencial

`exp (f , H|D) = Ex∼D [e−f (x)H(x) ]

para

T
X
H(x) = αt ht (x)
t=1

Andrés G. Abad, Ph.D., agabad@[Link] 33 / 48

Descripción general II

Al minimizar la función de pérdida exponencial `exp (f , H|D) tenemos

∂e−f (x)H(x)
= −f (x)e−f (x)H(x)
∂H(x)
= e−H(x) P(f (x) = +1|x) + eH(x) P(f (x) = −1|x) = 0

Resolviendo

1 P(f (x) = +1|x)

H(x) = ln
2 P(f (x) = −1|x)

Andrés G. Abad, Ph.D., agabad@[Link] 34 / 48

Descripción general III

Dado que

1 P(f (x) = +1|x)

!
sign (H(x)) = sign ln
2 P(f (x) = −1|x)
si P(f (x) = +1|x) > P(f (x) = −1|x);
(
1
=
−1 si P(f (x) = +1|x) < P(f (x) = −1|x)
= arg máx P(f (x) = y|x)
y∈{−1,+1}

lo que implica que sign (H(x)) alcanza la tasa de error bayesiano.

Andrés G. Abad, Ph.D., agabad@[Link] 35 / 48

Descripción general IV

Para t = 1, . . . , T:
1. Entrenar la hipótesis débil ht : X → {−1, +1} utilizando la distribución Dt
Obtener H(x) = Ti=1 αi hi (x).
P

Para completamente definir el AdaBoost necesitamos definir

I Como determinar las distribuciones Dt
I Cómo determinar los pesos αt

Andrés G. Abad, Ph.D., agabad@[Link] 36 / 48

Descripción general V

El clasificador ht que corrige los errores de Ht−1 debe minimizar la función de

pérdida exponencial

h i
`exp (Ht−1 + ht |D) = Ex∼D e−f (x)(Ht−1 (x)+ht (x))
f (x)2 ht (x)2
" !#
≈ Ex∼D e−f (x)Ht−1 (x)
1 − f (x)ht (x) +
2
1
  
= Ex∼D e−f (x)Ht−1 (x) 1 − f (x)ht (x) +
2

Andrés G. Abad, Ph.D., agabad@[Link] 37 / 48

Descripción general VI
El clasificador ideal ht sera tal que
ht (x) = arg mı́n `exp (Ht−1 + h|D)
h
f (x)2 h(x)2
" !#
≈ arg mı́n Ex∼D e −f (x)Ht−1 (x)
1 − f (x)h(x) +
h 2
h i
= arg máx Ex∼D e −f (x)Ht−1 (x)
f (x)h(x)
h
e−f (x)Ht−1 (x)
" #
= arg máx Ex∼D f (x)h(x)
h Ex∼D [e−f (x)Ht−1 (x) ]
= arg máx Ex∼Dt [f (x)h(x)]
h
= arg mı́n Ex∼Dt [I(f (x) , h(x))]
h

D(x)e−f (x)Ht−1 (x)

para Dt (x) = Ex∼D [e−f (x)Ht−1 (x) ]
.

Andrés G. Abad, Ph.D., agabad@[Link] 38 / 48

Descripción general VII

Bajo una distribución Dt , el peso αt se escoge minimizando la función de pérdida

exponencial

h i
`exp (f , αt ht |Dt ) =Ex∼Dt e−f (x)αt ht (x)
=Ex∼Dt e−αt I(f (x) = ht (x)) + eαt I(f (x) , ht (x))
 

=e−αt Px∼Dt (f (x) = ht (x)) + eαt Px∼Dt (f (x) , ht (x))

=e−αt (1 − t ) + eαt t

donde t = Px∼Dt (f (x) , ht (x)).

Andrés G. Abad, Ph.D., agabad@[Link] 39 / 48

Descripción general VIII

Para obtener el αt óptimo hacemos

∂`exp (f , αt ht |Dt )
= − e−αt (1 − t ) + eαt t = 0
∂αt

cuya solución es

1 1 − t
 
αt = ln
2 t

Andrés G. Abad, Ph.D., agabad@[Link] 40 / 48

Algoritmo AdaBoost I
Inicialice: D1 (i) = 1/m para i = 1, . . . , m.
Para t = 1, . . . , T:
1. Entrenar la hipótesis débil ht : X → {−1, +1} utilizando la distribución Dt
2. Evalue error ponderado:

t = Pri∼Dt [ht (xi ) , yi ]

 
1−t
3. Seleccione αt = 1
2 ln t
4. Actualice para i = 1, . . . , m:

Dt (i) exp(−αt yi ht (xi ))

Dt+1 (i) = ,
Zt
donde Zt es el factor de normalización

Andrés G. Abad, Ph.D., agabad@[Link] 41 / 48

Algoritmo AdaBoost II

α1 = 0,42, α2 = 0,65, α3 = 0,92

Andrés G. Abad, Ph.D., agabad@[Link] 42 / 48

Agenda
Introducción
Problema de aprendizaje supervisado
Métodos de clasificación
Combinando hipótesis
Motivación
Diversidad
Métodos de ensembles
Algoritmo AdaBoost
Introducción al AdaBoost
Descripción general
Conclusiones
Referencias Bibliográficas

Andrés G. Abad, Ph.D., agabad@[Link] 43 / 48

Conclusiones I

I Los métodos de ensembles reducen el error de entrenamiento y el de prueba

I El concepto de diversidad entre hipótesis es central
I Existen diferentes maneras de introducir diversidad a las hipótesis
I El AdaBoost es un algoritmo especı́fico para el Boosting que introduce
diversidad ajustando la distribución de la muestra
I El Boosting reduce asintóticamente el error de entrenamiento exponencialmente

Andrés G. Abad, Ph.D., agabad@[Link] 44 / 48

Referencias Bibliográficas I

Bauer, E. and Kohavi, R. (1999). An Empirical Comparison of Voting Classification Algorithms:

Bagging, Boosting, and Variants. Machine Learning, 36(1-2):105–139.
Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2):123–140.
Dietterich, T. G. (2000a). Ensemble Methods in Machine Learning. In Multiple Classifier Systems,
number 1857 in Lecture Notes in Computer Science, pages 1–15. Springer Berlin Heidelberg.
Dietterich, T. G. (2000b). An Experimental Comparison of Three Methods for Constructing
Ensembles of Decision Trees: Bagging, Boosting, and Randomization. Machine Learning,
40(2):139–157.
Freund, Y. and Schapire, R. (1996). Experiments with a New Boosting Algorithm. pages 148–156.
Freund, Y. and Schapire, R. (1999). A short introduction to boosting. Japonese Society for Artificial
Intelligence, 14(5):771–780.
Freund, Y. and Schapire, R. E. (1997). A Decision-Theoretic Generalization of on-Line Learning and
an Application to Boosting.
Kearns, M. and Valiant, L. (1989). Cryptographic Limitations on Learning Boolean Formulae and
Finite Automata.

Andrés G. Abad, Ph.D., agabad@[Link] 45 / 48

Referencias Bibliográficas II

Krogh, A. and Vedelsby, J. (1995). Neural Network Ensembles, Cross Validation, and Active
Learning. In Advances in Neural Information Processing Systems, pages 231–238. MIT Press.
Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning, 1(1):81–106.
Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc.,
San Francisco, CA, USA.
Schapire, R. E. (1990). The strength of weak learnability. Machine Learning, 5(2):197–227.
Ueda, N. and Nakano, R. (1996). Generalization error of ensemble estimators. In , IEEE
International Conference on Neural Networks, 1996, volume 1, pages 90–95 vol.1.
Viola, P. and Jones, M. (2001). Rapid object detection using a boosted cascade of simple features.
In Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern
Recognition, 2001. CVPR 2001, volume 1, pages I–511–I–518 vol.1.

Andrés G. Abad, Ph.D., agabad@[Link] 46 / 48

Apéndice I

Una expansión aditiva de funciones bases toma la forma

M
X
f (x) = βm b(x; γm )
m=1

El ajuste se realiza minimizando función de pérdida

N
 M

X  X 
mı́n L yi , βm b(xi ; γm )
{βm ,γm }M
1 i=1 m=1

N
X
L yi , βb(xi ; γ)


mı́n
β,γ
i=1

Andrés G. Abad, Ph.D., agabad@[Link] 47 / 48

Apéndice II

Algoritmo: Ajuste por Etapas hacia Adelante

1. Inicialice f0 (x) = 0
2. Para m = 1, . . . , M:
a Calcule

N
X
(βm , γm ) = arg mı́n L(yi , fm−1 (xi ) + βb(xi ; γ))
β,γ
i=1

b Establezca fm (x) = fm−1 (x) + βm b(x; γm )

Andrés G. Abad, Ph.D., agabad@[Link] 48 / 48