Variable Selection

bayesianvariable-selectionspike-and-slabregressiongibbs-samplermodel-selectionconjugate-priorgray-codemetropolis-hastingsvarstochastic-search

Definition

Variable selection is the problem of identifying which subset of pp candidate regressors X1,…,XpX_1,\ldots,X_p should enter a linear model Y=Xγβγ+εY = X_\gamma\beta_\gamma + \varepsilon, trading off model fit against complexity across the 2p2^p possible subsets. Bayesian approaches assign a prior over subsets and use posterior inference to identify high-probability models.

Key Ideas

How It Works

Stochastic Search Variable Selection (George-McCulloch 1993)

The SSVS formulation links each βi\beta_i to a latent inclusion indicator γi\gamma_i via a mixture prior:

βi∣γi∼(1−γi) N(0, τi2)+γi N(0, ci2τi2)(eq. 2)\beta_i|\gamma_i \sim (1-\gamma_i)\,\mathcal{N}(0,\,\tau_i^2) + \gamma_i\,\mathcal{N}(0,\,c_i^2\tau_i^2) \tag{eq. 2}

with τi\tau_i small (exclusion: spike) and ci≫1c_i \gg 1 (inclusion: slab). This does not hard-zero βi\beta_i when γi=0\gamma_i=0; instead it shrinks it toward zero by a factor of cic_i. The joint prior is:

β∣γ∼Np(0, DγRDγ)(eq. 4)\beta|\gamma \sim \mathcal{N}_p(0,\, D_\gamma R D_\gamma) \tag{eq. 4}

where Dγ=diag[a1τ1,…,apτp]D_\gamma = \mathrm{diag}[a_1\tau_1,\ldots,a_p\tau_p] with ai=1a_i = 1 if γi=0\gamma_i=0 and ai=cia_i=c_i if γi=1\gamma_i=1 (eq. 5). The error variance prior is σ2∣γ∼IG(νγ/2, νγλγ/2)\sigma^2|\gamma \sim \mathrm{IG}(\nu_\gamma/2,\, \nu_\gamma\lambda_\gamma/2) (inverse-gamma (IG), eq. 6).

Three-block Gibbs sampler (given current draws (βj−1,σj−1,γj−1)(\beta^{j-1},\sigma^{j-1},\gamma^{j-1})):

Block 1 — βj\beta^j: Conjugate Normal update (eq. 13): βj∼Np ⁣(Aγ(σj−1)−2X′Xβ^LS,  Aγ)\beta^j \sim \mathcal{N}_p\!\left(A_\gamma(\sigma^{j-1})^{-2}X'X\hat\beta_{LS},\; A_\gamma\right) Aγ=((σj−1)−2X′X+Dγ−1R−1Dγ−1)−1A_\gamma = \left((\sigma^{j-1})^{-2}X'X + D_\gamma^{-1}R^{-1}D_\gamma^{-1}\right)^{-1}

Block 2 — σj\sigma^j: Conjugate Inverse-Gamma update (eq. 14): σj∼IG ⁣(n+νγ2,  ∥Y−Xβj∥2+νγλγ2)\sigma^j \sim \mathrm{IG}\!\left(\frac{n+\nu_\gamma}{2},\; \frac{\|Y-X\beta^j\|^2 + \nu_\gamma\lambda_\gamma}{2}\right)

Block 3 — γij\gamma_i^j: Independent Bernoulli draws componentwise (eqs. 15–16). For each ii: P(γi=1∣βj,γ(i))=aa+bP(\gamma_i=1|\beta^j, \gamma_{(i)}) = \frac{a}{a+b} where (eqs. 16c–d): a=f(βj∣γ(i), γi=1)⋅pi,b=f(βj∣γ(i), γi=0)⋅(1−pi)a = f(\beta^j|\gamma_{(i)},\, \gamma_i=1)\cdot p_i, \qquad b = f(\beta^j|\gamma_{(i)},\, \gamma_i=0)\cdot(1-p_i) Each f(⋅)f(\cdot) is a univariate Normal density evaluation at βij\beta_i^j under the spike or slab component — the γi\gamma_i conditional does not depend on YY directly, only through the already-drawn βj\beta^j.

Tuning Parameters

The method requires choices for (τi,ci,pi)(\tau_i, c_i, p_i):

Unified Hierarchical Framework (George-McCulloch 1997)

George-McCulloch (1997) embeds SSVS within a unified hierarchical mixture model:

f(Y∣β,σ)=Nn(Xβ,σ2I),π(β,σ,γ)=π(β∣σ,γ)π(σ∣γ)π(γ)f(Y|\beta,\sigma) = \mathcal{N}_n(X\beta,\sigma^2 I), \quad \pi(\beta,\sigma,\gamma) = \pi(\beta|\sigma,\gamma)\pi(\sigma|\gamma)\pi(\gamma)

π(γ)=∏iwiγi(1−wi)1−γi(eq. 4)\pi(\gamma) = \prod_i w_i^{\gamma_i}(1-w_i)^{1-\gamma_i} \tag{eq. 4}

Two prior formulations emerge from this framework:

Nonconjugate prior (= SSVS): π(β∣γ)=Np(0,DγRγDγ)\pi(\beta|\gamma) = \mathcal{N}_p(0,D_\gamma R_\gamma D_\gamma) (eq. 5); β\beta and σ\sigma are independent given γ\gamma. Point-mass limit (v0→0v_0 \to 0): π(βi∣γ)=(1−γi)I0+γiN(0,v1γ(i))\pi(\beta_i|\gamma) = (1-\gamma_i)I_0 + \gamma_i\mathcal{N}(0,v_{1_{\gamma(i)}}) (eq. 9) — makes Gibbs reducible. Practical δ\delta-threshold: log⁡(v1/v0)/(v0−1−v1−1)=δ2\log(v_1/v_0)/(v_0^{-1}-v_1^{-1}) = \delta^2 (eq. 8).

Conjugate prior (new in 1997): π(β∣σ,γ)=Np(0,σ2Dγ∗RγDγ∗)\pi(\beta|\sigma,\gamma) = \mathcal{N}_p(0,\sigma^2 D^*_\gamma R_\gamma D^*_\gamma) (eq. 15); β\beta and σ\sigma are not independent given γ\gamma. Marginal of βi\beta_i is tt-distributed (eq. 19). Translation from nonconjugate scale: v0∗=v0/σ^2v^*_0 = v_0/\hat\sigma^2, v1∗=v1/σ^2v^*_1 = v_1/\hat\sigma^2 (eq. 18). Point-mass limit: π(βi∣σ,γ(i))=(1−γi)I0+γiT(ν,0,λγv1γ(i)∗)\pi(\beta_i|\sigma,\gamma_{(i)}) = (1-\gamma_i)I_0 + \gamma_i T(\nu,0,\lambda_\gamma v^*_{1_{\gamma(i)}}) (eq. 21).

Analytical Marginal Posterior Under Conjugate Prior (George-McCulloch 1997)

With the conjugate prior, β\beta and σ2\sigma^2 can be integrated out analytically, leaving a posterior over the discrete γ\gamma space alone. When v0∗>0v^*_0 > 0:

π(γ∣Y)∝g(γ)≡∣X~′X~∣−1/2 ∣Dγ∗RγDγ∗∣−1/2 (νλ+Sγ2)−(n+ν)/2 π(γ)(eq. 24)\pi(\gamma|Y) \propto g(\gamma) \equiv |\tilde X'\tilde X|^{-1/2}\,|D^*_\gamma R_\gamma D^*_\gamma|^{-1/2}\,(\nu\lambda+S^2_\gamma)^{-(n+\nu)/2}\,\pi(\gamma) \tag{eq. 24}

Sγ2=Y′Y−Y′X ⁣(X′X+(Dγ∗RγDγ∗)−1)−1X′Y(eq. 25)S^2_\gamma = Y'Y - Y'X\!\left(X'X+(D^*_\gamma R_\gamma D^*_\gamma)^{-1}\right)^{-1}X'Y \tag{eq. 25}

The g-prior case (v0∗≡0v^*_0 \equiv 0) yields a simplified formula (eqs. 27–28). This reduces the three-block Gibbs to a one-block sampler over the 2p2^p discrete γ\gamma space — a major computational simplification.

Fast Updating and Gray Code Exhaustive Evaluation (George-McCulloch 1997)

Chambers (1971) condition (29): When v0∗>0v^*_0>0 and Rγ=IR_\gamma=I, flipping one γi\gamma_i updates g(γ)g(\gamma) in O(p2)O(p^2) (Chambers rank-1 update):

g(γ)=(∏iTii2[(1−γi)v0∗+γiv1∗])−1/2(νλ+Y′Y−W′W)−(n+ν)/2π(γ)(eq. 31)g(\gamma) = \left(\prod_i T^2_{ii}[(1-\gamma_i)v^*_0+\gamma_i v^*_1]\right)^{-1/2}(\nu\lambda+Y'Y-W'W)^{-(n+\nu)/2}\pi(\gamma) \tag{eq. 31}

Dongarra et al. (1979) condition (30): When D1γ∗R1γD1γ∗=c(Xγ′Xγ)−1D^*_{1\gamma}R_{1\gamma}D^*_{1\gamma}=c(X'_\gamma X_\gamma)^{-1} (g-prior structure), update is O(qγ2)O(q^2_\gamma):

g(γ)=(1+c)−qγ/2 ⁣(νλ+Y′Y−(1+1/c)−1W′W)−(n+ν)/2π(γ)(eq. 32)g(\gamma) = (1+c)^{-q_\gamma/2}\!\left(\nu\lambda+Y'Y-(1+1/c)^{-1}W'W\right)^{-(n+\nu)/2}\pi(\gamma) \tag{eq. 32}

Gray Code enumeration: Order all 2p2^p γ\gamma vectors so consecutive ones differ in exactly one bit (Reingold-Nievergelt-Deo 1977; Diaconis-Holmes 1994). Apply fast O(p2)O(p^2) updating at each step to enumerate g(γ)g(\gamma) for all models in O(2p⋅p2)O(2^p \cdot p^2) total operations (vs. brute force O(2p⋅p3)O(2^p \cdot p^3)). Feasible through p≤25p \leq 25 (p=15p=15: 7 sec; p=20p=20: 5 min on a 1996 SPARCstation 10).

Three MCMC Algorithms and Normalization Constant Estimation (George-McCulloch 1997)

NG — Nonconjugate Gibbs (= SSVS): Full three-block Gibbs over (β,σ2,γ)(\beta,\sigma^2,\gamma). Fastest per iteration at large pp (≈30\approx 30 sec/1000 iters at p=100p=100) but vulnerable to stuck-γ\gamma failure.

CG — Conjugate Gibbs: Samples only γ\gamma using the Bernoulli inclusion ratio:

π(γi=1,γ(i)∣Y)π(γi=0,γ(i)∣Y)=g(γi=1,γ(i))g(γi=0,γ(i))(eq. 40)\frac{\pi(\gamma_i=1,\gamma_{(i)}|Y)}{\pi(\gamma_i=0,\gamma_{(i)}|Y)} = \frac{g(\gamma_i=1,\gamma_{(i)})}{g(\gamma_i=0,\gamma_{(i)})} \tag{eq. 40}

Never samples β\beta or σ\sigma directly. Slower per iteration at large pp (≈5\approx 5 min/1000 iters at p=100p=100) but mixes correctly even under weak information.

CM — Conjugate Metropolis (= MC³ of Madigan-York 1995): Proposes flipping or swapping one γi\gamma_i; accepts via Metropolis ratio using g(γ)g(\gamma) (eqs. 43–44). Similar speed to CG; explores model space differently.

Normalization constant estimation: Since π(γ∣Y)=C⋅g(γ)\pi(\gamma|Y) = C \cdot g(\gamma) (eq. 34), estimate C^\hat C from MCMC output via indicator function on a reference set AA:

C^=1g(A)⋅K∑kIA(γ(k))(eq. 35)\hat C = \frac{1}{g(A) \cdot K}\sum_k I_A(\gamma^{(k)}) \tag{eq. 35}

Improved individual posterior estimates π^(γ∣Y)=C^⋅g(γ)\hat\pi(\gamma|Y) = \hat C \cdot g(\gamma) (eq. 36); total visited probability π^(B∣Y)=C^⋅g(B)\hat\pi(B|Y) = \hat C \cdot g(B) (eq. 37) characterizes model space coverage.

Stuck-γ\gamma Failure Mode of Nonconjugate Gibbs

Under weak information (e.g., σ=200\sigma=200, v1/v0=2500v_1/v_0=2500), NG malfunctions: β\beta is drawn from N(0,v0)\mathcal{N}(0,v_0) (the spike) and is unlikely to resemble a draw from N(0,v1)\mathcal{N}(0,v_1) (the slab). Consequently γi\gamma_i stays at 0 for long runs, occasionally jumps to 1 and stays there. The γ\gamma chain is nearly non-ergodic. Monte Carlo SE for marginal inclusion probabilities: NG ≈ 0.10 vs. CG/CM ≈ 0.02 in this setting. The conjugate methods, which never sample β\beta, are immune.

Financial Index Tracking Application (George-McCulloch 1997)

p=200p=200 S&P 500 constituent stocks, n=362n=362 weekly returns. Two-phase strategy:

Phase 1 (NG screening): 10,000 draws, wi=0.05w_i=0.05, δ=0.008\delta=0.008, v1/v0=625v_1/v_0=625. Identifies top 50 stocks by marginal inclusion frequency.

Phase 2 (CG estimation): 50 stocks, 450,000 draws, wi=0.01w_i=0.01. Identifies 789 high-probability models within e−5e^{-5} of the best model. Best model: 21 variables, R2=95.6%R^2=95.6\%, matches classical stepwise regression. The stepwise model's posterior probability is only 0.00176×0.00176\times the maximum-probability model — demonstrating that a single "best" model severely understates posterior uncertainty.

Why It Matters

Open Questions

Bayesian Stochastic Search for VAR Restrictions (George-Sun-Ni 2008)

George, Sun, and Ni extend SSVS to VAR models, simultaneously searching restrictions on the p×(h+Lp)p \times (h+Lp) coefficient matrix Φ\Phi and the off-diagonal elements of the upper-triangular factor Ψ\Psi in the precision decomposition Σ−1=ΨΨ′\Sigma^{-1} = \Psi\Psi' (eq. 9). Upper-triangular Ψ\Psi is required for global identification (unique Σ→Ψ\Sigma \to \Psi mapping); arbitrary Ψ\Psi satisfies only local rank conditions (Bekker-Pollock 1986; Amisano-Giannini 1997).

Prior structure: Five-component mixture prior.

Five-step Gibbs sampler (Appendix A.3): Every conditional is standard — Gamma for ψii2\psi_{ii}^2, Normal for ηj\eta_j, Bernoulli for ωij\omega_{ij} and γi\gamma_i, Normal for ϕ\phi — with no Metropolis-Hastings steps. Key property inherited from George-McCulloch (1993): γi\gamma_i does not depend on YY given ϕ\phi (eq. 37).

Key finding: Restricting Φ\Phi aids Ψ\Psi selection and vice versa — the two searches are interdependent. Rao-Blackwell model-averaged forecasts improve over maximum likelihood estimator (MLE) by 20–67% in simulation.

Poisson Log-Linear Model Selection (Albert 1996)

Albert (1996) extends the SSVS idea to contingency tables via a Poisson log-linear likelihood. The design matrix X0X_0 encodes which interaction terms are included in model MkM_k. The block-diagonal precision prior is:

Σ−1=diag(0Ip0, P1Ip1, …, PsIps)\Sigma^{-1} = \text{diag}(0I_{p_0},\, P_1I_{p_1},\,\ldots,\, P_sI_{p_s})

where β0\beta_0 (always-included terms) receives an improper flat prior (00 precision) and each group jj of testable parameters receives precision PjP_j. Rather than a fixed spike-and-slab, a Gamma hyperprior Pj∼Gamma(νj/2,bj2νj/2)P_j \sim \text{Gamma}(\nu_j/2, b_j^2\nu_j/2) integrates out to a tνjt_{\nu_j} marginal for βj\beta_j. Setting νj=1\nu_j=1 gives Cauchy marginals — heavier-tailed and more robust to extreme cell counts than the Normal (νj→∞\nu_j\to\infty).

Posterior model probabilities are approximated by a Laplace expansion around the posterior mode found by IWLS. The Gibbs sampler cycles over:

  1. βj∣rest\beta_j|\text{rest}: conjugate Normal given current PjP_j
  2. Z∣restZ|\text{rest}: auxiliary IWLS working response
  3. Pj∗∣restP_j^*|\text{rest}: Gamma(νj/2+pj/2\nu_j/2+p_j/2,; bj2νj/2+∑tβjt2/2b_j^2\nu_j/2+\sum_t\beta_{jt}^2/2)

Bayesian model averaging (BMA) with this sampler inflates posterior standard errors nearly 2× relative to the maximum-probability single model, illustrating the cost of ignoring model uncertainty.

Related