Browse Prior Art Database

CAUSAL NETWORKS: SEMANTICS AND EXPRESSIVENESS

IP.com Disclosure Number: IPCOM000128348D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 10 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

Thomas Verma: AUTHOR [+3]

Abstract

Dependency knowledge of the foam "x is independent of y once z is known" can often be stored efficiently in graphical structures. Both undirected graphs, and DAGs (directed acyclic graphs) have been studied for this purpose. It is shown that DAGs constructed from stratified protocols do in fact perfectly represent the underlying dependency model whenever possible. Further, if the underlying model is a semi-graphoid then the DAG generated by any protocol is an I-reap of the model (i.e. produces sound assertions of independence) and the set of all DAGs generated is a perfect map. Finally the possibility of using hybrid graphs with both directed and undirected links is introduced and shown to be more expres-sive than the union of the previous two representations.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

CAUSAL NETWORKS: SEMANTICS AND EXPRESSIVENESS

Thomas Verma July 1987 CSD TECHNICAL REPORT R-65-I June 1987 Causal Networks: Semantics and Expressiveness

_ by

Thomas Verma

Cognitive Systems Laboratory Computer Science Department University of California Los Angeles, CA 90024 verrna@cs.ucla.edu

ABSTRACT

Dependency knowledge of the foam "x is independent of y once z is known" can often be stored efficiently in graphical structures. Both undirected graphs, and DAGs (directed acyclic graphs) have been studied for this purpose. It is shown that DAGs constructed from stratified protocols do in fact perfectly represent the underlying dependency model whenever possible. Further, if the underlying model is a semi-graphoid then the DAG generated by any protocol is an I-reap of the model (i.e. produces sound assertions of independence) and the set of all DAGs generated is a perfect map. Finally the possibility of using hybrid graphs with both directed and undirected links is introduced and shown to be more expres-sive than the union of the previous two representations.

Science track

Major topic: Knowledge Representation

Subtopics: Data Dependencies, Logic of Relevance, Network Representations * This work was supported in part by the National Science Foundation Grants #DCR 85-01234 and #IRI 86 ntroduction

Dependency knowledge is useful in several areas of research, for example in database design it is useful to reason about embedded-multivalued-dependence (EMVD) of attributes [Fagin, 1977] and in ex-pert systems it is useful to reason about probabilistic independence of variables [Pearl, 1986a]. These ex-amples represent two formalizations of the intuitive relation "knowing Z renders X and Y independent" which shall be denoted as I (X, Z, Y). This relation would naturally have different properties in different applications, but it is interesting to note that most sensible definitions of this relation share four common properties listed below:

(Equation Omitted)

where X, Y and Z represent three disjoint subsets of objects (e.g. variables, attributes). It is known that every EMVD relation obeys the four properties listed above, as well as many other properties. (The nota-tion I (X, Z, Y) is equivalent to the standard EMVD notation Z -).*X I Y). Probabilistic dependencies also obey these four properties, and it has been conjectured that they are, in fact, complete [Pearl and Paz, 1986), namely, that any other property of probabilistic

UCLA Page 1 Dec 31, 1987

Page 2 of 10

CAUSAL NETWORKS: SEMANTICS AND EXPRESSIVENESS

independence is a logical consequence of the four. Three place relations which obey these four properties are called semi-graphoids [Dawid, 1979].

It is worth noting that for probability distributions containing strictly positive probabilities, the independence relation has a fifth independent property:

(Equation Omitted)

This property along with the four of semi-grapho...