[UAI] JAIR article - resend

From: Steve Minton (Steve.Minton@fetch.com)
Date: Fri Oct 13 2000 - 10:35:42 PDT

  • Next message: owner-uai@cs.orst.edu: "(no subject)"

    (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