Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text). Rejection Sampling

Given some evidence e, rejection sampling estimates P(h|e) using the formula

P(h|e) = (P(h ∧e))/(P(e)).

This can be computed by considering only the samples where e is true and by determining the proportion of these in which h is true. The idea of rejection sampling is that samples are generated as before, but any sample where e is false is rejected. The proportion of the remaining, non-rejected, samples where h is true is an estimate of P(h|e). If the evidence is a conjunction of assignments of values to variables, a sample can be rejected when any of the variables assigned in the sample are different from the observed value.

The error in the probability of h depends on the number of samples that are not rejected. The number of samples that are not rejected is proportional to P(e). Thus, in Hoeffding's inequality, n is the number of non-rejected samples. Therefore, the error depends on P(e).

Rejection sampling does not work well when the evidence is unlikely. This may not seem like that much of a problem because, by definition, unlikely evidence is unlikely to occur. But, although this may be true for simple models, for complicated models with complex observations, every possible observation may be unlikely. Also, for many applications, such as in diagnosis, the user is interested in determining the probabilities because unusual observations are involved.

Sample Tampering Fire Alarm Smoke Leaving Report
s1 false true true true
s2 false false false false false false
s3 false true true true
s4 false false false false false true
s5 false false false false false false
s6 false false false false false false
s7 true false false true
s8 true false false false false true
s1000 true false true true
Figure 6.11: Rejection sampling for P(tampering | ¬smoke ∧report)

Example 6.24: Figure 6.11 shows how rejection sampling can be used to estimate P(tampering | ¬smoke ∧report). Any sample with Smoke=true is rejected. The sample can be rejected without considering any more variables. Any sample with Report=false is rejected. The sample average from the remaining samples (those marked with ✔) is used to estimate the posterior probability of tampering.

Because P(¬smoke ∧report)=0.0213, we would expect about 21 samples out of the 1,000 to not be rejected. Thus, 21 can be used as n in Hoeffding's inequality, which, for example, guarantees an error for any probability computed from these samples of less than 0.2 in about 63% of the cases.