Archive for nested sampling

approximation of Bayes Factors via mixing

Posted in Books, Statistics, University life with tags , , , , , , , , , , , on December 21, 2020 by xi'an

A [new version of a] paper by Chenguang Dai and Jun S. Liu got my attention when it appeared on arXiv yesterday. Due to its title which reminded me of a solution to the normalising constant approximation that we proposed in the 2010 nested sampling evaluation paper we wrote with Nicolas. Recovering bridge sampling—mentioned by Dai and Liu as an alternative to their approach rather than an early version—by a type of Charlie Geyer (1990-1994) trick. (The attached slides are taken from my MCMC graduate course, with a section on the approximation of Bayesian normalising constants I first wrote for a short course at Jim Berger’s 70th anniversary conference, in San Antonio.)

A difference with the current paper is that the authors “form a mixture distribution with an adjustable mixing parameter tuned through the Wang-Landau algorithm.” While we chose it by hand to achieve sampling from both components. The weight is updated by a simple (binary) Wang-Landau version, where the partition is determined by which component is simulated, ie by the mixture indicator auxiliary variable. Towards using both components on an even basis (à la Wang-Landau) and stabilising the resulting evaluation of the normalising constant. More generally, the strategy applies to a sequence of surrogate densities, which are chosen by variational approximations in the paper.

nested sampling X check

Posted in Books, Mountains, pictures, Statistics with tags , , , , , , on September 18, 2020 by xi'an

Andrew Fowlie, Will Handley and Liangliang Su have recently arXived a new paper on checking the convergence of nested sampling by a uniformity test. The argument goes as follows: if the draw from the prior under the likelihood restriction (at the core of the nested sampling principle) is correctly generated, the rank of the realised value of the associated likelihood should be uniformly distributed among the remaining likelihoods. Obviously, the opposite does not hold:  a perfectly uniform distribution can happen even when the sampler misses a particularly well-hidden mode of the target disstribution or when it systematically stops too early, using for instance a misspecified bound on the likelihood. One particular setting when uniformity fails is when the likelihood surface plateaus in a particular region of the parameter space. (As a French speaker, writing plateaus makes me cringe since the plural of plateau is plateaux! Pardon my French!) When reaching the plateau the algorithm starts accumulating at the limiting value (or else completely ignores the plateau and its prior mass). I actually wonder if the existence of plateaux is not a sufficient reason for invalidating nested sampling, at least in its original version, since it assumes a continuous distribution on the likelihood values… If no plateau comes to hinder the algorithm, the rank test could be used to calibrate the exploration algorithm as for instance in the determination of the number of MCMC steps, running in parallel T random walks until the rank test across these runs turns green. The authors of the paper suggest using a Kolmogorov-Smirnov test, which strikes me as not the most appropriate solution, given the discrete nature of the theoretical distribution and the existence of uniformity tests in the pseudo random generation literature. At a conceptual level, I am also wondering at the sequential use of the test (as opposed to a parallel version at each iteration) since the target distribution is changing at every step (and so does the approximate method used to reproduce the prior simulation under the likelihood restriction).

state of the art in sampling & clustering [workshop]

Posted in Books, pictures, Statistics, Travel, University life with tags , , , , , , , , , , on September 17, 2020 by xi'an

Next month, I am taking part in a workshop on sampling & clustering at the Max-Planck-Institut für Physik in Garching, Germany (near München). By giving a three hour introduction to ABC, as I did three years ago in Autrans. Being there and talking with local researchers if the sanitary conditions allow. From my office otherwise. Other speakers include Michael Betancourt on HMC and Johannes Buchner on nested sampling. The remote participation to this MPI workshop is both open and free, but participants must register before 18 September, namely tomorrow.

Nested Sampling SMC [a reply]

Posted in Books, Statistics, University life with tags , , , , , , , , , on April 9, 2020 by xi'an
Here is a response from Robert Salomone following my comments of the earlier day (and pointing out I already commented the paper two years ago):
You may be interested to know that we are at the tail end of carrying out a major revision of the paper, which we hope will be done in the near future — there will be some new theory (we are in the final stages for a consistency proof of the ANS-SMC algorithm with new co-author Adam Johansen), as well as new numerics (including comparisons to Nested Sampling), and additional discussion that clarifies the overall narrative.
A few comments relating your post that may clear some things up:
  • The method you describe with the auxiliary variable is actually one of three proposed algorithms. We call this one “Improved Nested Sampling” as it is the algorithm most similar to the original Nested Sampling. Two further extensions are the adaptive SMC sampler, and the fixed SMC sampler – the latter of which is provably consistent and unbiased for the model evidence (we also often see improvements over standard NS for similar computational effort when MCMC is used).
  • Regarding computational effort – it is the same for Improved NS (in fact, you can obtain the standard Nested Sampling evidence estimate from the same computational run!). For the adaptive variant, the computational effort is roughly the same for ρ = e⁻¹. In the current version of the paper this is only discussed briefly (last page of p.23). However, in the revision we will include additional experiments comparing the practical performance.
  • Regarding the question of “why not regular SMC”; we chose to focus more on why SMC is a good way to do Nested Sampling rather than why Nested Sampling is a good way to do SMC. Our main priority was to show there is a lot of opportunity to develop new nested sampling style algorithms by approaching it from a different angle. That said, Nested Sampling’s primary advantage over standard SMC seems to be in problems involving “phase transitions’’ such as our first example, for which temperature based methods are inherently ill-suited (and will often fail to detect so!).

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.”)