Subscribe to RSS
Please copy the URL and add it into your RSS Feed Reader.
https://www.thieme-connect.de/rss/thieme/en/10.1055-s-00035037.xml
Download PDF
Methods Inf Med 1991; 30(02): 81-89
DOI: 10.1055/s-0038-1634820
DOI: 10.1055/s-0038-1634820
Statistical Applications
Algorithms for Bayesian Belief-Network Precomputation
We thank H. Jacques Suermondt for providing us with his implementation of the Lauritzen-Spiegelhalter algorithm. We gratefully acknowledge the assistance of Ingo Beinlich, who supplied us with the ALARM belief network and provided insightful criticism of earlier versions of this paper. We thank Harold Lehmann for his comments regarding the theoretical basis of our algorithms. Lyn Dupre provided excellent editorial advice. This work is supported by training grant LM-07033 from the National Library of Medicine, by grant IRI-8703710 from the National Science Foundation, and by grant P-25514-EL from the U. S. Army Research office. Computing resources were provided by grant RR-00785 from the Division of Research Resources of the National Institutes of Health.
Further Information
Publication History
Publication Date:
07 February 2018 (online)
Abstract
Bayesian belief networks provide an intuitive and concise means of representing probabilistic relationships among the variables in expert systems. A major drawback to this methodology is its computational complexity. We present an introduction to belief networks, and describe methods for precomputing, or caching, part of a belief network based on metrics of probability and expected utility. These algorithms are examples of a general method for decreasing expected running time for probabilistic inference.
We first present the necessary background, and then present algorithms for producing caches based on metrics of expected probability and expected utility. We show how these algorithms can be applied to a moderately complex belief network, and present directions for future research.
1 A belief network is a special case of an influence diagram. An influence diagram represents decision alternatives and outcome values in addition to the probabilistic associations among variables found in a belief network.
-
REFERENCES
- 1 Pearl J. Evidential reasoning using stochastic simulation of causal models. Artif Intell 1987; 32: 245-57.
- 2 Good IJ. A causal calculus (I). Brit J Philos of Science 1961; 11: 305-18.
- 3 Good IJ. A causal calculus (II). Brit J Philos of Science 1961; 12: 43-51.
- 4 Cooper GE. NESTOR: A Computer-Based Medical Diagnostic Aid that Integrates Causal and Probabilistic Knowledge (Ph. D. dissertation). Department of Medical Information Sciences. Stanford CA: Stanford University; 1984
- 5 Shachter RD. Evaluating influence diagrams. Operations Res 1986; 34: 871-82.
- 6 Howard RA, Matheson JE. Readings on the Principles and Applications of Decision Analysis. Menlo Park CA: Strategic Decisions Group; 1984
- 7 Lauritzen SL, Spiegelhalter DJ. Local computations with probabilities on graphical structures and their applications to expert systems. J Royal Statist Soc 1988; 50: 157-224.
- 8 Cooper GE. Current research directions in the development of expert systems based on belief networks. App Stoch Models and Data Anal 1989; 05: 39-52.
- 9 Horvitz EJ, Breese JS, Henrion M. Decision theory in expert systems and artificial intelligence. J Approx Reas 1988; 02: 247-302.
- 10 Chavez RM, Cooper GE. A randomized approximation algorithm for probabilistic inference on Bayesian belief networks. Networks 1990; 20: 661-85.
- 11 Heckerman DE, Horvitz EJ, Nathwani BN. Update on the Pathfinder project. In: Proceedings of the Thirteenth Annual Symposium on Computer Applications in Medical Care. Washington DC: IEEE Computer Society Press; 1989: 203-7.
- 12 Lehmann HP. Knowledge acquisition for probabilistic expert systems. In: Proceedings of the Twelfth Symposium on Computer Applications in Medical Care. Washington DC: IEEE Computer Society Press; 1988: 73-7.
- 13 Pearl J. Fusion, propagation, and structuring in belief networks. Artif Intell 1986; 29: 241-88.
- 14 Suermondt HJ. Updating probabilities in multiply connected belief networks. In: Proceedings of the Fourth Workshop on Uncertainty in Artificial Intelligence. Minneapolis MIN: American Association for Artificial Intelligence; 1988: 335-43.
- 15 Cooper GE. The computational complexity of probabilistic inference using Bayesian belief networks. Artif Intell 1990; 42: 393-405.
- 16 Henrion M. Propagation of uncertainty by probabilistic logic sampling in Bayes’ networks. In: Kanal LN, Lemmer JF. (eds). Uncertainty in Artificial Intelligence, 2. Amsterdam: Elsevier Science Publ; 1988: 149-63.
- 17 Pearl J. Addendum: Evidential reasoning using stochastic simulation of causal models. Artif Intell 1987; 33: 131-2.
- 18 Schoppers MJ. Universal plans for reactive robots in unpredictable environments. In: Proceedings of the Tenth International Joint Conference on Artificial Intelligence. Milan Italy: International Joint Conferences on Artificial Intelligence; 1987: 1039-46.
- 19 Shachter RD. Intelligent probabilistic inference. In: Kanal LN, Lemmer JF. (eds). Uncertainty in Artificial Intelligence. Amsterdam: Elsevier Science Publ; 1986: 371-82.
- 20 Beinlich IA, Suermonth HJ, Chavez RM, Cooper GF. The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks. In: Proceedings of the Second European Conference on Artificial Intelligence in Medicine. London: Springer Verlag 1989; 38: 247-56.
- 21 Heckerman DE, Horvitz EJ. Personal communication. 1989
- 22 Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Mateo CA: Morgan Kaufmann Publ; 1988
- 23 Breese JS, Horvitz EJ. Ideal reformulation of belief networks. In: Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence. Cambridge MA: Association for Uncertainty in Artificial Intelligence; 1990: 64-9.