Por que existe um E no nome do algoritmo EM?

Eu entendo onde a etapa E acontece no algoritmo (conforme explicado na seção de matemática abaixo). Na minha opinião, a principal engenhosidade do algoritmo é o uso da desigualdade de Jensen para criar um limite inferior à probabilidade do log. Nesse sentido, aceitar isso Expectationé simplesmente feito para reformular a probabilidade logarítmica de se encaixar na desigualdade de Jensen (ie para a função côncava.) $E(f(x)) < f(E(x))$

Existe uma razão para que o E-step seja chamado? Existe algum significado para o que estamos ? seja, ? Sinto que estou perdendo alguma intuição por que a Expectativa é tão central, em vez de simplesmente ser incidental ao uso da desigualdade de Jensen. $p(x_i, z_i| \theta)$

EDIT: Um tutorial diz:

O nome 'E-step' vem do fato de que geralmente não é necessário formar a distribuição de probabilidade sobre conclusões explicitamente, mas sim apenas computar estatísticas suficientes 'esperadas' sobre essas conclusões.

O que significa "normalmente não é necessário formar a distribuição de probabilidade sobre conclusões explicitamente"? Como seria essa distribuição de probabilidade?

Apêndice: Etapa E no 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
fonte

Não está claro para mim o que você está perguntando, mas sempre assumi que a relevância por trás do nome da etapa E é que, em certo sentido, você está "preenchendo" ou "imputando" o ausente , assumindo a expectativa. É verdade que isso não é exatamente o que está acontecendo porque você está usando que não é a mesma coisa que conectar algo para o faltando os valores de , mas, operacionalmente, muitas vezes acaba-se fazendo algo assim. Se estivéssemos realizando aumento de dados - que é semelhante ao EM em muitos aspectos.

z

$z$

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

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

Z

$Z$

cara

Sim, este é o tipo de discussão que eu quero ter. .? Então, quando você diz z impute tomando expectativa" A expectativa de que Além disso, você quer dizer vez de ?

E_{z}

$E_z$

E_{θ}

$E_\theta$

Heisenberg

Minha educação sempre foi indexar o com o parâmetro indexar a medida de probabilidade com a qual a expectativa está sendo tomada. No CS, eles fazem isso como você está sugerindo. Estou integrando , condicionando a uma medida indexada por .

E

$E$

Z

$Z$

X

$X$

θ

$\theta$

cara

Como exemplo, ao ajustar misturas gaussianas, o E-step imputou os indicadores de classe ausentes. Mas o faz de maneira confusa, calculando responsabilidades para cada observação.

cara

Respostas:

As expectativas são centrais para o algoritmo EM. Para começar, a probabilidade associada aos dados é representada como uma expectativa onde a expectativa é em termos da distribuição marginal do vetor latente . $(x_1,\ldots,x_n)$

\begin{aligned} p (x_{1}, \dots, x_{n}; θ) & = \int_{Z^{n}} p (x_{1}, \dots, x_{n}, z_{1}, \dots, z_{n}; θ) d z \\ = \int_{Z^{n}} p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ) p (z_{1}, \dots, z_{n}; θ) d z \\ = E_{θ} [p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ)] \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)$

A intuição por trás do EM também se baseia em uma expectativa. Como não pode ser otimizado diretamente, enquanto pode, mas depende dos não observados , a idéia é maximizar a probabilidade completa de log esperada exceto que essa expectativa também depende de um valor , escolhido como , digamos, portanto, a função para maximizar (in ) na etapa M: $\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$

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

$\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]$

θ

$\theta$

θ_{0}

$\theta_0$

θ

$\theta$

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

$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]$ A desigualdade de Jensen é apenas uma justificativa para o aumento da probabilidade observada em cada etapa M.

Xi'an
fonte

Obrigada pelo esclarecimento. Como nossa distribuição posterior para os vetores latentes muda a cada passo, muda a cada passo também? Nesse caso, essa imagem é um pouco confusa porque há uma curva vermelha fixa representando , enquanto que "muda" a cada passo, pois estamos calculando a média de nossa crença atual sobre os vetores latentes nessa etapa.

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

desculpe, eu não entendo a pergunta: em cada etapa do EM, o valor de muda e aumenta. Isso não significa que a própria função de probabilidade mude.

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]$

Xian

Não é ? Se o RHS muda de acordo com nossa crença posterior sobre o vetor latente, o LHS também muda?

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

Essa identidade está na minha resposta. Ambos os lados assumem valores diferentes quando varia. No entanto, nesta equação não há noção de crença posterior, pois (a) é fixo e (b) os são considerados marginalmente.

θ

$\theta$

θ

$\theta$

z_{i}

$\mathfrak{z}_i$

Xian

Em cada iteração , a etapa E usa para calcular o integralPortanto, a função de destino para maximizar as alterações a cada iteração . Isso não diz nada sobre a probabilidade original do destino que depende apenas de um .

t

$t$

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

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

Q (θ_{t}, θ) = E_{θ_{t}} [\log p (x_{1}, \dots, x_{n}, z_{1}, \dots, z_{n}; θ) | x_{1}, \dots, x_{n}] .

$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$

Xian

A resposta de Xi'an é muito boa, apenas uma extensão referente à edição.

O nome 'E-step' vem do fato de que geralmente não é necessário formar a distribuição de probabilidade sobre conclusões explicitamente, mas sim apenas computar estatísticas suficientes 'esperadas' sobre essas conclusões.

Como o valor de não é observado, estimamos uma distribuição para cada ponto de dados partir dos dados não observados. A função Q é a soma das probabilidades esperadas de log em $z$ $q_x(z)$ $x$ completions $q_x(z)$

Q (θ) = \sum_{x} E_{q_{x}} [\log p (x, z | θ)]

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

O mencionado probability distribution over completionsdeve se referir a . Para algumas distribuições (especialmente a família exponencial, já que a probabilidade está em sua forma logarítmica), precisamos apenas conhecer o esperado (em vez da probabilidade esperada) para calcular e maximizar . $p(x,z|\theta)$ sufficient statistics $Q(\theta)$

Há uma introdução muito boa no capítulo 19.2 dos modelos gráficos probabilísticos.

dontloo
fonte