Download PDF
Methods Inf Med 1991; 30(02): 81-89
DOI: 10.1055/s-0038-1634820
Statistical Applications
Schattauer GmbH

Algorithms for Bayesian Belief-Network Precomputation

E. H. Herskovits
1   Section on Medical Informatics, Stanford University, Stanford CA, USA
,
G. F. Cooper
1   Section on Medical Informatics, Stanford University, Stanford CA, USA
› Author AffiliationsWe 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)

    Permissions and Reprints

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.

Key-Words

Expert Systems - Algorithms - Computer-Assisted Diagnosis - Probability Theory

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.
    CrossrefPubMedSearch in Google Scholar
  • 2 Good IJ. A causal calculus (I). Brit J Philos of Science 1961; 11: 305-18.
    PubMedSearch in Google Scholar
  • 3 Good IJ. A causal calculus (II). Brit J Philos of Science 1961; 12: 43-51.
    PubMedSearch in Google Scholar
  • 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
    Search in Google Scholar
  • 5 Shachter RD. Evaluating influence diagrams. Operations Res 1986; 34: 871-82.
    CrossrefPubMedSearch in Google Scholar
  • 6 Howard RA, Matheson JE. Readings on the Principles and Applications of Decision Analysis. Menlo Park CA: Strategic Decisions Group; 1984
    Search in Google Scholar
  • 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.
    PubMedSearch in Google Scholar
  • 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.
    PubMedSearch in Google Scholar
  • 9 Horvitz EJ, Breese JS, Henrion M. Decision theory in expert systems and artificial intelligence. J Approx Reas 1988; 02: 247-302.
    PubMedSearch in Google Scholar
  • 10 Chavez RM, Cooper GE. A randomized approximation algorithm for probabilistic inference on Bayesian belief networks. Networks 1990; 20: 661-85.
    CrossrefPubMedSearch in Google Scholar
  • 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.
    Search in Google Scholar
  • 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.
    Search in Google Scholar
  • 13 Pearl J. Fusion, propagation, and structuring in belief networks. Artif Intell 1986; 29: 241-88.
    CrossrefPubMedSearch in Google Scholar
  • 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.
    Search in Google Scholar
  • 15 Cooper GE. The computational complexity of probabilistic inference using Bayesian belief networks. Artif Intell 1990; 42: 393-405.
    CrossrefPubMedSearch in Google Scholar
  • 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.
    Search in Google Scholar
  • 17 Pearl J. Addendum: Evidential reasoning using stochastic simulation of causal models. Artif Intell 1987; 33: 131-2.
    CrossrefPubMedSearch in Google Scholar
  • 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.
    Search in Google Scholar
  • 19 Shachter RD. Intelligent probabilistic inference. In: Kanal LN, Lemmer JF. (eds). Uncertainty in Artificial Intelligence. Amsterdam: Elsevier Science Publ; 1986: 371-82.
    Search in Google Scholar
  • 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.
    PubMedSearch in Google Scholar
  • 21 Heckerman DE, Horvitz EJ. Personal communication. 1989
    PubMedSearch in Google Scholar
  • 22 Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Mateo CA: Morgan Kaufmann Publ; 1988
    Search in Google Scholar
  • 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.
    Search in Google Scholar