Rejection Sampling
Rejection Sampling is an approximate inference method for Bayes Nets that improves upon prior sampling by discarding samples inconsistent with the evidence as early as possible, reducing wasted computation while preserving correctness. For a sample to be valid, parents must be sampled before their children.
Sampling follows the same procedure as prior sampling, but with an added rule:
- If at any point a sampled variable contradicts the evidence, the sample is rejected immediately.
The posterior is estimated as:
This works because every accepted sample still occurs with probability proportional to the true joint distribution.
Limitation: when the evidence has very low probability, nearly all samples are rejected. Although rejection sampling is more efficient than prior sampling, it still performs poorly under unlikely evidence.