Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

#### 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 *X _{1},...,X_{n}* 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

*X*in order. First, it samples

_{1},...,X_{n}*X*using the aforementioned method. For each of the other variables, due to the total ordering of variables, when it comes time to sample

_{1}*X*, it already has values for all of

_{i}*X*'s parents. It now samples a value for

_{i}*X*from the distribution of

_{i}*X*given the values already assigned to the parents of

_{i}*X*. 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.

_{i}**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 |

s _{1} | false | true | true | true | false | false |

s _{2} | false | false | false | false | false | false |

s _{3} | false | true | true | true | true | true |

s _{4} | false | false | false | false | false | true |

s _{5} | false | false | false | false | false | false |

s _{6} | false | false | false | false | false | false |

s _{7} | true | false | false | true | true | true |

s _{8} | true | false | false | false | false | true |

... | ||||||

s _{1000} | true | false | true | true | false | false |

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.