• Author / Uploaded
• Alvaro Vergara Sepulveda

Citation preview

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

El algoritmo EM y aplicaciones Jos´e Alberto Hern´andez email: [email protected]

Julio, 2006

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Contenido

I

Introducci´on: M´axima verosimilitud

I

Mixturas de distribuciones de probabilidad

I

Algoritmo EM

I

Caracterizaci´on de tr´afico y retardo en Internet

I

Mixturas de distribuciones Weibull

I

Conclusiones

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

La fuente

I

Dempster et. al.: Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 39(1):1–38. 1977.

I

Seg´ un Google scholar: 7310 citas.

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

M´axima verosimilitud I

Definici´on del problema de estimaci´on de los par´ametros de una distribuci´on.

I

Sea X = {x1 , x2 , . . . , xN } una muestra que pensamos que se distribuye seg´ un una distribuci´on de probabilidad p(x|Θ) con par´ametros Θ.

Estimaci´on Encontrar los par´ametros Θ∗ o´ptimos, es decir, que m´as se ajustan a la muestra. I

I I

La funci´on de Q verosimilitud de los par´ametros dada la muestra es: L(Θ|X ) = N i=1 p(xi |Θ). Entonces: Θ∗ = arg m´axΘ L(Θ|X ).

Se consigue derivando e igualando a cero: J. A. Hern´ andez

∂ ∂Θ

log L(Θ|X ) = 0.

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Ejemplo: Distribuci´on exponencial

I I I

Dist. exponencial: p(x|λ) = λe −λx ,

Θ=λ

Data la muestra x = {x1 , . . . , xN } Q −λxi L(λ|x) = N i=1 λe log L(λ|x) =

N X i=1

N   X log λe −λxi = N log λ − λ xi i=1

N

1 X ∂ xi = 0 log L(λ|X ) = N − ∂λ λ

⇒

ˆ MV = λ

i=1

J. A. Hern´ andez

El algoritmo EM y aplicaciones

N 1 X xi N i=1

!−1

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Mixturas de distribuciones (1)

I

I

Qu´e ocurre si la muestra x proviene de una combinaci´on de multiples distribuciones, en lugar de una sola? Mixtura Combinaci´on ponderada de distribuciones de probabilidad. p(x|Θ) =

M X

qj pj (x|θj ),

Θ = {qj , θj }

j=1

J. A. Hern´ andez

X j

El algoritmo EM y aplicaciones

qj = 1

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Mixturas de distribuciones (2)

Example: data sample histogram 0.4

PDF

0.3

0.2

0.1

0 −5

0

5 x

J. A. Hern´ andez

El algoritmo EM y aplicaciones

10

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Mixturas de distribuciones (2)

Example: Single gaussian match 0.4

PDF

0.3

0.2

0.1

0 −5

0

5 x

J. A. Hern´ andez

El algoritmo EM y aplicaciones

10

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Mixturas de distribuciones (2)

Example: mixture of M=2 gaussians 0.4 q1=0.7, µ1=0, σ1=1 q1=0.3, µ1=2, σ2=3

PDF

0.3

Mixture Histogram

0.2

0.1

0 −5

0

5 x

J. A. Hern´ andez

El algoritmo EM y aplicaciones

10

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Mixturas de distribuciones (3)

I

Aplicando m´axima verosimilitud:     M M N N X X Y X  qj pj (xi |θj ) = qj pj (xi |θj ) log  log L(Θ|x) = log i=1

j=1

i=1

∂ log L(Θ|x) = 0 ∂Θ No se puede resolver anal´ıticamente!!

J. A. Hern´ andez

El algoritmo EM y aplicaciones

j=1

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Soluci´on: Algoritmo EM Definici´on El algoritmo EM (Expectation Maximisation) es un m´etodo general para encontrar el estimador de m´axima verosimilitud de los par´ametros de una distribuci´on de probabilidad, especialmente u ´til cuando parte de la informaci´on est´a oculta. I

Supondremos un conjunto de datos Z = (X , Y ), donde los datos X son visibles, pero los datos Y est´an ocultos. p(z|Θ) = p(x, y |Θ) = p(x|y , Θ)p(y |Θ)

I

C´omo calculamos L(Θ|Z ) = L(Θ|X , Y ) si no conocemos Y ? J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Soluci´on: Algoritmo EM (2)

I

No conocemos la Y de L(Θ|X , Y ), as´ı que la supondremos como variable aleatoria y calculamos una media:

g

Q(Θ, Θ ) = I

Z

log L(Θ|X , y )p(y |X , Θg )dy = E [log p(x, y |Θ)|X , Θg ] y

Θg son unos par´ametros propuestos.

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

EM en dos pasos: I

Para encontrar los par´ametros o´ptimos Θ∗ a partir de L(Θ|X , Y ), hay que proceder en dos pasos: I

Paso E (Expectation): Calcular la esperanza de la verosimilitud con respecto a la informaci´on conocida y unos par´ametros propuestos Θ(t) cualesquiera: Q(Θ, Θ(t) ) = E [log p(x, y |Θ)|X , Θ(t) ]

I

Paso M (Maximization): Maximizar Q con respecto a los par´ametros: Θ(t+1) = arg m´ax Q(Θ, Θ(t) ) Θ

I

Repetir E y M de forma iterativa hasta alcanzar convergencia. J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Mixturas: Aplicaci´on de EM I I

I

P Recordamos: p(x|Θ) = M j=1 qj p(x|θj ) Introducimos etiquetas ocultas: yi asociados a los valores conocidos de la muestra xi tales que: p(yi = j|xi , Θ) representa la probabilidad de que xi pertenezca a la componente j de la mixtura. Evidentemente: I I

I

p(xi |yi = j, Θ) = p(xi |θj ) p(yi = j|Θ) = qj

Con esta nueva formulaci´on: M M X X p(x|Θ) = p(x, y = j|Θ) = p(x|y = j, Θ)p(y = j|Θ) j=1

=

M X

j=1

qj p(x|θj )

j=1

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Desarrollando EM: I

p(x, y |Θ) = qy p(x|θy ) I I

I

I

E-step: Q(Θ, Θ(t) ) = E [log L(Θ|x, y )|x, Θ(t) ] M-step: Θ(t+1) = arg m´axΘ Q(Θ, Θ(t) )

Expandiendo el paso E:
PM PN (t) Q(Θ, Θ(t) ) = i=1 log p(xi |θj ) p(yi = j|xi , Θ ) + j=1
PM PN (t) + j=1 i=1 log qj p(yi = j|xi , Θ ) Maximizando (paso M):

∂Q(Θ, Θ(t) ) =0 ∂qj J. A. Hern´ andez

∂Q(Θ, Θ(t) ) =0 ∂θj El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Caracterizaci´on de tr´afico y retardos (1)

I

< 1990s: Se utilizaban modelos Poissonianos para modelar el tr´afico en Internet, muy al estilo de los modelos de telefon´ıa.

I

Principios 1990s: Experimentos con medidas de tr´afico reales muestran que los modelos Poissonianos no son adecuados, debido al car´acter “rafagoso” del tr´afico.

I

Mediados 1990s: Se empiezan a utilizar modelos de “caja negra”, tales como: fBm, fARIMA, etc.

I

Mediados-finales 1990s: Aparecen los modelos estructurales.

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Caracterizaci´on de tr´afico y retardos (2) I

I

Leland et. al.1 son los primeros en introducir los conceptos de auto-semejanza y dependencia a largo plazo en el tr´afico. Sus resultados emp´ıricos con medidas de tr´afico Ethernet tambi´en son observados en otros escenarios: tr´afico WAN 2 , tr´afico de v´ıdeo VBR3 y el web4 .

1

Leland, W. E. et al: “On the self-similar nature of Ethernet traffic (extended version)”, in IEEE/ACM Trans. Networking, 1994 2 Paxson, V. et al: ”Wide Area traffic: the failure of Poisson modeling”, in IEEE/ACM Trans. Networking, 1995 3 Beran, J. et al: ”Long-range dependence in variable-bit-rate video traffic”, in IEEE Trans. Communications, 1995 4 Crovella, M. E. et al: ”Self-similarity in world wide web traffic: evidence and possible causes”, in IEEE/ACM Trans. Networking, 1997 J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Caracterizaci´on de tr´afico y retardos (3) I

I

I

I

Es necesario utilizar modelos que presenten las caracter´ısticas observadas en los experimentos. Por ejemplo: fBM5 , fARIMA6 , etc. Cuando se introduce tr´afico fBm o fARIMA en un router, la distribuci´on de la cola es de cola pesada, y puede ser aproximada por una distribuci´on de probabilidad Weibull7 . Tal resultado se ha comprobado emp´ıricamente en un router de backbone8 ... ... y tambi´en en un escenario extremo-extremo.

5

Norros, I.: ”On the use of fractional Brownian motion in the theory of connectionless networks”, in IEEE JSAC, 1995 6 L´ opez-Ardao, J. C. et al: ”On the use of self-similar processes in network simulation”, in ACM TOMACS, 2000 7 Norros, I.: ”A storage model with self-similar input”, in Queueing Systems, 1994 8

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

La distribuci´on Weibull

The Weibull distribution 0.01 r=4 fixed

p(x|r,s)

0.008 0.006

I

0.004 0.002 0

0

1

2

3

4

5 x

6

7

8

9

10

0.02


x s r )

I

r est´a relacionado con el m´aximo.

I

s est´a relacionado con la ca´ıda de la cola.

s=4 fixed 0.015 p(x|r,s)

p(x|r , s) = sx s−1 r s exp(−

0.01

0.005

0

0

1

2

3

4

5 x

6

7

8

9

J. A. Hern´ andez

10

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

EM para mixturas de Weibulls

I

I

Expandiendo el paso E:
PM PN (t) Q(Θ, Θ(t) ) = j=1 i=1 log p(xi |θj ) p(yi = j|xi , Θ ) +
PM PN (t) + j=1 i=1 log qj p(yi = j|xi , Θ ) Maximizando (paso M): ∂Q(Θ, Θ(t) ) = 0, ∂qj

∂Q(Θ,Θ(t) ) ∂rj

J. A. Hern´ andez

= 0,

∂Q(Θ, Θ(t) ) =0 ∂sj

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Aplicaci´on a mixturas de distribuciones Weibull

1. Obteniendo par´ametros: P p(yi = j|xi , Θ) qj = N1 N 1/sj  PN i=1sj x p(y i =j|xi ,Θ) rj = Pi=1N i p(yi =j|xi ,Θ) i=1 P N i=1 p(yi =j|xi ,Θ)

sj =

PN

i=1

sj i sj r j

x




−1 log

xi rj

2. Actualizando las etiquetas oculta p(yi = j|xi , Θ) =

qj p(xi |θj ) PM k=1 qk p(xi |θk )




p(yi =j|xi ,Θ)

Cuadro: Resumen de EM para mixturas de distribuciones Weibull.

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Resultados

Animaci´on MATLAB

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Conclusiones (1)

I

Una mixtura de distribuciones Weibull caracterizan bastante bien el retardo extremo-extremo en los paquetes.

I

Los par´ametros de la mixtura se pueden obtener f´acilmente mediante el algoritmo EM.

I

Adem´as, los par´ametros de la mixtura son representativos de caracter´ısticas importantes de la red: retardo medio (par´ametro r ), comportamiento de la cola (par´ametro s).

I

Mediante el estudio de la evoluci´on de los par´ametros en el tiempo se pueden detectar anomal´ıas en la red: cambios de routing, sobrecarga, etc.

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Conclusiones (2)

I

EM se utiliza en muchos otros problemas: I I I

I

HMM (Hidden Markov Models) Clustering, Pattern Recognition etc.

Problema: “Curse of dimensionality”.

J. A. Hern´ andez

El algoritmo EM y aplicaciones

Introducci´ on Algoritmo EM Soluci´ on EM para mixturas Caracterizaci´ on de retardos Conclusiones

Preguntas

Gracias por su atenci´on

J. A. Hern´ andez

El algoritmo EM y aplicaciones