Browse Prior Art Database

THE LOGIC OF REPRESENTING DEPENDENCIES BY DIRECTED GRAPHS

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

Publishing Venue

Software Patent Institute

Related People

Judea Pearl: AUTHOR [+3]

Abstract

Data-dependencies of the type "x can tell us mono about y given that we already know z " can be represented in various formalisms: Probabilistic Dependencies (PD), Embedded-Mufti-Valued Depen-dencies (EMVD), Undirected Graphs (UG) and Directed-Acyclic Graphs (DAGs). This paper provides an axiomatic basis, called a semi-graplsoid, which captures the structure common to all four types of depen-dencies and explores the expressive power of DAGs in representing various types of data dependencies. It is shown that DAGs can represent a richer set of dependencies than UGs, that DAGs completely represent the closure of their generating bases, and that they offer an effective computational device for testing con-sistency in a given set of dependencies as well as inferring new dependencies from that set. These proper-ties might explain the prevailing use of DAGs in causal reasoning and semantic nets.

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

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE LOGIC OF REPRESENTING DEPENDENCIES BY DIRECTED GRAPHS

Judea Pearl February 1987 Thomas Verms CSO-870004

TECHNICAL REPORT R-79 February, 1987 THE LOGIC OF REPRESENTING DEPENDENCIES BY DIRECTED GRAPHS by Judea Pearl & Thomas Verma

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

ABSTRACT

Data-dependencies of the type "x can tell us mono about y given that we already know z " can be represented in various formalisms: Probabilistic Dependencies (PD), Embedded-Mufti- Valued Depen-dencies (EMVD), Undirected Graphs (UG) and Directed-Acyclic Graphs (DAGs). This paper provides an axiomatic basis, called a semi-graplsoid, which captures the structure common to all four types of depen-dencies and explores the expressive power of DAGs in representing various types of data dependencies. It is shown that DAGs can represent a richer set of dependencies than UGs, that DAGs completely represent the closure of their generating bases, and that they offer an effective computational device for testing con-sistency in a given set of dependencies as well as inferring new dependencies from that set. These proper-ties might explain the prevailing use of DAGs in causal reasoning and semantic nets.

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 Grant #DCR 85-01234.

1. INTRODUCTION

Why Dependencies? '

The notion of relevance or informational dependency is basic to human reasoning. People tend to judge the 3-place relationships of mediated dependency (i.e., x influences y via z ) with clarity, conviction and consistency. For example, knowing the departure time of the last bus is relevant for assessing how long we are about to wait for the next bus. However, once we learn the current whereabouts of the next bus, the former no longer provides useful information. These common-sensical judgments are issued qualitatively and reliably and are robust to the uncertainties which accompany the assessed events. Con-sequently, if one aspires to construct common-sensical reasoning systems, it is important that the language used for representing knowledge should allow assertions about dependency relationships to be expressed qualitatively, directly and explicitly. Moreover, the verification of dependencies should be

UCLA Page 1 Dec 31, 1987

Page 2 of 12

THE LOGIC OF REPRESENTING DEPENDENCIES BY DIRECTED GRAPHS

accomplished swiftly by a few primitive operations on the salient features of the representation scheme.

Making effective use of information about dependencies is a computational necessity, essential in any reasoning. If we have acquired a body of knowledge z and now wish to assess the truth of proposition x, it is important to know whether it would be worthwhile to consult anot...