¿Por qué hay una E en el algoritmo de nombre EM?

Entiendo dónde ocurre el paso E en el algoritmo (como se explica en la sección matemática a continuación). En mi opinión, el ingenio clave del algoritmo es el uso de la desigualdad de Jensen para crear un límite inferior a la probabilidad logarítmica. En ese sentido, tomar Expectationsimplemente se hace para reformular la probabilidad logarítmica para encajar en la desigualdad de Jensen (es decir, para la función cóncava). $E(f(x)) < f(E(x))$

¿Hay alguna razón por la que se llama el E-step? ¿Hay algún significado para lo que estamos esperando (es decir, ? Siento que me falta algo de intuición detrás de por qué la Expectativa es tan central, en lugar de simplemente ser incidental para el uso de la desigualdad de Jensen. $p(x_i, z_i| \theta)$

EDITAR: Un tutorial dice:

El nombre 'E-step' proviene del hecho de que generalmente no es necesario formar la distribución de probabilidad sobre las terminaciones explícitamente, sino que solo necesita calcular estadísticas suficientes 'esperadas' sobre estas terminaciones.

¿Qué significa "uno no necesita formar la distribución de probabilidad sobre terminaciones explícitamente"? ¿Cómo sería esa distribución de probabilidad?

Apéndice: E-step en el algoritmo EM

\begin{aligned} l l & = \sum_{i} \log p (x_{i}; θ) & definition of log likelihood \\ = \sum_{i} \log \sum_{z_{i}} p (x_{i}, z_{i}; θ) & augment with latent variables z \\ = \sum_{i} \log \sum_{z_{i}} Q_{i} (z_{i}) \frac{p (x_{i}, z_{i}; θ)}{Q_{i} (z_{i})} & Q_{i} is a distribution for z_{i} \\ = \sum_{i} \log E_{z_{i}} [\frac{p (x_{i}, z_{i}; θ)}{Q_{i} (z_{i})}] & taking expectations - hence the E in EM \\ \geq \sum E_{z_{i}} [\log \frac{p (x_{i}, z_{i}; θ)}{Q_{i} (z_{i})}] & Using Jensen's rule for \log which is concave \\ \geq \sum_{i} \sum_{z_{i}} Q_{i} (z_{i}) \log \frac{p (x_{i}, z_{i}; θ)}{Q_{i} (z_{i})} & Q function to maximize \end{aligned}

$\begin{align} ll &= \sum_i{\log p(x_i; \theta)} && \text{definition of log likelihood} \\ &= \sum_i \log \sum_{z_i}{p(x_i, z_i; \theta)} && \text{augment with latent variables $z$} \\ &= \sum_i \log \sum_{z_i} Q_i(z_i) \frac{p(x_i, z_i; \theta)}{Q_i(z_i)} && \text{$Q_i$ is a distribution for $z_i$} \\ &= \sum_i \log E_{z_i}[\frac{p(x_i, z_i; \theta)}{Q_i(z_i)}] && \text{taking expectations - hence the E in EM} \\ &\geq \sum E_{z_i}[\log \frac{p(x_i, z_i; \theta)}{Q_i(z_i)}] && \text{Using Jensen's rule for $\log$ which is concave} \\ &\geq \sum_i \sum_{z_i} Q_i(z_i) \log \frac{p(x_i, z_i; \theta)}{Q_i(z_i)} && \text{Q function to maximize} \end{align}$

maximum-likelihood optimization expectation-maximization latent-variable kullback-leibler Heisenberg
fuente

No me queda claro lo que está preguntando, pero siempre he asumido que la relevancia detrás de nombrar el E-step es que, en cierto sentido, está "completando" o "imputando" la faltante tomando la expectativa. De acuerdo, esto no es exactamente lo que está sucediendo porque está tomando que no es lo mismo que enchufar algo para desaparecido

z

$z$

E_{θ} [\log p (x, Z; θ^{'}) ∣ X = x]

$E_\theta [\log p(x, Z; \theta') \mid X = x]$

Z

$Z$ valores de , pero operacionalmente uno a menudo termina haciendo algo así. Si estuviéramos haciendo aumento de datos, que es similar a EM en muchos aspectos.

chico

Sí, este es el tipo de discusión que quiero tener. Entonces, cuando dices imputar z tomando expectativa ". ¿La expectativa de qué? Además, ¿te refieres a lugar de

E_{z}

$E_z$

E_{θ}

$E_\theta$ ?

Heisenberg

Mi educación siempre ha sido indexar la con el parámetro que indexa la medida de probabilidad con la que se está tomando la expectativa. En CS lo hacen como sugieres. Estoy integrando , condicionando a contra una medida indexada por .

E

$E$

Z

$Z$

X

$X$

θ

$\theta$

chico

Como ejemplo, cuando se ajustan mezclas gaussianas, el paso E imputa los indicadores de clase que faltan. Pero lo hace de manera difusa calculando las responsabilidades de cada observación.

chico

Respuestas:

Las expectativas son fundamentales para el algoritmo EM. Para empezar, la probabilidad asociada con los datos se representa como una expectativa donde la expectativa es en términos de la distribución marginal del vector latente . $(x_1,\ldots,x_n)$

\begin{aligned} pags (X_{1}, ..., X_{norte}; θ) & = \int_{Z^{norte}} pags (X_{1}, ..., X_{norte}, z_{1}, ..., z_{norte}; θ) re z \\ = \int_{Z^{norte}} pags (X_{1}, ..., X_{norte} El | z_{1}, ..., z_{norte}, θ) pags (z_{1}, ..., z_{norte}; θ) re z \\ = {mi}_{θ} [pags (X_{1}, ..., X_{norte} El | z_{1}, ..., z_{norte}, θ)] \end{aligned}

$\begin{align*} p(x_1,\ldots,x_n;\theta) &= \int_\mathfrak{{Z}^n} p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)\,\text{d}\mathbf{\mathfrak{z}}\\ &=\int_\mathfrak{{Z}^n} p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)p(\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)\,\text{d}\mathbf{\mathfrak{z}}\\ &=\mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right] \end{align*}$

(z_{1}, \dots, z_{n})

$(\mathfrak{z}_1,\ldots,\mathfrak{z}_n)$

La intuición detrás de EM también se basa en una expectativa. Dado que no se puede optimizar directamente, mientras que puede, pero depende de la ' no observada , la idea es maximizar en su lugar la probabilidad de registro completa esperada $\log p(x_1,\ldots,x_n;\theta)$ $\log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)$ $\mathfrak{z}_i$

mi [Iniciar sesión pags (X_{1}, ..., X_{norte}, z_{1}, ..., z_{norte}; θ) El | X_{1}, ..., X_{norte}]

$\mathbb{E}\left[ \log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta) \big| x_1,\ldots,x_n \right]$ excepto que esta expectativa también depende de un valor de , elegido como , por ejemplo, la función para maximizar (en ) en el paso M:

θ

$\theta$

θ_{0}

$\theta_0$

θ

$\theta$

Q (θ_{0 0}, θ) = {mi}_{θ_{0 0}} [Iniciar sesión pags (X_{1}, ..., X_{norte}, z_{1}, ..., z_{norte}; θ) El | X_{1}, ..., X_{norte}]

$Q(\theta_0,\theta)=\mathbb{E}_{\theta_0}\left[ \log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta) \big| x_1,\ldots,x_n \right]$ La desigualdad de Jensen solo se presenta como justificación del aumento de la probabilidad observada en cada paso M.

Xi'an
fuente

Gracias por la explicación. Dado que nuestra distribución posterior para los vectores latentes cambia en cada paso, cambia en cada paso ¿también? Si es así, esta imagen es un poco confusa porque hay una curva roja fija que representa , mientras que "cambia" en cada paso ya que estamos promediando nuestra creencia actual sobre los vectores latentes en ese paso.

E_{θ} [p (x_{1}, \dots, x_{n}, z, \dots, z, θ)]

$E_\theta[p(x_1,\dots,x_n, \mathfrak{z}, \dots, \mathfrak{z}, \theta)]$

p (x; θ)

$p(x;\theta)$

p (x; θ)

$p(x;\theta)$

z

$z$

Heisenberg

lo siento, no entiendo la pregunta: en cada paso EM, el valor de cambia y aumenta. Esto no significa que la función de probabilidad cambie.

E_{θ} [p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ)]

$\mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right]$

Xi'an

No es ? Si el RHS cambia de acuerdo con nuestra creencia posterior sobre el vector latente, ¿cambia también el LHS?

p (x_{1}, \dots, x_{n}; θ) = E_{θ} [p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ)]

$p(x_1,\ldots,x_n;\theta) = \mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right]$

Heisenberg

Esta identidad está en mi respuesta. Ambas partes toman valores diferentes cuando varía. Sin embargo, en esta ecuación no existe una noción de creencia posterior ya que (a) es fija y (b) los 's se consideran marginalmente.

θ

$\theta$

θ

$\theta$

z_{i}

$\mathfrak{z}_i$

Xi'an

En cada iteración , el paso E usa para calcular la integralDe ahí la función objetivo para maximizar los cambios en cada iteración . Esto no dice nada sobre la probabilidad objetivo original que solo depende de un único .

t

$t$

p (z | x, θ_{t})

$p(\mathfrak{z}|x, \theta_t)$

Q (θ_{t}, θ) = {mi}_{θ_{t}} [Iniciar sesión pags (X_{1}, ..., X_{norte}, z_{1}, ..., z_{norte}; θ) El | X_{1}, ..., X_{norte}] .

$Q(\theta_t,\theta)=\mathbb{E}_{\theta_t}\left[ \log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta) \big| x_1,\ldots,x_n \right].$

t

$t$

p (x_{1}, \dots, x_{n}; θ) = E_{θ} [p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ)]

$p(x_1,\ldots,x_n;\theta) = \mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right]$

θ

$\theta$

Xi'an

La respuesta de Xi'an es muy buena, solo una extensión con respecto a la edición.

El nombre 'E-step' proviene del hecho de que generalmente no es necesario formar la distribución de probabilidad sobre las terminaciones explícitamente, sino que solo necesita calcular estadísticas suficientes 'esperadas' sobre estas terminaciones.

Como no se observa el valor de , estimamos una distribución para cada punto de datos partir de los datos no observados. La función Q es la suma de las probabilidades de registro esperadas sobre $z$ $q_x(z)$ $x$ completions $q_x(z)$

Q (θ) = \sum_{X} {mi}_{q_{X}} [Iniciar sesión pags (X, z El | θ)]

$Q(\theta)=\sum_x E_{q_x}[\log p(x,z|\theta)]$

Lo mencionado probability distribution over completionsdebe referirse a . Para algunas distribuciones (especialmente la familia exponencial, ya que la probabilidad está en su forma de registro), solo tenemos que conocer la probabilidad esperada (en lugar de la probabilidad esperada) para calcular y maximizar . $p(x,z|\theta)$ sufficient statistics $Q(\theta)$

Hay una muy buena introducción en el Capítulo 19.2 de Modelos Gráficos Probabilísticos.

dontloo
fuente