En el enfoque del algoritmo EM, utilizamos la desigualdad de Jensen para llegar a
y defina por
Todo lo que leo EM simplemente lo deja caer, pero siempre me he sentido incómodo al no tener una explicación de por qué el algoritmo EM surge de forma natural. Entiendo que la probabilidad de generalmente se trata para lidiar con la suma en lugar de la multiplicación, pero la aparición de en la definición de parece desmotivada. ¿Por qué debería uno considerar y no otras funciones monótonas? Por varias razones, sospecho que el "significado" o la "motivación" detrás de la maximización de las expectativas tiene algún tipo de explicación en términos de teoría de la información y estadísticas suficientes. Si hubiera tal explicación, eso sería mucho más satisfactorio que un simple algoritmo abstracto.
fuente
Respuestas:
El algoritmo EM tiene diferentes interpretaciones y puede surgir en diferentes formas en diferentes aplicaciones.
Todo comienza con la función de probabilidad , o de manera equivalente, la función de probabilidad de nos gustaría maximizar. (Generalmente usamos logaritmo ya que simplifica el cálculo: es estrictamente monótono, cóncavo y .) En un mundo ideal, el valor de depende solo del parámetro del modelo , para que podamos buscar a través del espacio de y encontrar uno que maximice .log p ( x | θ ) log ( a b ) = log a + log b p θ θ pp ( x | θ ) Iniciar sesiónp ( x | θ ) Iniciar sesión( a b ) = loga + logsi pags θ θ pags
Sin embargo, en muchas aplicaciones interesantes del mundo real, las cosas son más complicadas porque no se observan todas las variables. Sí, podríamos observar directamente , pero algunas otras variables no son observadas. Debido a las variables que faltan , estamos en una especie de situación de gallina y huevo: sin no podemos estimar el parámetro y sin no podemos inferir cuál puede ser el valor de .z z z θ θ zX z z z θ θ z
Es donde entra en juego el algoritmo EM. Comenzamos con una suposición inicial de los parámetros del modelo y derivamos los valores esperados de las variables que faltan (es decir, el paso E). Cuando tenemos los valores de , podemos maximizar la probabilidad de wrt los parámetros (es decir, el paso M, correspondiente a la ecuación en la declaración del problema). Con this podemos derivar los nuevos valores esperados de (otro paso E), y así sucesivamente. En otras palabras, en cada paso asumimos uno de los dos, yz z θ arg max θ z z θθ z z θ argmax θ z z θ , es conocida. Repetimos este proceso iterativo hasta que ya no se pueda aumentar la probabilidad.
Este es el algoritmo EM en pocas palabras. Es bien sabido que la probabilidad nunca disminuirá durante este proceso iterativo de EM. Pero tenga en cuenta que el algoritmo EM no garantiza un óptimo global. Es decir, podría terminar con un óptimo local de la función de probabilidad.
La aparición de en la ecuación de es inevitable, porque aquí la función que desea maximizar se escribe como una probabilidad logarítmica.θ ( k + 1 )Iniciar sesión θ( k + 1 )
fuente
Probabilidad versus probabilidad logarítmica
Como ya se ha dicho, el se introduce con la máxima probabilidad simplemente porque generalmente es más fácil optimizar sumas que los productos. La razón por la que no consideramos otras funciones monótonas es que el logaritmo es la función única con la propiedad de convertir productos en sumas.Iniciar sesión
Otra forma de motivar el logaritmo es la siguiente: en lugar de maximizar la probabilidad de los datos según nuestro modelo, podríamos tratar de minimizar la divergencia de Kullback-Leibler entre la distribución de datos, y distribución del modelo, ,p ( x ∣ θ )pagsdatos( x ) p ( x ∣ θ )
El primer término en el lado derecho es constante en los parámetros. Si tenemos muestras de la distribución de datos (nuestros puntos de datos), podemos aproximar el segundo término con la probabilidad de registro promedio de los datos,norte
Una vista alternativa de EM
No estoy seguro de que este sea el tipo de explicación que está buscando, pero la siguiente visión de la maximización de expectativas es mucho más esclarecedora que su motivación a través de la desigualdad de Jensen (puede encontrar una descripción detallada en Neal y Hinton (1998) o en el libro PRML de Chris Bishop, Capítulo 9.3).
No es difícil demostrar que
para cualquier . Si llamamos al primer término en el lado derecho , esto implica queF ( q , θ )q(z∣x) F(q,θ)
Debido a que la divergencia KL es siempre positiva , es un límite inferior en la probabilidad logarítmica de cada fijo . Ahora, EM puede verse como maximizando alternativamente con respecto a y . En particular, mediante el establecimiento de en el E-paso, se minimiza la divergencia KL en el lado derecho y así maximizar .q F q θ q ( z ∣ x ) = p ( z ∣ x , θ ) FF(q,θ) q F q θ q(z∣x)=p(z∣ x ,θ) F
fuente
El artículo que encontré aclarando con respecto a la maximización de expectativas es Bayesian K-Means como un algoritmo de " maximización -expectativa" (pdf) por Welling y Kurihara.
Supongamos que tenemos un modelo probabilístico con observaciones, variables aleatorias ocultas y un total de parámetros . Se nos da un conjunto de datos y estamos obligados (por poderes superiores) a establecer .x z θ D p ( z , θ | D )p ( x , z, θ ) X z θ re p ( z, θ | D )
1. muestreo de Gibbs
Podemos aproximar por muestreo. El muestreo de Gibbs da alternando:p ( z , θ | D )p ( z, θ | D ) p ( z, θ | D )
2. Bayes variacionales
En cambio, podemos intentar establecer una distribución y y minimizar la diferencia con la distribución que buscamos después de . La diferencia entre las distribuciones tiene un nombre elegante y conveniente, la divergencia KL. Para minimizar actualizamos:q ( z ) p ( θ , z | D ) K L [ q ( θ ) q ( z ) | El | p ( θ , z | D ) ]q( θ ) q( z) p ( θ , zEl | D) KL [q( θ )q(z) | El | p ( θ , zEl | D)]
3. Expectativa-Maximización
Proponer distribuciones de probabilidad completas para y podría considerarse extremo. ¿Por qué no consideramos una estimación puntual para uno de estos y mantenemos el otro agradable y matizado? En EM, el parámetro se establece como el que no merece una distribución completa, y se establece en su valor MAP (Maximum A Posteriori), .θ θ θ ∗z θ θ θ∗
Aquí realidad sería una mejor notación: el operador argmax puede devolver múltiples valores. Pero no peleemos. En comparación con Bayes variacionales, ve que la corrección para by no cambia el resultado, por lo que ya no es necesario.log expθ∗∈ argmax Iniciar sesión Exp
4. Maximización-Expectativa
No hay razón para tratar a como un niño mimado. También podemos usar estimaciones puntuales para nuestras variables ocultas y dar a los parámetros el lujo de una distribución completa.z ∗ θz z∗ θ
Si nuestras variables ocultas son variables indicadoras, de repente tenemos un método computacionalmente barato para realizar inferencia sobre el número de grupos. En otras palabras: selección de modelo (o detección automática de relevancia o imagina otro nombre elegante).z
5. Modos condicionales iterados
Por supuesto, el elemento secundario de la inferencia aproximada es usar estimaciones puntuales tanto para los parámetros como para las observaciones .zθ z
Para ver cómo se desarrolla Maximización-Expectativa, recomiendo el artículo. En mi opinión, la fuerza de este artículo no es, sin embargo, la aplicación a una alternativa significa, sino esta exposición lúcida y concisa de aproximación.k
fuente
Existe una técnica útil de optimización subyacente al algoritmo EM. Sin embargo, generalmente se expresa en el lenguaje de la teoría de la probabilidad, por lo que es difícil ver que en el fondo hay un método que no tiene nada que ver con la probabilidad y la expectativa.
Considere el problema de maximizar (o equivalentemente ) con respecto a . Si escribe una expresión para y la establece igual a cero, a menudo terminará con una ecuación trascendental para resolver. Estos pueden ser desagradables.log g ( x ) x g ′ ( x )
Ahora suponga que juega bien juntos en el sentido de que las combinaciones lineales de ellos le dan algo fácil de optimizar. Por ejemplo, si todos los son cuadráticos en entonces una combinación lineal de también será cuadrática y, por lo tanto, fácil de optimizar.f i ( x ) x f i ( x )fi fi(x) x fi(x)
Dado este supuesto, sería genial si, para optimizar pudiéramos barajar el allá del para que pudiera cumplir con el s y eliminarlos. Entonces el podría jugar juntos. Pero no podemos hacer eso.log ∑ exp f ilogg(x)=log∑iexp(fi(x)) log ∑ exp fi
Hagamos la siguiente mejor cosa. Haremos otra función que sea similar a . Y lo haremos con combinaciones lineales de .g f ih g fi
Digamos que es una suposición para un valor óptimo. Nos gustaría mejorar esto. Busquemos otra función que coincida con su derivada en , es decir, y . Si trazas una gráfica de en un vecindario pequeño de se verá similar a . h g x 0 g ( x 0 ) = h ( x 0 ) g ′ ( x 0 ) = h ′ ( x 0 ) h x 0 gx0 h g x0 g(x0)=h(x0) g′(x0)=h′(x0) h x0 g
Puede mostrar queQueremos algo que coincida con esto en . Hay una elección natural:Puedes ver que coinciden en . ObtenemosComo es una constante, tenemos una combinación lineal simple de cuya derivada coincide con . Solo tenemos que elegir la constante en para hacer .x 0 h ( x ) = constante + ∑ i f i ( x ) exp ( f i ( x 0 ) ) . x = x 0 h ′ ( x ) = ∑
Entonces, comenzando con , formamos y optimizamos eso. Debido a que es similar a en la vecindad de , esperamos que el óptimo de sea similar al óptimo de g. Una vez que tenga una nueva estimación, construya la siguiente y repita. h ( x ) g ( x ) x 0 h hx0 h(x) g(x) x0 h h
Espero que esto haya motivado la elección de . Este es exactamente el procedimiento que tiene lugar en EM.h
Pero hay un punto más importante. Usando la desigualdad de Jensen puedes demostrar que . Esto significa que cuando optimizas siempre obtienes una que hace que sea más grande en comparación con . Entonces, aunque fue motivado por su similitud local con , es seguro maximizar globalmente en cada iteración. La esperanza que mencioné anteriormente no es necesaria.h ( x ) x g g ( x 0 ) h g hh(x)≤g(x) h(x) x g g(x0) h g h
Esto también da una pista sobre cuándo usar EM: cuando las combinaciones lineales de los argumentos de la función son más fáciles de optimizar. Por ejemplo, cuando son cuadráticos, como sucede cuando se trabaja con mezclas de gaussianos. Esto es particularmente relevante para las estadísticas donde muchas de las distribuciones estándar son de familias exponenciales .exp
fuente
Como dijiste, no entraré en detalles técnicos. Hay bastantes tutoriales muy bonitos. Uno de mis favoritos son las notas de clase de Andrew Ng . Echa un vistazo también a las referencias aquí .
EM está naturalmente motivado en modelos mixtos y modelos con factores ocultos en general. Tomemos, por ejemplo, el caso de los modelos de mezcla gaussiana (GMM). Aquí modelamos la densidad de las observaciones como una suma ponderada de gaussianos: donde es la probabilidad de que la muestra sido causada / generada por el componente i-ésimo, es la media de la distribución, y es la covarianza matriz. La manera de entender esta expresión es la siguiente: cada muestra de datos ha sido generada / causada por un componente, pero no sabemos cuál. El enfoque es entonces expresar la incertidumbre en términos de probabilidad (p ( x ) = K ∑ i = 1 π i N ( x | μ i , Σ i ) π i x μ i Σ i π iK
El punto no es usar funciones monótonas sino funciones convexas. Y la razón es la desigualdad de Jensen que asegura que las estimaciones del algoritmo EM mejorarán en cada paso.
fuente