What is the difference between the forward-backward and Viterbi algorithms?

Question

I want to know what the differences between the forward-backward algorithm and the Viterbi algorithm for inference in hidden Markov models (HMM) are.

Answer 1

A bit of background first maybe it clears things up a bit.

When talking about HMMs (Hidden Markov Models) there are generally 3 problems to be considered:

1. Evaluation problem

   • Evaluation problem answers the question: what is the probability that a particular sequence of symbols is produced by a particular model?
   • For evaluation we use two algorithms: the forward algorithm or the backwards algorithm (DO NOT confuse them with the forward-backward algorithm).

2. Decoding problem

   • Decoding problem answers the question: Given a sequence of symbols (your observations) and a model, what is the most likely sequence of states that produced the sequence.
   • For decoding we use the Viterbi algorithm.

3. Training problem

   • Training problem answers the question: Given a model structure and a set of sequences, find the model that best fits the data.
   • For this problem we can use the following 3 algorithms:
     1. MLE (maximum likelihood estimation)
     2. Viterbi training(DO NOT confuse with Viterbi decoding)
     3. Baum Welch = forward-backward algorithm

To sum it up, you use the Viterbi algorithm for the decoding problem and Baum Welch/Forward-backward when you train your model on a set of sequences.

---

Baum Welch works in the following way.

For each sequence in the training set of sequences.

1. Calculate forward probabilities with the forward algorithm
2. Calculate backward probabilities with the backward algorithm
3. Calculate the contributions of the current sequence to the transitions of the model, calculate the contributions of the current sequence to the emission probabilities of the model.
4. Calculate the new model parameters (start probabilities, transition probabilities, emission probabilities)
5. Calculate the new log likelihood of the model
6. Stop when the change in log likelihood is smaller than a given threshold or when a maximum number of iterations is passed.

If you need a full description of the equations for Viterbi decoding and the training algorithm let me know and I can point you in the right direction.

Answer 2

Forward-Backward gives marginal probability for each individual state, Viterbi gives probability of the most likely sequence of states. For instance if your HMM task is to predict sunny vs. rainy weather for each day, Forward Backward would tell you the probability of it being "sunny" for each day, Viterbi would give the most likely sequence of sunny/rainy days, and the probability of this sequence.

Answer 3

I find these two following slides from {2} to be really good to situate the forward-backward and Viterbi algorithms amongst all other typical algorithms used with HMM:

Notes:

• $x$ is the observed emission(s), $\pi$ are the parameters of the HMM.
• path = a sequence of emissions
• decoding = inference
• learning = training = parameter estimation
• Some papers (e.g., {1}) claim that Baum–Welch is the same as forward–backward algorithm, but I agree with Masterfool and Wikipedia: Baum–Welch is an expectation-maximization algorithm that uses the forward–backward algorithm. The two illustrations also distinguish Baum–Welch from the forward–backward algorithm.

---

References:

• {1} Lember, Jüri, and Alexey Koloydenko. "The adjusted Viterbi training for hidden Markov models." Bernoulli 14, no. 1 (2008): 180-206.
• {2} 6.047/6.878 Computational Biology: Genomes, Networks, Evolution (Fall 2012) Lecture 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):

Answer 4

Morat's answer is false on one point: Baum-Welch is an Expectation-Maximization algorithm, used to train an HMM's parameters. It uses the forward-backward algorithm during each iteration. The forward-backward algorithm really is just a combination of the forward and backward algorithms: one forward pass, one backward pass. On its own, the forward-backward algorithm is not used for training an HMM's parameters, but only for smoothing: computing the marginal likelihoods of a sequence of states.

https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm

https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

Answer 5

@Yaroslav Bulatov had a precise answer. I would add one example of it to tell the differences between forward-backward and Viterbi algorithms.

Suppose we have an this HMM (from Wikipedia HMM page). Note, the model is already given, so there is no learning from data task here.

---

Suppose our data is a length 4 sequence. (Walk, Shop, Walk, Clean). Two algorithm will give different things.

• Forward backward algorithm will give the probability of each hidden states. Here is an example. Note, each column in the table sum up to $1$.

• Viterbi algorithm will give the most probable sequence of hidden states. Here is an example. Note, there is also a probability associated with this hidden state sequence. This sequence has max prob. over all other sequences (e.g., $2^4=16$ sequences from all Sunny to all Rainy).

---

Here is some R code for the demo

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))