weighting and self-importance sampling on a large practical model, the CPCS network, with evidence as unlikely as 5.54 × 10- 42 and typically 7 × 1.0- 24 . In our experiments, we observed that the AIS-BN algorithm was always better than likelihood weighting and selfimportance sampling and in over 60% of the cases it reached over two orders of magnitude improvement in accuracy. Tests performed on the other two networks, PATHFINDER and ANDES, yielded similar results.

Although there may exist other approximate algorithms that will prove superior to AIS-
BN in networks with special structure or distribution, the AIS-BN algorithm is simple and robust for general evidential reasoning problems in large multiply-connected Bayesian ntworks.

## Acknowledgments

We thank anonymous referees for several insightful comments that led to a substantial improvement of the paper. This research was supported by the National Science Foundation under Faculty Early Career Development (CAREER) Program, grant IRI–9624629, and by the Air Force Office of Scientific Research grants F49620–97–1–0225 and F49620–00–1–
0112. An earlier version of this paper has received the 2000 School of Information Sciences Robert R. Korfhage Award, University of Pittsburgh. Malcolm Pradhan and Max Henrion of the Institute for Decision Systems Research shared with us the CPCS network with a kind permission from the developers of the INTERNIST system at the University of Pittsburgh.  We thank David Heckerman for the PATHFINDER network and Abigail Gerner for the ANDES
nnetwork used in our tests. All experimental data have been obtained using SMILE, a Bayesian inference engine developed at the Decision Systems Laboratory and available at http://www2.sis.pitt.edu/~genie.

## References

Cano, J. E., Hernandez, L. D., & Moral, S. (1996). Importance sampling algorithms for the propagation of probabilities in belief networks. International Journal of Approximate Reasoning, 15, 77-92.

Chavez, M. R., & Cooper, G. F. (1990). A randomized approximation algorithm for probabilistic inference on Bayesian belief networks. Networks, 20 (5), 661–685.

Cheng, J., & Druzdzel, M. J. (2000a).  Computational investigations of low-discrepancy sequences in simulation algorithms for Bayesian networks. In Proceedings of the Sixteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI–2000), pp. 72–81 San Francisco, CA. Morgan Kaufmann Publishers.

Cheng, J., & Druzdzel, M. J. (2000b). Latin hypercube sampling in Bayesian networks. In Proceedings of the 13th International Florida Artificial Intelligence Research Symposium Conference (FLAIRS-2000), pp. 287–292 Orlando, Florida.

Conati, C., Gertner, A. S., VanLehn, K., & Druzdzel, M. J. (1997). On-line student modeling for coached problem solving using Bayesian networks. In Proceedings of the Sixth