AIS-BN: An Adaptive Importance Sampling Algorithm for Evidential
  Reasoning in Large Bayesian Networks
  Stochastic sampling algorithms, while an attractive alternative to exact
algorithms in very large Bayesian network models, have been observed to perform
poorly in evidential reasoning with extremely unlikely evidence. To address
this problem, we propose an adaptive importance sampling algorithm, AIS-BN,
that shows promising convergence rates even under extreme conditions and seems
to outperform the existing sampling algorithms consistently. Three sources of
this performance improvement are (1) two heuristics for initialization of the
importance function that are based on the theoretical properties of importance
sampling in finite-dimensional integrals and the structural advantages of
Bayesian networks, (2) a smooth learning method for the importance function,
and (3) a dynamic weighting function for combining samples from different
stages of the algorithm. We tested the performance of the AIS-BN algorithm
along with two state of the art general purpose sampling algorithms, likelihood
weighting (Fung and Chang, 1989; Shachter and Peot, 1989) and self-importance
sampling (Shachter and Peot, 1989). We used in our tests three large real
Bayesian network models available to the scientific community: the CPCS network
(Pradhan et al., 1994), the PathFinder network (Heckerman, Horvitz, and
Nathwani, 1990), and the ANDES network (Conati, Gertner, VanLehn, and Druzdzel,
1997), with evidence as unlikely as 10^-41. While the AIS-BN algorithm always
performed better than the other two algorithms, in the majority of the test
cases it achieved orders of magnitude improvement in precision of the results.
Improvement in speed given a desired precision is even more dramatic, although
we are unable to report numerical results here, as the other algorithms almost
never achieved the precision reached even by the first few iterations of the
AIS-BN algorithm.
