El algoritmo de esperanza-maximización (EM)

[pic 1]

[pic 2]

[pic 3]

ALGORITMO EXPECTATION-MAXIMIZATION EM

Definición

El algoritmo de esperanza-maximización (EM) se trata de una técnica de optimización utilizada en estadísticas y aprendizaje automático para abordar problemas en los que los datos observados están incompletos o contienen variables latentes no observadas.  

Objetivo

Estimar los parámetros de un modelo probabilístico cuando se tienen datos incompletos o faltantes. El algoritmo EM consta de dos pasos iterativos: el paso de expectativa (E-step) y el paso de maximización (M-step).

¿Cómo funciona?

Inicialización:

Comienza con una estimación inicial de los parámetros del modelo. Esto podría ser aleatorio o basado en algún conocimiento previo.

Etapa de Esperanza (E-step)

En esta etapa, se calcula la esperanza (expectativa) de la función de verosimilitud condicional con respecto a las variables latentes, dado los datos observados y los parámetros actuales del modelo. Se estima la distribución de probabilidad condicional de las variables latentes dados los datos observados y los parámetros actuales. Esto implica calcular los valores esperados de las variables latentes, que a menudo se llaman "responsabilidades". Estas responsabilidades indican la probabilidad de que cada variable latente esté presente en cada observación.

Etapa de Maximización (M-step): 

En dicha etapa, se maximiza la función de verosimilitud condicional, dadas las responsabilidades (valores esperados) estimadas de las variables latentes en la etapa de esperanza. Se ajustan los parámetros del modelo para aumentar la probabilidad de los datos observados dados los valores estimados de las variables latentes. Esto puede implicar resolver un problema de optimización para encontrar los nuevos valores de los parámetros que mejor se ajusten a los datos observados.

Iteración

Los pasos de expectativa y maximización se repiten en iteraciones sucesivas hasta que la convergencia se alcanza. La convergencia generalmente se verifica mediante criterios como la diferencia en la función de verosimilitud entre iteraciones.

El algoritmo EM se repite hasta que la función de verosimilitud no aumente significativamente.

El algoritmo EM se utiliza en una variedad de aplicaciones, incluyendo:

• Clasificación
• Agrupación
• Detección de anomalías
• Regresión
• Aprendizaje automático

Descripción paso a paso

Supongamos un conjunto incompleto (algunas características de algunos patrones se han perdido) de datos X, asumiremos que se puede descomponer en dos componentes, la componente observada X0 y la componente perdida Xm. Especificaremos con p(X | θ) la función de densidad de probabilidad que generó los datos. De este modo podemos escribir:

[pic 4]

El algoritmo EM pretende encontrar un valor de θ que maximice p( X0| θ) dada una observación X0. La función p(Xm | X0, θ) juega un papel importante, ya que relaciona la función de probabilidad del conjunto total con la de la componente observada. Además, fijados los parámetros permite estimar un valor de Xm, y fijado Xm nos permite verificar como de bien se ajustan los parámetros.

Entonces podemos expresar:

[pic 5]

En la notación empleada, cuando escribimos θ nos referimos a una variable aleatoria, mientras que si añadimos el subíndice superior θk a lo que nos referimos es a la estimación k-ésima de esos parámetros.

Los cuatro pasos del algoritmo EM son los siguientes:

1. Fijar k=0 e inicializar θ con un θ0 arbitrario.
2. Paso-E: calcular Q (θk+1 | θk ) .
3. Paso-M: encontrar θk+1 tal que Q (θ| θk ) quede maximizado.
4. Si θk+1 ≠ θk incrementar k y volver al paso 2.

Ciclo del algoritmo proyectado en un caso de perfil tumoral dentro de biología computacional

El algoritmo EM se emplea en problemas de biología computacional relacionados al “dogma central” de la biología molecular, el descubrimiento de motif de secuencia, alineación de secuencias de proteínas, genética de poblaciones, modelos evolutivos y análisis de datos de microarrays de expresión de ARN, etc

• Figura A - Data Original Etiquetada (3 grupos):

En la Figura A, se tiene un conjunto de datos donde los perfiles tumorales de los pacientes están etiquetados en tres grupos diferentes. Los descriptores en dos dimensiones (X1 y X2) podrían representar características específicas de los perfiles tumorales.

...