Sequential Monte Carlo on large binary sampling spaces

By Christian Alexander Schäfer, Nicolas Chopin. 2011

108 citations recorded by the source corpus.

A Monte Carlo algorithm is said to be adaptive if it automatically calibrates its current proposal distribution using past simulations. The choice of the parametric family that defines the set of proposal distributions is critical for good performance. In this paper, we present such a parametric family for adaptive sampling on high dimensional binary spaces. A practical motivation for this problem is variable selection in a linear regression context. We want to sample from a Bayesian posterior distribution on the model space using an appropriate version of Sequential Monte Carlo. Raw versions of Sequential Monte Carlo are easily implemented using binary vectors with independent components. For high dimensional problems, however, these simple proposals do not yield satisfactory results. The key to an efficient adaptive algorithm are binary parametric families which take correlations into account, analogously to the multivariate normal distribution on continuous spaces. We provide a review of models for binary data and make one of them work in the context of Sequential Monte Carlo sampling. Computational studies on real life data with about a hundred covariates suggest that, on difficult instances, our Sequential Monte Carlo approach clearly outperforms standard techniques based on Markov chain exploration.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Kernel Sequential Monte Carlo (2015, methodology): “onally was employed for ﬁltering problems with a sequence of time-varying target distributions [4], has been employed as an alternative to MCMC in the context of a single (static) target distribution [5, 6, 7, 8, 1], with particular success on multi-modal targets, and for estimating model evidence. ”
On the stability of sequential Monte Carlo methods in high dimensions (2011, background): “many practical contexts: financial modeling [32], regression [46] and approximate Bayesian inference [23].”
Towards Automatic Model Comparison: An Adaptive Sequential Monte Carlo Approach (2013, methodology): “The Bayesian Information Criterion (BIC), developed by Schwarz (1978), is based upon a large sample approximation of the Bayes factor.”
BAYESIAN LINEAR REGRESSION WITH SPARSE PRIORS (2014, methodology): “In [39, 42] such methods are shown to perform well for model selection in regression models with up to hundreds of covariates.”
Gradient Importance Sampling (2015, background): “This approach is very robust when compared to MCMC algorithms, as it explores the probability space better [5, 3].”
An Adaptive Sequential Monte Carlo Sampler (2010, methodology): “The optimum scaling for the Gaussian proposal kernel, hopt, was computed using 1-dimensional numerical integration and Theorem 1 of Sherlock and Roberts (2009). The left plot in Figure 1 shows g(h) for this target explored by the Gaussian proposal kernel (black) and the multivariate t proposal (gree”