Approximate Inference: Sampling Methods

Direct sampling from a Bayesian network

import random

def direct_sample(bn, topological_order):
    """Generate one complete sample from the prior distribution P(X)."""
    sample = {}
    for var in topological_order:
        parents = bn.parents[var]
        parent_vals = tuple(sample[p] for p in parents)
        # Sample from P(var | parent_vals)
        prob_true = bn.cpt[var][parent_vals][True]
        sample[var] = (random.random() < prob_true)
    return sample

def estimate_prior_probability(bn, query_var, query_val, N=10000):
    """Estimate P(query_var=query_val) from N direct samples."""
    count = sum(
        1 for _ in range(N)
        if direct_sample(bn, bn.topological_order)[query_var] == query_val
    )
    return count / N

Likelihood weight: product of CPT probabilities for each evidence variable given its sampled parent values. High-weight samples are more consistent with the observed evidence.

Likelihood Weighting — the key GATE DA algorithm to know

def lw_sample(bn, evidence, topological_order):
    """One likelihood-weighted sample.
    Evidence variables are FIXED to observed values; weight accumulates."""
    sample = {}
    weight = 1.0

    for var in topological_order:
        parent_vals = tuple(sample[p] for p in bn.parents[var])

        if var in evidence:
            # Fix to observed value; multiply weight by P(E_i=e_i | parents)
            e_val = evidence[var]
            sample[var] = e_val
            weight *= bn.cpt[var][parent_vals][e_val]
        else:
            # Sample non-evidence variable normally from its CPT
            prob_true = bn.cpt[var][parent_vals][True]
            sample[var] = (random.random() < prob_true)

    return sample, weight

def lw_estimate(bn, query_var, query_val, evidence, N=10000):
    """P(query_var=query_val | evidence) via likelihood weighting."""
    weighted_count = total_weight = 0.0
    for _ in range(N):
        s, w = lw_sample(bn, evidence, bn.topological_order)
        total_weight += w
        if s[query_var] == query_val:
            weighted_count += w
    return weighted_count / total_weight   # normalized weighted estimate

Gibbs full conditional: the probability of Xᵢ given its Markov blanket. mb(Xᵢ) = parents, children, and children's other parents. Only local CPTs are needed — the rest of the network is irrelevant given the blanket.

1. What is the core idea of MCMC (Markov Chain Monte Carlo) sampling? (Answer: MCMC: construct a Markov chain whose stationary distribution equals the target distribution P(x). Sample from the chain by running it long enough to 'mix' (reach stationarity). Then use samples to estimate expectations: E[f(X)] ≈ (1/N)Σf(xᵢ). The key: we don't need to compute P(x) normalised — only need to evaluate P(x) up to a constant (the Metropolis acceptance criterion uses ratios P(x')/P(x) where the constant cancels).)
2. What is the difference between the Metropolis-Hastings algorithm and Gibbs sampling? (Answer: Metropolis-Hastings: propose x' from any proposal distribution Q(x'|x); accept with probability min(1, P(x')Q(x|x') / P(x)Q(x'|x)). General — works for any distribution. Gibbs sampling: a special case of MH where each variable is sampled from its full conditional P(xᵢ|x_{-i}). Acceptance rate = 1 always (no rejection). Efficient when full conditionals are easy to sample (conjugate priors in Bayesian models). Requires knowing all full conditionals.)
3. What is the 'burn-in' period in MCMC and how do you determine its length? (Answer: Burn-in: the initial samples before the chain reaches stationarity — discarded because they depend on the initialisation rather than the target distribution. How long: run multiple chains from different starting points; burn-in ends when chains converge to the same distribution (Gelman-Rubin diagnostic R̂ < 1.1). Alternatively: monitor trace plots for when autocorrelation drops and the chain mixes. Typical burn-in: 10–50% of total samples for well-mixed chains.)
4. What is variational inference and how does it differ from MCMC? (Answer: Variational inference (VI): approximate P(z|x) with a simpler distribution Q(z; λ) from a tractable family (e.g., mean-field Gaussian). Optimise λ to minimise KL(Q||P) — turns inference into an optimisation problem. MCMC: generates exact (asymptotically) samples from P(z|x) but can be slow to converge. VI: faster (gradient-based optimisation), scalable to large datasets, gives a closed-form approximation. MCMC: exact in the limit but slow. Modern deep learning (VAEs, normalising flows) uses VI for scalable approximate inference.)
5. What is the effective sample size (ESS) in MCMC and why is it important? (Answer: MCMC samples are autocorrelated — consecutive samples are not independent. ESS = N / (1 + 2Σ ρ_k) where ρ_k is autocorrelation at lag k. ESS << N means you have fewer independent samples than actual samples. Example: 10,000 MCMC samples with ESS=500 provides the same statistical power as 500 independent samples. Report ESS, not raw N. Improve ESS: better proposal distributions, HMC (Hamiltonian Monte Carlo) uses gradient information to take large steps and reduces autocorrelation dramatically.)