Bayesian Networks: Rejection Sampling

Study Notes

The estimated probability of rain, ˆP(Rain = true), is 0.511 when 511 out of 1000 samples from the sprinkler network have Rain = true.

Rejection sampling is a general method for producing samples from a hard-to-sample distribution given an easy-to-sample distribution.
It can be used to compute conditional probabilities, P(X | e), by generating samples from the prior distribution and rejecting those that do not match the evidence.
The algorithm returns an estimated distribution, ˆP(X | e), which is obtained by counting how often X = x occurs in the remaining samples.
ˆP(X | e) is a consistent estimate of the true probability, P(X | e).

To estimate P(Rain | Sprinkler = true) using 100 samples, 27 samples with Sprinkler = true are generated, and 8 of those have Rain = true.
P(Rain | Sprinkler = true) ≈ NORMALIZE(8, 19) = (0.296, 0.704), which is an estimate of the true answer (0.3, 0.7).

The biggest problem with rejection sampling is that it rejects many samples, making it inefficient for complex problems.
The fraction of samples consistent with the evidence e drops exponentially as the number of evidence variables grows.

Likelihood weighting avoids the inefficiency of rejection sampling by generating only events that are consistent with the evidence e.
It is a particular instance of the general statistical technique of importance sampling, tailored for inference in Bayesian networks.
Likelihood weighting is more efficient than rejection sampling, as it only generates relevant samples.