MCMC for non-Linear State Space Models Using Ensembles of Latent Sequences

Alexander Y. ShestopaloffarXiv 2014 · DOI · arXiv

Abstract

Non-linear state space models (SSMs) are a widely used class of models for biological, economic, and physical processes. However, fitting these models to observed data remains a difficult inference problem. We take a Bayesian approach to the inference of unknown parameters, requiring efficient Markov Chain Monte Carlo (MCMC) sampling methods for both latent variables and model parameters. By combining the ensemble technique of Neal (2010) with the embedded Hidden Markov Model (HMM) technique of Neal (2003), we introduce a new MCMC method for non-linear SSMs. The key innovation is performing parameter updates conditional on an enormously large ensemble of latent sequences rather than a single sequence. We evaluate this method using the Ricker model of population dynamics, demonstrating that the ensemble method is significantly more efficient than standard Metropolis and single-sequence embedded HMM methods. Furthermore, we introduce a "staged" proposal scheme that utilizes partial backward passes to discard poor proposals at low cost, resulting in efficiency gains of up to 20.4 times over existing techniques.

Introduction

State Space Models (SSMs) are fundamental to time-series analysis, providing a framework to model hidden states that evolve over time and the noisy observations generated by those states. While linear-Gaussian SSMs are analytically tractable, many real-world phenomena in ecology and economics are non-linear and non-Gaussian. In these cases, Bayesian inference becomes computationally intensive, as researchers must sample from the joint posterior of both the hidden state sequences and the model parameters ($\theta$).

Traditional MCMC methods often struggle with two specific issues in this context:

  1. Strong Dependencies: When state transitions are nearly deterministic, the current state is "locked" by its neighbors. Standard Gibbs sampling, which updates one variable at a time, fails to move effectively through the state space.
  2. Concentrated Posteriors: When updating parameters $\theta$ while conditioning on a single latent sequence, the resulting posterior is often extremely "peaky." This forces the sampler to take very small steps to maintain acceptance, leading to slow exploration of the parameter space.

The Ensemble Embedded HMM

To address these challenges, this research introduces the Ensemble Embedded HMM. This method builds upon two foundational techniques:

  • Embedded HMM (2003): This approach handles continuous state spaces by discretizing them on the fly. At each time step, a pool of $L$ candidate states is randomly sampled. This transforms the complex non-linear model into a finite HMM that can be solved exactly using the forward-backward algorithm.
  • Ensemble MCMC (2010): Rather than selecting a single latent sequence from the pool, this method considers the entire ensemble of all $L^N$ possible sequences (where $N$ is the sequence length).

By integrating these ideas, the authors propose updating parameters $\theta$ by summing over the entire ensemble. While the number of sequences is astronomical, the mathematical structure of HMMs allows this sum to be computed in $O(NL^2)$ time. This "smoothing" of the posterior allows the MCMC sampler to take much larger steps, significantly improving the mixing of the chain.

Staged Proposals for Computational Efficiency

To further optimize the method, the authors introduce Staged Ensemble MCMC. This is a "fail-fast" mechanism designed to reduce redundant computations. The algorithm evaluates a parameter proposal using only a representative subset of the data in an initial stage. If the proposal is deemed poor based on this subset, it is rejected immediately. If it passes, the algorithm proceeds to the full calculation, reusing the backward probabilities from the first stage to minimize work. This filtering process ensures that computational resources are focused on the most promising regions of the parameter space.

Experimental Evaluation: The Ricker Model

The effectiveness of the ensemble method was tested on the Ricker model, a classic non-linear SSM used to describe population dynamics. The model was tested using 100 simulated time points, with a specific challenge: observations were only provided for the latter half of the sequence (times 51–100), mimicking real-world scenarios with missing data. The goal was to infer the growth rate ($r$), environmental noise ($\sigma$), and observation scale ($\phi$).

Key Results

The ensemble methods were compared against a standard Metropolis sampler and a single-sequence embedded HMM:

  • Vs. Metropolis: The simple Metropolis sampler was vastly less efficient and frequently became trapped in local modes, particularly failing to explore the posterior for the noise parameter $\sigma$.
  • Vs. Single-Sequence: The basic ensemble method demonstrated an efficiency gain of 1.9 to 12.0 times over the single-sequence method.
  • Staged Performance: With the addition of the staged proposal scheme, the efficiency gain increased to 3.4 to 20.4 times that of the single-sequence method.

The most significant improvements were observed in the inference of the observation scale ($\phi$), where the ensemble approach allowed for much broader and more accurate exploration of the marginal posterior.

Conclusion and Future Work

The Ensemble Embedded HMM provides a powerful new tool for Bayesian inference in non-linear state space models. By leveraging the efficiency of HMM algorithms to integrate over an ensemble of sequences, the method overcomes the limitations of single-sequence conditioning.

Future research directions include developing automated methods for choosing the "pool distribution" used to generate candidate states, as the current heuristic approach may not be optimal for all models. Additionally, testing the method on a broader range of non-linear, non-Gaussian models will further establish its general-purpose utility in the field of time-series analysis.

Summary updated

Abstract

Non-linear state space models are a widely-used class of models for biological, economic, and physical processes. Fitting these models to observed data is a difficult inference problem that has no straightforward solution. We take a Bayesian approach to the inference of unknown parameters of a non-linear state model; this, in turn, requires the availability of efficient Markov Chain Monte Carlo (MCMC) sampling methods for the latent (hidden) variables and model parameters. Using the ensemble technique of Neal (2010) and the embedded HMM technique of Neal (2003), we introduce a new Markov Chain Monte Carlo method for non-linear state space models. The key idea is to perform parameter updates conditional on an enormously large ensemble of latent sequences, as opposed to a single sequence, as with existing methods. We look at the performance of this ensemble method when doing Bayesian inference in the Ricker model of population dynamics. We show that for this problem, the ensemble method is vastly more efficient than a simple Metropolis method, as well as 1.9 to 12.0 times more efficient than a single-sequence embedded HMM method, when all methods are tuned appropriately. We also introduce a way of speeding up the ensemble method by performing partial backward passes to discard poor proposals at low computational cost, resulting in a final efficiency gain of 3.4 to 20.4 times over the single-sequence method. This research has been done jointly with Radford M. Neal.
BibTeX
@misc{shestopaloff2014mcmc,
  author = {Alexander Y. Shestopaloff},
  title = {{MCMC for non-Linear State Space Models Using Ensembles of Latent Sequences}},
  year = {2014},
  eprint = {1305.0320},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1305.0320},
}
Figure