La motivación de Maximización de la Expectativa algoritmo

Question

En el algoritmo EM enfoque que usamos la desigualdad de Jensen para llegar a $$\log p(x|\theta) \geq \int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz - \int \log p(z|x,\theta) p(z|x,\theta^{(k)})dz$$

y definir $\theta^{(k+1)}$ $$\theta^{(k+1)}=\arg \max_{\theta}\int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz$$

Todo lo que he leído EM solo brinca hacia abajo, pero siempre me he sentido incómodo por no tener una explicación de por qué el algoritmo EM surge de forma natural. Entiendo que $\log$ probabilidad es normalmente tratado con lidiar con la adición en lugar de la multiplicación, pero la aparición de $\log$ en la definición de $\theta^{(k+1)}$ se siente motivado para mí. ¿Por qué debe uno considerar $\log$ y no otras funciones monótonas? Por diversas razones, tengo la sospecha de que el "significado" o "motivación" detrás de maximización de la expectativa tiene algún tipo de explicación en términos de la teoría de la información y las estadísticas suficientes. Si hubiera una explicación que sería mucho más satisifying que sólo un resumen del algoritmo.

Answer 1

Probabilidad vs log-verosimilitud

Como ya se ha dicho, el $\log$ es introducido en el de máxima verosimilitud, simplemente porque es generalmente más fácil optimizar las sumas de productos. La razón por la que no considerar otras funciones monótonas es que el logaritmo es la única función con la propiedad de convertir los productos en sumas.

Otra forma de motivar el logaritmo es la siguiente: en Lugar de maximizar la probabilidad de los datos bajo nuestro modelo, podríamos equivalentemente, intenta minimizar el Kullback-Leibler divergencia entre la distribución de los datos, $p_\text{data}(x)$, y el modelo de distribución, $p(x \mid \theta)$,

$$D_\text{KL}[p_\text{datos}(x) \mid\mediados de p(x \mid \theta)] = \int p_\text{datos}(x) \log \frac{p_\text{datos}(x)}{p(x \mid \theta)} \, dx = const - \int p_\text{datos}(x)\log p(x \mid \theta) \, dx.$$

El primer término en el lado derecho es una constante en los parámetros. Si tenemos $N$ de las muestras de la distribución de los datos (nuestros puntos de datos), podemos aproximar el segundo término con el promedio de la log-verosimilitud de los datos,

$$\int p_\text{data}(x)\log p(x \mid \theta) \, dx \approx \frac{1}{N} \sum_n \log p(x_n \mid \theta).$$

Una visión alternativa de la EM

No estoy seguro de que este va a ser el tipo de explicación que usted está buscando, pero me he encontrado con el siguiente punto de vista de maximización de la expectativa mucho más esclarecedor que en su motivación a través de la desigualdad de Jensen (puede encontrar una descripción detallada en Neal & Hinton (1998) o en Chris Obispo PRML libro, el Capítulo 9.3).

No es difícil mostrar que

$$\log p(x \mid \theta) = \int p(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz + D_\text{KL}[q(z \mid x) \mid\mediados de p(z \mid x, \theta)]$$

para cualquier $q(z \mid x)$. Si decimos que el primer término en el lado derecho de la $F(q, \theta)$, esto implica que

$$F(q, \theta) = \int p(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz = \log p(x \mid \theta) - D_\text{KL}[q(z \mid x) \mid\mediados de p(z \mid x, \theta)].$$

Debido a la divergencia KL es siempre positivo, $F(q, \theta)$ es el límite inferior de la log-verosimilitud para todos los fijos $q$. Ahora, la EM puede ser visto como alternativamente maximizar $F$ con respecto al $q$$\theta$. En particular, mediante el establecimiento $q(z \mid x) = p(z \mid x, \theta)$ en el E-paso, podemos minimizar el KL de la divergencia en el lado derecho y por lo tanto maximizar $F$.

Answer 2

El algoritmo EM tiene diferentes interpretaciones y puede surgir de diferentes formas en diferentes aplicaciones.

Todo comienza con la probabilidad de la función $p(x \vert \theta)$, o lo que es equivalente, la función de verosimilitud logarítmica $\log p(x \vert \theta)$ nos gustaría maximizar. (Por lo general utilizamos el logaritmo ya que simplifica el cálculo: es estrictamente monótona, cóncava, y $\log(ab) = \log a + \log b$.) En un mundo ideal, el valor de $p$ sólo depende de los parámetros de los modelos $\theta$, así que podemos buscar a través del espacio de $\theta$ y encontrar uno que maximiza $p$.

Sin embargo, en muchos interesantes aplicaciones en el mundo real las cosas son más complicadas, porque no todas las variables observadas. Sí, podríamos observar directamente la $x$, pero algunas otras variables $z$ son observados. Debido a la falta de información sobre variables $z$, estamos en una especie de gallina de los huevos de situación: Sin $z$ no podemos estimar el parámetro $\theta$ sin $\theta$ que no se puede inferir cuál es el valor de $z$ puede ser.

Es donde el algoritmo EM entra en juego. Empezamos con una estimación inicial de los parámetros del modelo $\theta$ y obtener los valores esperados de la falta de información sobre variables $z$ (es decir, la dirección de paso). Cuando tenemos los valores de $z$, podemos maximizar la probabilidad de w.r.t. los parámetros de $\theta$ (es decir, la M de paso, correspondiente a la $\arg \max$ ecuación en el enunciado del problema). Con esto $\theta$ se obtienen los nuevos valores esperados de $z$ (otro E paso), y así sucesivamente. En otra palabra, en cada paso que asumir uno de los dos, $z$$\theta$, es conocido. Repetimos este proceso iterativo hasta que la probabilidad no puede ser mayor ya.

Este es el algoritmo EM en una cáscara de nuez. Es bien sabido que la probabilidad de que nunca va a disminuir a lo largo de este proceso iterativo EM el proceso. Pero tenga en cuenta que el algoritmo EM no garantiza el óptimo global. Es decir, podría terminar con un óptimo local de la función de probabilidad.

La aparición de $\log$ en la ecuación de $\theta^{(k+1)}$ es inevitable, porque aquí la función que desea maximizar está escrito como un log-verosimilitud.

Answer 3

El papel que he encontrado aclarar con respecto a expectation-maximization es Bayesiano K-Medios como "la Maximización de la Expectativa" Algoritmo (pdf) por Welling y Kurihara.

Supongamos que tenemos un modelo probabilístico $p(x,z,\theta)$ $x$ observaciones, $z$ ocultos variables aleatorias, y un total de $\theta$ parámetros. Se nos da un conjunto de datos $D$ y se ven obligados (por poderes superiores) para establecer $p(z,\theta|D)$.

1. Muestreo de Gibbs

Podemos aproximar $p(z,\theta|D)$ por muestreo. Muestreo de Gibbs da $p(z,\theta|D)$ por la alternancia de:

$$ \theta \sim p(\theta|z,D) \\ z \sim p(z|\theta,D) $$

2. Variacional De Bayes

En su lugar, podemos intentar establecer una distribución $q(\theta)$ $q(z)$ y minimizar la diferencia con la distribución que estamos después de $p(\theta,z|D)$. La diferencia entre las distribuciones tiene un conveniente nombre de fantasía, el KL-divergencia. Para minimizar $KL[q(\theta)q(z)||p(\theta,z|D)]$ actualizamos:

$$ q(\theta) \propto \exp (E [\log p(\theta,z,D) ]_{p(z)} ) \\ q(z) \propto \exp (E [\log p(\theta,z,D) ]_{p(\theta)} ) $$

3. Expectation-Maximization

Para venir para arriba con pleno derecho de las distribuciones de probabilidad para ambos $z$ $\theta$ pueden ser considerados extremos. ¿Por qué no en lugar de considerar una estimación de punto para uno de estos y mantener a los demás agradable y lleno de matices. En EM el parámetro de $\theta$ es establecido como un ser indigno de una distribución completa y ajustada a su MAP (maximum a Posteriori) de valor, $\theta^*$.

$$ \theta^* = \underset{\theta}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{p(z)} \\ q(z) = p(z|\theta^*,D) $$

Aquí $\theta^* \in \operatorname{argmax}$ sería una mejor notación: el argmax operador puede devolver varios valores. Pero no vamos a ser quisquilloso. En comparación con variacional de Bayes puede ver que la corrección de la $\log$ $\exp$ no cambia el resultado, por lo que no es necesario más.

4. La Maximización De La Expectativa

No hay ninguna razón para tratar a $z$ como un niño malcriado. Podemos también utilizar las estimaciones puntuales $z^*$ para nuestras variables ocultas y dar los parámetros $\theta$ el lujo de una distribución completa.

$$ z^* = \underset{z}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{p(\theta)} \\ q(\theta) = p(\theta|z^*,D) $$

Si nuestras variables ocultas $z$ son variables indicadoras, de repente tenemos barato de cómputo método para realizar la inferencia en el número de clústeres. Esto es en otras palabras: selección de modelo (o automático de la relevancia de la detección o imaginar otro nombre de fantasía).

5. Iteración condicional modos

Por supuesto, el niño del cartel de aproximado de inferencia es el uso de estimaciones puntuales por tanto los parámetros de $\theta$ así como las observaciones $z$.

$$ \theta^* = \underset{\theta}{\operatorname{argmax}} p(\theta,z^*,D) \\ z^* = \underset{z}{\operatorname{argmax}} p(\theta^*,z,D) \\ $$

Para ver cómo la Maximización de la Expectativa juega recomiendo el artículo. En mi opinión, la fuerza de este artículo no es sin embargo la aplicación a un $k$-medios alternativos, pero esta lúcida y concisa exposición de aproximación.

Answer 4

Como usted dijo, no voy a entrar en detalles técnicos. Hay unos cuantos muy buenos tutoriales. Uno de mis favoritos son Andrew Ng notas de la conferencia. Echa un vistazo también a las referencias aquí.

1. EM es una motivación natural en la mezcla de modelos y modelos con los factores ocultos en general. Tomemos por ejemplo el caso de Gaussian mixture models (GMM). Aquí el modelo de la densidad de las observaciones como una suma ponderada de $K$ gaussianas: $$p(x) = \sum_{i=1}^{K}\pi_{i} \mathcal{N}(x|\mu_{i}, \Sigma_{i})$$ donde $\pi_{i}$ es la probabilidad de que la muestra $x$ fue causado/generada por la i-ésima componente, $\mu_{i}$ es la media de la distribución, y $\Sigma_{i}$ es la matriz de covarianza. La forma de entender esta expresión es la siguiente: cada uno de los datos de la muestra se ha generado/causado por uno de los componentes, pero no sabemos cuál. El enfoque entonces para expresar la incertidumbre en términos de probabilidad ($\pi_{i}$ representa la posibilidad de que la i-ésima componente de la cuenta para que la muestra), y tomar la suma ponderada. Como un ejemplo concreto, supongamos que desea clúster de documentos de texto. La idea es asumir que cada documento pertenecen a un tema (la ciencia, el deporte,...) los cuales no se sabe de antemano!. Los temas posibles son variables ocultas. A continuación, se le da un montón de documentos, y por conteo de n-gramas o lo que sea de las características de extraer, desea, a continuación, encontrar esos grupos y ver a qué grupo pertenece el documento. EM es un procedimiento que ataca este problema paso a paso: la expectativa de paso de los intentos para mejorar la asignación de las muestras se ha logrado hasta ahora. La maximización de paso mejorar los parámetros de la mezcla, en otras palabras, la forma de los clusters.

2. El punto no es el uso de funciones monótonas pero de las funciones convexas. Y la razón es la de Jensen desigualdad que garantiza que en las estimaciones del algoritmo EM va a mejorar a cada paso.