8.6 Stochastic Simulation

8.6.2 Forward Sampling in Belief Networks

Forward sampling is a way to generate a sample of every variable in a belief network so that each sample is generated in proportion to its probability. This enables us to estimate the prior probability of any variable.

Suppose X1,,Xn is a total ordering of the variables so that the parents of each variable come before the variable in the total order. Forward sampling draws a sample of all of the variables by drawing a sample of each variable X1,,Xn in order. First, it samples X1 using the cumulative distribution, as described above. For each of the other variables, due to the total ordering of variables, when it comes time to sample Xi, it already has values for all of Xi’s parents. It now samples a value for Xi from the distribution of Xi given the values already assigned to the parents of Xi. Repeating this for every variable generates a sample containing values for all of the variables. The probability distribution of a query variable is estimated by considering the proportion of the samples that have assigned each value of the variable.

Example 8.40.

To create a set of samples for the belief network of Figure 8.3, suppose the variables are ordered: Tampering, Fire, Alarm, Smoke, Leaving, Report.

Sample Tampering Fire Alarm Smoke Leaving Report
s1 false true true true false false
s2 false false false false false false
s3 false true true 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 true true
s8 true false false false false true
s1000 true false true true false false
Figure 8.28: Sampling for a belief network

First the algorithm samples Tampering, using the cumulative distribution. Suppose it selects Tampering=false. Then it samples Fire using the same method. Suppose it selects Fire=true. Then it samples a value for Alarm, using the distribution P(AlarmTampering=false,Fire=true). Suppose it selects Alarm=true. Next, it samples a value for Smoke using P(SmokeFire=true). And so on for the other variables. It has thus selected a value for each variable and created the first sample of Figure 8.28. Notice that it has selected a very unlikely combination of values. This does not happen very often; it happens in proportion to how likely the sample is. It repeats this until it has enough samples. In Figure 8.28, it generated 1000 samples.

The probability that Report=true is estimated from the proportion of the samples where the variable Report has value true.