# Ais-Bn: An Adaptive Importance Sampling Algorithm For Evidential Reasoning In Large Bayesian Networks

## Jian Cheng Marek J. Druzdzel

JCHENG@SIS. PITT. ED U
MAREK@SIS. PITT. EDU
Decision Systems Laboratory School of Information Sciences and Intelligent Systems Program University of Pittsburgh, Pittsburgh, PA 15260 USA

## 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 en 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 nnetworks, (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 CP CS network (Pradhan et al., 1994), the P ATH F INDER 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.

## 1. Introduction

Bayesian networks (Pearl, 1988) are increasingly popular tools for modeling uncertainty in intelligent systems. With practical models reaching the size of several hundreds of variables
(e.g., Pradhan et al., 1994; Conati et al., 1997), it becomes increasingly important to address the problem of feasibility of probabilistic inference. Even though several ingenious exact algorithms have been proposed, in very large models they all stumble on the theoretically demonstrated NP-hardness of inference (Cooper, 1990). The significance of this result can be observed in practice - exact algorithms applied to large, densely connected practical networks require either a prohibitive amount of memory or a prohibitive amount of computation and are unable to complete. While approximating inference to any desired precision has been shown to be NP-hard as well (Dagum & Luby, 1993), it is for very com¬