Expectation-Maximization Algorithm/es

Article
Topic area	Machine Learning
Prerequisites	Maximum Likelihood Estimation, Latent Variable Models, Kullback-Leibler Divergence

This page is a translated version of the page Expectation-Maximization Algorithm and the translation is 100% complete.

Other languages:

English
Español
中文

Esperanza-Maximización (EM) es un algoritmo iterativo para hallar estimaciones de máxima verosimilitud o máximo a posteriori (MAP) de los parámetros en modelos estadísticos que involucran variables latentes no observadas. Cada iteración alterna entre calcular la log-verosimilitud esperada de los datos bajo la distribución posterior actual sobre las latentes (el paso E) y maximizar esta esperanza con respecto a los parámetros (el paso M). EM es la herramienta estándar para ajustar modelos de mezcla, modelos ocultos de Markov, analizadores factoriales y muchos otros modelos con variables latentes, y constituye la base de la teoría moderna de la inferencia variacional.

Visión general

Muchos modelos de interés práctico suponen que cada punto de datos observado $$ x $$ se genera junto con una variable latente $$ z $$ que nunca se observa directamente. Algunos ejemplos son la asignación de clúster en una mezcla gaussiana, la secuencia de estados ocultos en un modelo oculto de Markov, el tópico de una palabra en Latent Dirichlet Allocation y el factor compartido en el análisis factorial. La verosimilitud marginal

p(x \mid \theta) = \sum_{z} p(x, z \mid \theta) \quad \text{or} \quad \int p(x, z \mid \theta)\, dz

típicamente carece de una forma cerrada manejable, y el ascenso de gradiente directo sobre $\log p(x \mid \theta)$ resulta incómodo porque la suma o la integral queda dentro del logaritmo.

EM sortea esta dificultad introduciendo la distribución posterior $p(z \mid x, \theta)$ como distribución de acoplamiento. En cada iteración el algoritmo calcula (o acota) esta posterior usando los parámetros actuales, y luego optimiza un objetivo sustituto en el que las variables latentes están efectivamente "completadas". El procedimiento recibió su nombre y formulación general por parte de Dempster, Laird y Rubin en 1977, aunque casos especiales habían aparecido décadas antes en la literatura de genética, procesamiento de señales y agrupamiento.

EM resulta atractivo porque cada iteración garantiza que la log-verosimilitud marginal nunca disminuye, el paso M a menudo se reduce a un problema familiar de máxima verosimilitud totalmente observado, y el algoritmo no requiere tasa de aprendizaje ni tamaño de paso. Es el ejemplo canónico de un procedimiento de Majorization-Minimization y un antecesor directo de la moderna Variational Inference.

Intuición

EM puede entenderse mediante una sencilla observación del tipo "el huevo y la gallina". Si las variables latentes $$ z $$ fueran conocidas, ajustar $\theta$ se reduciría a una Maximum Likelihood Estimation estándar sobre los datos completos $$ (x, z) $$ . Recíprocamente, si $\theta$ fuera conocido, la distribución posterior $p(z \mid x, \theta)$ nos diría cuáles son probablemente las latentes. Ninguna de las dos cosas está disponible al inicio, así que EM se autoarranca: hace una conjetura blanda sobre las latentes usando los parámetros actuales, vuelve a ajustar los parámetros como si esa conjetura fuera cierta, e itera.

El calificativo "blando" es importante. A diferencia de las heurísticas de asignación dura, como la actualización canónica de k-medias, EM no se compromete con un único valor de $$ z $$ . En su lugar, calcula una distribución sobre las latentes y pondera el paso M con dicha distribución. Esta asignación blanda es lo que hace que la log-verosimilitud marginal sea no decreciente y lo que distingue a EM del descenso por coordenadas sobre un objetivo de asignación dura.

Formulación

Cota inferior de la evidencia

Sea $$ q(z) $$ una distribución cualquiera sobre las variables latentes. La desigualdad de Jensen proporciona la cota inferior de la evidencia (ELBO):

\log p(x \mid \theta) \;\geq\; \mathbb{E}_{q(z)}\!\left[\log p(x, z \mid \theta)\right] - \mathbb{E}_{q(z)}\!\left[\log q(z)\right] \;\equiv\; \mathcal{L}(q, \theta).

La diferencia entre la log-verosimilitud marginal y la ELBO es exactamente la Kullback-Leibler Divergence de $$ q(z) $$ a la verdadera distribución posterior:

\log p(x \mid \theta) - \mathcal{L}(q, \theta) = \mathrm{KL}\!\left(q(z) \,\Vert\, p(z \mid x, \theta)\right) \geq 0.

Entonces EM es un ascenso por coordenadas sobre $\mathcal{L}$ : maximiza alternadamente respecto de $$ q $$ (con $\theta$ fijo) y respecto de $\theta$ (con $$ q $$ fijo).

Paso E

Con $\theta$ fijo en la estimación actual $\theta^{(t)}$ , la ELBO se maximiza igualando $$ q $$ a la distribución posterior:

q^{(t+1)}(z) = p(z \mid x, \theta^{(t)}).

Esto reduce a cero el término de KL y aprieta la cota. Equivalentemente, el paso E calcula la log-verosimilitud esperada de los datos completos, a menudo denotada

Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{p(z \mid x, \theta^{(t)})}\!\left[\log p(x, z \mid \theta)\right].

En la práctica, el paso E se reduce a evaluar las estadísticas suficientes de $$ z $$ bajo la distribución posterior — por ejemplo, las responsabilidades $r_{ik} = p(z_i = k \mid x_i, \theta^{(t)})$ en un modelo de mezcla, o las probabilidades de estado suavizadas calculadas mediante la recursión hacia adelante y hacia atrás en un modelo oculto de Markov.

Paso M

Manteniendo $q^{(t+1)}$ fijo, la ELBO se convierte (salvo una constante aditiva) en la log-verosimilitud esperada de los datos completos, y el paso M resuelve

\theta^{(t+1)} = \arg\max_{\theta} \; Q(\theta \mid \theta^{(t)}).

Como $q^{(t+1)}$ no depende de $\theta$ , las latentes actúan como pesos fijos y la optimización suele reducirse a un problema estándar de máxima verosimilitud totalmente observado. Para familias exponenciales, el paso M tiene a menudo forma cerrada: las medias ponderadas, las covarianzas ponderadas y los conteos multinomiales ponderados sustituyen a sus análogos no ponderados.

Mejora monótona

La actualización combinada satisface

\log p(x \mid \theta^{(t+1)}) \;\geq\; \mathcal{L}(q^{(t+1)}, \theta^{(t+1)}) \;\geq\; \mathcal{L}(q^{(t+1)}, \theta^{(t)}) \;=\; \log p(x \mid \theta^{(t)}),

de modo que la log-verosimilitud marginal es no decreciente en cada iteración. Bajo condiciones suaves de regularidad, las iteraciones convergen a un punto estacionario de la verosimilitud marginal, aunque no necesariamente a un óptimo global.

Ejemplo canónico: Modelos de mezcla gaussiana

Para un modelo de mezcla gaussiana con $$ K $$ componentes, parámetros $\theta = \{\pi_k, \mu_k, \Sigma_k\}$ y asignación latente $z_i \in \{1, \ldots, K\}$ , las actualizaciones de EM adoptan una forma especialmente transparente.

El paso E calcula la responsabilidad de cada componente para cada punto:

r_{ik} = \frac{\pi_k \, \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \, \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}.

El paso M utiliza estas responsabilidades como conteos blandos:

N_k = \sum_{i=1}^{N} r_{ik}, \quad \pi_k^{\text{new}} = \frac{N_k}{N}, \quad \mu_k^{\text{new}} = \frac{1}{N_k}\sum_{i=1}^{N} r_{ik}\, x_i, \quad \Sigma_k^{\text{new}} = \frac{1}{N_k}\sum_{i=1}^{N} r_{ik}\,(x_i - \mu_k^{\text{new}})(x_i - \mu_k^{\text{new}})^{\!\top}.

En el límite en que cada responsabilidad colapsa a un vector one-hot (por ejemplo, cuando las covarianzas se contraen hacia un valor isótropo $\sigma^2 I$ con $\sigma \to 0$ ), el algoritmo se reduce exactamente a k-medias, que por tanto constituye el límite de asignación dura de EM para una mezcla gaussiana esférica.

Variantes y generalizaciones

Varias relajaciones de la receta básica amplían su aplicabilidad cuando el paso E o el paso M son intratables.

EM generalizado (GEM): el paso M se sustituye por cualquier actualización que aumente (en lugar de maximizar) $Q(\theta \mid \theta^{(t)})$ . Se conserva la mejora monótona de la log-verosimilitud marginal.
Esperanza-Maximización Condicional (ECM): el paso M se descompone en una secuencia de maximizaciones condicionales sobre bloques disjuntos de parámetros, lo cual es útil cuando la maximización conjunta es difícil pero la condicional es fácil.
EM estocástico y EM de Monte Carlo: cuando la distribución posterior $p(z \mid x, \theta)$ es intratable, el paso E se reemplaza por muestreo. En el EM estocástico se extrae una sola muestra; en el EM de Monte Carlo, una media muestral aproxima la esperanza.
EM variacional: el paso E restringe $$ q $$ a una familia tratable $\mathcal{Q}$ y minimiza la divergencia KL a la verdadera posterior dentro de esa familia. La log-verosimilitud marginal queda entonces acotada pero no necesariamente alcanzada, sacrificando exactitud por tratabilidad. Este es el puente entre el EM clásico y los modernos métodos variacionales.
EM en línea e incremental: las estadísticas suficientes se actualizan mediante medias móviles ponderadas exponencialmente sobre minilotes, escalando EM a datos en streaming o a conjuntos masivos.
EM duro: cada paso E reemplaza la posterior por una masa puntual en su moda. Se pierde la garantía de mejora monótona, pero a veces se prefiere por velocidad o cuando las posteriores son muy concentradas.

Propiedades de convergencia

EM es un algoritmo de búsqueda local. Su propiedad de mejora monótona garantiza la convergencia de la sucesión de log-verosimilitud marginal a un límite, y bajo condiciones de regularidad estándar las iteraciones de los parámetros convergen a un punto estacionario — típicamente un máximo local, pero posiblemente un punto silla o un punto de la frontera del espacio de parámetros. La tasa de convergencia es genéricamente lineal y está gobernada por el principio de información faltante de Dempster, Laird y Rubin: cuanto más cercana esté la distribución posterior sobre las latentes a una masa puntual, más rápido converge EM. Cuando la fracción de información faltante es grande, la convergencia puede ser muy lenta, y a veces se emplean esquemas de aceleración cuasi-Newton (Aitken, SQUAREM, EM con expansión de parámetros).

La sensibilidad a la inicialización es un problema práctico bien conocido. Para los modelos de mezcla, las estrategias habituales incluyen múltiples reinicios aleatorios, inicialización con k-medias y enfriamiento determinista, que comienza con un objetivo fuertemente suavizado y lo afina gradualmente.

Conexiones

EM es un caso particular de la familia Majorization-Minimization: cada iteración construye una cota inferior tangente (la ELBO en los parámetros actuales) y maximiza esa cota. Esta perspectiva unifica EM con los métodos proximales, los algoritmos MM en optimización y la literatura reciente sobre maximización de cotas inferiores en problemas no convexos.

EM es también el ancestro conceptual de la Variational Inference y del autocodificador variacional. Mientras que EM evalúa la distribución posterior exacta en el paso E, los métodos variacionales la sustituyen por una aproximación tratable; mientras que EM optimiza los parámetros en el paso M, la inferencia variacional amortizada aprende una red de inferencia que predice la posterior variacional a partir de los datos. La ELBO, que surgió como herramienta para analizar EM, es hoy el objetivo central de entrenamiento de los modelos generativos probabilísticos profundos.

En el análisis de componentes principales probabilístico (PPCA), en el análisis factorial y en el análisis de componentes independientes, EM ofrece una alternativa escalable a la descomposición en autovectores directa o a la iteración de punto fijo. En los modelos ocultos de Markov, el algoritmo EM se especializa en el algoritmo de Baum-Welch, donde el paso E es la recursión hacia adelante y hacia atrás y el paso M es una reestimación cerrada de los parámetros de transición y de emisión.

Limitaciones

EM es potente, pero no universal. Sus principales limitaciones prácticas son:

Óptimos locales: la verosimilitud marginal suele ser no convexa y EM converge solo a un punto estacionario. Las mezclas con componentes mal separados, en particular, exhiben muchos máximos locales y puntos silla.
Convergencia lenta con alta información faltante: cuando la distribución posterior es difusa, el paso M solo realiza pequeños movimientos en los parámetros, y el algoritmo puede requerir muchísimas iteraciones.
Singularidades: en las mezclas gaussianas con covarianza no restringida, la verosimilitud no está acotada — un único componente puede colapsar sobre un solo punto y llevar la verosimilitud al infinito. Las implementaciones prácticas regularizan las covarianzas o imponen priors para evitar esta patología.
Paso E intratable: para modelos complejos con latentes discretas en alta dimensión o con estructura latente fuertemente acoplada, calcular la posterior exacta es inviable y se requieren aproximaciones variacionales o de Monte Carlo.
Sin cuantificación de la incertidumbre: EM devuelve estimaciones puntuales de $\theta$ y, por sí mismo, no proporciona una distribución posterior sobre los parámetros. Añadir un prior y emplear MAP-EM aborda esto parcialmente; un tratamiento plenamente bayesiano requiere Bayes variacional o MCMC.

Estas limitaciones motivan el panorama más amplio de las técnicas de inferencia aproximada en el aprendizaje automático probabilístico moderno.

Véase también

Referencias

Dempster, A. P., Laird, N. M. y Rubin, D. B. (1977). "Maximum Likelihood from Incomplete Data via the EM Algorithm". Journal of the Royal Statistical Society, Series B, 39(1), 1-38.
Wu, C. F. J. (1983). "On the Convergence Properties of the EM Algorithm". The Annals of Statistics, 11(1), 95-103.
McLachlan, G. J. y Krishnan, T. (2008). The EM Algorithm and Extensions (2.ª ed.). Wiley.
Neal, R. M. y Hinton, G. E. (1998). "A View of the EM Algorithm that Justifies Incremental, Sparse, and Other Variants". En Learning in Graphical Models, M. I. Jordan (ed.), Kluwer, 355-368.
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer, capítulo 9.
Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. MIT Press, capítulo 11.
Baum, L. E., Petrie, T., Soules, G. y Weiss, N. (1970). "A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains". The Annals of Mathematical Statistics, 41(1), 164-171.