Training a Hidden Markov Model, multiple training instances

Question

I've implemented a discrete HMM according to this tutorial http://cs229.stanford.edu/section/cs229-hmm.pdf

This tutorial and others always speak of training a HMM given an observation sequence.

What happens when I have multiple training sequences? Should I just run them sequentially , training the model after the other?

Another option is to concatenate the sequences to one and train on it, but then I will have state transitions from the end of one sequence to the start of the next one which are not real.

Answer 1

Neither concatenating nor running each iteration of training with a different sequence is right thing to do. The correct approach requires some explanation:

One usually trains an HMM using an E-M algorithm. This consists of several iterations. Each iteration has one "estimate" and one "maximize" step. In the "maximize" step, you align each observation vector x with a state s in your model so that some likelihood measure is maximized. In the "estimate" step, for each state s, you estimate (a) the parameters of a statistical model for the x vectors aligned to s and (b) the state transition probabilities. In the following iteration, the maximize step runs again with the updated statistical models, etc. The process is repeated a set number of times or when the likelihood measure stops rising significantly (i.e, the model converges to a stable solution). Finally, (at least in speech recognition) an HMM will typically have a designated "start" state which is aligned to the first observation of the observation sequence and have a "left to right" topology so that once you leave a state you don't return to it.

So, if you have multiple training sequences, on the estimate step you should run each sequence so that it's initial observation vector aligns with the initial state. That way, the statistics on that initial state are collected from the first observations over all your observation sequences, and in general observation vectors are aligned to the most likely states throughout each sequence. You would only do the maximize step (and future iterations) after all sequences have been provided for training. On next iteration, you'd do exactly same thing.

By aligning the start of each observation sequence to the initial state you avoid the problem of concatenating sequences where you'd be incorrectly modelling transitions between the end of one sequence and beginning of next. And by using all the sequences on each iteration you avoid providing different sequences each iteration, which as the responder noted, will not guarantee convergence.

Answer 2

Lawrence Rabiner describes a mathematically well-founded approach in this tutorial from IEEE 77. The tutorial is also the 6th chapter of the book Fundamentals of Speech Recognition by Rabiner and Juang.

R.I.A Davis et. al. provides some additional suggestions in this paper.

I have not gone thoroughly through the math, but to me Rabiner's approach sounds the most promising, while Davis's approach seems to lack the mathematical foundation.

Answer 3

If you follow the math, adding extra training examples implies to recalculate the way you compute the likelihood. Instead of summing over dimensions, you also sum over training examples.

If you train one model after the other, there is no guarantee that the EM is going to coverage for every training example, and you are going to end up with bad estimates.

Here is a paper that does that for the Kalman Filter (which is an HMM with Gaussian Probabilities), it can give you a taste of how to modify your code so you can support more examples.

http://ntp-0.cs.ucl.ac.uk/staff/S.Prince/4C75/WellingKalmanFilter.pdf

He also has a lecture on HMM, but the logic is pretty straightforward.

Answer 4

This is more of a comment on the paper by RIA Davis referenced by Bittenus (above). I will have to agree with Bittenus, there is not much of a mathematical backing behind the techniques proposed in the paper - it is more of an empirical comparison.

The paper only considers the case wherein the HMM is of a restricted topology (feed-forward). (in my case I have a standard topology, and I found the most consistent results by implementing a non-weighted averaging of all models trained with Baum-Welch. This approach is mentioned in the paper but only cited with marginal results).

Another type of model-averaging training was detailed by RIA Davis in a journal article and uses Vitterbi Training instead of Baum-Welch Comparing and Evaluating HMM Ensemble Training Algorithms Using Train and Test and Condition Number Criteria. However this paper only explores the HMMs with the same restricted feed-forward topology. (I plan to explore this method and will update this post with my findings.)