foundations of computational agents
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 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 in order. First, it samples 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 , it already has values for all of ’s parents. It now samples a value for from the distribution of given the values already assigned to the parents of . 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.
To create a set of samples for the belief network of Figure 8.3, suppose the variables are ordered: , , , , , .
First the algorithm samples , using the cumulative distribution. Suppose it selects . Then it samples using the same method. Suppose it selects . Then it samples a value for , using the distribution . Suppose it selects . Next, it samples a value for using . 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 is estimated from the proportion of the samples where the variable has value .