J. Cheng et Mj. Druzdzel, AIS-BN: An adaptive importance sampling algorithm for evidential reasoningin large Bayesian networks, J ARTIF I R, 13, 2000, pp. 155-188
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.