The Logic of Representing Dependencies by Directed Graphs

Judea Pearl, Thomas VermaAAAI 1987

This paper introduces the concept of "semi-graphoids" and "graphoids" as formalisms for representing dependencies between pieces of information. It argues that directed acyclic graphs (DAGs) are a more expressive and computationally efficient tool for capturing these dependencies compared to undirected graphs, particularly for probabilistic and logical reasoning.

TL;DR

This paper formalizes the notion of "mediated dependency" using graph-based structures and introduces DAGs as a superior representation over undirected graphs for capturing complex dependencies. DAGs offer a more expressive and computationally tractable way to infer relationships, making them ideal for causal and semantic reasoning.

What Problem Does This Paper Address?

Human reasoning relies heavily on understanding how different pieces of information influence each other, even indirectly. For example, knowing the bus schedule is relevant to how long you'll wait for the next bus, but this relevance disappears if you know the bus's current location. This paper tackles the challenge of creating symbolic systems that can effectively represent and reason about these "informational dependencies" and their dynamic nature. Existing formalisms like probabilistic dependencies and database dependencies capture this, but explicit encoding is impractical due to combinatorial explosion. The authors seek a logic that allows for qualitative reasoning about these dependencies, mirroring human intuition and enabling efficient inference.

Methods

The paper proposes a formal framework for representing dependencies, starting with the general notion of a "dependency model" defined by triplets of disjoint sets (X, Z, Y) indicating that X is independent of Y given Z. They then define specific types of dependency models:

  • Probabilistic Dependencies (PD): Based on conditional independence in probability distributions.
  • Embedded Multivalued Dependencies (EMVD): From relational databases, capturing how fixed attributes constrain others.
  • Undirected Graph Dependency models (UGD): Where independence is defined by cutsets in undirected graphs.
  • Directed Acyclic Graph Dependency models (DAGD): Where independence is defined by "d-separation" in DAGs.

These models are then unified under the umbrella of semi-graphoids (closed under symmetry, decomposition, and weak union) and graphoids (semi-graphoids also closed under intersection). The core contribution lies in demonstrating the superior expressive power of DAGs over undirected graphs for representing these dependencies, particularly for non-transitive relationships. They introduce the concept of a "stratified protocol" as a parsimonious basis for DAGs, which allows for efficient inference of dependencies.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • DAGs are more expressive than undirected graphs: While undirected graphs can represent some dependencies, they struggle with non-transitive relationships. DAGs, by using arrow directionality, can capture a richer set of dependencies, including those that are not directly transitive.
  • D-separation is key to DAG expressiveness: The concept of d-separation in DAGs provides a graphical criterion for conditional independence that is more powerful than simple cutset separation in undirected graphs.
  • Semi-graphoids and Graphoids provide a unifying framework: These axiomatic systems capture the essential properties of various dependency models, allowing for a general theory of mediated dependence.
  • DAGs enable efficient inference: By representing dependencies as DAGs, inference tasks that would be computationally expensive in other formalisms can be performed efficiently through graphical manipulations. This is facilitated by "stratified protocols," which act as compact bases for DAGs.
  • Auxiliary variables can bridge the gap: Even when an undirected graph's dependency structure cannot be directly represented by a DAG, introducing auxiliary variables can achieve this equivalence.

Key Results

  • Theorem 1: Undirected Graph Dependencies (UGD) and Directed Acyclic Graph Dependencies (DAGD) intersect in dependency models representable by chordal graphs. Non-chordal graphs highlight where undirected graphs have superior expressiveness, but this can be overcome with auxiliary variables.
  • Theorem 2: Every dependency model expressible by an undirected graph is also expressible by a DAG, potentially with the addition of auxiliary nodes.
  • Theorem 3: For any semi-graphoid, a DAG generated from a stratified protocol is an I-map of the semi-graphoid. This means any independence inferred from the DAG is true in the original model.
  • Corollary to Theorem 3: A DAG generated from a stratified protocol is a perfect map of the semi-graphoid closure of that protocol. This generalizes the Markov-chain property to qualitative dependencies.
  • Theorem 4: For any semi-graphoid, the set of DAGs generated from all its stratified protocols forms a perfect map of the semi-graphoid.

Limitations and Future Work

The paper acknowledges that while DAGs are powerful, they might not perfectly capture all aspects of dependencies, especially when dealing with logical, functional, and definitional constraints that are excluded from purely probabilistic models. The authors suggest that DAGs provide a powerful inference tool for handling data dependencies in probabilistic and logical reasoning, explaining their prevalence in causal models and semantic nets. Future work could explore the axiomatization of EMVD and PD, and further investigate the computational advantages of DAGs for complex reasoning tasks.

Summary updated

BibTeX
@inproceedings{pearl1987logic,
  author = {Judea Pearl and Thomas Verma},
  title = {{The Logic of Representing Dependencies by Directed Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure