What is the difference between Forward-backward algorithm and Viterbi algorithm?

Question

What is the difference between Forward-backward algorithm on n-gram model and Viterbi algorithm on Hidden Markov model (HMM)?

When I review the implementation of these two algorithms, only thing I found is that the transaction probability is coming from different probabilistic models.

Is there a difference between these 2 algorithms?

Jespersen

Answer 1

The Forward-Backward algorithm combines the forward step and the backward step to get the probability of being at each state at a specific time. Doing this for all time steps can therefore give us a sequence of individually most likely states at each time (although not guaranteed to be valid sequence, since it considers individual state at each step, and it can happen that the probability p(q_i -> q_j)=0 in the transition model), in other words:

, where

On the other hand, Viterbi algorithm finds the most likely state sequence given an observation sequence, by maximizing a different optimality criterion:

I suggest you refer to this well-known paper for a detailed explanation (see Problem #2):

LAWRENCE R. RABINER, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition

Manuel

Answer 2

Succinctly put:

Forward-Backward is used if only want to predict what the most likely token is at one particular time. It will take every possible sequence into account and average over them to find the most likely token at that time. So the sequence you will get back won't be a true sequence, but a collect of the most probable tokens when you consider all of the possible sequences.

Viterbi is used to find the most likely sequence of events. This will look at every sequence and simply select the sequence that is most likely.

Ventage

Answer 3

Take a look at the pages 262 - 264 of Rabiner's paper and it should all become clear. Here is a directly quoted answer -from this paper- to your question:

"...It should be noted that the Viterbi algorithm is similar (except for the backtracking step) in implementation to the forward calculation of the forward-backward algorithm (Equations 19-21). The major difference is the maximisation in (Equation 33a) over previous states, which is used in place of the summing procedure in (Equation 20)."

Secundines