In the current work we investigate the relationship between the classical distribution semantics and causal semantics for probabilistic logic programming. We first give an infinite family of programs yielding the same distribution. Therefore, we deduce that unlike in classical causal structure discovery, in the relational case it is not possible to build a finite search space of causal explanations for an observed distribution. Finally, this article develops a procedure to verify the causal content of a probabilistic logic program, whose structure is obtained from observations.
_ℎ( ) ← (, 1), (1, 2), ..., (− 1, ), () Further, we write __ℎ() if no such path exists, i.e. __ℎ( ) ← ¬ _ℎ( ).
to two Boolean random variables () and (). We consider the following probabilistic logic program:
P := ⎪⎧() : ← _ℎ() ⎪ ⎪⎪⎨() ← (), _ℎ() ⎪() : ← __ℎ() ⎪ ⎪ ⎪⎩() ← (), __ℎ() , An easy calculation shows that all the programs P yield the same distribution of the random variables () and (), where ranges over the nodes of the fixed directed graph . However, for a fixed ∈ N the program P describes a causal mechanism, in which for every node in we find that () is a cause of () unless _ℎ() holds. On the other hand () is a cause of () if we find _ℎ() in . Hence, all the P represent diferent causal structures.
Furthermore, assume that we are given data sampled from the distribution of (_) and (_).
Moreover, a structure learning algorithm like slipcover [
Therefore, unlike the situation in classical causal structure discovery in probabilistic logic programming it is in general impossible to compute the search space of all causal explainations for an observed distribution. Hence, given a probabilistic logic program, whose structure has been derived from observational data, the best one can do is to verify its causal content. The aim of this contribution is to propose a procedure for this verification task.
In Section 2 we begin by recalling Pearl’s functional causal models and their relations to causal Bayesian networks. Further, we give a brief overview over the theory of causal structure discovery for causal Bayesian networks. Finally, we introduce a semantics for probabilistic logic programs in terms of functional causal models, which allows us to ground a given program to a causal Bayesian network. The main idea of our work in Section 3 is then to lift the indistinguishability statement for causal Bayesian networks, Theorem 5, to probabilistic logic programming in order to accomplish our verification task.
We begin with recalling Pearl’s theory of causality. Further, we establish a semantics for probabilistic logic programs that allows us to reason about causal relationships in those programs. Note that in the following we use to denote probabilities of random variables.
Let us recall the definition of a functional causal model [2, 1.4.1]: Definition 1 (Functional Causal Model). A functional causal model or causal model ℳ on a set of variables V is a system of equations that consists of one defining equation of the form := (Pa(), Error()) for each variable ∈ V. Here the parents Pa() ⊆ V of form a subset of the set of variables V, the error term Error() of is a vector of random variables Analogously, a country is corrupt (denoted ()) with probability , i.e. (, ) := 1(, ) with (1(, )) :=
() := 2() with (2()) := .
If a country 1 needs a product and does not produce , but 2 does, then with probability the country 1 imports from 2, denoted by (1, 2), i.e.
(1, 2) :=
(1, ) ∧ 3(1, 2, ) with (3(1, 2, )) := . and is a function defining in terms of the parents Pa() and the error term Error() of .
To illustrate Definition 1 we introduce the following example: Example 1. Assume we are given a database of countries. Further, we know which products are produced in country denoted by (, ). For each product and each country there is a probability such that country needs the product , denoted by (, ). This is reflected in the following equation: (1) (2) (3) (4) (5) ⋁︁ ¬(1,) (2,)
⋁︁ 1 country Further, if a country 1 imports from a country 2, we observe economic growth in 2, denoted (2) with probability , i.e.
(2) :=
(1, 2) ∧ 4(1, 2) with (4(1, 2)) := . Finally, if we find economic growth in country and is not corrupt, the living standard rises in , denoted by (), with probability , i.e.
() := () ∧ (¬()) ∧ 5() with (5()) := .
The equations of the form (1), (2), (3), (4) and (5) yield a functional causal model ℳ.
Next, we note that causal models do not only support queries about conditional and unconditional probabilities. They support two other more general query types, namely determining the efect of interventions and counterfactuals. Here, we focus on the treatment of external interventions. 2.1.1. Predicting the Efect of Interventions
X := {1, ..., } ⊆ V together with a vector of possible values x := (1, ..., ). To calculate the efect of setting the variables in X to the values specified by x we replace the equations for in ℳ by := for all 1 ≤ ≤ and calculate the desired probabilities. The resulting probability distribution is then denoted by (_| do(X = x)) [2, §1.4.3].
Example 2. If a commission roots out corruption in country , we can model this intervention by replacing equation (4) for in the causal model ℳ of Example 1 with () := .
We briefly recall the theory of Bayesian networks, a widespread representation for probability distributions. We compare them with the functional causal models of 2.1 and obtain a causal semantics for Bayesian networks, i.e. we discuss how to determine the efect of an intervention from a Bayesian networks structure.
We begin by recalling the definition of a Bayesian network: Definition 2 (Bayesian Network). A Bayesian network on a set of random variables V consists of a directed acyclic graph on V and the conditional probability distributions (| Pa()) of the random variables ∈ V conditioned on the set Pa() of their parents in the graph . It gives rise to a probability distribution on V = {1, ..., } by setting (1 = 1, ..., = ) = ∏︁ ( = | pa()) , =1 where pa() := { = | ∈ Pa()}.
We proceed by recalling the relation between Bayesian networks and causal models. Definition 3 (Acyclic & Markovian Causal Models). For each causal model ℳ on V we define the causal diagram graph(ℳ) to be the directed graph on V, which is given by drawing an arrow → if and only if ∈ Pa( ). Further, we call ℳ an acyclic causal model if its causal diagram graph(ℳ) is a directed acyclic graph. Finally, an acyclic causal model is said to be Markovian if the error terms Error() are mutually independent for all ∈ V.
The next theorem describes how causal models and Bayesian networks are related to each other [2, 1.4.2]: Theorem 1. Every Markovian causal model ℳ gives rise to a probability distribution that can be stored in a Bayesian network ℬ(ℳ) on its causal diagram.
corresponding to a Markovian causal model ℳ. To calculate the efect of setting X := {1, ..., } to x := (1, ..., ) one can modify ℬ(ℳ) by adjusting the conditional distributions (| Pa()) to (| pa()) = , , where , denotes the Kronecker delta. The resulting structure is then called the causal Bayesian network ℬ(ℳ) [2, §1.3]. In other words a causal Bayesian network is a Bayesian network that supports the calculation of efects of interventions. Example 3. Assume that the error terms 1(_, _), 2(_), 3(_, _, _), 4(_, _) and 5(_) are mutually independent, i.e. the causal model ℳ of Example 1 is Markovian. Hence, for three countries 1, 2, 3 and one product with (2, ) and not (, ) for = 1, 2. We obtain by Theorem 1 that omitting isolated points the resulting distribution can be stored in a causal Bayesian network on the graph (3, ) (1, ) (3, 2)
(2) (1, 2) (2) (2) .
Finally, we state a modularity result for causal models, whose proof is given in the Appendix:
Theorem 2 (Modularity of Causal Models). Let ℳ1 and ℳ2 be functional causal models that
induce the same distribution on the set of variables V and let ∈ V be a variable.
Furthermore, let us assume that the set Pa() of the parents of coincide for both causal diagrams
graph(ℳ1) and graph(ℳ2). If we construct the causal model ℳ3 by exchanging the defining
equation for in ℳ1 by the defining equation for in ℳ2, we obtain that the causal Bayesian
networks ℬ(ℳ1) and ℬ(ℳ3) coincide.
2.2.1. d-Separation
The graph underlying a Bayesian network gives rise to a correct conditional independence
oracle in the following way [
Further, let Z be a set of nodes. A d-connecting path := 1 − ... − is an undirected path in such that each non-collider of the path does not lie in Z and such that for every collider at of the path there exists a directed path from to a node in Z.
Moreover, we say that Z d-connects two nodes and if there exists a d-connecting path between and with respect to Z. Otherwise, we say that Z d-separates and . Finally, two sets of nodes A and B are said to be d-separated by Z if Z d-separates and for every ∈ A and every ∈ B. Otherwise, the sets A and B are d-connected by Z.
Remark 1. The term “d-connected” is a shorthand for “directionally connected” [
Note that in general d-separation does not yield a complete independence oracle [5, 1.4]. This motivates the following definition: Definition 5 (Causal Faithfulness). Let be a distribution on a set of random variables V and let be a directed acyclic graph on theses random variables V. We say that the distribution is (causally) faithful to the graph in the case where two random variables , ∈ V are conditionally independent with respect to a subset of random variables Z ⊆ V if and only if and are d-separated by Z in .
However, the following theorem shows that faithfulness holds for almost all discrete Bayesian
networks [
For an in depth discussion of causal faithfulness we refer the reader to [
More precisely, we want to find all possible causal explanations for the observed distribution.
We consider this as an inverse problem and to tackle this inverse problem we assume that the
causal Bayesian network that generated our data satisfies the causal faithfulness assumption of
Definition 5. In the light of Theorem 4 this doesn’t seem to be too restrictive. Furthermore, the
following fact is known [
Theorem 5 forms the theoretical basis for causal structure discovery algorithms such as the
PC-algorithm [
Example 4. It is easy to see that in Example 3 the causal relationship between (_, _) and (_, _) cannot by identified.
Let us fix a query language, i.e. a language Q ⊇ L ⊇ E in three parts with an extensional vocabulary E and a logical vocabulary L. Here Q is a finite multisorted relational vocabulary, i.e. it consists of a finite set of sorts, a finite set of relation symbols and a finite set of constants in those sorts, as well as a countably infinite set of variables in every sort. For every variable or constant we will denote its sort by s(). Further, L is a subvocabulary of Q that contains all of the variables and constants of Q as well as a (possibly empty) subset of the relation symbols of Q. Moreover, E is a subvocabulary of L that satisfies the same properties with respect to L as L does with respect to Q.
Example 5. In order to model Example 1 we need two sorts: and . Further, we model (_), (_, _), (_, _), (_) and (_) as random predicates and (_, _) as an external predicate. Later, we will also see an example for an internal predicate.
As usual, an atom is an expression of the form (1, . . . , ), where is a relation symbol and 1 to are constants or variables of the correct sorts and a literal is an expression of the form or ¬ for an atom . It is called a external atom or literal if is in E, logical atom or literal if is in L, internal atom or literal if lies in L ∖ E and a random atom or literal if is in Q ∖ L. A literal of the form is called positive and a literal of the form ¬ is called negative. Moreover, we will use the operator var(_) to refer to the variables in an expression.
The logical vocabulary will be used to formulate constraints and conditions for our probabilistic logic program. The purpose of a probabilistic logic program, however, is to define distributions for the random variables, determined by the language Q. This is done by so called random clauses, i.e. LPAD-clauses with one random atom in the head.
Definition 6 (Random Clause). A random clause is an expression of the form : () ←
1, ..., , 1, ..., , where := efect( ) is a random atom, called the efect of , causes() := {1, ..., } is a finite set of random literals, called the causes of , cond() := {1, ..., } is a finite set of logical atoms, called the condition of and () ∈ (0, 1] is a number called the probability of . In this case we also denote the random clause by efect( ) : () ←
causes() ∪ cond().
Having established the necessary syntax, we introduce the corresponding semantics. The semantics of logical expressions are given in a straightforward way; we just want to highlight the unique names assumption in our definition of a structure:
An L-structure Λ consists of a sort universe sΛ for every sort s, an element of the corresponding sort universe for every constant in L, such that two diferent constants are mapped to diferent elements , and a relation among the corresponding sort universes for every relation in L.
Whether a logical formula is satisfied by a given L-structure (under an interpretation of its free variables) is determined by the usual rules of first-order logic. Finally, note that the semantics of external expressions is defined analogously.
Lifted Programs We start with the definition of a lifted program: Definition 7 (Lifted Program & Program Structure). A (lifted) program P := (R, I, C) is a triple that consists of a finite set of normal clauses I of the form ← 1, ..., with logical literals 1, ..., and an internal atom , integrity constraints C of the form ⊥← 1, ..., for logical literals with 1 ≤ ≤ , as well as a finite set of random clauses R.
We call C the constraints, I the internal part and R the random part of P. Further, we say that P is stratified if its internal part I is a stratified set of normal clauses.
Example 6. We model the causal mechanism in Example 1 by a program P, given by the random part: (, ) : () : (1, 2) : ← (1, ), _(1, ), (2, ) (2) : ← (1), (2) () : ← (), ¬() and the internal part: _(, ) ← ¬ (, ) for an internal predicate _(_, _). Note that the database ℰ described in Example 3 yields an external database for P. Notation 1. Let P := (R, I, C) be a stratified program and let ℰ be an E-structure. In our setting we may w.l.o.g. assume that ℰ is a Herbrand model of an alphabet E* , extending the external alphabet E by constants. Further, denote by L* and Q* the extension of the languages L and Q by the new constants in E* . We write ℰ I := { ground atom of L* : I ∪ ℰ |= } for the minimal Herbrand model of I ∪ ℰ , which is the result of applying the stratified datalog program I to ℰ .
An E-structure ℰ is said to be an external database for the program P if it satisfies all integrity constraints in C, i.e. if ℰ I |= C. A ground variable is a ground random atom := (1, ..., ) of Q* . Finally, we write (ℰ ) for the set of all ground variables.
The term ground variable indicates that we expect to become a proper random variable under our semantics. From now on we will assume every program to be stratified. Definition 8 (FCM-Semantics of lifted Programs). Let P := (R, I, C) be a program and let ℰ be an external database for P. The grounding Pℰ of the program P with respect to ℰ is the Boolean functional causal model on the set of ground variables (ℰ ) given by the following defining equation for every ground variable ∈ (ℰ ): :=
⋁︁ ∈R(P) interpretation on var()
effect() = (ℰI, )|=cond() ⎛ ⎝
⋀︁ ∈causes()
⎞ ∧ (, )⎠ Here, the error term (, ) is a distinct Boolean random variable with the distribution ( (, )) = () for every random clause ∈ R and every variable interpretation on var(). Besides, the error terms (, ) are assumed to be mutually independent.
Example 7. As intended, the causal model ℳ of Example 1 yields the semantics of the program P in Example 6 with respect to the described database ℰ .
Definition 9 (Ground Graph & Acyclicity). Let ℰ be an external database for the program P := (R, I, C). Then the ground graph Graphℰ (P) is the directed graph on the set of ground variables (ℰ ) with an edge 1 → 2 if and only if there exists a random clause ∈ R, a cause ∈ causes() and a variable interpretation on var() such that (︀ ℰ I, )︀ |= cond(), ∈ {1, ¬1} and such that efect( ) = 2. In this case we say that the edge 2 ← 1 is induced by . Moreover, we call P an acyclic program if Graphℰ (P) is a directed acyclic graph for every external database ℰ .
Example 8. The graph in Example 3 is the ground graph of the program P in Example 6 with respect to the described database ℰ . Further, it is easy to see that P yields an acyclic program.
From now on we assume every program P := (R, I, C) to be acyclic. Then for every external database ℰ the grounding Pℰ yields unique expressions for every ground variable ∈ (ℰ ) in terms of the error terms (, ). Hence, it induces a unique probability distribution on (ℰ ). We will show in a forthcoming paper that this distribution coincides with the distribution induced by the LPAD-program P ∪ ℰ via the distribution semantics [10, Chapter 1 §2.1]. All in all Definition 7 yields a generalization of the standard semantics for acyclic LPAD-programs with interesting properties regarding causation. Further, since we observe that Graphℰ (P) is the causal diagram of Pℰ , we obtain: Proposition 1. Let P := (R, I, C) be a program. For every external database ℰ the grounding Pℰ yields a distribution, which can be stored in a Boolean Bayesian network on the ground graph Graphℰ (P). This is also the causal Bayesian network corresponding to the functional causal model Pℰ .
semantics of P with respect to ℰ . In our future paper we will also show that our semantics is
consistent with CP-logic [
The proofs of all further statements can be found in the proof appendix. We now return to the task of verifying the causal content of a probabilistic logic program whose structure was derived from observational data. More formally, we investigate the following situation: Problem 1. Suppose we are given a query alphabet Q ⊇ L ⊇ E, a stratified datalog program I, I = C. Further, assume we are given a set of integrity constraints C and an E-structure ℰ with ℰ | data, which is sampled from a functional causal model P˜ℰ , where P˜ = (R˜ , I, C) is a program in the query alphabet Q.
From a structure learning algorithm like slipcover [
As we are mainly interested in the causal Bayesian network semantics of the program P˜ we introduce the following equivalence relation: Definition 10. Let ℰ be an external database for the programs P1 = (R1, I, C) and P2 = (R2, I, C). We call P1 and P2 intervention equivalent on ℰ if they induce the same causal Bayesian network semantics on ℰ , i.e. if the causal Bayesian networks ℬ (P1, ℰ ) and ℬ (P2, ℰ ) coincide. Note that this is the case if and only if the causal models P1ℰ and P2ℰ predict the same efects for every intervention.
To apply Theorem 5, we need to make the following assumption.
Definition 11 (Faithful Programs). Let P := (R, I, C) be a program and let ℰ be an external database. We say that P is faithful for ℰ if the distribution induced by Pℰ is faithful to the ground graph Graphℰ (P). We say that two programs P1 and P2 are faithfully indistinguishable on ℰ if P1ℰ and P2ℰ induce the same distribution and if P1 and P2 are faithful for ℰ .
Assumption 1 (Faithfulness). In the situation of Problem 1 the programs P˜ and P are faithfully indistinguishable on the external database ℰ .
With our notion of faithfulness in Definition 11, Theorem 5 translates to the following statement about faithfully indistinguishable programs: Theorem 6. Let ℰ be an external database for the programs P1 = (R1, I, C) and P2 = (R2, I, C). If P1 and P2 are faithfully indistinguishable on ℰ , the ground graphs Graphℰ (P1) and Graphℰ (P2) share the same adjacencies and the same unshielded colliders.
Hence, Assumption 1 yields that the ground graphs Graphℰ (P) and Graphℰ (P˜) yield the same adjacencies and the same unshielded colliders. To reason about colliders instead of unshielded colliders we restrict ourselves to triangle free programs.
Definition 12 (Triangle Free Program Structures). We call a program P triangle free if for every external database ℰ the skeleton of the ground graph Graphℰ (P) does not contain any triangles. Proposition 2. For every triangle free program P := (R, I, C) and every external database ℰ every collider in the ground graph Graphℰ (P) is unshielded. □ Assumption 2. The programs P and P˜ in Problem 1 are triangle free.
If in Problem 1 every edge of the ground graph Graphℰ (P) is involved in a collider, Theorem 6 and Proposition 2 imply that every program faithfully indistinguishable from P yields the same ground graph on ℰ . Due to the following consequence of Theorem 2 the causal Bayesian network semantics also coincide in this case.
Lemma 1. Let P1 := (R1, I, C) and P2 := (R2, I, C) be programs such that the functional causal models P1ℰ and P2ℰ induce the same distribution for an external database ℰ . In this case P1 and P2 are intervention equivalent on ℰ if the ground graphs Graphℰ (P1) and Graphℰ (P2) coincide. □
Assertions i)-iii) of the following lemma list the conditions under which a given random
clause induces a collider in the ground graph of an external database ℰ . Moreover, the symmetry
represented by the query alphabet Q implies that all edges induced by a random clause satisfying
Assertion iv) also appear in every ground graph of a program faithfully indistinguishable
from P. Note that Assertion iv) yields an analogue of the relational orientation rule in the
RPC-Algorithm [
Lemma 2. Let P1 := (R1, I, C) and P2 := (R2, I, C) be triangle free programs that are faithfully indistinguishable on the external database ℰ . Let ∈ R1 be a random clause that induces an edge → efect( ) in the ground graph Graphℰ (P1) for an interpretation on var(). Moreover, assume that the random clause ∈ R1 and the interpretation on var() satisfy one of the following assertions: i) We find two causes 1, 2 ∈ causes() such that 1 ̸= 2. ii) There exists a second random clause ′ ∈ R1 together with an interpretation ′ on var(′) satisfying (ℰ I, ′) |= cond(′) such that we find efect( ) = efect( ′) ′ and ̸= (′) ′ for two causes ∈ causes() and ′ ∈ causes(′). iii) There exists a cause ∈ causes() together with a variable ∈ var() such that ̸∈ var(efect( )). Moreover, we find another interpretation ′ on var() satisfying (ℰ I, ′) |= cond(), efect( ) = efect( ) ′ and () ̸= ′(). iv) There is only one cause ∈ causes() in and there exists a variable ∈ var(efect( )) such that ̸∈ var(). Moreover, there exists an interpretation ′ on var() of the same type in L as , i.e. makes an existential formula true if and only if ′ does, such that = ′ and such that () ̸= ′().
Then the edge → efect( ) appears in the ground graph Graphℰ (P2) as well.
Combining Theorem 6, Lemma 1 and Lemma 2 we get the following corollary: Theorem 7. Let P1 := (R1, I, C) and P2 := (R2, I, C) be triangle free programs that are faithfully indistinguishable on the external database ℰ . Further, assume that every random clause ∈ R1 with causes() ̸= ∅ and every interpretation on var() with (ℰ , ) |= cond() satisfies at least one of assertions i)-iv) in Lemma 2. In this case P1 and P2 are intervention equivalent on the external database ℰ . □ Example 9. Assume we obtained the program P as described in Problem 1 and Assumption 1 from a structure learning algorithm on the database ℰ in Example 8. In this case we cannot verify the causal content of P! However, if we would add a country producing or a country not producing , the program P would be guaranteed to be intervention equivalent to P˜ as desired.
Theorem 7 yields a partial answer for Problem 1 if we want to predict efects of external interventions in the functional causal model P˜ℰ . Next, we want to generalize our result to other external databases. To this aim we introduce the following assumption: Assumption 3 (Generalization). In Problem 1 we additionally assume that the query alphabet Q contains no constants and that the programs P˜ and P are faithfully indistinguishable on every external database ℰ ′.
Next, we modify Assertions i),iii) and iv) of Lemma 2 to guarantee that under Assumption 3 every edge in the ground graph Graphℰ′ (P) of an arbitrary external database ℰ ′ also occurs in the ground graph Graphℰ′ (P˜): Lemma 3. Let P1 := (R1, I, C) and P2 := (R2, I, C) be triangle free programs that are faithfully indistinguishable on every external database ℰ . Further, assume that no variable appears twice in the head of a clause in I.
Moreover, let ∈ R be a random clause that induces an edge ′ → efect( ) ′ in the ground graph Graphℰ′ (P1) of an external database ℰ ′ for an interpretation ′ on var() in ℰ ′. Furthermore, assume that the random clause ∈ R1 satisfies at least one of the following assertions: i) We find two causes 1, 2 ∈ causes() that are not sharing the same underlying predicate. ii) We find a cause ∈ causes() and a variable ∈ var() such that ̸∈ var(efect( )).
Moreover, and efect( ) do not share the same underlying predicate. iii) We find a cause ∈ causes() and variable ∈ var(efect( )) such that ̸∈ var().
Moreover, and efect( ) do not share the same underlying predicate.
Then we obtain that the edge ′ → efect( ) ′ is contained in the ground graph Graphℰ′ (P2) as well.
The proof of Lemma 3 requires the construction of external databases, in which causes are witnessed by more than one individual. Adding extra individuals is enabled by not having any kind of privileged equality, which is reflected in the following assumption: Assumption 4. In the situation of Problem 1 no variable appears twice in the head of a clause in I.
Finally, we combine Theorem 6, Lemma 3 and Lemma 2: Theorem 8. In the situation of Lemma 3 we assume that every random clause in P1 satisfies one of the Assertions i)-iii). In this case the programs P1 and P2 are intervention equivalent on every external database ℰ . □ Example 10. Assume we obtained the program P as described in Problem 1 and Assumption 3 from a structure discovery algorithm on the database ℰ in Example 8. In this case we can invoke Theorem 8 to see that P and P˜ are intervention equivalent on every external database ℰ ′.
Based on our results we propose the following procedure to verify the causal content of a given probabilistic logic program.
Procedure 1. In the situation of Problem 1 we first check that every random clause of program P and every interpretation on var() in the external database ℰ satisfies one of the Assertions i)-iv) of Lemma 2. In this case we obtain that P˜ and P are intervention equivalent on ℰ under Assumption 2 and Assumption 1. Further, we check for every random clause of P1 whether there is an interpretation on var() in ℰ such that (ℰ I, ) |= cond().
Next, we use this result to justify Assumption 3, i.e. to justify that no random clause is verified on the basis of a collider not observed in the ground graph Graphℰ (P). Finally, we check whether every random clause in P satisfies one of the Assertions i)-iii) of Lemma 3 and invoke Theorem 8 to conclude that under Assumption 4 the programs P and P˜ are intervention equivalent on every external database ℰ ′ as desired.
We first illustrated that in the lifted case, the search space of causal explanations for an observed distribution can be infinite. Hence, there is no straightforward generalization of causal structure discovery here. However, we developed a procedure to verify the causal content of an acyclic, stratified, triangle free probabilistic logic program, whose structure was determined by observational data. Intuitively, we argued that we can verify every clause that observably implies only colliders in the associated ground graphs.
In future we would like to remove the assumption of triangle freeness. Furthermore, we want to verify pairs of clauses that induce colliders in the ground graph for every external database. To obtain a complete result we also aim to incorporate the orientation rules of the PC-algorithm into our framework.
The research leading to this publication was supported by LMUexcellent, funded by the Federal Ministry of Education and Research (BMBF) and the Free State of Bavaria under the Excellence Strategy of the Federal Government and the Länder.
Proof of Theorem 2. Recall Definition 3 to see that has the same parents in the causal diagrams graph(ℳ2) and graph(ℳ3) and that every other node ̸= has the same parents in graph(ℳ3) as in graph(ℳ1). Furthermore, apply the assumption to obtain that the causal diagram graph(ℳ3) coincides with graph(ℳ1).
and ℬ(ℳ3) coincide as well. As ℳ1 and ℳ2 induce the same distribution, we find that the parameters for coincide in the causal Bayesian networks ℬ(ℳ1) and ℬ(ℳ2). To conclude we recall that the parameters of every node ∈ V in ℬ(ℳ1/2/3) can be computed from the corresponding defining equation by intervening on the set of parents Pa( ) [2, Theorem 3.3.2].
Proof of Theorem 6. Assume that the functional causal models P1ℰ and P2ℰ induce the same distribution . Further, assume that both programs P1 and P2 are faithful for ℰ . In this case by Definition 11 we see that the ground graphs Graphℰ (P1) and Graphℰ (P2) are both faithful to the distribution . Hence, we obtain the desired result from Theorem 5.
Proof of Lemma 2. If satisfies one of the assertions i)-iii), it is easy to see that the edge → efect( ) is involved in a collider at efect( ) and the claim follows since by Theorem 6 and Proposition 2 the ground graphs Graphℰ (P1) and Graphℰ (P2) share the same colliders.
Next, assume that and satisfy iv). By assumption there exists an interpretation ′ on var() of the same type in L as such that = ′ and such that () ̸= ′() for a variable ∈ var(efect( )). As and ′ have the same type in L we find that the edges − efect( ) and − efect( ) ′ also share the same orientation in the ground graph Graphℰ (P2). If they were both pointing to , we would observe a collider in Graphℰ (P2) not contained Graphℰ (P2). This is a contradiction to Theorem 6 and Proposition 2 and the claim follows. □
To prove Lemma 3 we need the following lemma: Lemma 4. Let P = (R, I, C) be a lifted program such that no variable appears twice in the head of a clause in I and let ℰ be an external database. Assume the following holds for every external atom = (1, ..., ): (* ) Let be a subset of {1, . . . , } and let be an interpretation on var() with () = if and only if ∈ . Moreover, let ′ be an individual in ℰ and let ′ be the interpretation on var(), which is given by setting () = ′ for ∈ and ′( ) = ( ) for ̸∈ . In this case (ℰ , ) |= if and only if (ℰ , ′) |= .
Then (* ) also holds for every internal atom .
on the iteration of to show that for every ∈ N we have ( (ℰ ), ) |= if and only if ( (ℰ ), ′) |= .
Note that the case = 0 follows directly from the assumption of the lemma. So assume that ( +1(ℰ ), ) |= . If we find ( +1(ℰ ), ′) |= , we are finished by the induction hypothesis. Hence, let us assume that ( +1(ℰ ), ′) ̸|= .
on var() such that = and such that ( (ℰ ), ) |= {1, ..., }. By the assumption of the lemma, = (1, . . . , ) where all 1, . . . , are distinct. Further, we know that () = () = for all ∈ . Define ′ by setting ′() = ′ for ∈ and ′() = () for all other variables on which is defined. Then the restrictions of and ′ to the variables in any , 1 ≤ ≤ , satisfies the requirements of the induction hypothesis. Hence, ( (ℰ ), ′) |= {1, ..., } and thus ( +1(ℰ ), ′) |= . Note that ′ = ′ by construction. Therefore, ( +1(ℰ ), ′) |= as required.
Proof of Lemma 3. We distinguish the following cases: Case. The clause ∈ R1 satisfies i).
In this case the desired result follows immediately from Lemma 2.
Case. The clause ∈ R1 satisfies ii).
By Theorem 6 we find an edge ′ − efect( ) ′ in the ground graph Graphℰ′ (P2). This edge needs now to be induced by a random clause ˜ ∈ R2, i.e. we obtain that ˜ ′ − efect( ) ′ = ˜ → efect( ˜)˜.
Further, we may assume w.l.o.g. that the clauses and ˜ don’t share common variables. Hence, we obtain an interpretation on var() ∪ var(˜) such that
((ℰ ′)I, ) |= edge_eq ∪ cond() ∪ cond(˜), where edge_eq denotes the set
{︁(˜ = efect( ) ∧ = efect( ˜)) ∨ (efect( ˜)) = efect( ) ∧ = ˜)}︁ .
̸∈ var(efect( )). Furthermore, choose a variable ′ not contained in var()∪var(˜).
atom (1, ..., (), ..., ) in ℰ ′ the ground atom (1, ..., (′), ..., ). In this way we end up with an external database ℰ ′′ and an interpretation on var() ∪ var(˜) ∪ {′}. Further, Lemma 4 yields that the following set is satisfied with respect to and (ℰ ′′)I: (edge_eq ∪ cond()) [′/] ∪ edge_eq ∪ cond() ∪ cond(˜) ∪ { ̸= ′} Hence, ∈ R1 satisfies the Assertion iii) of Lemma 2 with respect to the interpretation and the external database ℰ ′′ and the edge − efect( ) is induced by ˜ in Graphℰ′′ (P2) as well. From Lemma 2 we further obtain that the orientation of the edge − efect( ) in Graphℰ′′ (P2) is also given by → efect( ) . Hence, we obtain from Definition 9 that the formula ˜ = efect( ) ∧ = efect( ˜) is not satisfiable with respect to I ∪ C as and efect( ) do not share the same underlying random predicate. However, this means that (ℰ I, ′) |= efect( ˜) = efect( ) ∧ = ˜ and the desired result follows. Case. The clause ∈ R1 and the interpretation 2 satisfy iii) of Lemma 2.
This can be proven analogously to the previous case.