×

An algebra of Bayesian belief universes for knowledge-based systems. (English) Zbl 0719.68081

Summary: Causal probabilistic networks (CPNs) have proved to be a useful knowledge representation tool for modeling domains where causal relations - in a broad sense - are a natural way of relating domain concepts and where uncertainty is inherited in these relations. The domain is modeled in a CPN by use of a directed graph where the nodes represent concepts in the domain and the arcs represent causal relations. Furthermore, the quantitative relation between a node and its immediate causes is expressed as conditional probabilities. During the last few years, several schemes based on probability theory for incorporating and propagating new information throughout a CPN has emerged. As long as the domain can be modeled by use of a singly connected CPN (i.e., no more than one path between any pair of nodes), the schemes operate directly in the CPN and perform conceptually simple operations in this structure. When it comes to more complicated structures such as multiply connected CPNs (i.e., more than one path is allowed between pairs of nodes), the schemes operate in derived strcutures where the embedded domain knowledge no longer is as explicit and transparent as in the CPN. Furthermore, the simplicity in the operations is lost also. This report outlines a scheme - the algebra of Bayesian belief universes - for absorbing and propagating evidence in multiply connected CPNs. The scheme provides a secondary struture, a junction tree, and a simple set of algebraic operations between objects in this structure, CollectEvidence and DistributeEvidence. These are the basic tools for making inference in a CPN domain model and yield a calculus as simple as in the case of singly connected CPNs.

MSC:

68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
62F15 Bayesian inference
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] , and , The HUGIN core–Preliminary considerations on systems for fast manipulations of probabilities. Proceedings of Workshop on Inductive Reasoning: Managing Empirical Information in Al-Systems. Risø National Laboratory, Roskilde, Denmark (1987).
[2] , , and , HUGIN–A shell for building belief universes for expert systems. Proceedings 11th International Joint Conference on Artificial Intelligence, Detroit (1989). · Zbl 0713.68051
[3] , , , , , , , and , MUNIN–An expert EMG assistant. Computer-Aided Surface or Needle Electromyography and Expert Systems in Diagnosis (Ed.), Elsevier, Amsterdam (1989).
[4] Graphs and Hypergraphs (Translation from French by E. Minicka) North-Holland, Amsterdam (1973).
[5] In Defence of probability. Proceedings of 9th International Joint Conference on Artificial Intelligence, Los Angeles (1985) 1002–1009.
[6] NESTOR: A computer based medical diagnostic aid that integrates causal and probabilistic knowledge. Technical report HHP-84-48, Medical Computer Science Group, Stanford University, Stanford, CA (1984).
[7] Probabilistic inference using belief networks is NP-hard. Memo KLS-87-27, Knowledge Systems Laboratory, Medical Computer Science Group, Stanford University, Stanford, CA (1987).
[8] , , , and , Computer-aided diagnosis of acute abdominal pain. Br. Med. J. (1972) 9–13.
[9] , and , Optimization in constraint networks. Proceedings of Conference on Influence Diagrams for Decision Analysis, Inference, and Prediction, University of California, Berkeley, May (1988).
[10] Algorithmic Graph Theory and Perfect Graphs. Academic Press, London (1980). · Zbl 0541.05054
[11] Horvitz, J. Approximate Reasoning (1988)
[12] and , Influence diagrams, in readings in decision analysis ( and , Eds.), Strategic Decisions Group, Menlo Park, CA (1981) chap. 38, 763–771.
[13] Discussion in Ref. 20.
[14] Junction trees and decomposable hypergraphs. JUDEX Research Report, Aalborg, Denmark (1988).
[15] , , and , MUNIN: On the case for probabilities in medical expert sytems–A practical exercise. Proceedings of First Conference of European Society for Artificial Intelligence in Medicine (, , Eds), Springer-Verlag, Heidelberg (1987) 149–160.
[16] Jensen, Computational Statistics Quarterly.
[17] and , A computational model for causal and diagnostic reasoning in inference systems. Proceedings 8th International Joint Conference on Artificial Intelligence, Karlsruhe, West Germany (1983) 190–193.
[18] (1989) Triangulation of graphs–Algorithms giving small total clique size. In preparation.
[19] Lauritzen, J. Aust. Math. Soc. A 36 pp 12– (1984)
[20] Lauritzen, J. R. Stat. Soc. B 50 pp 157– (1988)
[21] and , Discussion in Ref. 20.
[22] , , , , , and , A MUNIN network for the median nerve-A case study on loops. Appl. Artificial Intell. Special Issue: Towards Causal AI Models in Practice (1989) 385–403.
[23] Pearl, Artificial Intell. 29 pp 241– (1986)
[24] A constraint-propagation approach to probabilistic reasoning. and Eds.), Uncertainty in Artificial Intelligence, Elsevier, Amsterdam (1986) 357–369. · doi:10.1016/B978-0-444-70058-2.50031-0
[25] and , Graphoids. Graph-based logic for reasoning about relevance relations. Proceedings 7th European Conference on Artificial Intelligence, Brighton, UK (1986) 55–61.
[26] Rose, SIAM J. Comput. 5 pp 266– (1976)
[27] Schachter, Operational Res. 34 pp 871– (1986) · doi:10.1287/opre.34.6.871
[28] Schachter, AI Magazine 8 pp 55– (1987)
[29] and , Bayesian and belief-function propagation. School of Business Working Paper no. 121, University of Kansas, Lawrence (1988).
[30] Fast algorithms for probabilistic reasoning in influence diagrams with application in genetics and expert systems. Proceedings of Conference on Influence Diagrams, Berkeley, May (1988).
[31] and , Updating probabilities in expert systems. Technical Report, MCR Biostatistics Unit, Cambridge (1988).
[32] Tarjan, SIAM J. Comput. 13 pp 566– (1984)
[33] Yannakakis, SIAM J. Algebraic Discrete Methods 2 pp 77– (1981)
[34] Is probability theory sufficient for dealing with uncertainty in AI: A negative view. Uncertainty in Artificial Intelligence ( and , Eds.), North-Holland, Amsterdam (1986) 103–116. · doi:10.1016/B978-0-444-70058-2.50012-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.