Artificial
Intelligence

6.4.2.4 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.