PDF de programación - El Algoritmo Expectation-Maximization

El Algoritmo E-M

José Antonio Camarena Ibarrola

Introducción

• Método para encontrar una estimación de

máxima verosimilitud para un parámetro ѳ de
una distribución


Ejemplo simple

• Si tiene las temperaturas del jardín de c/u de las

24 horas del día

• Sabemos que la distribución de probabilidad x depende

de la estación ѳ (Primavera, Verano, Otoño, Invierno)

• Suponga que lo único con lo que en realidad contamos

es con la temperatura promedio del día

• Se quiere hacer una estimación acerca de ѳ
• Un estimador de máxima verosimilitud maximiza

para encontrar ѳ pero puede ser un problema
intratable

• El algoritmo EM hace suposiciones acerca de los datos

completos e iterativamente encuentra el ѳ que
maximiza

24xxy)|(ypx)|(xp Que se necesita para usar EM

• Los datos observados
• Una densidad paramétrica que describa los

datos observados

• Una descripción de los datos completos
• Una densidad paramétrica de los datos
completos considerando que el
soporte de X no depende de ѳ

y)|(ypx)|(xp X no se observa directamente

• Lo que se observa son realizaciones y de la

variable aleatoria Y=T(X)

• Ej. T puede mapear X a su media
• Ej. Si X es un número complejo Y es solo su

magnitud

• Ej. T devuelve la norma de un vector X

Estimador de máxima verosimilitud

• Dado que solo contamos con y, la estimación de ѳ

deseable es

• Frecuentemente es mas fácil maximizar la log-

verosimilitud

• En muchas ocasiones, es muy complicado maximizar
cualquiera de las dos, entonces EM surge como una
mejor opción

• EM hacemos una suposición acerca de X (los datos

completos), luego encontramos el ѳ que maximiza el
valor esperado de la log-verosimilitud de X, una vez
que tenemos el nuevo ѳ, podemos elegir una mejor
elección respecto a X e iteramos

El paso E

1. Elegir un valor inicial para ѳ
2. Dados los datos observados y pretendiendo por
ahora que la suposición actual de es correcta,
calcular que tan probable es que los datos completos
valgan , es decir, determinar la distribución
condicional

3. Desechar , sin embargo, preservar
4. Quisiéramos maximizar , pero como no
conocemos realmente , vamos a maximizar su
valor esperado a lo cual llamamos “Función Q”.



• Se integra sobre todo el soporte =
• Observe que la función Q depende de ѳ pero también

de la suposición inicial de

El paso M

5. Elegir un nuevo valor para ѳ seleccionando

aquel que maximiza a la función Q


6. Hacer m=m+1
7. Volver a (2)

Expresión mas conveniente para la función Q

• Vimos que



• Pero de acuerdo a Bayes



• Y como Y=T(X) es una función determinista



• Decir que Y=T(X) es una función determinista significa que

una realización x determina a y de manera única y por lo tanto
la probabilidad de que ocurra el par (x,y) es igual a la
probabilidad de que ocurra x, por ejemplo la probabilidad de
que llueva es igual a la probabilidad de que llueva y haya
nubes en el cielo.

• Finalmente:



Ejemplo

• A n niños les dan a escoger un juguete de entre 4

opciones

• El histograma de elecciones es
Entonces es el número de niños que escogieron

el juguete 1, etc

• Podemos modelar el histograma aleatorio Y

mediante la distribución multinomial la cual tiene
2 parámetros, el número de ensayos (n) y la
probabilidad de que los niños elijan cada uno de
los 4 juguetes, el vector ;

• La probabilidad de observar un histograma en

particular es



Ejemplo (continuación)

• Suponga que en este caso p depende de un parámetro

ѳ de manera que


• El problema consiste en estimar el valor de ѳ que

maximiza la verosimilitud del histograma observado

• La probabilidad de observar el histograma
es entonces:



• Este ejemplo puede resolverse mediante un

maximización de la log-verosimilitud directamente, sin
embargo lo resolveremos mediante EM

El truco

• Para utilizar EM necesitamos especificar a que llamamos X

(los datos completos) y hacerlo de manera que su
distribución también se pueda expresar en términos del
mismo parámetro ѳ. Para nuestro ejemplo, una solución es
considerar

con distribución multinomial donde las probabilidades de

cada evento son

• Y la relación entre los datos observados Y con los datos

completos X es:

• Por tanto, la verosimilitud de una realización x de los datos

completos es:



La función Q del ejemplo

• Sabemos que la función Q está definida por



• En nuestro caso



• Para maximizar Q solo necesitamos los términos que

dependan de ѳ, los demás son irrelevantes (para
efectos de la maximización sobre ѳ)



Obteniendo la expresión a maximizar
• Para resolver



• Necesitamos la esperanza condicional de los datos
completos X condicionada a la realización de datos
completos conocidos (y) lo cual solo nos deja
incertidumbre acerca de dado que

• Dado , el par se distribuye binomialmente

es la función indicadora
• El valor esperado es la media, en este caso es
binomial por tanto

Obteniendo la expresión a maximizar y
comenzamos a maximizar de una vez

• Sustituyendo
en

obtenemos



• Derivando e igualando a cero obtenemos

0)1(112324)(1)(yyyymm Maximizando

)()1(2324)(1)(yyyymm4)(1)(324)(1)(22yyyyyymmmm0)1(112324)(1)(yyyymm Ejecutando el algoritmo EM

Si iniciamos con

Si los datos observados (el histograma) fueran y=[55 20 20 5]

Aplicando sucesivamente :

t=( (t/(2+t))*y(1)+y(4) )/( (t/(2+t))*y(1)+y(2)+y(3)+y(4) )

m

0

1

2

3

4

5

6

7

8

0.5

0.2857

0.2289

0.2102

0.2037

0.2013

0.2005

0.2002

0.2001

)(m Cuando realmente se trata de un
problema de datos incompletos

• Si los datos completos X consisten de datos observados Y y de datos

perdidos (u ocultos) de manera que X=(Y,Z) se puede escribir la
función Q como una integral sobre todo el dominio de Z dado que
es la única parte aleatoria de X

• Un ejemplo de esto es cuando se estiman los parámetros de una

mezcla de gaussianas

• Otro ejemplo es cuando se estiman los parámetros de un modelo

oculto de Markov


Mezcla de gaussianas

Una mezcla de gaussianas es una suma ponderada de k gaussianas

Donde:

Dadas n observaciones de dimensión d, deseamos estimar los parámetros:

Mezcla de 3 gaussianas 1D

Mezcla de 2 gaussianas 2D

Una proposición útil

Si X consiste de n muestras

i.i.d., es decir:

Entonces

donde

Demostración

Ya que las muestras son i.i.d.

Ya que

Y esto es porque no depende de excepto cuando i=j

ixjy Derivación de EM para mezcla de

gaussianas

Dadas n muestras i.i.d.

tomadas de una mezcla de gaussianas con parámetros

Sea:

Definimos a la probabilidad de que la i-ésima muestra pertenezca a la j-ésima gaussiana como

que satisface:

El paso E

Por tanto:

El paso M

Definiendo

Podemos reescribir la función Q como

El paso M consiste en maximizar

sujeto a

Multiplicadores de Lagrange

• Para maximizar una función no lineal



• Sujeta a restricciones dadas por



• Formamos el Lagrangiano asociando un multiplicador de

Lagrange λ con cada restricción


• Luego se resuelve el sistema de n+m ecuaciones



),...,,(21nxxxfmnmnnbxxxgbxxxgbxxxg),...,,(:),...,,(),...,,(2122121211miniiinmnxxxgbxxxfxxxL121212121)],...,,([),...,,(),...,,,,...,,(mjLnjxLjj,..,2,10,..,2,10 Aplicando Lagrange para encontrar los pesos

Maximizar la función

Sujeto a la restricción

Formamos el Lagrangiano:

Observe que se han eliminado los términos que no depende de ω

Derivando respecto a
Obtenemos k ecuaciones

Derivando respecto a λ
Obtenemos otra ecuación

Finalmente, resolvemos el
sistema de k+1 ecs de donde:

Para encontrar las medias:

hacemos:

pero

Lo cual conduce a:

j=1,…,k

por lo tanto:

nimijjniimijjjmyQ1)(1)(1)()|( Para encontrar la matriz de

covarianzas

Derivando:

De ahí:

Algoritmo EM para mezcla de gaussianas

Ejemplo

Considere una mezcla de 2 gaussianas 2D con los siguientes parámetros:

Se generan 1000 valores aleatorios
de esta distribución

Solución

Usamos k-medias para determinar los centroides y usarlos como primera aproximación

Elegimos

también

y

Y después de solo tres iteraciones encontramos:

Tres iteraciones