**Contents :**Uncertainty in Artificial Intelligence 4 R.D. Shachter T.S. Levitt L.N. Kanal J.F. Lemmer (Editors) © Elsevier Science Publishers B.V. (North-Holland) 1990 69 CAUSAL NETWORKS: SEMANTICS AND EXPRESSIVENESS* Thomas VERMA and Judea PEARL Cognitive Systems Laboratory Computer Science Department University of California Los Angeles Los Angeles CA 90024 Internet: verma@cs.ucla.edu pearl@cs.ucla.edu Dependency knowledge of the form "x is independent ofy once z is known" invariably obeys the four graphoid axioms examples include probabilistic and database dependencies. Often such knowledge can be represented efficiently with graphical structures such as undirected graphs and directed acyclic graphs (DAGs). In this paper we show that the graphical criterion called d-separation is a sound rule for reading independencies from any DAG based on a causal input list drawn from a graphoid. The rule may be extended to cover DAGs that represent functional dependencies as well as conditional dependencies. 1. INTRODUCTION In several areas of research it is beneficial to reason about dependency knowledge. For example in database design it is useful to reason about embedded-multivalued-dependence (EMVD) of attributes [2]. Similarly in decision analysis and expert systems design it is useful to reason about probabilistic independence of variables [5 9]. These examples give two well known formalizations of the intuitive relation "knowing Z renders X and Y independent" which shall be denoted I ( X Z Y ) . Naturally such a relation would have different properties for different formalizations but it is interesting to note that most sensible definitions share the four common properties listed below: symmetry decomposition weakunion contraction I ( X Z Y ) o/(r Z X) I ( X Z Y W ) =>/(X Z r) I ( X Z Y W ) =>I(X ZY W) I ( X Z Y W ) & I ( X Z Y ) =>I(X Z YW) (l.a) (l.b) (l.c) (l.d) where X Y and Z represent three disjoint subsets of objects (e.g. variables or attributes) • This work was partially supported by the National Science Foundation Grant #IRI-8610155. "Graphoids: A Computer Representation for Dependencies and Relevance in Automated Reasoning (Computer Information Science)." 70 and the notation YW is a shorthand for Y u W. These four properties in addition to others hold for EMVDs^ as well as for probabilistic dependencies [1]. Three place relations which obey the four properties listed above are called graphoids^'. Those relations which obey the following additional axiom: intersection I(X ZY W) & I(X ZW Y) =>I(X Z YW) (2) are called positive graphoids since this axiom holds for probabilistic dependencies when the distributions are constrained to be strictly positive (non-extreme distributions). A naive approach for representing a dependency model i.e. particular instance of a dependency relation would be to enumerate all triplets ( X Z Y ) for which I ( X Z Y ) holds. This could require an exponential amount space since the relation / ranges over subsets of objects. In fact any general representation scheme will require exponential space on average to represent a dependency model given that it is a graphoid probabilistic dependency or EMVD [14]. The graphical representation schemes presented in this paper are appealing for three reasons. First the graphs have an intuitive conceptual meaning. Second the representations are efficient in terms of time and space [11]. Third there exist various efficient algorithms that make implicit use of these representation schemes [6 7 8 9 12 13]. 2. UNDIRECTED GRAPHS The meaning of a particular undirected graph is straight forward each node in the graph represents a variable and a link in the graph means that the two variables are directly dependent. With this semantics a set of nodes Z would separate two other sets X and Y if and only if every path between a node in X and a node in Y passes through Z. This representation can fully represent only a small set of dependency models defined by the following properties [10]: symmetry decomposition strongunion intersection transitivity I(X Z Y) wI(Y Z X) I(X Z YW) =^I(X Z Y) I(X Z Y) =>l(X ZW Y) I(X ZY W) & I(X ZW Y) =^I(X Z YW) I(X Z Y) =>I(X Z j)or I(Y Z y)Vye XYZ (3.a) (3.b) (3.c) (3.d) (3.e) It is not always necessary nor feasible to have an exact representation of a dependency model; in fact an efficient approximation called an I-map is often preferred to an inefficient perfect map. A representation R is an I-map of a dependency model M iff every independence statement represented by R is also a valid independence ofAf. Thus R may not represent every statement of M but the ones it does represent are correct. The rationale behind the use of I-maps is that an ignored independence will cause a redundant consultation thus only cost some time whereas use of an incorrect independence will cause (1) The notation I ( X Z Y ) is equivalent to the standard EMVD notation Z —»->X I Y. •' Historically the tenn semi-graphoids was used for graphoids and graphoids was used for positive graphoids. 71 relevant information to be ignored thereby corrupting the integrity of the system. (This rationale presupposes a specific type of use for the dependency knowledge thus will not apply in general). The set of undirected graphs that are I-maps of a given positive graphoid forms a complete lattice under the I-mapness relation. This means that every positive graphoid has a unique most representative I-map graph. Furthermore there is a polynomial algorithm which will find it [10]. Thus for example every non-extreme probability distribution P has a unique edge-minimal undirected graph I-map of P (i.e. no edge can be removed without destroying the I-mapness of this graph). This is not the case for EMVD relations nor for probabilistic distributions in general. In fact with out the intersection property there is no unique edge-minimal I-map for a given model and moreover there is no effective method of constructing even one of the minimal I-maps. Hence undirected graphs are only useful as I-maps of positive graphoids. 3. DffiECTED-ACYCLIC GRAPHS (DAGS) The dependency model represented by a particular DAG has a simple causal interpretation. Each node represents a variable and there is a directed arc from one node to another if the first is a direct cause of the second. Under this interpretation graph-separation is not as straight forward as before since two unrelated causes of a symptom may become related once the symptom is observed [8]. In general a set of nodes Z is defined to d-separate two other sets X and Y if and only if every trail from a node in X to a node in Y is rendered inactive by Z. A trail is a path which follows arcs ignoring their directionality and is rendered inactive by a set of nodes Z in exactly two ways; either there is a head-to-head node on the trail which is not in Z and none of its descendents are in Z or some node on the trail is in Z but is not head-to-head. A node on the trail is head-to-head if the node before it and after it on the trail both point to it in the graph. One node is a descendent of another if there is a directed trail from the latter to the former. There is a procedure that produces an edge-minimal I-map DAG for any graphoid. It employs an algorithm which takes a causal input list (or simply causal list) of a dependency model and produces a perfect map of the list's graphoid closure. A casual list of a dependency model contains two things: an ordering of the variables and a function that assigns a tail boundary to each variable x. For each variable x let U^ denote the set of all variables which come before x in the given ordering. A tail boundary of a variable x denoted B^ is any subset of U^ that renders x independent of U^-B^. A unique DAG can be generated from each casual list by associating the tail boundary of the variable x in the list with the set of direct parents of any node x in the DAG. An equivalent specification of a casual list is an ordered list of triplets of the form / (x 5^ R) one triplet for each variable in the model where R is t/ -5». For a particular dependency model over n variables there are n! orderings and for each ordering there can be up to V^'W- different sets of tail boundaries since in the worst case every subset of lesser variables could be a boundary. Thus there can be as many as n \ 2"("-ly- casual lists for any given dependency model. But if a model posses a perfect map DAG then one of the causal lists is guaranteed to generate that DAG by the following theorem. 72 Theorem 1: If M is a dependency model which can be perfectly represented by some DAG D then there is a causal list LQ which generates D. Proof: Let D be a DAG which perfectly represents M. Since D is a directed acyclic graph it imposes a partial order <)) on the variables ofAf. Let 9 be any total ordering consistent with<|)(i.e. a <^b =>a

**Rating :**-
**Length :**8 pages **File Size:**512.2 kb**Virus Tested :**No**Verified :**2015-11-29**Source:**ftp.cs.ucla.edu

INFO HASH : a9bc43a3f44ca745c6b8543e9383dfba

**Source:**ftp.cs.ucla.edu**Rating :**

No description.