(8th-September-2020)
Rejection function
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.
• For example, 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.
Comments