Em estatística, o algoritmo de expectativa-maximização (EM) é um método iterativo para estimar parâmetros em modelos estatísticos, quando o modelo depende de variáveis latentes, ou seja, não observadas. A iteração EM alterna entre executar uma etapa de expectativa (E), e uma de maximização (M). A etapa de expectativa cria uma função para a expectativa da verossimilhança logarítmica usando a estimativa atual para os parâmetros. A etapa de maximização (M), calcula parâmetros para maximizar a verossimilhança logarítmica encontrada na etapa E. Essas estimativas de parâmetro são usadas para determinar a distribuição das variáveis latentes na próxima etapa E, e o algoritmo se repete várias vezes (por isso é chamado iterativo). direita|commoldura| Agrupamento por EM de dados sobre as erupções do gêiser Old Faithful . O modelo inicial aleatório vai sendo adequado aos dados observados. Nas primeiras iterações, o modelo muda substancialmente, mas depois converge para os dois modos padrões do gêiser . Visualizado usando ELKI .

História O algoritmo EM foi explicado e recebeu seu nome em um artigo clássico de 1977 de Arthur Dempster, Nan Laird e Donald Rubin. Eles apontaram que o método havia sido "proposto várias vezes em circunstâncias especiais" por autores anteriores. Uma das primeiras vezes foi no caso do método de contagem de genes para estimar frequências alélicas por Cedric Smith. Um tratamento detalhado do método EM para famílias exponenciais foi publicado por Rolf Sundberg em sua tese e em vários artigosRolf Sundberg. 1971. Maximum likelihood theory and applications for distributions generated when observing a function of an exponential family variable. Dissertation, Institute for Mathematical Statistics, Stockholm University. na etapa seguinte de sua colaboração com Per Martin-Löf e Anders Martin-Löf.G. Kulldorff. 1961. Contributions to the theory of estimation from grouped and partially grouped samples. Almqvist & Wiksell.Anders Martin-Löf. 1963. "Utvärdering av livslängder i subnanosekundsområdet" ("Evaluation of sub-nanosecond lifetimes"). ("Sundberg formula")Per Martin-Löf. 1966. «Statistics from the point of view of statistical mechanics». Lecture notes, Mathematical Institute, Aarhus University. ("Sundberg formula" credited to Anders Martin-Löf).Martin-Löf (1974). «The notion of redundancy and its use as a quantitative measure of the discrepancy between a statistical hypothesis and a set of observational data». Scand. J. Statist. 1: 3–18 With a discussion by F. Abildgård, A. P. Dempster, D. Basu, D. R. Cox, A. W. F. Edwards, D. A. Sprott, G. A. Barnard, O. Barndorff-Nielsen, J. D. Kalbfleisch and G. Rasch and a reply by the author. Proceedings of Conference on Foundational Questions in Statistical Inference (Aarhus, 1973), pp. 1–42. Memoirs, No. 1, Dept. Theoret. Statist., Inst. Math., Univ. Aarhus, Aarhus, 1974. O artigo de Dempster-Laird-Rubin, em 1977, generalizou o método e esboçou uma análise de convergência para uma classe mais ampla de problemas. Independentemente de invenções anteriores, o artigo de Dempster-Laird-Rubin recebeu uma discussão entusiasmada na reunião da Royal Statistical Society com Sundberg, chamando o artigo de "brilhante". O artigo de Dempster-Laird-Rubin estabeleceu o método EM como uma importante ferramenta de análise estatística.

A análise de convergência do algoritmo Dempster-Laird-Rubin tinha falhas e uma análise de convergência correta foi publicada por CF Jeff Wu em 1983. A prova de Wu estabeleceu a convergência do método EM fora da família exponencial, conforme reivindicado por Dempster – Laird – Rubin.

Introdução O algoritmo EM é usado para encontrar parâmetros de máxima verossimilhança de um modelo estatístico quando as equações não podem ser resolvidas diretamente. Normalmente, esses modelos envolvem variáveis latentes, além de parâmetros desconhecidos e observações de dados conhecidas.

Encontrar uma solução de máxima verossimilhança normalmente requer derivar a função de verossimilhança em relação a todos os valores desconhecidos, a todos parâmetros e variáveis latentes ao mesmo tempo. Em modelos estatísticos com variáveis latentes, isso é impossível (normalmente).O resultado é tipicamente um conjunto de equações interligadas em que a solução para os parâmetros requer os valores das variáveis latentes e vice-versa. Contudo, a substituição de um conjunto de equações pelo outro produz uma equação insolúvel.

O algoritmo EM procede da observação de que existe uma maneira de resolver esses dois conjuntos de equações (de parâmetros e variáveis latentes) numericamente. Isso significa escolher um valor arbitrário para um dos conjuntos, usá-lo para estimar o segundo conjunto e, em seguida, usar esses novos valores para encontrar uma estimativa melhor do primeiro conjunto e continuar alternando entre os dois até os valores resultantes convirjam para pontos fixos. Não é óbvio que isso funcionará, mas nesse contexto a derivada da probabilidade é (arbitrariamente próxima a) zero nesse ponto, o que, por sua vez, significa que o ponto é máximo ou um ponto de sela. Em geral, múltiplos máximos locais podem ocorrer, sem garantia de que o máximo global seja encontrado. Algumas probabilidades também têm singularidades matemáticas nelas, isto é, máximos sem sentido.

Descrição Dados:

o modelo estatístico que gera um conjunto dos dados observados, um conjunto de dados latentes não observados (ou valores ausentes) um vetor de parâmetros desconhecidos , e uma função de verossimilhança ,

a estimativa de máxima verossimilhança (MLE) dos parâmetros desconhecidos é determinada maximizando a verossimilhança marginal dos dados observados

Contudo, a equação obtida é frequentemente intratável. Por exemplo, o cálculo é extremamente difícil se for uma sequência de eventos na qual o número de valores cresce exponencialmente com o comprimento.

O algoritmo EM procura encontrar a MLE da verossimilhança marginal aplicando iterativamente estas duas etapas:

Etapa de expectativa (etapa E) : Defina como o valor esperado do logaritmo da função de verossimilhança de , com relação à atual distribuição condicional de dado e (as estimativas atuais dos parâmetros) :

Etapa de maximização (etapa M) : encontre os parâmetros que maximizam essa quantidade:

Os modelos típicos nos quais o EM é aplicado usam como uma variável latente indicando participação em um de um conjunto de grupos:

Os pontos de dados observados podem ser discretos ou contínuos. Associado a cada ponto de dados pode haver um vetor de observações. As variáveis latentes são discretas, extraídos de um número fixo de valores e com uma variável latente por unidade observada. Os parâmetros são contínuos e de dois tipos: Parâmetros associados a todos os pontos de dados e aqueles associados a um valor específico de uma variável latente (isto é, associados a todos os pontos de dados cuja variável latente correspondente possui esse valor).

No entanto, é possível aplicar EM a outros tipos de modelos.

O motivo segue. Se o valor dos parâmetros é conhecido, o valor das variáveis latentes pode ser encontrada maximizando o logaritmo da verossimilhança sobre todos os valores possíveis de , simplesmente iterando sobre ou através de um algoritmo como o algoritmo Baum – Welch para modelos ocultos de Markov . Se soubermos o valor das variáveis latentes , podemos estimar os parâmetros com bastante facilidade. Para isso, podemos agrupar os dados observados de acordo com o valor da variável latente e tirar a média dos pontos em cada grupo. Isso sugere um algoritmo iterativo, no caso em que ambos e são desconhecidos:

Primeiro, inicialize os parâmetros para alguns valores aleatórios. Calcule a probabilidade de cada valor possível de , dado . Em seguida, use os valores calculados apenas de para calcular uma estimativa melhor para os parâmetros . Itere as etapas 2 e 3 até a convergência.

O algoritmo, conforme descrito acima, aborda monotonicamente um mínimo local da função de custo.

Propriedades Falar de uma etapa de expectativa (E) é um pouco inadequado. O que é calculado na primeira etapa são os parâmetros fixos e dependentes da função Q. Uma vez que os parâmetros de Q são conhecidos, o máximo da função é encontrado na segunda etapa (M) de cada algoritmo EM.

Embora uma iteração EM aumente a função de verossimilhança observada dos dados (ou seja, marginal), não existe garantia de que a sequência convirja para um estimador de máxima verossimilhança. Para distribuições multimodais, isso significa que um algoritmo EM pode convergir para um máximo local. Existe uma variedade de abordagens heurísticas (ou metaheurísticas) para escapar de um máximo local, como a subida de colina com reinício aleatório (começando com várias estimativas iniciais aleatórias diferentes θ ( t )) ou a aplicação de métodos simulados de recozimento.

O EM é especialmente útil quando a probabilidade é de uma família exponencial : o passo E torna-se a soma das expectativas de estatísticas suficientes, e o passo M envolve maximizar uma função linear. Nesse caso, geralmente é possível obter atualizações de de forma fechada para cada etapa, usando a fórmula de Sundberg.Rolf Sundberg. 1971. Maximum likelihood theory and applications for distributions generated when observing a function of an exponential family variable. Dissertation, Institute for Mathematical Statistics, Stockholm University.Anders Martin-Löf. 1963. "Utvärdering av livslängder i subnanosekundsområdet" ("Evaluation of sub-nanosecond lifetimes"). ("Sundberg formula")

O método EM foi modificado para calcular estimativas da máximas a posteriori (PAM) para inferência bayesiana no artigo original de Dempster, Laird e Rubin.

Existem outros métodos para encontrar estimativas de máxima verossimilhança, como descida de gradiente, gradiente conjugado ou variantes do algoritmo de Gauss-Newton. Diferentemente do EM, esses métodos geralmente requerem a avaliação de primeira e / ou segunda derivada da função de probabilidade.

Prova de que está correto A maximização de expectativas trabalha para melhorar ao invés de melhorar diretamente . Aqui é mostrado que melhorias no primeiro implicam melhorias no último.

Para qualquer com probabilidade diferente de zero , nós podemos escrever

Tomamos a expectativa sobre os possíveis valores de sob a estimativa de parâmetro atual , multiplicamos os dois lados por e somamos (ou integramos) sobre . O lado esquerdo é a expectativa de uma constante, então temos:

Onde é definido pela soma negada que está substituindo. Esta última equação vale para todo valor de Incluindo ,

e subtrair esta última equação da equação anterior dá

A desigualdade de Jensen nos diz que , e podemos concluir que

Em palavras, escolhendo de forma a aumentar leva a um aumento de mesmo tamanho (ou maior) de .

Como um procedimento de maximização-maximização O algoritmo EM pode ser visto como duas etapas de maximização alternadas, ou seja, como um exemplo de subida coordenada. Considere a função:

onde q é uma distribuição de probabilidade arbitrária sobre os dados não observados Z e H (q) é a entropia da distribuição q. Esta função pode ser escrita como

Onde é a distribuição condicional dos dados não observados, dados os dados observados e é a divergência Kullback-Leibler .

Em seguida, as etapas no algoritmo EM podem ser vistas como:

Etapa de expectativa : escolha de forma a maximizar :

Etapa de maximização : escolha Para maximizar :

Aplicações O algoritmo de EM é usado para tarefas como agrupamento (clustering) em aprendizado de máquina e visão computacional . No campo de processamento de linguagem natural, duas instâncias proeminentes do algoritmo são o algoritmo de Baum-Welch para modelos ocultos de Markov e o algoritmo de dentro para fora para indução não supervisionada de gramáticas livres de contexto estocásticas.

O algoritmo de EM é usado para estimativa de parâmetros de modelos de misturas, principalmente na genética quantitativa.