O algoritmo de maximização de expectativa (EM) é um método iterativo usado em estatística para encontrar estimativas de máxima verossimilhança local ou máxima a posteriori (MAP) de parâmetros em modelos estatísticos que dependem de variáveis latentes não observadas. O algoritmo alterna entre uma etapa de expectativa (etapa E), que calcula a verossimilhança logarítmica esperada dadas as estimativas atuais dos parâmetros, e uma etapa de maximização (etapa M), que atualiza os parâmetros para maximizar essa verossimilhança logarítmica esperada. Esses parâmetros atualizados então informam a próxima etapa E, e o processo se repete até a convergência. O EM é amplamente aplicado em campos como Machine learning para tarefas como estimar modelos de mistura, lidar com dados ausentes e treinar modelos ocultos de Markov.
O desafio central que o EM aborda surge quando uma função de verossimilhança envolve tanto dados observados quanto variáveis latentes não observadas. Maximizar diretamente a verossimilhança calculando derivadas em relação a todas as incógnitas tipicamente produz equações interligadas que não podem ser resolvidas analiticamente. O EM contorna isso resolvendo iterativamente um conjunto de incógnitas enquanto mantém o outro fixo, alternando até que ambos convinjam para um ponto fixo. Essa abordagem garante o aumento da verossimilhança a cada iteração, embora possa convergir para um máximo local ou ponto de sela em vez do ótimo global.
História
O algoritmo EM foi formalmente nomeado e explicado em um artigo clássico de 1977 por Arthur Dempster, Nan Laird e Donald Rubin. No entanto, o método já havia sido proposto em casos especiais por autores anteriores. Cedric Smith introduziu um método de contagem de genes para estimar frequências alélicas, e H.O. Hartley propôs uma abordagem relacionada em 1958, com desenvolvimentos adicionais por Hartley e Hocking em 1977. Rolf Sundberg forneceu um tratamento detalhado para famílias exponenciais em sua tese e em artigos subsequentes, com base na colaboração com Per Martin-Löf e Anders Martin-Löf. O artigo de 1977 de Dempster, Laird e Rubin generalizou essas ideias e esboçou uma análise de convergência, estabelecendo o EM como uma ferramenta estatística importante. Uma prova de convergência correta foi posteriormente publicada por C. F. Jeff Wu em 1983, abordando falhas na análise original e estendendo as garantias de convergência além das famílias exponenciais.
Descrição do Algoritmo
Dados os dados observados X, os dados latentes Z e os parâmetros desconhecidos θ, o objetivo é maximizar a verossimilhança marginal L(θ; X) = ∫ p(X, Z | θ) dZ. A iteração do EM consiste em duas etapas:
- Etapa E: Calcular o valor esperado da função de verossimilhança logarítmica, Q(θ | θ^(t)), em relação à distribuição condicional de Z dados X e a estimativa atual dos parâmetros θ^(t).
- Etapa M: Encontrar os parâmetros θ^(t+1) que maximizam Q(θ | θ^(t)).
Os parâmetros atualizados são então usados na próxima etapa E, e o processo se repete até que a mudança nos parâmetros ou na verossimilhança caia abaixo de um limiar. Esse procedimento aumenta monotonicamente a verossimilhança, garantindo a convergência para um ponto estacionário.
Aplicações
O EM é comumente usado para estimar parâmetros de modelos de mistura, como misturas gaussianas, onde cada ponto de dados observado é assumido como proveniente de um dos vários componentes subjacentes. Ele também lida com problemas de dados ausentes, onde algumas observações estão incompletas. Em Artificial intelligence, o EM sustenta algoritmos de treinamento para modelos ocultos de Markov, que são usados em reconhecimento de fala e bioinformática. Além disso, o EM pode resolver problemas de regressão linear múltipla com variáveis latentes e é aplicado em análise de fatores e agrupamento (clustering).
Propriedades e Limitações
O EM é computacionalmente eficiente e fácil de implementar para muitos modelos, mas tem limitações. Ele pode convergir para máximos locais, e a solução final depende da inicialização. Em modelos de mistura, o EM pode encontrar soluções singulares onde um componente tem variância zero, o que são máximos sem sentido. O algoritmo também requer a especificação do número de componentes ou estados latentes, que muitas vezes é desconhecido. Variantes como o algoritmo EM generalizado e o EM estocástico abordam alguns desses problemas, mas o método básico permanece uma ferramenta fundamental na computação estatística.
Conceitos Relacionados
O algoritmo EM está intimamente relacionado a outras técnicas de otimização iterativa em Machine learning, como métodos baseados em gradiente, incluindo Stochastic Gradient Descent Variants e Adam (Optimizer). Ele também está conectado à inferência variacional em Deep learning, onde distribuições posteriores aproximadas são otimizadas. Em Generative AI, abordagens inspiradas no EM aparecem no treinamento de modelos com variáveis latentes, e seus princípios são fundamentais para entender algoritmos mais avançados como Reinforcement Learning from AI Feedback (RLAIF) e Curriculum Learning.