AIS-BN: An adaptive importance sampling algorithm for evidential reasoningin large Bayesian networks

Stochastic sampling algorithms, while an attractive alternative to exact al gorithms in very large Bayesian network models, have been observed to perfo rm poorly in evidential reasoning with extremely unlikely evidence. To addr ess this problem, we propose an adaptive importance sampling algorithm, AIS -BN, that shows promising convergence rates even under extreme conditions a nd seems to outperform the existing sampling algorithms consistently. Three sources of this performance improvement are (1) two heuristics for initial ization of the importance function that are based on the theoretical proper ties of importance sampling in finite-dimensional integrals and the structu ral advantages of Bayesian networks, (2) a smooth learning method for the i mportance function, and (3) a dynamic weighting function for combining samp les from different stages of the algorithm. We tested the performance of the AIS-BN algorithm along with two state of t he art general purpose sampling algorithms, likelihood weighting (Fung & Ch ang, 1989; Shachter & Peot, 1989) and self-importance sampling (Shachter & Peot, 1989). We used in our tests three large real Bayesian network models available to the scientific community: the CPCS network (Pradhan et al., 19 94), the PathFinder network (Heckerman, Horvitz, & Nathwani, 1990), and the ANDES network (Conati, Gertner, VanLehn, & 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 achieve d orders of magnitude improvement in precision of the results. Improvement in speed given a desired precision is even more dramatic, although we are u nable to report numerical results here, as the other algorithms almost neve r achieved the precision reached even by the first few iterations of the AI S-BN algorithm.