7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is this question so difficult to answer? or is it so simple that no one want to answer? If its difficult i wonder how people are implementing HMM in different applications and if its simple then may be its simple for you guys.. but i really need help to understand it.. if someone can answer.. $\endgroup$ – amw10 Jan 17 '13 at 1:53
  • $\begingroup$ I am working with HMM and I liked the previous answer. My data is a series of images and one feature vector was extracted from each image to create a feature matrix. I have a question, what could be the training data that I can use for initializing the emission matrix. Can I use my feature matrix? $\endgroup$ – user74021 Apr 20 '15 at 6:59
11
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome to the site, @Kat. This is a really nice answer (+1), I hope we'll see more. Since you're new here, you might like to read our FAQ to help learn your way around. $\endgroup$ – gung - Reinstate Monica Mar 20 '13 at 0:42
5
$\begingroup$

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.

| cite | improve this answer | |
$\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.