Replica Conditional Sequential Monte Carlo

Alexander Y. Shestopaloff, Randal Douc

TL;DR

This paper introduces "Replica Conditional Sequential Monte Carlo" (Replica cSMC), a novel MCMC method for inferring hidden states in complex, non-linear, non-Gaussian time-series models. By using multiple "replicas" of the state sequence that can "see" the entire observation history and condition on each other, Replica cSMC significantly improves sampling efficiency and accuracy compared to existing methods, especially for challenging multimodal distributions.

What Problem Does This Paper Address?

Inferring the hidden states of a dynamic system from noisy observations is a fundamental problem in many fields, from finance to robotics. State-space models are a common framework for this, but when the models are non-linear and the noise is non-Gaussian, exact inference becomes intractable. Current state-of-the-art methods often rely on Particle Markov Chain Monte Carlo (PMCMC) techniques, specifically iterated Conditional Sequential Monte Carlo (cSMC). A key limitation of standard cSMC is that its proposal mechanism for estimating the state at time t typically only uses observations up to time t. This is inefficient when the entire observation sequence is available, as it fails to leverage all available information. While some "lookahead" techniques exist, they can be complex to implement. The paper aims to bridge this gap by developing a more efficient and practical cSMC-based MCMC method that can effectively utilize the full observation history.

Methods

The core innovation is the "Replica cSMC" algorithm. Instead of a single chain, it maintains K parallel chains (replicas) of the state sequence. Each replica's proposal mechanism is enhanced by conditioning on the states of the other replicas. This allows each replica to effectively "see" the entire observation sequence when proposing its own state sequence.

Here's a breakdown:

  • Iterated cSMC (Baseline): The paper starts by reviewing the standard iterated cSMC, which uses a sequence of auxiliary target distributions and a backward sampling step to construct an MCMC kernel. A key limitation is the variance of importance weights due to only using partial observation history.
  • Replica cSMC:
    • Multiple Replicas: The algorithm maintains K copies of the state sequence ($x^{(1)}_{1:T}, \dots, x^{(K)}_{1:T}$).
  • Conditional Proposals: When updating replica k, its proposal mechanism uses an estimate of the backward information filter that is built using the other replicas ($j \neq k$). This estimate is derived from the observed data and the states of the other replicas.
  • Parallelizable: The structure naturally lends itself to parallel computation, as replicas can be updated independently or in parallel.
  • Estimating Backward Information Filter: A novel aspect is how the backward information filter is estimated. Instead of relying on analytical approximations (which can be difficult for multimodal posteriors), they propose using a Monte Carlo approximation based on the other replicas. They also explore using a constant approximation for the predictive density within this estimator, which simplifies computation and can reduce variance.

Datasets

The paper evaluates the proposed Replica cSMC method on several synthetic datasets generated from:

  • A linear Gaussian state-space model.
  • Two non-Gaussian state-space models previously used in (Shestopaloff & Neal, 2018).
  • The Lorenz-96 model, a standard benchmark for chaotic systems, in a low-noise regime.

No new datasets were introduced.

Key Insights and Ideas

  • Leveraging Full Observation History: The most significant insight is that by allowing replicas to condition on each other, each replica can effectively incorporate information from the entire observation sequence into its proposals. This directly addresses a major limitation of standard cSMC.
  • Parallelism for Efficiency: The replica structure naturally enables parallelization, allowing for more efficient exploration of the state space, especially in high-dimensional or complex models.
  • Improved Handling of Multimodality: The method shows promise in handling multimodal posteriors. By using multiple replicas, the sampler is less likely to get stuck in a single mode, and the ability to share information across replicas can facilitate transitions between modes.
  • Constant Predictive Density Approximation: The finding that using a constant approximation for the predictive density in the backward information filter estimator can improve performance (reduce variance) is counter-intuitive and practically significant, simplifying implementation.
  • Reduced Variance in Importance Weights: By using the full observation history and the conditional information from other replicas, the variance of the importance weights is reduced, leading to more efficient sampling.

Key Results

  • Empirical Performance: Replica cSMC consistently demonstrated excellent empirical performance across various models, outperforming standard iterated cSMC.
  • Accuracy: In the linear Gaussian model, Replica cSMC results agreed well with a Kalman smoother (achieving ~91.4% agreement for $x_{i,t}$).
  • Efficiency: For a challenging linear Gaussian scenario, Replica cSMC achieved a similar level of precision (standard error) as standard iterated cSMC but with only 5% of the particles.
  • Multimodal Sampling: For a multimodal model (Model 2), Replica cSMC successfully explored different modes without requiring specialized "flip" updates or a significantly larger number of particles, unlike previous methods.
  • Long Time Series: The method showed robustness on longer time series (T=1500) without performance degradation.
  • Computational Complexity: The paper emphasizes that Replica cSMC achieves its performance gains at a fixed computational complexity per iteration compared to standard iterated cSMC, primarily due to its parallelizable nature and efficient use of particles.

Limitations and Future Work

  • Estimating Predictive Density: The authors acknowledge that estimating the predictive density is still an open question. They suggest exploring alternative ways to estimate it that might further reduce the variance of mixture weights.
  • Choosing Number of Replicas: Developing better guidelines for selecting the optimal number of replicas (K) for a given scenario is identified as future work.
  • Non-Time-Series Applications: The paper suggests exploring the application of Replica cSMC to non-time-series problems.
  • Multimodal Improvement: While promising for multimodal scenarios, further improvements are needed to fully address the challenges of sampling in such distributions.
  • Initialization: For multimodal distributions, initialization of replicas is crucial, and the paper notes that ensuring replicas are well-distributed amongst modes at the start is important.

Summary updated

Abstract

We propose a Markov chain Monte Carlo (MCMC) scheme to perform state inference in non-linear non-Gaussian state-space models. Current state-of-the-art methods to address this problem rely on particle MCMC techniques and its variants, such as the iterated conditional Sequential Monte Carlo (cSMC) scheme, which uses a Sequential Monte Carlo (SMC) type proposal within MCMC. A deficiency of standard SMC proposals is that they only use observations up to time $t$ to propose states at time $t$ when an entire observation sequence is available. More sophisticated SMC based on lookahead techniques could be used but they can be difficult to put in practice. We propose here replica cSMC where we build SMC proposals for one replica using information from the entire observation sequence by conditioning on the states of the other replicas. This approach is easily parallelizable and we demonstrate its excellent empirical performance when compared to the standard iterated cSMC scheme at fixed computational complexity.
BibTeX
@inproceedings{shestopaloff2019replica,
  author = {Alexander Y. Shestopaloff and Randal Douc},
  title = {{Replica Conditional Sequential Monte Carlo}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=HkbGQjWuWS},
}
Figure