Estou tentando entender bem o algoritmo EM, para poder implementá-lo e usá-lo. Passei um dia inteiro lendo a teoria e um artigo em que o EM é usado para rastrear uma aeronave usando as informações de posição provenientes de um radar. Honestamente, acho que não entendo completamente a idéia subjacente. Alguém pode me apontar para um exemplo numérico que mostra algumas iterações (3-4) do EM para um problema mais simples (como estimar os parâmetros de uma distribuição gaussiana ou uma sequência de uma série sinusoidal ou ajustar uma linha).
Mesmo que alguém possa me indicar um pedaço de código (com dados sintéticos), eu posso tentar percorrer o código.
Respostas:
Esta é uma receita para aprender EM com um exemplo prático e (na minha opinião) muito intuitivo 'Coin-Toss':
Leia este pequeno tutorial sobre EM de Do e Batzoglou. Este é o esquema no qual o exemplo do sorteio é explicado:
Você pode ter pontos de interrogação em sua mente, principalmente em relação à origem das probabilidades na etapa Expectativa. Veja as explicações nesta página de troca de pilhas matemáticas .
Veja / execute este código que escrevi em Python que simula a solução para o problema do sorteio no artigo do tutorial 1 do EM:
fonte
pA_heads[j+1]
epA_heads[j]
e 2) a mudança entrepB_heads[j+1]
epB_heads[j]
. E é preciso o máximo das duas alterações. Por exemplo, seDelta_A=0.001
eDelta_B=0.02
, a melhoria da etapaj
paraj+1
será0.02
.delta
.Parece que sua pergunta tem duas partes: a ideia subjacente e um exemplo concreto. Começarei com a ideia subjacente e, em seguida, vinculo a um exemplo na parte inferior.
EM é útil em Catch-22 situações em que parece que você precisa saber antes de poder calcular e você precisa saber antes de poder calcular .B B AA B B A
O caso mais comum com o qual as pessoas lidam é provavelmente a distribuição de misturas. Para o nosso exemplo, vejamos um modelo simples de mistura gaussiana:
E agora você está preso:
Se você soubesse o verdadeiro meio, poderia descobrir quais pontos de dados vieram de quais gaussianos. Por exemplo, se um ponto de dados tinha um valor muito alto, provavelmente vinha da distribuição com a média mais alta. Mas você não sabe quais são os meios, então isso não vai funcionar.
Se você soubesse de qual distribuição cada ponto veio, poderia estimar as médias das duas distribuições usando as médias amostrais dos pontos relevantes. Mas você realmente não sabe quais pontos atribuir a qual distribuição, portanto, isso também não funcionará.
Portanto, nenhuma das abordagens parece funcionar: você precisaria saber a resposta antes de poder encontrá-la e ficar preso.
O que o EM permite fazer é alternar entre essas duas etapas tratáveis, em vez de enfrentar todo o processo de uma só vez.
Você precisará começar com um palpite sobre os dois meios (embora seu palpite não precise necessariamente ser muito preciso, você precisa começar em algum lugar).
Se o seu palpite sobre os meios fosse preciso, você teria informações suficientes para executar a etapa no meu primeiro ponto acima e poderia (probabilisticamente) atribuir cada ponto de dados a um dos dois gaussianos. Mesmo sabendo que nosso palpite está errado, vamos tentar assim mesmo. E então, dadas as distribuições atribuídas a cada ponto, você pode obter novas estimativas para as médias usando o segundo ponto. Acontece que, cada vez que você percorre essas duas etapas, você está melhorando um limite inferior na probabilidade do modelo.
Isso já é bem legal: mesmo que as duas sugestões nos pontos acima não pareçam funcionar individualmente, você ainda pode usá-las juntas para melhorar o modelo. A verdadeira mágica do EM é que, após iterações suficientes, o limite inferior será tão alto que não haverá espaço entre ele e o máximo local. Como resultado, você otimizou localmente a probabilidade.
Portanto, você não apenas melhorou o modelo, mas encontrou o melhor modelo possível com atualizações incrementais.
Esta página da Wikipedia mostra um exemplo um pouco mais complicado (gaussianos bidimensionais e covariância desconhecida), mas a idéia básica é a mesma. Também inclui
R
código bem comentado para implementar o exemplo.No código, a etapa "Expectativa" (etapa E) corresponde ao meu primeiro ponto: descobrir qual gaussiano é responsável por cada ponto de dados, dados os parâmetros atuais de cada gaussiano. A etapa "Maximização" (etapa M) atualiza os meios e covariâncias, dadas essas atribuições, como no meu segundo item.
Como você pode ver na animação, essas atualizações permitem rapidamente que o algoritmo passe de um conjunto de estimativas terríveis para um conjunto de estimativas muito boas: realmente parece haver duas nuvens de pontos centradas nas duas distribuições gaussianas encontradas pela EM.
fonte
Aqui está um exemplo de Maximização de Expectativa (EM) usada para estimar a média e o desvio padrão. O código está em Python, mas deve ser fácil de seguir, mesmo que você não esteja familiarizado com o idioma.
A motivação para EM
Os pontos vermelho e azul mostrados abaixo são extraídos de duas distribuições normais diferentes, cada uma com uma média e desvio padrão específicos:
Para calcular aproximações razoáveis dos parâmetros "verdadeiro" de média e desvio padrão para a distribuição vermelha, poderíamos facilmente olhar para os pontos vermelhos e registrar a posição de cada um e, em seguida, usar as fórmulas familiares (e da mesma forma para o grupo azul) .
Agora considere o caso em que sabemos que existem dois grupos de pontos, mas não podemos ver qual ponto pertence a qual grupo. Em outras palavras, as cores estão ocultas:
Não é de todo óbvio como dividir os pontos em dois grupos. Agora somos incapazes de olhar apenas as posições e calcular estimativas para os parâmetros da distribuição vermelha ou azul.
É aqui que o EM pode ser usado para resolver o problema.
Usando EM para estimar parâmetros
Aqui está o código usado para gerar os pontos mostrados acima. Você pode ver as médias reais e os desvios padrão das distribuições normais das quais os pontos foram extraídos. As variáveis
red
eblue
mantêm as posições de cada ponto nos grupos vermelho e azul respectivamente:Se pudéssemos ver a cor de cada ponto, tentaríamos recuperar médias e desvios padrão usando as funções da biblioteca:
Mas como as cores estão ocultas, iniciaremos o processo EM ...
Primeiro, adivinhamos os valores para os parâmetros de cada grupo ( etapa 1 ). Essas suposições não precisam ser boas:
Suposições muito ruins - os meios parecem estar muito longe de qualquer "meio" de um grupo de pontos.
Para continuar com o EM e melhorar essas suposições, calculamos a probabilidade de cada ponto de dados (independentemente de sua cor secreta) aparecer sob essas suposições para a média e o desvio padrão ( etapa 2 ).
A variável
both_colours
contém cada ponto de dados. A funçãostats.norm
calcula a probabilidade do ponto em uma distribuição normal com os parâmetros fornecidos:Isso nos diz, por exemplo, que, com nossas suposições atuais, o ponto de dados em 1.761 tem muito mais probabilidade de ser vermelho (0,189) do que azul (0,00003).
Podemos transformar esses dois valores de probabilidade em pesos ( etapa 3 ) para que eles somarem 1 como a seguir:
Com nossas estimativas atuais e nossos pesos recém-calculados, agora podemos calcular novas estimativas, provavelmente melhores, para os parâmetros ( etapa 4 ). Precisamos de uma função para a média e uma função para o desvio padrão:
Eles parecem muito semelhantes às funções usuais ao desvio médio e padrão dos dados. A diferença é o uso de um
weight
parâmetro que atribui um peso a cada ponto de dados.Essa ponderação é a chave para o EM. Quanto maior o peso de uma cor em um ponto de dados, mais ele influencia as próximas estimativas para os parâmetros dessa cor. Por fim, isso tem o efeito de puxar cada parâmetro na direção certa.
As novas suposições são computadas com estas funções:
O processo EM é então repetido com essas novas suposições da etapa 2 em diante. Podemos repetir as etapas para um determinado número de iterações (digamos 20), ou até vermos os parâmetros convergirem.
Após cinco iterações, vemos nossas primeiras suposições ruins começarem a melhorar:
Após 20 iterações, o processo EM convergiu mais ou menos:
Para comparação, eis os resultados do processo EM comparados com os valores calculados onde as informações de cores não estão ocultas:
Nota: esta resposta foi adaptada da minha resposta no Stack Overflow aqui .
fonte
Seguindo a resposta de Zhubarb, implementei o exemplo de EM de "lançamento de moeda" de Do e Batzoglou no GNU R. Observe que eu uso a
mle
função dostats4
pacote - isso me ajudou a entender mais claramente como EM e MLE estão relacionados.fonte
Todas as opções acima parecem ótimos recursos, mas devo vincular a este ótimo exemplo. Apresenta uma explicação muito simples para encontrar os parâmetros para duas linhas de um conjunto de pontos. O tutorial é de Yair Weiss no MIT.
http://www.cs.huji.ac.il/~yweiss/emTutorial.pdf
http://www.cs.huji.ac.il/~yweiss/tutorials.html
fonte
A resposta dada por Zhubarb é ótima, mas infelizmente está em Python. Abaixo está uma implementação em Java do algoritmo EM executado no mesmo problema (apresentado no artigo de Do e Batzoglou, 2008). Adicionei alguns printfs à saída padrão para ver como os parâmetros convergem.
O código Java segue abaixo:
fonte
fonte
Bem, eu sugiro que você leia um livro sobre R de Maria L. Rizzo. Um dos capítulos contém o uso do algoritmo EM com um exemplo numérico. Lembro-me de passar pelo código para entender melhor.
Além disso, tente visualizá-lo do ponto de vista do cluster no começo. Elabore manualmente, um problema de agrupamento em que 10 observações são obtidas de duas densidades normais diferentes. Isso ajuda.Take a ajuda de R :)
fonte
Apenas no caso, eu escrevi uma implementação Ruby do exemplo de lançamento de moeda mencionado acima por Do & Batzoglou e produz exatamente os mesmos números que os mesmos parâmetros de entrada e . θ B = 0,5θA=0.6 θB=0.5
fonte