Viterbi training or Baum-Welch algorithm to estimate the transition and emission probabilities?

algorithm hidden-markov-models viterbi expectation-maximization
dx_mrt picture dx_mrt · Nov 13, 2012 · Viewed 7.6k times · Source

I'm trying to find the most probable path (i.e. a sequence of states) on an HMM using the Viterbi algorithm. However, I don't know the transition and emission matrices, which I need to estimate from the observations (data).

To estimate these matrices, which algorithm should I use: the Baum-Welch or the Viterbi training algorithm? Why?

In case I should use the Viterbi training algorithm, can anyone provide me a good pseudocode (it's not easy to find)?

Answer

nickponline picture nickponline · Nov 15, 2012

Given enough resources, you should probably use the Baum-Welch (forward-backward) algorithm over the Viterbi training algorithm (a.k.a. segmental k-means algorithm), which is an alternative parameter estimation process that sacrifices some of Baum-Welch's generality for computational efficiency. In general, the Baum-Welch algorithm will give parameters that lead to better performance, although there are cases where this is not the case. Here is a nice comparative study.

Furthermore, note that you should use the Baum-Welch algorithm to estimate the parameters of the model. This sets the emission probability and transmission probabilities using something similar to the EM algorithm. After you have trained the HMM, you would then use the Viterbi decoding algorithm to compute the most likely sequence of states which could have generated your observations.

Reference-wise I would recommend Speech and Language Processing, Artificial Intelligence a Modern Approach or this paper

Related questions

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

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 …

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More