Archive for sequential Monte Carlo

nested sampling via SMC

Posted in Books, pictures, Statistics with tags , , , , , , , , , , , , on April 2, 2020 by xi'an

“We show that by implementing a special type of [sequential Monte Carlo] sampler that takes two im-portance sampling paths at each iteration, one obtains an analogous SMC method to [nested sampling] that resolves its main theoretical and practical issues.”

A paper by Queenslander Robert Salomone, Leah South, Chris Drovandi and Dirk Kroese that I had missed (and recovered by Grégoire after we discussed this possibility with our Master students). On using SMC in nested sampling. What are the difficulties mentioned in the above quote?

  1. Dependence between the simulated samples, since only the offending particle is moved by one or several MCMC steps. (And MultiNest is not a foolproof solution.)
  2. The error due to quadrature is hard to evaluate, with parallelised versions aggravating the error.
  3. There is a truncation error due to the stopping rule when the exact maximum of the likelihood function is unknown.

Not mentioning the Monte Carlo error, of course, which should remain at the √n level.

“Nested Sampling is a special type of adaptive SMC algorithm, where weights are assigned in a suboptimal way.”

The above remark is somewhat obvious for a fixed sequence of likelihood levels and a set of particles at each (ring) level. moved by a Markov kernel with the right stationary target. Constrained to move within the ring, which may prove delicate in complex settings. Such a non-adaptive version is however not realistic and hence both the level sets and the stopping rule need be selected from the existing simulation, respectively as a quantile of the observed likelihood and as a failure to modify the evidence approximation, an adaptation that is a Catch 22! as we already found in the AMIS paper.  (AMIS stands for adaptive mixture importance sampling.) To escape the quandary, the authors use both an auxiliary variable (to avoid atoms) and two importance sampling sequences (as in AMIS). And only a single particle with non-zero incremental weight for the (upper level) target. As the full details are a bit fuzzy to me, I hope I can experiment with my (quarantined) students on the full implementation of the method.

“Such cases asides, the question whether SMC is preferable using the TA or NS approach is really one of whether it is preferable to sample (relatively) easy distributions subject to a constraint or to sample potentially difficult distributions.”

A question (why not regular SMC?) I was indeed considering until coming to the conclusion section but did not find it treated in the paper. There is little discussion on the computing requirements either, as it seems the method is more time-consuming than a regular nested sample. (On the personal side,  I appreciated very much their “special thanks to Christian Robert, whose many blog posts on NS helped influence this work, and played a large partin inspiring it.”)

ensemble rejection sampling

Posted in Statistics with tags , , , on March 25, 2020 by xi'an

George Deligiannidis, Arnaud Doucet and Sylvain Rubenthaler have constructed a form of Rao-Blackwellised estimate out of a regular rejection sampler. Doubly surprisingly as turning importance sampling into regular sampling plus  gaining over the standard accept-reject estimate. They call their approach ensemble rejection sampling. This is done by seeing the N-sample created from the proposal as an importance sampler, exploiting the importance weights towards estimating the (intractable) normalising constant of the target density, and creating an upper bound on this estimate Ẑ. That depends on the current value X from the N-sample under consideration for acceptance as


with a probability Ẑ/Z⁺ to accept X. The amazing result is that the X thus marginaly produced is distributed from the target! Meaning that this is a case for a self-normalised importance sampling distribution producing an exact simulation from the target. While this cannot produce an iid sample, it can be exploited to produce unbiased estimators of expectations under the target. Without even resampling and at a linear cost in the sample size N.

The method can be extended to the dynamic (state-space) case. At a cost of O(N²T) as first observed by Radford Neal. However, the importance sample seems to be distributed from a product of proposals that do not account for the previous particles. But maybe accounting for the observations. While the result involves upper bounds on the dynamic importance weights, the capacity to deliver exact simulations remains a major achievement, in my opinion.

SMC 2020 [en Madrid]

Posted in pictures, Statistics, Travel, University life with tags , , , , , , , , , , , on January 30, 2020 by xi'an

Palacio Real from Casa del Campo, on Nov. 10, 2011, during a pleasant bike ride through the outskirts of Madrid and along the renovated banks of Rio ManzanaresAn announcement for the incoming SMC 2020 workshop, taking place in Madrid next 27-29 of May! The previous workshops were in Paris in 2015 (at ENSAE-CREST) and Uppsala in 2017.  This workshop is organised by my friends Víctor Elvira and Joaquín Míguez. With very affordable registration fees and an open call for posters. Here are the invited speakers (so far):

Deniz Akyildiz (University of Warwick)
Christophe Andrieu (University of Bristol)
Nicolas Chopin (ENSAE-CREST)
Dan Crisan (Imperial College London)
Jana de Wiljes (University of Potsdam)
Pierre Del Moral (INRIA)
Petar M. Djuric (Stony Brook University)
Randal Douc (TELECOM SudParis)
Arnaud Doucet (University of Oxford)
Ajay Jasra (National University of Singapore)
Nikolas Kantas (Imperial College London)
Simon Maskell (University of Liverpool)
Lawrence Murray (Uber AI)
François Septier (Université Bretagne Sud)
Sumeetpal Singh (University of Cambridge)
Arno Solin (Aalto University)
Matti Vihola (University of Jyväskylä)
Anna Wigren (Uppsala University)

postdoc at Warwick on robust SMC [call]

Posted in Kids, pictures, R, Statistics, University life with tags , , , , , , , , on January 11, 2020 by xi'an

Here is a call for a research fellow at the University of Warwick to work with Adam Johansen and Théo Damoulas on the EPSRC and Lloyds Register Foundaton funded project “Robust Scalable Sequential Monte Carlo with application to Urban Air Quality”. To quote

The position will be based primarily at the Department of Statistics of the University of Warwick. The post holder will work closely in collaboration with the rest of the project team and another postdoctoral researcher to be recruited shortly to work within the Data Centric Engineering programme at the Alan Turing Institute in London. The post holder will be expected to visit the Alan Turing Institute regularly.

Candidates with strong backgrounds in the mathematical analysis of stochastic algorithms or sequential Monte Carlo methods are particularly encouraged to apply. Closing date is 19 Jan 2020.

particular degeneracy in ABC model choice

Posted in Statistics with tags , , , , , , on February 22, 2019 by xi'an

In one of the presentations by the last cohort of OxWaSP students, the group decided to implement an ABC model choice strategy based on sequential ABC inspired from Toni et al.  (2008). and this made me reconsider this approach (disclaimer: no criticism of the students implied in the following!). Indeed, the outcome of the simulation led to the ultimate selection of a single model, exclusive of all other models, corresponding to a posterior probability of one in favour of this model. Which sounds like a drawback of the ABC-SMC model choice approach in this setting, namely that it is quite prone to degeneracy, much more than standard SMC, since once a model vanishes from the list, it can never reappear in the following iterations if I am reading the algorithm correctly. To avoid this degeneracy, one would need to keep a population of particles of a given size, for each model, towards using it as a pool for moves at following iterations… Which also means that running in parallel as many ABC-SMC filters as there are models would be equally or more efficient, a wee bit like parallel MCMC chains may prove more efficient than reversible jump for model comparison. (On the trivial side, the OxWaSP seminar on the same day was briefly interrupted by water leakage caused by Storm Eric and poor workmanship on the new building!)