An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation

Abstract

An Algorithm for Deciding if a Set of Observed Has a Causal Explanation Thomas Verma Northrop Corporation One Research Park Palos Verdes, CA 90274 [email protected] Abstract In a previous paper [Pearl and Verma, 1991] we presented an algorithm for extracting causal influences from independence informa- tion, where a causal influence was defined as the existence of a directed arc in all mini- mal causal models consistent with the data. In this paper we address the question of de- ciding whether there exists a causal model that explains ALL the observed dependencies and independencies. Formally, given a list M of conditional independence statements, it is required to decide whether there exists a directed acyclic graph (dag) D that is per- fectly consistent with M, namely, every state- ment in M, and no other, is reflected via d- separation in D. We present and analyze an effective algorithm that tests for the existence of such a dag, and produces one, if it exists. Introduction Directed acyclic graphs (dags) have been widely used for modeling statistical data. Starting with the pio- neering work of Sewal Wright [Wright, 1921] who in- troduced path analysis to statistics, through the more recent development of Bayesian networks and influence diagrams, dag structures have served primarily for en- coding causal influences between variables as well as between actions and variables. Even statisticians who usually treat causality with ex- treme caution, have found the structure of dags to be an advantageous model for explanatory purposes. N. Wermuth, for example, mentions several such ad- vantages [Wermuth, 1991]. First, the dag describes a stepwise stochastic process by which the data could have been generated and in this sense it may even prove the basis for developing causal explanations [Cox, 1992]. Second, each parameter in the dag has a well understood meaning since it is a conditional probability, i.e., it measures the probability of the re- sponse variable given a particular configuration of the Independencies Judea Pearl Cognitive Systems Laboratory Computer Science Department University of California Los Angeles, CA 90024 [email protected] explanatory (parents) variables and all other variables being unspecified. Third, the task of estimating the parameters in the dag model can be decomposed into a sequence of local estimation analyses, each involv- ing a variable and its parent set in the dag. Fourth, general results are available for reading all implied independencies directly off the dag [Verma, 1986], [Pearl, 1988], [Lauritzen et al., 1990] and for deciding from the topology of two given dags whether they are equivalent, i.e., whether they specify the same set of independence-restrictions on the joint distribu- tion [Frydenberg, 1990], [Verma and Pearl, 1990], and whether one dag specifies more restrictions than the other [Pearl et al., 1989] . This paper adds a fifth advantage to the list above. It presents an algorithm which decides for an ar- bitrary list of conditional independence statements whether it defines a dag and, if it does, a correspond- ing dag is drawn. The algorithm we present has its basis in the Inferred-Causation (IC) algorithm de- scribed in [Pearl and Verma, 1991] and in Lemmas 1 and 2 of [Verma and Pearl, 1990]. Whereas in [Pearl and Verma, 1991] we were interested in detect- ing local relationships that we called genuine causal influences , we now consider an entire dag as one unit which ought to fit the data at hand. Problem Given a list M of conditional independence statements ranging over a set of variables U it is required to decide whether there exists a directed acyclic graph (dag) D that is consistent with M. Our analysis will focus on lists that are closed un- der the graphoid axioms (see Appendix for definition). Section 5 will discuss possible extensions to lists which are not closed. The criterion for dag equivalence is given in Corol- lary 3.2. It follows from Frydenberg's analysis of chain graphs, which applies to strictly positive distribu- tions. The more direct analysis of Verma and Pearl [Verma and Pearl, 1990] renders the criterion applicable to arbitrary distributions, as well as to non-probabilistic de- pendencies of the graphoid type [Pearl and Paz, 1986].