Intervention and Conditioning in Causal Bayesian Networks

Authors: sainyam  galhotra
joseph y halpern
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-06 21:07:44

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.

Main paper: 
 introduction: 
 Causal models play a pivotal role in elucidating the causal relationships among variables. These models facilitate a principled approach to understanding how various factors interact and influence 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 dynamics (Hicks 1979) . These examples underscore the versatility and utility of causal models for providing a 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 explain the outcome of complex ML systems (Galhotra, Pradhan, and Salimi 2021) ; and in AI-driven healthcare diagnostics, it is crucial to discern the effect of a particular intervention (like a change in treatment protocol) on 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 models1 and causal Bayesian networks (Pearl 2000) . Both are typically described using directed 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 a function of the values of its parents; there is also a probability on the values of root nodes. In a CBN, like in a Bayesian network, each variable Y is associated with a conditional probability 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 a 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. 2 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 an explicit reduction, nor does he give a formal definition of the probability of a formula in a CBN. Here, we do both. Using this approach leads to formulas having a 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 interventions 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) independencies in the underlying Bayesian network, as 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 = 0 ∧ Y = 0 ∧ [X ← 1](Y = 1) (X and Y have value 0, but if X is set to 1, Y gets value 1). Taking these latter equations to be independent is not always appropriate; 3 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 4 shows that any CBN can be converted to a compatible causal model that satisfies the independence assumptions that we are interested in. We show how counterfactual probabilities of necessity and sufficiency can be simplified and calculated in the appendix.2 Pearl (2000) [Theorem 7.1.7 ] provides a (correct) three-step procedure for calculating counterfactual probabilities in a causal model. But then on p. 220, Pearl says that the same procedure works for CBNs. Specifically, he says "counterfactual probabilities p(Yx = y | e) can still be evaluated using the three steps (abduction, action, and prediction) of Theorem 7.1.7. In the abduction phase, we condition the prior probability p(u) of 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 = 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 a trivial counterexample. Suppose that we have a 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 = 1 with probability 1. Y = U , and if Y = 1, then X = 0 with probability 1/2 and X = 1 with probability 1/2. Now consider p(X = 1 | X = 1). Applying Pearl's procedure, the probability of U = 1 continues to be 1 (no amount of conditioning will change that). Since there are no interventions, Y = 1 with probability 1, and X = 1 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 in any obvious way. 3 We thank Elias Bareinboim and Scott Muller for stressing this point. 
causal models and cbns: 
 In a (functional) causal model (also called a 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. A signature S is a tuple (U, V, R), where U is a set of exogenous variables, V is a set of endogenous variables, and R associates with every variable Y ∈ U ∪ V a nonempty set R(Y ) 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 R(Y ) for every endogenous variable Y ∈ V. F associates with each endogenous variable X ∈ V a function denotedF X such that F X : (× U ∈U R(U )) × (× Y ∈V-{X} R(Y )) → R(X). This mathematical notation just makes precise the fact that F X determines the value of X, given the values of all the other variables in U ∪ V.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 a new causal model, denoted M X←x , which is identical to 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 a total ordering ≺ of the endogenous variables such that if X ≺ Y , then X is not causally influenced by Y , that is, F X (. . . , y, . . .) = F X (. . . , y , . . .) for all y, y ∈ R(Y ). If 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 u for the exogenous variables in U, 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 a 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. 4A 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 a 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 a collection P of conditional probability tables (cpts), one for each (endogenous and exogenous) variable. 5 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 a 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 ∈ {0, 1} 2 , where the entry for (j, k) describes{P r(X = 0 | Y = j, Z = k). (There is no need to have an explicit entry for P(X = 1 | Y = j ∩ Z = k), since this is just 1 -P (X = 0 | Y = j ∩ Z = k).)The cpt for a root of the dag is just an unconditional probability, since a root has no parents.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 a CBN M results in a new CBN, denoted M X←x , 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 a cpt. It is also worth noting that a causal model can be viewed as a CBN; the equation Y = F ( x) can be identified with the entryP (Y = F ( x)) | X = x) = 1 in a cpt.3 Giving semantics to formulas in CBNs 
the problem: 
 Consider the following (standard) language for reasoning about causality: Given a signature S = (U, V, R), a primitive event is a formula of the form X = x, for X ∈ V and x ∈ R(X In a probabilistic causal model (M, Pr), we can assign a probability to formulas in L by taking the probability of a formula ϕ in M , denoted Pr(ϕ), to be Pr({ u : (M, u) |= ϕ}). Thus, the probability of ϕ in M is simply the probability of the set of contexts in which ϕ is true; we can view each formula as corresponding to an event.When we 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 a truth value for formulas that do not involve interventions; call such formulas simple formulas. Thus, we can compute the truth of a simple formula ϕ in a context, and then using the probability of contexts, determine the probability of ϕ in a CBN M . But what about a causal formula such as ψ = [ Y ← y]ϕ? Given a context u, we can determine the model M = M Y ← y .In (M , u), ϕ 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, u). But note that ψ does not correspond to an event in M , although we assign it a probability.It gets harder to evaluate probability if we add another conjunct ψ and consider the formula ψ ∧ ψ . While we can use the procedure above to compute the probability of ψ and ψ individually in (M, u), 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 (probabilistically) independent. In a causal model, the mechanism for a given variable (specifically, the outcome after the intervention) is an event, so we can talk about mechanisms being independent. While it is not an event in a CBN, we nevertheless use the assumption that mechanisms are independent to guide how we determine the probability of formulas in L in a CBN.To describe our approach, we must first make clear what we mean by mechanisms (cpts) being independent. This has two components: the outcomes of cpts for different variables are independent, and for the cpt for a single variable Y, the outcomes for different settings of the parents of Y are independent. 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 cpts involving different variables are independent 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 Y 1 in a CBN M with parents X 1 . . . , X m . We want to consider events of the formY 1 = y 1 | (X 1 = x 1 , . . . , X m = x m ), which we read "Y 1 = y 1 given that X 1 = x 1 , .. . , and X m = x m ". Such events have a probability, given by the cpts for Y 1 . 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 1 ← j 1 , . . . , X m ← j m ](Y 1 = 1). This identification already hints at why we we care about conditional events (and their independence). Suppose for simplicity that m = 1. To determine the probability of a formula such asX 1 = 0 ∧ Y 1 = 0 ∧ [X 1 ← 1](Y 1 = 1)we need to apply both the entry in the cpt for Y 1 = 0 | X 1 = 0 and the entry for Y 1 = 1 | X = 1. They each give a probability; the probability of the formulaX 1 = 0 ∧ Y 1 = 0 ∧ [X 1 ← 1](Y 1 = 1) is the probability that the conditional events Y 1 = 0 | X 1 = 0 and Y 1 = 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 Y 1 ).This is an instance of independence within a cpt; 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 asY 1 = 0 | X 1 = 1 and Y 1 = 1 | X 1 = 1, are not independent.) Independence for cpts of different variables is most easily explained by example: Suppose that Y 2 has parents X 1 and X 3 . Then we want the eventsY 1 = 0 | X 1 = 0 and Y 2 = 1 | (X 1 = 0, X 3 = 1)to be independent. This independence assumption will be needed to compute the probability of formulas such as[X 1 ← 0](Y 1 = 0) ∧ [X 1 = 0, X 3 = 1](Y 2 = 1).As we said, we in fact want to view all the relevant conditional events as mutually independent.7 Although we use the term "conditional event", these are not events in 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 Y 1 = 0 | X 1 = 1 corresponds to the set of contexts where the formula[X 1 ← 1](Y 1 = 1) is true.Starting with a CBN M , we will be interested in causal models for which the probability P (Y 1 = 0 | X 1 = 1), as given by the cpt for Y 1 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 to be a conjunction consisting of the choice of one conditional event for M for each endogenous variable X and each setting of the parents of X. A fixed-context ccce (fccce) involves fewer conjuncts; we have only conditional events where for all the exogenous parents U of a 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).Example 3.1. Consider the CBN M * with the following dag: U X Y , where all variables are binary, and the cpts give the following probabilities:P (U = 0) = a, P (X = 0 | U = 0) = b, P (X = 0 | U = 1) = c, P (Y = 0 | X = 0) = d, and P (Y = 0 | X = 1) = e.Then a ccce consists of 5 conjuncts:• one of U = 0 and U = 1;• one of X = 0 | U = 0 and X = 1 | U = 0; • one of X = 0 | U = 1 and X = 1 | U = 1; • one of Y = 0 | X = 0 and Y = 1 | X = 0; and • one of Y = 0 | X = 1 and Y = 1 | X = 1.An fccce consist of only 4 conjuncts; it has only one of the second and third conjuncts of a ccce. In particular, if U = 0 is a conjunct of the fccce, then we have neitherX = 0 | U = 1 nor X = 1 | U = 1 as a conjunct; similarly, if U = 1 is a conjunct, then we have neither X = 0 | U = 0 nor X = 1 | U = 0 as a conjunct.(This is what we meant above by saying that each exogenous parent U of X must have the same value as in conjunct that determines U 's value.)It is not hard to show that, in this case, there are 32 ccces and 16 fccces. Moreover, (in this example and in general) each fccce is equivalent to a disjunction of ccces. The number of ccces and fccces 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 n parents, each of them binary, there are 2 n possible settings of the parents of Y , and we must choose one value of Y for each of these 2 n settings, already giving us 2 2 n 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 = 1 | X = 0, Y = 0 as saying "if X were (set to) 0 and Y were (set to) 0, then Z would be 1", then given a ccce and a formula ϕ ∈ L and context u, we can determine if ϕ is true or false. We formalize this shortly. We can then take the probability of ϕ to be the sum of the probabilities of the ccces that make ϕ 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 ccce, and hence the probability of any formula ϕ. 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.1, there are two fccces where ϕ= X = 0 ∧ Y = 0 ∧ [X ← 1](Y = 1) is true: (a) U = 0 ∧ (X = 0 | U = 0) ∧ (Y = 0 | X = 0) ∧ (Y = 1 | X = 1); and (b) U = 1 ∧ (X = 0 | U = 1) ∧ (Y = 0 | X = 0) ∧ (Y = 1 | X = 1). Each of these two fccces is the disjunction of two ccces, which extend the fccce by adding a fifth conjunct.For example, for the first fccce, we can add either the conjunct X = 0 | U = 1 or the conjunct X = 1 | U = 1. The total probability of these two fccces is abd(1 -e) + (1 -a)cd(1 -e);(Y = 0 | U = 0, X = 0) = f 1 , P (Y = 0 | U = 0, X = 1) = f 2 , P (Y = 0 | U = 1, X = 0) = f 3 , P (Y = 0 | U = 1, X = 1) = f 4 . U X YNow there are 128 ccces, but only 16 fccces; the formula ϕ= X = 0 ∧ Y = 0 ∧ [X ← 1](Y = 1) is true in only two of these fccces: (a) U = 0 ∧ (X = 0 | U = 0) ∧ (Y = 0 | (U = 0, X = 0)) ∧ (Y = 1 | (U = 0, X = 1)); and (b) U = 1∧)X = 0 | U = 1) ∧ (Y = 0 | (U = 1, X = 0)) ∧ (Y = 1 | (U = 1, X = 1)). It is easy to check that Pr M † (ϕ) = abf 1 (1 -f 2 ) + (1 -a)cf 3 (1 -f 4 ).The calculation of the probability of ϕ is essentially the same in M * and M † .We denote by Pr M (ϕ) the probability of a formula ϕ in a CBN or causal model M . (We provide a formal definition of Pr M (ϕ) for a CBN M at the end of Section 3.)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 ccce (resp., fccce) determines the truth of a formula in L + (S) (resp., L(S)) in a causal model. To make this precise, we need a few definitions. We take the type of a CBN M = (S, P), where S = (U, V, R) to consist of its signature S 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 ) has the same type asM if S = (U ∪ U , V, R ), where U is arbitrary, R | U ∪V = R,and F is such that each endogenous variable X depends on the same variables in U ∪ V according to F as it does according to the type of M (but may also depend on any subset of U ).Definition 3.4. For the conditional event Y = y | (X 1 = x 1 , . . . , X m = x m ), let the corresponding formula be [X 1 ← x 1 , . . . , X m ← x m ](Y = y).(Note that the corresponding formula may be in L + -L, since some of the X i s may be exogneous.) Let ϕ α ∈ L + (S), the formula corresponding to the ccce α, be the conjunction of the formulas corresponding to the conditional events in α. We can similarly define the formula corresponding to an fccce.Example 3.5. In the modelM † of Example 3.3, if α is the fccce U = 0 ∧ (X = 0 | U = 0) ∧ (Y = 0 | (U = 0, X = 0)) ∧ (Y = 1 | (U = 0, X = 1)), then ϕ α is U = 0 ∧ [U ← 0]X = 0 ∧ [U ← 0, X ← 0](Y = 0) ∧ [U ← 0, X ← 1](Y = 1).Say that a formula ψ is valid with respect to a CBN M if (M , u) |= ψ for all causal settings (M , u), where M is a 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) α, then for all formulas ψ ∈ L + (S) (resp., ψ ∈ L(S)) either ϕ α ⇒ ψ is valid with respect to M or ϕ α ⇒ ¬ψ is valid with respect to M .Proof: We show that if two causal models M 1 and M 2 have the same type as M and u 1 and u 2 are contexts such that (M 1 , u 1 ) |= ϕ α and (M 2 , u 2 ) |= ϕ α , then for all formulas ψ ∈ L + (S) (resp., ψ ∈ L(S)), we have thatEQUATIONThe claimed result follows immediately. The details of the proof can be found in the appendix.Based on this result, we can take the probability of a formula ϕ ∈ L + (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 as M , and the probability Pr is such that all the cpts in M get the right probability in M . More precisely, for each endogenous variable Y in M , if X 1 , . . . , X k are the parents of Y in M , then for each entryP (Y = y | X 1 = x 1 , . . . , X k = x k ) = a in the cpt for Y , Pr is such that the corresponding formula [X 1 ← x 1 , . . . , X k ← x k ](Y = y) gets probability a. (M , Pr)is i-compatible with M (the i stands for independence) if it is compatible with M and, in addition, Pr is such that the events described 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 cpt for a given variable. Thus, for example, if (x 1 , . . . , x k ) = (x 1 , . . . , x k ), then we want the events described by[X 1 ← x 1 , . . . , X k ← x k ](Y = y) and [X 1 ← x 1 , . . . , X k ← x k ](Y = y)to be independent (these are different entries of the cpt for Y ); and if Y = Y and has parents X 1 , . . . , X m in M , then we want the events described by[X 1 ← x 1 , . . . , X k ← x k ](Y = y) and [X 1 ← x 1 , . . . , X m ←x m ](Y = y ) to be independent (these are entries of cpts for different variables).Theorem 3.7. Given a CBN M and a formula ϕ ∈ L + (S), the probability of ϕ is the same in all causal models M i-compatible with M .Proof: It follows from Theorem 3.6 that the probability of ϕ is the sum of the probabilities of the formulas ϕ α for the ccces α such that ϕ α ⇒ ϕ is valid. It is immediate that these formulas have the same probability in all causal models i-compatible with M .Formally, we take Pr M (ϕ), the probability of ϕ in the CBN M , to be Pr M (ϕ) 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.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 ϕ ∈ L + being a sum of products of entries in the cpt. Thus, we 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 cpt 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 ccces. For one thing, it follows from Theorem 3.6 that to compute the probability of ϕ ∈ L, it suffices to consider fccces. Moreover, when computing Pr M (ϕ) where ϕ involves an intervention of the form X ← x, we can ignore the entries in the cpts involving X, and for variables for which X is a parent, we consider only entries in the cpts where X = x. We can also take advantage of the structure of the formula whose probability we are interested in computing to further simplify the computation, although the details are beyond the scope of this paper.Third, as mentioned above, a 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, a context not only determines a state; it determines a state for every intervention. We can view a formula involving interventions as an event in a space whose elements are functions from interventions to worlds. Since a context can be viewed this way, we can view a 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 a 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 cpts involving different variables are independent is equivalent to the (conditional) independence assumptions made in Bayesian networks. More precisely, given a CBN M , let M be the non-probabilistic causal model constructed above. They show that if the probability Pr makes interventions on different variables independent (i.e., ifPr ( U , f 1 , . . . , f m ) = Pr( u) × Pr Y1 (f 1 ) × • • • × Pr Ym (f m ), as 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 = 0∧Y = 0∧[X ← 1](Y = 1), for which we need to consider (simultaneously) 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 software) 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, Lourenc ¸o, Freire, Meliou, and Srivastava 2022) . With this infor-mation, a 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 B solve the problem" using our techniques.2. Manufacturing pipelines across various industries, such as semiconductor fabrication, pharmaceuticals, 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, pressure, and other factors that can influence the quality, efficiency, and consistency of the final product. For instance, in semiconductor fabrication, precise control of environmental conditions like temperature and humidity is crucial to ensuring the integrity of the microchips produced (Wu 2008) . Similarly, in pharmaceutical manufacturing, sensors monitor parameters 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 increase of 3 degrees Celsius would result in a 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.X for Y : PNS X,Y M = Pr M ([X ← 1](Y = 1) ∧ [X ← 0](Y = 0)).Let P a X (Y ) consist of all the parents of Y other than X. For a set Z of variables, let T Z consist of all possible settings of the variables in Z.Theorem 5.2. If M is a CBN where Y is a child of X, then (a) PN X,Y M = c j P a X (Y ) ∈T P a X (Y ) Pr M (P a X (Y ) = c j P a X (Y ) | Y = 1 ∧ X = 1) Pr M (Y = 0 | X = 0 ∧ P a X (Y ) = c j P a X (Y ) ); (b) PS X,Y M = c j P a X (Y ) ∈T P a X (Y ) Pr M (P a X (Y ) = c j P a X (Y ) | Y = 0 ∧ X = 0) Pr M (Y = 1 | X = 1 ∧ P a X (Y ) = c j P a X (Y ) ); (c) PNS X,Y M = PS X,Y M • Pr M (X = 0 ∧ Y = 0) + PN X,Y M • Pr M (X = 1 ∧ Y = 1).We defer the proof of the theorem to Section B.1 in the appendix, where further extensions are also provided.A Proof of Theorem 3.6Proof: As we said, we show that if two causal models M 1 and M 2 have the same type as M and u 1 and u 2 are contexts such that (M 1 , u 1 ) |= ϕ α and (M 2 , u 2 ) |= ϕ α , then for all formulas ψ ∈ L + (S) (resp., ψ ∈ L(S)), we have that (1) (as defined in the main text) holds. The claimed result follows immediately.We give the proof in the case that α is a ccce and ψ ∈ L + (S). The modifications needed to deal with the case that α is an fccce and ψ ∈ L(S) are straightforward and left to the reader. Since M is acyclic, we can order the exogenous and endogenous variables topologically. Let X 1 , . . . , X m be such an ordering. We first prove by induction on j that, for all interventions Y ← y (including the empty intervention) andx j ∈ R(X j ), (M 1 , u 1 ) |= [ Y ← y](X j = x j ) iff (M 2 , u 2 ) |= [ Y ← y](X j = x j ).For the base case, X 1 must be exogenous, and hence have no parents. If X 1 is not one of the variables in Y , then we must have(M 1 , u 1 ) |= [ Y ← y](X 1 = x 1 ) iff (M 1 , u 1 ) |= (X 1 = x 1 ), and similarly for M 2 ; since no variable in Y is a parent of X 1 , intervening on Y has no effect on X 1 . Since (M 1 , u 1 ) |= ϕ α and (M 2 , u 2 ) |= ϕ α , M 1 and M 2 agree on the values of variables in U. Thus,(M 1 , u 1 ) |= (X 1 = x 1 ) iff (M 2 , u 2 ) |= (X 1 = x 1 ). It follows that (M 2 , u 2 ) |= [ Y ← y](X 1 = x 1 ). (M 2 , u 2 ) |= [ Y ← y](X 1 = x 1 ), as desired.On the other hand, if X 1 is one of the variables in Y (which can happen only if the formula is in L + (S)), let x * be the value in y corresponding to X 1 . In that case, the formula[ Y ← y](X 1 = x * ) is valid with respect to M . It follows that (M 1 , u 1 ) |= [ Y ← y](X 1 = x 1 ) iff x 1 =x * , and similarly for (M 2 , u 2 ). The desired result follows. This completes the proof for the base case.Now suppose that we have proved the result for j < m. Let Z 1 , . . . , Z k be the parents ofX j+1 in M . Since X 1 , . . . , X m is a topological sort, we must have {Z 1 , . . . , Z k } ⊆ {X 1 , . . . , X j }. Let z 1 , . . . , z k be values in R(Z 1 ), . . . , R(Z k ), respectively, such that (M 1 , u 1 ) |= [ Y ← y](Z h = z h ), for h = 1, . . . , k. By the induction hypothesis, (M 2 , u 2 ) |= [ Y ← y](Z h = z h ), for h = 1, . . . , k. Moreover, it is easy to see that ([ Y ← y]ϕ ∧ [ Y ← y]ϕ )) ⇔ [ Y ← y](ϕ ∧ ϕ ) is valid with respect to M . Thus, (M 1 , u 1 ) |= [ Y ← y](Z 1 = z 1 ∧ . . . Z k = z k )and similarly for (M 2 , u 2 ). Moreover, since Z 1 , . . . , Z k are the parents of X j+1 , it follows that(M 1 , u 1 ) |= [ Y ← y](X j+1 = x j+1 ) iff [Z 1 = z 1 ∧ . . . Z k = z k )](X j+1 = x j+1) is a conjunct of ϕ α . Since (M 1 , u 1 ) |= ϕ α and (M 2 , u 2 ) |= ϕ α , the desired result follows, completing the induction proof.The argument that(M 1 , u 1 ) |= [ Y ← y]ψ iff (M 2 , u 2 ) |= [ Y ← y]ψfor arbitrary (simple) formulas ψ now follows from the fact that (as we already observed)([ Y ← y]ϕ ∧ [ Y ← y]ϕ )) ⇔ [ Y ← y](ϕ ∧ ϕ ) is valid with respect to M , as are ([ Y ← y]ϕ ∨ [ Y ← y]ϕ )) ⇔ [ Y ← y](ϕ ∨ ϕ ) and [ Y ← y]¬ϕ ⇔ ¬[ Y ← y]ϕ.Finally, we can deal with Boolean combinations of causal formulas by a straightforward induction. This completes the argument that (1) holds for all formulas in ψ ∈ L + (S).B.1 Proof of Theorem 5.2We prove the calculation for the probability of sufficiency, PS X,Y M . Essentially the same argument can be used to compute the probability of necessity, PN X,Y M . Finally, for part (c), we use the representation of PNS X,Y M in terms of PS X,Y M and PN X,Y M given in (Pearl 2000, Lemma 9.2.6 ).Proof of Theorem 5.2 (b). Let Z = U ∪ V \ {X, Y }. T Z has 2 n-2 settings, where n = |U ∪ V|. For a setting c ∈ T Z , let c Z be the setting of the variable Z in c.EQUATIONLet the numerator (X = 0) ∧ (Y = 0) ∧ [X ← 1](Y = 1) be ψ. Then we havePr M (ψ) = c∈T Z Pr M ((X = 0) ∧ (Y = 0) ∧ [X ← 1](Y = 1) ∧ Z∈Z (Z = c Z )).We next compute the probability ofψ c = (X = 0) ∧ (Y = 0) ∧ [X ← 1](Y = 1) ∧ Z∈Z (Z = c Z ).From Theorem 3.6, it follows that in all causal models M compatible with M ,Pr M (ψ c ) = ϕα =⇒ ψc Pr M (ϕ α ).Now ϕ α =⇒ ψ c holds whenever α contains the following events:1. (X = 0 | P a(X) = c P a(X) ) 2. (Y = 0 | X = 0, P a X (Y ) = c P a X (Y ) ) 3. (Y = 1 | X = 1, P a X (Y ) = c P a X (Y ) ) 4. (Z = c Z | P a(Z) = c P a(Z) ), for all Z ∈ Z.Let S c consist of all ccces that contain these four events, and let ϕ Sc be the conjunction of the formulas corresponding to the events in S c . Then by Theorem 3.6,ϕ c ⇔ α∈Sc ϕ α .Since the formulas ϕ α for distinct ccces in S c are mutually exclusive, we have that Pr M (ψ c ) = Pr M (ϕ S ). Therefore,Pr M (ψ) = c∈T Z Pr M (ϕ c ) = c∈T Z Pr M (X = 0 ∧ Y = 0 ∧ Z∈Z (Z = c Z ) ∧ [X ← 1, P a X (Y ) ← c P a X (Y ) ](Y = 1)) = c P a X (Y ) ∈T P a X (Y ) Pr M (X = 0 ∧ Y = 0 ∧ P a X (Y ) ← c P a X (Y ) ∧ [X ← 1, P a X (Y ) ← c P a X (Y ) ](Y = 1)).If M is i-compatible with M , then we can further conclude thatc∈T Z Pr M (X = 0 ∧ Y = 0 ∧ Z∈Z (Z = c Z ) ∧ [X ← 1, P a X (Y ) ← c P a X (Y ) ](Y = 1)) = c P a X (Y ) ∈T P a X (Y ) Pr M (X = 0 ∧ P a X (Y ) = c P a X (Y ) ) Pr M (Y = 0 | X = 0 ∧ P a X (Y ) = c P a X (Y ) ) Pr M (Y = 1 | X = 1 ∧ P a X (Y ) = c P a X (Y ) ) = c P a X (Y ) ∈T P a X (Y ) Pr M (Y = 0 ∧ X = 0 ∧ P a X (Y ) = c P a X (Y ) ] Pr M [Y = 1 | X = 1 ∧ P a X (Y ) = c P a X (Y ) ).Since Pr M (ψ) = Pr M (ψ), substituting the expression for Pr M (ψ) into (2), we getPS M = c P a X (Y ) ∈T P a X (Y ) Pr(Y = 0 ∧ X = 0 ∧ P a X (Y ) = c P a X (Y ) ) Pr(Y = 1 | X = 1 ∧ P a X (Y ) = c P a X (Y ) )Pr(X = 0 ∧ Y = 0) , as desired.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 P a(Y ) would change to the set of the ancestors of Y at the same level as X in the topological ordering of the variables. We can further extend Theorem 5.2 to arbitrary formulas ψ, where Pr(ψ) 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 ψ to a disjunction of conjunctions, where the disjuncts are mutually exclusive and have the form ψ i = ψ i0 ∧ j∈{1,...,r} ψ ij , where ψ i0 = j∈{1,...,s} (Z ij = z ij ) is a simple formula (with no intervention), and ψ ij for j > 0 has the form [ X j ← x j ]( k∈{1,...,t} Y ijk = y ijk ), where Y ijk is a descendant of X j 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 • 2 nr * ) conditional probability calculations, where r * is the maximum number of conjuncts in a disjunction ψ i that involve at least one intervention, and m is the number of disjuncts in the DNF. Unfortunately, for an arbitrary formula ψ, determining Pr(ψ) may involve doubly-exponentially many conditional probabilities. We defer details to Section ?? in the appendix.Theorem B.1. Given a CBN M = (S, P) and an arbitrary formila ψ, then Pr(ψ) 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 can be estimated from observational data. To prove this result, we first convert ψ to an equivalent formula in a canonical form. Specifically, it has the form ψ 1 ∨ • • • ∨ ψ m , where the ψ i s are mutually exclusive and each ψ i is a conjunction of the form ψ i0 ∧ • • • ∧ ψ iri , where ψ i0 is a simple formula and for 1 ≤ j ≤ r i , ψ ij is a formula of the form [ X j ← x j ]( k∈{1,...,tij } Y ijk = y ijk ), and the interventions are all distinct. This conversion just involves standard propositional reasoning and two properties which hold under the semantics described in Section 3. The first is that[Y ← y]ϕ ∧ [Y ← y]ϕ is equivalent to [Y ← y](ϕ ∧ ϕ ). The second is that ¬[Y ← y]ϕ is equivalent to [Y ← y]¬ϕ.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 ϕ to an equivalent formula in DNF, where the literals are either simple formulas or intervention formulas (i.e., formulas of the form [X ← x]ϕ). Of course, the disjuncts may not be mutually exclusive. Again, using straightforward propositional reasoning, we can convert the formula to a DNF where the disjuncts are mutually exclusive. Rather than writing out the tedious details, we give an example. Consider a formula of the form (ϕ 1 ∧ ϕ 2 ) ∨ (ϕ 3 ∧ ϕ 4 ). This is propositionally equivalent to(ϕ 1 ∧ ϕ 2 ∧ ϕ 3 ∧ ϕ 4 ) ∨ (ϕ 1 ∧ ϕ 2 ∧ ¬ϕ 3 ∧ ϕ 4 ) ∨ (ϕ 1 ∧ ϕ 2 ∧ ϕ 3 ∧ ¬ϕ 4 ) ∨ (ϕ 1 ∧ ϕ 2 ∧ ¬ϕ 3 ∧ ¬ϕ 4 ) ∨(¬ϕ 1 ∧ ϕ 2 ∧ ϕ 3 ∧ ϕ 4 ) ∨ (ϕ 1 ∧ ¬ϕ 2 ∧ ϕ 3 ∧ ϕ 4 ) ∨ (¬ϕ 1 ∧ ¬ϕ 2 ∧ ϕ 3 ∧ ϕ 4 ).We can now apply the two equivalences mentioned above to remove leading negations from intervention formulas and to ensure that, in each disjunct, all interventions are distinct. These transformations maintain the fact that the disjuncts are mutually exclusive. Since the disjuncts in ψ are mutually exclusive, the probability of ψ is the sum of the probabilities of the disjuncts; that is, Pr(ψ) = i∈{1,...,m} Pr(ψ i ). To compute the probability of a disjunct ψ i , 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 ∧ [X ← x, Z ← z](Y = 1)), the intervention X ← x is redundant and can be dropped; for example, X= 0 ∧ [X ← 0, Z ← 1](Y = 1) is equivalent to X = 0 ∧ [Z ← 1](Y = 1). Second, if an intervention formula does not contain a descendant of the intervened variables, such as ψ = [ X ← x](ψ 1 ∧ ψ 2 ), where all variables in ψ 1 are non-descendants of the variables in X, then the variables in ψ 1 are not affected by the intervention, so ψ 1 can be pulled out of the scope of the intervention; that is, ψ is equivalent to ψ 1 ∧ [X ← x](ψ 2 ). 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.• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 authors should reflect on how these assumptions might be violated in 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 a few datasets or with a 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 approach. For example, a 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 to provide closed captions for online lectures because it 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 address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.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 supplementary 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • 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 a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
converting a cbn to a (probabilistic) causal model: 
 Our semantics for formulas in CBNs reduced to considering their semantics in i-compatible causal models. It 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 X 1 , . . . , X n , we add a new exogenous variable Balke and Pearl (1994) call such an exogenous variable a response function.U Y ; R(U Y ) consists of all functions from R(X 1 ) × • • • × R(X n ) to R(Y ).(Response functions, in turn, are closely related to the potential response variables introduced by Rubin (1974) .) We take U Y to be a parent of Y (in addition to X 1 , . . . , X n ). We replace the cpt for Y be the following equation for Y ; F Y (x 1 , . . . , x n , f ) = f (x 1 , . . . , x n ), where f is the value of U Y . Since f is a function from R(X 1 ) × • • • × R(X n ) to R(Y ),(f ) = Π x∈R(X1)×•••×R(Xn) Pr(Y = f (x 1 , . . . , x n ) | X 1 = x 1 , . . . , X n = x n ).This makes interventions for different settings of X 1 , . . . , X n independent, which is essentially what we assumed in the previous section when defining the probability of formulas in L in M 0 , in addition to making interventions on 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(U) × R(U Y1 ) × R(U Ym ), the contexts in M . Moreover, M is clearly a causal model with the same type as M that is i-compatible with M .We can easily modify this construction to get a family of causal models compatible with M , by loosening the requirements on Pr . While we do want the marginal of Pr on U to agree with the marginal of Pr on U, and we want it to reproduce the probability of the cpt for each variable Y i (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. ({(u, f X , f U , f Y ) : u = 0}) = 1, Pr * * ({(u, f X , f Y ) : f X (0) = 0}) = 1/2, and Pr * * ({(u, f X , f Y ) : f Y (0) = 0}) = 1/2, so thatPr * * agrees with the three cpts. But this still leaves a lot of flexibility. For example, we might have (Tian and Pearl (2000) give bounds on the range of probabilities for this formula, which is called the probability of necessity; see also Section B and (Pearl 2000, Section 9.2).)Pr * * ({(u, f X , f Y ) : f X (0) = f Y (0) = 0} = P r * * ({(u, f X , f Y ) : f X (1) = f Y (1) = 1} = 1/2 (so that Pr * * ({(u, f X , f Y ) : f X (0) = 0, f Y (1) = 1}) = Pr * * ({(u, f X , f Y ) : f X (0) = 1, f Y (1) = 0}) = 0). As shown in Example 3.2, Pr M * (X = 0 ∧ Y = 0 ∧ [X ← 1](Y = 1)) = 1/4. However, it is easy to check that Pr M * * (X = 0 ∧ Y = 0 ∧ [X ← 1](Y = 1)) = 1/2.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 conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [NA] Justification: We do not have experimental results.• The answer NA means that the paper does not include experiments.• 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 a 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 to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are 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., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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 (Hoerl, McCormack, and Beck 2011) , epidemiology (Greenland and Robins 1999) , and political science (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; we focus on them in this section. As discussed by Pearl (2000) , counterfactual analysis is particularly useful when it comes to understanding the impact 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 is 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. Pearl (2000) gives examples showing that neither the probability of necessity nor the probability of sufficiency in a 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.Question: Does the paper provide open access to the data and code, with sufficient instructions 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?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 be presented in the core of the paper to a 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, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate 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 are accompanied by error bars, confidence 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is 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 are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: We do not have experiment results.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 (if applicable), such as the institution conducting the review.Unless specified, in this paper, "causal models" refer to "functional causal models".38th Conference on Neural Information Processing Systems (NeurIPS2024).Note that the equation for an endogenous variable X with no parents must be a constant function; e.g., FX = 3. In the model MX←x that results from M after intervening on X, X is an endogenous variable with no parents.Some authors (e.g.,Pearl (2000) seem to assume that CBNs do not include exogenous variables. We find it useful to allow them.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.This 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 a single cpt for contexts. Nothing in the rest of the discussion would change if we did this. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_summary: They define counterfactual probability for causal Bayesian networks as the probability of i-compatible causal models.

In the appendix, they show how to calculate counterfactual probabilities and necessary/sufficient probabilities.
strength_weakness: strength_weakness: Exponential complexity

Lots of things in the appendix

Some proofs are hard to understand

A lot of the motivation depends on an unpublished Becker paper and an unnamed NeurIPS submission
questions: 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?

>p2 footnote: p(umide).
that should be p(u|e) ?

Does 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)

What probability do you obtain in this example, if you calculate it according to your definition of counterfactual probability?

>4 159 for the exogenous variables 

are those not the endogenous variables?

>4 161 , u)_Y ..

should that be , u_Y..) ?

(there are also parenthesis missing in p9 401 and elsewhere)

>5 199 In fact, in another NeurIPS submission (with a different set of authors)

are the authors also independent?

>5 213 the probability that the conditional events Y1 = 0 | X1 = 0 and Y1 = 1 | X = 1  hold simultaneously.

would that not be  [X1 ← 0](Y1 = 0) ∧ [X1 ← 1](Y1 = 1) ? 

or is it the same? why would it be the same?

>7 316  all the cpts in M get the right probability in M 

"in M" twice? Is on of them supposed to be "M'"?


>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).

and there are no unobserved variables?

>p11 section B

there is a lot of text here in the appendix which is hardly referenced by the main text. 

are the results here less important?

>p13 557 in S. .. φ_S 

what is S and φ_S? is that S_c? and then φ_c?

>p15 593 ψ_ic = Pr_M(/\..)

{1,..,s} that is {1,..,s_i} ?

ψ_ic is the formula /\...., not the Pr_M ?
 
 
>p15 595ff c_Pa(..)

c_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}.
Do you prove somewhere that there is no Z_{ij} with Pa(Z) = Z_{ij}?

>p16 617 "in S"

what is S?
limitations: limitations: yes
paper_summary: paper_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).
strength_weakness: strength_weakness: 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

- The outcomes of opts for different variables are independent.
- For the opt of a single variable $Y$, the outcomes under different settings of $Y$'s parents are independent.
- We have available all the basic ccce formulas.

The 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. 

What 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.

My 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.

Moreover, 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.
questions: questions: 1. Can you give a nontrial, meaningful example where Peal's "abduction, action, and prediction" procedure fails (footnote 1)?
2. 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: limitations: I would suggest the authors to include their limitations (e.g., assumption, computational cost) in the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: The results make sense to me and I don't have any specific questions for now.
limitations: limitations: OK.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
- 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".
- 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.
- 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...
- 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?
- 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?)
- 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.
- 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 

$\vec{u}_{\vec{Y} \leftarrow \vec{y}}$.  So should the initial line instead be 

$(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)
- 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.
- 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.
- 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.
- 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"


The 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.
- 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.

Please 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.

The 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.
questions: questions: Is the unpublished Beckers 2023 manuscript available anywhere?  If not, can you describe the main argument of that work?

What 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.

In 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: limitations: I'm unclear about the applicability and use case of this work, so I'm not sure what the limitations could be.


I'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.

Comments: title: Example applications
Response to the first question about the counterexample
comment: We will check with Beckers about the timeline. We'll also add a
discussion to the paper (from Beckers' paper) explaining why the problem
is deeper than just a counterexample. We thank you for
engaging with us and appreciate your willingness to raise your
score!
I appreciate the authors' clarifying comments and examples and apologize for not responding sooner.  This paper is in a weird spot for me since a lot of the motivation is currently unavailable, and it's unclear when Beckers' paper will be made public.  If the timing is just off by a couple of months, and Beckers' findings should be available publicly by NeurIPS or shortly thereafter, then this is less of an issue.  However, if Beckers' findings will still be an unpublished and unavailable manuscript a year from now, then this publication seems premature.

Those concerns aside, I think the authors did address some of my concerns adequately and, with their proposed modifications, I'm happy to raise my score.
> "Question 2: We will give examples of the usefulness of our
> approach in the full paper. We agree that this is important."

> Would it be possible to provide an example now (or at least a sketch of
> what this will look like)?

Sure!  Generally, any setting where exogenous variables can be observed
would directly benefit from our results. We present two diverse example
scenarios here.
(i) While debugging systems (ml pipelines, database engines
or any general software) and network failures,
users have access to all parameters
related to the code and the execution environment [1,2].
With this information, a 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
B solve the problem", using our techniques.


(ii) Manufacturing pipelines across various industries,
such as semiconductor fabrication, pharmaceuticals,
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 on
variables such as temperature, humidity, pressure, and other
factors that can influence the quality, efficiency, and consistency
of the final product. For instance, in semiconductor fabrication,
precise control of environmental conditions like temperature and
humidity is crucial to ensuring the integrity of the microchips
produced [3]. Similarly, in pharmaceutical manufacturing, sensors monitor
parameters like pH levels and chemical concentrations to maintain
the efficacy of the drugs being produced.
Thus, we can address queries with what probability would a
temperature increase of 3 degrees Celsius result in a poor quality product,
given that the humidity is high.


Other potential applications of our framework include
(a) modelling player performance in sports by considering factors like
injury, skill, sports facilities, etc.
(b) urban planning scenarios to analyze the impact of zoning laws, interest
rate and other factors on house prices
(c) modelling agriculture yield by considering variables like
soil quality, weather conditions.
(d) transportation applications like railway operation management,
where data is collected from different sensors and monitoring devices
about track integrity, train speed, braking performance,
and environmental variables such as temperature and precipitation.
In this case, environment information is exogenous as it can not be
intervened on.

As can be seen, there is no lack of applications!
Thanks again for your comments.

> To your point that your paper isn't really based on the findings of
> Beckers, maybe 'based' isn't the right word, but at the very least it
> seems somewhat dependent on the findings of Beckers.

The paper was certainly motivated by Beckers' observation, but is
not dependent on it.  That said, once we appreciated Beckers'
observation, our reaction was pretty much what you said: "We want to
calculate
probabilities under intervention and conditioning. The classic method
of doing that in CBNs doesn't actually work, as shown by
Beckers. Here, we show a way to do that which actually works."

So, yes, that's what you should be getting from the introduction!

> Given that current understanding, I agree with Reviewer nbxs (Reviewer
> 2?) that a non-toy example for Footnote 1 would help a lot. I
> understand and appreciate that the authors don't want to steal
> Beckers' thunder. However, as it stands, the paper does nothing to
> suggest to me the seriousness of what Beckers has found. The fact that
> Footnote 1 only has 3 variables isn't really a problem. The problem
> for me is that of those 3 variables, 2 of them (U and Y) are exactly
> the same ($Y = U$), but somehow one is exogenous and one is
> endogenous. And then the query we're asking is $p(X = 1 | X = 1)$, a
> query that I struggle to see the practical use of. It's possible that
> the incorrect result seen in Footnote 1 would be present in a wide
> range of situations, but with this as the provided example and no
> access to Beckers' paper, my first thought is "So does it only break
> in extreme fringe cases like this?" I understand that one
> counter-example is enough to show that it's incorrect. However,
> there's a big practical difference between "It will often given
> incorrect probabilities in a wide range of practical situations" and
> "It will break if we have deterministic dependence spanning
> exogenous-endogenous edges and ask then ask a query where the left and
> right hand sides are exactly the same".

We do agree with the point that it's useful for the reader  to
appreciate how deep the problem is.  But, at the same time, as we said,
we feel it inappropriate to steal Beckers' thunder.  We're also not
sure that any single example will solve the problem that you raise.
But we could add the following modification of the example of the
example in the footnote: Suppose that Y = U with probability 1/2 and Y
= 1-U with probability 1/2. Similarly X = Y with probability 1/2 and 1-Y
with
probability 1/2. Even in this case, Pr(X=1|X=1) would evaluate to
1/2.  This shows that dependence between exogenous and endogenous
variables is not the problem. Rather, whenever the exogenous
distribution does not change by conditioning, it is easy to construct
a counterexample.  Would adding that help?  Perhaps what might work
best is (with Beckers' agreement) to add a few sentences of
discussion which we clearly indicate are taken from Beckers' paper
that explains why he thinks that this is a deep problem, that isn't
easily fixable.
I appreciate the authors' response, which go part of the way to answering my concerns.

To your point that your paper isn't really based on the findings of Beckers, maybe 'based' isn't the right word, but at the very least it seems somewhat dependent on the findings of Beckers.  The message I get from the introduction as it stands is "We want to calculate probabilities under intervention and conditioning.  The classic method of doing that in CBNs doesn't actually work, as shown by Beckers.  Here, we show a way to do that which actually works."  If that's not what I should be getting from the introduction, then it should be reworked to show the value of this work independent of whether or not Pearl's CBN procedure is correct.

Given that current understanding, I agree with Reviewer nbxs (Reviewer 2?) that a non-toy example for Footnote 1 would help a lot.  I understand and appreciate that the authors don't want to steal Beckers' thunder.  However, as it stands, the paper does nothing to suggest to me the seriousness of what Beckers has found.  The fact that Footnote 1 only has 3 variables isn't really a problem.  The problem for me is that of those 3 variables, 2 of them (U and Y) are exactly the same ($Y = U$), but somehow one is exogenous and one is endogenous.  And then the query we're asking is $p(X = 1 | X = 1)$, a query that I struggle to see the practical use of.  It's possible that the incorrect result seen in Footnote 1 would be present in a wide range of situations, but with this as the provided example and no access to Beckers' paper, my first thought is "So does it only break in extreme fringe cases like this?"  I understand that one counter-example is enough to show that it's incorrect.  However, there's a big practical difference between "It will often given incorrect probabilities in a wide range of practical situations" and "It will break if we have deterministic dependence spanning exogenous-endogenous edges and ask then ask a query where the left and right hand sides are exactly the same".

> "Question 2: We will give examples of the usefulness of our approach in the full paper. We agree that this is important."

Would it be possible to provide an example now (or at least a sketch of what this will look like)?
I thank the authors for responding, I will maintain my score.