Augmented Ensemble MCMC sampling in Factorial Hidden Markov Models

Kaspar Märtens, Michalis K. Titsias, Christopher YauAISTATS 2019 · OpenReview

Abstract

Sampling from Factorial Hidden Markov Models (FHMMs) is notoriously difficult because the latent state space is massive and full of local traps. This paper introduces a clever "augmented crossover" move for ensemble MCMC that uses auxiliary variables to guarantee 100% acceptance of complex, genetic-style swaps between chains. The result is a sampler that explores complex posterior landscapes significantly faster and more reliably than traditional methods.

Introduction

Factorial Hidden Markov Models (FHMMs) are powerful tools for modeling data generated by multiple parallel processes—for example, identifying different sub-populations of cells within a single tumor sample. However, performing Bayesian inference on these models is a significant computational challenge.

The latent state space, representing the possible configurations of hidden chains, grows exponentially with the number of chains. Standard Markov Chain Monte Carlo (MCMC) methods, such as Gibbs sampling, often get "stuck" in local modes because they only update one part of the model at a time. While parallel tempering—running multiple versions of the model at different "temperatures" to smooth out the landscape—can help, the standard way to share information between these versions (swapping entire states) is almost always rejected in high-dimensional problems.

Methodology

The authors propose a novel Augmented Ensemble MCMC approach. The core innovation is the augmented crossover move, which draws inspiration from genetic algorithms but frames it as a Gibbs sampling step.

Schematic of the auxiliary variable crossover move: (a) starting sequences, (b) constructing bridge variables, and (c) sampling new configurations.
  1. Parallel Tempering: The algorithm runs an ensemble of chains. High-temperature chains explore the space freely, while the "cold" chain samples from the true target distribution.
  2. The Augmented Crossover: Instead of a simple "all-or-nothing" swap between two chains, the method uses an auxiliary variable scheme:
  3. Step 1: Create two "bridge" variables ($\mathbf{u}, \mathbf{v}$) by performing a random one-point crossover on the current states of two chains.
  4. Step 2: Define a set of all possible crossovers between these bridge variables.
  5. Step 3: Jointly sample new states for both chains from this set, weighted by their posterior probabilities.

Because this is formulated as a Gibbs update, the move is always accepted. This allows the chains to exchange significant chunks of information (effectively performing two-point crossovers) without the high rejection rates typical of Metropolis-Hastings proposals. For FHMMs, the authors show this can be computed efficiently in linear time relative to the sequence length.

Experimental Setup

The method was evaluated on three distinct setups:

  • Multimodal Toy Problem: Synthetic binary sequences designed with a highly fragmented landscape (up to $2^{10}$ local modes) to test exploration capabilities.
  • FHMM Simulation: A controlled simulation of tumor sub-populations ($K=3$ chains) where two different configurations could explain the observed data, but one is slightly more probable.
  • Real Cancer Genomics Data: Whole-genome sequencing data from a bladder cancer patient (10,877 loci). The goal was to deconvolve the "subclonal architecture"—identifying which chromosomes had extra copies in different cell populations.

Results and Discussion

The augmented crossover demonstrated superior exploration across all tests. In the toy problem with 1,024 modes, the augmented crossover visited an average of 144 modes, while standard swaps only managed 3 and random crossovers managed 27.

Cumulative number of mode jumps over iterations. The purple line (augmented crossover) shows significantly better exploration as problem complexity (B) increases.

In FHMM simulations, the augmented sampler reached high-probability regions much faster than standard Gibbs or Hamming Ball samplers. On real bladder cancer data, the method identified more probable, less "fragmented" genetic configurations. It successfully captured the uncertainty of whether certain chromosomal alterations co-occurred, which is vital for understanding how a tumor evolves.

A key insight is the "Gibbs-ification" of genetic moves. By realizing that genetic crossover moves can be made 100% efficient using auxiliary variables, the authors created a valid Gibbs sampler that finds a "Goldilocks" zone—local enough to be probable but global enough to jump between modes.

Conclusion

While the current implementation focuses on binary latent states, the theory is general. Extending the recursive efficiency to categorical or continuous states is a primary area for future work. Additionally, performance still depends on temperature ladder tuning, and future research could involve adaptively tuning these temperatures or fully integrating the scheme to simultaneously sample both latent sequences and model parameters.

Summary updated

Abstract

Bayesian inference for Factorial Hidden Markov Models is challenging due to the exponentially sized latent variable space. Standard Monte Carlo samplers can have difficulties effectively exploring ...
BibTeX
@inproceedings{martens2019augmented,
  author = {Kaspar Märtens and Michalis K. Titsias and Christopher Yau},
  title = {{Augmented Ensemble MCMC sampling in Factorial Hidden Markov Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=GJs_QkWdQG},
}
Figure