Source-linked AI summary
Evolutionary Stochastic Search for Bayesian model exploration
Leonardo Bottolo, Sylvia Richardson
TL;DR
Bayesian variable selection becomes difficult when the model space grows rapidly with the number of covariates, limiting operational analysis of linear Gaussian regression models. The paper proposes a new sampling algorithm with an automatic temperature-ladder choice and reports effective local moves that work under both g-prior and independent-prior settings.
Problem
Rapid growth of the model space makes Bayesian variable selection in linear Gaussian regression models difficult to operationalize for datasets with many covariates.
Method
The paper proposes a new sampling algorithm for variable selection, using a conjugate model structure and automatic choice of the temperature ladder during burn-in.
Results
The proposed Scan Metropolis Hastings sampler achieves effective local moves, and the latter strategy works in both g-prior and independent-prior cases.
Takeaways & Limitations
The new local move is reported as superior and performs well across the g-prior and independent-prior settings.
Takeaways & Limitations
The approach has so far been applied only to linear regression with a univariate response.
Abstract
from arXiv · showhide
Implementing Bayesian variable selection for linear Gaussian regression models for analysing high dimensional data sets is of current interest in many fields. In order to make such analysis operational, we propose a new sampling algorithm based upon Evolutionary Monte Carlo and designed to work under the "large p, small n" paradigm, thus making fully Bayesian multivariate analysis feasible, for example, in genetics/genomics experiments. Two real data examples in genomics are presented, demonstrating the performance of the algorithm in a space of up to 10,000 covariates. Finally the methodology is compared with a recently proposed search algorithms in an extensive simulation study.
1 Introduction
The paper develops a Bayesian variable-selection sampler for linear Gaussian regression, targeting high-dimensional multimodal model spaces where exhaustive enumeration and standard MCMC face difficulties. It adapts Evolutionary Monte Carlo ideas and evaluates the resulting algorithm on real and simulated examples, including comparisons with Shotgun Stochastic Search.
- Method: The paper proposes a new sampling algorithm based on tailoring Evolutionary Monte Carlo ideas to explore the model space.The algorithm is intended to overcome difficulties faced by MCMC samplers in high-dimensional multimodal spaces.
- Motivation: Bayesian variable selection for linear Gaussian regression is difficult when the covariate dimension is high because the model space grows rapidly and becomes infeasible to enumerate.The model-space search must sample selected-covariate indicators and any parameters not integrated out.
- Method: The algorithm has generic features and can be coupled with different prior formulations for the regression-coefficient variance-covariance matrix.The paper illustrates this flexibility with g-priors and independent priors, including hierarchical prior extensions.
- Evaluation: The sampler uses a wide portfolio of moves, including two newly proposed moves, and its performance is demonstrated in real and simulated examples.The examples involve different predictor structures and include genomics applications and simulations.
- Evaluation: The simulation study compares the new algorithm with Hans et al.'s Shotgun Stochastic Search algorithm.This comparison complements the reported real-data and simulation results.
2 Background
The background formulates Bayesian subset selection for linear Gaussian regression through latent inclusion indicators and prior distributions over coefficients and model size. It emphasizes conjugate marginal likelihoods, contrasts g-priors with independent and Zellner–Siow alternatives, and notes computational trade-offs among specifications.
- Variable selection: Variable selection seeks a subset of predictors for modeling y, especially when p is large and parsimonious models are desired for interpretability.The latent binary vector γ records whether each coefficient is included, yielding 2^p possible models.
- Variable selection: A Gaussian linear model conditions on γ by extracting the nonzero coefficient vector βγ and corresponding design matrix Xγ.The selected design matrix has n×pγ dimensions, where pγ is the number of included predictors.
- Prior specifications: The conjugate prior structure makes the marginal likelihood analytically tractable for different prior covariance matrices Σγ.The paper uses this tractability to discuss g-priors and independent priors within a unified notation.
- Model-space prior: The beta-binomial prior on γ induces a distribution over model size whose hyperparameters can be chosen from elicited expectations and variances.In the large p, small n setting, the prior is recommended to favor sparse models with pγ ≪ p.
- Prior specifications: g-priors set Σγ = gVγ and provide automatic scaling, whereas independent priors use Vγ = Ipγ and are attractive when variables share a common scale.For independent priors, the posterior covariance is driven toward the independence case.
- Computational considerations: Zellner–Siow priors adapt the shrinkage parameter τ but remove closed-form availability of the marginal likelihood, while independent-prior likelihoods require an extra determinant and are more computationally demanding than g-priors.QR decomposition ensures the independent-prior marginal likelihood is defined, including when n ≤ pγ.
3 MCMC sampler
The sampler combines Evolutionary Monte Carlo with local and global genetic-algorithm-inspired moves to explore multimodal, high-dimensional variable-selection spaces. Its design targets large p, small n settings by improving computational efficiency, mixing, and temperature exchange.
- EMC framework: Evolutionary Monte Carlo uses parallel chains at different temperatures to reduce trapping in local posterior modes and transmit state information across chains.The non-heated chain records the sampled binary vector while chains exchange states probabilistically.
- Target distribution: The sampler integrates out β and σ^2, leaving the latent binary vector and variable-selection coefficient as the parameters to sample.Each chain has temperature t_l with 1 = t_1 < t_2 < ··· < t_L.
- EMC framework: The algorithm updates binary inclusion vectors with local Metropolis-Hastings or Gibbs moves and global selection, crossover, and exchange moves.Global moves are crucial because they allow jumps between local modes.
- Novel moves: The implementation adds a correlation-informed global move and a local FSMH move designed for large predictor spaces.The method uses a wide portfolio of moves to improve mixing in complex predictor spaces.
- Local moves and FSMH: For large p, the Fast Scan Metropolis-Hastings sampler avoids the cost of a full Gibbs cycle over all p indicators.Its acceptance/rejection step selects which indices receive Gibbs-like updates and uses both current model size and chain temperature.
- Temperature and τ updates: Temperature placement is tuned to promote effective interchange between chains, while adaptive Metropolis-within-Gibbs updates sample τ when its full conditional lacks closed form.The population can instead share a common τ, alleviating earlier convergence and mixing problems.
4 Performance of ESS
ESS performs effectively across genomics examples and simulation comparisons, including settings with thousands of covariates. Its adaptive temperature strategy and new moves support mixing, model exploration, and competitive search performance.
- Real data examples: Automatic temperature placement produces overlapping chain distributions that enable effective information exchange.The chains marginally reach equilibrium, while temperature adaptation during burn-in improves overlap of log posterior probabilities.
- Real data examples: Data-driven shrinkage favors smaller models and helps the search discriminate among competing models.The hyperprior version also shows higher stability among the top 1,000 visited models ranked by posterior probability.
- Real data examples: ESS maintains efficient chain mixing in the mQTL example with n = 50 and p = 10,000.The reported acceptance behavior was not substantially affected across examples with p ranging from 60 to 1,000.
- Simulation study: ESSg with FSMH reaches the same top visited model in 68% of 25 runs with fixed τ and 88% with the Z-S prior.The corresponding MC3 rates are 28% and 40%, respectively.
- Simulation study: With fixed τ, block crossover finds the best model in 80% of runs versus about 60% for other crossover operators.The block crossover also has higher acceptance and greater capacity to accumulate posterior mass.
- Simulation study: ESSi explores competing models more fully than SSSi while retaining comparable goodness-of-fit and stability measures.ESSi also shows a computational-time advantage, especially when the estimated pγ is large.
5 Discussion
The discussion presents ESS as a parallel-tempering sampler tailored to large-p variable selection through temperature adaptation and efficient local updates. It highlights strong search performance while identifying computational and inferential scope boundaries.
- Algorithmic design: The temperature parameter weakens the likelihood contribution and enables chains to escape local modes.The temperature strategy works in both g-prior and independent-prior settings.
- Limitations and extensions: Running parallel chains at different temperatures is computationally expensive, so exchange gains must be balanced against added cost.The discussion motivates careful selection of chain pairs as a response to this trade-off.
- Algorithmic design: ESS combines parallel tempering with automatic temperature-ladder selection during burn-in to improve exchanges in multimodal posterior spaces.The strategy uses marginal and joint chain information to select both bold and conservative exchanges.
- Algorithmic design: FSMH updates a subset of latent-variable indices, providing a compromise between infeasible full Gibbs scans and add/delete moves when p is large.The comparison with MC3 reports superiority of the new local move.
- Limitations and extensions: The current implementation does not use heated-chain output for posterior inference, leaving possible variance reduction for future work.The authors place this investigation beyond the scope of the present work.
- Limitations and extensions: The approach has so far been applied to linear regression with a univariate response y.A multidimensional n × q response extension is described as an interesting generalisation and has been implemented in a genomics case study.
A Technical details of EMC implementation
This appendix section introduces technical details of the sampling schemes for the binary latent vectors γ and the selection coefficient τ.
- Technical implementation: The technical appendix describes implementation details for sampling the population of binary latent vectors γ and the selection coefficient τ.
Local move: FSMH scheme
The FSMH local move uses random-scan Metropolis-within-Gibbs updates for binary inclusion indicators, reducing computation when p is large. It trades lower per-iteration statistical efficiency for better efficiency per floating-point operation.
- Transition probabilities: The proposal probabilities and acceptance probabilities are defined separately for inclusion and exclusion transitions of each variable in each chain.The construction is specialized for the Evolutionary Monte Carlo local move.
- FSMH scheme: FSMH is a random-scan Metropolis-within-Gibbs algorithm whose evaluation count depends on current model size and chain temperature.The extra acceptance/rejection computation is described as modest because it uses a normalized tempered expression.
- FSMH scheme: FSMH proposes binary indicator values using Bernoulli probabilities and applies an additional acceptance/rejection step when the proposed value changes.The scheme operates within each chain and selects another covariate when the proposed value is unchanged.
- Efficiency trade-off: For a fixed iteration count, Gibbs sampling has lower MCMC standard error than FSMH.The comparison concerns statistical efficiency rather than computational cost per operation.
- Efficiency trade-off: When p is very large, FSMH becomes more efficient per floating-point operation because full Gibbs sampling is computationally more expensive.
Global move: exchange operator
ESS improves exchange between temperature-ladder chains through delayed-rejection and all-exchange operators, while adapting the ladder during burn-in to target efficient acceptance.
- Exchange design: The exchange operator swaps binary latent states between chains, extending ordinary crossover through temperature-ladder moves.The paper describes exchange as an extreme crossover case and selects chains for state swapping.
- Delayed rejection: Delayed rejection first attempts distant-chain swaps, then falls back to adjacent-chain selection after rejection.This increases mixing without drastically reducing acceptance rates.
- Acceptance limitations: Acceptance for randomly selected chain pairs decreases exponentially with |1/t_l − 1/t_r|, causing most proposed moves to be rejected.The delayed-rejection move addresses this problem by retrying between adjacent chains.
- All-exchange operator: The all-exchange operator evaluates all L(L−1)/2 pairwise exchange rates and can replace several adjacent swaps with one move.Its distant swaps may be rare events with low and unknown acceptance probability.
- Temperature tuning: During burn-in, the geometric temperature ratio b is adjusted every batch so delayed-rejection acceptance approaches 0.50.The initial ladder satisfies t_l+1/t_l = b with b > 1, and updates use an increment δ_b.
B Performance of ESS: Simulation study
The simulation study evaluates ESSi against SSS under matched settings, using independent priors and a fixed τ to support a fair comparison.
- Experimental setup: ESSi assumes independent priors with Σ_γ = τI_pγ, enabling comparison with SSS, which also implements an independent prior.The comparison fixes τ at 1 and standardizes covariates before sampling.
- Experimental setup: ESSi and SSS 2.0 are run for 22,000 sweeps with matching model-size hyperparameters.This design keeps the computational effort and model-size specification aligned across algorithms.
- Experimental setup: A separate implementation examines ESS mixing when the prior p(τ) is defined directly on τ.The study therefore considers both fixed-τ comparisons and prior-based τ exploration.
B.1 Simulated experiments
The experiments test ESSi across increasingly difficult simulated regression designs, including p > n, strong multicollinearity, contamination, and naturally correlated genetic data.
- Study design: ESSi is evaluated on six simulated examples spanning n > p and p > n settings, varied sample sizes, effect sizes, and error variances.Examples Ex1–Ex5 use constructed covariance structures, while Ex6 uses phased HapMap genotype data.
- Study design: The constructed designs combine X1 and X2 blocks to create moderate, strong, and increasingly intricate correlations among covariates.X2 includes pairwise correlations of about 0.998 for selected neighboring variables.
- Selection challenges: Ex2 tests whether ESSi avoids selecting variables from a correlated second block that does not generate the response.This probes variable-selection specificity under complicated correlation structures.
- Selection challenges: Ex3 tests selection of a large subset of variables while excluding the first 15 null variables.The 60 predictors are partitioned into groups with coefficients 0, 1, 2, and 3.
- Selection challenges: Ex5 evaluates robustness to contamination by combining a dominant model with a second model that has a non-negligible effect.The experiment also tests whether ESS can move between local modes and select the secondary model.
- Study design: Each example is replicated 25 times, with 20,000 post-burn-in sweeps recorded after 2,000 burn-in sweeps for automatic temperature tuning.Ex6 averages across replicates only for mixing properties because its effect sizes vary.
B.2 Mixing properties of ESSi
ESSi shows effective chain mixing and stable exchange acceptance across simulated problems, including p > n, although higher-temperature chains remain more variable and could be tuned further.
- Mixing performance: ESSi reaches convergence between chains 3 and 4 and between chains 4 and 5 in Examples 3–6.Trace plots also show mixing in the p > n case.
- Mixing performance: The automatically tuned temperature ladder produces overlapping chain distributions, allowing effective exchange of information.This pattern is reported for both overall mixing and log-posterior distributions.
- Crossover performance: The crossover operator has stable acceptance across examples, including p > n, with averages ranging from 0.147 in Ex4 to 0.193 in Ex6.The paper relates this performance to the selection operator and new block crossover within the limited experiments.
- Limitations: Fewer global moves appear to be accepted by the higher-temperature chain, indicating that further temperature-ladder tuning may be possible.Higher-temperature chains also show more variability in their overlap indices.
Comparison with SSS
Compared with SSS, ESSi generally agrees on marginal inclusion probabilities while exploring the model space more fully, especially for small effects. ESSi also offers computational advantages when the fitted model is large, although SSS can be more stable in some settings.
- ESSi detects covariates with small effects in several examples, including coefficients β2 = 0.112 and β10 = 0.950 in Ex6.
- ESSi can miss small effects, including β16 = 0.5 in Ex4, showing that weak signals are not always detected.
- ESSi and SSS generally agree on marginal posterior inclusion probabilities across the simulated examples.
- ESSi more fully explores the model space and finds small effects, producing posterior model sizes closer to the true size.
- ESSi and SSS show general agreement on goodness of fit and stability, but SSS is more stable across all examples.
- ESSi is computationally faster when the simulated and estimated model size is large, especially when pγ ≳10, because it evaluates fewer models per sweep.
- ESSi is generally robust and competitive with SSS, while SSS is faster in Ex5 but underestimates the simulated model and evaluates fewer models.