17
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ What do you mean by 'viterbi training' exactly? $\endgroup$ – bmargulies Jul 24 '10 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$ – Digital Gal Jul 26 '10 at 16:05
  • 1
    $\begingroup$ The same question was asked on stack overflow: viterbi training vs baum-welch algorithm $\endgroup$ – Franck Dernoncourt Jan 1 '17 at 4:15
21
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ If I'm right you mix up Viterbi training and Viterbi decoding. $\endgroup$ – Peter Smit Jul 24 '10 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$ – Rich Jul 24 '10 at 19:08
  • $\begingroup$ @Rich: Could you point me to some accessible material (such as Rabiner's original HMM tutorial) on Viterbi Training? $\endgroup$ – Jacob Dec 4 '12 at 1:13
  • 4
    $\begingroup$ @Jacob Viterbi training also goes by the name Segmental K-Means, see this paper by Juang and Rabiner. $\endgroup$ – alto Oct 23 '13 at 18:37
  • 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$ – alto Oct 1 '14 at 21:56
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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