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, the only thing I found is that the transaction probability is coming from different probabilistic models.

Is there a difference between these 2 algorithms?

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:

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

Machine Learning Algorithms is one of the parts , studying which you will know what exactly Forward and Backward Algorithms are.