0
$\begingroup$

Assume that we have set of Hidden Markov Models (Bayesian networks) Set{(n, m, P, A, B)} (n - number of hidden states, m - number of observable states, P - initial probabilities, A - transition matrix, B - emission matrix). Are the peculiar algorithms or approaches how to classify those HMMs into different subsets of HMMs? If n and m are equal for all the HMMs in the set then classification can be build from the ranges of elements in A and B. If n and m are different for different HMMs then one classify hidden and observable states first...

Are there some research or trends for this? Google is not helping here because it returns results for classification methods using HMMs, but we want to classify (or find clusters) of HMMs themselves.

$\endgroup$
  • $\begingroup$ Are you referring to Hierarchical Hidden Markov Model (HHMMs)? you need to figure out the correct terminology before searching. $\endgroup$ – smci Nov 28 '16 at 13:22
  • $\begingroup$ No. I have set of customers, each customer can be associated with its own HMM. And I want to do classification of customers based on the their respective HMMs. One HMM is associated with one customer. This HMM summarizes the history of customer behavior. Therefore - classiciation of HMMs. $\endgroup$ – TomR Nov 28 '16 at 20:18
  • $\begingroup$ I know what classification of HMMs means. You are doing something slightly different, and you need to figure out what the standard terminology for it is (HMM mixture model? or what?) You can't just make up a term and expect people to understand what it means. $\endgroup$ – smci Nov 28 '16 at 21:10
3
$\begingroup$

What you are looking for is called a metric (or distance, or similarity measure) for HMMs (some people would say SVM kernel for HMMs).

Somehow, if you have a distance, you can cluster the HMMs.

The most classical distance, defined by Rabiner and Juang is a Monte-Carlo approximation of a Kullback-Leibler divergence for HMM. It requires a long observation sequence $O$ generated from the first HMM $\lambda_1$ and is then computed as: $$ D_{KL}(\lambda_1||\lambda_2) = 1/T * (log(P(O|\lambda_1)-log(P(O|\lambda_2))$$

The advantage of this is that it does not imply any constraint on the number of hidden state. However, $O$ needs to be a long sequence if you want accurate results. There is some research on the topic but not too much, and even less for HMMs with different topology (which is another reason why Google does not give much results...)

Edit: This paper proposes a distance measure that does not require the number of hidden states to be the same but is only valid for uni-dimensional observations. A new distance measure for hidden Markov models by Zeng, Duan, and Wu in Experts Systems with Applications 37, p. 1550-1555, 2010. It is rather easy to implement.

| 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.