(Sorry to those of you who receive this twice. There was a small typo in the
previous version.)
Readers of this mailing list may be interested in the following article
recently published by JAIR.
Cheng, J. and Druzdzel, M.J. (2000)
"AIS-BN: An Adaptive Importance Sampling Algorithm for Evidential
Reasoning in Large Bayesian Networks", Volume 13, pages 155-188.
Available in HTML, PDF, PostScript and compressed PostScript.
For quick access via your WWW browser, use this URL:
http://www.jair.org/abstracts/cheng00a.html
More detailed instructions are below.
Abstract: 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 & Chang, 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., 1994), 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 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.
The article is available via:
-- comp.ai.jair.papers (also see comp.ai.jair.announce)
-- World Wide Web: The URL for our World Wide Web server is
http://www.jair.org/
For direct access to this article and related files try:
http://www.jair.org/abstracts/cheng00a.html
-- Anonymous FTP from either of the two sites below.
Carnegie-Mellon University (USA):
ftp://ftp.cs.cmu.edu/project/jair/volume13/cheng00a.ps
The University of Genoa (Italy):
ftp://ftp.mrg.dist.unige.it/pub/jair/pub/volume13/cheng00a.ps
The compressed PostScript file is named cheng00a.ps.Z (260K)
For more information about JAIR, visit our WWW or FTP sites, or
contact jair-ed@isi.edu
This archive was generated by hypermail 2b29 : Fri Oct 13 2000 - 10:36:39 PDT