PaperlayerView exact revision on arXiv

Source-linked AI summary

Particle Gibbs with Ancestor Sampling

Fredrik Lindsten, Michael I. Jordan, Thomas B. Schön

arXiv:1401.0604v1stat.COstat.ML

TL;DR

Inference for non-Markovian latent processes remains difficult because existing methods retain a strong Markovianity assumption and backward simulation is problematic with intricate dependencies. The paper introduces PGAS, which uses ancestor sampling within particle Gibbs to obtain backward-simulation effects without an explicit backward pass. PGAS supports high-dimensional state-trajectory inference and is reported to improve accuracy over PGBS by up to an order of magnitude under truncation.

  • Problem

    Efficient inference for non-Markovian latent stochastic processes remains challenging, while backward simulation is problematic for models with intricate dependencies.

  • Method

    PGAS modifies particle Gibbs with an ancestor sampling step, achieving the effect of backward sampling without an explicit backward pass.

  • Results

    PGAS provides off-the-shelf Markov kernels for simulating high-dimensional, highly autocorrelated state trajectories and is reported to yield up to an order-of-magnitude greater accuracy than PGBS in the simulation study.

  • Takeaways & Limitations

    PGAS is applicable to state-space, non-Markovian, nonparametric, and graphical models, and can serve as a component of Bayesian and frequentist inference algorithms.

  • Takeaways & Limitations

    For non-Markovian models, PGAS and backward simulation have different properties, and equivalence between the samplers does not generally hold outside state-space models.

Abstract

from arXiv · show

Particle Markov chain Monte Carlo (PMCMC) is a systematic way of combining the two main tools used for Monte Carlo statistical inference: sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC). We present a novel PMCMC algorithm that we refer to as particle Gibbs with ancestor sampling (PGAS). PGAS provides the data analyst with an off-the-shelf class of Markov kernels that can be used to simulate the typically high-dimensional and highly autocorrelated state trajectory in a state-space model. The ancestor sampling procedure enables fast mixing of the PGAS kernel even when using seemingly few particles in the underlying SMC sampler. This is important as it can significantly reduce the computational burden that is typically associated with using SMC. PGAS is conceptually similar to the existing PG with backward simulation (PGBS) procedure. Instead of using separate forward and backward sweeps as in PGBS, however, we achieve the same effect in a single forward sweep. This makes PGAS well suited for addressing inference problems not only in state-space models, but also in models with more complex dependencies, such as non-Markovian, Bayesian nonparametric, and general probabilistic graphical models.

1 Introduction

The paper addresses efficient inference for non-Markovian latent processes, where existing Monte Carlo methods have not substantially weakened the Markovianity assumption. It introduces PGAS, which mitigates path degeneracy through ancestor sampling without an explicit backward pass.

  • Research gap: Efficient inference remains a major challenge for latent stochastic processes that are non-Markovian.Such models arise through direct modeling or transformations and marginalizations of state-space models.
  • Scope: The method is designed for inference in state-space and non-Markovian latent variable models, while not being limited to those classes.The paper places PGAS within particle MCMC, which combines sequential Monte Carlo and Markov chain Monte Carlo.
  • Research gap: Particle Gibbs can mix poorly under path degeneracy, an inevitable issue for high-dimensional problems.This limits the applicability of the original PG method.
  • Proposed method: PGAS modifies particle Gibbs with ancestor sampling to alleviate path degeneracy without an explicit backward pass.It thereby achieves the same effect as backward sampling in a single forward procedure.
  • Reported outcome: A truncation strategy for non-Markovian models produces up to an order-of-magnitude increase in accuracy over PGBS in the simulation study.The strategy is also applicable to PGBS, but its truncation error is reported as less severe for PGAS.

2 Sequential Monte Carlo

Sequential Monte Carlo constructs a weighted particle approximation to a sequence of target distributions by propagating particles with proposal kernels and ancestor indices. Importance weights correct the proposal, and the procedure supports inference for latent variables and model parameters.

  • State-space specialization: For state-space models, the normalized target is the posterior pθ(x1:t | y1:t), the unnormalized target is pθ(x1:t, y1:t), and the normalizer is pθ(y1:t).These quantities instantiate the general SMC formulation for an important special case.
  • Purpose: SMC uses particle filters to draw inference about latent variables and enable learning of model parameters.The sequential structure of the problem motivates using SMC methods, particularly particle filters.
  • Approximation: The weighted particle system provides an empirical point-mass approximation to the target distribution at each step.The SMC sampler generates particles and ancestor indices across the sequence of steps.
  • Particle propagation: At each step, particles are propagated by sampling ancestor indices and states from a proposal kernel.The proposal kernel can depend on the complete particle system from the preceding step.
  • Particle propagation: Ancestor indices identify each particle’s ancestral path, while resampling is represented implicitly through those indices.The particle trajectory is defined recursively from the selected ancestor and newly sampled state.
  • Weighting: Particles receive importance weights based on the ratio of successive unnormalized target densities to the proposal kernel.The displayed weight function applies for t ≥ 2, following initialization from the time-one proposal density.

3 The PGAS kernel

PGAS modifies particle Gibbs by sampling ancestor indices for the reference trajectory, addressing path degeneracy while preserving target-distribution invariance. This single forward-sweep modification can substantially improve mixing and produce high update rates in state-space inference.

  • Kernel construction: PGAS constructs Markov kernels on trajectory space by extending particle Gibbs with an ancestor-sampling step.The algorithm maps a reference trajectory stochastically into a new trajectory and defines a family indexed by the particle count N.
  • Particle Gibbs: Particle Gibbs retains a reference trajectory deterministically during SMC, then samples the output trajectory from the resulting particle paths.The reference path is intended to guide simulated particles, while one particle path is forced to coincide with it throughout the pass.
  • Theoretical validity: PGAS leaves the exact target distribution invariant for any particle count, extending the corresponding invariance property of particle Gibbs.The paper establishes this theoretical validity together with a novel uniform ergodicity result.
  • Ancestor sampling: PGAS samples the reference trajectory’s ancestor index by connecting its future segment to one of the particle histories using computed ancestor weights.The weighting construction is justified as the ancestor distribution required to preserve the kernel’s invariance properties.
  • Mixing improvement: Ancestor sampling changes only one step relative to particle Gibbs, yet the paper reports a considerable improvement in kernel mixing.It achieves the effect of backward sampling without an explicit backward pass.
  • Numerical illustration: In a stochastic-volatility example with T = 400 observations and N ranging from 5 to 1 000, update rates compare particle Gibbs and PGAS across time.Update rate is defined as the proportion of iterations in which xt changes value; Figure 1 plots it against t and includes ideal rates (N −1)/N.

4 Theoretical justification

PGAS preserves the target distribution through a particle-based Gibbs construction while addressing path degeneracy without an explicit backward pass. Under support and bounded-weight conditions, the paper establishes ergodicity properties for the resulting kernel.

  • Theorem 1 establishes that PGAS leaves the target distribution invariant for any N ≥1 and θ ∈Θ.The proof uses an extended target density and a properly collapsed Gibbs sampler.
  • Ancestor sampling breaks the reference trajectory into pieces, preventing the particle system from degenerating toward the same trajectory as ordinary PG.Figure 2 contrasts the resulting particle systems for PG and PGAS using the same reference trajectory.
  • PGAS is equivalent to a partially collapsed Gibbs sampler under the specified reference-trajectory conditioning.Algorithm 2 implements the sampling steps of the instrumental reformulation.
  • The invariance proof relies on interpreting PGAS as a properly collapsed Gibbs procedure whose collapsing order respects variable dependencies.The procedure leaves the extended target density invariant because the unused variables can be marginalized in the required order.
  • Under Assumption (A1), the proposal support covers the target support, and PGAS inherits an ergodicity result for any N ≥2.The paper identifies (A1) as the minimal support condition.
  • Under bounded importance weights in Assumption (A2), PGAS is uniformly ergodic for any N ≥2 and θ ∈Θ.The result provides constants Rθ < ∞ and ρθ ∈[0, 1).

5 PGAS for state-space models

For state-space models, PGAS provides a particle-based route to latent-state inference and parameter learning. Its ancestor-sampling formulation addresses poor mixing from path degeneracy and is related to backward simulation under specific conditions.

  • PGAS targets latent states and parameters in nonlinear, non-Gaussian state-space models.The model contains a static parameter θ, latent states xt, and observations yt.
  • Poor mixing in Gibbs sampling can result from the high autocorrelation of state trajectories.This motivates particle-based methods for jointly handling the latent trajectory and model parameters.
  • PGAS supports maximum-likelihood learning of state-space models through particle versions of EM and SAEM.The stochastic-approximation update uses trajectories simulated from the PGAS kernel instead of direct draws from the intractable smoothing density.
  • PGAS constructs a particle MCMC transition using ancestor sampling weights for the joint smoothing distribution.For learning algorithms, the unnormalized target density is pθ(x1:T, y1:T).
  • PGAS and PGBS are probabilistically equivalent for state-space models with bootstrap proposal kernels under the conditions of Proposition 1.The equivalence applies when both methods target the joint smoothing distribution and use rθ,t(xt | x1:t−1) = fθ(xt | xt−1).

6 PGAS for non-Markovian models

This section extends PGAS to non-Markovian latent-variable models, where ancestor sampling can be costly because dependencies involve entire latent histories. Truncation and adaptive evaluation reduce this cost while retaining accurate approximations under stated decay conditions.

  • Non-Markovian latent-variable models allow transition and measurement densities to depend on the entire latent history, unlike state-space models.
  • For non-Markovian models, evaluating ancestor-sampling weights can become the computational bottleneck.
  • Metropolis-Hastings within PGAS provides an alternative implementation that preserves the correct limiting distribution when its kernel leaves the relevant distribution invariant.
  • Under the stated conditions, the KL divergence between the exact and truncated ancestor-sampling distributions is bounded by C exp(−cℓ).
  • Adaptive truncation selects the level using moving averages of total-variation differences, avoiding direct specification of ℓ.
  • O(NTℓ) is the total cost when truncated weights replace exact weights directly in PGAS.

7 Numerical evaluation

The numerical studies evaluate PGAS against PG, PGBS, and particle-smoothing baselines in standard, degenerate, and reformulated non-Markovian models. Across these settings, the experiments examine mixing, truncation, dimensionality, and epidemiological parameter inference.

  • 7.1 1st order LGSS model: In the linear Gaussian state-space model, PGAS and PG are compared across particle counts using an ideal Gibbs sampler as a baseline.The experiments use T = 100 and evaluate autocorrelation functions for the parameter q.
  • 7.1 1st order LGSS model: For T = 2 000, the difference in mixing between PGAS and PG becomes more pronounced, consistent with their differing sensitivity to path degeneracy.The comparison is based on autocorrelation functions for q and is reported in Figure 4.
  • 7.2 Degenerate LGSS models: With truncation level ℓ= 1 and N = 5 particles, PGAS achieves significantly lower running RMSEs than PGBS across five independent runs.The study also compares both methods with an untruncated FFBS particle smoother using N = 10 000 particles and M = 1 000 backward trajectories.
  • 7.2 Degenerate LGSS models: Across 150 random systems with dimensions d = 2, 5, and 20, RMSE box plots assess PGAS and PGBS under multiple and adaptive truncation levels.The experiments note that mixing tends to deteriorate as model order increases and report accurate results with adaptive truncation.
  • 7.3 Epidemiological model: In the epidemiological application, PGAS estimates model parameters from eight years of weekly data and produces one-month-ahead predictions within the estimated 95 % credibility intervals.The parameter posterior distributions place the true system parameters within the credible regions, and the predictions cover subsequent disease activity.

8 Discussion

PGAS combines conditioned particle sampling with ancestor sampling to improve mixing and extend PMCMC inference beyond standard state-space models. The discussion highlights implementation advantages over backward-simulation approaches and identifies open questions about convergence rates.

  • Contribution: PGAS provides off-the-shelf Markov kernels for simulating high-dimensional, highly autocorrelated state trajectories.The kernels support both Bayesian and frequentist parameter inference as well as state inference.
  • Application: The disease-activity experiment uses four years for parameter estimation and four subsequent years for one-month-ahead predictions.Figure 8 reports the infected-individual trajectory over the full eight-year period.
  • Scope: PGAS is intended for models with complex dependencies, including non-Markovian, nonparametric, and graphical models.The method is presented as applicable beyond state-space models.
  • Method: Ancestor sampling preserves the target stationary distribution through a conditioned SMC sampler while enabling movement around the reference trajectory.Empirically, this makes mixing robust to few particles and large data records.
  • Comparison with PGBS: PGAS uses backward-simulation ideas without an explicit backward pass, simplifying implementation and reducing memory requirements for non-Markovian models.With truncated backward weights, PGAS was found more robust to approximation error than PGBS, with up to an order-of-magnitude improvement in accuracy.
  • Open questions: Further work is needed to determine how PGAS mixing rates depend on particle number, data amount, and latent-process dimension.The established uniform ergodicity result does not provide an explicit dependence on N.

A.1 Proof of Proposition 1

The proof establishes the required PGAS distributional identities by analyzing ancestor selection and using induction over bounded multiplicative functionals. For bootstrap proposals, ancestor variables do not affect the forward particle-system law.

  • Bootstrap proposal: For a bootstrap proposal, the particle weight depends only on the current state, so the forward particle-system law is independent of ancestor variables.The weight is Wθ,t(xt)=gθ(yt | xt).
  • Proof strategy: The proof reduces the result to equality of expectations for bounded multiplicative functionals of the generated trajectory.A π-λ argument extends this equality from measurable rectangles to the full product space.
  • Proof strategy: Induction over time establishes the required expectation identity, with the base case following because the terminal ancestor and comparison index have the same weight-induced distribution.The argument then proceeds for earlier time indices.
  • Induction step: The induction step combines the Markov property of the particle system with the tower property of conditional expectation and boundedness of the relevant function.These properties allow the induction hypothesis to be applied recursively.
  • Ancestor selection: Ancestor sampling yields the same conditional ancestor-selection expression for the retained particle as for ordinary particles.Bayes’ theorem gives the expression when the next ancestor is nonretained, and the ancestor-sampling rule extends it to the retained case.

A.2 Proof of Proposition 2

The proposition’s proof bounds the KL divergence between the relevant distributions, providing the stated convergence control.

  • KL-divergence bound: The KL divergence is bounded according to the proposition’s derived inequality.The supplied passage states the bound but does not include its explicit expression.
Loading 1401.0604v1…