O algoritmo de maximização de expectativa (EM) é um método iterativo em estatística e aprendizado de máquina para encontrar estimativas de máxima verossimilhança ou máxima a posteriori de parâmetros em modelos estatísticos que dependem de variáveis latentes não observadas. O EM alterna entre uma etapa de expectativa (E), que calcula uma função para a verossimilhança logarítmica esperada usando as estimativas atuais dos parâmetros, e uma etapa de maximização (M), que atualiza os parâmetros para maximizar essa verossimilhança logarítmica esperada. Essas estimativas atualizadas então informam a próxima etapa E, e o processo se repete até a convergência.
Em aprendizado de máquina, o EM é uma ferramenta central para modelos com dados incompletos, como modelos de mistura (por exemplo, modelos de mistura gaussiana) e modelos ocultos de Markov. Ele tem aplicações em agrupamento, segmentação de imagens e estimação de parâmetros para modelos gráficos probabilísticos, e serve como base para a inferência variacional mais avançada usada em modelos generativos profundos.
História
O algoritmo EM foi formalmente nomeado e explicado em um artigo de 1977 por Arthur Dempster, Nan Laird e Donald Rubin, mas o método já havia sido proposto anteriormente para casos específicos. Cedric Smith usou a contagem de genes para estimar frequências alélicas, e H.O. Hartley introduziu uma abordagem relacionada em 1958, que Hartley estendeu com Hocking em 1977, fornecendo conceitos-chave. Rolf Sundberg desenvolveu um tratamento detalhado para famílias exponenciais, influenciado por Per Martin-Löf e Anders Martin-Löf. O artigo de Dempster-Laird-Rubin generalizou o método e o expandiu para uma classe mais ampla, embora sua prova de convergência contivesse falhas. C. F. Jeff Wu ofereceu uma análise de convergência corrigida em 1983, estabelecendo a validade do EM além das famílias exponenciais. O algoritmo tornou-se um padrão na análise estatística, e trabalhos posteriores, como os de Meng e van Dyk (1997), o refinaram ainda mais.
Etapas do Algoritmo
O algoritmo EM aborda problemas de otimização onde a função de verossimilhança contém variáveis latentes, tornando a maximização direta baseada em derivadas impossível em muitos casos. Em vez disso, o algoritmo resolve iterativamente equações interligadas: os parâmetros dependem das variáveis latentes, e as variáveis latentes dependem dos parâmetros, o que geralmente resulta em equações insolúveis quando substituídas diretamente.
O EM quebra esse ciclo alternando entre duas etapas:
- Etapa E: Dadas as estimativas atuais dos parâmetros da iteração anterior, calcular o valor esperado da verossimilhança logarítmica em relação à distribuição das variáveis latentes, condicionada aos dados observados.
- Etapa M: Maximizar a verossimilhança logarítmica esperada em relação aos parâmetros, produzindo novas estimativas que são garantidamente não decrescentes na verossimilhança dos dados observados. Isso se repete até a convergência.
Se o modelo tiver variáveis latentes independentes, a etapa E simplifica-se para encontrar a estimativa de máxima posteriori das variáveis latentes, frequentemente usando métodos como o algoritmo de Viterbi para modelos ocultos de Markov. O processo inteiro eventualmente atinge um máximo local da verossimilhança marginal, mas não garante o ótimo global. Em modelos de mistura, o procedimento pode convergir para uma solução com singularidades, como quando um componente tem variância zero e sua média se alinha exatamente com um ponto de dados.
Aplicações
O EM é usado para estimar misturas de gaussianas e para resolver problemas de regressão linear múltipla com dados ausentes. Em aprendizado de máquina, é um componente central na inferência de modelos com variáveis latentes, incluindo modelos de mistura gaussiana para agrupamento, como implementado no scikit-learn e em outras bibliotecas. Ele também sustenta algoritmos para cadeias de Markov em sequências de texto e para segmentação de imagens em visão computacional.
O método foi adotado em áreas como redes bayesianas e modelos gráficos probabilísticos, com influenciadores como Michael Jordan e Daphne Koller aplicando-o a modelos estruturados. Em ambientes modernos, o EM serve como base teórica para otimização iterativa em modelos como graphcore, embora redes neurais profundas frequentemente utilizem métodos baseados em gradiente em seu lugar.
Variantes e Extensões
Várias variantes melhoram o EM básico. O EM generalizado (GEM) relaxa a etapa M para encontrar parâmetros que aumentem, em vez de maximizar, a verossimilhança logarítmica esperada. A maximização condicional de expectativa (ECM) divide a etapa M em subetapas mais simples, sendo útil para parâmetros com restrições. O EM de Monte Carlo usa amostragem estocástica (por exemplo, cadeias de Markov Monte Carlo) na etapa E quando a verossimilhança logarítmica esperada não pode ser calculada analiticamente. Essas variantes mantêm a robustez central do EM, mas abordam desafios específicos de custo computacional.
Limitações e Considerações
O EM não garante encontrar um máximo global; pode parar em um máximo local ou em um ponto de sela. Ele pode ser sensível às inicializações e, em alguns casos, as soluções podem apresentar singularidades artificiais. Além disso, a etapa E assume que a verossimilhança logarítmica esperada pode ser calculada, o que pode ser intratável para modelos complexos. Variantes como inferência variacional (uma alternativa para aproximação) ou métodos conjuntos podem ser mais apropriadas nesses casos. Em contextos modernos de aprendizado de máquina, profissionais frequentemente dependem do EM por sua simplicidade, mas para modelos como redes neurais profundas ou GP, a otimização baseada em gradiente é preferida.
Ver Também
- Aprendizado de máquina
- Aprendizado profundo
- Inteligência artificial
- Universidade Carnegie Mellon (pesquisa em ML)
Referências
- 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.
- Wu, C. F. J. (1983). On the convergence properties of the EM algorithm. Annals of Statistics.
- Hartley, H. O. (1958). Maximum likelihood estimation from incomplete data. Biometrics.
{, "infobox": {"type": "algorithm", "introduced": "1977", "introduced_by": "Arthur Dempster, Nan Laird e Donald Rubin", "related": ["machine-learning", "artificial-intelligence", "deep-learning"]}, ", "categories": ["statistical-algorithms", "machine-learning", "latent-variable-models", "optimization-methods"]}