coupled filters

couplartPierre Jacob, Fredrik Lindsten, and Thomas Schön recently arXived a paper on coupled particle filters. A coupling problem that proves to be much more complicated than expected, due to the discrete nature of particle filters. The starting point of the paper is the use of common (e.g., uniform) random numbers for the generation of each entry in the particle system at each time t, which maximal correlation gets damaged by the resampling steps (even when using the same uniforms). One suggestion for improving the correlation between entries at each time made in the paper is to resort to optimal transport, using the distance between particles as the criterion. A cheaper alternative is inspired from multi-level Monte Carlo. It builds a joint multinomial distribution by optimising the coupling probability. [Is there any way to iterate this construct instead of considering only the extreme cases of identical values versus independent values?] The authors also recall a “sorted sampling” method proposed by Mike Pitt in 2002, which is to rely on the empirical cdfs derived from the particle systems and on the inverse cdf technique, which is the approach I would have first considered. Possibly with a smooth transform of both ecdf’s in order to optimise the inverse cdf move.  Actually, I have trouble with the notion that the ancestors of a pair of particles should matter. Unless one envisions a correlation of the entire path, but I am ensure how one can make paths correlated (besides coupling). And how this impacts likelihood estimation. As shown in the above excerpt, the coupled approximations produce regular versions and, despite the negative bias, fairly accurate evaluations of likelihood ratios, which is all that matters in an MCMC implementation. The paper also proposes a smoothing algorithm based on Rhee and Glynn (2012) debiasing technique, which operates on expectations against the smoothing distribution (conditional on a value of the parameter θ). Which may connect with the notion of simulating correlated paths. The interesting part is that, due to the coupling, the Rhee and Glynn unbiased estimator has a finite (if random) stopping time.

3 Responses to “coupled filters”

  1. […] Both are described in detail in the article. We’ve been blessed to have been advertised by xi’an’s og, so glory is just around the […]

  2. […] Both are described in detail in the article. We’ve been blessed to have been advertised by xi’an’s og, so glory is just around the […]

  3. Pierre Jacob Says:

    Thanks for having had a look at our paper! I’ll put some more explanations on Statisfaction soon.

    The sorting and interpolating ideas do not work so well when the dimension of the state space is not very small, which motivates the development of the other coupled resampling schemes.

    You can definitely introduce couplings that would be based on the whole paths instead of the latest components of the paths. In transport resampling, this could be done e.g. by simply changing the distance matrix. The index-coupled one is more exciting though, since it leverages the contracting properties of the latent process to produce correlated trajectories without ever computing pairwise distances.

    The new smoothing is what is most exciting for us! It’s surprisingly simple to code and its parallel nature should make it very competitive against state of the art methods. It’s also hopefully another step towards perfect samplers.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s