We describe an approach to learning causal models that leverages temporal information. We posit the existence of a graphical description of a causal process that generates observations through time. We explore assumptions connecting the graphical description with the statistical process and what one can infer about the causal structure of the process under these assumptions.
Data that measure the temporal dynamics of systems is pervasive. The goal of this paper is to describe an approach to the development of a sound approach to causal inference for dynamic systems. One of the popular extant approaches is Granger causality (Granger 1969) which fails to be sound in the presence of latent variables. Granger causality is typically applied in discrete-time continuous valued time-series. Roughly speaking, in a multivariate time series X a set of variables are the Granger-causes of Xj if the historical values of this set of variables (including Xj ) are necessary and su cient for optimal prediction. Unfortunately a variable deemed a Granger-cause can arise due to either a latent common cause or as a result of a direct causal relationship and thus the approach cannot be used to determine causal relationships if one does not exclude the possibility of latent variables.
In this paper, we explore how one can leverage the assumption that causes must precede e ects to inform causal conclusions drawn from observations of a temporal statistical process. The approach taken here is similar to the approach developed by Verma and Pearl (1990) and Spirtes, Glymour, and Scheines (2001) for atemporal causal discovery. One key ingredient in our approach is a new asymmetric graphical separation criterion for directed (possibly cyclic) graphs called *separation which plays an analogous role as d-separation in the work of Verma and Pearl (1990) and Spirtes, Glymour, and Scheines (2001). Another key ingredient is the process independence statement that plays an analogous role to the independence statement. Conceptually, we assume that we can test whether a process independence statements about observable quantities holds by observing the process and that these observation provide insight into the causal structure governing the process. In particular, we posit the existence of a graphical description of a causal process and make assumptions that connect *separation with observable process independence statements. We explore what can be inferred about the causal structure of the process under various observability assumptions. While the ultimate goal is to create a sound and complete method for causal inference for observations from a stochastic dynamic system, this paper represents some initial steps towards this ultimate goal. In particular, the results in Section 3.2 can be viewed su cient conditions for Granger causality and, in Section 3.3, we present su cient conditions under which we can make sound inferences about causal relationships including the existence of causal relationships and the existence and non-existence of latent common causal relationships. As presented in Section 3, our causal discovery algorithm assumes the existence of an oracle for process independence statements. Our approach of abstracting away the details of how one connects process independence statements with particular statistical processes allows us to simultaneously make progress on the causal discovery problem for multiple distinct statistical processes such as marked point processes, Gaussian processes and dynamic Bayesian networks. In Section 4, we discuss two particular statistical processes and their associated process independence statements. In Section 5, we discuss some related work and open research questions.
We use G = hL; E i to denote a directed graph where L is a set of vertices and E hL Li is a set of edges represented as ordered pairs. We write a ! b if ha; bi 2 E and say that a is a parent of b and b is the child of a. Note that, in addition to allowing cycles, we also allow that a vertex can be its own parent and child (i.e., a self-edge a ! a). We use the shorthand a $ b to indicate that a ! b and b ! a.
A path in G is a sequence hl1; : : : ; lni where there is an edge between successive pairs of vertices in G. The length of a path p = hl1; : : : ; lni is jpj = n and a path p is termed a trivial path if jpj = 1. A vertex li on path p = hl1; : : : ; lni is a collider on p if li 1 ! li and li li+1 and a non-collider otherwise. A directed path in graph G = hL; E i is a sequence of vertices hl1; : : : ; lni such that hli; li+1i 2 E . The source of a directed path is the rst vertex in the path. We denote the set of ancestors for a set A by An(A). The ancestor relation is re exive and thus A An(A).
We de ne a graph separation criterion called d*separation for directed graphs which is an extension of d-separation (Pearl 1988). An extension of dseparation is required as a pure vertex separation criterion like d-separation cannot separate a vertex from itself which is required to appropriately handle selfedges in directed graphs. A path p d*connects vertices a and b given the set of vertices C in graph G if every collider on p is in An(C) and every non-collider on p is not in C. For sets of vertices A; B; C L where A \ C = ; we say that B is d*separated from A by C in graph G if and only if there does not exist a non-trivial d*connecting path between some a 2 A and some b 2 B given C in G.
There are two key di erences from Pearl's d-separation that allow us to appropriately handle cyclic directed graphs. First, we restrict d*separation statements to sets in which A \ C is the empty set but allow the sets A and B to overlap. Second, d*connecting paths must be non-trivial. These modi cations enable us to use d*separation statements to distinguish between graphs in which there is a self-edge (a ! a) and one in which there is not.
We use directed graphs to represent temporal statistical processes. We associate the vertices L with a set of possible observation types (i.e., things that can happen). The edges denote potential dependencies between observations and the absence of a directed edge from observation type a to observation type b indicates that the process that generates observations of type b does not directly depend on the history of observations of type a. Analogous to the use of dseparation for directed acyclic graphs, we would like a graphical separation criterion for directed graphs to answer questions about how past observations in uence future observations. Due in part to the fact that a directed graph does not explicitly encode temporal information we cannot simply apply d*separation on the directed graph. Instead, we de ne *separation which extends the graphical -separation of Didelez (2008) to handle self-edges. For sets A; B; C L where A \ C = ; we say that that B is *separated from A given C (or simply (A; C; B)) in G if an only if B is d-separated from A given C in the Bhistorical dependency graph GB where GB = L; E B and E B = E nfhb; ai 2 E jb 2 B; a 6= bg. Note that *separation is not symmetric in the rst and third arguments due to the use of the graph GB. 3
Our aim is to connect statistical processes with causal graphs and to learn the causal graph governing a system of observed events. We assume that there is a statistical process governing what and when events happen. We denote a statistical process for a set of observation types L by PL. We also assume that we can observe the process to determine the whether process independence statements hold. We will write P I(A; C; B) to indicate that the process associated with observations of type B does not depend on the history of observations of type A given the history of observations of type C in a given process PL (where A \ C = ;). We write :P I(A; C; B) if this is not the case. We call such statements process independence statements. We note that process independence statements need not correspond to statistical independence statements and, as with *separation, there is no expectation that such process independence statements ought to be symmetric. In this section, we assume the existence of a process independence oracle for the relevant statistical process. In Section 4, we discuss particular statistical processes and the problem of testing process independence statements for those processes. A process PL satis es the Causal Factorization Assumption with respect to a causal process graph G = hL; E i if and only if for all A; B; C L where A\B = ; it is the case that (A; B; C) ) P I(A; B; C) A process PL satis es the Causal Dependence Assumption with respect to a causal process graph G = hL; E i if and only if for all A; B; C L where A \ B = ; it is the case that P I(A; B; C) ) (A; B; C) The Causal Analysis (CA) Algorithm (Algorithm 1) uses a process independence oracle to construct a directed graph. We use lG to denote the parents of l in graph G and jBj to denote the cardinality of the set B. The basic idea is to use process independence statements to remove edges from an initially complete graph. This algorithm is analogous to the PC Algorithm of Spirtes, Glymour and Scheines (2001) but does not have an orientation phase.
Note that the output of the CA algorithm is a directed graph and that any edges presented do not necessarily indicate a causal relationship. In the remainder of this section we explore the interpretation of the output of the CA algorithm under various assumptions. Recall that a $ b simply indicates that a ! b and b ! a and not the existence of a latent common cause. Input: A set of events L and a process PL Output: A directed graph G Let G = hL; E i be a complete directed graph.; foreach l 2 L do
Let n = 0; foreach l0 2 lG do foreach B lG n fl0g where jBj = n do if P I(l0; B; l) holds in PL then
E = E n hl0; li end end
Let n = n + 1; end end Return G = hL; E i; Algorithm 1: The Causal Analysis (CA) Algorithm Theorem 1 (Complete Observations). If PL satis es both the causal dependence and factorization assumptions with respect to G then algorithm CA(L; PL) returns G0 = G.
Lemma 1. If PL satis es the causal dependence assumption for G = hL; E i and algorithm CA(L; PL) returns G0 = hL; E 0i then if l0 ! l 2 E then l0 ! l 2 E 0. Lemma 2. If PL satis es both the causal dependence and factorization assumptions for G = hL; E i and algorithm CA(L; PL) returns G0 = hL; E 0i then if l0 ! l 62 E then l0 ! l 62 E 0.
Proof of Theorem 1: The theorem follows from Lemmas 1 and 2. 3.1
Next we consider the case in which some of the event types in the system are not observed. We let O L be the set of observed event types. In this case we will assume that the causal factorization and dependence assumptions hold for a process PL and some causal process graph G. Our causal factorization and dependence assumptions allow us to focus on *separation in G by assuming that the observed process independence statements accurately re ect the *separation statements about G for the observed observation types. In order to understand and interpret the output of the CA algorithm we need to understand the conditions that lead to edges in the nal output. We begin by de ning the concept of vertex blockability relative to a set of observed event types.
We say that a vertex a is b-unblockable relative to O in G if and only if for all C O n fa; bg : (a; C; b) is true of G. Otherwise the vertex is said to be b-blockable relative to O. Note that if b ! b then if b 2 O b is b-unblockable relative to O.
We say that l is a direct cause of l0 relative to O for causal process graph G if and only if there exists a directed path hl1; : : : ; lni where l1 = l and ln = l0 and li 62 O for (1 < i < n). We call the path in the de nition of direct cause a witnessing path that l is a direct cause of l0. We let Db denote the set of observed direct causes of the variable b relative to O, that is, members of O that are direct causes of b relative to O. Example 1. Let E = fa ! c; c ! bg, L = fa; b; cg and O = fa; bg. The vertex a is b-unblockable relative to O for G = hL; E i but the vertex b is a-blockable relative to O. In this example, a is a direct cause of b relative to O in graph G and a ! c ! b is a witnessing path for this fact.
Lemma 3. If l0 is a direct cause of l relative to O in G then l0 is l-unblockable relative to O in G. The following lemma allows us to make causal inferences using the causal analysis algorithm about the absence of a direct causal relationship.
Lemma 4. If PL satis es the causal dependence assumption with respect to G then, in the graph G0 output by CA(O,PL), the set of parents for each event type include all of its direct causes relative to O. In particular, if the algorithm nds that an event type a is not a parent of event type b then a is not a direct cause of b. 3.2
In the section, we restrict the type of unobserved event types which enables us to make strong inferences about the causal structure of a process. In particular we assume causal su ciency which is essentially an assumption that there are no latent confounding processes. A set of event types O L is causally su cient with respect to a graph G = hL; E i if and only if every common cause of l; l0 2 O is in the set of event types
A directed graph G0 = hO; E 0i is causally correct with respect to a graph G = hL; E i if for every edge ha; bi 2 E 0 a is a direct cause of b with respect to O in G. Theorem 2 (Causal Su ciency). If PL satis es both the causal dependence and factorization assumptions for G = hL; E i and O L is causally su cient with respect to G then the graph G0 returned by algorithm CA(O; PL) is causally correct with respect to G and O.
Lemma 5. If PL satis es the causal dependence and factorization assumptions with respect to G and O is causally su cient for G then the output of the CA algorithm removes the edge a ! b if a is not a direct cause of b relative to O. 3.3
We have shown that the CA algorithm can provide causally accurate information under the assumptions of causal su ciency, causal factorization and causal dependence. In this section we consider removing the assumption of causal su ciency.
Example 2. Let E = fa c; c ! bg, L = fa; b; cg and O = fa; bg. The observed event types O are not causally su cient for the graph G = hL; E i. In addition, the CA algorithm fails to provide output that is causally correct. In particular, the CA algorithm yields the graph in which a ! b and b ! a despite the fact that neither is a a cause of b in G nor is b a cause of a.
Our aim is to graphically characterize vertex
separability. We do so using the idea of an inducing path in a
directed graph that was introduced for directed acyclic
graphs by Verma and Pearl (1990). For a pair of
vertices a; b, we de ne Aab = An(fag) [ An(fbg) n fa; bg.
A path p between ha; bi is an inducing path relative to
O if and only if (
Lemma 6. For a directed graph G the following three statements are equivalent: (a) A vertex a is b-unblockable relative to O in graph
G (b) There is an inducing path between a and b relative to O in graph Gb. Note this inducing path must be into b. (c) : (a; O \ Aab; b) in G.
We say that a is a cause of b in G and if there is a directed path from a to b in G.
We aim to nd common features of all graphs that are consistent with the observed pattern of process independence statements. Latent processes, however, can mask the causal nature of the observed pattern of dependencies.
For a pair of vertices a; b and graph G we say that there
is a potential indirect inducing path into b relative to O
if and only if (
Lemma 7. For any set of observed variable O, if a graph has an inducing path between observed variables a; b into b containing another observed variable then the output of the CA algorithm will contain a potential indirect inducing path into b.
Theorem 3 (Su cient Cause). If PL satis es both the causal dependence and factorization assumptions for G = hL; E i then if CA produces G0 with vertices O L for which the subgraph over fa; bg is a ! b and G0 contains no potential inducing path between a; b into b then a is a cause of b in G.
Lemma 8. If PL satis es both the causal dependence and factorization assumptions for G = hL; E i and CA produces G0 with vertices O L for which the subgraph over fa; b; cg is a $ b $ c then if P I(a; ;; c) and P I(c; ;; a) then there is a latent common causes of a; b and a (possibly distinct) latent cause of b; c and b is not a direct cause of c and b is not a direct cause of a. if P I(a; b; c) then there is no latent common causes of b; c, b is a cause of c in G. 4
Our approach to causal discovery through the observation of a dynamic process is applicable to di erent temporal statistical processes. The key connection required is a connection between process independence statements and the observations from a particular statistical process. In this section we consider two distinct statistical processes and discuss process independence for these processes. 4.1
Dynamic Bayesian networks (DBNs) are a popular discrete-time model that can capture temporal dynamics of a statistical process. A DBN is a statistical model of an in nite set of variables indexed by time. A variable Xit denotes the ith variable at time t. We use X = X1; : : : ; Xn to denote the set of variable types in the DBN, that is, a variable with an unspeci ed time component and Xt to denote the set of variables at time t. The DBN speci es the evolution of Xt as a stochastic function of the value of previous variables Xt i (i > 0). In particular, the variable Xt i is a stochastic function of the value of its parents in a graph. The causal process graph associated with a causal DBN is a graph over the variable types of the DBN X where there is an edge Xi ! Xj if there exists a t; i such that there is an edge Xit i ! Xj in the DBN. Thus, the parent relationship of the causal process graph captures the dependence of a variable type on the history of other variable types. Furthermore, process independence statements P I(Xi; C; Xj ) correspond to a set of independence statements of the form I(Xi1; : : : ; Xit 1; XC1 ; : : : ; XCt 1; Xjt). Without further assumptions, testing process independence would be unfeasible but if we focus on stationary processes with nite temporal dependency we can potentially test process independence statements. 4.2
In this section, we de ne Conditional Intensity Models and Graphical Event Models (GEMs) and connect these models with previous work on the class of Piecewise-Constant Conditional Intensity Models and Poisson Networks. We assume that events of di erent types are distinguished by labels l drawn from a nite alphabet L. An event is then composed of a non-negative time-stamp t and a label l. A history is an event sequence h = f(ti; li)gin=1 where 0 < t1 < < tn, and our data is a speci c history denoted by D. Given data D, we de ne the history at time t as h(t; D) = f(ti; li) j (ti; li) 2 D; ti tg. We suppress D from h(t; D) when clear from context and write hi = h(ti 1). By convention t0 = 0. We de ne the ending time t(h) of a history h as the time of the last event in h: t(h) = max(t;l)2h t so that t(hi) = ti 1. A Conditional Intensity Model (CIM) is a set of nonnegative conditional intensity functions indexed by label f l(tjh; )gl2L. The data likelihood for this model is p(Dj ) =
n
Y Y
l2L i=1
l(tijhi; )1l(li)e
l(tijhi; )
(
One of the goals for the research direction described in this paper is the development a sound approach to causal inference for dynamic systems. One of the popular extant approaches is that of Granger causality which fails on this account. This approach is typically applied in a discrete-time continuous valued timeseries and, thus, can be viewed as a dynamic Bayesian network. Roughly speaking, in a multivariate time series X a set of variables are the Granger-causes of Xj if the historical values of this set of variables (including Xj ) are necessary and su cient for optimal prediction. Unfortunately this approach does not appropriately handle latent common causes. In particular, for both of the scenarios described in Lemma 8 it is the case that each of the variables is a Granger cause of its neighbors while this relationships need not be causal as the lemma demonstrates. In fact, it is easy to construct stochastic processes with latent factors which demonstrate that the inferential approach to Granger causality is not sound with respect to causal relations. There has been much work related to causal discovery and the estimation of causal e ects in time-series. As discussed above, the work on Granger causality (Granger 1969) is the most well known. The shortcomings of this approach are also well known (e.g., Eichler 2007) and there has been some work in trying to address these known short comings. For instance, Eichler (2007) proposes a similar approach to the approach described here but di ers in that it allows for the possibility of \simultaneous correlation" which requires the use of an alternative de nition of separation. In addition, while providing de nitions of cause and spurious cause, su cient conditions for the identication of causal relationships are not presented. The work of Entner and Hoyer (2010) considers the problem of causal discovery from time series data using limited dependence vector autoregressive models and the FCI algorithm that uses conditional independence tests to identify the structure. Our approach of using *separation is inspired by the work of Didelez (2008) who de ned -separation and shows the connection between that graphical separation criterion and local independence of marked point processes. Our extension to *separation allows for the appropriate treatment of self-edges which are essential in any self-excitatory or self-inhibitory dynamic process. Another more loosely connected work is that of Eichler and Didelez (2007) that considers the estimation of causal e ects based on an intervention in a time-series.
While the results described in this paper o er hope for developing a methodologically sound approach to causal inference for dynamic systems, there is much work that needs to be done. Here are some of the open research questions.
Non-parametric tests for process independence for various type of temporal statistical processes Soundness and completeness results for *separation analogous to those provided by Pearl (1988), Meek (1995) and Spirtes et al (2001) for d-separation. Note that Didelez (2008) has shown the soundness of -separation for a family of marked point processes related to GEMs.
A representation for equivalence classes of causal graphs with respect to *separation in the case of causal insu ciency (O L) analogous to those developed by Verma and Pearl (1990) and Spirtes et al (2001) that captures the common casual aspects of the set of graphs in the equivalence class.
Thanks to Asela Gunawardana and two anonymous reviewers for their comments on an earlier draft of this paper.