Algoritmo de expectativa-maximización

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 expectativa de la log-verosimilitud evaluada utilizando 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 utilizan luego para determinar la distribución de las variables latentes en el siguiente paso E. Se puede utilizar, 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 recibió su nombre en un artículo clásico de 1977 de 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 de alelos de Cedric Smith . ^[4] Otro fue propuesto por HO Hartley en 1958, y Hartley y Hocking en 1977, de donde 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 se pueden ampliar 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–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–Rubin estableció el método EM como una herramienta importante de análisis estadístico. Véase también Meng y van Dyk (1997).

El análisis de convergencia del algoritmo Dempster–Laird–Rubin era defectuoso y un análisis de convergencia correcto fue publicado por CF Jeff Wu en 1983. ^[15] La prueba de Wu estableció la convergencia del método EM también fuera de la familia exponencial , como afirmó Dempster–Laird–Rubin. ^[15]

El algoritmo EM se utiliza para encontrar parámetros de máxima verosimilitud (locales) de un modelo estadístico en casos en los que las ecuaciones no se pueden resolver directamente. Normalmente, estos modelos implican variables latentes además de parámetros desconocidos y observaciones de datos conocidos. Es decir, o bien existen valores faltantes entre los datos, o bien el modelo se puede formular de forma más sencilla suponiendo la existencia de más puntos de datos no observados. Por ejemplo, un modelo de mezcla se puede describir de forma más sencilla suponiendo que cada punto de datos observado tiene un punto de datos no observado correspondiente, o variable latente, que especifica el componente de la mezcla al que pertenece cada punto de datos.

Para encontrar una solución de máxima verosimilitud es necesario tomar las derivadas de 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 los modelos estadísticos con variables latentes, esto suele ser imposible. En cambio, el resultado suele ser un conjunto de ecuaciones entrelazadas en las que la solución de los parámetros requiere los valores de las variables latentes y viceversa, pero la sustitución de un conjunto de ecuaciones en el otro produce 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. Se pueden elegir valores arbitrarios para uno de los dos conjuntos de incógnitas, utilizarlos para estimar el segundo conjunto, utilizar estos nuevos valores para encontrar una mejor estimación del primer conjunto y, a continuación, 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 probabilidad 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 producirse múltiples máximos, sin garantía de que se encuentre el máximo global. Algunas probabilidades también tienen singularidades , es decir, máximos sin sentido. Por ejemplo, una de las soluciones que se pueden encontrar mediante EM en un modelo de mezcla implica establecer que uno de los componentes tenga una varianza cero y que el parámetro medio para el mismo componente sea igual a uno de los puntos de datos. La convergencia de los algoritmos basados ​​en maximización de expectativas (EM) generalmente requiere la continuidad de la función de probabilidad con respecto a todos los parámetros desconocidos (denominados variables de optimización). ^[16]

Dado el modelo estadístico que genera un conjunto de datos observados, un conjunto de datos latentes no observados o valores faltantes y un vector de parámetros desconocidos , junto con una función de verosimilitud , la estimación de máxima verosimilitud (MLE) de los parámetros desconocidos se determina maximizando la verosimilitud marginal de los datos observados.${\displaystyle \mathbf {X} }$ ${\displaystyle \mathbf {Z} }$${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})}$

${\displaystyle L({\boldsymbol {\theta }};\mathbf {X} )=p(\mathbf {X} \mid {\boldsymbol {\theta }})=\int p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})\,d\mathbf {Z} =\int p(\mathbf {X} \mid \mathbf {Z} ,{\boldsymbol {\theta }})p(\mathbf {Z} \mid {\boldsymbol {\theta }})\,d\mathbf {Z} }$

Sin embargo, esta cantidad es a menudo intratable ya que no se observa y se desconoce su distribución antes de alcanzarla .${\displaystyle \mathbf {Z} }$${\displaystyle \mathbf {Z} }$${\displaystyle {\boldsymbol {\theta }}}$

El algoritmo EM busca encontrar la estimación de máxima verosimilitud de la verosimilitud marginal aplicando iterativamente estos dos pasos:

Paso de expectativa (paso E) : se define como el valor esperado de la función de verosimilitud logarítmica de , con respecto a la distribución condicional actual de los datos y las estimaciones actuales de los parámetros :${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$${\displaystyle {\boldsymbol {\theta }}}$${\displaystyle \mathbf {Z} }$${\displaystyle \mathbf {X} }$${\displaystyle {\boldsymbol {\theta }}^{(t)}}$

${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} \sim p(\cdot |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}\left[\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})\right]\,}$

Paso de maximización (paso M) : encuentre los parámetros que maximizan esta cantidad:

${\displaystyle {\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\,}$

Más sucintamente, podemos escribirlo como una ecuación:$${\displaystyle {\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\operatorname {E} _{\mathbf {Z} \sim p(\cdot |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}\left[\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})\right]\,}$$

Los modelos típicos a los que se aplica EM utilizan como variable latente la que indica la pertenencia a uno de un conjunto de grupos:${\displaystyle \mathbf {Z} }$

1. Los puntos de datos observados pueden ser discretos (que toman valores en un conjunto finito o infinito numerable) o continuos (que toman valores en un conjunto infinito numerable). A cada punto de datos puede estar asociado un vector de observaciones.${\displaystyle \mathbf {X} }$
2. Los valores faltantes (también conocidos como variables latentes ) son discretos , se extraen de un número fijo de valores y con una variable latente por unidad observada.${\displaystyle \mathbf {Z} }$
3. Los parámetros son continuos y son de dos tipos: parámetros que están asociados con todos los puntos de datos y aquellos asociados con un valor específico de una variable latente (es decir, asociados con todos los puntos de datos cuya variable latente correspondiente tiene ese valor).

Sin embargo, es posible aplicar EM a otros tipos de modelos.

La motivación es la siguiente. Si se conoce el valor de los parámetros, normalmente el valor de las variables latentes se puede encontrar maximizando la verosimilitud logarítmica sobre todos los valores posibles de , ya sea simplemente iterando sobre o mediante un algoritmo como el algoritmo de Viterbi para modelos ocultos de Markov . Por el contrario, si conocemos el valor de las variables latentes , podemos encontrar una estimación de los parámetros con bastante facilidad, normalmente simplemente agrupando los puntos de datos observados según el valor de la variable latente asociada y promediando los valores, o alguna función de los valores, de los puntos de cada grupo. Esto sugiere un algoritmo iterativo, en el caso en que tanto y sean desconocidos:${\displaystyle {\boldsymbol {\theta }}}$${\displaystyle \mathbf {Z} }$${\displaystyle \mathbf {Z} }$${\displaystyle \mathbf {Z} }$${\displaystyle \mathbf {Z} }$${\displaystyle {\boldsymbol {\theta }}}$${\displaystyle {\boldsymbol {\theta }}}$${\displaystyle \mathbf {Z} }$

1. Primero, inicialice los parámetros con algunos valores aleatorios.${\displaystyle {\boldsymbol {\theta }}}$
2. Calcular la probabilidad de cada valor posible de , dado .${\displaystyle \mathbf {Z} }$${\displaystyle {\boldsymbol {\theta }}}$
3. Luego, utilice los valores recién calculados de para calcular una mejor estimación para los parámetros .${\displaystyle \mathbf {Z} }$${\displaystyle {\boldsymbol {\theta }}}$
4. Iterar los pasos 2 y 3 hasta la convergencia.

El algoritmo tal como se acaba de describir se aproxima monótonamente a un mínimo local de la función de costo.

Aunque una iteración EM sí 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. Existe una variedad de enfoques heurísticos o metaheurísticos para escapar de un máximo local, como la escalada de colinas con reinicio aleatorio (comenzando con varias estimaciones iniciales aleatorias diferentes ) o la aplicación de métodos de recocido simulado .${\displaystyle {\boldsymbol {\theta }}^{(t)}}$

EM es especialmente útil cuando la probabilidad es una familia exponencial , véase Sundberg (2019, cap. 8) para un tratamiento integral: ^[17] el paso E se convierte en la suma de expectativas de estadísticas suficientes , y el paso M implica maximizar una función lineal. En tal caso, normalmente es posible derivar actualizaciones de expresiones de forma cerrada para cada paso, utilizando la fórmula de Sundberg ^[18] (probada 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]}

El método EM fue modificado para calcular estimaciones máximas a posteriori (MAP) para la inferencia bayesiana en el artículo original de Dempster, Laird y Rubin.

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 EM, estos métodos suelen requerir la evaluación de la primera y/o segunda derivada de la función de verosimilitud.

La maximización de expectativas funciona para mejorar en lugar de mejorar directamente . Aquí se muestra que las mejoras en la primera implican mejoras en la segunda. ^{[19] [20]}${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}$

Para cualquier con probabilidad distinta de cero , podemos escribir${\displaystyle \mathbf {Z} }$${\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})}$

${\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 }}).}$

Calculamos la expectativa sobre los posibles valores de los datos desconocidos según la estimación del parámetro actual multiplicando ambos lados por y sumando (o integrando) sobre . El lado izquierdo es la expectativa de una constante, por lo que obtenemos:${\displaystyle \mathbf {Z} }$${\displaystyle \theta ^{(t)}}$${\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}$${\displaystyle \mathbf {Z} }$

${\displaystyle {\begin{aligned}\log p(\mathbf {X} \mid {\boldsymbol {\theta }})&=\sum _{\mathbf {Z} }p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\sum _{\mathbf {Z} }p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\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}}}$

donde se define por la suma negada que reemplaza. Esta última ecuación es válida para cada valor de, incluido ,${\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$${\displaystyle {\boldsymbol {\theta }}}$${\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 nos da

${\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 , por lo que podemos concluir que${\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})}$

${\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 mejorar provoca que mejoremos al menos tanto como antes.${\displaystyle {\boldsymbol {\theta }}}$${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}$

El algoritmo EM puede verse como dos pasos de maximización alternos, es decir, como un ejemplo de descenso de coordenadas . ^{[21] [22]} 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),}$

donde es la distribución condicional de los datos no observados dados los datos observados y es la divergencia de Kullback-Leibler .${\displaystyle p_{Z\mid X}(\cdot \mid x;\theta )}$${\displaystyle x}$${\displaystyle D_{KL}}$

Entonces los pasos del algoritmo EM pueden verse como:

Paso de expectativa : Elija maximizar :${\displaystyle q}$${\displaystyle F}$

${\displaystyle q^{(t)}=\operatorname {arg\,max} _{q}\ F(q,\theta ^{(t)})}$

Paso de maximización : Elija maximizar :${\displaystyle \theta }$${\displaystyle F}$

${\displaystyle \theta ^{(t+1)}=\operatorname {arg\,max} _{\theta }\ F(q^{(t)},\theta )}$

• EM se utiliza con frecuencia para la estimación de parámetros de modelos mixtos , ^{[23] [24]} especialmente en genética cuantitativa . ^[25]
• En psicometría , la EM es una herramienta importante para estimar los parámetros de los ítems y las capacidades latentes de los modelos de teoría de respuesta a los ítems .
• Con la capacidad de manejar datos faltantes y observar variables no identificadas, EM se está convirtiendo en una herramienta útil para fijar el precio y gestionar el riesgo de una cartera. ^{[ cita requerida ]}
• El algoritmo EM (y su variante más rápida, la maximización de la expectativa de subconjunto ordenado ) 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 por rayos X. Vea a continuación otras variantes más rápidas de EM.
• En ingeniería estructural , el algoritmo de identificación estructural mediante maximización de expectativas (STRIDE) ^[26] es un método de solo salida para identificar las 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 , es decir, el tiempo entre transacciones subsiguientes de acciones en una bolsa de valores, el algoritmo EM ha demostrado ser muy útil. ^[27]

Por lo general, se utiliza un filtro Kalman para la estimación de estado en línea y se puede emplear un suavizador de mínima varianza 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 estado. Los algoritmos EM se pueden utilizar para resolver problemas conjuntos de estimación de estado y parámetros.

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

Paso E

Opere un filtro Kalman o un suavizador de varianza mínima diseñado con 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 Kalman o un suavizador de varianza mínima opera sobre mediciones de un sistema de una sola entrada y una sola salida que posee 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},}$

donde son estimaciones de salida escalar calculadas por un filtro o un suavizador a partir de N mediciones escalares . La actualización anterior también se puede aplicar para actualizar la intensidad del ruido de una medición de Poisson. De manera similar, para un proceso autorregresivo de primer orden, se puede calcular una estimación de varianza del ruido del proceso actualizada mediante${\displaystyle {\widehat {x}}_{k}}$${\displaystyle z_{k}}$

${\displaystyle {\widehat {\sigma }}_{w}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k})}^{2},}$

donde y son estimaciones de estado escalar calculadas mediante un filtro o suavizador. La estimación del coeficiente del modelo actualizado se obtiene mediante${\displaystyle {\widehat {x}}_{k}}$${\displaystyle {\widehat {x}}_{k+1}}$

${\displaystyle {\widehat {F}}={\frac {\sum _{k=1}^{N}{({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k})}^{2}}{\sum _{k=1}^{N}{\widehat {x}}_{k}^{2}}}.}$

La convergencia de estimaciones de parámetros como las anteriores ha sido bien estudiada. ^{[28] [29] [30] [31]}

Se han propuesto varios métodos para acelerar la convergencia a veces lenta del algoritmo EM, como los que utilizan el gradiente conjugado y los métodos de Newton modificados (Newton-Raphson). ^[32] Además, EM se puede utilizar con métodos de estimación restringida.

El algoritmo de maximización de expectativas expandidas por parámetros (PX-EM) a menudo proporciona 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". ^[33]

La maximización condicional de expectativas (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, condicionalmente a que los otros parámetros permanezcan fijos. ^[34] Esto mismo se puede extender al algoritmo de maximización condicional de expectativas (ECME) . ^[35]

Esta idea se amplía aún más en el algoritmo de maximización de expectativas generalizadas (GEM) , en el que se busca únicamente un aumento 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. ^[21] GEM se desarrolla aún más en un entorno distribuido y muestra resultados prometedores. ^[36]

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

La función Q utilizada en el algoritmo EM se basa en la probabilidad logarítmica. Por lo tanto, se considera el algoritmo log-EM. El uso de la probabilidad logarítmica se puede generalizar al de la razón de probabilidad logarítmica α. Entonces, la razón de probabilidad logarítmica α de los datos observados se puede expresar exactamente como igualdad utilizando la función Q de la razón de probabilidad logarítmica α y la divergencia α. Obtener esta función Q es un paso E generalizado. Su maximización es un paso M generalizado. Este par se denomina algoritmo α-EM ^[38] que contiene el algoritmo log-EM como su subclase. Por lo tanto, el algoritmo α-EM de Yasuo Matsuyama es una generalización exacta del algoritmo log-EM. No se necesita ningún cálculo de gradiente o matriz hessiana. El α-EM muestra una convergencia más rápida que el algoritmo log-EM al elegir un α apropiado. El algoritmo α-EM conduce a una versión más rápida del algoritmo de estimación del modelo de Markov oculto α-HMM. ^[39]

EM es un método de máxima verosimilitud parcialmente no bayesiano. Su resultado final da una distribución de probabilidad sobre las variables latentes (en el estilo bayesiano) junto con una estimación puntual para θ (ya sea una estimación de máxima verosimilitud o un modo posterior). Puede ser necesaria una versión completamente bayesiana de esto, que dé una distribución de probabilidad sobre θ y las variables latentes. El enfoque bayesiano para la inferencia es simplemente 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 la vez. 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 la nueva 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.

Sea una muestra de observaciones independientes de una mezcla de dos distribuciones normales multivariadas de dimensión , y sean las variables latentes que determinan el componente del que se origina la observación. ^[22]${\displaystyle \mathbf {x} =(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})}$${\displaystyle n}$${\displaystyle d}$${\displaystyle \mathbf {z} =(z_{1},z_{2},\ldots ,z_{n})}$

${\displaystyle X_{i}\mid (Z_{i}=1)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{1},\Sigma _{1})}$y${\displaystyle X_{i}\mid (Z_{i}=2)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{2},\Sigma _{2}),}$

dónde

${\displaystyle \operatorname {P} (Z_{i}=1)=\tau _{1}\,}$y${\displaystyle \operatorname {P} (Z_{i}=2)=\tau _{2}=1-\tau _{1}.}$

El objetivo es estimar los parámetros desconocidos que representan el valor de mezcla entre las gaussianas y las medias y covarianzas de cada una:

${\displaystyle \theta ={\big (}{\boldsymbol {\tau }},{\boldsymbol {\mu }}_{1},{\boldsymbol {\mu }}_{2},\Sigma _{1},\Sigma _{2}{\big )},}$

donde la función de verosimilitud de datos incompletos es

${\displaystyle L(\theta ;\mathbf {x} )=\prod _{i=1}^{n}\sum _{j=1}^{2}\tau _{j}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j}),}$

y la función de verosimilitud de datos completos es

${\displaystyle L(\theta ;\mathbf {x} ,\mathbf {z} )=p(\mathbf {x} ,\mathbf {z} \mid \theta )=\prod _{i=1}^{n}\prod _{j=1}^{2}\ [f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})\tau _{j}]^{\mathbb {I} (z_{i}=j)},}$

o

${\displaystyle L(\theta ;\mathbf {x} ,\mathbf {z} )=\exp \left\{\sum _{i=1}^{n}\sum _{j=1}^{2}\mathbb {I} (z_{i}=j){\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}\right\},}$

donde es una función indicadora y es la función de densidad de probabilidad de una normal multivariada.${\displaystyle \mathbb {I} }$${\displaystyle f}$

En la última igualdad, para cada i , un indicador es igual a cero y otro indicador es igual a uno. La suma interna se reduce entonces a un término.${\displaystyle \mathbb {I} (z_{i}=j)}$

Dada nuestra estimación actual de los parámetros θ ^{( t )} , la distribución condicional de Z _i está determinada por el teorema de Bayes como la altura proporcional de la densidad normal ponderada por τ :

${\displaystyle T_{j,i}^{(t)}:=\operatorname {P} (Z_{i}=j\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})={\frac {\tau _{j}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j}^{(t)},\Sigma _{j}^{(t)})}{\tau _{1}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{1}^{(t)},\Sigma _{1}^{(t)})+\tau _{2}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{2}^{(t)},\Sigma _{2}^{(t)})}}.}$

Estas se denominan "probabilidades de pertenencia", que normalmente se consideran el resultado del paso E (aunque esta no es la función Q que se muestra a continuación).

Este paso E corresponde con la configuración de esta función para Q:

${\displaystyle {\begin{aligned}Q(\theta \mid \theta ^{(t)})&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} =\mathbf {x} ;\mathbf {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} ,\mathbf {Z} )]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} =\mathbf {x} ;\mathbf {\theta } ^{(t)}}[\log \prod _{i=1}^{n}L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} =\mathbf {x} ;\mathbf {\theta } ^{(t)}}[\sum _{i=1}^{n}\log L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\sum _{i=1}^{n}\operatorname {E} _{Z_{i}\mid X_{i}=x_{i};\mathbf {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}P(Z_{i}=j\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})\log L(\theta _{j};\mathbf {x} _{i},j)\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}T_{j,i}^{(t)}{\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}.\end{aligned}}}$

La expectativa de dentro de la suma se toma con respecto a la función de densidad de probabilidad , que puede ser diferente para cada uno de los conjuntos de entrenamiento. Todo en el paso E se conoce antes de que se realice el paso, excepto , que se calcula de acuerdo con la ecuación al comienzo de la sección del paso E.${\displaystyle \log L(\theta ;\mathbf {x} _{i},Z_{i})}$${\displaystyle P(Z_{i}\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})}$${\displaystyle \mathbf {x} _{i}}$${\displaystyle T_{j,i}}$

No es necesario calcular esta expectativa condicional completa en un solo paso, porque τ y μ / Σ aparecen en términos lineales separados y, por lo tanto, pueden maximizarse independientemente.

${\displaystyle Q(\theta \mid \theta ^{(t)})}$Al tener forma cuadrática, es relativamente sencillo determinar los valores maximizadores de. Además, , y pueden maximizarse independientemente, ya que todos aparecen en términos lineales separados.${\displaystyle \theta }$${\displaystyle \tau }$${\displaystyle ({\boldsymbol {\mu }}_{1},\Sigma _{1})}$${\displaystyle ({\boldsymbol {\mu }}_{2},\Sigma _{2})}$

Para comenzar, considere , que tiene la restricción :${\displaystyle \tau }$${\displaystyle \tau _{1}+\tau _{2}=1}$

${\displaystyle {\begin{aligned}{\boldsymbol {\tau }}^{(t+1)}&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ Q(\theta \mid \theta ^{(t)})\\&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ \left\{\left[\sum _{i=1}^{n}T_{1,i}^{(t)}\right]\log \tau _{1}+\left[\sum _{i=1}^{n}T_{2,i}^{(t)}\right]\log \tau _{2}\right\}.\end{aligned}}}$

Esto tiene la misma forma que la estimación de máxima verosimilitud para la distribución binomial , por lo que

${\displaystyle \tau _{j}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{j,i}^{(t)}}{\sum _{i=1}^{n}(T_{1,i}^{(t)}+T_{2,i}^{(t)})}}={\frac {1}{n}}\sum _{i=1}^{n}T_{j,i}^{(t)}.}$

Para las próximas estimaciones de :${\displaystyle ({\boldsymbol {\mu }}_{1},\Sigma _{1})}$

${\displaystyle {\begin{aligned}({\boldsymbol {\mu }}_{1}^{(t+1)},\Sigma _{1}^{(t+1)})&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}\ Q(\theta \mid \theta ^{(t)})\\&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}\ \sum _{i=1}^{n}T_{1,i}^{(t)}\left\{-{\tfrac {1}{2}}\log |\Sigma _{1}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})^{\top }\Sigma _{1}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})\right\}\end{aligned}}.}$

Esto tiene la misma forma que una estimación de máxima verosimilitud ponderada para una distribución normal, por lo que

${\displaystyle {\boldsymbol {\mu }}_{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}}$y${\displaystyle \Sigma _{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}}$

y, por simetría,

${\displaystyle {\boldsymbol {\mu }}_{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}}$y${\displaystyle \Sigma _{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}.}$

Concluya el proceso iterativo si está por debajo de un umbral preestablecido.${\displaystyle E_{Z\mid \theta ^{(t)},\mathbf {x} }[\log L(\theta ^{(t)};\mathbf {x} ,\mathbf {Z} )]\leq E_{Z\mid \theta ^{(t-1)},\mathbf {x} }[\log L(\theta ^{(t-1)};\mathbf {x} ,\mathbf {Z} )]+\varepsilon }$${\displaystyle \varepsilon }$

El algoritmo ilustrado arriba se puede generalizar para mezclas de más de dos distribuciones normales multivariadas .

El algoritmo EM se ha implementado en el caso en que existe un modelo de regresión lineal subyacente que explica la variación de alguna cantidad, pero donde los valores realmente observados son versiones censuradas o truncadas de los representados en el modelo. ^[40] Los casos especiales de este modelo incluyen observaciones censuradas o truncadas de una distribución normal . ^[40]

El EM converge típicamente a un óptimo local, no necesariamente al óptimo global, sin límite en la tasa de convergencia en general. Es posible que pueda ser arbitrariamente pobre en dimensiones altas y puede haber un número exponencial de óptimos locales. Por lo tanto, existe una necesidad de métodos alternativos para el aprendizaje garantizado, especialmente en el entorno de alta dimensión. Existen alternativas al EM con mejores garantías de consistencia, que se denominan enfoques basados ​​en momentos ^[41] o las llamadas técnicas espectrales . ^{[42] [43]} Los enfoques basados ​​en momentos para aprender los parámetros de un modelo probabilístico disfrutan de garantías como la convergencia global bajo ciertas condiciones a diferencia del EM que a menudo está plagado por el problema de quedarse atascado en óptimos locales. Se pueden derivar algoritmos con garantías de aprendizaje para una serie de modelos importantes, como modelos de mezcla, HMM, etc. Para estos métodos espectrales, no ocurren óptimos locales espurios y los parámetros verdaderos se pueden estimar de manera consistente bajo algunas condiciones de regularidad. ^{[ cita requerida ]}

• distribución de 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-mayorización (MM) . ^[44]

• Hogg, Robert; McKean, Joseph; Craig, Allen (2005). Introducción a la estadística matemática . Upper Saddle River, NJ: Pearson Prentice Hall. págs. 359–364.
• Dellaert, Frank (febrero de 2002). El algoritmo de maximización de expectativas (PDF) (número de informe técnico GIT-GVU-02-20). Facultad de Informática de Georgia Tech.da una explicación más sencilla del algoritmo EM en cuanto 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 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 sobre el 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 mezclas gaussianas.
• McLachlan, Geoffrey J.; Krishnan, Thriyambakam (2008). El algoritmo EM y extensiones (2.ª ed.). Hoboken: Wiley. ISBN 978-0-471-20170-0.

• Se ofrecen diversas demostraciones en 1D, 2D y 3D de EM junto con el modelado de mezclas como parte de las actividades y aplicaciones SOCR emparejadas . Estas aplicaciones 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) incluidas las 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 simples del algoritmo EM, como la agrupación mediante el algoritmo k -medias suave, y enfatiza la visión variacional del algoritmo EM, como se describe en el Capítulo 33.7 de la versión 7.2 (cuarta edición).
• Algoritmos variacionales para inferencia bayesiana aproximada, por 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 expectativas: un breve tutorial, una derivación autónoma del algoritmo EM por Sean Borman.
• El algoritmo EM, de Xiaojin Zhu.
• Algoritmo EM y variantes: un tutorial informal de Alexis Roche. Una descripción concisa y muy clara del EM y muchas variantes interesantes.