Identifying independence in Bayesian networks. (English) Zbl 0724.05066

An important feature of Bayesian networks is that they facilitate explicit encoding of information about independencies in the domain, information that is indispensable for efficient inferencing. This paper characterizes all independence assertions that logically follow from the topology of a network and develops a linear time algorithm that identifies these assertions. Finally, the algorithm is shown to work for a broad class of nonprobabilistic independencies.


05C99 Graph theory
Full Text: DOI


[1] Mathematical Methods of Statistics, Princeton University Press, Princeton, NJ (1964).
[2] Dawid, J. R. Stat. Soc. B 41 pp 1– (1979)
[3] Introduction to Structural Equation Models, Academic Press, New York (1975). · Zbl 0337.90019
[4] Graph Algorithms, Computer Science Press, Potomac, MD (1979). · Zbl 0441.68072
[5] Fagin, ACM Trans. Database Syst. 2 pp 262– (1977)
[6] Fagin, Proc. Symp. Appl. Math. 34 pp 19– (1986) · doi:10.1090/psapm/034/846853
[7] Personal communication (1988).
[8] Graphoids–A qualitative framework for probabilistic inference. Ph. D dissertation, UCLA (1990).
[9] and , On the logic of causal models. Proceedings of the 4th Workshop on Uncertainty in AI, St. Paul, MN, August (1988) 136–147.
[10] and , Logical and algorithmic properties of conditional independence. Technical Report 870056 (R-97), UCLA Cognitive Systems Laboratory February (1988) To appear in Ann. Statist.
[11] , , and , Discovering Causal Structure, Academic Press, New York (1987).
[12] and , Influence diagrams. Principles and Applications of Decision Analysis, Strategic Decisions Group, Menlo Park, CA (1981).
[13] Isham, Int. Stat. Rev. 49 pp 21– (1981)
[14] Lectures on Contingency Tables, 2nd ed., University of Aalborg Press, Aalborg, Denmark (1982).
[15] Lauritzen, J. R. Stat. Soc. 50 pp 157– (1988)
[16] Lauritzen, Networks 20 pp 491– (1990)
[17] On representing and solving decision problems. Ph. D. Thesis, EES Dept., Stanford University (1983).
[18] Pearl, Artificial Intell. 29 pp 241– (1986)
[19] Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, San Mateo, CA (1988).
[20] and , Graphoids: A graph-based logic for reasoning about relevance relations. Advances in Artificial Intelligence-II ( et al., Eds.), North Holland, Amsterdam (1987) 357–363.
[21] and , The logic of representing dependencies by directed acyclic graphs. Proceedings of the AAAI, Seattle, Washington, July (1987) 374–379.
[22] Shachter, Operations Res. 36 pp 589– (1988)
[23] Shachter, Networks 20 pp 535– (1990)
[24] Shafer, Int. J. Approximate Reasoning 1 pp 349– (1987)
[25] Smith, Ann. Stat. 17 pp 654– (1989)
[26] Spohn, J. Phil. Logic 9 pp 73– (1980)
[27] Fundamentals of dependency theory. Trends in Theoretical Computer Science (Ed.), Computer Science Press, Rockville, MD (1988) 171–224.
[28] Some mathematical properties of dependency models. UCLA Cognitive Systems Laboratory, Technical Reports R-103 (1987).
[29] and , Causal networks: Semantics and expressiveness. Proceedings of the 4th Workshop on Uncertainty in AI, St. Paul, MN (1988) 352–359.
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.