Products of Hidden Markov Models: It Takes N>1 to Tango

Graham W. Taylor, Geoffrey E. Hinton

Abstract

Standard Hidden Markov Models (HMMs) face a "multinomial bottleneck" when modeling high-dimensional data, requiring an exponential number of states to represent distributed information. This paper revitalizes Products of Hidden Markov Models (PoHMMs) as an efficient alternative for modeling time-series data with "componential" structure. By utilizing Contrastive Divergence for learning and Annealed Importance Sampling (AIS) for likelihood estimation, the authors show that PoHMMs consistently outperform standard HMMs and directed distributed models like Factorial HMMs in complex real-world tasks, including rainfall prediction and human motion capture.

Introduction

Sequence modeling has long relied on HMMs, yet their architecture is fundamentally limited. To represent $K$ bits of information about the past, a standard HMM requires $2^K$ discrete states. While Factorial HMMs (FHMMs) introduce a distributed state to address this, they are directed models. This leads to "explaining away," where dependencies between hidden chains arise during inference, making exact computation impossible.

PoHMMs offer an undirected "Product of Experts" approach. In a PoHMM, individual HMM experts become independent when conditioned on observed data, providing a more elegant distributed representation where the representational capacity grows linearly with the number of components.

Comparison of HMM-based graphical models: (a) Standard HMM, (b) Input-Output HMM, (c) Factorial HMM, and (d) Product of HMMs.

Methods

A PoHMM combines several HMMs by multiplying their probabilities and renormalizing.

Learning via Contrastive Divergence

Because PoHMMs are undirected, standard Expectation-Maximization (EM) is difficult. Instead, the authors employ Contrastive Divergence (CD). This gradient-based method approximates the log-likelihood gradient using a small number of Gibbs sampling steps, facilitating efficient training of the joint distribution.

Evaluation via Annealed Importance Sampling

A significant challenge for undirected models is the intractable partition function (the normalizing constant). The authors adapt Annealed Importance Sampling (AIS) to PoHMMs. By bridging a simple "base rate" model to the complex PoHMM through a sequence of intermediate distributions, they can reliably estimate log-likelihoods, allowing for direct comparison with standard HMMs.

Experimental Results

The models were evaluated on two high-dimensional datasets: rainfall occurrence in Ceará, Brazil, and human motion capture (Mocap) data of salsa dancers.

Rainfall Modeling

In the rainfall task, PoHMMs demonstrated superior performance across multiple metrics for a fixed number of parameters. Notably, the individual HMM experts within the product naturally specialized, focusing on distinct geographical regions. For instance, different experts learned to capture northern/southern effects versus eastern effects independently.

Human Motion Capture

The advantage of PoHMMs was most pronounced in the "strongly componential" salsa dancing task. When modeling pairs of subjects, the PoHMM significantly outperformed baseline HMMs, which struggled to capture the complex joint dynamics of two interacting bodies.

Performance metrics for the rainfall task across varying numbers of free parameters, showing PoHMMs (Po2HMM-CI, Po3HMM-CI) generally achieving higher likelihood and accuracy with lower error in spatial and temporal statistics.

Conclusion

PoHMMs provide a parameter-efficient distributed representation for complex time-series data. While computationally more intensive to train than standard HMMs, their ability to capture independent underlying processes makes them highly effective for high-dimensional tasks. Future work includes extending these models to continuous emission distributions and exploring more advanced optimization techniques to reduce training time.

Summary updated

Abstract

Products of Hidden Markov Models(PoHMMs) are an interesting class of generative models which have received little attention since their introduction. This maybe in part due to their more computationally expensive gradient-based learning algorithm,and the intractability of computing the log likelihood of sequences under the model. In this paper, we demonstrate how the partition function can be estimated reliably via Annealed Importance Sampling. We perform experiments using contrastive divergence learning on rainfall data and data captured from pairs of people dancing. Our results suggest that advances in learning and evaluation for undirected graphical models and recent increases in available computing power make PoHMMs worth considering for complex time-series modeling tasks.
BibTeX
@inproceedings{taylor2009products,
  author = {Graham W. Taylor and Geoffrey E. Hinton},
  title = {{Products of Hidden Markov Models: It Takes N>1 to Tango}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=KoMzgs68Pkl},
}
Figure