Hierarchical hidden Markov model

The hierarchical hidden Markov model (HHMM) is a statistical model derived from the hidden Markov model (HMM). In an HHMM, each state is considered to be a self-contained probabilistic model. More precisely, each state of the HHMM is itself an HHMM.

HHMMs and HMMs are useful in many fields, including pattern recognition.

Background

It is sometimes useful to use HMMs in specific structures in order to facilitate learning and generalization. For example, even though a fully connected HMM could always be used if enough training data is available, it is often useful to constrain the model by not allowing arbitrary state transitions. In the same way it can be beneficial to embed the HMM into a greater structure; which, theoretically, may not be able to solve any other problems than the basic HMM but can solve some problems more efficiently when it comes to the amount of training data required.

Description

In the hierarchical hidden Markov model (HHMM), each state is considered to be a self-contained probabilistic model. More precisely, each state of the HHMM is itself an HHMM. This implies that the states of the HHMM emit sequences of observation symbols rather than single observation symbols as is the case for the standard HMM states.

Illustration of the structure of a HHMM. Gray lines show vertical transitions. The horizontal transitions are shown as black lines. The light gray circles are the internal states and the dark gray circles are the terminal states that returns control to the activating state. The production states are not shown in this figure.

When a state in an HHMM is activated, it will activate its own probabilistic model, i.e. it will activate one of the states of the underlying HHMM, which in turn may activate its underlying HHMM and so on. The process is repeated until a special state, called a production state, is activated. Only the production states emit observation symbols in the usual HMM sense. When the production state has emitted a symbol, control returns to the state that activated the production state. The states that do not directly emit observations symbols are called internal states. The activation of a state in an HHMM under an internal state is called a vertical transition. After a vertical transition is completed, a horizontal transition occurs to a state within the same level. When a horizontal transition leads to a terminating state, control is returned to the state in the HHMM, higher up in the hierarchy, that produced the last vertical transition.

Note that a vertical transition can result in more vertical transitions before reaching a sequence of production states and finally returning to the top level. Thus the production states visited give rise to a sequence of observation symbols that is "produced" by the state at the top level.

The methods for estimating the HHMM parameters and model structure are more complex than for HMM parameters, and the interested reader is referred to Fine et al. (1998).

The HMM and HHMM belong to the same class of classifiers. That is, they can be used to solve the same set of problems. In fact, the HHMM can be transformed into a standard HMM. However, the HHMM leverages its structure to solve a subset of the problems more efficiently.

Topology

Classical HHMMs require a pre-defined topology, meaning that the number and hierarchical structure of the submodels must be known in advance. Samko et al. (2010) used information about states from feature space (i. e., from outside the Markov Model itself) in order to define the topology for a new HHMM in an unsupervised way. However, such external data containing relevant information for HHMM construction may not be available in all contexts, e. g. in language processing.

See also

• Layered hidden Markov model
• Hierarchical temporal memory

Further reading

• S. Fine, Y. Singer and N. Tishby, "The Hierarchical Hidden Markov Model: Analysis and Applications", Machine Learning, vol. 32, p. 41–62, 1998
• K.Murphy and M.Paskin. "Linear Time Inference in Hierarchical HMMs", NIPS-01 (Neural Info. Proc. Systems).
• H. Bui, D. Phung and S. Venkatesh. "Hierarchical Hidden Markov Models with General State Hierarchy", AAAI-04 (National Conference on Artificial Intelligence).