Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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

share|improve this question
2  
Would descriptions of the algortihms (here and here) answer your question or are you looking for something else? Are you wondering when to use which algorithm? Looking for a discussion of their respective merits? –  MånsT Jul 6 '12 at 8:05

2 Answers 2

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

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

  1. Evaluation problem. This 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. Given a sequence of symbols (your observations) and a model, what is the most likely sequence of states that produced the sequence. For this problem we use the Viterbi algorithm.
  3. Training problem. 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:

    • MLE (maximum likelihood estimation)
    • Viterbi training(do not confuse with Viterbi decoding)
    • Baum Welch = forward-backward algorithm

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.

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.

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.