Algoritmo de maximización de expectativas

En estadística , un algoritmo de expectativa-maximización ( EM ) es un método iterativo para encontrar estimaciones de máxima verosimilitud (local) o máxima a posteriori (MAP) de parámetros en modelos estadísticos , donde el modelo depende de variables latentes no observadas . ^{[ 1 ]} La iteración EM alterna entre realizar un paso de expectativa (E), que crea una función para la esperanza de la log-verosimilitud evaluada usando la estimación actual para los parámetros, y un paso de maximización (M), que calcula parámetros que maximizan la log-verosimilitud esperada encontrada en el paso E. Estas estimaciones de parámetros se usan luego para determinar la distribución de las variables latentes en el siguiente paso E. Se puede usar, por ejemplo, para estimar una mezcla de gaussianas o para resolver el problema de regresión lineal múltiple. ^{[ 2 ]}

El algoritmo EM fue explicado y nombrado en un artículo clásico de 1977 por Arthur Dempster , Nan Laird y Donald Rubin . ^{[ 3 ]} Señalaron que el método había sido "propuesto muchas veces en circunstancias especiales" por autores anteriores. Uno de los primeros es el método de conteo de genes para estimar frecuencias alélicas por Cedric Smith . ^{[ 4 ]} Otro fue propuesto por HO Hartley en 1958, y Hartley y Hocking en 1977, del cual se originaron muchas de las ideas del artículo de Dempster-Laird-Rubin. ^{[ 5 ]} Otro por SK Ng, Thriyambakam Krishnan y GJ McLachlan en 1977. ^{[ 6 ]} Las ideas de Hartley pueden ampliarse a cualquier distribución discreta agrupada. Rolf Sundberg publicó un tratamiento muy detallado del método EM para familias exponenciales en su tesis y varios artículos, ^{[ 7 ] [ 8 ] [ 9 ]} tras su colaboración con Per Martin-Löf y Anders Martin-Löf . ^{[ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] El artículo de Dempster, Laird y Rubin de 1977 generalizó el método y esbozó un análisis de convergencia para una clase más amplia de problemas. El artículo de} Dempster, Laird y Rubin estableció el método EM como una herramienta importante del análisis estadístico. Véase también Meng y van Dyk (1997).

El análisis de convergencia del algoritmo de Dempster-Laird-Rubin era erróneo y un análisis de convergencia correcto fue publicado por CF Jeff Wu en 1983. ^{[ 15 ]} La demostración de Wu estableció la convergencia del método EM también fuera de la familia exponencial , como afirmaban Dempster-Laird-Rubin. ^{[ 15 ]}

El algoritmo EM se utiliza para encontrar parámetros de máxima verosimilitud (local) de un modelo estadístico cuando las ecuaciones no pueden resolverse directamente. Normalmente, estos modelos incluyen variables latentes, además de parámetros desconocidos y observaciones de datos conocidas. Es decir, existen valores faltantes en los datos o el modelo puede formularse de forma más sencilla asumiendo la existencia de otros datos no observados. Por ejemplo, un modelo de mezcla puede describirse de forma más sencilla asumiendo que cada dato observado tiene un dato no observado correspondiente, o variable latente, que especifica el componente de la mezcla al que pertenece cada dato.

Para encontrar una solución de máxima verosimilitud, normalmente se requiere derivar la función de verosimilitud con respecto a todos los valores desconocidos (los parámetros y las variables latentes) y resolver simultáneamente las ecuaciones resultantes. En modelos estadísticos con variables latentes, esto suele ser imposible. En cambio, el resultado suele ser un conjunto de ecuaciones interconectadas en las que la solución de los parámetros requiere los valores de las variables latentes y viceversa, pero al sustituir un conjunto de ecuaciones en el otro se obtiene una ecuación irresoluble.

El algoritmo EM parte de la observación de que existe una forma de resolver numéricamente estos dos conjuntos de ecuaciones. Simplemente se pueden elegir valores arbitrarios para uno de los dos conjuntos de incógnitas, usarlos para estimar el segundo conjunto, luego usar estos nuevos valores para encontrar una mejor estimación del primer conjunto, y luego seguir alternando entre los dos hasta que los valores resultantes converjan a puntos fijos. No es obvio que esto funcione, pero se puede demostrar en este contexto. Además, se puede demostrar que la derivada de la verosimilitud es (arbitrariamente cercana a) cero en ese punto, lo que a su vez significa que el punto es un máximo local o un punto de silla . ^{[ 15 ]} En general, pueden ocurrir múltiples máximos, sin garantía de que se encuentre el máximo global. Algunas verosimilitudes también tienen singularidades , es decir, máximos sin sentido. Por ejemplo, una de las soluciones que puede encontrar EM en un modelo de mezcla implica establecer uno de los componentes con varianza cero y el parámetro de media para el mismo componente igual a uno de los puntos de datos.

Aunque una iteración EM aumenta la función de verosimilitud de los datos observados (es decir, marginal), no existe garantía de que la secuencia converja a un estimador de máxima verosimilitud . Para distribuciones multimodales , esto significa que un algoritmo EM puede converger a un máximo local de la función de verosimilitud de los datos observados, dependiendo de los valores iniciales. Existen diversos enfoques heurísticos o metaheurísticos para escapar de un máximo local, como el ascenso de colinas con reinicio aleatorio (comenzando con varias estimaciones iniciales aleatorias diferentes ).${\displaystyle {\boldsymbol {\theta }}^{(t)}}$) , o aplicando métodos de recocido simulado .

EM es especialmente útil cuando la verosimilitud es una familia exponencial , véase Sundberg (2019, cap. 8) para un tratamiento exhaustivo: ^{[ 16 ]} el paso E se convierte en la suma de esperanzas de estadísticas suficientes , y el paso M implica maximizar una función lineal. En tal caso, suele ser posible derivar actualizaciones de expresiones de forma cerrada para cada paso, utilizando la fórmula de Sundberg ^{[ 17 ]} (demostrada y publicada por Rolf Sundberg, basada en resultados no publicados de Per Martin-Löf y Anders Martin-Löf ). ^{[ 8 ] [ 9 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ]}

En el artículo original de Dempster, Laird y Rubin, se modificó el método EM para calcular estimaciones de máxima probabilidad a posteriori (MAP, por sus siglas en inglés) para la inferencia bayesiana.

Existen otros métodos para hallar estimaciones de máxima verosimilitud, como el descenso de gradiente , el gradiente conjugado o variantes del algoritmo de Gauss-Newton . A diferencia del algoritmo EM, estos métodos suelen requerir la evaluación de las primeras y/o segundas derivadas de la función de verosimilitud.

Expectation-Maximization funciona para mejorar${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$en lugar de mejorar directamente${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}$Aquí se demuestra que las mejoras en el primero implican mejoras en el segundo. ^{[ 18 ]}

Para cualquier${\displaystyle \mathbf {Z} }$con probabilidad distinta de cero${\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})}$⁠ , podemos escribir $${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})=\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}).}$$ Tomamos la esperanza sobre los posibles valores de los datos desconocidos.${\displaystyle \mathbf {Z} }$bajo la estimación de parámetros actual${\displaystyle \theta ^{(t)}}$multiplicando ambos lados por${\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}$y sumando (o integrando) sobre${\displaystyle \mathbf {Z} }$. El lado izquierdo es la esperanza de una constante, por lo que obtenemos: $${\displaystyle {\begin{aligned}\log p(\mathbf {X} \mid {\boldsymbol {\theta }})&=\sum _{\mathbf {Z} }p{\left(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)}\right)}\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\sum _{\mathbf {Z} }p{\left(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)}\right)}\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})\\&=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)}),\end{aligned}}}$$ dónde${\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$se define por la suma negada que está reemplazando. Esta última ecuación se cumple para cada valor de${\displaystyle {\boldsymbol {\theta }}}$incluido${\displaystyle {\boldsymbol {\theta }}={\boldsymbol {\theta }}^{(t)}}$, $${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}),}$$ y restando esta última ecuación de la ecuación anterior se obtiene $${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}).}$$ Sin embargo, la desigualdad de Gibbs nos dice que${\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})}$, por lo que podemos concluir que $${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})\geq Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}).}$$ En palabras, elegir${\displaystyle {\boldsymbol {\theta }}}$para mejorar${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$causas${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}$mejorar al menos en la misma medida.

El algoritmo EM puede verse como dos pasos de maximización alternados, es decir, como un ejemplo de descenso de coordenadas . ^{[ 19 ] [ 20 ]} Considere la función: $${\displaystyle F(q,\theta ):=\operatorname {E} _{q}[\log L(\theta ;x,Z)]+H(q),}$$ donde q es una distribución de probabilidad arbitraria sobre los datos no observados z y H ( q ) es la entropía de la distribución q . Esta función se puede escribir como $${\displaystyle F(q,\theta )=-D_{\mathrm {KL} }{\big (}q\parallel p_{Z\mid X}(\cdot \mid x;\theta ){\big )}+\log L(\theta ;x),}$$ dónde ${\displaystyle p_{Z\mid X}(\cdot \mid x;\theta )}$es la distribución condicional de los datos no observados dados los datos observados${\displaystyle x}$y${\displaystyle D_{KL}}$es la divergencia de Kullback-Leibler .

Entonces, los pasos del algoritmo EM pueden verse como:

• Paso de expectativa : Elegir${\displaystyle q}$para maximizar${\displaystyle F}$:​$${\displaystyle q^{(t)}=\mathop {\arg \max } _{q}F{\left(q,\theta ^{(t)}\right)}}$$
• Paso de maximización : Elegir${\displaystyle \theta }$para maximizar${\displaystyle F}$:​$${\displaystyle \theta ^{(t+1)}=\mathop {\arg \max } _{\theta }F{\left(q^{(t)},\theta \right)}}$$

• EM se utiliza frecuentemente para la estimación de parámetros de modelos mixtos , ^{[ 21 ] [ 22 ]} especialmente en genética cuantitativa . ^{[ 23 ]}
• En psicometría , el EM es una herramienta importante para estimar los parámetros de los ítems y las habilidades latentes de los modelos de teoría de respuesta al ítem .
• Gracias a su capacidad para gestionar datos faltantes y observar variables no identificadas, el modelo EM se está convirtiendo en una herramienta útil para fijar precios y gestionar el riesgo de una cartera.
• El algoritmo EM (y su variante más rápida, la maximización de la expectativa de subconjuntos ordenados ) también se utiliza ampliamente en la reconstrucción de imágenes médicas , especialmente en la tomografía por emisión de positrones , la tomografía computarizada por emisión de fotón único y la tomografía computarizada de rayos X. Consulte a continuación otras variantes más rápidas del algoritmo EM.
• En ingeniería estructural , el algoritmo de identificación estructural mediante maximización de expectativas (STRIDE) ^{[ 24 ]} es un método de solo salida para identificar propiedades de vibración natural de un sistema estructural utilizando datos de sensores (ver Análisis modal operacional ).
• EM también se utiliza para la agrupación de datos . En el procesamiento del lenguaje natural , dos ejemplos destacados del algoritmo son el algoritmo Baum-Welch para modelos ocultos de Markov y el algoritmo inside-outside para la inducción no supervisada de gramáticas probabilísticas libres de contexto .
• En el análisis de los tiempos de espera entre transacciones , el algoritmo EM ha demostrado ser muy útil. ^{[ 25 ]}

El filtro de Kalman se utiliza habitualmente para la estimación de estado en línea, mientras que un suavizador de mínima varianza puede emplearse para la estimación de estado fuera de línea o por lotes. Sin embargo, estas soluciones de mínima varianza requieren estimaciones de los parámetros del modelo de espacio de estados. Los algoritmos EM pueden utilizarse para resolver problemas conjuntos de estimación de estado y parámetros.

Los algoritmos EM de filtrado y suavizado surgen al repetir este procedimiento de dos pasos:

Paso E

Utilice un filtro de Kalman o un suavizador de varianza mínima diseñado con las estimaciones de parámetros actuales para obtener estimaciones de estado actualizadas.

Paso M

Utilice las estimaciones de estado filtradas o suavizadas dentro de los cálculos de máxima verosimilitud para obtener estimaciones de parámetros actualizadas.

Supongamos que un filtro de Kalman o un suavizador de varianza mínima opera sobre mediciones de un sistema de una entrada y una salida que poseen ruido blanco aditivo. Se puede obtener una estimación actualizada de la varianza del ruido de medición a partir del cálculo de máxima verosimilitud.$${\displaystyle {\widehat {\sigma }}_{v}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{(z_{k}-{\widehat {x}}_{k})}^{2},}$$

dónde${\displaystyle {\widehat {x}}_{k}}$son estimaciones de salida escalar calculadas por un filtro o un suavizador a partir de N mediciones escalares${\displaystyle z_{k}}$La actualización anterior también se puede aplicar para actualizar la intensidad del ruido de medición de Poisson. De manera similar, para un proceso autorregresivo de primer orden, se puede calcular una estimación actualizada de la varianza del ruido del proceso mediante $${\displaystyle {\widehat {\sigma }}_{w}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k})}^{2},}$$

dónde${\displaystyle {\widehat {x}}_{k}}$y${\displaystyle {\widehat {x}}_{k+1}}$son estimaciones de estado escalares calculadas por un filtro o un suavizador. La estimación actualizada del coeficiente del modelo se obtiene mediante $${\displaystyle {\widehat {F}}={\frac {\sum \limits _{k=1}^{N}{\left({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k}\right)}^{2}}{\sum \limits _{k=1}^{N}{\widehat {x}}_{k}^{2}}}.}$$

La convergencia de las estimaciones de parámetros como las anteriores está bien estudiada. ^{[ 26 ] [ 27 ] [ 28 ] [ 29 ]}

Se han propuesto varios métodos para acelerar la convergencia, a veces lenta, del algoritmo EM, como los que utilizan el método del gradiente conjugado y el método de Newton modificado (Newton-Raphson). ^{[ 30 ]} Además, EM puede utilizarse con métodos de estimación con restricciones.

El algoritmo de maximización de la expectativa con parámetros expandidos (PX-EM) a menudo proporciona una aceleración al "utilizar un 'ajuste de covarianza' para corregir el análisis del paso M, aprovechando la información adicional capturada en los datos completos imputados". ^{[ 31 ]}

La maximización condicional de la expectativa (ECM) reemplaza cada paso M con una secuencia de pasos de maximización condicional (CM) en los que cada parámetro θ _i se maximiza individualmente, con la condición de que los demás parámetros permanezcan fijos. ^{[ 32 ]} A su vez, puede extenderse al algoritmo de maximización condicional de la expectativa (ECME) . ^{[ 33 ]}

Esta idea se extiende aún más en el algoritmo de maximización de la expectativa generalizada (GEM) , en el que solo se busca un incremento en la función objetivo F tanto para el paso E como para el paso M, como se describe en la sección " Como procedimiento de maximización-maximización" . ^{[ 19 ]} GEM se desarrolla aún más en un entorno distribuido y muestra resultados prometedores. ^{[ 34 ]}

También es posible considerar el algoritmo EM como una subclase del algoritmo MM (Mayorizar/Minimizar o Minorizar/Maximizar, según el contexto), ^{[ 35 ]} y por lo tanto utilizar cualquier maquinaria desarrollada en el caso más general.

EM es un método de máxima verosimilitud parcialmente no bayesiano. Su resultado final proporciona una distribución de probabilidad sobre las variables latentes (al estilo bayesiano) junto con una estimación puntual para θ (ya sea una estimación de máxima verosimilitud o una moda posterior). Puede ser deseable una versión completamente bayesiana de este método, que proporcione una distribución de probabilidad sobre θ y las variables latentes. El enfoque bayesiano para la inferencia consiste simplemente en tratar a θ como otra variable latente. En este paradigma, la distinción entre los pasos E y M desaparece. Si se utiliza la aproximación Q factorizada como se describió anteriormente ( Bayes variacional ), la resolución puede iterar sobre cada variable latente (ahora incluyendo θ ) y optimizarlas una a una. Ahora, se necesitan k pasos por iteración, donde k es el número de variables latentes. Para los modelos gráficos , esto es fácil de hacer ya que el nuevo Q de cada variable depende solo de su manta de Markov , por lo que se puede utilizar el paso de mensajes local para una inferencia eficiente.

En geometría de la información , el paso E y el paso M se interpretan como proyecciones bajo conexiones afines duales , llamadas conexión e y conexión m; la divergencia de Kullback-Leibler también puede entenderse en estos términos.

El algoritmo EM suele converger a un óptimo local, no necesariamente al óptimo global, sin límite en la tasa de convergencia en general. Es posible que su rendimiento sea arbitrariamente deficiente en dimensiones altas y que exista un número exponencial de óptimos locales. Por lo tanto, se necesitan métodos alternativos para garantizar el aprendizaje, especialmente en entornos de alta dimensión. Existen alternativas a EM con mejores garantías de consistencia, denominadas enfoques basados ​​en momentos ^{[ 39 ]} o las llamadas técnicas espectrales ^{[ 40 ] [ 41 ]} . Los enfoques basados ​​en momentos para aprender los parámetros de un modelo probabilístico ofrecen garantías como la convergencia global bajo ciertas condiciones, a diferencia de EM, que a menudo se ve afectado por el problema de quedarse atascado en óptimos locales. Se pueden derivar algoritmos con garantías de aprendizaje para varios modelos importantes, como modelos de mezcla, HMM, etc. Para estos métodos espectrales, no se producen óptimos locales espurios y los parámetros verdaderos se pueden estimar de forma consistente bajo ciertas condiciones de regularidad.

• distribución de la mezcla
• distribución compuesta
• estimación de densidad
• Análisis de componentes principales
• espectroscopia de absorción total
• El algoritmo EM puede considerarse un caso especial del algoritmo de minimización mayoritaria (MM) . ^{[ 42 ]}

• Hogg, Robert; McKean, Joseph; Craig, Allen (2005). Introducción a la estadística matemática . Upper Saddle River, NJ: Pearson Prentice Hall. pp. 359–364 . 
• Dellaert, Frank (febrero de 2002). El algoritmo de maximización de expectativas (PDF) (Informe técnico número GIT-GVU-02-20). Facultad de Informática de Georgia Tech.Ofrece una explicación más sencilla del algoritmo EM en lo que respecta a la maximización del límite inferior.
• Bishop, Christopher M. (2006). Reconocimiento de patrones y aprendizaje automático . Springer. ISBN 978-0-387-31073-2.
• Gupta, MR; Chen, Y. (2010). "Teoría y uso del algoritmo EM". Fundamentos y tendencias en el procesamiento de señales . 4 (3): 223– 296. CiteSeerX 10.1.1.219.6830 . doi : 10.1561/2000000034 . Un libro breve y bien escrito sobre EM, que incluye una derivación detallada de EM para GMM, HMM y Dirichlet.
• Bilmes, Jeff (1997). Un tutorial sencillo del algoritmo EM y su aplicación a la estimación de parámetros para modelos de mezcla gaussiana y modelos ocultos de Markov (Informe técnico TR-97-021). Instituto Internacional de Ciencias de la Computación.Incluye una derivación simplificada de las ecuaciones EM para mezclas gaussianas y modelos ocultos de Markov de mezcla gaussiana.
• McLachlan, Geoffrey J.; Krishnan, Thriyambakam (2008). El algoritmo EM y sus extensiones (2.ª  ed.). Hoboken: Wiley. ISBN 978-0-471-20170-0.

• Como parte de las actividades y applets de SOCR , se ofrecen diversas demostraciones en 1D, 2D y 3D del algoritmo EM, junto con el modelado de mezclas . Estos applets y actividades muestran empíricamente las propiedades del algoritmo EM para la estimación de parámetros en diversos entornos.
• Jerarquía de clases en C++ (GPL) incluyendo mezclas gaussianas
• El libro de texto en línea "Teoría de la información, inferencia y algoritmos de aprendizaje" , de David JC MacKay, incluye ejemplos sencillos del algoritmo EM, como la agrupación mediante el algoritmo k -medias suave, y enfatiza la visión variacional del algoritmo EM, tal como se describe en el capítulo 33.7 de la versión 7.2 (cuarta edición).
• Variational Algorithms for Approximate Bayesian Inference , de MJ Beal, incluye comparaciones de EM con EM bayesiano variacional y derivaciones de varios modelos, incluidos HMM bayesianos variacionales ( capítulos ).
• El algoritmo de maximización de la esperanza: un breve tutorial , una derivación autocontenida del algoritmo EM por Sean Borman.
• El algoritmo EM , de Xiaojin Zhu.
• Algoritmo EM y sus variantes: un tutorial informal de Alexis Roche. Una descripción concisa y muy clara del algoritmo EM y muchas variantes interesantes.