Algoritmo de maximização de expectativa

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).

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 artigos na etapa seguinte de sua colaboração com Per Martin-Löf e Anders Martin-Löf. 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 $\mathbf {X}$ dos dados observados,
• um conjunto de dados latentes não observados (ou valores ausentes) $\mathbf {Z}$
• um vetor de parâmetros desconhecidos ${\boldsymbol {\theta }}$,
• e uma função de verossimilhança $L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})$,

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

$L({\boldsymbol {\theta }};\mathbf {X} )=p(\mathbf {X} \mid {\boldsymbol {\theta }})=\int p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})\,d\mathbf {Z}$

Contudo, a equação obtida é frequentemente intratável. Por exemplo, o cálculo é extremamente difícil se $\mathbf {Z}$ 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 $Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})$ como o valor esperado do logaritmo da função de verossimilhança de ${\boldsymbol {\theta }}$, com relação à atual distribuição condicional de $\mathbf {Z}$ dado $\mathbf {X}$ e ${\boldsymbol {\theta }}^{(t)}$ (as estimativas atuais dos parâmetros) :

$Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)}}\left[\log L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )\right]\,$

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

${\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\,$

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

1. Os pontos de dados observados $\mathbf {X}$ podem ser discretos ou contínuos. Associado a cada ponto de dados pode haver um vetor de observações.
2. As variáveis latentes $\mathbf {Z}$ são discretas, extraídos de um número fixo de valores e com uma variável latente por unidade observada.
3. 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 ${\boldsymbol {\theta }}$ é conhecido, o valor das variáveis latentes $\mathbf {Z}$ pode ser encontrada maximizando o logaritmo da verossimilhança sobre todos os valores possíveis de $\mathbf {Z}$, simplesmente iterando sobre $\mathbf {Z}$ ou através de um algoritmo como o algoritmo Baum – Welch para modelos ocultos de Markov . Se soubermos o valor das variáveis latentes $\mathbf {Z}$, podemos estimar os parâmetros ${\boldsymbol {\theta }}$ 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 ${\boldsymbol {\theta }}$ e $\mathbf {Z}$ são desconhecidos:

1. Primeiro, inicialize os parâmetros ${\boldsymbol {\theta }}$ para alguns valores aleatórios.
2. Calcule a probabilidade de cada valor possível de $\mathbf {Z}$, dado ${\boldsymbol {\theta }}$ .
3. Em seguida, use os valores calculados apenas de $\mathbf {Z}$ para calcular uma estimativa melhor para os parâmetros ${\boldsymbol {\theta }}$ .
4. 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.

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 maxima 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 $Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})$ ao invés de melhorar diretamente $\log p(\mathbf {X} \mid {\boldsymbol {\theta }})$ . Aqui é mostrado que melhorias no primeiro implicam melhorias no último.

Para qualquer $\mathbf {Z}$ com probabilidade diferente de zero $p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})$, nós podemos escrever

$\log p(\mathbf {X} \mid {\boldsymbol {\theta }})=\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}).$

Tomamos a expectativa sobre os possíveis valores de $\mathbf {Z}$ sob a estimativa de parâmetro atual $\theta ^{(t)}$, multiplicamos os dois lados por $p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})$ e somamos (ou integramos) sobre $\mathbf {Z}$ . O lado esquerdo é a expectativa de uma constante, então temos:

${\begin{aligned}\log p(\mathbf {X} \mid {\boldsymbol {\theta }})&=\sum _{\mathbf {Z} }p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\sum _{\mathbf {Z} }p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})\\&=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)}),\end{aligned}}$

Onde $H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})$ é definido pela soma negada que está substituindo. Esta última equação vale para todo valor de ${\boldsymbol {\theta }}$ Incluindo ${\boldsymbol {\theta }}={\boldsymbol {\theta }}^{(t)}$ ,

$\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}),$

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

$\log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}),$

A desigualdade de Jensen nos diz que $H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})$, e podemos concluir que

$\log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})\geq Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}).$

Em palavras, escolhendo ${\boldsymbol {\theta }}$ de forma a aumentar $Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})$ leva a um aumento de mesmo tamanho (ou maior) de $\log p(\mathbf {X} \mid {\boldsymbol {\theta }})$.

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:

$F(q,\theta ):=\operatorname {E} _{q}[\log L(\theta ;x,Z)]+H(q),$

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

$F(q,\theta )=-D_{\mathrm {KL} }{\big (}q\parallel p_{Z\mid X}(\cdot \mid x;\theta ){\big )}+\log L(\theta ;x),$

Onde $p_{Z\mid X}(\cdot \mid x;\theta )$ é a distribuição condicional dos dados não observados, dados os dados observados $x$ e $D_{KL}$ é a divergência Kullback-Leibler .

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

Etapa de expectativa : escolha $q$ de forma a maximizar $F$ :

$q^{(t)}=\operatorname {arg\,max} _{q}\ F(q,\theta ^{(t)})$

Etapa de maximização : escolha $\theta$ Para maximizar $F$ :

$\theta ^{(t+1)}=\operatorname {arg\,max} _{\theta }\ F(q^{(t)},\theta )$

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.

Na área da psicometria, o EM é quase indispensável para estimar parâmetros de itens e habilidades latentes nos modelos de teoria de respostas ao item.

O algoritmo EM também é amplamente utilizado na reconstrução de imagens médicas, especialmente em tomografia por emissão de pósitrons, tomografia computadorizada por emissão de fóton único, e tomografia computadorizada.

Na engenharia estrutural, o algoritmo de Identificação Estrutural usando Maximização de Expectativas (STRIDE, sigla do inglês) é um método somente de saída para identificar propriedades de vibração natural de um sistema estrutural usando dados de sensores (consulte Análise Modal Operacional).

Filtrando e suavizando algoritmos de EM

Um filtro de Kalman é tipicamente usado para estimativa de estado on-line e um suavizador de variância mínima pode ser empregado para estimativa off-line ou em lote. No entanto, essas soluções de variação mínima requerem que os parâmetros do modelo de espaço de estado sejam estimados. Os algoritmos EM podem ser usados para resolver problemas conjuntos de estimativa de parâmetros e estados das juntas.

Os algoritmos EM de filtragem e suavização surgem repetindo este procedimento de duas etapas:

E-step

Opere um filtro Kalman ou um suavizador de variância mínima projetado com estimativas de parâmetros atuais para obter estimativas de estado atualizadas.

M-step

Use as estimativas de estado filtradas ou suavizadas nos cálculos de máxima verossimilhança para obter estimativas de parâmetros atualizadas.

Suponha que um filtro Kalman ou suavizador de variância mínima opere nas medições de um sistema de entrada única e saída única que possua ruído branco aditivo. Uma estimativa atualizada da variação de ruído de medição pode ser obtida a partir do cálculo da máxima verossimilhança:

${\widehat {\sigma }}_{v}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{(z_{k}-{\widehat {x}}_{k})}^{2},$

onde ${\widehat {x}}_{k}$ são estimativas de saída escalares calculadas por um filtro ou suavizador a partir de medições escalares de N $z_{k}$ . A atualização acima também pode ser aplicada à atualização de uma intensidade de ruído de medição de Poisson. Da mesma forma, para um processo autorregressivo de primeira ordem, uma estimativa atualizada da variação do ruído do processo pode ser calculada por

${\widehat {\sigma }}_{w}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k})}^{2},$

Onde ${\widehat {x}}_{k}$ e ${\widehat {x}}_{k+1}$ são estimativas de estado escalar calculadas por um filtro ou por um suavizador. A estimativa atualizada do coeficiente do modelo é obtida via

${\widehat {F}}={\frac {\sum _{k=1}^{N}({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k})}{\sum _{k=1}^{N}{\widehat {x}}_{k}^{2}}}.$

A convergência de estimativas de parâmetros como as acima são bem estudadas.

Variantes

Vários métodos foram propostos para acelerar a convergência do algoritmo EM. Esses métodos incluem os que utilizam gradiente conjugado e os métodos de Newton modificados (Newton – Raphson). Além disso, o EM pode ser usado com métodos de estimativa com restrições (constraints).

O algoritmo de maximização de expectativa expandida por parâmetros (PX-EM) acelera o processo por "usar um ajuste de covariância para corrigir a análise da etapa M, capitalizando em informações extras capturadas nos dados completos imputados " (tradução livre).

A maximização condicional da expectativa (ECM) substitui cada etapa M por uma sequência de etapas da maximização condicional (CM). Em cada etapa CM, ada parâmetro θ _i é maximizado individualmente, condicionalmente nos outros parâmetros que permanecem fixos. O próprio algoritmo de ECM possuí ao menos uma extensão, o algoritmo de maximização condicional da expectativa (ECME).

Essa idéia é estendida no algoritmo de maximização de expectativa generalizada (GEM), no qual se busca um aumento na função objetivo F para ambas etapas E e M. O GEM é desenvolvido em um ambiente distribuído e mostra resultados promissores.

Também é possível considerar o algoritmo EM como uma subclasse do algoritmo MM (Maiorizar/Minimizar ou Minorizar Maximizar, dependendo do contexto) e, portanto, pode usar qualquer mecanismo desenvolvido para caso mais geral.

Algoritmo α-EM

A função Q usada no algoritmo EM é baseada no logaritmo da verossimilhança. Portanto, é considerado como o algoritmo log-EM. O uso da verossimilhança logarítmica pode ser generalizado ao da razão de verossimilhança α-log. Então, a razão de verossimilhança α-log dos dados observados pode ser expressa exatamente como igualdade usando a função Q da razão de verossimilhança α-log e a divergência α. A obtenção dessa função Q é uma etapa E generalizada. Sua maximização é uma etapa M generalizada. Esse par é chamado de algoritmo α-EM que contém o algoritmo log-EM como sua subclasse. Dessa forma, o algoritmo α-EM de Yasuo Matsuyama é uma generalização exata do algoritmo log-EM. Não é necessário o cálculo do gradiente ou da matriz hessiana. O α-EM converge mais rapidamente que o algoritmo log-EM se um α apropriado for escolhido. O algoritmo α-EM leva a uma versão mais rápida do algoritmo de estimativa do modelo Hidden Markov α-HMM.

Relação com métodos variacionais de Bayes

O EM é um método parcialmente não-bayesiano de máxima verossimilhança. Seu resultado final fornece uma distribuição de probabilidade sobre as variáveis latentes (no estilo bayesiano) juntamente com uma estimativa pontual para θ (uma estimativa de máxima verossimilhança ou um modo posterior). Uma versão totalmente bayesiana disso pode ser desejada, fornecendo uma distribuição de probabilidade sobre θ e as variáveis latentes. A abordagem bayesiana da inferência é simplesmente tratar θ como outra variável latente. Nesse paradigma, a distinção entre os passos E e M desaparece. Se você estiver usando a aproximação Q fatorizada, como descrito acima ( Bayes variacionais , a solução pode iterar sobre cada variável latente (agora incluindo θ) e otimizá-las uma por vez. Agora, são necessárias k etapas por iteração, onde k é o número de variáveis latentes. Para modelos gráficos, é fácil fazer isso, pois o novo Q de cada variável depende apenas de seu cobertor de Markov; portanto, a passagem de mensagens local pode ser usada para inferência eficiente.

Interpretação geométrica

Na geometria da informação, a etapa E e a etapa M são interpretadas como projeções sob conexões afins duplas, chamadas de conexão e e conexão m; a divergência Kullback-Leibler também pode ser entendida nesses termos.

Exemplos

Mistura de gaussianas

Comparação de k-means e EM em dados artificiais. Usando as variâncias, o algoritmo EM pode descrever exatamente as distribuições normais, enquanto k-means divide os dados em células Voronoi . O centro do cluster é indicado pelo símbolo maior e mais claro.

Uma animação demonstrando o algoritmo EM ajustando um modelo de mistura Gaussiana de dois componentes ao conjunto de dados Old Faithful . O algoritmo passa de uma inicialização aleatória para convergência.

Tome $\mathbf {x} =(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})$ como uma amostra de $n$ observações independentes de uma mistura de duas distribuições normais multivariadas de dimensão $d$, e $\mathbf {z} =(z_{1},z_{2},\ldots ,z_{n})$ como as variáveis latentes que determinam o componente do qual a observação se origina.

$X_{i}\mid (Z_{i}=1)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{1},\Sigma _{1})$ e $X_{i}\mid (Z_{i}=2)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{2},\Sigma _{2}),$

Onde

$\operatorname {P} (Z_{i}=1)=\tau _{1}\,$ e $\operatorname {P} (Z_{i}=2)=\tau _{2}=1-\tau _{1}.$

O objetivo é estimar os parâmetros desconhecidos que representam o valor da mistura entre as gaussianas e as médias e covariâncias de cada um:

$\theta ={\big (}{\boldsymbol {\tau }},{\boldsymbol {\mu }}_{1},{\boldsymbol {\mu }}_{2},\Sigma _{1},\Sigma _{2}{\big )},$

onde a função de probabilidade de dados incompletos é

$L(\theta ;\mathbf {x} )=\prod _{i=1}^{n}\sum _{j=1}^{2}\tau _{j}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j}),$

e a função de probabilidade de dados completos é

$L(\theta ;\mathbf {x} ,\mathbf {z} )=p(\mathbf {x} ,\mathbf {z} \mid \theta )=\prod _{i=1}^{n}\prod _{j=1}^{2}\ [f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})\tau _{j}]^{\mathbb {I} (z_{i}=j)},$

ou

$L(\theta ;\mathbf {x} ,\mathbf {z} )=\exp \left\{\sum _{i=1}^{n}\sum _{j=1}^{2}\mathbb {I} (z_{i}=j){\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}\right\},$

Onde $\mathbb {I}$ é uma função indicadora e $f$ é a função de densidade de probabilidade de uma curva normal multivariada.

Na última igualdade, para cada i, um indicador $\mathbb {I} (z_{i}=j)$ é igual a 0 e um indicador é igual a 1. A soma interna reduz-se assim a um termo.

Etapa E

Dada a atual estimativa dos parâmetros q ^(t), a distribuição condicional de Z _I é determinada (pelo teorema de Bayes) como sendo ser proporcional a altura do normal de densidade ponderadas por τ:

$T_{j,i}^{(t)}:=\operatorname {P} (Z_{i}=j\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})={\frac {\tau _{j}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j}^{(t)},\Sigma _{j}^{(t)})}{\tau _{1}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{1}^{(t)},\Sigma _{1}^{(t)})+\tau _{2}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{2}^{(t)},\Sigma _{2}^{(t)})}}.$

Essas são chamadas de "probabilidades de associação", que normalmente são consideradas a saída (output) da etapa E (embora essa não seja a função Q abaixo).

Essa etapa E corresponde à configuração desta função para Q:

${\begin{aligned}Q(\theta \mid \theta ^{(t)})&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} ,\mathbf {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} ,\mathbf {Z} )]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} ,\mathbf {\theta } ^{(t)}}[\log \prod _{i=1}^{n}L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} ,\mathbf {\theta } ^{(t)}}[\sum _{i=1}^{n}\log L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\sum _{i=1}^{n}\operatorname {E} _{Z_{i}\mid \mathbf {X} ;\mathbf {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} _{i},Z_{i})]\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}P(Z_{i}=j\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})\log L(\theta _{j};\mathbf {x} _{i},j)\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}T_{j,i}^{(t)}{\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}.\end{aligned}}$

A expectativa de $\log L(\theta ;\mathbf {x} _{i},Z_{i})$ dentro da soma é tomada em relação à função de densidade de probabilidade $P(Z_{i}\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})$, que pode ser diferente para cada $\mathbf {x} _{i}$ do conjunto de treinamento. Tudo na etapa E é conhecido antes da etapa ser executada, exceto $T_{j,i}$, que é calculado de acordo com a equação no início da seção da etapa E.

Essa expectativa condicional completa não precisa ser calculada em uma única etapa, porque τ e μ / Σ aparecem em termos lineares separados e, portanto, podem ser maximizados independentemente.

Etapa M

Sendo Q ( θ | θ ^{( t )} ) de forma quadrática, significa que a determinação dos valores que maximizam de θ é direta. Além disso, τ, ( μ ₁, Σ ₁ ) e ( μ ₂, Σ ₂ ) podem ser maximizados independentemente, uma vez que todos aparecem em termos lineares separados.

Para começar, considere τ, que tem a restrição τ ₁ + τ ₂ = 1:

${\begin{aligned}{\boldsymbol {\tau }}^{(t+1)}&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ Q(\theta \mid \theta ^{(t)})\\&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ \left\{\left[\sum _{i=1}^{n}T_{1,i}^{(t)}\right]\log \tau _{1}+\left[\sum _{i=1}^{n}T_{2,i}^{(t)}\right]\log \tau _{2}\right\}.\end{aligned}}$

Ele tem a mesma forma que o MLE para a distribuição binomial, portanto

$\tau _{j}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{j,i}^{(t)}}{\sum _{i=1}^{n}(T_{1,i}^{(t)}+T_{2,i}^{(t)})}}={\frac {1}{n}}\sum _{i=1}^{n}T_{j,i}^{(t)}.$

Para as próximas estimativas de ( μ ₁, Σ ₁ ):

${\begin{aligned}({\boldsymbol {\mu }}_{1}^{(t+1)},\Sigma _{1}^{(t+1)})&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}Q(\theta \mid \theta ^{(t)})\\&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}\sum _{i=1}^{n}T_{1,i}^{(t)}\left\{-{\tfrac {1}{2}}\log |\Sigma _{1}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})^{\top }\Sigma _{1}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})\right\}\end{aligned}}.$

Ele tem a mesma forma que um MLE ponderado para uma distribuição normal, portanto

${\boldsymbol {\mu }}_{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}$ e $\Sigma _{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}$

e, por simetria,

${\boldsymbol {\mu }}_{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}$ e $\Sigma _{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}.$

Conclusão

Conclua o processo iterativo se $E_{Z\mid \theta ^{(t)},\mathbf {x} }[\log L(\theta ^{(t)};\mathbf {x} ,\mathbf {Z} )]\leq E_{Z\mid \theta ^{(t-1)},\mathbf {x} }[\log L(\theta ^{(t-1)};\mathbf {x} ,\mathbf {Z} )]+\varepsilon$ para $\varepsilon$ menor que algum limite predefinido.

Generalização

O algoritmo ilustrado acima pode ser generalizado para misturas de mais de duas distribuições normais multivariadas.

Alternativas

O algoritmo de EM converge para um ótimo local, que não é necessariamente o ponto ótimo global. Portanto, existe uma necessidade de métodos alternativos para a aprendizagem garantida, especialmente no cenário de alta dimensão. Existem alternativas ao EM com melhores garantias de consistência, denominadas abordagens baseadas no momento ou as chamadas técnicas espectrais.

Leitura adicional

• Hogg, Robert; McKean, Joseph; Craig, Allen (2005). Introduction to Mathematical Statistics. Pearson Prentice Hall. Upper Saddle River, NJ: [s.n.] pp. 359–364 
• Dellaert (2002). «The Expectation Maximization Algorithm». CiteSeerX 10.1.1.9.9735  gives an easier explanation of EM algorithm as to lowerbound maximization.
• Bishop, Christopher M. (2006). Pattern Recognition and Machine Learning. Springer. [S.l.: s.n.] ISBN 978-0-387-31073-2 
• «Theory and Use of the EM Algorithm». Foundations and Trends in Signal Processing. 4: 223–296. 2010. CiteSeerX 10.1.1.219.6830. doi:10.1561/2000000034  A well-written short book on EM, including detailed derivation of EM for GMMs, HMMs, and Dirichlet.
• Bilmes (1998). «A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models». CiteSeerX 10.1.1.28.613  includes a simplified derivation of the EM equations for Gaussian Mixtures and Gaussian Mixture Hidden Markov Models.
• McLachlan, Geoffrey J.; Krishnan, Thriyambakam (2008). The EM Algorithm and Extensions. Wiley 2nd ed. Hoboken: [s.n.] ISBN 978-0-471-20170-0 

Ligações externas

• Várias demonstrações 1D, 2D e 3D de EM, juntamente com a Modelagem de Mistura, são fornecidas como parte das atividades e applets SOCR emparelhados. Esses applets e atividades mostram empiricamente as propriedades do algoritmo EM para estimativa de parâmetros em diversas configurações.
• k-MLE: um algoritmo rápido para aprender modelos estatísticos de mistura
• Hierarquia de classes em C ++ (GPL) incluindo misturas gaussianas
• O livro on-line: teoria da informação, inferência e algoritmos de aprendizado, de David JC MacKay, inclui exemplos simples do algoritmo EM, como agrupar usando o algoritmo soft k -eans, e enfatiza a visualização variacional do algoritmo EM, conforme descrito em Capítulo 33.7 da versão 7.2 (quarta edição).
• Os algoritmos variacionais para inferência bayesiana aproximada, por MJ Beal, incluem comparações de EM com EM bayesiano variacional e derivações de vários modelos, incluindo HMMs bayesianos variacionais ( capítulos ).
• O algoritmo de maximização de expectativa: Um breve tutorial, Uma derivação independente do algoritmo EM de Sean Borman.
• O algoritmo EM, de Xiaojin Zhu.
• Algoritmo EM e variantes: um tutorial informal de Alexis Roche. Uma descrição concisa e muito clara do EM e muitas variantes interessantes.