Hamming Ball Auxiliary Sampling for Factorial Hidden Markov Models

Michalis K. Titsias, Christopher YauNeurIPS 2014 · OpenReview

Introduction

Hidden Markov Models (HMMs) are foundational tools for analyzing time-series data, but they struggle when multiple independent processes contribute to a single observation. The Factorial HMM (FHMM) addresses this by utilizing $K$ parallel hidden chains that cooperatively generate the observed data.

However, the state space of an FHMM grows exponentially ($2^K$) with the number of chains, making standard exact inference—such as the Forward-Filtering Backward-Sampling (FF-BS) algorithm—computationally intractable for even a modest number of chains. Researchers typically rely on Gibbs sampling, updating one chain at a time while holding the others fixed. Because these chains are often strongly coupled through the observed data, Gibbs samplers frequently get trapped in "local modes." These are suboptimal configurations that require multiple chains to change simultaneously to escape, a move standard Gibbs cannot make.

This paper introduces a novel Markov chain Monte Carlo (MCMC) sampling algorithm for FHMMs that uses a "Hamming Ball" auxiliary variable to enable efficient, joint updates of latent sequences. By restricting the search space to a controllable neighborhood, the method escapes the local modes that trap traditional Gibbs samplers while maintaining polynomial-time complexity.

Methods: Hamming Ball Sampling

Factorial Hidden Markov Model structure

To overcome the limitations of asymmetric Gibbs updates, the authors propose Hamming Ball (HB) sampling, a strategy that uses an auxiliary variable construction to allow "locally symmetric" moves across the parallel chains.

The algorithm proceeds as follows:

  1. The Hamming Ball: For a given state matrix $X$ (representing the hidden chains over time), the method defines a "ball" of radius $m$. This ball contains all configurations that differ from $X$ by at most $m$ bits per time step.
  2. The Auxiliary Variable: A latent matrix $U$ is introduced. In each iteration, $U$ is sampled uniformly from the Hamming ball centered at the current state $X$.
  3. The Joint Update: A new state $X$ is then sampled from the Hamming ball centered at $U$.

Because the search space is restricted to the size of the Hamming ball ($M$), the efficient FF-BS algorithm can be used to sample the new $X$ in $O(M^2N)$ time. Unlike Gibbs sampling, which is "asymmetric" (only changing a specific subset of the matrix), the HB sampler is "symmetric." Any bit in the entire matrix has a chance to flip in a single update, provided it falls within the ball's radius.

Evaluation and Key Results

The paper evaluates the algorithm on two primary datasets:

  • Simulated Dataset: An artificial sequence ($N=200$) with $K=5$ factor chains and high-dimensional (25D) observations, designed to create a "peaky" posterior where the ground truth is hard to find.
  • REDD (Reference Energy Disaggregation Data Set): A real-world dataset containing household electricity usage. The task is energy disaggregation: taking the total power signal and inferring which individual appliances (the "factors", $K=10$) were on at any given time.
Performance comparison between Hamming Ball (HB) and Block Gibbs (BG) samplers

The results demonstrate significant improvements over traditional methods:

  • Escaping Local Modes: In simulations, all versions of Block Gibbs (BG) sampling failed to find the ground truth, remaining trapped in local optima. In contrast, the HB sampler (with radius $m=2$ or $3$) quickly discovered the optimal solution, driving the number of errors to zero.
  • Superior Disaggregation: On the REDD dataset, the HB sampler achieved significantly lower Mean Squared Error (MSE) in the prediction phase compared to Block Gibbs.
  • Efficiency Trade-off: While individual HB moves are computationally heavier than simple Gibbs moves, they are far more effective per unit of time because they move the chain to high-probability regions much faster.

Key Insights

  • Symmetry is Key: The failure of Gibbs sampling is not just about the size of the move, but the asymmetry of the update. Allowing all chains to be "unfrozen" simultaneously within a restricted radius enables the HB sampler to navigate complex posterior landscapes.
  • User-Controllable Complexity: The radius $m$ acts as a computational dial. A small $m$ (e.g., $m=1$) is cheap but allows for more global exploration than standard Gibbs. As $m$ increases, the sampler approaches exact inference at a higher cost.
  • Generalizability: While framed for binary FHMMs, the Hamming Ball concept can be extended to any finite discrete state space and other models like "spike and slab" variable selection or Indian Buffet Processes.

Limitations and Future Work

The primary limitation is the scaling of the ball size. While $O(M^2N)$ is polynomial, the number of states in the ball ($M$) still grows combinatorially with the radius $m$ and the number of chains $K$. For very large $K$, even $m=1$ might become computationally expensive.

The authors suggest several promising future directions, including dynamically tuning the radius $m$ during sampling to focus computational effort where uncertainty is highest, using non-uniform weighted distributions within the ball to keep the sampler closer to high-probability regions, and extending the method to models with undirected dependencies or more complex coupling between chains.

Summary updated

Abstract

We introduce a novel sampling algorithm for Markov chain Monte Carlo-based Bayesian inference for factorial hidden Markov models. This algorithm is based on an auxiliary variable construction that restricts the model space allowing iterative exploration in polynomial time. The sampling approach overcomes limitations with common conditional Gibbs samplers that use asymmetric updates and become easily trapped in local modes. Instead, our method uses symmetric moves that allows joint updating of the latent sequences and improves mixing. We illustrate the application of the approach with simulated and a real data example.
BibTeX
@inproceedings{titsias2014hamming,
  author = {Michalis K. Titsias and Christopher Yau},
  title = {{Hamming Ball Auxiliary Sampling for Factorial Hidden Markov Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=S1VD3L-u-B},
}
Figure