6.4.2 Approximate Inference Through Stochastic Simulation

Many problems are too big for exact inference, and one must resort to approximate inference. One of the most effective methods is based on generating random samples from the (posterior) distribution that the network specifies.

Stochastic simulation is based on the idea that a set of samples can be used to compute probabilities. For example, you could interpret the probability P(a)=0.14 as meaning that, out of 1,000 samples, about 140 will have a true. You can go from (enough) samples into probabilities and from probabilities into samples.

We consider three problems:

  • how to generate samples,
  • how to incorporate observations, and
  • how to infer probabilities from samples.

We examine three methods that use sampling to compute the posterior distribution of a variable: (1) rejection sampling, (2) importance sampling, and (3) particle filtering.