Clyde-Ghosh-Littman (2011) Bayesian Adaptive Sampling for Variable Selection and Model Averaging

Summary

Clyde, Ghosh and Littman introduce Bayesian Adaptive Sampling (BAS), an algorithm for model choice and model averaging in linear regression that samples models without replacement from the space of $2^p$ models. When all models can be enumerated, BAS is guaranteed to traverse the whole space in $2^p$ iterations; for larger problems it yields (under stated conditions) perfect samples without replacement. Setting the sampling probabilities to the marginal variable-inclusion probabilities makes BAS sample near the Barbieri-Berger median probability model; since those probabilities are unknown in advance, the paper gives strategies to estimate them adaptively as sampling proceeds. Simulations and real data show BAS can outperform MCMC; it ships as the R package BAS.

Key Claims

• Sample without replacement. Represent each model as a binary vector $\gamma\in\{0,1\}^p$ and the model space as a binary tree ($\gamma_1$ at the root, left/right = exclude/include); BAS draws unique root-to-leaf paths without replacement, renormalizing the remaining probability after each draw — so no model is ever revisited (unlike with-replacement MCMC).
• Enumeration guarantee. For $p$ small enough to enumerate, BAS visits all $2^p$ models in $2^p$ steps; for larger $p$ it provides perfect without-replacement samples under conditions on the sampling probabilities.
• Median probability model connection. If sampling probabilities equal the marginal inclusion probabilities, BAS concentrates near the median probability model (Barbieri-Berger) — the model including exactly the variables with inclusion probability $\ge 1/2$.
• Adaptive inclusion probabilities. Because marginal inclusion probabilities are not known a priori, BAS estimates them on the fly (several strategies), improving sampling efficiency as it learns the posterior.
• Conjugate marginal likelihoods. Works with the conjugate Normal-Gamma family and Zellner's g-prior (and mixtures such as Zellner-Siow and the hyper-g of Liang et al.), whose marginal likelihoods are closed-form functions of the model $R^2$.

Concepts Introduced or Extended

• Bayesian Adaptive Sampling
• Variable Selection
• Bayesian Model Averaging

Entities Mentioned

• Merlise Clyde
• Joyee Ghosh (UNC/Iowa biostatistics); Michael Littman (computer science, Rutgers/Brown) — coauthors

Quotes

"We introduce a Bayesian adaptive sampling algorithm (BAS), that samples models without replacement from the space of models … BAS may be viewed as sampling models 'near' the median probability model of Barbieri and Berger."

My Take

A neat reframing of the model-search problem: instead of running a with-replacement Markov chain that wastes effort revisiting the same high-probability models, treat the $2^p$ model space as a tree and sample distinct models without replacement, so every draw is new information. That is exactly the right instinct when $p$ is moderate (tens of predictors) and the posterior is concentrated — the regime where MC³ mixes slowly but full enumeration is just out of reach. The median-probability-model link ties it to optimal-prediction theory, and the adaptive estimation of inclusion probabilities is the bandit-flavoured part (unsurprising given Littman's involvement). The honest caveat is scaling: for very large $p$ the tree is astronomically large and the without-replacement advantage over a well-tuned sampler fades.