plex networks the only alternative that will produce any result at all. Furthermore, while obtaining the result is crucial in all applications, precision guarantees may not be critical for some types of problems and can be traded off against the speed of computation.

A prominent subclass of approximate algorithms is the family of stochastic sampling algorithms (also called stochastic simulation or Monte Carlo algorithms). The precision obtained by stochastic sampling generally increases with the number of samples generated and is fairly unaffected by the network size. Execution time is fairly independent of the topology of the network and is linear in the number of samples.  Computation can be interrupted at any time, yielding an anytime property of the algorithms, important in timecritical applications.

While stochastic sampling performs very well in predictive inference, diagnostic reasoning, i.e., reasoning from observed evidence nodes to their ancestors in the network often exhibits poor convergence. When the number of observations increases, especially if these observations are unlikely a-priori, stochastic sampling often fails to converge to reasonable estimates of the posterior probabilities. Although this problem has been known since the very first sampling algorithm was proposed by Henrion (1988), little has been done to address it effectively. Furthermore, various sampling algorithms proposed were tested on simple and small networks, or networks with special topology, without the presence of extremely unlikely evidence and the practical significance of this problem has been underestimated. Given a typical number of samples used in real-time that are feasible on today's hardware, say 10 6 samples, the behavior of a stochastic sampling algorithm will be drastically different for different size networks. While in a network consisting of 10 nodes and a few observations, it may be possible to converge to exact probabilities, in very large nnetworks only a negligibly small fraction of the total sample space will be probed. One of the practical Bayesian network models that we used in our tests, a subset of the CPCS
nnetwork (Pradhan et al., 1994), consists of 179 nodes. Its total sample space is larger than 10 61 . With 10 6 samples, we can sample only 10 -55 fraction of the sample space.

We believe that it is crucial (1) to study the feasibility and convergence properties of sampling algorithms on very large practical networks, and (2) to develop sampling algorithms that will show good convergence under extreme, yet practical conditions, such as evidential reasoning given extremely unlikely evidence.  After all, small networks can be updated using any of the existing exact algorithms - it is precisely the very large networks where stochastic sampling can be most useful. As to the likelihood of evidence, we know that stochastic sampling will generally perform well when it is high (Henrion, 1988). So, it is important to look at those cases in which evidence is very unlikely. In this paper, we test two existing state of the art stochastic sampling algorithms for Bayesian networks, likelihood weighting (Fung & Chang, 1989; Shachter & Peot, 1989) and self-importance sampling
(Shachter & Peot, 1989), on a subset of the CPCS network with extremely unlikely evidence. We show that they both exhibit similarly poor convergence rates. We propose a new sampling algorithm, that we call the adaptive importance sampling for Bayesian networks
( AIS- BN ), which is suitable for evidential reasoning in large multiply-connected Bayesian nnneeeer applied method for variance reduction in simulation that has also been applied in Bayesian networks (e.g., Shachter & Peot, 1989). We demonstrate empirically on three large practical Bayesian network models that the AIS-BN algorithm consistently outperforms