Abstract
Products of Hidden Markov Models (PoHMMs) are an interesting class of generative models which have received little attention since their introduction. This may be 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.
Introduction: The State Explosion Problem
In sequence modeling, the Hidden Markov Model (HMM) has long been a reliable workhorse. However, HMMs suffer from a fundamental limitation: their state representation is "atomic." To model a system requiring $K$ bits of information about its past, a standard HMM requires $2^K$ hidden states. This exponential explosion makes them inefficient for high-dimensional data with multiple underlying causes.
In their 2009 work, Taylor and Hinton revisit the Product of Hidden Markov Models (PoHMM). By combining multiple HMM "experts," they create a model with a distributed hidden state that scales linearly rather than exponentially.
Architecture and Inference
PoHMMs solve the state-explosion problem by using multiple experts that work together to describe a sequence. Unlike Factorial HMMs (FHMMs), which are directed models prone to "explaining away" (where hidden chains become dependent upon observing data), PoHMMs are undirected.
In a PoHMM, each HMM expert independently constrains the data. Because it is a "Product of Experts," the individual HMMs decouple when the data is observed, making inference (determining hidden states) simple and efficient. The primary challenge lies in calculating the likelihood of a sequence, which involves a difficult normalizing constant known as the partition function.
Technical Contributions
The authors address the likelihood challenge using two key techniques:
- Contrastive Divergence (CD): Instead of the standard Expectation-Maximization (EM) algorithm, CD is used to approximate the gradient of the log-likelihood, making learning feasible for undirected models.
- Annealed Importance Sampling (AIS): The paper's primary technical contribution is showing how AIS can reliably estimate the partition function. By "annealing" from a simple base-rate HMM to the complex PoHMM, the authors can finally calculate and compare log-likelihoods.
Experimental Results
The models were tested on two challenging real-world datasets:
- Ceará Rainfall Data: Binary observations from 10 weather stations in Brazil, exhibiting both spatial and temporal dependencies.
- CMU Human Motion Capture: High-dimensional data of people salsa dancing, including pairs dancing together to test "componential" structure.
In rainfall experiments, PoHMMs consistently outperformed standard HMMs and more complex variants in both log-likelihood and classification accuracy.
For salsa dancing, the advantage was even more pronounced. The PoHMM's ability to use distributed states allowed it to achieve significantly higher test log-likelihoods than standard HMMs with comparable parameter counts. When modeling pairs, the model naturally allocated different experts to different dancers, capturing the task's inherent componential nature.
Conclusion
PoHMMs provide a representational capacity that scales linearly with the number of components, avoiding the exponential explosion of standard HMMs. While they are more computationally intensive to train than HMMs, the use of Contrastive Divergence and Annealed Importance Sampling makes them a viable and powerful choice for complex, multi-process time-series modeling. Future work may explore extending these models to continuous latent variables.
Summary updated