How to define initial probabilities for HMM?

Question

HI This is first time I was reading about HMM, however I have read so many articles on web, but two things where I am confused are:

1. How to decide number of Hidden States (although HMM says we don't need to know, we just have to make a guess, even for making guess what should be the best criteria)
2. Once define hidden states let say 5, then how to define initial probabilities for each hidden state and the transitional probabilities among each other...

I would appreciate if someone can give me example... But please don't give me example of weather system.

Answer 1

1. How to decide number of Hidden States (although HMM says we don't need to know, we just have to make a guess, even for making guess what should be the best criteria)

The number of hidden states is problem dependent. For example in speech recognition and synthesis, 3 and 5 states are commonly used. The reason for using these is that speech is a highly variable data. So the distribution at different instants of speech sounds (phonemes) varies with time and each state models the different distributions.

2. Once define hidden states let say 5, then how to define initial probabilities for each hidden state and the transitional probabilities among each other...

An HMM can be defined by (A, B, $\pi$), where A is a matrix of state transition probabilities, B is a vector of state emission probabilities and $\pi$ (a special member of A) is a vector of initial state distributions. The following steps are taken to estimate these parameters:

• For the A and $\pi$ parameters, randomly initialise the HMM (between 0 and 1)
• Initialise the B parameter by uniformly segmenting the training data and estimating the global mean and variance. The B parameter deals with the mean and variances of each state
• Re-estimate and refine the parameters using the Baum-Welch algorithm. This is a variant of the well-known Expectation-Maximation (EM) algorithm.

References:

• Rabiner, L. 1989. A tutorial on hidden Markov models and selected applications in speech recognition.
• Baum, L.E., T. Petrie, G. Soules and N. Weiss. 1970. A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains. The Annals of Mathematical Statistics Vol. 41, No. 1, pp. 164-171.
• Dempster, A. P., N. M. Laird, and D. B. Rubin. 1977. Maximum likeli- hood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological) 39 (1), pp. 1-38.

Answer 2

The usual, uninspiring and uninformative answer to this question is that 'the dynamics of your system / the nature of the physical problem will indicate how many hidden states there are', which translates into: "Take a pick and get over it". However, I do not buy into this. I think most problems are more complex than that, hence your question is a very valid one.

Let us assume you are using a Gaussian distribution to model your emission (observation) variables. When fitting an HMM, what you are doing is essentially temporal clustering. Hence, you could utilise a quick and simpler clustering method to form the initial guesstimates of your Gaussian distributions per state. This is also mentioned in Rabiner's paper - the main reference for HMM's.

1) You can run a (simple) k-means on your dataset to roughly estimate the optimal number of clusters and the locations of the centroids (mean vector) in your dataset. Have a look at here for a great coverage on the topic of how to determine the number of clusters.

2) Better yet, you can choose to fit a mixture of Gaussians (or any mixture model) on your dataset to see how many mixture components best explain your dataset and what the sufficient statistics (Mean vector, Covariances) are. You can use these outputs to form your initial parameters while training the HMM - which is computationally harder than training a Mixture model (and obviously a k-means routine) primarily due to the serial dependencies that go into the loglikelihood (and therefore Expectation-Maximisation) calculation.

Now, the important thing here is that these clustering techniques will not take into account the serial dependencies (as a HMM does via its transition matrix) while calculating what point most likely belongs to what state. Nevertheless they will give you rough estimations as to what your starting points (e.g. Mean vector, Covariance vector, prior distributions) should be.

You can, for instance, calculate the loglikelihood of your HMM trained in this way and then compare it to the loglikelihood of one that has been trained using randomised initial values to observe the difference yourself.

This is in a way analogous to, for instance, starting-off the global optimisation for a non-convex problem with the optimal values to its simplified (approximate) convex version. You do steps 1 and/or 2 to reduce the search space. Needless to say, the final values you find are not in anyway guaranteed to be the global solution to your optimisation problem - but maybe sufficiently good for your purposes.