Algoritmo de maximização de expectativa - Expectation–maximization algorithm

Em estatística , um algoritmo de maximização de expectativa ( EM ) é um método iterativo para encontrar estimativas de máxima verossimilhança (local) ou máxima a posteriori (MAP) de parâmetros em modelos estatísticos , onde o modelo depende de variáveis ​​latentes não observadas . A iteração EM alterna entre realizar uma etapa de expectativa (E), que cria uma função para a expectativa do log-verossimilhança avaliada usando a estimativa atual para os parâmetros, e uma etapa de maximização (M), que calcula os parâmetros maximizando o log- probabilidade encontrada na etapa E. Essas estimativas de parâmetros são então usadas para determinar a distribuição das variáveis ​​latentes na próxima etapa E.

Agrupamento EM de dados de erupção do Old Faithful . O modelo inicial aleatório (que, devido às diferentes escalas dos eixos, parece ser duas esferas muito planas e largas) é adequado aos dados observados. Nas primeiras iterações, o modelo muda substancialmente, mas depois converge para os dois modos 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 muitas vezes em circunstâncias especiais" por autores anteriores. Um dos primeiros é o método de contagem de genes para estimar frequências de alelos por Cedric Smith . Um tratamento muito detalhado do método EM para famílias exponenciais foi publicado por Rolf Sundberg em sua tese e em vários artigos após 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. 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 foi falha 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 afirmado por Dempster-Laird-Rubin.

Introdução

O algoritmo EM é usado para encontrar parâmetros de máxima verossimilhança (locais) de um modelo estatístico nos casos em que 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 conhecidos. Ou seja, existem valores ausentes entre os dados ou o modelo pode ser formulado de forma mais simples, assumindo a existência de mais pontos de dados não observados. Por exemplo, um modelo de mistura pode ser descrito de forma mais simples assumindo que cada ponto de dados observado tem um ponto de dados não observado correspondente, ou variável latente, especificando o componente de mistura ao qual cada ponto de dados pertence.

Encontrar uma solução de máxima verossimilhança normalmente requer tomar as derivadas da função de verossimilhança em relação a todos os valores desconhecidos, os parâmetros e as variáveis ​​latentes e, simultaneamente, resolver as equações resultantes. Em modelos estatísticos com variáveis ​​latentes, isso geralmente é impossível. Em vez disso, o resultado é tipicamente um conjunto de equações interligadas em que a solução dos parâmetros requer os valores das variáveis ​​latentes e vice-versa, mas substituir um conjunto de equações pelo outro produz uma equação insolúvel.

O algoritmo EM parte da observação de que existe uma maneira de resolver esses dois conjuntos de equações numericamente. Pode-se simplesmente escolher valores arbitrários para um dos dois conjuntos de incógnitas, usá-los para estimar o segundo conjunto e, em seguida, usar esses novos valores para encontrar uma estimativa melhor do primeiro conjunto e, em seguida, continuar alternando entre os dois até que os valores resultantes sejam ambos convergem para pontos fixos. Não é óbvio que isso funcionará, mas pode ser comprovado neste contexto. Além disso, pode ser provado que a derivada da probabilidade é (arbitrariamente próxima de) zero naquele ponto, o que por sua vez significa que o ponto é um máximo local ou um ponto de sela . Em geral, múltiplos máximos podem ocorrer, sem nenhuma garantia de que o máximo global será encontrado. Algumas probabilidades também possuem singularidades nelas, isto é, máximas sem sentido. Por exemplo, uma das soluções que podem ser encontradas por EM em um modelo de mistura envolve definir um dos componentes para ter variância zero e o parâmetro médio para o mesmo componente ser igual a um dos pontos de dados.

Descrição

Dado o modelo estatístico que gera um conjunto de dados observados, um conjunto de dados latentes não observados ou valores ausentes e um vetor de parâmetros desconhecidos , juntamente com uma função de verossimilhança , a estimativa de verossimilhança máxima (MLE) dos parâmetros desconhecidos é determinada pela maximização a probabilidade marginal dos dados observados ${\ displaystyle \ mathbf {X}}$ ${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$ ${\ displaystyle L ({\ boldsymbol {\ theta}}; \ mathbf {X}, \ mathbf {Z}) = p (\ mathbf {X}, \ mathbf {Z} \ mid {\ boldsymbol {\ theta}} )}$

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

No entanto, essa quantidade é freqüentemente intratável, uma vez que não é observada e a distribuição de é desconhecida antes de ser atingida . ${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$

O algoritmo EM busca encontrar o MLE da probabilidade marginal aplicando iterativamente estas duas etapas:

Passo expectativa (E passo) : Definir como o valor esperado do log função probabilidade de , no que diz respeito à corrente de distribuição condicional de dado e as estimativas actuais dos parâmetros : ${\ displaystyle Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}} ^ {(t)})}$${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {X}}$${\ displaystyle {\ boldsymbol {\ theta}} ^ {(t)}}$

${\ displaystyle 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:

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

Os modelos típicos aos quais o EM é aplicado são usados como uma variável latente, indicando pertencimento a um de um conjunto de grupos: ${\ displaystyle \ mathbf {Z}}$

1. Os pontos de dados observados podem ser discretos (tomando valores em um conjunto finito ou infinito contável) ou contínuos (tomando valores em um conjunto infinito incontável). Associado a cada ponto de dados pode haver um vetor de observações.${\ displaystyle \ mathbf {X}}$
2. Os valores ausentes (também conhecidos como variáveis ​​latentes ) são discretos , extraídos de um número fixo de valores e com uma variável latente por unidade observada.${\ displaystyle \ mathbf {Z}}$
3. Os parâmetros são contínuos e são 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 (ou seja, associados a todos os pontos de dados cuja variável latente correspondente tem esse valor).

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

A motivação é a seguinte. Se o valor dos parâmetros for conhecido, normalmente o valor das variáveis ​​latentes pode ser encontrado maximizando a probabilidade logarítmica sobre todos os valores possíveis de , seja simplesmente iterando sobre ou por meio de um algoritmo como o algoritmo Baum-Welch para Markov oculto modelos . Por outro lado, se soubermos o valor das variáveis ​​latentes , podemos encontrar uma estimativa dos parâmetros com bastante facilidade, normalmente simplesmente agrupando os pontos de dados observados de acordo com o valor da variável latente associada e calculando a média dos valores, ou alguma função do valores, dos pontos em cada grupo. Isso sugere um algoritmo iterativo, no caso em que e são desconhecidos: ${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle \ mathbf {Z}}$

1. Primeiro, inicialize os parâmetros com alguns valores aleatórios.${\ displaystyle {\ boldsymbol {\ theta}}}$
2. Calcule a probabilidade de cada valor possível de , dado .${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$
3. Em seguida, use os valores recém-calculados de para calcular uma estimativa melhor para os parâmetros .${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$
4. Repita as etapas 2 e 3 até a convergência.

O algoritmo, conforme descrito anteriormente, aproxima-se monotonicamente de um mínimo local da função de custo.

Propriedades

Falar de um passo de expectativa (E) é um pouco incorreto . O que são calculados no primeiro passo são os parâmetros fixos, dados dependentes da função Q . Uma vez que os parâmetros de Q são conhecidos, ele é totalmente determinado e maximizado na segunda (M) etapa de um algoritmo EM.

Embora uma iteração EM aumente a função de verossimilhança dos dados observados (isto é, marginal), não existe garantia de que a sequência converge para um estimador de verossimilhança máxima . Para distribuições multimodais , isso significa que um algoritmo EM pode convergir para um máximo local da função de verossimilhança de dados observada, dependendo dos valores iniciais. Uma variedade de abordagens heurísticas ou metaheurísticas existe para escapar de um máximo local, como escalada com reinício aleatório (começando com várias estimativas iniciais aleatórias θ ^{( t )} ) ou aplicando métodos de recozimento simulado .

EM é especialmente útil quando a probabilidade é uma família exponencial : a etapa E se torna a soma das expectativas de estatísticas suficientes e a etapa M envolve a maximização de uma função linear. Nesse caso, geralmente é possível derivar atualizações de expressão de forma fechada para cada etapa, usando a fórmula de Sundberg (publicada por Rolf Sundberg usando resultados não publicados de Per Martin-Löf e Anders Martin-Löf ).

O método EM foi modificado para calcular estimativas de máximo a posteriori (MAP) 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 gradiente descendente , gradiente conjugado ou variantes do algoritmo de Gauss-Newton . Ao contrário de EM, tais métodos normalmente requerem a avaliação da primeira e / ou segunda derivadas da função de verossimilhança.

Prova de correção

A maximização da expectativa funciona para melhorar, em vez de melhorar diretamente . Aqui é mostrado que melhorias para o primeiro implicam melhorias para o último. ${\ displaystyle Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}} ^ {(t)})}$${\ displaystyle \ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}})}$

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

${\ displaystyle \ 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 valores possíveis dos dados desconhecidos sob a estimativa do parâmetro atual , multiplicando ambos os lados por e somando (ou integrando) . O lado esquerdo é a expectativa de uma constante, então temos: ${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ theta ^ {(t)}}$${\ displaystyle p (\ mathbf {Z} \ mid \ mathbf {X}, {\ boldsymbol {\ theta}} ^ {(t)})}$${\ displaystyle \ mathbf {Z}}$

${\ displaystyle {\ begin {alinhados} \ 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 {alinhado}}}$

onde é definido pela soma negada que está substituindo. Esta última equação vale para todos os valores de inclusão , ${\ displaystyle H ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}} ^ {(t)})}$${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle {\ boldsymbol {\ theta}} = {\ boldsymbol {\ theta}} ^ {(t)}}$

${\ displaystyle \ 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á

${\ displaystyle \ 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)}),}$

No entanto, a desigualdade de Gibbs nos diz isso , então podemos concluir que ${\ displaystyle H ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}} ^ {(t)}) \ geq H ({\ boldsymbol {\ theta}} ^ {(t)} \ mid {\ boldsymbol {\ theta}} ^ {(t)})}$

${\ displaystyle \ 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, escolher melhorar faz com que melhore pelo menos o mesmo. ${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}} ^ {(t)})}$${\ displaystyle \ 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 descida de coordenadas . Considere a função:

${\ displaystyle 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

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

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

Então, as etapas no algoritmo EM podem ser vistas como:

Etapa de expectativa : escolha maximizar : ${\ displaystyle q}$${\ displaystyle F}$

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

Etapa de maximização : escolha maximizar : ${\ displaystyle \ theta}$${\ displaystyle F}$

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

Formulários

EM é freqüentemente usado para estimativa de parâmetros de modelos mistos , notadamente em genética quantitativa .

Em psicometria , o EM é uma ferramenta importante para estimar parâmetros de itens e habilidades latentes de modelos de teoria de resposta a itens .

Com a capacidade de lidar com dados perdidos e observar variáveis ​​não identificadas, o EM está se tornando uma ferramenta útil para precificar e gerenciar o risco de um portfólio.

O algoritmo EM (e sua variante mais rápido ordenou maximização expectativa subconjunto ) também é amplamente utilizado na imagem médica reconstrução, especialmente em tomografia de emissão de pósitrons , tomografia computadorizada por emissão de fóton único , e raios-x tomografia computadorizada . Veja abaixo outras variantes mais rápidas de EM.

Em engenharia estrutural , o algoritmo de Identificação Estrutural usando Maximização de Expectativas (STRIDE) é um método de saída apenas para identificar propriedades de vibração natural de um sistema estrutural usando dados de sensor (consulte Análise Modal Operacional ).

EM também é usado para agrupamento de dados . No processamento de linguagem natural , duas instâncias proeminentes do algoritmo são o algoritmo Baum – Welch para modelos de Markov ocultos e o algoritmo interno-externo para indução não supervisionada de gramáticas probabilísticas livres de contexto .

Algoritmos de filtragem e suavização EM

Um filtro de Kalman é normalmente usado para estimativa de estado on-line e um mais suave de variância mínima pode ser empregado para estimativa de estado off-line ou em lote. No entanto, essas soluções de variação mínima requerem estimativas dos parâmetros do modelo de espaço de estado. Algoritmos EM podem ser usados ​​para resolver problemas de estimativa de estado e parâmetro de junta.

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

E-step

Opere um filtro de Kalman ou um suavizador de variação mínima projetado com estimativas de parâmetros atuais para obter estimativas de estado atualizadas.

Passo M

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

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

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

onde estão as estimativas de saída escalar calculadas por um filtro ou mais suave a partir de N medições escalares . A atualização acima também pode ser aplicada para atualizar uma intensidade de ruído de medição de Poisson. Da mesma forma, para um processo auto-regressivo de primeira ordem, uma estimativa de variância de ruído de processo atualizada pode ser calculada por ${\ displaystyle {\ widehat {x}} _ {k}}$${\ displaystyle z_ {k}}$

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

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

${\ displaystyle {\ 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 às vezes lenta do algoritmo EM, como aqueles que usam gradiente conjugado e métodos de Newton modificados (Newton-Raphson). Além disso, EM pode ser usado com métodos de estimativa restritos.

O algoritmo de maximização de expectativa expandida por parâmetro (PX-EM) frequentemente fornece velocidade "usando um 'ajuste de covariância' para corrigir a análise do passo M, capitalizando informações extras capturadas nos dados completos imputados".

A maximização condicional de expectativa (ECM) substitui cada etapa M por uma sequência de etapas de maximização condicional (CM) em que cada parâmetro θ _i é maximizado individualmente, condicionalmente aos outros parâmetros permanecendo fixos. Ele mesmo pode ser estendido para o algoritmo de maximização condicional de expectativa (ECME) .

Esta ideia é posteriormente estendida no algoritmo de maximização de expectativa generalizada (GEM) , no qual se busca apenas um aumento na função objetivo F para ambos os passos E e M, conforme descrito na seção Como um procedimento de maximização-maximização . 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 (Majorize / Minimize ou Minorize / Maximize, dependendo do contexto) e, portanto, usar qualquer mecanismo desenvolvido no caso mais geral.

algoritmo α-EM

A função Q usada no algoritmo EM é baseada no log da verossimilhança. Portanto, é considerado o algoritmo log-EM. O uso da probabilidade de log pode ser generalizado para a razão de verossimilhança α-log. Então, a razão de verossimilhança α-log dos dados observados pode ser exatamente expressa 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 é um passo E generalizado. Sua maximização é um passo M generalizado. Esse par é chamado de algoritmo α-EM, que contém o algoritmo log-EM como sua subclasse. Assim, o algoritmo α-EM de Yasuo Matsuyama é uma generalização exata do algoritmo log-EM. Nenhum cálculo de gradiente ou matriz Hessiana é necessário. O α-EM mostra uma convergência mais rápida do que o algoritmo log-EM ao escolher um α apropriado. O algoritmo α-EM leva a uma versão mais rápida do algoritmo de estimação do modelo Hidden Markov α-HMM.

Relação com métodos variacionais de Bayes

EM é um método de máxima verossimilhança parcialmente não bayesiano. Seu resultado final fornece uma distribuição de probabilidade sobre as variáveis ​​latentes (no estilo bayesiano) junto 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 para inferência é simplesmente tratar θ como outra variável latente. Nesse paradigma, a distinção entre as etapas E e M desaparece. Se estiver usando a aproximação Q fatorada conforme descrito acima ( Bayes variacional ), a resolução pode iterar sobre cada variável latente (agora incluindo θ ) e otimizá-los um de cada vez. Agora, são necessários k passos por iteração, onde k é o número de variáveis ​​latentes. Para modelos gráficos, isso é fácil de fazer, pois o novo Q de cada variável depende apenas de seu cobertor de Markov , de modo que a passagem local de mensagens pode ser usada para inferência eficiente.

Interpretação geométrica

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

Exemplos

Mistura gaussiana

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

Uma animação que demonstra 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 a convergência.

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

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

Onde

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

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

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

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

${\ displaystyle 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 verossimilhança de dados completos é

${\ displaystyle 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

${\ displaystyle 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 é uma função indicadora e é a função de densidade de probabilidade de uma normal multivariada. ${\ displaystyle \ mathbb {I}}$${\ displaystyle f}$

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

Passo E

Dada nossa estimativa atual dos parâmetros θ ^{( t )} , a distribuição condicional de Z _i é determinada pelo teorema de Bayes como sendo a altura proporcional da densidade normal ponderada por τ :

${\ displaystyle 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)})}}.}$

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

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

${\ displaystyle {\ begin {alinhados} 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} \ soma _ {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 {alinhado}}}$

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

Esta expectativa condicional completa não precisa ser calculada em uma etapa, porque τ e μ / Σ aparecem em termos lineares separados e, portanto, podem ser maximizados de forma independente.

Passo M

Q ( θ  |  θ ^{( t )} ) sendo quadrático na forma significa que determinar os valores de maximização de θ é relativamente simples. 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:

${\ displaystyle {\ begin {align} {\ boldsymbol {\ tau}} ^ {(t + 1)} & = {\ underset {\ boldsymbol {\ tau}} {\ operatorname {arg \, max}}} \ Q (\ theta \ mid \ theta ^ {(t)}) \\ & = {\ underset {\ boldsymbol {\ tau}} {\ operatorname {arg \, max}}} \ \ left \ {\ left [\ soma _ {i = 1} ^ {n} T_ {1, i} ^ {(t)} \ direita] \ log \ tau _ {1} + \ esquerda [\ sum _ {i = 1} ^ {n} T_ {2, i} ^ {(t)} \ right] \ log \ tau _ {2} \ right \}. \ End {alinhado}}}$

Tem a mesma forma que o MLE para a distribuição binomial , então

${\ displaystyle \ 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 ( μ ₁ , Σ ₁ ):

${\ displaystyle {\ begin {align} ({\ boldsymbol {\ mu}} _ {1} ^ {(t + 1)}, \ Sigma _ {1} ^ {(t + 1)}) & = {\ sublinhado {{\ 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 {alinhado}}.}$

Tem a mesma forma de um MLE ponderado para uma distribuição normal, então

${\ displaystyle {\ 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 ${\ displaystyle \ 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,

${\ displaystyle {\ 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 ${\ displaystyle \ 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)}}}.}$

Terminação

Concluir o processo iterativo se para abaixo de um limiar pré-definido. ${\ displaystyle 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}$${\ displaystyle \ varepsilon}$

Generalização

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

Regressão truncada e censurada

O algoritmo EM foi implementado no caso em que existe um modelo de regressão linear subjacente explicando a variação de alguma quantidade, mas onde os valores realmente observados são versões censuradas ou truncadas daqueles representados no modelo. Casos especiais desse modelo incluem observações censuradas ou truncadas de uma distribuição normal .

Alternativas

EM tipicamente converge para um ótimo local, não necessariamente o ótimo global, sem limite na taxa de convergência em geral. É possível que seja arbitrariamente pobre em dimensões altas e pode haver um número exponencial de ótimos locais. Portanto, existe a necessidade de métodos alternativos para a aprendizagem garantida, especialmente no ambiente de alta dimensão. Alternativas para EM existem com melhores garantias de consistência, que são chamadas de abordagens baseadas em momentos ou as chamadas técnicas espectrais . Abordagens baseadas em momentos para aprender os parâmetros de um modelo probabilístico são de crescente interesse recentemente, uma vez que desfrutam de garantias como convergência global sob certas condições, ao contrário do EM, que é frequentemente atormentado pelo problema de ficar preso em ótimos locais. Algoritmos com garantias de aprendizagem podem ser derivados para uma série de modelos importantes, como modelos de mistura, HMMs etc. Para esses métodos espectrais, não ocorrem ótimos locais espúrios e os parâmetros verdadeiros podem ser estimados de forma consistente sob algumas condições de regularidade.

Veja também

• distribuição de mistura
• distribuição composta
• estimativa de densidade
• espectroscopia de absorção total
• O algoritmo EM pode ser visto como um caso especial do algoritmo de minimização de majoração (MM) .

Referências

Leitura adicional

• Hogg, Robert; McKean, Joseph; Craig, Allen (2005). Introdução à Estatística Matemática . Upper Saddle River, NJ: Pearson Prentice Hall. pp. 359–364.
• Dellaert, Frank (2002). "O algoritmo de maximização da expectativa". CiteSeerX  10.1.1.9.9735 . Citar diário requer |journal=( ajuda ) fornece uma explicação mais fácil do algoritmo EM quanto à maximização de limites inferiores.
• Bispo, Christopher M. (2006). Reconhecimento de padrões e aprendizado de máquina . Springer. ISBN 978-0-387-31073-2.
• Gupta, MR; Chen, Y. (2010). "Teoria e uso do algoritmo EM". Fundamentos e tendências em processamento de sinais . 4 (3): 223–296. CiteSeerX  10.1.1.219.6830 . doi : 10.1561 / 2000000034 . Um pequeno livro bem escrito sobre EM, incluindo derivação detalhada de EM para GMMs, HMMs e Dirichlet.
• Bilmes, Jeff (1998). "Um tutorial suave do algoritmo EM e sua aplicação à estimativa de parâmetros para modelos de mistura gaussiana e Markov oculto". CiteSeerX  10.1.1.28.613 . Citar diário requer |journal=( ajuda ) inclui uma derivação simplificada das equações EM para misturas gaussianas e modelos ocultos de Markov de mistura gaussiana.
• McLachlan, Geoffrey J .; Krishnan, Thriyambakam (2008). The EM Algorithm and Extensions (2ª ed.). Hoboken: Wiley. ISBN 978-0-471-20170-0.

links externos

• Várias demonstrações 1D, 2D e 3D de EM, juntamente com a Modelagem de Mistura, são fornecidas como parte das atividades e miniaplicativos 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 de mistura estatística
• Hierarquia de classes em C ++ (GPL) incluindo misturas gaussianas
• O livro on-line: Teoria da Informação, Inferência e Algoritmos de Aprendizagem , de David JC MacKay inclui exemplos simples do algoritmo EM, como clustering usando o algoritmo soft k -means, e enfatiza a visão variacional do algoritmo EM, conforme descrito em Capítulo 33.7 da versão 7.2 (quarta edição).
• Algoritmos Variacionais para Inferência Bayesiana Aproximada , de MJ Beal, inclui comparações de EM para EM Bayesiano Variacional e derivações de vários modelos, incluindo HMMs Bayesianos Variacionais ( capítulos ).
• O algoritmo de maximização da expectativa: um breve tutorial , uma derivação independente do algoritmo EM por 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.