Factorial Hidden Markov Models

Zoubin Ghahramani, Michael I. Jordan

TL;DR

Standard Hidden Markov Models (HMMs) suffer from a "state explosion" problem: to represent complex histories, they require an exponential number of states. This paper introduces Factorial Hidden Markov Models (FHMMs), which use a distributed state representation—multiple parallel Markov chains—to model time series more efficiently, leveraging variational approximations to keep the mathematics tractable.

The Bottleneck of Standard HMMs

The classic HMM is a workhorse of time-series modeling, but it has a fundamental bottleneck: it represents the "history" of a sequence using a single multinomial variable.

Imagine you want to track 30 independent binary features over time. A standard HMM would need $2^{30}$ (over a billion) distinct states to represent every possible combination. This leads to two massive issues:

  1. Computational Complexity: The standard learning algorithm (Baum-Welch) becomes impossibly slow.
  2. Overfitting: With so many states, the model has too many parameters and fails to generalize to new data.

The authors aim to create a model that can handle "distributed" information—where the state is composed of several independent components—without falling into the trap of exponential complexity.

The Factorial HMM Architecture

To solve this, the authors propose the Factorial Hidden Markov Model (FHMM). Instead of one state sequence, an FHMM consists of $d$ parallel, independent Markov chains.

Standard HMM vs. Factorial HMM Architecture
  • Cooperative Output: At each time step, the observable output is a weighted combination of the current states of all $d$ chains, plus some Gaussian noise. This is essentially a "cooperative" model where multiple hidden processes contribute to a single signal (similar to multiple people talking at once in a single audio stream).
  • Distributed Efficiency: An FHMM with 30 binary units can represent the same information as an HMM with $2^{30}$ states, but with vastly fewer parameters. This drastically reduces the risk of overfitting.

Overcoming Intractable Inference

The authors use the Expectation-Maximization (EM) framework to train the model.

  • M-Step: They show that the parameters (weights, transition matrices, and covariance) can be solved analytically and exactly.
  • E-Step: This is the hard part. Because the hidden chains interact through the shared output, calculating the exact probability of the hidden states is computationally "intractable" (it still scales exponentially). The chains are independent until you see the output; once observed, they become coupled.

To make the E-step work, they introduce two approximations:

  1. Gibbs Sampling: A stochastic method that updates states one by one.
  2. Mean Field Approximation: A variational technique from statistical mechanics. It approximates the complex, coupled system with a simpler, factorized one. This leads to a fast, iterative "fixed-point" equation that usually converges in just 2 to 10 iterations, providing a mathematically grounded way to decouple the chains during inference.

Key Results

The paper evaluates the model using synthetic datasets generated from random FHMM structures, comparing the FHMM against a "standard" HMM given the same total number of possible states ($k^d$).

Experimental Results Comparing Algorithms
  • Overfitting Resistance: In larger problems (e.g., 5 chains with 3 states each, $d=5, k=3$), the standard HMM suffered from severe overfitting (evidenced by poor test set performance), while the FHMM maintained much better test-set likelihood.
  • Speedup: The Mean Field (MF) approach was significantly faster than the exact algorithm. For the largest test case, the MF approach took 4.7 seconds per cycle, compared to 90.0 seconds for the standard HMM.
  • Performance: Both Gibbs sampling and Mean Field approximations achieved performance comparable to the exact (but slow) E-step, proving they are viable for real-world applications.

Limitations and Future Directions

  • Real-Valued Focus: The derivation in this paper assumes real-valued (Gaussian) observables. While the authors note it can be adapted for discrete data, the math becomes significantly more difficult.
  • Independent Chains: The basic FHMM assumes the underlying Markov chains don't influence each other. Adding "coupling" between chains is possible but risky, as it could break the "constant partition function" property that makes their M-step so efficient.
  • Structured Approximations: The authors point toward "Structured Mean Field" as a future direction—a hybrid approach that uses the exact forward-backward algorithm within each chain while using mean field theory to handle the interactions between chains.

Summary updated

Abstract

We present a framework for learning in hidden Markov models with distributed state representations. Within this framework , we de(cid:173) rive a learning algorithm based on the Expectation-Maximization (EM) procedure for maximum likelihood estimation. Analogous to the standard Baum-Welch update rules, the M-step of our algo(cid:173) rithm is exact and can be solved analytically. However, due to the combinatorial nature of the hidden state representation, the exact E-step is intractable. A simple and tractable mean field approxima(cid:173) tion is derived. Empirical results on a set of problems suggest that both the mean field approximation and Gibbs sampling are viable alternatives to the computationally expensive exact algorithm.
BibTeX
@inproceedings{ghahramani1995factorial,
  author = {Zoubin Ghahramani and Michael I. Jordan},
  title = {{Factorial Hidden Markov Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
  url = {https://openreview.net/forum?id=rJW43LbObS},
}
Figure