EM Algorithm
- Proposto por
- Dempster, Laird & Rubin
- Ano
- 1977
- Tipo
- Iterative optimization algorithm
- Família
- Estimation
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Imagine tentar aprender as regras de um jogo observando jogadores cujas cartas você não consegue ver.
A cada rodada, você adivinha quais cartas eles provavelmente têm, com base no que observa, e então atualiza seu modelo das regras, assumindo que essas suposições estão corretas. O EM faz exatamente isso: o passo E preenche a informação ausente probabilisticamente usando as estimativas de parâmetros atuais, e o passo M reajusta o modelo como se esses valores preenchidos fossem observações reais.
A intuição por trás do método
Antes do início da iteração, o analista seleciona valores iniciais para os parâmetros desconhecidos, denotados por theta-0. Estes podem ser escolhidos aleatoriamente, a partir de um ajuste simplificado, ou com base no conhecimento do domínio. A qualidade da inicialização pode afetar qual máximo local o algoritmo converge, tornando múltiplas reinicializações aleatórias uma prática comum.
História
Ajuste de modelos de mistura Gaussiana para clusterização e estimação de densidade
Quando usar
Aumento monotônico garantido na verossimilhança dos dados observados a cada iteração, garantindo convergência estável
Limitações e considerações
- Pode apresentar convergência muito lenta (linear) quando a fração de informação ausente é grande
- Requer que o analista especifique o modelo de dados completos e a distribuição das variáveis latentes
- O EM padrão não fornece diretamente a matriz de covariância dos dados observados das estimativas; um passo suplementar (por exemplo, o método de Louis ou o algoritmo SEM) é necessário para erros padrão
- Usar uma única inicialização aleatória arrisca terminar em um máximo local ruim; sempre execute múltiplas reinicializações e selecione a solução com a maior log-verossimilhança final
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Converte um problema difícil de dados ausentes em uma sequência de otimizações tratáveis de dados completos
- Ampla aplicabilidade em modelos da família exponencial, modelos de mistura e frameworks de variáveis latentes
- Atualizações do passo M em forma fechada estão disponíveis para muitos modelos padrão, tornando a implementação eficiente
- Convergência para um máximo local em vez do máximo global quando a superfície de verossimilhança é multimodal
Aplicações
- Treinamento de modelos de Markov ocultos para reconhecimento de fala e análise de sequências biológicas
- Imputação múltipla e análise de dados ausentes em pesquisa clínica e de ciências sociais
- Estimação de parâmetros em análise fatorial e análise de classes latentes
- Segmentação e reconstrução de imagens em imagens médicas
- O algoritmo EM sempre converge para o máximo global?
Como funciona
Como funciona
Dado a estimativa de parâmetro atual theta-t, o passo E calcula Q, o valor esperado da log-verossimilhança dos dados completos sobre a distribuição das variáveis latentes não observadas Z, condicionada aos dados observados X. Essa expectativa efetivamente substitui quantidades desconhecidas por suas estimativas probabilísticas sem se comprometer com um único valor imputado.
Fórmula
\text{Choose initial parameter estimates } \theta^{(0)}O passo M maximiza a função Q do passo E em relação a theta, produzindo uma estimativa atualizada theta-(t+1). Como a log-verossimilhança dos dados completos é frequentemente mais simples de maximizar do que a log-verossimilhança marginal dos dados observados, este passo é frequentemente tratável mesmo quando a máxima verossimilhança direta não é.
Fórmula
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]Os passos E e M são repetidos alternadamente. Após cada ciclo completo, a log-verossimilhança dos dados observados é avaliada. A iteração para quando a mudança na log-verossimilhança (ou no vetor de parâmetros) cai abaixo de uma tolerância epsilon definida pelo usuário. Dempster et al. provaram que cada ciclo não pode diminuir a verossimilhança dos dados observados, garantindo convergência estável.
Fórmula
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})Use o algoritmo EM quando os dados contiverem valores ausentes, estados ocultos ou variáveis latentes e você precisar de estimativas de máxima verossimilhança. Ele é bem adequado para modelos de mistura Gaussiana, modelos de Markov ocultos, análise fatorial e imputação de dados ausentes. Suposições chave incluem que os dados ausentes estão ausentes aleatoriamente (MAR) e que o modelo de dados completos é tratável. Limitações incluem sensibilidade à inicialização, possível convergência para máximos locais e convergência lenta perto de pontos de sela. Alternativas incluem otimização baseada em gradiente com integração numérica, inferência variacional ou métodos MCMC.
Fórmula
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilonErros comuns
- Declarar convergência muito cedo monitorando apenas a mudança de parâmetro em vez da log-verossimilhança dos dados observados pode gerar estimativas imprecisas
- Aplicar EM quando os dados são Ausentes Não Aleatoriamente (MNAR) sem ajuste do modelo pode introduzir viés sistemático nas estimativas
- Ignorar o problema de troca de rótulos em modelos de mistura leva a atribuições de componentes não interpretáveis mesmo após convergência correta
- O algoritmo foi formalmente unificado e nomeado por Arthur Dempster, Nan Laird e Donald Rubin em seu artigo de 1977 no JRSS-B, que permanece um dos artigos de estatística mais citados já publicados. O artigo generalizou procedimentos de caso especial anteriores desenvolvidos independentemente para problemas específicos de dados ausentes. Décadas subsequentes produziram numerosas extensões, incluindo os algoritmos ECM, ECME, AECM e SEM, ampliando a aplicabilidade e acelerando a convergência em muitos cenários práticos.
Perguntas frequentes
Não. O EM garante apenas encontrar um máximo local (ou ponto de sela) da verossimilhança dos dados observados. Quando a superfície de verossimilhança tem múltiplos modos, a solução final depende da inicialização. Executar o algoritmo a partir de vários pontos de partida diferentes e reter a solução com a maior log-verossimilhança é o remédio prático padrão.
Como o EM difere da otimização direta de máxima verossimilhança?
O MLE direto maximiza a log-verossimilhança dos dados observados, o que pode envolver integrais intratáveis sobre variáveis latentes. O EM contorna isso maximizando iterativamente a log-verossimilhança esperada dos dados completos, que é frequentemente tratável analiticamente. A troca é que o EM pode convergir lentamente, enquanto métodos baseados em gradiente podem ser mais rápidos quando os gradientes da verossimilhança marginal estão disponíveis.
Quando devo preferir a imputação MICE ao algoritmo EM?
MICE (Multiple Imputation by Chained Equations) é preferível quando os dados incluem variáveis de tipos mistos, relações não lineares ou estruturas de interação complexas que são difíceis de codificar em um único modelo paramétrico de dados completos. O EM é mais natural quando existe um modelo conjunto bem especificado para todas as variáveis e a inferência visa os parâmetros do modelo, em vez de conjuntos de dados imputados.
O algoritmo EM está disponível como uma rotina central nos principais pacotes de estatística e aprendizado de máquina, e também pode ser implementado do zero, dado um modelo de dados completos tratável e suas estatísticas suficientes.
Métodos relacionados
Fontes
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.
Abrir referência DOICopiado.