Algoritmo de expectativa-maximización - Expectation–maximization algorithm

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 . La iteración EM alterna entre realizar un paso de expectativa (E), que crea una función para la expectativa de la probabilidad logarítmica evaluada utilizando la estimación actual para los parámetros, y un paso de maximización (M), que calcula los parámetros que maximizan el logaritmo esperado. probabilidad 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.

Agrupación EM de datos de erupciones Old Faithful . El modelo inicial aleatorio (que, debido a las diferentes escalas de los ejes, parece ser dos esferas muy planas y anchas) se ajusta a los datos observados. En las primeras iteraciones, el modelo cambia sustancialmente, pero luego converge a los dos modos del géiser . Visualizado usando ELKI .

Historia

El algoritmo EM se explicó y se le dio su nombre en un artículo clásico de 1977 de Arthur Dempster , Nan Laird y Donald Rubin . 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 recuento de genes para estimar las frecuencias alélicas de Cedric Smith . Rolf Sundberg publicó un tratamiento muy detallado del método EM para familias exponenciales en su tesis y varios artículos tras su colaboración con Per Martin-Löf y Anders Martin-Löf . 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.

El análisis de convergencia del algoritmo Dempster-Laird-Rubin fue defectuoso y CF Jeff Wu publicó un análisis de convergencia correcto en 1983. La prueba de Wu estableció la convergencia del método EM fuera de la familia exponencial , como afirma Dempster-Laird-Rubin.

Introducción

El algoritmo EM se utiliza para encontrar parámetros de máxima verosimilitud (local) de un modelo estadístico en los casos en que las ecuaciones no se pueden resolver directamente. Por lo general, estos modelos involucran variables latentes además de parámetros desconocidos y observaciones de datos conocidos. Es decir, o existen valores perdidos entre los datos o el modelo se puede formular de manera más simple asumiendo la existencia de puntos de datos adicionales no observados. Por ejemplo, un modelo de mezcla se puede describir de manera más simple asumiendo que cada punto de datos observado tiene un punto de datos no observado correspondiente, o variable latente, especificando el componente de mezcla al que pertenece cada punto de datos.

Encontrar una solución de máxima verosimilitud normalmente requiere 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 modelos estadísticos con variables latentes, esto suele ser imposible. En cambio, el resultado es típicamente 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 por el otro produce una ecuación sin solución.

El algoritmo EM procede de la observación de que existe una manera de resolver estos dos conjuntos de ecuaciones numéricamente. Uno puede simplemente 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 sean ambos. convergen en puntos fijos. No es obvio que esto funcione, pero se puede probar en este contexto. Además, se puede probar 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 silla . En general, pueden ocurrir 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 puede encontrar EM en un modelo mixto implica establecer uno de los componentes para que tenga varianza cero y el parámetro medio para el mismo componente sea igual a uno de los puntos de datos.

Descripción

Dado el modelo estadístico que genera un conjunto de datos observados, un conjunto de datos latentes no observados o valores perdidos , 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 probabilidad marginal de los datos observados

Sin embargo, esta cantidad es a menudo intratable ya que no se observa y se desconoce la distribución de antes de alcanzarla .

El algoritmo EM busca encontrar el MLE de la probabilidad marginal aplicando iterativamente estos dos pasos:

Paso de expectativa (paso E) : Defina como el valor esperado de la función logarítmica de verosimilitud de , con respecto a la distribución condicional actual de los estimados dados y actuales de los parámetros :
Paso de maximización (paso M) : encuentre los parámetros que maximizan esta cantidad:

Los modelos típicos a los que se aplica EM se utilizan como una variable latente que indica la pertenencia a uno de un conjunto de grupos:

  1. Los puntos de datos observados pueden ser discretos (tomando valores en un conjunto finito o infinito numerable) o continuos (tomando valores en un conjunto infinito incontable). Asociado con cada punto de datos puede haber un vector de observaciones.
  2. Los valores perdidos (también conocidos como variables latentes ) son discretos , extraídos de un número fijo de valores y con una variable latente por unidad observada.
  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 correspondiente variable latente 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 , generalmente el valor de las variables latentes se puede encontrar maximizando la probabilidad logarítmica sobre todos los valores posibles de , ya sea simplemente iterando sobre oa través de un algoritmo como el algoritmo de Baum-Welch para Markov oculto modelos . Por el contrario, si conocemos el valor de las variables latentes , podemos encontrar una estimación de los parámetros con bastante facilidad, por lo general 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 la variable latente. valores, de los puntos en cada grupo. Esto sugiere un algoritmo iterativo, en el caso de que ambos y sean desconocidos:

  1. Primero, inicialice los parámetros a algunos valores aleatorios.
  2. Calcule la probabilidad de cada valor posible de dado .
  3. Luego, use los valores recién calculados de para calcular una mejor estimación de los parámetros .
  4. Repita los pasos 2 y 3 hasta la convergencia.

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

Propiedades

Hablar de un paso de expectativa (E) es un nombre poco apropiado . Lo que se calculan en el primer paso son los parámetros fijos, los datos que dependen de la función Q . Una vez que se conocen los parámetros de Q , se determina completamente y se maximiza en el segundo paso (M) de un algoritmo EM.

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 probabilidad de 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 θ ( t ) ) o la aplicación de métodos de recocido simulados .

EM es especialmente útil cuando la probabilidad es una familia exponencial : el paso E se convierte en la suma de las expectativas de estadísticas suficientes y el paso M implica maximizar una función lineal. En tal caso, generalmente es posible derivar actualizaciones de expresión de forma cerrada para cada paso, usando la fórmula de Sundberg (publicada por Rolf Sundberg usando resultados no publicados de Per Martin-Löf y Anders Martin-Löf ).

El método EM se modificó 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 encontrar las estimaciones de máxima verosimilitud, como el descenso de gradiente , gradiente conjugado , o variantes del algoritmo de Gauss-Newton . A diferencia de EM, estos métodos normalmente requieren la evaluación de la primera y / o la segunda derivada de la función de verosimilitud.

Prueba de corrección

La maximización de expectativas trabaja para mejorar en lugar de mejorar directamente . Aquí se muestra que las mejoras a las primeras implican mejoras a las segundas.

Para cualquiera con probabilidad distinta de cero , podemos escribir

Tomamos la expectativa sobre los posibles valores de los datos desconocidos bajo la estimación del parámetro actual multiplicando ambos lados por y sumando (o integrando) . El lado izquierdo es la expectativa de una constante, por lo que obtenemos:

donde se define por la suma negada que está reemplazando. Esta última ecuación es válida para cada valor de incluir ,

y restar esta última ecuación de la ecuación anterior da

Sin embargo, la desigualdad de Gibbs nos dice eso , por lo que podemos concluir que

En palabras, elegir mejorar causa mejorar al menos tanto.

Como procedimiento de maximización-maximización

El algoritmo EM puede verse como dos pasos de maximización alternos, es decir, como un ejemplo de descenso de coordenadas . Considere la función:

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

donde es la distribución condicional de los datos no observados dados los datos observados y es la divergencia Kullback-Leibler .

Entonces, los pasos en el algoritmo EM pueden verse como:

Paso de expectativa : elija maximizar :
Paso de maximización : elija maximizar :

Aplicaciones

EM se utiliza con frecuencia para la estimación de parámetros de modelos mixtos , especialmente en genética cuantitativa .

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 lidiar con datos faltantes y observar variables no identificadas, EM se está convirtiendo en una herramienta útil para valorar y administrar el riesgo de una cartera.

El algoritmo EM (y su variante más rápido ordenó expectativa de maximización subconjunto ) también se usa ampliamente en imagen médica reconstrucción, sobre todo en la tomografía por emisión de positrones , tomografía computarizada por emisión de fotón único , y de rayos X de tomografía computarizada . Consulte a continuación otras variantes más rápidas de EM.

En ingeniería estructural , el algoritmo de identificación estructural mediante la maximización de expectativas (STRIDE) es un método de salida solo para identificar las propiedades de vibración natural de un sistema estructural utilizando datos de sensores (consulte Análisis modal operativo ).

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 de Baum-Welch para modelos de Markov ocultos y el algoritmo de adentro hacia afuera para la inducción no supervisada de gramáticas probabilísticas libres de contexto .

Algoritmos EM de filtrado y suavizado

Un filtro de Kalman se usa típicamente para la estimación del estado en línea y se puede emplear un suavizador de varianza mínima para la estimación del estado fuera de línea o por lotes. Sin embargo, estas soluciones de varianza mínima requieren estimaciones de los parámetros del modelo de espacio de estado. Los algoritmos EM se pueden utilizar para resolver problemas de estimación de parámetros y estados conjuntos.

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

E-paso
Utilice un filtro de 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.

Suponga que un filtro de Kalman o un suavizador de varianza mínima opera en las mediciones de un sistema de entrada única y salida única 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

donde se calculan las estimaciones de salida escalares mediante un filtro o un suavizador a partir de N medidas 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 autoregresivo de primer orden, se puede calcular una estimación actualizada de la varianza del ruido del proceso mediante

donde y son estimaciones de estado escalar calculadas por un filtro o un suavizador. La estimación del coeficiente del modelo actualizado se obtiene a través de

La convergencia de estimaciones de parámetros como las anteriores está bien estudiada.

Variantes

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). Además, EM se puede utilizar con métodos de estimación restringidos.

El algoritmo de maximización de expectativas de parámetros expandidos (PX-EM) a menudo proporciona una aceleración al "usar un 'ajuste de covarianza' para corregir el análisis del paso M, capitalizando la información adicional capturada en los datos completos imputados".

La maximización condicional de expectativa (ECM) reemplaza cada paso M con una secuencia de pasos de maximización condicional (CM) en la que cada parámetro θ i se maximiza individualmente, condicionalmente en los otros parámetros que permanecen fijos. En sí mismo se puede extender al algoritmo de maximización condicional de expectativa (ECME) .

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

También es posible considerar el algoritmo EM como una subclase del algoritmo MM (Majorize / Minimize o Minorize / Maximize, según el contexto), y por lo tanto utilizar cualquier maquinaria desarrollada en el caso más general.

algoritmo α-EM

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 llama algoritmo α-EM 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 Hidden Markov α-HMM.

Relación con los métodos de Bayes variacionales

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). Se puede desear una versión completamente bayesiana de esto, dando una distribución de probabilidad sobre θ y las variables latentes. El enfoque bayesiano de 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 utiliza la aproximación Q factorizada como se describe anteriormente ( Bayes variacional ), la resolución puede iterar sobre cada variable latente (ahora incluye θ ) 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 manto de Markov , por lo que el paso de mensajes locales se puede usar para una inferencia eficiente.

Interpretación geométrica

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 Kullback-Leibler también puede entenderse en estos términos.

Ejemplos de

Mezcla gaussiana

Comparación de k-medias y EM en datos artificiales visualizados con ELKI . Usando las varianzas, el algoritmo EM puede describir las distribuciones normales exactamente, mientras que k-means divide los datos en las celdas de Voronoi . El centro del grupo está indicado por el símbolo más grande y más claro.
Una animación que demuestra el algoritmo EM que ajusta un modelo de mezcla gaussiana de dos componentes al conjunto de datos Old Faithful . El algoritmo pasa de una inicialización aleatoria a la convergencia.

Sea una muestra de observaciones independientes de una mezcla de dos distribuciones normales multivariadas de dimensión , y sean las variables latentes las que determinan el componente a partir del cual se origina la observación.

y

dónde

y

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

donde la función de probabilidad de datos incompletos es

y la función de verosimilitud de datos completos es

o

donde es una función indicadora y es la función de densidad de probabilidad de una normal multivariante.

En la última igualdad, para cada i , un indicador es igual a cero y un indicador es igual a uno. La suma interna se reduce así a un término.

E paso

Dada nuestra estimación actual de los parámetros θ ( t ) , el teorema de Bayes determina que la distribución condicional de Z i es la altura proporcional de la densidad normal ponderada por τ :

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

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

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 conjunto de entrenamiento. Todo en el paso E se conoce antes de dar el paso excepto , que se calcula de acuerdo con la ecuación al comienzo de la sección del paso E.

Esta expectativa condicional completa no necesita calcularse en un solo paso, porque τ y μ / Σ aparecen en términos lineales separados y, por lo tanto, se pueden maximizar de forma independiente.

Paso M

Q ( θ  |  θ ( t ) ) siendo cuadrático en forma significa que determinar los valores maximizadores de θ es relativamente sencillo. Además, τ , ( μ 1 , Σ 1 ) y ( μ 2 , Σ 2 ) se pueden maximizar de forma independiente, ya que todos aparecen en términos lineales separados.

Para comenzar, considere τ , que tiene la restricción τ 1 + τ 2 = 1:

Esto tiene la misma forma que el MLE para la distribución binomial , por lo que

Para las próximas estimaciones de ( μ 1 , Σ 1 ):

Tiene la misma forma que una MLE ponderada para una distribución normal, por lo que

y

y, por simetría,

y

Terminación

Concluya el proceso iterativo si está por debajo de algún umbral preestablecido.

Generalización

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

Regresión truncada y censurada

El algoritmo EM se ha implementado en el caso donde 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. Los casos especiales de este modelo incluyen observaciones censuradas o truncadas de una distribución normal .

Alternativas

Los ME convergen típicamente a un óptimo local, no necesariamente al óptimo global, sin límite en la tasa de convergencia en general. Es posible que sea arbitrariamente pobre en grandes dimensiones y puede haber un número exponencial de óptimos locales. Por tanto, existe la necesidad de métodos alternativos para el aprendizaje garantizado, especialmente en entornos de alta dimensión. Existen alternativas a la EM con mejores garantías de coherencia, que se denominan enfoques basados ​​en momentos o las denominadas técnicas espectrales . Los enfoques basados ​​en momentos para aprender los parámetros de un modelo probabilístico son de creciente interés recientemente, ya que disfrutan de garantías como la convergencia global en ciertas condiciones, a diferencia de la EM, que a menudo se ve afectada por el problema de quedarse atascado en los ó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 coherente en algunas condiciones de regularidad.

Ver también

Referencias

Otras lecturas

  • Hogg, Robert; McKean, Joseph; Craig, Allen (2005). Introducción a la estadística matemática . Upper Saddle River, Nueva Jersey: Pearson Prentice Hall. págs. 359–364.
  • Dellaert, Frank (2002). "El algoritmo de maximización de expectativas". CiteSeerX  10.1.1.9.9735 . Cite journal requiere |journal=( ayuda ) ofrece una explicación más sencilla del algoritmo EM en cuanto a la maximización del límite inferior.
  • Obispo, Christopher M. (2006). Reconocimiento de patrones y aprendizaje automático . Saltador. 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 bien escrito sobre EM, que incluye una derivación detallada de EM para GMM, HMM y Dirichlet.
  • Bilmes, Jeff (1998). "Un suave tutorial del algoritmo EM y su aplicación a la estimación de parámetros para la mezcla gaussiana y modelos de Markov ocultos". CiteSeerX  10.1.1.28.613 . Cite journal requiere |journal=( ayuda ) incluye una derivación simplificada de las ecuaciones EM para mezclas gaussianas y modelos de Markov ocultos 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.

enlaces externos