8.6.3 Rejection Sampling

Given some evidence $e$ , rejection sampling estimates $P(h\mid e)$ using the formula

P(h\mid e)=\frac{P(h\wedge e)}{P(e)}.

This is 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\mid e)$ . If the evidence is a conjunction of assignments of values to variables, a sample is rejected when any variable is assigned a value different from its observed value.

Sample	Tampering	Fire	Alarm	Smoke	Leaving	Report
$s_{1}$	$f a l s e$	$f a l s e$	$t r u e$	$f a l s e$	✘
$s_{2}$	$f a l s e$	$t r u e$	$f a l s e$	$t r u e$	$f a l s e$	$f a l s e$	✔
$s_{3}$	$f a l s e$	$t r u e$	$t r u e$	$f a l s e$	✘
$s_{4}$	$f a l s e$	$t r u e$	$f a l s e$	$t r u e$	$f a l s e$	$f a l s e$	✔
$s_{5}$	$f a l s e$	$t r u e$	$t r u e$	$t r u e$	$t r u e$	$t r u e$	✘
$s_{6}$	$f a l s e$	$f a l s e$	$f a l s e$	$t r u e$	$f a l s e$	$f a l s e$	✔
$s_{7}$	$t r u e$	$f a l s e$	$f a l s e$	$f a l s e$	✘
$s_{8}$	$t r u e$	$t r u e$	$t r u e$	$t r u e$	$t r u e$	$t r u e$	✘
…
$s_{1000}$	$t r u e$	$f a l s e$	$t r u e$	$f a l s e$	✘

Figure 8.29: Rejection sampling for

P(tampering\mid smoke\wedge\mbox{}\neg report)

Example 8.41.

Figure 8.29 shows how rejection sampling is used to estimate $P(tampering\mid smoke\wedge\mbox{}\neg report)$ . Any sample with $Smoke{=}false$ is rejected. The sample is rejected without considering any more variables. Any sample with $Report{=}true$ is rejected. The sample average from the remaining samples (those marked with ✔) is used to estimate the posterior probability of $t a m p e r i n g$ .

Because $P(smoke\wedge\mbox{}\neg report)=0.0128$ , we would expect about 13 samples out of the 1000 to have $smoke\wedge\mbox{}\neg report$ true; the other 987 samples would have $smoke\wedge\mbox{}\neg report$ false, and so would be rejected. Thus, 13 is used as $n$ in Hoeffding’s inequality, which, for example, guarantees an error for any probability computed from these samples of less than $0.25$ in about 86% of the cases, which is not very accurate.

The error in the probability of $h$ depends on the number of samples that are not rejected, which proportional to $P(e)$ . Hoeffding’s inequality can be used to estimate the error of rejection sampling, where $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.

Artificial Intelligence 2E

8.6.3 Rejection Sampling

Example 8.41.

Artificial
Intelligence 2E