Modelos ocultos de Markov e algoritmo de maximização de expectativas

10

Alguém pode esclarecer como os modelos de Markov ocultos estão relacionados à maximização de expectativas? Passei por muitos links, mas não consegui ter uma visão clara.

Obrigado!

thchand
fonte

Respostas:

12

O algoritmo EM (maximização de expectativa) é um algoritmo geral para otimização da função de probabilidade nos casos em que o modelo é especificado probabilisticamente em termos de um componente observado e um não observado (latente). Os HMMs (modelos de Markov ocultos) são modelos desse formato porque possuem um componente não observado, os estados ocultos e as observações reais são frequentemente chamadas de emissões na terminologia do HMM. Portanto, os HMMs formam uma classe de modelos para os quais o algoritmo EM pode ser útil.

Em geral, se o modelo consistir em dois componentes , que assumimos assumir valores em um espaço finito por simplicidade, e se a especificação do modelo probabilístico consistir nas probabilidades de pontos comuns , parametrizado por , a probabilidade de observar apenas é (X,Y)pθ(x,y)θX=x

Lx(θ)=ypθ(x,y).
Embora a soma pareça inocente, não é. Para os HMMs, a soma será sobre todas as transições possíveis entre os estados ocultos, que rapidamente se tornam um número formidável quando o comprimento da sequência observada aumenta. Felizmente, existem algoritmos para HMMs (para frente e para trás) para o cálculo rápido da probabilidade, e a probabilidade pode, em princípio, ser conectada a qualquer algoritmo de otimização de uso geral para a estimativa da probabilidade máxima de . A alternativa é o algoritmo EM. Este é um algoritmo que alterna iterativamente entreθ
  • a etapa E , que é um cálculo de uma expectativa condicional, dado o observado sob a estimativa atual dexθ
  • o passo M , que é uma maximização

O algoritmo EM faz mais sentido se as duas etapas acima puderem ser implementadas de maneira computacionalmente eficiente, por exemplo, quando fechamos expressões de formulário para a expectativa condicional e a maximização.

Historicamente, o algoritmo EM geral é creditado a Dempster, Laird e Rubin , que provaram em seu artigo de 1977, entre outras coisas, que o algoritmo leva a uma sequência de parâmetros com valores de probabilidade cada vez maiores. Eles também cunharam o termo "algoritmo EM". Curiosamente, o algoritmo EM para HMMs já foi descrito em 1970 por Baum et al. , e também é frequentemente referido como o algoritmo de Baum-Welch na literatura do HMM (não sei exatamente o que Welch fez ...).

NRH
fonte
3
Welch inventou o que agora é chamado algoritmo Baum-Welch (ele chama de "a parte fácil"); Baum prova matematicamente que o algoritmo funciona ("a parte difícil"). Consulte cursos.cs.tamu.edu/rgutier/cpsc689_s07/welch2003baumWelch.pdf para obter detalhes exatos.
Mikhail Korobov 25/03
@MikhailKorobov, obrigado por esta referência informativa.
NRH
2

A Maximização de Expectativas é um método iterativo usado para realizar inferência estatística em uma variedade de modelos estatísticos generativos diferentes, por exemplo, uma mistura de gaussianos e outros modelos do tipo de rede bayesiana. A única conexão é que os HMMs também são redes bayesianas. Mas provavelmente não se usaria EM nos HMMs porque existe um algoritmo exato para inferência dentro dos HMMs chamado algoritmo de Viterbi. Portanto, embora se possa usar o EM para realizar inferência em um HMM, você não faria isso porque não há motivo para isso.

William
fonte
4
Isso não é totalmente exato porque você mistura dois tipos diferentes de "inferência". EM é um algoritmo para estimativa de parâmetros desconhecidos, Viterbi é o algoritmo para calcular a sequência mais provável de estados ocultos. Você usaria EM para HMMs para estimativa de parâmetros. Dei mais detalhes sobre o algoritmo EM com referências históricas que explicam a relação entre HMMs e EM em minha resposta.
NRH 14/09/11
0

No HMM, tentamos estimar principalmente três parâmetros:

  1. As probabilidades iniciais do estado. Este é um vetor com elementos, onde é o número de estados.KK

  2. A matriz de transição. Esta é uma matriz quadrada de tamanho .K×K

  3. As probabilidades condicionais de observar um item, condicionadas por algum estado. Essa também é uma matriz de tamanho , em que é o número de observações.K×NN

Agora, a parte EM vem quando você tenta estimar as quantidades / parâmetros mencionados acima. Começando com algum palpite aleatório, a probabilidade das observações é avaliada e os parâmetros são ajustados iterativamente até obtermos a máxima probabilidade. Assim, através do HMM, modelamos alguns processos e, para isso, precisamos introduzir alguns parâmetros. Para estimar os parâmetros, EM é renderizado.

Esta é uma resposta muito breve. A implementação do EM requer vários outros subproblemas para resolver por meio de uma série de técnicas. Para uma compreensão aprofundada, o artigo tutorial clássico Rabiner é altamente recomendado.

Riaz Khan
fonte