Journal of Artificial Intelligence Research
pp. 155-188. Submitted 6/00; published 10/00.
© 2000 AI Access Foundation
and Morgan Kaufmann Publishers.
All rights reserved.
Postscript and PDF versions of this document are
available from here.
AIS-BN: An Adaptive Importance Sampling Algorithm for Evidential
Reasoning in Large Bayesian Networks
Jian Cheng (firstname.lastname@example.org)
Marek J. Druzdzel (email@example.com)
Decision Systems Laboratory
School of Information Sciences and Intelligent Systems Program
University of Pittsburgh, Pittsburgh, PA 15260 USA
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 Chang1989,Shachter and Peot1989] and self-importance
sampling [Shachter and Peot1989]. 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 et al.1990], and the ANDES
network [Conati et al.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.