Por que existe um E no nome do algoritmo EM?

8

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(xi,zi|θ)

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

ll=ilogp(xi;θ)definition of log likelihood=ilogzip(xi,zi;θ)augment with latent variables z=ilogziQi(zi)p(xi,zi;θ)Qi(zi)Qi is a distribution for zi=ilogEzi[p(xi,zi;θ)Qi(zi)]taking expectations - hence the E in EMEzi[logp(xi,zi;θ)Qi(zi)]Using Jensen's rule for log which is concaveiziQi(zi)logp(xi,zi;θ)Qi(zi)Q function to maximize
Heisenberg
fonte
2
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. E θ [ log p ( x , Z ; θ ) X = x ] ZzEθ[logp(x,Z;θ)X=x]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 θEzEθ
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 . Z X θEZXθ
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:

11

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 .p ( x 1 , , x n ; θ )(x1,,xn) (z1,,zn)

p(x1,,xn;θ)=Znp(x1,,xn,z1,,zn;θ)dz=Znp(x1,,xn|z1,,zn,θ)p(z1,,zn;θ)dz=Eθ[p(x1,,xn|z1,,zn,θ)]
(z1,,zn)

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 n ] ( x 1 , , x n , z 1 , , z n ; θ ) |logp(x1,,xn;θ)z i E θ θ 0 θ Q ( θ 0 , θ ) = E θ 0 [ log plogp(x1,,xn,z1,,zn;θ)zi

E[logp(x1,,xn,z1,,zn;θ)|x1,,xn]
θθ0θ
Q(θ0,θ)=Eθ0[logp(x1,,xn,z1,,zn;θ)|x1,,xn]
A desigualdade de Jensen é apenas uma justificativa para o aumento da probabilidade observada em cada etapa M.
Xi'an
fonte
1
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(x1,,xn,z,,z,θ)]p(x;θ)p(x;θ)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(x1,,xn|z1,,zn,θ)]
Xian
Não é ? Se o RHS muda de acordo com nossa crença posterior sobre o vetor latente, o LHS também muda? p(x1,,xn;θ)=Eθ[p(x1,,xn|z1,,zn,θ)]
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. θθzi
Xian
1
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 . p ( z | x , θ t ) Q ( θ t , θ ) = Etp(z|x,θt)
Q(θt,θ)=Eθt[logp(x1,,xn,z1,,zn;θ)|x1,,xn].
t θp(x1,,xn;θ)=Eθ[p(x1,,xn|z1,,zn,θ)]θ
Xian
1

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 emq x ( z ) x q x ( z )zqx(z)xcompletionsqx(z)

Q(θ)=xEqx[logp(x,z|θ)]

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 .Q ( θ )p(x,z|θ)sufficient statisticsQ(θ)


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

dontloo
fonte