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

6.4.2.2 Forward Sampling in Belief Networks

Forward sampling is a way to generate a sample of every variable of a belief network so that each sample is generated in proportion to it probability. Suppose X1,...,Xn is a total ordering of the variables so that the parents of a 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 aforementioned method. 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 of selecting a particular assignment to all of the variables will be the probability of the assignment.

Example 6.23: Let us create a set of samples for the belief network of Figure 6.1. Suppose the variables are ordered as follows: 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 6.10: Sampling for a belief network

First the algorithm samples Tampering, using the inverse of the cumulative distribution. Suppose it selects Tampering=false. Then it samples Fire using the same method. Suppose it selects Fire=true. Then it must select a value for Alarm, using the distribution P(Alarm|Tampering=false,Fire=true). Suppose it selects Alarm=true. Next, it selects a value for Smoke using P(Smoke|Fire=true). Then it selects a value for Leaving using the distribution for P(Leaving|Alarm=true). Suppose it selects Leaving=false. Then it selects a value for Report, using the distribution P(Report|Leaving=false). It has thus selected a value for each variable and created the first sample of Figure 6.10. 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 can then repeat this until it has enough samples. In Figure 6.10, it generated 1,000 samples.