Intervention and Conditioning in Causal Bayesian Networks
Authors: sainyam galhotra
Joseph Halpern
Venue: NeurIPS 2024 poster (2024)
Keywords: causal bayesian networks
interventions
counterfactuals
Primary area: causal_inference

Abstract: Causal models are crucial for understanding complex systems and
identifying causal relationships among variables. Even though causal
models are extremely popular, conditional probability calculation of
formulas involving interventions pose significant challenges.
In case of Causal Bayesian Networks (CBNs), Pearl assumes autonomy 
of mechanisms that determine interventions to calculate a range of
probabilities. We show that by making simple yet
often realistic independence assumptions, it is possible 
to uniquely estimate the probability of an interventional formula (including
the well-studied notions of probability of sufficiency and necessity). 
We discuss when these assumptions are appropriate.
Importantly, in many cases of interest, when the assumptions are appropriate,
these probability estimates can be evaluated using
observational data, which carries immense significance in scenarios
where conducting experiments is impractical or unfeasible.

Intervention and Conditioning in Causal Bayesian Networks
Sainyam Galhotra Computer Science Dept. Cornell University sgêcs. cornell. edu
Joseph Y. Halpern Computer Science Dept. Cornell University halpern@cs. cornell. edu
Abstract
Causal models are crucial for understanding complex systems and identifying causal relationships among variables. Even though causal models are extremely popular, conditional probability calculation of formulas involving interventions pose significant challenges. In case of Causal Bayesian Networks (CBNs), Pearl assumes autonomy of mechanisms that determine interventions to calculate a range of probabilities. We show that by making simple yet often realistic inde- pendence assumptions, it is possible to uniquely estimate the probability of an interventional formula (including the well-studied notions of probability of suffi- ciency and necessity). We discuss when these assumptions are appropriate. Im- portantly, many cases of interest, when the assumptions are appropriate, these probability estimates can be evaluated using observational data, which carries im- mense significance in scenarios where conducting experiments impractical or unfcasible.
Introduction
Causal models play a pivotal role in elucidating the causal relationships among variables. These models facilitate principled approach to understanding how various factors interact and influ- ence each other in complex systems. For instance, in epidemiology, causal models often help us understand the relationship between lifestyle choices and health outcomes (Greenland, Pearl, and Robins 1999); and in economics, they help to analyze the impact of policy changes on market dy- namics (Hicks 1979). These examples underscore the versatility and utility of causal models for providing formal representation of system variables.
Interventions and conditioning are the most fundamental procedures in the application of causal models, useful to examine and analyze causal mechanisms. For example, interventions help ex- plain the outcome of complex ML systems (Galhotra, Pradhan, and Salimi 2021); and in Al-driven healthcare diagnostics, is crucial to discern the effect of a particular intervention (like a change in treatment protocol) patient outcomes (Greenland 1999).
Despite their utility, calculating the probabilities related to interventions and conditioning in tandem presents significant challenges. Indeed, it is not even clear what the semantics of queries involving counterfactuals is. Work in the AI literature has focused on two types of models: functional causal models"] and causal Bayesian networks (Pearl 2000). Both acyclic graphs, where each node is associated with a variable. In a causal model, with each variable Y associated with a non-root node, there is a deterministic (structural) equation, that gives the value of Y as function of the values of its parents; there is also probability on the values of root nodes. In CBN, like in Bayesian network, each variable Y is associated with conditional probability
typically described using directed
Unless specified, in this paper, "causal models" refer "functional causal models".
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

table (cpt), that for each setting of the parents of Y. gives the probability of Y conditional on that setting. In a functional causal model, it is actually straightforward to determine the conditional probability of formulas involving interventions. In CBN, this is far from true. Indeed, recent work of Beckers (2023) has shown that an approach given by Pearl (2000) to calculate these probabilities in a CBN is incorrect. D Pearl also calculates probabilities in a CBN by implicitly reducing the CBN to a family of functional causal models (see, e.g., (Pearl 2000, Theorem 9.2.10)), but he does not give explicit reduction, nor does he give formal definition of the probability of formula in CBN. Here, we do both. Using this approach leads to formulas having range of probabilities in a CBN, whereas in a functional causal model, their probability is unique.
But we take an additional significant step. Pearl assumes that mechanisms that determine how inter- ventions work (which are given by the cpts in the case of CBNs and the structural equations in the case of causal models) are autonomous: as Pearl puts it, "external changes affecting one equation do not imply changes to the others" (Pearl 2000, p. 28). We model this autonomy formally by taking the equations to be independent of each other, in an appropriate space. As shown recently by Richardson, Peters, and Halpern (2024), taking the equations that characterize different variables to be independent is a necessary and sufficient condition for reproducing all the (conditional) indepen- dencies in the underlying Bayesian network, determined by d-separation (Pearl 1988). Thus, this independence seems like a natural and critical assumption to get CBNs and causal models to work as we would expect.
Here we assume that, not only are the equations that define different variables independent. but also the equations that give the values of a variable for different settings of its parents. We never need to consider the values of a variable for different settings of its parents in a standard Bayesian network, but this is necessary to determine the probability of a formula involving interventions, such as X = OYY = 0 A [X < I[(Y- = 1) (X and Y have value O, but if X is set to 1, Y gets value 1). Taking these latter equations to be independent is not always appropriate For example, there may be a latent exogenous variable that affects the value of Y for different settings of Y's parents. But if the parents of Y (including exogenous variables) are all observable, and screen Y off from the effects of all other variables, then the independence assumption seems appropriate.
Making these independence assumptions has significant benefits. For one thing, it allows us to uniquely identify the probability of queries in a CBN; rather than getting a range of values, we get a unique value. Moreover, for many formulas of interest (including the probability of necessity and probability of sufficiency (Pearl 2000). we can compute the probability by considering only conditional probabilities involving only a subset of endogenous and exogenous variables, which do not involve interventions. This means that these probabilities can be estimated from observational data, without requiring involving controlled experiments. This can have huge implications in settings where such experimental data is not available but the exogenous variables can be observed.
The rest of this paper is organized as follows. Section 2 reviews the formalism of causal models. Section 3 gives semantics to formulas in Causal Bayesian Networks (CBNs) and Section D shows that any CBN can be converted to compatible causal model that satisfies the independence assump- tions that we are interested in. We show how counterfactual probabilities of necessity and sufficiency can be simplified and calculated in the appendix.
PPearl [Theorem 7.1.7] provides (correct) three-step procedure for calculating counterfactual proba- bilitics in causal model. But then on p. 220, Pearl says that the same procedure works for CBNs. Specifically, he says "counterfactual probabilities p YY, = y. | e) can still be evaluated using the three steps (abduction, action, and prediction) of Theorem 7.1.7. In the abduction phase, the root nodes on the evidence available, e, and so obtain p(u e). In the action phase, we delete the arrows entering variables in set X and instantiate their values to X æ. Finally, in the prediction phase, we compute the probability of Y = y resulting from the updated manipulated network." As Beckers shows, this is incorrect. Here's trivial countercxample. Suppose that we have simple causal model with one exogenous variable U. which is the parent of an endogenous variable Y, which in turn in is the parent of an endogenous variable x. All variables are binary. U = with probability 1. = U. and if = 1, then X = with probability 1/2 and X == 1 with probability 1/2. Now consider p( p(X' = 1 X = 1). Applying Pearl's 's procedure, the probability of U = continues to be 1 (no amount of conditioning will change that). Since there are no interventions, Y =
condition the prior probability p(u) of
with probability 1. and X = with probability 1/2. That is, p(X 1 | X = 1) 1/2 according to Pearl's procedure. But this is clearly incorrect. Beckers provides a more general counterexample, and shows that the problem is not fixable any obvious way.
We thank Elias Bareinboim and Scott Muller for stressing this point.

---

2 Causal Models and CBNs
In a (functional) causal model (also called structural equations model), the world is assumed to be described in terms of variables and their values. Some variables may have a causal influence on others. This influence is modeled by a set of structural equations. It is conceptually useful to split the variables into two sets: the exogenous variables, whose values are determined by factors outside the model, and the endogenous variables, whose values are ultimately determined by the exogenous variables. In some settings, exogenous variables can be observed; but they can never be intervened upon, as (by assumption) their values are determined by factors outside the model. Note that exogenous variables may involve latent factors that are not observable, and may even be unknown. For example, in an agricultural setting, we could have endogenous variables that describe crop produce, amount of fertilizers used, water consumption, and so on, and exogenous variables that describe weather conditions (which cannot be modified, but can be observed) and some latent factors, like the activity level of pollinators (which cannot be observed or measured). The structural equations describe how the values of endogenous variables are determined (e.g., how the water consumption depends on the weather conditions and the amount of fertilizer used).
Formally, a causal model M is a pair (S,F), where S is a signature, which explicitly lists the endogenous and exogenous variables and characterizes their possible values, and F defines a set of modifiable structural equations, relating the values of the variables. (u, R), where Ut is a set of exogenous variables, V is a set of endogenous variables, and R associates with every variable Y E EUUVa a nonempty set RYY of possible values for Y (that is, the set of values over which Y ranges). For simplicity, we assume that V is finite, as is RYYY) for every endogenous variable Y E V. F associates with each endogenous variable X E V function denoted Fx such that Fx: makes precise the fact that Fx determines the value of X, given the values of all the other variables in i U..
signature S is a tuple
R(U)) x (Xyev- (x) R(Y)) + R(X). This mathematical notation just
The structural equations define what happens in the presence of external interventions. Setting the value of some variable X to x in a causal model M = (S, F) results in new causal model, denoted Mx+x- which is identical M. except that the equation for X in F is replaced by X x.
Following most of the literature, we restrict attention here to what are called recursive (or acyclic) models. In such models, there is total ordering x of the endogenous variables such that if X < Y, then X is not causally influenced by Y. that is, (x...., .....) = F/ .....) for all y. y E RYY). If X x Y, then the value of X may affect the value of Y. but the value of Y cannot affect the value of X. It should be clear that if M is an acyclic causal model, then given a context, that is, a setting ū for the exogenous variables in U4 there is a unique solution for all the equations. We simply solve for the variables in the order given by <.
A recursive causal model can be described by dag (directed acyclic graph) whose nodes are labeled by variables, and there is an edge from X to Y if X < Y. We can assume without loss of generality that the equation for Y involves only the parents of Y in the dag. The roots of the dag are labeled by exogenous variables or endogenous variables with no parents; all the remaining nodes are labeled by endogenous variables
A probabilistic (functional) causal model is a pair (M, Pr) consisting of a causal model M and a probability Pr on the contexts of M. In the rest of this paper, when we refer to a "causal model", we mean probabilistic functional causal model, unless we explicitly say otherwise.
A causal Bayesian network (CBN) is a tuple M = (S.P) described by a signature S. just like a causal model, and collection P of conditional probability tables (cpts), one for each (endogenous and exogenous) variable For this paper, we focus on recursive CBNs that can be characterized by a dag, where there is a bijection between the nodes and the (exogenous and endogenous) variables. The cpt for variable X quantifies the effects of the parents of X on X. For example, if the parents of X are Y and Z and all variables are binary, then the cpt for X would have entries for all j. k e {0, 1)", where the entry for k) describes Pr = 0 Y j, 2 = k). (There is no need to have
*Note that the equation for an endogenous variable X with no parents must be a constant function; e.g., F'x 3. In the model Mx that results from M after intervening X, X is endogenous variable with no parents.
"Soee authors (e.g.. Pearl (2000) seem to assume that CBNs do not include exogenous variables. We find it useful to allow them.
3

---

an explicit entry for = 1 -j=z== k), since this is just 1- P(X = The ept for root of the dag just an unconditional probability, since a root has no parents.
k).)
Just as for causal models, we can also perform interventions in a CBN: intervening to set the value of some variable X to x in CBN M results in new CBN, denoted Mx-z- which is identical to M, except that now X has no parents; the cpt for X just gives X value x with probability 1.
Note that we typically use the letter M to refer to both non-probabilistic causal models and CBNs, while we use Pr to refer to the probability on contexts in a probabilistic causal model. We use P to refer to the probability in ept. It is also worth noting that causal model can be viewed
CBN; the equation Y F(F) can be identified with the entry P(Y F(T)) X = Ø) 1 in a ept.
3 Giving semanties to formulas in CBNs
3.1
The problem
Consider the following (standard) language for reasoning about causality: Given a signature S = (U, V, R), a primitive event is formula of the form X x. for X E V and R(X). A causal formula (over S) is one of the form [Y] < 91...., Yı + 3k 3klp, where
is a Boolcan combination of primitive events, .,,..., Ys are distinct variables in V. and yi E R(Y:). Such
formula abbreviated as [ < T/.p. The special case where = is abbreviated as s. Intuitively, [Y1 y1..... Y& + yk] l says that would hold if Y, were set to y/. for ...... k. ((S) is the language consisting of Boolean combinations of causal formulas. We typically take the signature S to be fixed, and just write L. It will be convenient to consider slightly richer language, that we denote L+ (S). It extends L(S) by allowing primitive events U = u, where U E U, and also allowing interventions exogenous variables
pair (M, it) consisting of a (non- mnon-probabilistic) causal model M and context i7 called (causal) setting. A formula yp E L+ is either true or false in a setting. We write (M, 77) } if the causal formula yp true in the setting (M, i7). The + relation is defined inductively. (M, 1) -
x the variable X has value x in the unique (since we are dealing with acyelic models) solution to the equations in M in context T (that is, the unique vector of values for the endogenous variables that si- multancously satisfies all equations in M with the variables in U set to ū). The truth of conjunctions and negations is defined in the standard way. Finally, (M, it) + Y + syy if (My-gr uz-g) } yp, where (M is identical to M except that the equation for each endogenous variable Y Y is replaced by Y y= yy", where y² E ER() is the value in ğ corresponding to Y, and وي is identical to J. except that for each exogenous variable U e Y, the component of ī corresponding U is replaced by u", where u² E RU)) is the value in ÿ corresponding to U. (We remark that in CBN, intervening to set an exogenous variable U u* is just like any other intervention; we change the ept for U so that u" gets probability 1.)
In a probabilistic causal model (M, we can assign a probability formulas in L by taking the probability of a formula yp in M, denoted Pr(y),, to be Pr((ū: (M, i7) } +))). Thus, the probability of o in M is simply the probability of the set of contexts in which yp is true; we can view each formula as corresponding to an event.
When move to CBNs, things are not so straightforward. First, while we still have a probability on contexts, each context determines a probability on states, assignments of values to variables. A state clearly determines truth value for formulas that do not involve interventions; call such formulas simple formulas. Thus, we can compute the truth of a simple formula to in a context, and then using the probability of contexts, determine the probability of & in CBN M. But what about causal formula such as 3 r ?/p Given context ये we can determine the model M' = MM+ - In (M', w). &p is an event whose probability we can compute, as discussed above. We can (and will) take this probability to be the probability of the formula & in (M, ūi). But note that sb does not correspond to an event in M, although we assign it probability.
'It is conceptually somewhat inconsistent to allow interventions on exogenous variables, since their value is assumed to be determined by factors outside the model, but it is technically convenient for some of our results.

---

It gets harder to evaluate probability if we add another conjunct ai and consider the formula 1/ A v//. While we can use the procedure above to compute the probability of and ei individually in (M, eT), what is the probability of the conjunction? Because such formulas do not correspond to events in M. this is not obvious. We give one approach for defining the probability of a formula in a CBN by making one key assumption, which can be viewed as a generalization of Pearl's assumption. Pearl assumes that mechanisms that determine how interventions work (which are the cpts in the case of CBNs and the structural equations in the case of causal models) are autonomous; he takes that to mean "it is conceivable to change one such relationship without changing the others" (Pearl 2000 p. 22). We go further and assume, roughly speaking, that they are (probabillistcallyy independent. In a causal model, the mechanism for given variable (specifically, the outcome after the intervention) is an event, so can talk about mechanisms being independent. While it is not event in CBN, we nevertheless use the assumption that mechanisms are independent to guide how we determine the probability of formulas in L in CBN.
3.2 Independence of cpts and complete combinations of conditional events
To deseribe our approach, we must first make clear what we mean by mechanisms (cpts) being inde- pendent. This has two components: the outcomes of cpts for different variables are independent. and for the ept for single variable Y. the outcomes for different settings of the parents of Y are inde- pendent. Indeed, all these outcomes are mutually independent. We believe that these independence assumptions are quite reasonable and, capture the spirit of Bayesian networks. In fact, Richardson, Peters, and Halpern (2024) show that the assumption that epts involving different variables are in- dependent is equivalent to the (conditional) independence assumptions made in Bayesian networks (see Section 3.4 for further discussion).
In more detail, suppose that we have a variable Y1 in a CBN M with parents X1 ...... Xm- We want to consider events of the form Yı = y1 (X1 = I1...., Xm = 2m), which we read "Y1 y1 given that X1 = 21, .... and Xm, Zm Such events have probability, given by the epts for Yı. We call such an event a conditional event for CBN M. (Explicitly mentioning the CBN M is necessary, since on the right-hand side of the conditional with left-hand side Y. we have all the parents of Y; what the parents are depends on M.) Roughly speaking, we identify such a conditional event with the formula [X] f ji,-.., Xmm < JYn = 1). This identification already hints at why we we care about conditional events (and their independence). Suppose for simplicity that determine the probability of a formula such as X, = A Y1 = 0 A [X, + L|(Y, = 1) we need to apply both the entry in the cpt for Y = 0 X = O and the entry for Y1 = 1 X = 1. They each give a probability: the probability of the formula X1 = 0 = 0 [X1 < 1] = is the
1. To
probability that the conditional events Y1 = 0 X₂ = 0 and Y1 = 1 X = 1 hold simultaneously.
Our independence assumption implies that this probability is the product of the probability that each of them holds individually (which is given by the cpt for Yi).
This is an instance of independence within ept; we want the conditional events in a cpt for a variable Y for different settings of the parents of Y to be independent. (Of course, conditional events for the same setting of the parents, such as Y1 = 0 X₁ 1 and Y, | X, 1, are not independent.) Independence for cpts of different variables is most easily explained by example: Suppose that Y22 has parents X1 and X3. Then we want the events Y = 0 Xi and Y-2 = 1 (X1 = 03 = 1) to be independent. This independence assumption will be needed to compute the probability of formulas such as [X] t (Y1 = 0) A [X1 = 0, X3, = 1](Y, = =1). As we said, we in fact want to view all the relevant conditional events mutually independent
Although we use the term "conditional event", these are not events a CBN. On the other hand, in a causal model, there are corresponding notions that really do correspond to events. For example, the conditional event Yi = X1 = corresponds to the set of contexts where the formula [X, + 1] = 1) is true. Starting with a CBN M, we will be interested in causal models for which the probability P(Y, = X1 = 1), as given by the cpt for Yi in M, is equal to the probability of the corresponding event in the causal model.
Going back to CBNs, define a complete combination of conditional events (ccce) for M be a conjunction consisting of the choice of one conditional event for M for each endogenous variable
TTis implicitly assumes that all exogenous variables are independent. We can easily drop this assumption by assuming that rather than having a separate cpt for each exogenous variable, we just have single cpt for contexts. Nothing in the rest of the discussion would change if we did this.
5

---

X and each setting of the parents of X. A fixed-context ecce (feece) involves fewer conjuncts; we have only conditional events where for all the exogenous parents of variable X, the value of U is the same as its value in the conjunct determining the value of U (the examples should make clear what this means).
U
X
Y
Example 3.1. Consider the CBN M with the following dag: where all variables are binary, and the cpts give the following probabilities: P(U 0) d
P(X = 0 U = -0) = b, P(X = 0 U =1) P(Y =
0 X = 0) = d, and P(Y = 0 X
1) = e. Then a cece consists of conjuncts:
one of U = and U = 1;
one of X = 0 = 0 and X 1 0;
one of X = 0 | = 1 and X 1| | U 1:
one Yf X 0 anddd Y = 1 X 0; and
one of 0| X = 1 and Y = - 1.
An fecce consist of only 4 conjuncts; it has only one of the second and third conjuncts of a coce. In particular, if U O is conjunct of the fecce, then we have neither X = 0 U = nor as conjunct; similarly, if
X ==1
is conjunct, then we have neither X = 0 U
nor X = 1 U = O as conjunct. (This is what we meant above by saying that each exogenous parent U of X must have the same value as conjunct that determines U' value.)
is not hard to show that, in this case, there are 32 occes and 16 fecces. Moreover, (in this example and in general) each fecce is equivalent to a disjunction of ccces. The number of ccces and feeces can be as high as doubly exponential (in the number of variables), each one involving exponentially many choices. For example, if a variable Y has parents, each of them binary, there are 2 possible settings of the parents of Y. and we must choose one value of Y for each of these 2" settings, already giving us 22" choices. It is easy to see that there is also a double-exponential upper bound.
If we think of a conditional event of the form Z = X 0, Y = 0 as saying "if X were (set to) 0 and Y were (set to) 0, then would be 1", then given a ccce and a formula yp E L and context i7, we can determine if yp is true or false. We formalize this shortly. We can then take the probability of ip to be the sum of the probabilities of the ccces that make yp true. The probability of a ccce is determined by the corresponding entry of the cpt. Thus, if we further assume independence, we can determine the probability of each coce, and hence the probability of any formula y We now give some informal examples of how this works, and then formalize the procedure in Section 3.3
Example 3.2. In the CBN M described in Example 3.7 there are two fccces where = X 1) is true: (a) U = = (X = 0 U 0) A (Y 0 X AY X = 1); and (b) U = A (X = 0 | U = 1) = X A (Y = X = =). Each these two fecces is the disjunction of two ccces, which extend the fecce by adding a fifth conjunct. For example, for the first foece, we can add either the conjunct X 0 U = or the conjunct
OAY 0 [X t 1](Y
X 1 U 1. The total probability of these two fecces is abd(1 e) (1 a)cd(1 - e); this is the probability of up in M
We give one more example of this calculation.
Example 3.3. Consider the model CBN M which differs from M in that now U also parent of Y; the dag is shown below. M and M have the same cpts for U and X; the ept of Y in M is P(Y = 0 U = =0,X = 0) f1, P(Y = U = O, = 1) 1)= = fz. P(Y = U =
1, =
fa. = U- -| fr.
U
X
Now there are 128 coces, but only 16 fccces the formula 4p = =X + 1] = i)
true in only two of these feeces: (a) U = 0A 0 =
00=
1 1 (U = 0. = 1)); and (b) U = 11)X =
(U = 1)). It is easy to check that P (ạ) = 00
The
calculation of the probability of yp is essentially the same in M

---

We denote by (g)) the probability of a formula in CBN or causal model M. (We provide a formal definition of Pr (p) for CBN M at the end of Section
3.3 Giving semantics to formulas in CBNs
We already hinted in Examples 3.2 and 3.3 how we give semantics to formulas in CBNs. We now formalize this.
The first step is to show that a cece (resp., fecce) determines the truth of formula in (S) (resp.. ((S)) in causal model. To make this precise, we need few definitions. We take the type of CBN M = (S,P), where S = (4, R) to consist of its signature and, for each endogenous variable, a list of its parents (which is essentially given by the dag associated with M, without the cpts). A causal model M' = (S',F') F²) has the same type as M if S' = (u U V, R'), where U' is arbitrary, R' R'luLv = R, and F' is such that each endogenous variable X depends on the same variables in u U according to F' as does according to the type of M (but may also depend on any subset of U').
Definition 3.4. For the conditional event Y = =X,--1,..... X = Im)) let the corresponding formula be [X1 s- Fi...., ,,, - Fm = y)- (Note that the corresponding formula may be in since some of the X,5 may be exogneous.) Let ia L (8), the formula corresponding to the ccce a, be the conjunction of the formulas corresponding to the conditional events in a. We can similarly define the formula corresponding to an fecce.
=y)
Example 3.5. In the model Mt of Example 3.3 if the fecce U A (X = 0 = 0) (Y=
0 (U = 0, X = 0)) A (Y = 1 (U =
0. x = 1)), then Pa. is U = 0 A IU + 0, = 0 A +
=
0, O) - -
1U
Say that a formula si is valid with respect to a CBN M if (M', x) 16 for all causal settings (M', w), where M' is causal model with the same type as M. The following theorem makes precise the sense in which a ccce determines whether or not an arbitrary formula is true.
Theorem 3.6. Given a CBN M = (S)P) and a ccce (resp., fccce) a, then for all formulas s E (S) (resp., &/ E L(S)) either Pa = a is valid with respect to M or Pa 7 -ap is valid with respect to M.
Proof: We show that two causal models M1 and M2 have the same type as M and iy and ūp are contexts such that (M1, ū7)) F Pa and (M2, (2)) += Pa, then for all formulas &b E L L* (S) (resp., di E L(S)), we have that
(M1, (7) F v iff (M2, T2) b
(I)
The claimed result follows immediately. The details of the proof can be found in the appendix. I
Based on this result, we can take the probability of formula 9 E C+(S) in a CBN M to be the probability of the ccces that imply it. To make this precise, given a CBN M, say that a probabilistic causal model (M', Pr) is compatible with M if M' has the same type M, and the probability Pr is such that all the cpts in M get the right probability in M'. More pre- cisely, for each endogenous variable Y in M, if X1,.... Xx are the parents of Y in M, then for each entry P(Y = y X1 = II,.... Xx = xx) = a in the cpt for Y. Pr is such that the corresponding formula [X, + Z1..... X2 <- xY is i-compatible with M (the stands for independence) if it is compatible with M and, in addi- tion, Pr is such that the events descrihed by the formulas corresponding to entries for cpts for different variable (i.e. the set of contexts in M that make these formulas true) are independent, as are the events described by the formulas corresponding to different entries for the ept for given variable. Thus, for example, if (#f,-. xx)) # (II,..., IR),, then we want the events de- v) to
y) gets probability
(M', Pr)
scribed by [Xi < 31...., X₁ + æx](Y be independent (these are different entries of the cpt for Y); and if Y # Y and has parents Xy.... X" in M, then we want the events described by [X] + T1...., X₁ + rxl(Y y) and [X] + r'....,, Xm + 2'm = y') to be independent (these are entries of cpts for different variables).
y) and [X] + x1 Ti...., X + x/
Theorem 3.7. Given a CBN M and a formula &p E (S),, the probability of yp is the same in all causal models M2 i-compatible with M.
7

---

Proof: It follows from Theorem 3.6 that the probability of ip is the sum of the probabilities of the formulas yo, for the ccces a such that yP,, * pp valid. is immediate that these formulas have the same probability in all causal models i-compatible with M.
Formally, we take PMM (vp), the probability of yp in the CBN M, to be (T))((p) for a causal model M' i-compatible with M. By Theorem 3.7, it does not matter which causal model M' i-compatible with M we consider. Note for future reference that if we consider only causal models compatible with M. dropping the independence assumption, we would get a range of probabilities.
3.4 Discussion
Four points are worth making: First, note that this way of assigning probabilities in a CBN M always results in the probability of a formula o E L being a sum of products of entries in the cpt. Thus, can in principle compute the probabilities of (conditional) events involving interventions from observations of statistical frequencies (at least, as long as all settings of the parents of a variable in the relevant entries of the ept have positive probability).
Second, the number of ccces may make the computation of the probability of a formula in a CBN seem unacceptably high. As the examples above shows, in practice, it is not so bad. For example, we typically do not actually have to deal with ceces. For one thing, it follows from Theorem 3.6 that to compute the probability of o E L. it suffices to consider fecces. Moreover, when computing PrM((p where yp involves an intervention of the form X + x, we can ignore the entries in the epts involving X, and for variables for which X is parent, consider only entries in the cpts where X = z. We can also take advantage of the structure of the formula whose probability we interested in computing to further simplify the computation, although the details are beyond the scope of this paper.
Third, as mentioned above, formula involving interventions does not correspond in an obvious way to an event in a CBN, but it does correspond to an event in a (functional) causal model. The key point is that in a causal model, context not only determines a state; it determines state for every intervention. We can view a formula involving interventions as an event in space whose elements are functions from interventions to worlds. Since a context can be viewed this way, we can view formula involving interventions as an event in such a space. This makes conditioning on arbitrary formulas in L (with positive probability) in causal models well defined. By way of contrast, in CBN, we can view a context as a function from interventions to distributions over worlds. Finally, it is worth asking how reasonable is the assumption that cpts are independent, that is, considering i-compatible causal models rather than just compatible causal models, which is what seems to have been done elsewhere in the literature (see, e.g., (Balke and Pearl 1994 Tian and Pearl 2000
As we said, Richardson, Peters, and Halpern (2024) show that the assumption that epts involv- ing different variables are independent is equivalent to the (conditional) independence assumptions made Bayesian networks. More precisely, given CBN M, let M' be the non- probbbbbbiilittic causal model constructed above. They show that if the probability Pr' makes interventions on different
variables independent (i.e., if Pr f fm) Pr( x Pry, (f1) ... Pry... (fm). in our construction), then all the conditional independencies implied by d-separation hold in (M, Pr') (see (Pearl 1988) for the formal definition of d-separation and further discussion). Conversely, if all the dependencies implied by d-separation hold in (M, Pr'), then Pr' must make interventions on different variables independent.
This result says nothing about making interventions for different settings of the parents of a single variable independent. This is relevant only if we are interested in computing the probability of formulas such as X = OΛY = [^[X= + I] = 1), for which we need to consider (simultancously) the cpt for Y when X 0 and when X 1. As discussed earlier, independence is reasonable in this case if we can observe all the parents of a variable Y. and thus screen off Y from the effects of all other variables (and other settings of the parents). We cannot always assume this, but in many realistic circumstances, we can. We give two general classes of examples where we can:
1. When debugging systems (including ml pipelines, database engines, or any general soft- ware) and network failures, users have access to all parameters related to the code and the execution environment (Fariha, Nath, and Meliou 2020, Kobayashi, Otomo, and Fukuda 2019, Galhotra, Fariha, Lourenço, Freire, Meliou, and Srivastava 2022). With this infor-
8

---

mation, causal graph over different blocks of code, its parameters, and other environment variables like information about background processes can be constructed. This means we can address queries like "Given that component A is faulty, with what probability would repairing component solve the problem" using our techniques.
2. Manufacturing pipelines across various industries, such as semiconductor fabrication, phar- maceuticals, automobile assembly, and battery production, typically consist of a series of interconnected stages. Each of these stages is equipped with several sensors designed to monitor and measure critical environmental conditions that directly impact the production process. These sensors collect data about variables such as temperature, humidity, pres- sure, and other factors that can influence the quality, efficiency, and consistency of the final product. For instance, in semiconductor fabrication, precise control of environmental con- ditions like temperature and humidity is erucial to ensuring the integrity of the microchips produced (Wu 2008). Similarly, in pharmaceutical manufacturing, sensors monitor param- eters like pH levels and chemical concentrations to maintain the efficacy of the drugs being produced. Thus, we can answer queries like "what is the probability that a temperature in- crease of 3 degrees Celsius would result in poor quality product, given that the humidity is high?""
Other potential applications of our framework include (a) modeling player performance in sports by considering factors like injury, skill, and sports facilities, (b) urban planning scenarios to analyze the impact of zoning laws, interest rates, and other factors on house prices, and (c) modeling agriculture yield by considering variables like soil quality and weather conditions.
4 Converting CBN to a (Probabilisticc Causal Model
Our semantics for formulas in CBNs reduced to considering their semantics in i-compatible causal models. would be useful to show explicitly that such i-compatible causal models exist and how to construct them. That is the goal of this section. Balke and Pearl (1994) sketched how this could be done. We largely follow and formalize their construction.
Starting with a CBN M, we want to construct an i-compatible probabilistic causal model (M', Pr'), where M' has the same type as M. To do this, for each endogenous variable Y in M with parents XI,..., Xn, we add a new exogenous variable Uy; R(yyy) consists of all functions from R(X,) x x R(X,) RYY). Balke and Pearl (1994) call such an exogenous variable response function. (Response functions, in turn, are closely related to the potential response variables introduced by Rubin (1974).) We take Uy to be a parent of Y (in addition to XI...., Xx)) We replace the cpt for Y be the following equation for Y; (z In.. f) = f(z1..... In). where f is the value of Uy. Since ff a function from R(X)) x... x R(x,) to R(Y). ). this indeed gives a value of Y. as desired. Let .i...., Ym be the endogenous variables in M. We define the probability Pr on R((() x R(Ur;) X x RUUY...) ) by taking Pr' Pr' fi.... = Pr(ūi)) x II Pry, (f)), where Pry, reproduces the probability of the cpt for Y, Specifically, for an endogenous variable Y with parents xx).
XI,...,,,, X,, (f) 1I xx) xxxx)x---((XX.) This makes interventions for different settings of XI...., Xn, independent, which is essentially what we assumed in the previous section when defining the probability of formulas in L in Mo. in addition to making interventions
Pr(Y = _(x (nn) | X1 = I1 II,....
different variables independent and independent of the context in M. In any case, it is easy to see that this gives a well-defined probability on R(4) x R(U,,) X R(Uy,,. ) the contexts in M'. Moreover, M' is clearly causal model with the same type as M that is i-compatible with M.
We can easily modify this construction to get family of causal models compatible with M, by loosening the requirements on Pr'. While we do want the marginal of Pr' on lI to agree with the marginal of Pr on U, and we want it to reproduce the probability of the cpt for each variable Y; (as defined above), there are no further independence requirements. If we do that, we get the bounds computed by Balke and Pearl (1994). The following example illustrates the impact of dropping the independence assumptions.
Example 4.1. Consider the CBN M* from Example 3.7 again. Using the notation from that ex- ample, suppose that a = and b = d 1/2. Independence guarantees that the set of ccces that includes U = 0, X = 0 | U = 0, and Y = =0 X = O has probability abd = 1/4. But now consider causal model (M*x Pr*t) compatible with M where the contexts are the
9

---

same as in our construction, but the probability Pr"" does not build in the independence assump-
tions of our construction. Recall that contexts M have the form (u, fr.xxxxyy fr). Since we wanr (M P)**) to be compatible with M we must have Pr (fu, JU.
u = 0}) = 1, (r fx, fx, : fx(0) = 0}) = 1/2, and Pr" Pr'"((u, fx. Jv) : =fr(0) = 0}) = 1/2 so that Pr" agrees with the three cpts. But this still leaves a lot of flexibility. For example, we might have
= f0( = 0} = (r""({(u, fx. : =1((1 = fy = 1 = 1/2 (so that Pr" (f(u, xx): (0) O, (1) = 1]) Pr
([ fy) fx(0)
:x(0))))) 0}) = 0). As shown in Example 3.2 PIM- (X= 0A +
11) 1/4 However, it is easy check that PIM. (X O Y A t 1 = 1)) = 1/2. (Tian and Pearl
(2000) give bounds on the range of probabilities for this formula, which is called the probability of necessity; see also Section Band (Pearl 2000) Section 9.2).)
5 Computing counterfactual probabilities
In this section, we analyze counterfactual probabilities, introduced by Balke and Pearl (1994). Counterfactual probabilities have been widely used in several domains, including psychology (Ho- erl. McCormack, and Beck 20IT), epidemiology (Greenland and Robins 1999), and political sci- ence [Grynaviski 2013), to explain the effects on the outcome. More recently, they have proved useful in machine learning to explain the output of ML models (Beckers 2022).
Two types of counterfactual formulas that have proved particularly useful are the probability of necessity and the probability of sufficiency; Pearl (2000), counterfactual analysis is particularly useful when comes to understanding the im- pact of a decision on the outcome. For example, we might be interested in the probability that an outcome O would not have been favorable if A were not true. This captures the extent to which A a necessary cause of O. Similarly, we might be interested in whether A is sufficient for O: that is if A were true, would O necessarily be true? We now review the formal definitions of these notions; see (Pearl 2000) for more discussion.
focus them in this section. As discussed by
Definition 5.1. Let X and Y be binary variables in a causal model or CBN M.
1. Probability of necessity of X for Y: PN PrM(IX + 0J(Y 0)( IAY = 1).
2. Probability of sufficiency of X for Y: PS M = PrM([X t =] = 1 x = =))
3. Probability of necessity and sufficiency of X for Y: PNS PrM((X + 1J(Y
1) - 0](Y = 0)).
Pearl (2000) gives examples showing that neither the probability of necessity nor the probability of sufficiency in CBN can be identified; we can just determine a range for these probabilities. But with our independence assumptions, they can be identified, justifying our notation. Moreover, these probabilities can be computed using only conditional probabilities of (singly) exponentially many simple formulas (not involving interventions). Since these formulas do not involve interventions, they can be estimated from observational data, without requiring involving controlled experiments. Thus, our results and assumptions have significant practical implications.
Let Pax (Y) consist of all the parents of Y other than X. For set 2 of variables, let Tz consist of all possible settings of the variables in Z.
Theorem 5.2. If M is a CBN where Y is child of X, then
(a) XN M = =E En
PrM(Pa* (Y) = 2 ppaxm = 1Y==AX=1
0 PI = - 0A (x) dpxx()))
(b) PS
(pax(() 1 -x=0A= Prm(PaX ETaa
Pr 1 Pa (Y) = (parr)))
(c) PNS M = PSX.
+ PN M PIM = IAY =).
We defer the proof of the theorem to Section B.I in the appendix, where further extensions are also provided.
10

---

Halpern's 's work was supported in part by AFOSR grant FA23862114029, ARO grant 1911NF-22-1-061,, and NSF grant FMitF-2319186. Galhotra's work is supported by grant from Infosys.
Acknowledgments:
MURI grant
References
Balke, A. and J. Pearl (1994). Probabilistic evaluation of counterfactual queries. In Proc. Twelfth National Conference on Artificial Intelligence (AAAI '94). pp. 200-207.
Beckers, S. (2022). Causal explanations and XAL. Proc. First Conference on Causal Learning and Reasoning, Volume 177 of Proceedings of Machine Learning Research, pp. 90-109. Beckers, S. (2023). Disjunctive counterfactuals using causal models: critical examination. Un- published manuseript.
Fariha, A., S. Nath, and A. Meliou (2020). Causality- adaptive interventional debugging. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 431-446.
Galhotra, S., A. Fariha, R. Lourenço, J. Freire, A. Meliou, and D. Srivastava (2022). Dataprism: Exposing disconnect between data and systems. In Proceedings of the 2022 International Conference on Management of Data, pp. 217-231.
Galhotra. S., R. Pradhan, and Salimi (2021). Explaining black-box algorithms using proba- bilistic contrastive counterfactuals. In Proceedings of the 2021 International Conference on Management of Data, pp. 577-590.
Greenland, S. (1999). Relation of probability of causation to relative risk and doubling dose: methodologic eπror that has become social problem. American journal of public health 89),), 1166-1169.
Greenland, S., J. Pearl, and J. M. Robins (1999). Causal diagrams for epidemiologic research. Epidemiology 10(1), 37-48.
Greenland, and M. Robins (1999). Epidemiology, justice, and the probability of causation.
Jurimetrics 40, 321.
Grynaviski, E. (2013). Contrasts, counterfactuals, and causes. European Journal of International Relations 19(4), 823-846.
Hicks, J. (1979), Causality in economics. Basic Books.
Hoerl, C., T. McCormack, and S. R. Beck (2011). I). Understanding Counterfactuals, Understand- ing Causation: Issues in Philosophy and Psychology. Oxford University Press.
Kobayashi, S., K. Otomo, and K. Fukuda (2019). Causal analysis of network logs with layered protocols and topology knowledge. In 2019 15th International Conference on Network and Service Management (CNSM), pp. 1-9. IEEE.
Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems. San Francisco: Morgan Kauf-
mann.
Pearl, J. (2000). Causality: Models, Reasoning, and Inference. New York: Cambridge University
Press.
Richardson, O. E., S. Peters, and J. Y. Halpern (2024). Representing mechanism (in (in)dependence. In Proc. Advances in Nueral Information Processing Systems 37 (NeuriPS '24). Rubin, D. B. (1974). Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of Educational Psychology 66(5), 688-701.
Tian, and Pearl (2000). Probabilities of causation: bounds and identification of Math-
ematics and Artificial Intelligncee 28, 287-313.
Wu, K. (2008), Modeling the semiconductor industry dynamics. Ph. thesis, Massachusetts Institute of Technology.
11

---

A Proof of Theorem 3.6
As we said, we show that two causal models Mj and M2 have the same type as M and i7i and lig are contexts such that (M Ti) } Pa and (M2, (22) F Pa. then for all formulas 1b E (S) (resp., v E ((S)). we have that (as defined in the main text) holds. The claimed result follows immediately.
Proof:
We give the proof in the case that a is cece and e E (S). The modifications needed to deal with the case that a is an focce and & E L(S) are straightforward and left to the reader. Since M acyclie, we can order the exogenous and endogenous variables topologically. Let Xx...., Xm be such an ordering. We first prove by induction on j that, for all interventions Y < y (including the empty intervention) and 2/ E R())). (M1, u1) F I t ( = x2) iff (M2, (2) F Y < (X, = x.).
For the base case, X1 must be exogenous, and hence have no parents. X1 is not one of the variables in Y, then we must have (M, ū.) [ + (X, = x1) iff (M,, Ti) - (X, æ1), and similarly for M2; since no variable in Y is a parent of X1, intervening on Y has no effect on X1. Since (M1, ū7j) F= Pa and (M2, (2)) F Pa. M1 and M2 agree on the values of variables u1. Thus, (M1, d)) F= (X1 = 21) iff (M2, (2)) += (X₂ = z1). follows that (M2, 12)) + Y + uX = 21).
(M2, T2) = [Y + 57 (X1 21), as desired.
On the other hand, if X₂ is one of the variables in Y (which can happen only if the formula is in L+ (S)), let xx be the value in j corresponning to X1. In that case, the formula (V <~ 5] (X1 xx) is valid with respect to M. It follows that (M1, iT) =18 + (X, x1) iff x², and similarly for (M2, T22). The desired result follows. This completes the proof for the base case.
Now suppose that we have proved the result for < m. Let Zi...., Zx be the parents of X in M. Since XI...., Xm is a topologiaal sort, we must have (Z,..... Σz} S (X X,}. Let Z1. . 2% be values in (..)....., R((x), respectively, such that (M1, T1) F [Ý + i2 = 2n), for h = -,.... k. By the induction hypothesis, (M2 T2)) F y (Zh zn), for h 1....,Ke k. Moreover, is easy to see that ([ + d/ [Y + Tl'') + [Y + 5 (/)) is valid with respect to M. Thus, (M, (h)) = I t ( = 21 A Zz = 2x) and similarly for (M2, dz). Moreover, since Z1. Ze are the parents of X it follows that (M1, T1) + [Ý + M s+1 = I)+1) iff [21 = 21 A ... Z& = 2*) (X = 2z+i) is a conjunct of Pa. Since (M1 ū1) F Pa and (M2, (2) F Pa. the desired result follows, completing the induction proof.
The argument that (M1 (7) - I < b iff (M2, T2) F [ + fi for arbitrary (simple) formulas
now follows from the fact that (as we already observed) (( <- v/ y ,)/')) 1 ( A (²) is valid with respect M, as are (T + s v [Y + )lw')) Y + Me V 4²) and [ + up + -I8 + spp
Finally, we can deal with Boolean combinations of causal formulas by straightforward induction. This completes the argument that (1) holds for all formulas 1a E C+
B Computing counterfactual probabilities (Missing Proof and Extension)
B.1 Proof of Theorem 5.2
M Essentially the same argument can be used to compute the probability of necessity, PN Finally, for part (c), we use the repre- X.Y
We prove the calculation for the probability of sufficiency, PS
X.Y sentation of XN in terms of X.Y and PN given in (Pearl 2000 Lemma 9.2.6).
Proof of Theorem 5.2 (b). Let 2 = (ONVV(XXYY Y). Tz has 2n-2 settings, where n = (u For setting c Tz, let ez be the setting of the variable Z in c.
12

---

By definition,
=0 0) - - =1)
PSXY
(2)
M
PrM((X =) 0) (Y = 0))
Let the numerator (X = 0Y 0)) + 1](Y = 1) be s/. Then we have
PrM( (+) =
ΣeETz (x
= = -2e2z=2(==cz))
We next compute the probability of
V (X 0) xY -0== 1] = 1) A (Z=cz)
Zez
From Theorem 3.6 it follows that in all causal models M' compatible with M,
Pr (v)c
Σ
(Pa).
Fir
Now Pa. = be holds whenever a contains the following events:
1. (X 0| Pa(X) cPa(X))
2. (Y = 0 X 0, 0, cP)
3. (Y = x P, (Pa= = CPax
4. (Z cz PZ(Z) cra(Z)) ) for all Z Z.
Let S₂ consist of all ceces that contain these four events, and let yss, be the conjunction of the formulas corresponding to the events in S.. Then by Theorem 3.6.
Pc V Pa-
OES.
Since the formulas Pa for distinct ccces in S. mutually exclusive, have that PrM:((t) Pr (yps). Therefore,
(1)
Σ (FM)((ee)
oETs
Σ = =0 = = =2) 1,Pa + ccxxp)l(=))))) =
cETZ
Σ
Pr (x=0XX=A OΛ -
+ cpa A IX + 1, + c = 1)).
Op. (r) (x)
M' i-compatible with M, then we can further conclude that
E (X = OAY = 0 Azez (Z (z) + (V) (p =1)
-EepeX ET ((Y) Pr [X = -A Pa XY))))))X))))))))))() = (Pa PrM x X Pa cpax(y))
Pr 1 = 1 PY) cP))(())
-Eepaxi (TwX(e))
Pr = 0x = 0 Pa (V) = (P))(())
- = -p)x
Since Pr (16) PRM (v), substituting the expression for Prar (xb) into
we get
E Pr(Y D X 0Λ Pax P = Cp.
Pr( X 1
(pax(M))
PSM
Pr(X = 00
desired.
13

---

We can extend Theorem 5.2 to the case where Y is any descendant of X (not necessarily a child of X). In this case, the term involving Pa(Y) would change the set of the ancestors of Y the same level as X in the topological ordering of the variables. We can further extend Theorem 5.2 to arbitrary formulas 15, where Pr(1)) can be determined by calculating the probability of formulas that do not involve interventions (although they may involve conditional probabilities), and thus can be determined using only observational information. The key idea of the proof is to convert d to a disjunction of conjunctions, where the disjuncts are mutually exclusive and have the form
vh = - A (Ave(I....r) viss) where 1i4o - (ASE(I.....) (.:=zz))) z45)) is a simple formula (with no intervention), and thaj for j > has the form [X, + 1-,,,(KE(E).-.. Yıjk - Vıjk), where Yujk descendant of X3 in M, so that we can apply the ideas in the proof of Theorem 5.2 to each disjunct separately. In terms of complexity, we show that Pr(()) can be estimated in O(m 2nn")) conditional probability calculations, where r" is the maximum number of conjuncts in disjunction ; that involve at least one intervention, and m is the number of disjuncts the DNF. Unfortunately, for an arbitrary formula 1/, determining Pr(s)) may involve expoe-eexponettially many conditional probabilities. We defer details to Section ?? in the appendix.
Theorem B.1. Given CBN PS, and an arbitrary formila v then Pr(e)) can be determined by taking the probability of formulas that do not involve interventions (although they may involve conditional probabilities), and thus can be determined using only observational information.
We now show that we can calculate the probability of an arbitrary formula & in terms of conditional probabilities that be estimated from observational data. To prove this result, we first convert ei to an equivalent formula in a canonical form. Specifically, it has the form th V ... V &mm where the wiys are mutually exclusive and each yb is a conjunction of the form rhan A A thir, where thao is a simple formula and for 1 S j S. ras tiyj is a formula of the form [X, + () (I...ffg)) Yijk = Diyk). and the interventions are all distinct. This conversion just involves standard propositional reasoning and two properties which hold under the semantics described in Section The first is
that [Y + w|@ A [Y + vlyp' is equivalent to (Y + yl(p A v²). The second is that - Y + vl p is equivalent to Y 1 -yp.
Ignore for now the requirements that the disjuncts be mutually exclusive, that all interventions be distinct, and that there be no leading formulas involving interventions. Using standard propositional reasoning, we can transform a formula &o to an equivalent formula in DNF, where the literals are either simple formulas or intervention formulas (i.e., formulas of the form [X + =x]p). Of course, the disjuncts may not be mutually exclusive. Again, using straightforward propositional reasoning, we can convert the formula to DNF where the disjuncts are mutually exclusive. Rather than writing out the tedious details, we give an example. Consider formula of the form (41 A 92) V (43 A pp)). This is propositionally equivalent to
(9) A A PI) V (91 A P2 A PS A PM) V (pr A9z A Ps A -P)) V (f1 A A -ps A -PL)) (( P2 A P3 A PA) V (F1 A 7p2 A P3 PA) V (Tp1 A 7p2 ys A p1).
We can now apply the two equivalences mentioned above to remove leading negations from inter- vention formulas and to ensure that, in each disjunct, all interventions are distinct. These transfor- mations maintain the fact that the disjuncts are mutually exclusive.
Since the disjuncts in se are mutually exclusive, the probability of d is the sum of the probabilities of the disjuncts; that is, Pr(Ø) = Eve( Pr( To compute the probability of a disjunct ei, we first simplify it using the following two observations. First, if a formula involves an intervention [X + x) on some variable X such that X is also set to x in the formula, such as (X = x A [X- < x, 7 + 2 = 1)), the intervention X + x is redundant and can be dropped; for example, X = OA + 0, Z + Y 1) is equivalent to X
A IZ + 1](Y 1). Second, if an intervention formula does not contain a descendant of the intervened variables, such as v = [X < (1/2 A v/2), where all variables in 1 are non non-descendants of the variables in X, then the variables in th are not affected by the intervention, so th can be pulled out of the scope of the intervention; that is, & is equivalent to 1/ A [X < ar] (viz). Using these observations, we remove all interventions that are redundant and pull formulas involving only non-descendants of the intervened variables out of the intervention formula.
14

---

After this simplification. without loss of generality, the disjunct dy is a conjunction of formulas 2/20 A (Nve(L.....)) Wis): where V/s0 = (A)e(L......)ZZ)) = kイy) is a simple formula (with no intervention), and Viy for j > 0 has the form [X, < E,I(Ake Yisk Vijk), where Yijk is descendant of some variable in X, in M. The following theorem proves the result for thi, which completes the proof.
Theorem B.2. If is CBN and dh = th:0 A (Ase(....r.) Wis). where iú; contains no redundant interventions, v/10 (NJE(1.....)) (2. = 2.5)) is simple formula (with no interventions), and Dbs for j > 0 has the form [X, ZJK(ARE(L.....)) Yisk Vsjk), where Ysjk a descendant of some variable in X3 M, then Pr(()) can be computed by determining the probability of formulas that do not involve an intervention.
Proof. The proof proceeds along lines very similar to the proof of Theorem 5.2
Let 2 1 Z -UV Z, and {zi : j E {I...., 8. Tz has 2 settings. For setting Tz, let ez be the setting of the variable in c. We use (Z) to denote An Pa(Z),
i.e, the set of parents of Z in A and žΛ to denote the values in E for all variables in A. Then
(r)(()) =
( A (& Ae (E(!..)))s)
Σ Prм A ( <ET2
=
A
Yisk = -osh=Wss) AA (Z =cz)
(E(l)..)))
jE(lI...)g)
ZEZ
We next compute the probability of
( (E((I....s.)
(Zy 24y ( A
+ Z,)(
A kE(),...)t))
Yys =wok) A (Z cz)
SE(L....r.)
ZEZ
From Theorem 3.6 it follows that in all causal models M' compatible with M,
Pr =
Σ
(yar((a))
PPx
Vic
Now Pa
ditc holds whenever contains the following events:
1. (Zi = 2iz Pa((2)) = Cr for all j E {l...., si}:
2. (7 = cz Paz (7) (a)( Pa (7) EPaz(Z)) for all Z E 2;
3. (X= =
Pa(X)= = ( for all X XY. where X2 consists of all descendants of the intervened variables in X, other than the variables in X,, and á¹ TT the set of settings of the variables U V, where the following variables are fixed as follows:
(a) X, Zy-
(b) Yisk Vijk for k E fl.....ttyh
(c) Zi 2i for Zu (X, U UX). sl.....s:)
(d) Z = for all Z E Z and Z & (Xy, UX,X))
Intuitively, Tj captures all possible post-intervention settings of all variables that are descendants of X,, while fixing Yiy&S as Yijk- By fixing the third set of events, (X Pa(X) e for all X E XY. we ensure that all events involving descendants X, are consistent with respect to one of the post-intervention settings E TŞ. These events represent the effects of interventions in x, +- J. on its descendants. For example, consider a causal graph as shown below and va
[X + X, + 1] = 1).
15

---

X1
X2
X3
In this case, X, = [Xi + 1, 1, + 1]. By the conditions mentioned above, a must contain one of
1) A (X: 2
the two events ((Y = X2 =
0, 03 = 1) A [X2 = 0 X1 = 1)) or ((Y = -
= 1, X2 - 0, X3 - 1, Y =
1Xxxx X = 1, X,
1.XG 11
1,
1
11
X1
1)), because 7/ = ((X) |
1).
(X]
1, X2
-a 13). This condition ensuree that if X1 1 and X3 1, then Pa implies Y = 1.
is easy to see that if a does not contain either of these two events, then it must contain ((Y =
X2 0, 1) A (X2 0 X1 = 1)) ((Y = 0 X₂ X3 = 1) A (X2 1 X1 = 1)), in
which case Pa does not imply 24.
Let Sc consist of all ccces that contain these events, and let yss, be the conjunction of the formulas corresponding to the events in Se. Thus,
[Pa(Zy) + cra(z = =2)1)
88. =
A
A [Paz(Z) + cPaz(z) A PZz(Z) + EPaz(2)1(2 = cz)
IEEZ
A
A (Pa(X) + Eracs))( = =cx))
(EET) XEEX xEXX
SE(L...rt
[Pa(Zig) cpalz = =
A
[Paz(Z) t cPaz(Z) A Paz(z) + ε EPas(2))( = 02))
A
7E2
V (KeA),
Po(x) + (pacx)](X -xax)))(x= )
(oiET : (E(l....)))) KEXX, (E(
Then by Theorem 3.6
gs. + V Pa.
aeS.
Since the formulas Pa for distinct ccces in S. are mutually exclusive, we have that Pra (1hc)) Pr (sps). Therefore,
(m))) Σ (1/r))
oETz
Σ Tz d dET; (E(li.).
PrAS
A
(Zig = =z)) A A (Z = c2)
(Pa(X) + dexxx)(( =xx d2).
Xex, (E(...)))))) )
We can further timllif this expression. Specifically, we can get rid of [Pa(X) + Frax))(X =
dxx for all descendants X of some YIsE with k E fl.....te t and E (l.......).
s:). We leave the details to the reader. The expression above may be infeasible for some combinations of settings c E Tz and e' for all ε (1...., rz}. (I.....r:).. For example [X + 1[(Y = A + 1] = 1) has zero probability, Furthermore, certain formulas in A (e
Seeeeayllli = dx) =
[Pa(X) + |
may be duplicates, and some interventions may be redundant. We need to drop the duplicates and
16

---

redundant interventions before further simplifying the expression. For ease of exposition, we assume that the expression feasible, all conjuncts in (x... + o ra(x))(XX xx) are distinct, and all interventions are non-redundant.
If M' is i-compatible with M, then can further conclude that
Pr (wt)
Σ cETz: ef dET
PrM*
A (EE(I.)))
(Zyy=
(Zig = =z)) A A (7 = ez)
ZEZ
x PTMM
(Pa(X) + (x
= =dx)
XEX
(E(I....r))
Σ
PrM*
A
(Zig = =zs)) A (Z= = ez)
cET2. dET..E
('E(Ima))
ZEZ
(x dx Pa((X) + {pacx))
II XEX IE IE(U.....
Since (I)) = ar (th)) we get the desired result.
In terms of complexity, each intervention X, H. requires most 2" different settings in the set T7. Therefore, the expression above for Pr (1/2) has O(2n(re+1) setting combinations in the summation and 0mr;++1) conditional probability calculations for each such setting. This shows that arbitrary formula d can be evaluated in terms of (mm(nr" + 1)2*(r"+1)) conditional probability calculations, where r* is the maximum number of conjuncts in a disjunction a that involve at least one intervention, and m is the number of disjuncts in the DNF.
NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We have summarized the key claims in the introduction and abstract, provided relevant references wherever we referenced prior work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 3.4 discusses the implications of assumptions.
Guidelines:
17

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have added all theorems and proofs (some of which are in the supplemen- tary material).
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided or not)?
Answer: [NA]
Justification:
We do not have experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- reasonable avenue for reproducibility, which may depend
missions to provide on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primanily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
We do not have experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//ipps.cc/pblic/gui.dee/ Sumeai/:seeeeeeeeeeoeeaaaeaaa ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
19

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification:
We do not have experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
We do not have experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, one should state The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
We do have experiment results.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
20

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have preserved anonymity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper diseuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do not any direct societal impact of the paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks identified.
Guidelines:
The answer NA means that the paper poses such risks.
21

---

Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, patuussss.aperswiittt paperswithcode com/ /ataaststeett has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer:[NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
22

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (i applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "D6ioIERhxG", "reviewer": "Reviewer_Yecn", "summary": "They define counterfactual probability for causal Bayesian networks as the probability of i-compatible causal models.\n\nIn the appendix, they show how to calculate counterfactual probabilities and necessary/sufficient probabilities.", "questions": "If the probability of a counterfactual formula in CBNs is defined using causal models, could one not use Pearl's method to calculate the probability in the causal model without using (f)ccccs?\n\n>p2 footnote: p(umide).\nthat should be p(u|e) ?\n\nDoes that footnote really describe what Pearl intended? Perhaps he meant that x,y, and e have to be disjoint variables when calculating P(Y_x = y | e)\n\nWhat probability do you obtain in this example, if you calculate it according to your definition of counterfactual probability?\n\n>4 159 for the exogenous variables \n\nare those not the endogenous variables?\n\n>4 161 , u)_Y ..\n\nshould that be , u_Y..) ?\n\n(there are also parenthesis missing in p9 401 and elsewhere)\n\n>5 199 In fact, in another NeurIPS submission (with a different set of authors)\n\nare the authors also independent?\n\n>5 213 the probability that the conditional events Y1 = 0 | X1 = 0 and Y1 = 1 | X = 1  hold simultaneously.\n\nwould that not be  [X1 ← 0](Y1 = 0) ∧ [X1 ← 1](Y1 = 1) ? \n\nor is it the same? why would it be the same?\n\n>7 316  all the cpts in M get the right probability in M \n\n\"in M\" twice? Is on of them supposed to be \"M'\"?\n\n\n>8 343 (at least, as long as all settings of the parents of a variable in the relevant entries of the cpt have positive probability).\n\nand there are no unobserved variables?\n\n>p11 section B\n\nthere is a lot of text here in the appendix which is hardly referenced by the main text. \n\nare the results here less important?\n\n>p13 557 in S. .. φ_S \n\nwhat is S and φ_S? is that S_c? and then φ_c?\n\n>p15 593 ψ_ic = Pr_M(/\\..)\n\n{1,..,s} that is {1,..,s_i} ?\n\nψ_ic is the formula /\\...., not the Pr_M ?\n \n \n>p15 595ff c_Pa(..)\n\nc_Pa(Z) is the c_Z\\in T_Z? That is only defined for Pa(Z) \\in \\cal Z, i.e. Pa(Z) != Z_{ij}.\nDo you prove somewhere that there is no Z_{ij} with Pa(Z) = Z_{ij}?\n\n>p16 617 \"in S\"\n\nwhat is S?", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "One needs definition like in this paper before doing any kind of research into counterfactuals", "weaknesses": "Exponential complexity\n\nLots of things in the appendix\n\nSome proofs are hard to understand\n\nA lot of the motivation depends on an unpublished Becker paper and an unnamed NeurIPS submission", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for several insightful and detailed comments\n(even from the appendix!).\n\np. 2: footnote: This should indeed be p(u \\mid e). Thanks! According\nto our reading of Pearl, the procedure as we've described it is\nPearl's.  He does not require disjointness.  Our method, even without\nindependence assumptions, gives p(X=1|X=1) = 1 (as it should).\n\np. 4, lines 159, 161, p. 9, 401: thanks for spotting these typos\n\np. 5, l. 199: there is one common author in the papers\n\np. 5, line 213: Technically,  Y1 = 0 | X1 = 0 and Y1 = 1 | X = 1 is an\nevent in a CBN, while [X1 ← 0](Y1 = 0) ∧ [X1 ← 1](Y1 = 1) is an\nevent in a functional causal model.  According to the mapping that we\ndefine, the former event holds in a CBN M iff the latter event holds\nin the causal model M' that it is M is mapped to (according to our\nmapping).  But, formally, they are different events.\n\np. 7, line 316: indeed the second M should be M'\n\np. 8, line 343: Technically, the statement here is true even if there\nare unobserved variables.  But if there are such variables, then it\nseems unreasonable to identify the probability of a formula \\phi in a\nCBN M with the probability of \\phi in a causal model i-compatible with M.\n\np. 11: Section B consists of background material needed to prove the\nbound on the probability of necessity and sufficiency under our\nindependence assumptions.  Since Pearl devotes a lot of discussion to\nthese probabilities in his book, we thought that the comparison would\nbe useful to the reader.  We will discuss this in more detail in the\nmain text in the full paper.  It's not so much that these results are\nless important, but we were short of space, and we felt that they were\nquite as necessary for telling our story.\n\np. 13, l. 557: Indeed, these subscripts were somewhat garbled. Thanks for\ncatching this!\n\np. 15, l. 593: Another good catch!\n\np. 15, l. 595: Good catch, we will fix this.\n\np. 16 line 617: Again, this should be S_c.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oxKcVtyCI1", "reviewer": "Reviewer_nbxs", "summary": "This paper shows the identifiability of interventional formulas in Causal Bayesian Networks (CBNs) under an independence-of-machanism assumption. It also formalizes the construction of Balke and Pearl (1994) of how to convert a CBN to a Structural Causal Model (SCM).", "questions": "1. Can you give a nontrial, meaningful example where Peal's \"abduction, action, and prediction\" procedure fails (footnote 1)?\n2. In line 176, why assigning causal formulas in CBN is hard? Considering the fact that we have defined intervention in CBN (line135), why we can not just apply the same definition as in line 160? I do not really understand your explanation in lines 354-361.", "limitations": "I would suggest the authors to include their limitations (e.g., assumption, computational cost) in the paper.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. This paper considers an important problem of identifying counterfactual formulas in CBN.\n2. Statements made in the paper are rigorously proved.", "weaknesses": "My first concern is regarding the assumptions required to identify the probability queries in a CBN. As far as I comprehend, there are three assumptions involved\n\n- The outcomes of opts for different variables are independent.\n- For the opt of a single variable $Y$, the outcomes under different settings of $Y$'s parents are independent.\n- We have available all the basic ccce formulas.\n\nThe first asm. is okay since it is just a restatement of Pearl's autonomous mechanism. The third asm. is also acceptable (thought can be costly for computation) since it just states that we need a full observation of the system's dynamics. \n\nWhat really concerns me is the second asm., which basically requires that the system does not contain unobserved, exogenous variables. For example, if we have $Y\\leftarrow U, Y\\leftarrow X$, where $U$ is a unobserved, exogenous variable, it is hard to imagine why $Y|X=0$ and $Y|X=1$ can be independent (they are both correlated to $U$). The authors should provide more justification of this assumption, and some concrete, real-world examples where this asm. can hold.\n\nMy second convern is clarity. This paper involves many definitions and notations, so the author should pay special attention to clarity. For example, what is the problem of existing framworks? what are your assumptions and their rationalities? what are your core contributions? These contents should be stated clearly and explained in depth. It would be nice to put the discussions right after the assumptions/theorems rather than in a separate section.\n\nMoreover, I feel a disconnection between the discussion of CBN and that of SCM. Now that your main result is the identification quantities in CBN, why do you mention SCM? Indeed, Sect. 4 connects CBN and SCM, but it is basically a refinement of Pearl's method and the novelty is limited. I would suggest you reconsider this part and save more space to discuss your main results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- With regard to the second assumption needed to identify the\nprobabilities in a CBN, we agree that it is nontrivial.  We will\nexpand the discussion on lines 55-63 and provide more examples.\nGiven our view of exogenous variables are simply variables whose\nvalues are determined \"from the outside\", such examples are easy to\ngenerate.  To take just one of many examples, climate conditions\n(temperature, sunlight, humidity, CO2 level)\nare often measured to help model crop yield in agriculture scenarios.\nThese variables typically cannot be intervened on, and their values come\nfrom \"outside the model\", so they are best viewed as exogenous.  But they\nsatisfy our independence assumptions.\n\n- We didn't really understand your second concern (although are happy\nto do what we can to address it once we do understand it).\nSpecifically, we don't think that there's a problem with the\nexisting frameworks.  We show that by making certain\nindependence assumptions (which we thought were stated clearly), we\nare able to identify probabilities in a CBN.  We would be happy to\ngive more examples to motivate our assumptions and show their\napplicability.\n\n\nWe believe that the discussion of SCMs is important.  Like Pearl, we\nneed to go through SCMs to get our result.  Indeed (given our\nindependence assumptions), we *define* the probability of a formula in\na CBN to be its probability in any one of a set  of SCMs.  So we can't\neven state our result without going through SCMs.  And while there is\ncertainly some overlap between our approach and Pearl's, there are\nalso some nontrivial differences. However, we will expand\non the points mentioned by the reviewer to clarify the key insights and\nassumptions.\n\nQuestion 1: The example in footnote 1 is a simple scenario to demonstrate\nthat Pearl's procedure violates basic conditional probability\ncalculations.\nOne counterexample is sufficient to prove that the three step\nprocedure fails.\nAlso, the example can be complicated by adding additional\ninterventional terms.\nIt is a toy example because (i) it is not the contribution of this paper.\n(ii) we wanted to convey the intuition with the simplest setting.\n\nQuestion 2:  In probability\ntheory, we can only assign probability\nto events (subsets of the\nsample space).  So to assign a probability to a formula like [Y ←\ny]\\phi in a CBN, we have to identify a sample space and an event\ncorresponding to this formula in the sample space. We will add more\njustification to the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Fc2HB8qYlk", "reviewer": "Reviewer_6Tw9", "summary": "The paper introduces a condition under which the counterfactual probabilities can be computed from a Causal Bayesian network (CBN). This is not the case in general and functional causal models such as SCMs are often required for counterfactual reasoning. Specifically, the paper shows that when the outcomes are independent under different parent instantiations (in addition to the independence of CPTs), counterfactual queries can also be answered with a CBN.", "questions": "The results make sense to me and I don't have any specific questions for now.", "limitations": "OK.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "I found the main idea of the paper very intuitive and significant. The paper also provided many examples to make it easy to follow. I found the discussion on the conversion of CBNs to SCMs in Section 4 quite helpful, and it is interesting to see how this is translated into the independence assumptions within CPTs (main contribution in Section 3.2). The results in this paper allow us to answer counterfactual queries (counterfactual layer in PCH) with the information from the interventional layer, which can be quite useful in practice as well.", "weaknesses": "I think the paper can be more convincing if the authors could provide some real-world scenarios in which the CPTs satisfy the independence assumptions and in which they do not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive comments.  We\nwill provide more examples where the independence assumptions do and\ndo not hold.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EPMyeU9PnO", "reviewer": "Reviewer_3ny6", "summary": "This paper builds off recent work showing that Pearl's proposed approach for calculating conditional probabilities involving interventions is incorrect.  Using Pearl's concept of autonomy (independence of mechanisms), the authors build a series of formalisms to calculate arbitrary conditional probabilities in causal Bayesian networks and show how these formalisms relate CBNs and functional causal models.", "questions": "Is the unpublished Beckers 2023 manuscript available anywhere?  If not, can you describe the main argument of that work?\n\nWhat is the practical use case of this work?  The only examples provided are toy examples, which, while useful for explaining the approach, don't do much for showing how the method presented in the paper could be used in a real-world setting to answer a relevant causal query.\n\nIn line 392, is the $f$ on the left-hand side of the equation the same as the $f$ on the right-hand side?  You define $f$ here as \"the value of $U_Y$\", and it seems strange to me that $U_Y$ would be an equation that depends on $x_1, ..., x_n$.  However, I'm not otherwise sure why you'd introduce a new variable that shares the name with a function in the same equation.", "limitations": "I'm unclear about the applicability and use case of this work, so I'm not sure what the limitations could be.\n\n\nI've raised my score from a 3 to a 5.  If the other reviewers don't view the fact that this work is motivated by fairly significant findings that cannot be viewed and assessed at the time of publication, then I'm completely fine with accepting.  The main sticking point for me is not being able to assess the severity of the problem that this is solving.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "I think this paper is overall well-organized and written.  While there is a lot of notation and terminology, the definitions are presented clearly, and the narrative is relatively easy to follow.", "weaknesses": "There are many cases of imprecise language or strange descriptions that, at least on the surface, appear incorrect.  These vary in severity, but their frequency is worrying.\n- line 17: \"in epidemiology, causal models are instrumental in deciphering the relationships between lifestyle choices and health outcomes (Greenland, Pearl, and Robins 1999)\".  I'm not sure that this is true, or, if it is (my knowledge of current epidemiological practice is limited), that citation certainly doesn't support this claim.  The abstract in the cited paper says that \"Causal diagrams can provide a starting point\", which is a far cry from them being \"instrumental\".\n- line 33: \"In a causal model [...] there is a deterministic (structural) equation, that gives the value of Y as a function of the values of its parents.\" There are a few issues here.  First, the previous line does introduce the functional causal model vs CBN distinction, but you haven't yet said that you'll be using the phrase \"causal models\" exclusively to refer to \"functional causal models\", so readers will assume you mean both types.  However, CBNs are not deterministic, so this line just reads as incorrect.  Second, even if we assume that you're using 'causal model' here as you later define it in line 123, it's still incorrect since line 123 says that \"in the rest of this paper, when refer to a 'causal model', we mean a probabilistic functional causal model\".  I discuss this issue in more detail below, but the terminology around 'functional causal models' needs to be reworked to be less confusing.\n- line 45-46: \"Pearl assumes that the mechanisms that determine how interventions work (which are given by the cpts in the case of CBNs and the structural equations in the case of causal models), [...]\" I understand that interventions are performed by replacing the CPT with a constant for CBNs or by replacing the right hand side of the equation in SEMs.  However, I wouldn't say that the CPT or the structural equations are \"the mechanism that determine how interventions work\".  Sort of the opposite - they're the mechanisms that determines how the model operates under observational conditions.  The intervention makes change to a CPT or structural equation, but nothing in that table or equation is determining how the intervention works...\n- line 108: \"if a theory is recursive, [...]\" This is the only time you refer to the noun 'theory', and in line 105, you define the term recursive wrt a model, not a theory.  Do you just mean model here?\n- line 127: \"we focus on recursive CBNs that can be characterized by a dag\".  This is strange and redundant.  Assuming here, recursive == acyclic, as you defined earlier, all CBNs are acyclic, so the phrase \"recursive CBN\" is redundant.  Similarly with \"that can be characterized by a dag\" - Bayes nets use a DAG representation, so all CBNs can be characterized by a DAG. (am I missing some nuance you're trying to convey here?)\n- line 155: Until this point, you've been using $\\phi$ to refer a specific formula (e.g., at the beginning of line 155).  Then, lines 155-156 use $\\psi$ before returning to $\\phi$ again.  Is this a typo?  If not and there's a meaningful difference, you need to describe that.\n- line 161: I think this is just a typo.  The line as-is reads $(M_{\\vec{Y} \\leftarrow \\vec{y}}, \\vec{u})_{\\vec{Y} \\leftarrow \\vec{y}}$.  However, the text afterwards refers to \n\n$\\vec{u}_{\\vec{Y} \\leftarrow \\vec{y}}$.  So should the initial line instead be \n\n$(M_{\\vec{Y} \\leftarrow \\vec{y}}, \\vec{u}_{\\vec{Y} \\leftarrow \\vec{y}})$ ? (excuse the weird line breaks...it didn't like multiple equations in one line for some reason)\n- footnote 5: \"it is conceptually somewhat inconsistent to allow interventions on exogenous variables, since their value is assumed to be determined by factors outside the model, [...]\" I agree it's conceptually strange to reason about intervening on exogenous variables, but not for that reason.  After all, in practice, we rarely observe all causes of endogenous variables (e.g., in a healthcare setting, many subtle biological factors will influence a patient's status, while only some biological indicators can be/are actually measured), so their values are, at least partially determined by factors outside the model.  The conceptual mismatch seems more rooted in the inability to influence those features or their status as logically outside the system under study.\n- line 180: \"The situation gets worse [...]\", where the preceding paragraph discusses causal formulas with interventions.  However, that paragraph didn't really discuss anything as being bad or problematic, so it's unclear what situation is getting worse, or what getting \"worse\" even means in this context.\n- lines 205-207: \"Explicitly mentioning the CBN M is necessary, since on the right-hand side of the conditional with left-hand side Y, we have all the parents of Y; what the parents are depends on M.\" However, the conditional being referred to here doesn't use notation like Pa(Y) (if it did, I would understand and agree with this point).  The conditional instead lists out \"$X_1 = x_1 ... X_m = x_m$, with those, in this case, corresponding to the parents of Y.  However, I don't see anything in the form of the conditional that requires that the right-hand side exclusively on the parents of the left-hand side.  If it's listing the variables out explicitly, there's no problem specifying \"CBN M\", but I don't see why it's necessary.\n- line 257-258: \"$Z = 1 | X = 0, Y = 0$ as saying 'if X were (set to) 0 and Y were (set to) 0, then Z would be 1\" My issue here is with the phrase \"set to\".  \"Set to\" implies intervention, but that would use an arrow, not an =.  I assume what this notation means if \"if X were (observed at) value 0 and Y were (observed at) value 0, then Z would be 1\"\n\n\nThe authors make a distinction throughout this paper between \"causal Bayesian networks\" and \"functional causal models\".  This is a useful distinction, but it's muddied by the authors' strange decision to simply call functional causal models \"causal models\", creating a frequent contrast between CBNs and causal models that implies that CBNs are not causal models.  This is even stranger in light of line 140, where the authors say \"a causal model can be viewed as a CBN\", suggesting that CBNs are a broader class....and yet they're somehow not 'causal models'??  I think this is just a terminology issue, but it's frequently confusing - I'd either find another term, say \"functional causal model\" throughout, or abbreviate it to FCM.\n- at the very least, make the notation consistent.  You don't actually say that \"causal model\" == \"functional causal model\" explicitly until line 123.  However, before that point, you switch between saying \"functional causal model\" (lines 31, 37, 41, 44), \"causal model\" (32, 47, 53, 72, 74...), and \"(functional) causal model (78).  I'm also unclear if the use of \"causal model\" in the introductions first two paragraphs are intended to only refer to \"functional causal models\".  I'm guessing not, but it's unclear when the transition takes place.\n\nPlease correct me if I'm wrong, but the motivation for this paper seems to be based on the findings of Beckers (2023) (since they show that Pearl's calculations are incorrect, this prompting the need for this paper to show how to do those calculations correctly).  However, looking for Beckers 2023, it's cited as an unpublished manuscript, so I'm not sure how to evaluate the motivation for this paper.  The authors do provide an example, presumably based on Beckers 2023, in footnote 1.  However, the example is strange (3 binary variables, two of which have deterministic dependencies) and the example query P(X = 1 | X = 1) seems nonsensical.  The authors don't go into any more detail about why Pearl's method for calculating probabilities is insufficient, they only give a strange toy example with deterministic dependencies, and I'm unable to look at the paper this work is based on (at least, I was unable to find it when looking at Beckers website); given this, it makes it very hard for me to assess the contribution of this paper since I can't understand the motivation and what problem it's trying to solve.\n\nThe biggest piece I'm missing, and the primary contributor towards my low score (along with the fuzziness around the Beckers result), is the lack of motivation for this work.  The authors say that there's a weakness in CBN theory (as exposed by Beckers 2023) and present a series of formalisms to calculate probabilities that over comes this weakness.  However, the negative effects of this weakness are never shown (apart from a toy example in a footnote), leaving the whole paper seeming like an interesting, but ultimately unimportant, mathematical exercise.  I don't mean that to come across as overly harsh, and I don't necessarily believe that this contribution is unimportant.  However, the authors have failed to show any evidence to the contrary.  If the authors can (1) discuss the limitations and pitfalls of using the calculations from Pearl and (2) provide a grounded example where such limitations could pose problems for causal estimation, I'm more than happy to raise my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "lines 17 and 33: we will clarify the issues you mentioned.\n\nlines 45-46: We think there's a natural reading of this material this\nis consistent with what we said.  Suppose that you intervene to set\nX=1. To find out the effect of this, you consult the structural\nequation.  That makes the equation the mechanism that determines how\nthe intervention works.\n\nl. 108: We did mean recursive model.\n\nl. 127: Although CBNs are typically taken to be acyclic, there is\ncertainly work on dealing with cyclic CBNs and BNs.  (See, for example,\nBaier et al., ON the foundation of cycles in Bayesian network,\nLecture Notes in Computer Science vol. 13360, pp. 343-363.)\n\nl. 155: good catch!  This is a typo\n\nl. 161: indeed, this is also a typo\n\nfootnote 5: We seem to have quite different views of exogenous\nvariables. We are willing to assume\nthat (at least, in some applications) there are reasonable models\nwhere you can observe all causes of endogenous variables.  It seems\n(to us) strange to limit the applicability of causal models to those\napplications where this is not the case.  That said, we agree that an\nagent in the system typically can't influence the value of an\nexogenous variable.\n\nl. 180: We'll clarify.  We meant that it gets harder to assign a\nprobability to a formula.\n\nl. 205: Even if we don't use the notation Pa(Y), we still have to\nexplicitly list all the parents of Y in M. Different choices of M\nwill in general involve different parents and hence result in different\nformulas.  So we do have to list the M explicitly.\n\nl. 257: \"Set to\" is closer to what we meant here.  We just made up\nthis notation temporarily to define what we really care about.  That\nsaid, you're right that we probably should have used <- rather than =.\n\n- Using FCM is a good suggestion.\n\nQuestion 1: Our paper is not really based on the findings of Beckers.\nThe only\nfact that we use from Beckers' paper is his observation that Pearl's\nprocedure gives incorrect results.  (Beckers does an analysis of why\nthe procedure is incorrect, and gives a more general example.)\nWe strongly disagree that the\nexample is nonsensical.\nPearl's procedure can clearly be applied to the\nformula X=1 in the model constructed, and gives the answer P(X=1|X=1)\n= 1/2, which is clearly incorrect.  It is up to the user of the\nprocedure to explain when it can (and can't) be applied.\nMathematically, one counterexample is sufficient\nto disprove a result. Beckers\nshows that the problem is rather deep, but it seemed inappropriate\nto steal his thunder, so to speak, by including this material in our\npaper.  Unfortunately, the paper is still an early draft, and is not\navailable on the web.\n\n\nRoughly speaking, Beckers shows that the problem is that the first step\nin Pearl's procedure\napplies conditioning only to the exogenous variables.  It should be\napplied to the joint\ndistribution on exogenous and endogenous variables.  While the two\napproaches agree in\nfunctional causal models, they do not agree in CBNs.  On the other hand,\napplying conditioning\nto the joint distribution typically breaks the independencies that are\nrequired for having a Markov\nfactorization.\n\n\nQuestion 2: We will give examples of the usefulness of our\napproach in the full paper.  We agree that this is important.\n\nQuestion 3: The f is the same on both sides of the equation. U_Y is a\nrandom variable (not an equation), and its values are functions. F_Y\ngets as input a value of each of the variables X_1, ..., X_n, and U_Y.\nGiven those values, it computes a value of Y. Since f is a function\nmapping values of X_1, ..., X_n to a value of Y, this equation does\nthe right thing.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper shows that interventional formulas of Causal Bayesian Netowrks are identifiable, assuming independence-of-mechanism (Pearl's concept of autonomy). The reviewers agree that the problem is important and quite interesting. Specifically, as one reviewer puts it, the paper builds off recent work showing that Pearl's proposed approach for calculating conditional probabilities involving interventions is incorrect. Using Pearl's concept of autonomy, the papers then build a series of formalisms to calculate arbitrary conditional probabilities in causal Bayesian networks and show how these formalisms relate CBNs and SCMs. This is important. As one reviewer points out, the independence-of-mechanism assumption is quite strong and should be even better justified. However, the authors addressed the issue well, admitting downsides but also providing interesting examples. Moreover, the link to Pearl's work is clear. So over all, I am with the authors and the other reviewers, and recommend to accept.
Decision: Accept (poster)