AIS-BN: Adaptive Importance Sampling for Bayesian Networks

The main reason why the existing stochastic sampling algorithms converge so slowly is that they fail to learn a good importance function during the sampling process and, effectively, fail to reduce the sampling variance. When the importance function is optimal, such as in probabilistic logic sampling without any evidence, each of the algorithms is capable of converging to fairly good estimates of the posterior probabilities within relatively few samples. For example, assuming that the posterior probabilities are not extreme (i.e., larger than say 0.01), as few as 1,000 samples may be sufficient to obtain good estimates. In this section, we present the adaptive importance sampling algorithm for Bayesian networks (AIS-BN) that, as we will demonstrate in the next section, performs very well on most tests. We will first describe the details of the algorithm and prove two theorems that are useful in learning the optimal importance sampling function.

Figure 2: The adaptive importance sampling for Bayesian Networks (AIS-BN) algorithm.