Qual é a diferença entre os algoritmos forward-backward e Viterbi?

Um pouco de contexto primeiro talvez esclareça as coisas um pouco.

Ao falar sobre HMMs (modelos de Markov ocultos), geralmente há 3 problemas a serem considerados:

1. Problema de avaliação

   • O problema de avaliação responde à pergunta: qual é a probabilidade de que uma sequência particular de símbolos seja produzida por um modelo particular?
   • Para avaliação, usamos dois algoritmos: o algoritmo de avanço ou o algoritmo de retrocesso (NÃO os confunda com o algoritmo de avanço / retrocesso).

2. Problema de decodificação

   • O problema de decodificação responde à pergunta: Dada uma sequência de símbolos (suas observações) e um modelo, qual é a sequência de estados mais provável que produziu a sequência.
   • Para decodificação, usamos o algoritmo de Viterbi .

3. Problema de treinamento

   • O problema de treinamento responde à pergunta: dada uma estrutura de modelo e um conjunto de sequências, encontre o modelo que melhor se ajusta aos dados .
   • Para este problema, podemos usar os seguintes 3 algoritmos:
     1. MLE (estimativa de máxima verossimilhança)
     2. Treinamento Viterbi (NÃO confunda com decodificação Viterbi)
     3. Baum Welch = algoritmo para frente e para trás

Para resumir, você usa o algoritmo de Viterbi para o problema de decodificação e Baum Welch / Forward-backward quando você treina seu modelo em um conjunto de sequências.

Baum Welch funciona da seguinte maneira.

Para cada sequência no conjunto de sequências de treinamento.

1. Calcule probabilidades progressivas com o algoritmo progressivo
2. Calcule probabilidades regressivas com o algoritmo retrógrado
3. Calcule as contribuições da sequência atual para as transições do modelo, calcule as contribuições da sequência atual para as probabilidades de emissão do modelo.
4. Calcule os novos parâmetros do modelo (probabilidades iniciais, probabilidades de transição, probabilidades de emissão )
5. Calcule o nova probabilidade de log do modelo
6. Pare quando a mudança na probabilidade de log for menor que um determinado limite ou quando um número máximo de iterações for passado.

Se você precisar uma descrição completa das equações para decodificação de Viterbi e o algoritmo de treinamento, deixe-me saber e eu posso apontar a direção certa.

Comentários

• Olá . Se salvarmos o caminho, durante a avaliação usando o algoritmo de encaminhamento, isso torna redundante o uso do algoritmo de Viterbi na decodificação?

Acho que estes dois slides seguintes de {2} são realmente bons para situar a frente algoritmos -backward e Viterbi entre todos os outros algoritmos típicos usados com HMM:

Observações :

• $ x $ é a (s) emissão (ões) observada (s), $ \ pi $ são os parâmetros do HMM.
• caminho = uma sequência de emissões
• decodificação = inferência
• aprendizagem = treinamento = estimativa de parâmetro
• Alguns artigos (por exemplo, {1}) afirmam que Baum – Welch é o mesmo que algoritmo para frente e para trás, mas Eu agr ee com Masterfool e Wikipedia: Baum – Welch é um algoritmo de maximização de expectativa que usa o algoritmo para frente e para trás. As duas ilustrações também distinguem Baum – Welch do algoritmo para frente e para trás.

Referências:

• {1} Lember, Jüri e Alexey Koloydenko. “O treinamento Viterbi ajustado para modelos de Markov ocultos.” Bernoulli 14, no. 1 (2008): 180-206.
• {2} 6.047 / 6.878 Biologia Computacional: Genomas, Redes, Evolução (Outono de 2012) Aula 07 – HMMs II (2012-09-29) http://stellar.mit.edu/S/course/6/fa12/6.047/courseMaterial/topics/topic2/lectureNotes/Lecture07_HMMsIIb_6up/Lecture07_HMMsIIb_6up.pdf (Manolis Kellis):

A resposta de Morat “é falsa em um ponto: Baum -Welch é um algoritmo de maximização de expectativa, usado para treinar os parâmetros de um HMM. Ele usa o algoritmo para frente e para trás durante cada iteração. O algoritmo para frente e para trás é, na verdade, apenas uma combinação dos algoritmos para frente e para trás: uma passagem para frente, uma passagem para trás. Por conta própria, o algoritmo para frente e para trás 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

@Yaroslav Bulatov tinha uma resposta precisa. Eu adicionaria um exemplo dela para dizer ao diferenças entre algoritmos forward-backward e Viterbi.

Suponha que temos um HMM (da página HMM da Wikipedia). Observe, o modelo já foi fornecido, então não há aprendizagem com a tarefa de dados aqui.

Suponha que nossos dados sejam uma sequência de comprimento 4. (Walk, Shop, Walk, Clean). Dois algoritmos fornecem coisas diferentes.

• O algoritmo de avanço para trás dará o probabi lidade de cada estado oculto . Aqui está um exemplo. Observe que cada coluna da tabela soma $ 1 $.

• O algoritmo de Viterbi fornecerá a sequência mais provável de estados ocultos . Aqui está um exemplo. Observe que também há uma probabilidade associada a essa sequência de estados ocultos. Esta sequência possui max prob. sobre todas as outras sequências (por exemplo, $ 2 ^ 4 = 16 $ sequências de todos os Sunny para todos os Rainy).

Aqui estão alguns R código da demonstração

library(HMM) # in education setting, # hidden state: Rainy and Sunny # observation: Walk, Shop, Clean # state transition P <- as.matrix(rbind(c(0.7,0.3), c(0.4,0.6))) # emission prob R <- as.matrix(rbind(c(0.1, 0.4, 0.5), c(0.6,0.3, 0.1))) hmm = initHMM(States=c("Rainy","Sunny"), Symbols=c("Walk","Shop", "Clean"), startProbs=c(0.6,0.4), transProbs=P, emissionProbs=R) hmm obs=c("Walk","Shop","Walk", "Clean") print(posterior(hmm,obs)) print(viterbi(hmm, obs))