I am currently using Viterbi training for an image segmentation problem. I wanted to know what the advantages/disadvantages are of using the Baum-Welch algorithm instead of Viterbi training.
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ What do you mean by 'viterbi training' exactly? $\endgroup$– bmarguliesCommented Jul 24, 2010 at 0:40
-
2$\begingroup$ In my problem I have an array of real valued data which I am modeling as a HMM (speficially a mixture of multiple density functions each with unknown parameters). For now I assume that I know the state transition probabilites. What I mean by Viterbi Trainig is the following algorithm. 1) Arbitrarily assign a state to each data point ( initialization) 2) Perform MLE of the density function parameters. 3) Re-estimate state for each point ( can be done with Viterbi Alg). 4) Goto step 2 and repeat unless stopping criteria is met. $\endgroup$– MykieCommented Jul 26, 2010 at 16:05
-
1$\begingroup$ The same question was asked on stack overflow: viterbi training vs baum-welch algorithm $\endgroup$– Franck DernoncourtCommented Jan 1, 2017 at 4:15
-
$\begingroup$ Are you using Viterbi training because a 2D-HMM is not amenable to a foward-backward algorithm because you cannot construct a tree-like transition and emission model? $\endgroup$– shouldseeCommented Mar 25, 2022 at 8:45
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
The Baum-Welch algorithm and the Viterbi algorithm calculate different things.
If you know the transition probabilities for the hidden part of your model, and the emission probabilities for the visible outputs of your model, then the Viterbi algorithm gives you the most likely complete sequence of hidden states conditional on both your outputs and your model specification.
The Baum-Welch algorithm gives you both the most likely hidden transition probabilities as well as the most likely set of emission probabilities given only the observed states of the model (and, usually, an upper bound on the number of hidden states). You also get the "pointwise" highest likelihood points in the hidden states, which is often slightly different from the single hidden sequence that is overall most likely.
If you know your model and just want the latent states, then there is no reason to use the Baum-Welch algorithm. If you don't know your model, then you can't be using the Viterbi algorithm.
Edited to add: See Peter Smit's comment; there's some overlap/vagueness in nomenclature. Some poking around led me to a chapter by Luis Javier Rodrıguez and Ines Torres in "Pattern Recognition and Image Analysis" (ISBN 978-3-540-40217-6, pp 845-857) which discusses the speed versus accuracy trade-offs of the two algorithms.
Briefly, the Baum-Welch algorithm is essentially the Expectation-Maximization (EM) algorithm applied to an HMM; as a strict EM-type algorithm you're guaranteed to converge to at least a local maximum, and so for unimodal problems find the MLE. It requires two passes over your data for each step, though, and the complexity gets very big in the length of the data and number of training samples. However, you do end up with the full conditional likelihood for your hidden parameters.
The Viterbi training algorithm (as opposed to the "Viterbi algorithm") approximates the MLE to achieve a gain in speed at the cost of accuracy. It segments the data and then applies the Viterbi algorithm (as I understood it) to get the most likely state sequence in the segment, then uses that most likely state sequence to re-estimate the hidden parameters. This, unlike the Baum-Welch algorithm, doesn't give the full conditional likelihood of the hidden parameters, and so ends up reducing the accuracy while saving significant (the chapter reports 1 to 2 orders of magnitude) computational time.
-
7$\begingroup$ If I'm right you mix up Viterbi training and Viterbi decoding. $\endgroup$ Commented Jul 24, 2010 at 5:00
-
1$\begingroup$ You're right. I wasn't aware that there was a procedure that used only the Viterbi algorithm to compute the transition probabilities as well. It looks -- on further reading -- like there's some overlap of nomenclature between discrete time/discrete state HMM analysis, and discrete time/continuous state analysis using Gaussian mixture distributions. My answer speaks to the DTDS HMM setup, and not the mixture model setup. $\endgroup$– RichCommented Jul 24, 2010 at 19:08
-
$\begingroup$ @Rich: Could you point me to some accessible material (such as Rabiner's original HMM tutorial) on Viterbi Training? $\endgroup$– JacobCommented Dec 4, 2012 at 1:13
-
4
-
1$\begingroup$ @Anoldmaninthesea. Looking at the likelihoods between epochs is the normal way to assess convergence (the likelihood should always increase at each epoch and then stop when you've reached a local maxima). The other thing you can do is early stopping by monitoring the likelihood of data not used during EM. $\endgroup$– altoCommented Oct 1, 2014 at 21:56
$\begingroup$
$\endgroup$
Forward-backward is used when you want to count 'invisible things'. For example, when using E-M to improve a model via unsupervised data. I think that Petrov's paper is an example. In the technique I'm thinking of, you first train a model with annotated data with fairly coarse annotations (e.g. a tag for 'Verb'). Then you arbitrarily split the probability mass for that state in two slightly unequal quantities, and retrain, running forward-backward to maximize likelihood by redistributing mass between the two states.
