Source-linked AI summary
Causal Networks: Semantics and Expressiveness
Tom S. Verma, Judea Pearl
TL;DR
Dependency models may require exponential-space representations, motivating efficient graphical alternatives. The paper formalizes d-separation for DAGs and proves that it soundly and completely extracts dependencies from suitable models.
Problem
Dependency models may require exponential-space relation-based representations, motivating efficient graphical representations.
Method
The paper uses d-separation, which determines whether paths between node sets are inactive under conditioning based on path structure and descendants.
Results
d-separation is sound and complete for extracting dependencies from the represented dependency model.
Takeaways & Limitations
DAGs provide a graphical criterion that can exactly extract the dependencies of the represented model.
Takeaways & Limitations
Some dependency models lack a unique edge-minimal I-map and have no effective procedure for finding one.
Abstract
from arXiv · showhide
Dependency knowledge of the form "x is independent of y 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.
INTRODUCTION
Dependency knowledge formalizes conditional independence across applications such as databases, probabilistic reasoning, and expert-system design, with common graphoid properties. Because explicit enumeration can require exponential space, graphs offer an intuitive, efficient, and algorithmically useful representation.
- INTRODUCTION: Conditional independence, denoted I(X, Z, Y), captures the idea that knowing Z renders X and Y independent across database and probabilistic applications.Examples include embedded-multivalued dependencies and probabilistic independence of variables.
- INTRODUCTION: Most sensible conditional-independence definitions share four properties, and relations satisfying them are called semi-graphoids.EMVD and probabilistic dependency relations obey these four properties.
- INTRODUCTION: Enumerating every valid dependency triplet can require exponential space because conditional independence ranges over subsets of objects.This motivates representing dependency models with graphical structures.
- INTRODUCTION: Graphs provide dependency representations with intuitive conceptual meaning, efficient time and space use, and methods that exploit organized dependency information.The paper identifies these as three advantages of graph-based representation.
1988] , [Shachter, 1985, 1988].
The section contrasts undirected graphs with DAGs as representations of dependency models, emphasizing the limitations of exact or minimal maps and defining d-separation for causal structures. It also describes a procedure for constructing minimal I-maps from stratified protocols for semi-graphoids.
- Undirected graphs: Undirected graphs encode direct dependence through links, while node separation represents conditional independence but can fully represent only a limited class of dependency models.A set Z separates X and Y when every path between them passes through Z.
- Undirected graphs: An I-map need only contain valid independencies, making efficient approximations preferable to inefficient perfect maps.The passage defines an I-map as a representation whose encoded independencies all hold in the dependency model.
- Undirected graphs: Positive-probability distributions have a unique edge-minimal undirected I-map, whereas EMVD relations and distributions excluding event combinations lack unique minimal I-maps and an effective construction method.The positive-probability result applies to non-extreme distributions; the latter models may lack any effectively constructible minimal I-map.
- Directed-acyclic graphs (DAGs): In a DAG, directed arcs represent direct causes, and d-separation renders every adjacency path between X and Y inactive under Z.Adjacency paths ignore arc direction; a path is inactive when a head-to-head condition blocks it or a non-head-to-head node lies in Z.
- Directed-acyclic graphs (DAGs): A head-to-head path node blocks a path when it and its descendants are outside Z, while a non-head-to-head node blocks it when included in Z.A head-to-head node has both neighboring path arcs pointing toward it, and descendants are connected by directed paths.
- Directed-acyclic graphs (DAGs): A procedure constructs a minimal I-map for any semi-graphoid by converting a stratified protocol into a DAG and a perfect map of its closure.The protocol orders variables and assigns each a tail boundary; that boundary becomes the variable’s set of direct parents.
I I I
The section proves that stratified protocols generate DAGs that are sound I-maps, with d-separation exactly capturing their semi-graphoid consequences. It further establishes perfect-map and minimal-I-map results, and extends representational coverage to arbitrary semi-graphoids and deterministic dependencies.
- Stratified protocols and DAGs: A dependency model perfectly representable by a DAG has a stratified protocol that generates that DAG.The protocol uses any total ordering consistent with the DAG’s partial order and each node’s parent set as its tail boundary.
- Stratified protocols and DAGs: Any stratified protocol of a semi-graphoid generates a DAG that is an I-map of the dependency model.This extends the construction beyond models that possess perfect maps in DAGs.
- Corollaries: A generated DAG is a perfect map of the semi-graphoid closure of its protocol, and minimal tail boundaries yield a minimal I-map.D-separation holds exactly when the corresponding independence follows from the protocol using the four graphoid axioms.
- Corollaries: D-separation is sound and complete for extracting independence information from DAGs relative to their stratified protocols.The paper also states that d-separation is sound for Bayesian-network distributions, while semi-graphoid completeness does not guarantee that it identifies more independencies than every other sound criterion.
- Multiple DAGs and extensions: For any semi-graphoid, the collection of DAGs generated from all stratified protocols is a perfect map when separation holds in at least one DAG.An effective algorithm can generate an I-map DAG for every semi-graphoid, supporting DAG representations of EMVD and probabilistic independence relations.
- Multiple DAGs and extensions: ID-separation extends d-separation to graphs with deterministic nodes and is sound and complete with respect to the input protocol under probabilistic and semi-graphoid inference.Deterministic-node graphs represent information that ordinary d-separation cannot fully extract.