Final update on unbiased smoothing

Two coupled chains, marginally following a conditional particle filter algorithm with ancestor sampling, and meeting in 20 iterations. Script here.


Two years ago I blogged about couplings of conditional particle filters for smoothing.  The paper with Fredrik Lindsten and Thomas Schön has just been accepted for publication at JASA, and the arXiv version and github repository are hopefully in their final forms. Here I’ll mention a few recent developments and follow-up articles by other researchers.

Smoothing refers to many things in data analysis; here I’m referring to the task of estimating a latent stochastic process given noisy measurements of it, using hidden Markov or state space models. For instance, you observe measurements of the location of an object/animal over time (maybe obtained by radar/GPS), and you want to retrieve the distribution of possible trajectories given the measurements, see here for an example in ecology. There are many occurrences of this problem and in general Monte Carlo methods are required. Our paper proposes an unbiased Monte Carlo method for this task, following the groundbreaking paper by Glynn and Rhee that showed that coupled Markov chains could lead to unbiased estimators with respect to the invariant distribution of these chains.

The later realization that this technique could be applied to generic MCMC algorithms led to a series of works on unbiased MCMC estimators; initially, we wrongly thought that it was applicable to only a few MCMC algorithms such as conditional particle filters, because of some special properties that they might have such as uniformly ergodicity.

In another post, I’ll write more about why we might care about unbiasedness, particularly in a parallel computing environment (following Glynn & Heidelberger’s series of papers on parallel replicate simulations, e.g. here). Here I’ll mention two recent articles that are related to couplings of conditional particle filters.

  • Blind Identification Based On Expectation-Maximization Algorithm Coupled With Blocked Rhee-Glynn Smoothing Estimator, by  Wenhao Chen, Lu Ma, and Xuwen Liang, published in IEEE Communications Letters (2018). This paper uses the proposed unbiased estimators within the E-step of an Expectation-Maximization algorithm for parameter estimation, in a signal processing setting.
  • Coupled conditional backward sampling particle filter, by Anthony Lee, Sumeetpal S. Singh, and Matti Vihola (arXiv, 2018). The authors consider similar coupled algorithms and obtain theoretical results on the distribution of meeting times. The dependencies on the number of particles and on the time horizon are studied explicitly. The part on the advantages of performing backward/ancestor sampling is also very relevant, as these techniques can lead to dramatic improvements in practice, and it hasn’t been studied much before, as far as I am aware.

Published by Pierre Jacob

Associate professor, Harvard University

One thought on “Final update on unbiased smoothing

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: