Bayesian Adaptive Sampling for Variable Selection and Model Averaging

Merlise A. Clyde, Joyee Ghosh, Michael L. LittmanJournal of Computational and Graphical Statistics 2010 · DOI

TL;DR

This paper introduces Bayesian Adaptive Sampling (BAS), a novel algorithm for efficiently exploring the vast space of possible models in linear regression. BAS samples models without replacement, outperforming traditional Markov Chain Monte Carlo (MCMC) methods in finding high-probability models and providing more accurate estimates, especially in complex scenarios with correlated predictors.

What Problem Does This Paper Address?

In statistical modeling, particularly linear regression, selecting the "best" set of predictor variables is a fundamental challenge. The number of possible models grows exponentially with the number of predictors ($2^p$), making exhaustive search computationally infeasible for even moderately sized problems. Traditional methods like MCMC can struggle with highly correlated predictors, leading to slow exploration of the model space and potentially biased results. This paper addresses the need for an efficient and robust algorithm that can navigate this complex model space, sample models without replacement, and provide accurate inferences.

Methods

The core contribution is the Bayesian Adaptive Sampling (BAS) algorithm. BAS represents the model space as a binary tree, allowing for efficient sampling without replacement. Key features include:

  • Sampling without Replacement: Unlike standard MCMC, BAS ensures that each model is sampled at most once, which can be more efficient when the goal is to explore the entire model space or a large fraction of it.
  • Adaptive Updating: Since the true marginal inclusion probabilities (which guide sampling) are unknown, BAS adaptively estimates them using the marginal likelihoods of the sampled models. This allows the algorithm to learn and focus on more promising regions of the model space.
  • Binary Tree Representation: The model space is structured as a binary tree, enabling efficient computation of re-normalized probabilities and direct sampling without replacement.
  • Initial Sampling Strategies: The paper proposes several methods for initializing the sampling probabilities, including uniform probabilities, p-value calibration ("eplogp"), and estimates derived from MCMC runs.

Datasets

The paper uses two datasets for evaluation:

  • Simulated Data: A dataset with $p=15$ predictors and $n=100$ observations was generated to allow for exact posterior model probabilities via enumeration. This dataset was designed with a pair of highly correlated predictors to test the algorithm's performance in challenging scenarios.
  • U.S. Crime Data: A real-world dataset previously analyzed in the literature, with $p=15$ predictors.
  • Protein Activity Data: A real-world dataset with a large number of potential predictors ($p=88$), characterized by high correlations among variables, posing a significant model search challenge.

Key Insights and Ideas

  • Sampling without replacement is crucial for efficiency: When exploring a large model space, avoiding redundant sampling of models can significantly speed up the process and lead to more comprehensive coverage.
  • Adaptive learning is key: The marginal inclusion probabilities are unknown and change as more models are sampled. BAS's ability to adaptively update these probabilities allows it to efficiently focus on high-probability regions.
  • BAS outperforms MCMC in finding high-probability models: Especially in scenarios with correlated predictors, BAS demonstrates a superior ability to quickly identify models with high posterior probability.
  • The median probability model (MPM) is a useful target: BAS's sampling strategy is motivated by the properties of the MPM, which is often preferred in practice over the highest posterior probability model.

Key Results

  • Improved MSE: In simulation studies where enumeration was possible, BAS achieved improved Mean Squared Error (MSE) for various quantities of interest compared to standard MCMC algorithms, even when sampling only a fraction of the model space.
  • Effective exploration of model space: For the U.S. Crime data, BAS sampled all $2^{15}$ models in a fraction of the time it took for RS-Thin to sample only a small subset, while leaving a much smaller unsampled mass.
  • Competitive performance on complex data: In the Protein Activity data with $p=88$, BAS, particularly when initialized with MCMC estimates, found higher log-marginal likelihoods than other methods, suggesting it is effective in high-dimensional, correlated settings.
  • BAS-uniform shows promise in cross-validation: Interestingly, the BAS variant using uniform initial probabilities yielded the smallest cross-validation error on the Protein Activity data, suggesting that even simpler initialization can be effective for predictive tasks.

Limitations and Future Work

  • Computational cost of adaptive updating: While beneficial, adaptively updating sampling probabilities can be computationally expensive, requiring retracing sampled paths. The paper suggests compromises like periodic updates.
  • Bias in adaptive estimates: While BAS is Fisher-consistent, the adaptive estimates of inclusion probabilities can be biased, especially early in the sampling process.
  • Future work: The authors plan to extend BAS to generalized linear models using Laplace approximations for marginal likelihoods. They also suggest exploring parallel implementations of BAS and investigating alternative estimators to address sampling bias in MCMC and PPS sampling. Further comparisons with state-of-the-art algorithms incorporating more complex global moves are also recommended for high-dimensional problems.

Summary updated

Abstract

For the problem of model choice in linear regression, we introduce a Bayesian adaptive sampling algorithm (BAS), that samples models without replacement from the space of models. For problems that permit enumeration of all models, BAS is guaranteed to enumerate the model space in 2p iterations where p is the number of potential variables under consideration. For larger problems where sampling is required, we provide conditions under which BAS provides perfect samples without replacement. When the sampling probabilities in the algorithm are the marginal variable inclusion probabilities, BAS may be viewed as sampling models “near” the median probability model of Barbieri and Berger. As marginal inclusion probabilities are not known in advance, we discuss several strategies to estimate adaptively the marginal inclusion probabilities within BAS. We illustrate the performance of the algorithm using simulated and real data and show that BAS can outperform Markov chain Monte Carlo methods. The algorithm is implemented in the R package BAS available at CRAN. This article has supplementary material online.
BibTeX
@article{clyde2010bayesian,
  author = {Merlise A. Clyde and Joyee Ghosh and Michael L. Littman},
  title = {{Bayesian Adaptive Sampling for Variable Selection and Model Averaging}},
  journal = {Journal of Computational and Graphical Statistics},
  year = {2010},
  doi = {10.1198/jcgs.2010.09049},
}
Figure