Nested Counterfactual Identification from Arbitrary Surrogate Experiments
Authors: Juan D. Correa
Sanghack Lee
Elias Bareinboim
Venue: NeurIPS 2021 Poster (2021)
Keywords: counterfactuals
identification
causal inference
experimental data

Abstract: The Ladder of Causation describes three qualitatively different types of activities an agent may be interested in engaging in, namely, seeing (observational), doing (interventional), and imagining (counterfactual) (Pearl and Mackenzie, 2018). The inferential challenge imposed by the causal hierarchy is that data is collected by an agent observing or intervening in a system (layers 1 and 2), while its goal may be to understand what would have happened had it taken a different course of action, contrary to what factually ended up happening (layer 3). While there exists a solid understanding of the conditions under which cross-layer inferences are allowed from observations to interventions, the results are somewhat scarcer when targeting counterfactual quantities. In this paper, we study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. Specifically, building on a more explicit definition of nested counterfactuals, we prove the counterfactual unnesting theorem (CUT), which allows one to map arbitrary nested counterfactuals to unnested ones. For instance, applications in mediation and fairness analysis usually evoke notions of direct, indirect, and spurious effects, which naturally require nesting. Second, we introduce a sufficient and necessary graphical condition for counterfactual identification from an arbitrary combination of observational and experimental distributions. Lastly, we develop an efficient and complete algorithm for identifying nested counterfactuals; failure of the algorithm returning an expression for a query implies it is not identifiable.


Nested Counterfactual Identification from Arbitrary Surrogate Experiments
Juan D. Correa
Sanghack Lee Seoul National University sanghack@snu.c ac
Elias Bareinboim Columbia University eb0cs. columbia edu
Columbia University j jccoreadcs. columbia. edu
Abstract
The Ladder of Causation describes three qualitatively different types of activities agent may be interested in engaging in, namely, sceing (observational), doing (interventional), and imagining (counterfactual) (Pearl and Mackenzie, 2018). The inferential challenge imposed by the causal hierarchy is that data is collected by agent observing or intervening in a system (layers I and 2). while its goal may be understand what would have happened had it taken different course of action, contrary to what factually ended up happening (layer 3). While there exists a solid understanding of the conditions under which cross-layer inferences allowed from observations to interventions, the results are somewhat scarcer when targeting counterfactual quantities. In this paper, we study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. Specifically, building on more explicit definition of nested counterfactuals, we prove the counterfactual unnesting theorem (CUT), which allows one to map arbitrary nested counterfactuals to unnested ones. For instance, applications mediation and fairness analysis usually evoke notions of direct, indirect, and spurious effects, which naturally require nesting. Second, we introduce sufficient and necessary graphical condition for counterfactual identification from an arbitrary combination of observational and experimental distributions. Lastly, we develop an efficient and complete algorithm for identifying nested counterfactuals: failure the algorithm returning an expression for a query implies not identifiable.
Introduction
Counterfactuals provide the basis for notions pervasive throughout human affairs, such credit assignment, blame and responsibility, and regret. One of the most powerful constructs in human reasoning "what if?" questions evokes hypothetical conditions usually contradicting the factual evidence. Judgment and understanding of critical situations found from medicine to psychology to business involve counterfactual reasoning, c.g.: "Joe received the treatment and died, would he be alive had he not received it?," "Had the candidate been male instead of female, would the decision from the admissions committee be more favorable?," or "Would the profit this quarter remain within key ingredients
5% of its value had increased the price by 2%."" By and large, counterfactuals that go in the construction of explanations about why things happened as they did 17 19
The structural interpretation of causality provides proper semantics for representing counterfactuals [7 Ch. 7J. Specifically, each structural causal model (SCM) M induces collection distributions related to the activities of seeing (called observational), doing (interventional), and imagining (counterfactual). The collection of these distributions known as the Ladder of causation [19, and has also been called the Pearl's s's Causal Hierarchy (PCH, for short) (2). The PCH is containment hierarchy; each type of distribution can be put in increasingly refined layers: observational content goes in layer I; experimental in layer 2; counterfactual in layer 3; see Fig.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

It is understood that if we have all the information in the world about layer I, there are still questions about layers 2 and 3 that are unanswerable, or technically undetermined; further, if we have data from layers 1 and 2, there are still questions in the world about layer that are underdetermined [172]. 2].
Structural Causal Model (Unobserved Nature)
P(X,Y) Layer
P[Y|do(X) Layer 2
P(Ya [all."'.' 9") Layer 3
The inferential challenge in these settings arises be- cause the generating model M is not fully observed, nor data from all of the layers are necessarily avail- able, perhaps due to the cost or the infeasibility of performing certain interventions. One common task found in the literature is to determine the effect of an intervention of a variable X on an outcome Y, say ((Y]d((X) )) (layer 2), using data from observations P(V) (layer 1), where V is the set of observed variables, and possibly other interventions, e.g. P(V]do(2) 2)). Also, qualitative assumptions about the system are usually articulated in the form of causal diagram G. This setting has been studied in the literature under the rubric of non-parametric identification from a combination of observations and experiments. Multiple solutions exist, including Pearl's celebrated do-calculus [T6,, and other increasingly refined methods that are computationally efficient, sufficient, and necessary 25 8
Figure 1: Every SCM induces different quan- tities in each layer of the PCH.
20
26
21
10
3
1 12
There is a growing literature about cross-layer inferences from data in layers I and to quantities in layer 3. For example, data scientist may be interested in evaluating the effect of an intervention on the group of subjects who receive the treatment instead of those randomly assigned to it. This measure is known as the effect of treatment on the treated [9] 17]. and there exists a graphical condition for mapping it to a (layer 2) causal effect [23]. Further, there are also results on the identification of path- specific effects, which are counterfactuals that isolate specific paths in the graph [88 In particular, (24] provides a sufficient and necessary algorithm for identification of these effects from observational data, and (28) provides identification conditions from observational and experimental data in general canonical models. Further, [22] studied counterfactual identification under the assumption that all experimental distributions (i.c., over every subset of the observed variables) are available U
In this paper, our goal is to identify the probability distribution of (possibly nested) counterfactual events from an arbitrary combination of user-specified observational and experimental distributions. To the best of our knowledge, this provides the first general treatment of nested counterfactual identi- fication from arbitrary data collections. Moreover, it also provides the first, graphical and algorithmic, sufficient and necessary conditions for the identifications of counterfactuals from observational data alone (when no experimental data is available) and arbitrary causal diagrams. Moving up the PCH, our results allow for arbitrary quantities as inferential targets and for the addition of arbitrary experimental distributions to the input, increasing the flexibility of the solution.
For concreteness, consider the causal diagram shown Fig. 2 and a counterfactual query called direct effect. This quantity represents the sensitivity of a variable Y to changes in another variable X while all other factors in the analysis remain fixed. Suppose X is level of exercise, M cholesterol levels, and Y cardiovaseular disease. Exercising can improve cholesterol levels, which in turn affect the chances of developing cardiovascular disease. An interesting question is how much exercise prevents the disease by means other than regulating cholesterol. In counterfactual notation, this is to compare Yz,M, and Yz' Ye' where x and x' are different values. The first quantity represents the value of Y when X=r and M varies accordingly. The second expression is the value Y attains if X is held constant at x' while M still known the natural direct effect (NDE)
M
Y
Figure 2: Causal diagram with treatment X, out- come Y, and mediator M.
follows X=r. The difference F| M. -Y,,M_l is non-zero if there is some direct effect of X on Y. In this instance, this nested counterfactual is identifiable only if observational data and experiments on X are available.
In fact, this is a classic task in a larger family of problems known as data fusion, which include other challenges such as selection bias, transportability, to cite a few. For more details, see [.
FFor the sake context, the work proposed here can be seen as generalization of two tasks, counterfactual identification under the assumptions discussed earlier [22) and interventional identification from arbitrary experiments [13]. As discussed later on, we will be able to show, based on the machinery developed here, that the individual methods for those tasks can be combined and also be shown complete.

---

After all, there is no general identification method for this particular counterfactual family (which also includes indirect and spurious effects) and, more broadly, other arbitrary nested counterfactuals that are well-defined in layer 3. Our goal is to understand the non-pau non-parametric identification of arbitrary nested and conditional counterfactuals when the input consists of any combination of observational and interventional distributions, whatever is available for the data scientist. More specifically, our contributions are as follows.
1. We look at nested counterfactuals from an SCM perspective and introduce machinery that supports counterfactual reasoning. In particular, we prove the counterfactual unnesting theorem (CUT), which allows one to map any nested counterfactual to an unnested one (Section 2).
2. Building on this new machinery. we derive sufficient and necessary graphical conditions and an algorithm to determine the identifiability of marginal nested counterfactuals from an arbitrary combination of observational and experimental distributions (Section 3).
3. We prove reduction from conditional counterfactuals to marginal ones, and use it to derive a complete algorithm for their identification (Section 4).
Due to space constraints, all the proof's in this paper can be found in the full technical report S
1.1 Preliminaries
We denote variables by capital letters, X, and values by small letters, x. Bold letters, X represent sets of variables and sets of values. The domain of a variable X is denoted by Ex. Two values and z are said to be consistent if they share the common values for X n Z. We also denote by x Z the value of X Z consistent with x and by n Z the subset of x corresponding to variables in Z. We assume the domain of every variable is finite.
We relay on causal graphs and denote them with calligraphic letter, e.g., g. We denote the set of vertices (i.e., variables) in G as V(G). Given a graph g. 9wx the result of removing edges coming into variables in W and going out from variables in X. G[W] denotes a vertex vertex-induced subgraph including W and the edges among its elements. We use kinship notation for graphical relationships such as parents, children, descendants, and ancestors of a set of variables. For example, the set of parents of X in G is P X UXXx Pa(X)ç. Similarly, we define Ch(), De and An()
To articulate and formalize counterfactual questions, we require a framework that allows us to reason simultaneously about events from alternative worlds. Accordingly, employ the Structural Causal Model (SCM) paradigm [17] Ch. 7]. An SCM M is a 4-tuple V.F,P(() where U is a set of exogenous (latent) variables; V is set of endogenous (observable) variables; F is collection of functions such that each variable V; E V is determined by a function fi E F.. Each fa is a mapping from set of exogenous variables U, C U and set of endogenous variables Pa, C V \ [V:) the domain of V,. Uncertainty is encoded through a probability distribution over the exogenous variables, P(U). An SCM M induces a causal diagram & where V the set of vertices, there directed edge (V; + Vi:) for every V; E V and Vj E Pa., and a bidirected edge (V: +--+ Vj) for every pair U, + (V; and Vj have a common exogenous parent).
V1, V É V such that U,nU
We assume that the underlying model is recursive. That is, there are no cyclic dependencies among the variables. Equivalently, that is to say, that the corresponding causal diagram is acyclic. The set Vg) can be partitioned into subsets called c-components (27] such that two variables belong to the same c-component if they connected in by a path made entirely of bidirected edges.
2 SCMs and Nested Counterfactuals
Intervening on system represented by an SCM M results in a new model differing only on the mechanisms associated with the intervened variables [5 6 7. If the intervention consists on fixing the value of a variable X to a constant x E Xx, it induces a submodel, denoted M,, [17 Def. 7.1.2]. To formally study nested counterfactuals, we extend this notion to models derived from interventions that replace functions from the original SCM with other, not necessarily constant, functions.
(Derived Model). Let M be an SCM. Ô C U, E V, and X Ú + Ex a function. Then, Mg. x. called the derived model of M according to X, is identical to M, except that the function fx is replaced with function fx identical to X.
Definition
3

---

This definition is easily extendable to models derived from an intervention on set X instead of singleton. When X is a collection of functions {X Ux +xxxex the derived model My obtained by replacing each fx with X for X E X. Next, we discuss the concept of potential response [17 Def. 7.4.1] with respect to the derived models.
Definition 2 (Potential Response). Let X. Y C V be subsets of observable variables, let u be a unit, and let (()) be a set of functions from Ux - Xx, for X E X where Üx S U. Then, Y x x (u) (or Yx (u), for short) is called the potential response of Y to X X, and is defined as the solution of Y, for particular u, in the derived model Mx
potential response Y& (u) describes the value that variable Y would attain for unit (or individual) u if the intervention X is performed. This concept is tightly related to that of potential oulcome, but the former explicitly allows for interventions that do not necessarily fix the variables in X to a constant value. Averaging over the space of U, a potential response Y& (u) induces random variable that we will denote simply as Xx If the intervention replaces function fx with a potential response of X in M, we say the intervention is natural.
When variables enumerated W1, W we may add square brackets around the part of the subscript denoting interventions. We use W. to denote sets of arbitrary counterfactual variables. Let W. = WIfTT) W We[Tx].... represent
of counterfactual variables such that W; E V and T; S V for i = I....,,. L. Define V(W.) = {W E V W E W. that is, the set of observables that appear in W.. Let w, represent vector of values, one for each variable in W. and define w, (X.) as the subset w. corresponding to X. for any X, S W..
The probability of any counterfactual event is given by
P(Y. =y.) Σ E(ury.(u)vv.) P(u),
(1)
where the predicate (u) = y, means ((xgEY.) (u) = y.
When all variables in the expression have the same subscript, that is, they belong to the same submodel; we will often denote it as (Wi, W,....)
For most weal-world scenarios, having access to fully specified SCM of the underlying system is unfeasible. Nevertheless, our analysis does not rely on such privileged access but the aspects of the model captured by the causal graph and data samples generated by the unobserved model.
2.1 Nested Counterfactuals
Potential responses can be compounded based on natural interventions. For instance, the counterfac- tual Yz, (u) (Yz=z, (u)) can be seen as the potential response of Y to an intervention that makes Ž equal to Zz. Notice that (u) is in itself a potential response, but from a different (nested) model. Hence we call Yz, a nested counterfactual.
Recall the causal diagram in Fig. 2 and consider once again the NDE as
NDE, z(Y) ElY, 2,1 E|Yy)-
(2)
The second term is also equal to Yuz, 7n is consistent with X = so it is the value Y listens to in My. Meanwhile, the first one is related to P(Y ), the probability of a nested counterfactual.
2.2 Tools for Counterfactual Reasoning
Before characterizing the identification of counterfactuals from observational and experimental data, develop from first principles canonical representation of any such query. First, we extend the notion of ancestors for counterfactual variables, which subsumes the usual one described before.
Definition 3 (Ancestors, of a counterfactual). Let Yx be such that Y V, X C V. Then, the set of (counterfactual) ancestors of Yx, denoted An(xx), consist of each Wz, such that W E An(Y))x (which includes Y itself), and z = x n (W)))
For a set of variables W., we define (n(W)) as the union of the ancestors of each variable in the set. That is, (WW)) = Uw,ew. An(W.). For instance, in Fig. 3(a) An(Yz) (Y., 2). Anxx)))

---

Z
X,
(a) "Backdoor" graph.
(b) Graphical representa- tion of the ancestors of Y..
(c) "Napkin" graph.
(d) Graphical representa-
tion of the ancestors of Y2.
Figure 3: Two causal diagrams and the subgraphs considered when finding sets of ancestors for counterfactual variable.
(X:) and An = (Yz, (depicted in Fig. 3()). In Fig. 3(c) An(Z, (Y2, X,, Z, W) and An(Y,) {Y2) (represented in Fig. 3(d).
Probabilistic and causal inference with graphical models exploits the local structure among variables, specifically parent-child relationships, to infer and even estimate probabilities. In particular, Tian 27 introduced c-factors which have proven instrumental in solving many problems in causal inference. We naturally generalize this notion to the counterfactual setting with the following definition.
Definition (Counterfactual Factor fctt-ractor). A counterfactual factor is distribution the form
P(Wi[pa,) wi, W W2]pa.] 02:---. Wi[pa.] wx),
where each W; E V and there could be Wi W, for some i,j (I....,
For example, for Fig. 3(c) P(Y2 y, Y v/), P(Y, = y, X= = x) are etf-factors but P(Y y: Z.. 2) is not. Using the notion of ancestrality introduced in Definition 3 can factorize counterfactual probabilities as etf-factors.
Theorem (Ancestral set factorization). Let W. be an ancestral set, that is, An(W.) W., and let be vector with value for each variable in W.. Then,
P(W.=w.) (N W pa. w
(4)
where each w is and p is determined for each We W. as follows:
(i) the values for variables in Paw T are the same as in t, and
(ii) the values for variables in Pa.. TT are taken from w. corresponding to the parents of W.
Proof outline. Following a reverse topological order in G, look at cach Wa, W.. Since any parent of W; not in T, must appear in W., the composition axiom [17 7.3. licenses adding them to the subscript. Then, by exclusion restrictions []]. any intervention not involving Pa(W,) can be
removed obtain the form Eq. (4)
For example, consider the diagram in Fig. 3(c) and the counterfactual P(Y, = y X = x') known as the effect of the treatment on the treated (ETT) g 17 First note that P(Y, X x') P(Y, = y. X x²)/ P(X = x²) and that An(Y,. z: X) (Yz. 2, W). then
P(Y, = y, X = x') Σ,
P(Y, = y, X = x' 2 2, w=ww
(5)
2,30
Then, by Theorem
we can write
P(Y, v, x =()==,,==))=>> Σ, 2,W
P(Y. v, 2' Un =2 W = w).
(6)
Moreover, the following result describes a factorization of etf-factors based on the e-component structure of the graph, which will prove instrumental in the next section.
Theorem 2 (Counterfactual factorization). Let P(W.- =w) ) be a ctf-factor, let W1 222 <.. be a topological order over the variables in G(V(W.)) }}, and let Ci...., C2 be the c-components of the same graph. Define Cj. (Wpa., E W. W E &,)) and Cjs as the values in w. corresponding to Cj., then P(W. = w.) decomposes as
P(W, = w.) = II, P(C,- C.,.)
(7)
5

---

Z
Z
W
W
(a)
(b)
(c)
Figure 4: Three causal diagrams representing plausible structures in mediation analysis.
Furthermore, each factor can be computed from P(W. w) as
E(mi EW.. W.W.,.sW. P(W. = w.)
= = II
(8)
Σ (w/W EW.. P(W. w.)
(W,EC))
Armed with these results, we consider the identification problem in the next section.
3 Counterfactual Identification from Observations and Experiments
In this section, we consider the identification of a counterfactual probability from a collection of observational and experimental distributions. This task be seen generalization of that in 13 where the available data the same, but the query is a causal effect Px Let Z = {Z,. Zz....). Z, V, and assume that all of (Pz;(V) 12) .2, E2 available. Notice that Z, = 0 is valid choice corresponding to P(V) the observational (non-interventional) distribution. Definition (Counterfactual Identification). A query P(Y. = y+) is said to be identifiable from & in G, if P(Y.- = y.) is uniquely computable from the distributions {P2, (V) EXz, 2,ez ez in any causal model which induces G.
Given an arbitrary query P(Y. = y.), we could express it in terms of ctf-factors by writing P(Y. y.) Ed.y. ly. P(D, d.) where D. An(Y.) and then using Theorem I to write P(D. d.) as etf-factor. For instance, the ancestral set W. (Y,, X,Z.W] with w {v.,', w) in Eq. (6) can be written in terms of ctf-factors as
P(Y, = y, X, = x', Zu 2, W = w) = P(Y, = y, X, = I W = P(Z = 2). (9)
The following lemma characterizes the relationship between the identifiability of P(Y. y.) and P(D. = =d.).
Lemma 1, Let P(W.- = -w.) be a ctf-factor and let Y. C W. be such that W. An(Y.). Then, Ew.y. P(W, w,) ) is identifiable from Z if and only P(W. w..) identifiable from Z.
Once the query of interest is in cuf-factor-form the identification task reduces to identifying smaller ctf-factors according to the c-components of G. In this respect, Theorem 2 iimpiis the following
Corollary 1. Let P(W. = w.) be etf-factor and Cj be a c-component of (V.(W.)) Then, if P(C)* Cj+) is not identifiable, P(W. w.) is also not identifiable.
Proof. Assume for the sake of contradiction that P(Cj. = C..) not identifiable but P(W. = w.) is. Then, by Theorem 2 the former is identifiable from the latter, contradiction.
L
Let us consider the causal diagrams in Fig. 4 and the counterfactual Yag, = - X = 2, with
F1, I E Ex, used to define quantities for faimess analysis in (28) (c.g., Yo,. Weo = 2 X = z):
P(Y,, W.. =vxx== x))
Σ P(Y = WT, W, X
Unnesting
(10)
Σ wiz P(Y = y. Way = w, = x, Z 2)
Complete ancestral set
(11)
= Σ w.z
P(Ye),u.s = B, Wa, = w. X, = =x, x.
Write in wasfaa-t-ooonm
(12)

---

Z
X
X
Y
X
Y
(a) The factor P(Z, 2) is identifiable only if {X} E Z.
(b) The factor P(Y, y, X x is inconsistent.
(c) The factor P(W, w, W.r
w') is inconsistent.
Figure 5: Examples of causal diagrams and inconsistent ctf-factors derived from them.
Due to the particular c-component structure of each model, we can factorize P(Y y, Was w, X2 = x, 2 = z) according to each model as:
P(Y = PWW do = P(X, = =Z = 2), P(Y = =: 7 P) no =
(13)
x)), and
(14)
P(Y - PW) me = X. - x =
(15)
The question then becomes, whether etf-factors corresponding to individual c-components can be identified from the available input. In this example, all factors in [q. (13) and Eq. (14) are identifiable from P(V). For Eq. (14) in particular, they are given by
P(Y = y, 2 = = W = w. X = x P(W = w = 20) = x =)
(16)
X,=z) = Eq. (15) (model 4(c)) is only identifiable if x= The following definition and theorem characterize the factors that can be identified from Z and G.
In contrast, the factor P(W,, =w,
Definition 6 (Inconsistent ctf fac-orc) P(W. w.) is an inconsistent stf-factor it is etf-factor, G(((W.) ])] has single c-component, and one of the following situations hold:
there exist W. W., Z T V(W.) such that = E t, E w. and + z', or
(ii) there exists Wilt.:: Wiits) E W. and 7 Trn T, such that & E tt, E t2 and t + t'.
Theorem (Ctf-factor identifiabilityy. A cifffcttor P(W. w) is identifiable from Z. if and only if it is consistent. If consistent, let W = V(W,) and W' = V W; then P(W. w.) is equal to Pw (w) where w and w/ are consistent with w, UUWpa_ Ew.) pa
Consider the NDE (Y) in Fig. 5(a) we can write
P y) = Σ.
= 2) Σ,
= 2).
(17)
While the factor P(Y='z = 2) is identifiable from P(V) as P(Y = X x=x', z), the second factor is identifiable only if experimental data X is available, as P=)...
We can also verify that the factor P(Y, = y. X x') in Fig. 5(b) inconsistent. For another
example consider the ETT-like expression P(yz,= X Z =2) in Fig. 5(c) we have
2')
P(Y.* 8= y. X = x', =
Σ w.a!!
P(Y== X- = 1', 2 = ,' W. = = W = w')
(18)
Σ we P(Y.: V, X- = x Zw = =z', W. w. Wa = =w')
(19)
Σ
w.eu! P(Y:: -))((X = x' P((w = P(W, = w. Wer = =w),
(20)
where the factor P(W, w. Wo w') is inconsistent.
Given a counterfactual variable Yx. could be the case that some values in x become causally irrelevant to Y after the rest of has been fixed. Formally,
Lemma 2 (Interventional Minimization). Ler Y ||= Urger, Ix such that \|x || := Yg where
Z X n (Y()) and Ż is consistent with | ||||= = x and ||0|= 0. Then, Y. = |Y
Moreover, such simplification may reveal counterfactual expressions with equivalent contradicting events. In Fig. 3(c) (Yn. = y. Yus'/ = 3/) = (Y, y. Y, = y') which has probability 0 if y # y/ or (Yn. y. az' v) that is simply (Yz y). Similarly, the probabilities of counterfactual events of the form P(X, = x'), x # x', and P (x, = .)) are trivially 0 and respectively.
The following result shows how nested counterfactuals can be written in terms of non non-nested ones.
7

---

Algorithm 1 CTFIDU( Y.,
Input: G causal diagram over variables V: Y, a set of counterfactual variables V; y. set of values for Y,; and available distribution specification Z.
Output: P(Y. = y-) terms of available distributions or FAIL if not identifiable from (G, Z).
1: let Y. < -||.|
2: if there exists Yx E Y. with
more different values in y. (Yx) Yr E YY, with (Y,)
then return 0.
3: if there exists Yx E Y. with two consistent values in y-x)) or Y, E Y. with y. (Y,)) - y then
remove repeated variables from Y. and values y.. 4: let W. < An(.).. and let C Ciey.... Ck. be corresponding etf- in GlV(W ))]
5: for each C, s.t. (C,, =c+)) is not inconsistent, Z E & s.t. n Z = 0 do
6: let B, be the c-component of Gz such that C₁ S B, compute PV,B, (B,) from Pz (V).
7: if IDENTIFY (C,, B;, Pv,B, (B;), 9) does not FAIL then 8: let Pvic, (C,) + IDENTIFY (C,, B, PvAB, (B.),)).
9: let P(Ci. c.a) <- Pvic, (C;) evaluated with values (cs. UUGEC, pa.)
move the next C..
11: end if
12: end for
13:
if any P(C,. = c.+) is inconsistent or not identified from E then return FAIL.
14: return P(Y. = y-) - -.w. ly. II, P(C,. = Cj+).
Theorem 4 (Counterfactual Unnesting Theorem (CUT)), Let X, Z be any natural interventions on disjoint sets X, Z C V. Then, for Y = V disjoint from and Z such that X S A
P(Y y) is identifiable iff P(Y 2, = v, x) is identifiable for every x, and given by
P(Y2x y) ExExx P(Y2,x = =
(21)
For instance, for the model in Fig. 2 we write
P(Yzz, = = Σ P(Y== = -. z))
(22)
As Theorem allloos us rewrite any nested counterfactual in terms of a non-nested one, we focus on the latter and assume that any given counterfactual already unnested.
Using the results in this section, we propose the algorithm CTFIDU (Algorithm I) which given a set of counterfactual variables Y.. values y. collection of observational and experimental distributions Z, and causal diagram G: outputs an expression for P(Y. y.) ) in terms of the specified distributions or FAIL if the query is not identifiable from such input in G. Line Temoves irrelevant subscripts from the query by virtue of Lemma 2] Then, lines 2 and look for inconsistent events and redundant events, respectively. Line 4 finds the relevant etf-factors consisting of a single e-component, licensed by Theorem [add Theorem 2 As long as the factors are consistent, and allowed by Theorem 3] lines IT earry out identification of the causal effect Pv.c, (C2) from the available distributions employing the algorithm IDENTIFY (26 as a subroutine (see an example in the next section). The procedure fails if any of the factors P(C,. = c..) is inconsistent not identifiable from Otherwise, it returns the corresponding expression.
Theorem 5 (CTFIDU completeness). A counterfactual probability P(Y. = -y.) is identifiable from Z and G if and only if CTFIDU returns expression for
This result ascertains that Algorithh I solves the identification task for counterfactuals in the form P(Y. y Still, there exist other quantities that take into account evidence from events observed in the system, and cannot be written in this particular form. Since these queries represent important aspects of the underlying system, we will discuss them in the next section.
"One corollary of this result is that two identification algorithms 22 13 can be combined be shown complete; for details, see Apppendixx F Even though our results were developed from first principles using an entirely new approach and machinery (which was the key to derive Algorithm I and prove its completeness). practitioners familiar with these algorithms may find the completeness of this combined approach attractive.
8

---

x
Z
Y
X
(a) While P(Y.=y 2,=2, from 2, -, 2, X=x' is not.
2, X X=r") is identifiable
(b) P(Y. 2,= x-=z) is not identifialle from
2 because of the factor
Figure 6: Examples conditional queries.
Algorithm 2 CTFID(Y Y.. X., X..
Input: G causal diagram over variables V: Y X, set of counterfactual variables in V: yo, X, set of values for Y. and X.; and available distribution specification Z. Output: Py.,=y, x.= terms of available distributions or FAIL if non-ID from (g, Z).
1: Let A1 Ag.,..... ... be the ancestral components of Y, U X. given X..
2: Let D. be the union of the ancestral components containing variable in Y. and d, the
corresponding set of values.
3: let Q <- CTFIDU(UDDe) D.EDD D Ppa, 2,
4: return Ed. (x,) Q/ Q/Ed.xx. Q.
4 Identification of Conditional Counterfactuals
In this section, we consider counterfactual quantities of the form P(Y. = y. X. = x.). is immediate to write such query as P(W, =w-)/ ww./Ey. P(W. w.) with W,= Y.UUX U.... and try to identify it using CTFIDU. Nevertheless, depending on the graphical structure, the original query may be identifiable even if the latter not. To witness, consider the causal diagram Fig. 6(a) and the counterfactual P(Y, y Ze 2, X = x'), which can be written as P(Y, y, Ze
x')/E, E,, P(Y, = y; Z5 = 2, = x'). Following the strategy explained so far, the numerator equal to P(Y= = y) P(Z, = 2, X = x²), where the second ctf-factor is inconsistent, and therefore not identifiable from Z. Nevertheless, the conditional query is identifiable
P(Y P(2, = x, x-x' P(Zg =, X x²) Σ, P(Y,; P(Y.. = y) P(Y y 7 = x))
(23)
To characterize such simplifications of the query, we look at the causal diagram paying special attention variables after the conditioning bar that are also ancestors of those before. Let (W+) V(JX.. [[nAm(W))), that is, the primitive variables in X, that are also ancestors of Wt.
Definition (Ancestral components). Let W. be a set of counterfactual variables, X, C W., and g be causal diagram. Then the ancestral components induced by W., given X,, sets A Js, Ag..... that form partition over An(W.) W.). made of unions of ancestral the sets (WWW)xxxcoo We E W..
Sets An (W(e,)) Gx_ (W: and An (Wafez)) fx. (WWjeg) are put together if they are not disjoint or there exists a bidirected arrow in G connecting variables in those sets.
Lemma 3 (Conditional Query Reduction). Let Y.,X, be two sets of counterfactual variables and let D2 be the set of variables in the same ancestral component, given X., as any variable in Y., then
P(Y. -y. X. xx) Ea. Ed.((r.ux.) P(AD,ED. D Dpa. d)
(24)
Ea.x. P(AD.ED. Dpa, d)
where a is consistent with t and d., for each D. E D.. Moreover, P(Y. = = X. xx) is identifiable from if and only if P(AD.ED. Dpa, d) identifiable from Z.
Using the notion of ancestral components and Lemma 3] we propose a conditional version of CTFIDU (Algorithm 2p. Due to Lemma 3) it easy to see that CTFID complete. In case that W, = Y. UX, contains nested counterfactuals, Theorem 4] can be used first and the new variables in the expression are added to W., then the new sum indexes added to d. in Eq. (24)
Theorem 6 (CTFID completeness). counterfactual probability P(Y. = y. X. x.) identifiable from Z and G if and only if CTFID returns an expression for it.

---

To illustrate the mechanics of our algorithm, consider the causal diagram g in Fig. 7(a) and the identification of the query P(Y,, Zzo Y1 X 21 Ir. RiR ro) from 2 (1. W T)
First, we can use [Theormm to write the query as:
Σ P(Y Zzo X I1, =,, R-ro).
(25)
The query within the sum can be processed using CTFID Y. (Yais Zoot. Y. = {v1,2), X. = {Xwas Tra R}. X. = (21, ro), G).
T
At line _ the algorithm looks for the ancestral components of Y, X. given X.. This results in three ancestral components, which can be labeled as A.. {Y=, am T, T). A2. {Zao] J and Ag. ). Then, we let D be the union of the ancestral sets that contain variables Y., that is D. {Yz, = T, R, Z }. We also gather the values d. (y1, 31, ro, =}, where is new value introduced for T' that will appear as the index in a sum on line 3
(a) g
R
T
At this point, CTFIDU is invoked with arguments (Y. (Yz: Tra: RG Zzoro] V. d., Z, 9). In this case lines 33 will not make any change. Note that An (Dnm.) their union is also an ancestral set, and W. will be equal to the Y.
X
(Ppa.) ). hence
(b) Gv(w.)
given to CTFIDU. The c-components in the graph G[V(W.) are (X, R. { and { then we need to consider the etf-factors P(Y, = W1, X1, m = Ii, R- ro), P(Tro = t) and P(Zmoro 2). In this case all of the ctf-factors are consistent, so we can try to identify each of them from Z. Specifically, we will obtain
Figure 7: Graphs used for the running example of the algo- rithms.
P(Y: Xmo = 21, R ro) Puo (ro)) Po) 21, P(TrO f) = P(t ro), and P(Zmoro = z) = Pu,r ro,
(26)
(27)
(28)
where w and E' could be any values in Ew and Ey, respectively. We could just take wp and t for simplicity. Then, considering the sum over introduced for unnesting, the final result is:
P(Y Zup = =1 Xwo = #1, Tm = -4==
(29)
Σ 2,
Poo. 2o) Poo. ro)
(30)
Conclusions
We investigated in this paper the problem of nested and non-nested counterfactual identification from an arbitrary combination of observational and experimental distributions. First, we introduced funda- mental building blocks for counterfactual reasoning, which allowed us to prove several properties of nested counterfactual distributions, including the counterfactual unnesting theorem (Thcorem 4). and the ancestral and counterfactual factorization theorems (Theorem TTeorem 2). Moreover, we introduced a graphical condition (Detinition 6 [Theorem 3) and developed an efficient algorithm (Algorithm Tp for identifying marginal counterfactuals. We then proved their sufficiency and necessity for the task of nested counterfactual identification (Theorem 5). Lastly, we reduced the identification of conditional counterfactuals to that of marginal ones (Lemma 3) and provided a corresponding complete algorithm (Algorithm 2) for this task (Theorem 6). These results advance the state of the art regarding the distributions the inference engine expects input, and the query it can generate as the output. In terms of the input, it accepts any combination of observational and experimental distributions, and in terms of the output, it considers arbitrary nested counterfactual distribution. This work closes the long-stann oongsstanding inferential gap within the layers of the Pearl's Causal Hierarchy, and now can move within all layers of the hierarchy in very flexible and general way.
For details on this example Appendix B
10

---

Perspective. Annual Review Acknowledgments and Disclosure of Funding
Elias Bareinboim and Juan D. Correa were supported in part by funding from the NSF IIS-1704352. IIS-1750807), Amazon, JP Morgan, and The Alfred P. Sloan Foundation. Sanghack Lee was supported by the New Faculty Startup Fund from Seoul National University.
References
[1] Avin, C., C., Shpitser, I., and Pearl, (2005). Identifiability of Path-Specific Effects. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05), pages 357-363, Edinburgh, UK. Borgan-Kaufman Publishers.
[2] Bareinboim, E., Correa, J. D., lbeling, D., and Icard, T. (2020). On Pearl's Hierarchy and the Foundations of Causal Inference. Technical Report R-60, Causal Artificial Intelligence Lab, Columbia University. In: "Probabílistic and Causal Inference: The Works of Judea Pearl", ACM Books, in press.
[3] Bareinboim, and Pearl, J. (2012). Causal Inference by Surrogate Experiments: z-Identifiabilityy. In Murphy, N. d. F. and Kevin, editors, Proceedings of the Twenty-Eighth Conference on Uncer- tainty in Artificial Intelligence, pages 113-120. AUAT Press.
[4] Bareinboim, E. and Pearl, J. (2016). Causal inference and the data-fusion problem. In Shiffrin, R. M., editor, Proceedings of the National Academy of Sciences, volume 1 113, pages 7345-7351 National Academy of Sciences.
[5] Correa, J. D., Lee, S., and Bareinboim, E. (2021). Nested Counterfactual Identification from Arbitrary Surrogate Experiments. Technical Report R-79, Causal Al Lab, Columbia University.
[6] Dawid, A. P. (2002). Influence diagrams for causal modelling and inference. International Statistical Review, 70:161-189.
[7] Dawid, A. P. (2015). Statistical Causality from of Statistics and Its Application, 2(1):273-303
[8] Galles, D. and Pearl, J. (1995). Testing identifiability of causal effects. In Besnard, P. and Hanks, S., editors, Uncertainty in Artificial Intelligence 11, pages 185-195, Morgan Kaufmann, San Francisco.
[9] Heckman, (1992). Randomization and Social Policy Evaluation. In Manski, C. and Garfinkle, I., editors, Evaluations: Welfare and Training Programs, pages 201-230. Harvard University Press, Cambridge, MA.
[10] Huang, Y. and Valtorta, M. (2006). Identifiability in Causal Bayesian Networks: A Sound and Complete Algorithm. In Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI 2006), pages 1 1149-1155 1156. AAAI Press, Menlo Park, CA.
[1I] Huang, Y. and Valtorta, M. (2008). On the completeness of an identifiability algorithm for sark-Mnr models. Annals of Mathematics and Artificial Intelligence, 54(4):363-44
[12] Lee, S. and Bareinboim, F. (2020). Causal effect identifiability under partial-observabiiity In Proceedings of the 37th International Conference on Machine Learning, volume 119. PMLR.
[13] Lee, S., Correa, D., and Bareinboim, E. (2019). General Identifiability with Arbitrary Surrogate Experiments. In Proceedings of the Thirty-Fifhh Conference Annual Conference on Uncertainty Artificial Intelligence, Corvallis, OR. AUAI Press.
[14] Lee, S., Correa, J. D., and Bareinboim, F. (2020). Generalized Transportability: Synthesis of Experiments from Heterogeneous Domains. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, Menlo Park, CA. AAAI Press.
[15] Pearl, J. (1994). A probabilistic calculus of actions. In de Mantaras. R. L. and D. "ooole, editors, Uncertainty in Artificial Intelligence 10, pages 454-462. Morgan Kaufmann, San Mateo, CA.
[16] Pearl, (1995). Causal diagrams for empirical research. Biometrika, 82(4):669-683
[17] Pearl, J. (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, USA, 2nd edition.
[18] Pearl, (2001). Direct and indirect effects. In Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, pages 411-420. Morgan Kaufmann, San Francisco, CA.
11

---

[19] Pearl, J. and Mackenzie, D. (2018). The Book of Why. Basic Books, New York.
[20] Pearl, J. and Robins. J. M. (1995). Probabilistic evaluation of sequential plans from causal models with hidden variables. In Besnard, P. and Hanks, S., editors, Uncertainty in Artificial Intelligence 11, pages 444-453. Morgan Kaufmann, San Francisco.
[21] Shpitser, I. and Pearl, J. (2006). Identification of Joint Interventional Distributions in Recursive semi-Markovian Causal Models. In Proceedings of the Twenty-First AAAI Conference on Artificial Intelligence, volume 2. pages 1219-1226.
[22] Shpitser, and Pearl, J. (2007). What Counterfactuals Can Be Tested. In Proceedings of the Twenty-Third Conference Uncertainty in Artificial Intelligence, pages 352-359. AUAI Press, Vancouver, BC, Canada.
[23] Shpitser, I. and Pearl, J. (2009). Effects of Treatment the Treated: Identification and Generalization. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, Montreal, Quebee, AUAI Press.
[24] Shpitser, I. and Sherman, E. (2018). Identification of Personalized Effects Associated With Causal Pathways. In Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, pages 530-539.
[25] Spirtes, P., Glymour, C. N., and Scheines, R. (2001). Causation, Prediction, and Search. MIT Press, 2nd edition.
[26] Tian, and Pearl, (2002a). A General Identification Condition for Causal Effects. In Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI 2002), pages 567-573, Menlo Park, CA. AAAI Press/The MIT Press.
[27] Tian, J. and Pearl, (2002b). On the Testable Implications of Causal Models with Hidden Variables. Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI-02), pages 519-527.
[28] Zhang, J. and Bareinboim, E. (2018). Fairness in Decision-Making- The Causal Explanation Formula. In AAAI Conference on Artificial Intelligence.
12


Reviews:
[{"review_id": "fMDhWQyPF53", "reviewer": "Reviewer_hjGq", "summary": "The authors study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. They prove the counterfactual unnesting theorem, which allows for the mapping of nested to unnested counterfactuals. Then they introduce 1) sufficient and necessary graphical conditions for counterfactual identification from an arbitrary combination of observational and empirical distributions, and 2) an algorithm for identifying nested counterfactuals, the failure of which implies non-identifiability. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is well written and the motivation for the presented theoretical work is well justified. Notation, definitions and assumptions are clearly stated. Though the contributions of the proposed theoretical results have important implications for the analysis, understanding and identifiability of structural causal models, the practical implications beyond of the analytical tools in Algorithms 1 and 2 remain to be seen.\n\nThere are few typos beyond those presented in Section F of the SM, thus the paper will benefit from careful proofreading.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and assumptions of the proposed theoretical work are fully described.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "MnE4ImnHvHg", "reviewer": "Reviewer_mQGH", "summary": "The paper presents identification algorithms for counterfactuals  and conditional counterfactuals. The counterfactuals can be nested. The input consists of observations and experiments were the interventions can be arbitrary. Proofs for soundness and completeness are provided. No software is included.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "[Note: I am an additional reviewer and have not seen the earlier comments or the authors' rebuttal.]\n\nThis is a potentially strong paper but I would not like to see it published in the current form because I see that the presentation could be improved in many ways. I am afraid that publishing the paper in the current form would create confusion. On the other hand, I think it is relatively easy to fix the paper and resubmit.\n\n1) The authors do not explain how their proposal differs from the current state-of-the-art.  For years I have believed that the algorithm published by Shpitser & Pearl (2007,2008) completely solves the counterfactual identification problem. The manuscript implicitly indicates that this is not the case but do not present the novel contribution in clear and direct way. It is should not be readers' task to find the subtle differences between the proposed algorithm and the algorithm published by Shpitser & Pearl. I would like to see the differences explicitly stated and demonstrated in an identification problem that is solvable with the proposed algorithm but not with the existing algorithms.\n\n2) The area chair has expressed a concern that a query could be identifiable from marginalization of  some other form than the one considered (e.g. the last line of Algorithm 1). I share this concern because I cannot see an immediate reason why some other marginalization could not be used.\n\n3) The  notation gets really heavy in some places like in line 9 of Algorithm 1.\n\n4) I traced algorithm 2 in Fig. 5(a) and obtained the same result as in equation (23). I ran a simulation to check the result numerically. So I can confirm that the algorithm works correctly in this example.  Proofs are of course needed but these kind demonstrations could serve the average reader who does not have the perseverance to study the proofs in detail.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " I would say that \"Arbitrary surrogate experiments\" in the title is a too strong statement. Although the interventions can be arbitrary, all variables are always measured in the experiments. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "GeD3hHCN_B", "reviewer": "Reviewer_KaGC", "summary": "This submission presents two contributions to the theory of counterfactual inference from observational and experimental data. First, it reduces nested counterfactuals (which are often required for standard estimates in the potential outcomes literature) to their non-nested counterparts. Second, it introduces a necessary and sufficient graphical condition under which these (conditional and marginal / nested and non-nested) counterfactuals are non-parametrically identifiable from observational and experimental data.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This is overall a very strong submission, tackling an important problem with what appears to be a technically correct approach. \n\nIn particular, I found the examples throughout the paper to be particularly helpful in understanding (i) how certain estimands could be connected to nested counterfactuals, and (ii) how the various theorems imply useful conclusions towards identification and estimation. This is particularly important in technically dense theoretical work such as this, and I would even encourage the authors to expand on the existing examples to further improve the paper's readability.\n\nI would appreciate if the authors could respond to a few minor questions about the results.\n\n1. Theorem 5 and Theorem 7 are described as \"completeness\" results, but the statements of the theorems appear to provide soundness and completeness. Could the authors clarify this?\n\n2. It appears that this submission only provides identification results for counterfactual queries that are averaged over units, and not unit-level counterfactual identifiability results. Could the authors clarify how unit-level identification results may or not differ? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not addressed limitations and societal impact, but because of the theoretical nature this is not necessary.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "B_1Mh2gcDz", "reviewer": "Reviewer_xPoj", "summary": "In this causality paper the evaluation of nested counterfactuals is reduced to that of unnested ones together with an algorithm for identification. This is a dense technical contribution, proofs are clearly detailed in the supplementary material. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The contribution is clearly an advance for the state of the art in causality research. I personally missed some attention in better motivating the importance of nested/conditional CFs in practical application, but apart from that I see no reasons for not accepting the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Nothing.", "review_text": "", "extra_scores": {"ethical_concerns": "Nothing.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "1ptj-zc5iyL", "reviewer": "Reviewer_EAGq", "summary": "This paper aims to use the theory of causal graphical models to yield a sound and complete identification algorithm for identification of a joint probability of counterfactual events from a combination of observed and interventional distributions.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "\nThe paper is very difficult to follow, as written.  The paper would definitely benefit from worked examples of the operation of the algorithms, and at least an outline of the proof strategy for soundness and completeness.  The proofs are very difficult to follow otherwise.\n\nIt appears to generalize results in [10].  However, the paper completely fails to mention (\"Complete Identification Methods for the Causal Hierarchy\", Shpitser and Pearl, 2008), which gives an algorithm for identification of counterfactual events in terms of all interventional distributions P* -- the same problem the authors consider.\n\nMany of the concepts the authors introduce, e.g. counterfactual factors, eliminating redundancy, and detecting inconsistency of events, and the problem of identifying a joint probabilities of counterfactual events and conditional probabilities of counterfactual events (at the third level of the ladder of causation) in terms of interventions distributions (at the second level) first appeared in the above reference.\nSpecifically, identification of counterfactual joints and conditionals is given by the ID* and IDC* algorithms, respectively.\n\nIn addition, the above reference gives a graphical view of the problem based on counterfactual graphs (a generalization of Balke and Pearl's twin network graphs) that shed light on many concepts the authors use that are typically graphical (e.g. ancestors of counterfactuals -- in what graph?, counterfactual factors -- corresponding to districts in what graph?, ancestral set factorization -- with respect to what graph?) but appear not to be in the authors' paper.\n\nGiven that the omitted paper deals with exactly the same problem, the omission is quite disappointing, and leads to serious worries regarding novelty, and the true relationship of the authors' work to prior work.  Are the authors' algorithms effectively the same as ID* or IDC*?  Did these algorithm \"miss something\" that the authors caught?\n\nOther comments:\n\nTheorem 1: this appears to be definition of notation, rather than a theorem.  In other words, the semantics the authors use give the definition of the joint distribution over counterfactuals using the structural model (via equation (1)), while Theorem 1 is a definition of the \"capital letters in the subscript\" notation, which is otherwise undefined via (1).\n\nMinor comments:\n\n\"Further, there are also result on the identification of path-specific effects, which correspond to counterfactuals that isolate specific paths in the graph. In particular, [1] provides a complete algorithm for identification from observational data.\"\n\nUnlike other results the authors cite, [1] appears to only apply to fully observed models.  The extensions to hidden variable models appear in (\"Identification of Personalized Effects Associated With Causal Pathways\" Shpitser and Sherman, 2018).\n\n---\n\n\"the composition axiom [13, 7.3.1]\"\n\nTo most readers, this is probably known as consistency.  It might be worth pointing this out to improve readability.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a methodological paper causal inference: no potential negative societal impacts are foreseen by this reviewer.\n\nFor limitations, please see the main body of the review.", "review_text": "", "extra_scores": {"ethical_concerns": "None noted.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper was discussed at length between the AC and SAC, and between the SAC and program chairs.  The AC was strongly against publication due to the lack of appropriate engagement with prior work.  The SAC and program chairs agree with this concern.  The discussion of the relationship with prior work is insufficient and absolutely must be addressed in the final version.  However, in light of the positive sentiment from four out of five reviewers, we believe the paper should be accepted.

(We are counting as "positive sentiment" one of the expert reviewers who gave the paper a low score, based on their comment: "This is a potentially strong paper but I would not like to see it published in the current form because I see that the presentation could be improved in many ways. I am afraid that publishing the paper in the current form would create confusion. On the other hand, I think it is relatively easy to fix the paper and resubmit.")

We expect the authors to address the points raised by the expert reviewers.  We would not be accepting this paper if we didn't think this was something the authors were capable of doing.

The original meta-review provided by the AC follows.

----

A summary from one of the reviews:

"The authors study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. They prove the counterfactual unnesting theorem (CUT), which allows for the mapping of nested to unnested counterfactuals. Then they introduce 1) sufficient and necessary graphical conditions for counterfactual identification from an arbitrary combination of observational and empirical distributions, and 2) an algorithm for identifying nested counterfactuals, the failure of which implies non-identifiability."

The paper was initially received fairly positively. However, some positive reviews were very short and lacking detail, and all were relatively low confidence. As a result, an additional expert reviewer's opinion was solicited, and (at the behest of the senior AE), another expert reviewer.

The paper received an extensive discussion, both with the authors and among reviewers. The result of this discussion was an overall reduction of scores. The concerns were as follows.

First, the authors' contribution builds on prior work on identification of joints and conditionals of counterfactual events. While the authors do cite this work, both expert reviewers independently felt that there was far from a sufficient comparison to it. In particular, while it is clear that the authors consider a generalization (where only some interventional distributions are allowed, in the spirit of (Lee et al, 2019)), it is not at all clear if sufficiently novel methods, in light of existing prior work, are needed to address this generalization. The authors' manuscript, as it is currently written, does not make it clear what is novel developments unique to the paper, and what is a reformulation of known prior work.

Second, the authors claim to consider identification of nested distributions, and discussion of nested distributions forms much of the paper (and indeed appears in the title). However, the authors do not consider a complete algorithm for the problem of identifiability of nested counterfactuals (and indeed did not seem to answer a direct question about this). Thus, reviewers felt the contribution, as written, did not properly emphasize the actual target they considered. In other words, it is true that the algorithm considered nested counterfactuals as valid targets, but only in a weak sense that such a counterfactual is a (marginal) function of a joint set of events (via what the authors call the CUT). But it is surely the case that in some cases marginals are identified while joints are not.

As a result, the reviewers felt the paper needs a restructure and another round of reviews.

Feedback for authors.

Two independent expert reviewers agreed that the appear needs a more extensive discussion of prior work, in order to make it clearer how novel the contribution is. The authors also need to make it clearer what the completeness argument applies to. It appears not to apply to nested distributions (a class of queries appearing in the title). This is quite confusing. Please address these issues when preparing your revision.
Decision: Accept (Poster)