Parameter elimination in particle Gibbs sampling

Anna Wigren, Riccardo Sven Risuleo, Lawrence Murray, Fredrik Lindsten

In the NeurIPS 2019 paper "Parameter elimination in particle Gibbs sampling," researchers present a clever way to boost the performance of Bayesian inference in state-space models. By leveraging mathematical conjugacy to "marginalize out" parameters, the authors break the performance ceiling of standard sampling methods without sacrificing computational efficiency.

The Bottleneck in State-Space Inference

State-space models (SSMs) are the bread and butter of fields like robotics, ecology, and epidemiology. They involve a hidden "state" (like the actual number of infected people in a region) and "observations" (like reported hospital cases). Bayesian inference in these models is notoriously difficult because you have to estimate both the high-dimensional state trajectory and the underlying parameters simultaneously.

The go-to tools for this task are Particle Markov chain Monte Carlo (PMCMC) methods, specifically Particle Gibbs (PG). These methods act as "exact approximations" of an ideal Gibbs sampler. However, they suffer from a fundamental flaw: they can never perform better than the hypothetical Gibbs sampler they are mimicking. If the states and parameters are strongly correlated, the sampler gets "stuck"—a problem known as poor mixing—requiring thousands of iterations to produce useful, independent samples.

Breaking the Ceiling with Marginalization

The authors propose mPG and mPGAS (Marginalized Particle Gibbs / Marginalized Particle Gibbs with Ancestor Sampling). The core idea is parameter elimination: instead of alternating between sampling states and sampling parameters, the algorithm integrates the parameters out of the state update entirely.

Key technical contributions include:

  • The Restricted Exponential Family: Marginalizing parameters usually turns a Markovian model (where the future depends only on the present) into a non-Markovian one. Normally, this makes computation time grow quadratically ($O(T^2)$). The authors identify a specific class of models—the restricted exponential family—where updates can be done using sufficient statistics, keeping the complexity linear ($O(T)$).
  • Blocking for Diffuse Priors: When we have very little prior knowledge (diffuse priors), marginalization can make the first few steps of a simulation very unstable, leading to low update frequencies. The authors introduce a "blocking" strategy that uses standard sampling for the start of the trajectory and marginalized sampling for the rest, stabilizing the algorithm.
Update frequency over time demonstrating how the blocking strategy stabilizes early simulation steps compared to standard mPGAS.
  • PPL Integration: They implemented these methods in Birch, a probabilistic programming language (PPL). This allows the "math heavy" part of marginalization to happen automatically behind the scenes.

Key Results and Performance Gains

The authors evaluated their methods on three distinct scenarios: a synthetic non-linear SSM benchmark, real-world epidemiological data from a Dengue outbreak in Micronesia, and a 20-year ecological dataset tracking Song Sparrow populations.

Superior Mixing and Efficiency

The most striking insight is that mPGAS can actually outperform the "ideal" unmarginalized Gibbs sampler. While standard PGAS approaches the Gibbs sampler's performance as you add more particles, mPGAS moves toward producing independent and identically distributed (i.i.d.) draws.

Autocorrelation comparison showing mPGAS with 50 particles outperforming standard PGAS with 5000 particles.

In synthetic tests, mPGAS with only 50 particles achieved lower autocorrelation than standard PGAS with 5000 particles. This represents a massive gain in sampling efficiency.

While marginalization adds a small amount of computational overhead per iteration (e.g., a test run showed mPGAS was ~24% slower per iteration than standard PGAS), the quality of each sample is so much higher that the overall "time-to-solution" is significantly reduced. The algorithm reaches a stable posterior much faster because its samples are far less correlated.

Real-world Accuracy

In the Dengue and Sparrow models, the marginalized methods successfully recovered parameters—like reporting rates and population density regulation—that matched literature values, but with much smoother convergence than non-marginalized versions.

Limitations and Future Work

  • Conjugacy Constraint: The method requires a conjugacy relationship between the parameter prior and the likelihood. If your model doesn't fit into the "restricted exponential family," you cannot fully eliminate the parameters, though "partial marginalization" remains a workaround.
  • Implementation Complexity: Deriving these relations by hand is difficult. The authors emphasize that the future of this method lies in Probabilistic Programming, where compilers can automatically detect and apply these mathematical shortcuts.
  • Blocking Automation: While the "blocking" strategy fixes issues with diffuse priors, it currently requires manual setup. Automating this within PPLs is a noted area for future development.

Summary updated

Abstract

Bayesian inference in state-space models is challenging due to high-dimensional state trajectories. A viable approach is particle Markov chain Monte Carlo (PMCMC), combining MCMC and sequential Monte Carlo to form ``exact approximations'' to otherwise-intractable MCMC methods. The performance of the approximation is limited to that of the exact method. We focus on particle Gibbs (PG) and particle Gibbs with ancestor sampling (PGAS), improving their performance beyond that of the ideal Gibbs sampler (which they approximate) by marginalizing out one or more parameters. This is possible when the parameter(s) has a conjugate prior relationship with the complete data likelihood. Marginalization yields a non-Markov model for inference, but we show that, in contrast to the general case, the methods still scale linearly in time. While marginalization can be cumbersome to implement, recent advances in probabilistic programming have enabled its automation. We demonstrate how the marginalized methods are viable as efficient inference backends in probabilistic programming, and demonstrate with examples in ecology and epidemiology.
BibTeX
@inproceedings{wigren2019parameter,
  author = {Anna Wigren and Riccardo Sven Risuleo and Lawrence Murray and Fredrik Lindsten},
  title = {{Parameter elimination in particle Gibbs sampling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=KCVRyvQ1Nxd},
}
Figure