×

The representation power of probabilistic knowledge by undirected graphs and directed acyclic graphs: A comparison. (English) Zbl 0806.68101

Summary: Two modes of representation of probabilistic knowledge are considered: undirected graphs (UG’s) and directed acyclic graphs (DAG’s). It is shown that there is a UG such that the knowledge represented in it requires exponentially many (in the number of vertices of the UG) DAG’s for its representation and there is a DAG such that the knowledge represented in it requires exponentially many UG’s for its representation. It is thus shown that neither method can be preferred in all cases over the other.

MSC:

68T30 Knowledge representation
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lauritzen S. L., Lectures on Contingency Tables (1982)
[2] Lauritzen S. L., Independence Properties of Directed Markov Fields (1988)
[3] Paz A., Closure Algorithms and Decision Problems for Graphoids Generated by Two Undirected Graphs–Abridged Version (1988)
[4] Pearl J., In Proc. 6th Natl. Conf. pp 374– (1987)
[5] Pearl J., GRAPHOIDS A Graph-Based Logic for Reasoning about Relevance Relations (1986)
[6] Pearl J., Probabilistic Reasoning in Intelligent Systems Networks of Plausible Inference (1988) · Zbl 0746.68089
[7] Studený M. [ 1989 ], ”Attempts at Axiomatic Description of Conditional Independence.” Kybernetika , 25 ( 1989 ), No. 1–3 , pp. 72 – 79 .
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.