Bayesian Adaptive Sampling

Definition

Bayesian Adaptive Sampling (BAS) is an algorithm (Clyde-Ghosh-Littman 2011) for exploring the space of linear-regression models in variable selection and Bayesian model averaging that samples models without replacement from the $2^p$ candidate models. It is a deterministic-when-enumerable, adaptive-when-not alternative to Markov chain Monte Carlo model search: because each model is visited at most once, sampling effort is never wasted re-drawing already-seen models.

Key Ideas

• Model space as a binary tree. Each model is a vector $\gamma\in\{0,1\}^p$ of inclusion indicators; arrange the tree with $\gamma_1$ at the root and left/right branches for exclude/include, so every model is a unique root-to-leaf path among $2^p$ paths.
• Sampling without replacement. BAS draws paths (models) without replacement, renormalizing the probabilities over the remaining unsampled models after each draw. For enumerable problems it traverses all $2^p$ models in $2^p$ iterations; for larger problems it gives perfect without-replacement samples under stated conditions.
• Inclusion-probability sampling → median probability model. If the branch probabilities equal the marginal variable-inclusion probabilities, BAS concentrates near the median probability model (Barbieri-Berger: include variables with posterior inclusion probability $\ge 1/2$), which is optimal for prediction under some conditions.
• Adaptivity. The marginal inclusion probabilities are unknown a priori, so BAS estimates them on the fly and updates the sampling probabilities — a learning loop (bandit-flavoured) that sharpens as the posterior is revealed.
• Conjugate marginal likelihoods. Uses closed-form marginal likelihoods from the conjugate Normal-Gamma family and Zellner's g-prior and its mixtures (Zellner-Siow, hyper-g), which are simple functions of the model $R^2$.

Why It Matters

• Efficiency in the moderate-$p$ regime. When $p$ is in the tens and the model posterior is concentrated, MCMC model search (MC³) mixes slowly and re-visits dominant models; sampling without replacement extracts more distinct information per draw and can beat MCMC on estimation error.
• Exact inclusion probabilities and BMA weights. Because BAS can enumerate or near-enumerate, it produces accurate posterior inclusion probabilities and model-averaged predictions rather than frequency estimates from a dependent chain.
• Practical tool. Implemented in the widely used R package BAS.

Open Questions

• Scaling to large $p$. For very large predictor sets the $2^p$ tree is astronomically large and the without-replacement advantage over a well-tuned sampler diminishes.
• Quality of adaptive estimates. Performance depends on how well the marginal inclusion probabilities are estimated early in the run.

Related

• Variable Selection
• Bayesian Model Averaging
• Spike-and-Slab Prior
• Zellner's g-Prior
• Clyde-Ghosh-Littman (2011) Bayesian Adaptive Sampling for Variable Selection and Model Averaging
• Merlise Clyde