Quero saber quais são as diferenças entre o algoritmo forward-backward e o algoritmo Viterbi para inferência em modelos ocultos de Markov (HMM).
44
Quero saber quais são as diferenças entre o algoritmo forward-backward e o algoritmo Viterbi para inferência em modelos ocultos de Markov (HMM).
Respostas:
Um pouco de fundo primeiro talvez esclareça um pouco as coisas.
Quando se fala de HMMs (Hidden Markov Models), geralmente existem 3 problemas a serem considerados:
Problema de avaliação
Problema de decodificação
Problema de treinamento
Para resumir, você usa o algoritmo Viterbi para o problema de decodificação e Baum Welch / Forward-backward quando treina seu modelo em um conjunto de seqüências.
Baum Welch funciona da seguinte maneira.
Para cada sequência no conjunto de sequências de treinamento.
Se você precisar de uma descrição completa das equações para a decodificação de Viterbi e o algoritmo de treinamento, deixe-me saber e eu posso apontá-lo na direção certa.
fonte
Para frente e para trás fornece probabilidade marginal para cada estado individual , Viterbi fornece probabilidade para a sequência mais provável de estados . Por exemplo, se sua tarefa do HMM é prever o tempo ensolarado versus chuvoso para cada dia, o Forward Backward diria a probabilidade de estar "ensolarado" para cada dia, Viterbi daria a sequência mais provável de dias ensolarados / chuvosos e os probabilidade desta sequência.
fonte
Eu acho esses dois slides a seguir de {2} realmente bons para situar os algoritmos forward-backward e Viterbi entre todos os outros algoritmos típicos usados com o HMM:
Notas:
Referências:
fonte
A resposta de Morat é falsa em um ponto: Baum-Welch é um algoritmo de Expectativa-Maximização, usado para treinar os parâmetros de um HMM. Ele usa o algoritmo de retroceder durante cada iteração. O algoritmo forward-backward é na verdade apenas uma combinação dos algoritmos forward e backward: uma passagem para frente, uma para trás. Por si só, o algoritmo de avanço / retrocesso não é usado para treinar os parâmetros de um HMM, mas apenas para suavizar: calcular as probabilidades marginais de uma sequência de estados.
https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm
https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm
fonte
@Yaroslav Bulatov teve uma resposta precisa. Eu adicionaria um exemplo disso para dizer as diferenças entre os algoritmos forward-backward e Viterbi.
Suponha que tenhamos este HMM (da página Wikipedia HMM). Observe que o modelo já foi fornecido, portanto, não há aprendizado com a tarefa de dados aqui.
Suponha que nossos dados sejam uma sequência de comprimento 4.
(Walk, Shop, Walk, Clean)
. Dois algoritmos fornecerão coisas diferentes.Sunny
Rainy
Aqui está um
R
código para a demonstraçãofonte