Approximate Inference — Sampling

Monte Carlo estimation of posteriors in Bayesian networks — prior (direct) sampling, rejection sampling and its waste when evidence is unlikely, likelihood weighting with sample weights, and Markov chain Monte Carlo with Gibbs sampling over Markov blankets — plus consistency, error rates and when to use which method.

Section 710 practice questions

Why sample?

Exact inference is NP-hard in general. Monte Carlo methods instead generate random samples and estimate probabilities as frequencies. They are consistent — estimates converge to the right answer as the number of samples $N \to \infty$ — and the error shrinks like $1/\sqrt N$ , independent of the network size.

Prior (direct) sampling

Sample each variable in topological order from $P(X_i\mid\text{parents}(X_i))$ , using the values already chosen for the parents. A complete event $(x_1, \dots, x_n)$ is generated with probability

S_{PS}(x_1, \dots, x_n) = \prod_i P(x_i\mid\text{parents}(X_i)) = P(x_1, \dots, x_n),

so the fraction of samples matching an event estimates its probability: $\hat P(\mathbf x) = N(\mathbf x)/N$ . Prior sampling answers queries with no evidence.

The sprinkler network: sample in topological order.

Rejection sampling

To estimate $P(X\mid\mathbf e)$ : generate prior samples, discard every sample inconsistent with $\mathbf e$ , and count $X$ among the rest:

\hat P(X = x\mid\mathbf e) = \frac{N(x, \mathbf e)}{N(\mathbf e)}.

It is consistent, but wasteful: only a fraction $P(\mathbf e)$ of samples survive, and $P(\mathbf e)$ drops exponentially with the number of evidence variables.

Likelihood weighting

Avoid rejection by fixing the evidence variables and sampling only the others (in topological order). Each sample carries a weight — the likelihood of the evidence given its sampled parents:

w = \prod_{E_j\in\mathbf E}P(e_j\mid\text{parents}(E_j)).

The estimate is the normalised total weight: $\hat P(x\mid\mathbf e) = \alpha\sum_{\text{samples with } X = x}w$ .

Likelihood weighting is consistent and uses every sample, but non-evidence variables are sampled ignoring downstream evidence. With evidence near the leaves, most samples are implausible and get tiny weights, so a few samples dominate and accuracy suffers as evidence grows.

Gibbs sampling (MCMC)

Markov chain Monte Carlo makes a random walk through complete states instead of generating each sample from scratch.

Fix the evidence; initialise the other variables arbitrarily.
Repeatedly pick a non-evidence variable $X_i$ and resample it from $P(X_i\mid\text{mb}(X_i))$ given the current values of its Markov blanket:

P(x_i\mid\text{mb}(X_i)) \propto P(x_i\mid\text{parents}(X_i))\prod_{Y_j\in\text{children}(X_i)}P(y_j\mid\text{parents}(Y_j)).

Count how often each value of the query variable occurs (after discarding an initial burn-in).

The states form a Markov chain whose stationary distribution is the posterior $P(\mathbf X\mid\mathbf e)$ , so the long-run fraction of time spent in each state converges to its posterior probability. Successive samples are correlated, and mixing can be slow with near-deterministic CPTs.

Comparison

Method	Handles evidence by	Weakness
Prior sampling	— (no evidence)	cannot condition
Rejection sampling	discarding inconsistent samples	wastes $1 - P(\mathbf e)$ of samples
Likelihood weighting	fixing evidence, weighting samples	weights degenerate when evidence is downstream
Gibbs sampling	fixing evidence, resampling from Markov blankets	correlated samples, burn-in, slow mixing

Quick revision

Practice questions

GATE-style questions: 5 one-mark and 5 two-mark. Wrong MCQs cost ⅓ of their marks in the real exam; MSQ and NAT have no negative marking. Attempt each before opening the solution.

Q1NAT2 marks

Sprinkler network. Cloudy $C$ is a parent of Sprinkler $S$ and Rain $R$ ; $S$ and $R$ are the parents of WetGrass $W$ . $P(C) = 0.5$ ; $P(S\mid C) = 0.1$ , $P(S\mid\neg C) = 0.5$ ; $P(R\mid C) = 0.8$ , $P(R\mid\neg C) = 0.2$ ; $P(W\mid S,R) = 0.99$ , $P(W\mid S,\neg R) = 0.90$ , $P(W\mid\neg S,R) = 0.90$ , $P(W\mid\neg S,\neg R) = 0$ .

Prior sampling in topological order generates one complete sample. The probability that it is $(C, \neg S, R, W)$ — i.e. $C$ true, $S$ false, $R$ true, $W$ true — is ______ (round to three decimals).

Q2NAT2 marks

Likelihood weighting is used with evidence $S = \text{true}$ , $W = \text{true}$ . In one run the sampled non-evidence values are $C = \text{true}$ and $R = \text{true}$ . The weight of this sample is ______ (round to three decimals).

Q3NAT1 mark

Rejection sampling generates 1000 samples from the prior. 250 of them agree with the evidence $\mathbf e$ , and 100 of those 250 have $X = \text{true}$ . The estimate of $P(X = \text{true}\mid\mathbf e)$ is ______.

Q4NAT1 mark

The evidence has probability $P(\mathbf e) = 0.002$ . Out of $N = 50\,000$ prior samples, the expected number that rejection sampling keeps is ______.

Q5NAT2 marks

Likelihood weighting produces five samples. The three with $X = \text{true}$ have weights 0.3, 0.2 and 0.1; the two with $X = \text{false}$ have weights 0.2 and 0.2. The estimate of $P(X = \text{true}\mid\mathbf e)$ is ______ (round to two decimals).

Q6MCQ1 mark

In Gibbs sampling for a Bayesian network, each non-evidence variable $X_i$ is resampled from

Q7NAT2 marks

Chain $A \to B \to C$ with $P(B\mid A) = 0.8$ , $P(B\mid\neg A) = 0.1$ , $P(C\mid B) = 0.6$ , $P(C\mid\neg B) = 0.2$ . During Gibbs sampling the current state has $A = \text{true}$ and $C = \text{true}$ . The probability that $B$ is resampled as true is ______ (round to two decimals).

Q8MSQ2 marks

Which statements about sampling methods are correct?

One or more options are correct.

Q9NAT1 mark

The standard error of a Monte Carlo estimate falls as $1/\sqrt N$ . To halve the error, the number of samples must be multiplied by ______.

Q10MCQ1 mark

Prior (direct) sampling of a Bayesian network samples the variables