--- title: "From Statistical Transportability to Estimating the Effect of Stochastic Interventions" authors: - "Juan D. Correa" - "Elias Bareinboim" doi: "10.24963/ijcai.2019/230" url: "https://ijcai.org/proceedings/2019/230" pdf: "https://ijcai.org/proceedings/2019/0230.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "1661-1667" track: "Main track" keywords: - "Uncertainty in AI: Graphical Models" - "Knowledge Representation and Reasoning: Action, Change and Causality" --- # From Statistical Transportability to Estimating the Effect of Stochastic Interventions Juan D. Correa, Elias Bareinboim *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 1661-1667. DOI: [10.24963/ijcai.2019/230](https://doi.org/10.24963/ijcai.2019/230) ## Abstract Learning systems often face a critical challenge when applied to settings that differ from those under which they were initially trained. In particular, the assumption that both the source/training and the target/deployment domains follow the same causal mechanisms and observed distributions is commonly violated. This implies that the robustness and convergence guarantees usually expected from these methods are no longer attainable. In this paper, we study these violations through causal lens using the formalism of statistical transportability [Pearl and Bareinboim, 2011] (PB, for short). We start by proving sufficient and necessary graphical conditions under which a probability distribution observed in the source domain can be extrapolated to the target one, where strictly less data is available. We develop the first sound and complete procedure for statistical transportability, which formally closes the problem introduced by PB. Further, we tackle the general challenge of identification of stochastic interventions from observational data [Sec.~4.4, Pearl, 2000]. This problem has been solved in the context of atomic interventions using Pearl's do-calculus, which lacks complete treatment in the stochastic case. We prove completeness of stochastic identification by constructing a reduction of any instance of this problem to an instance of statistical transportability, closing the problem. ## Full text ## 1 Introduction Generalizing causal and statistical findings across settings is central in scientific inferences as well as in many applications throughout artificial intelligence and machine learning. The environment where the data is collected (source) is related to, but almost never the same as, the one where the inferences are intended (target). If the target environment is arbitrary, or drastically different from the training (source) environment, no learning could take place. However, the fact that we learn and perform relatively well in a new environment suggest that certain environments share common characteristics and that, owing to these commonalities, causal and statistical claims would be valid and robust even in settings where no or very little data is available [Pearl, 2000; Spirtes et al., 2001; Bareinboim and Pearl, 2016; Pearl and Mackenzie, 2018]. Remarkably, the anchors of knowledge that allow extrapolations to take place are eminently causal, following from the stability of the mechanisms shared across settings [Aldrich, 1989]. The systematic analysis of these mechanisms and the conditions under which extrapolations could be formally justified has been studied in the literature under the rubric of transportability theory [Pearl and Bareinboim, 2011]. A number of results showed the robustness and efficiency of transportability under a wide range of conditions [Bareinboim and Pearl, 2012; Lee and Honavar, 2013a; Lee and Honavar, 2013b; Bareinboim and Pearl, 2013; Bareinboim and Pearl, 2014]; for a survey, refer to [Bareinboim and Pearl, 2016]. Despite all the progress achieved so far, most of these results were focused on the conditions under which causal distributions could be extrapolated, leaving a general class of extrapolation problems without solution, namely, non-causal distributions. In practice, on the other hand, many problems in AI and ML today, including classification and clustering, entail the learning of a (non-causal) probability distributions of the form P(y|x). In these settings, it's also the case that the training environment does not always match the one where the classifier, for example, is intended to be deployed. Depending on the differences between environments, the distribution P(y|x) may not be a good predictor in the target domain. The mismatches between the source and target environments are due to the differences in the underlying causal mechanisms and data-collection method. Through the lens of causal reasoning, this setting has been called statistical transportability in [Pearl and Bareinboim, 2011], dataset shift, or domain adaptation in [Qui˜noneroCandela et al., 2009; Zhang et al., 2013; Zhang et al., 2015; Magliacane et al., 2018; Rojas-Carulla et al., 2018]. The statistical transportability problem has been formalized but has not been solved systematically nor in its non-parametric version. For concreteness, consider the following example. Example 1. An internet company stores records on the type of advertisement displayed to its customers (X) and whether the corresponding product was sold (Y ) in its website Π. Each user's age (W) is also measured, which affects both the ad format (X) as well as her/his propensity for buying the product (Y ). The distribution P(x,w, y) can be estimated from this dataset. The company plans to expand to a different country Π∗ and call the data science team to help to predict Y given X, P ∗ (y|x), in the new market. In transportability theory, the differences in the causal mechanisms across settings are encoded through square nodes (□), which will be formally defined later on. The causal diagrams shown in Fig. 1 entail different statistical patterns in the data when comparing against the source, when - C1 the age distribution (P ∗ (W)) is significantly different, - C2 the strategy to select the ad format (X) is different, and - C3 the buying behavior (Y ) differs, for instance, since users are less wealthy in population Π∗ . For case (C1), the causal analyst in the team suggests that they should use data from the Census in population Π∗ , and estimate the new age distribution, P ∗ (w). The team goes on to say that this will allow the target query P ∗ (y|x) to be written in a convenient form, namely, The r.h.s. of the expression is estimable by combining data from the source (P (v)) and the smaller dataset from the target (P ∗ (w)). For the second case, (C2), the new strategy to select ads (i.e., P ∗ (x|w)) is needed, the team suggests, so that the effect of the new policy in Π∗ can be assessed. It further says that, for case (C3), P ∗ (y|x) needs be obtained from scratch in Π∗ . The main goal of this paper is to explicate the rationale behind this analysis and, more broadly, to provide a systematic way of deciding statistical transportability in arbitrary settings. Specifically, the contributions of the paper are as follows. In Sec. 3, we develop a novel graphical decomposition of the observational distribution that takes the latent structure into account, which generalizes the celebrated C-component strategy. In Sec. 4, we develop a sound, complete, and efficient algorithm to decide whether a query P ∗ (y|x) can be transported from a combination of data in the source (P(v)) and target domains (P ∗ (w),W⊆V). In Sec. 5, we connect the problem of identification of dynamic plans (stochastic interventions) with statistical transportability, and show a reduction that proves the completeness of the former. After all, the algorithmic treatment and completeness results proved in Sections 4 and 5 close two long-standing problems in causal inference, respectively, statistical transportability [Pearl and Bareinboim, 2011] and identification of dynamic plans [Pearl and Robins, 1995; Pearl, 2000, Ch. 4.4; Dawid et al., 2010]. ## 2 Preliminaries We use as basic semantical framework of our analysis Structural Causal Models [Pearl, 2000, pp. 204-207], which will allow the formal articulation of the invariances needed to extrapolate findings across settings, as defined next: Definition 1 (Structural Causal Model (SCM)). A structural causal model M is a 4-tuple 〈U, V, F, P (u)〉, where - U is a set of exogenous (unobserved) variables; - V is a set of endogenous (observed) variables; - F represents a collection of functions F = {fi} such that each endogenous variable Vi ∈ V is determined by a function fi ∈ F, where fi is a mapping from the respective domain of Ui ∪ Pai to Vi, with Ui ⊆ U, Pai ⊆ V \ {Vi}; S 1 Figure 1: Models where the differences between source and target domain affect different variables. ![Image](https://ijcai.org/proceedings/2019/fulltext/230/image_000000_240553fd849744f8288333640966ab243f0ad00aee56ee3f7eb1410fe8000fd9.png) - The uncertainty is encoded through a probability distribution over the exogenous variables, P(u). Every SCM M is associated with one causal diagram represented as a directed acyclic graph where any variable in Vi ∈ V is a vertex, and there exists a directed edge from every variable in Pai to Vi. Also, for every pair Vi, Vj ∈ V such that Ui ∩Uj ̸= ∅, there exists a bidirected edge between Vi and Vj . We denote this causal diagram with the letter G. A SCMM induces a probability distribution P (v) over the set of observed variables V such that where each term P(vi|pai, ui) corresponds to the function fi ∈ F in the underlying structural causal model M. These functions represent autonomous mechanisms affecting only its corresponding Vi, locally [Aldrich, 1989]. In this paper, we operate non-parametrically, i.e., making no assumption about the particular functional form or the distribution of the unobserved variables [Pearl, 2000]. In this case, the only assumption is that the arguments of the functions are known as encoded through the causal diagram G. If each exogenous Ui ∈ U affects only one observed variable Vi ∈ V, the causal model is called Markovian. In this class of models, the joint distribution over observables can be factorized as the product of the conditional probabilities of each variable given its parents, i.e., P(v) = ∏i P(vi|pai). Those conditional distributions provide a canonical way to parametrize a model, since once each of them is given, the whole joint distribution is characterized. In contrast, in most real-world scenarios, Markovianity rarely holds since latent variables commonly affect more than one observable. In this paper, we focus on models where Markovianity does not hold, which we call non-Markovian. Random variables are denoted with uppercase letters (e.g, C) while their instantiations to particular values are written in lowercase (e.g, c). Similarly, sets of variables are written in bold (e.g, C) and a vector of a value assignment to them in lowercase-bold letters (e.g., c). Following standard notation, we denote by GWX the graph that is the same as G except that the edges incoming to variables in W and the edges going out from variables in X are removed. Let G[C] be the subgraph of G made only of nodes in C⊂V and the edges between them. When considering any topological order V1, . . . , Vk consistent with G, let D≤i = {Vd1 , . . . , Vdi } be the set of variables in D ⊂ V ordered before Vdi (including Vdi ), and D>i = D \ D≤i for i = 1, . . . , k, and D≤0 = ∅. We define Pa(C) and An(C), as the union of C ⊂ V with its parents and ancestors, respectively. ## 3 Factorization of Non-MarkovianModels In order to find a complete method for obtaining P ∗ (y|x) from P(v) and P ∗ (w), we will decompose both input and output distributions into small factors identifiable from data. We introduce a strategy for decomposing distributions induced by Non-Markovian models, and derive a number of corresponding graphical and algorithmic properties. Overall, once both input and output distributions are canonically decomposed into factors, we solve the task if every factor of the output can be obtained from the available inputs. Our factorization builds on constructs known as c-factors and c-components developed by Tian and Pearl in (2002a; 2002b). We start by augmenting these definitions to explicitly account for marginalization. First, let C,H ⊆ V be disjoint subsets, define the quantity Q[C‖H], called c*-factor, to denote the following function where pai and ui are the sets of observable and unobservable parents of Vi, respectively; and for any set B ⊆ V, define U(B) = ⋃Vi∈B Ui. For consistency, we define Q[∅ ‖ .] = 1. For the three diagrams in Fig. 1, the factor Q[X,W, Y ‖∅] is equal to P(w)P(x|w)P(y|w, x)=P(v). Similarly, the c*- factor Q[X, Y ‖ W ]= ∑w P (w)P (x|w)P (y|w, x)=P (x, y). On the other hand, for the non-Markovian model in Fig. 2(a), where U ′ = {U1,U2,U3} is the corresponding set of unobserved variables represented by the bidirected edges between the pairs of observables (C, Z), (B, C), (B, D). To simplify the notation, whenever clear from the context, we will write Q[C‖H](pa(c∪h)\h) as Q[C‖H], Q[C‖ ∅] as Q[C], and whenever C = {Vi}, H = {Vj}, we will write Q[Vi ‖ Vj ] instead of Q[{Vi} ‖ {Vj}]. Decomposing Distributions based on the Causal Graph. As functions of probability distributions, c*-factors can, sometimes, be "factorized" depending on the variables that are marginalized out. The following definition characterize such decomposability property. Definition 2 (C*-Component). Let G be a graph over variables V and let C,H ⊆ V be two disjoint subsets such that C ∪ H = V. Then, C ∪ H can be partitioned, relative to C, into sets {(C1‖H1), (C2‖H2), . . . (Cl‖Hl)}, such that {C1, . . . , Cl} partition C and {H1, . . . , Hl} partition H. Two variables Vj, Vk ∈ V belong to the same (Ci‖Hi) if there exists any path (regardless of the directionality of the arrows) between them in GC. For G in Fig. 2(a), with V = {A, B, Y, Z, C, D} there are two c*-components relative to V, i.e.: (Z,C,B,D‖∅) and (A, Y ‖∅), which are the two disconnected subgraphs in GV in (Fig. 2(b)). Meanwhile, for G[Y,Z,C,D] in Fig. 2(c), where V = {Y, Z, C, D}, the c*-components relative to {Z, Y } are Figure 2: (a) Causal graph G, (b) subgraph GV, and (c) subgraph G[Y,Z,C,D]. Further, G[Y,Z,C,D]Y,Z can be obtained from the subgraph (c) by removing the arrow Z → Y (shown in gray). ![Image](https://ijcai.org/proceedings/2019/fulltext/230/image_000001_414c8725053ef256c5a19f1fbf1170aff2407d0fb5fb59ca9c5d5384a855c97f.png) (Y ‖D) and (Z‖C). This is clear when we look at the graph G[Y,Z,C,D]Y,Z where the outgoing arrows from Z and Y are removed (in this case, the arrow is shown in grey). The importance of the c*-components stems from the fact that they lead to a natural decomposition of the corresponding c*-factors, which will disentangle the latents in a fundamental way. For example, we note that the factor Q[Y,Z ‖C,D] = ∑u,c,d P (z|c, u1, u2)P (c|u1, u2)P (d|u3)P (y|z, d, u4)P (u) can be decomposed as the following independent factors, which is equal to Q[Z ‖C]Q[Y ‖D] (i.e., product of (Y ‖D) and (Z‖C)). The lemma below generalizes this property. Lemma 1 (C*-Decomposition). Let D ⊆ V\H, and assume that D is partitioned into c*-components (Di‖Hi)i=1,...,l in the subgraph G[D∪H], relative to D. Then we have (i) Q[D‖H] decomposes as (ii) Let a topological order of the variables in D be Vd1 <· · ·<Vdk in G[D∪H]. To illustrate this lemma, suppose we are given Q[Y,Z ‖C,D], and note that according to Eqs. (7)-(8), As it turns out, it is not always possible to uniquely identify a particular c*-factor from the available data. The following definition formalizes this notion. Definition 3 (C*-factor Identifiability). A c*-factor Q[C‖H] is said to be identifiable from a causal graph G and a c*-factor Q[T‖L] if Q[C‖H] can be computed uniquely from Q[T‖L]. That is, if QM1 [C‖H]=QM2 [C‖H] for every pair of models M1 and M2 that induce the same G with QM1 [T‖L]=QM2 [T‖L], Q[C‖H] is identifiable. For instance, the c*-factor Q[Z ‖∅] in Fig. 2(a) cannot be identified from Q[Z, C ‖ ∅]. In words, there exists two different SCMs M1 and M2 with the same G and generating the same Q[Z, C ‖ ∅]= ∑u1,u2 P (z|c, u1)P (c|u1, u2)P (u1, u2), but with different Q[Z ‖ ∅]= ∑u1 P (z|c, u1)P (u1), for some values z, c. In Alg. 1, we develop a procedure to identify c*-factors from other c*-factors, which we called Identify*. This algorithm uses a modified version of Identify [Tian and Pearl, 2002a] as a subroutine (for details, see Appendix A). Theorem 1. Q[C‖H] is identifiable from Q[T‖L] in G if and only if Identify* returns an expression for it. In words, failure of Identify* implies there exist SCMs M1,M2 compatible with G that induce the same Q[T‖L] but QM1 [C‖H](v) ̸= QM2 [C‖H](v), for some values v. Query Decomposition. Once the c*-factors and components are well-understood given a specific causal graph, we turn our attention to the query distribution, P(y|x), given by The distribution P(y, x) can be expressed in terms of c*- factors, as shown in the following example. Example 2. Consider the query P(y|z) in the context of the graph in Fig. 2(a), we have where the last equality follows from the fact that D, Y /∈ An(Z)G[Z,C,D,Y ] . The graph G[An(Y,Z)] = G[Y,Z,C,D] can be partitioned relative to {Y, Z} into c*-components (Y ‖D) and (Z‖C) (the connected components in G[Y,Z,C,D]Y,Z, shown in Fig. 2(c)), and by Lemma 1, Q[Y,Z ‖C,D] decomposes as Q[Z ‖C]Q[Y ‖D], and The conditional distribution will be equal to Remarkably, while P(y, z) depends on Q[Z ‖C] = ∑c P(z|c)P(c) and Q[Y ‖D] = ∑d P(y|z, d)P(d), the query P(y|z) is independent of Q[Z ‖C]. Naturally, if the joint distribution P(y, z, d, c, b, a) is available, P(y, z) is trivially computable. But, if we consider a scenario with two domains (e.g., websites), Π and Π∗ , with the goal of estimating P ∗ (y|z) in the target domain, the previous analysis (example 2) shows that even if the distribution P ∗ (z, c) and P(z, c) are different, P ∗ (y|z) can still be obtained from data in the source alone. A more surprising conclusion is that if there are differences across settings in the distribution of D, P ∗ (d) needs to be measured despite D not appearing in the query expression. This leads to a more fundamental issue about which factors of the model are really required to compute a certain query. The following result answers this question in generality. ## Algorithm 1 Identify*(C, H, T, L, Q, G) L⊆V\An(T)G[T∪L] , Q = Q[T‖L], graph G. Assuming G[C∪H] and G[T∪L] are composed of a single c*-component. Output: Expression for Q[C‖H] in terms of Q or Fail. - 1: B=H\ L. - 2: if B ̸= ∅ then - 3: Let (C1,H1), (C2,H2), . . . be the c*-components of G relative to B intersecting variables in C. - 4: return ∑b ∏i Identify*(Ci,Hi,T,L,Q, G) - 5: end if - 6: return Identify(C,T,H,Q, G) Lemma 2. Let Y,X⊆V be disjoint sets of variables, then where (A\Y‖H∪Y) is the union of the c*-components of G[An(Y∪X)], relative to X, intersecting the variables in Y. In example 2, this maps to A = {Y } and H = {D} since (∅‖Y, D) is the only c*-component relative to Z in G[Z,Y,C,D] that intersects variables in Y. ## 4 Transporting Probabilistic Relations In this section, we build on the machinery developed so far to decompose conditional distributions (e.g., classifiers) and extrapolate them from one domain to another, as illustrated in Example 1. This task is known as statistical transportability [Pearl and Bareinboim, 2011, Section 5]. In any transportability instance, the source and target domains, Π and Π∗ , are modelled explicitly and assumed to be governed by two corresponding SCMs, M and M ∗ . Each causal model is accompanied by its corresponding causal graph, in this case, G and G ∗ . In the language of transportability, a special indicator variable T (drawn as squares in G ∗ ) is used to represent differences between the two domains. A T-node points to a variable affected by unobserved factors (causal mechanism or distribution of exogenous) that are distinct across domains. Formally, G ∗ contains an extra edge Ti → Vi whenever there might exist a discrepancy fi ̸= f ∗ i or P(Ui) ̸= P ∗ (Ui) between M and M ∗ . This also allows one to accommodate structural changes such as when Vi has a different parent set across domains. Recall case 2 from Example 1. Note that a T -node pointing to X indicates that the underlying function that assign values to X is different in the source and target domains, which implies that P ∗ (x|w) ̸= P(x|w). The query P ∗ (y|x) can be transported in this case if we have P ∗ (x, w) or more specifically P ∗ (x|w). To see how, write the query as Due to the absence of a square node pointing to W and Y in Fig. 1(b), it follow that P ∗ (y|x,w) = P(y|x,w) and P ∗ (w) = P(w), which leads to the following expression: Figure 3: Causal diagrams involved in transporting P ∗ (y|x, z). ![Image](https://ijcai.org/proceedings/2019/fulltext/230/image_000002_cd553e31d84043548eec93c30648350edf6e0c74b67779084d3c3e8a71b096c7.png) Eq. (18) is a mixture of factors from Π and Π∗ within the available input distributions, P ∗ (x|w) and P(w, x, y). On the other hand, the third case (Fig. 1(c)) requires one to measure P ∗ (y|x,w) in the target domain, which usually means having the full distribution P ∗ (y, x,w). In this case, the task is done from scratch, without any transportability. Next, we formally state the statistical transportability task. Definition 4 (Statistical Transportability [Pearl and Bareinboim, 2011]). Given two populations, Π and Π∗ , characterized by probability distributions P and P ∗ , and causal diagrams G and G ∗ , respectively; a statistical relation R(P) is said to be statistically transportable from Π to Π∗ over W ⊂ V if R(P ∗ ) is identified from P , P ∗ (W), G, and G ∗ . We will now focus on the general case of transporting relationships R of the form R(P ∗ ) = P ∗ (y|x) for any pair of disjoint sets of variables X,Y ⊂ V, from inputs P(v) and P ∗ (w). Using Lemma 2 in the context of Π∗ , we can write where Q∗ [. ‖ .] describes a c*-factor in the domain Π∗ and consistent with the corresponding causal model G ∗ . Example 3. Figs. 3(a) and (b) represent the causal graphs in the source and target domains, Π and Π∗ . The goal is to transport R = P ∗ (y|x, z) to a domain Π∗ where the behavior of the variable Z depends only on C, which contrasts with the Π's behavior where Z depends on an unobservable variable shared with Y (bidirected arrow). Note that the variable A in Π∗ has an extra dependency on the value of X that is not present Π. Only data from P ∗ (x, a) is available in Π∗ . Due to their distinct behaviors, G ∗ has T-nodes pointing to Z and A (i.e., □ → Z,□ → A). Using Lemma 2 w.r.t. R, note that the c*-components relative to {X,Z} in G ∗ [An(Y,Z,X)] that contain Y is (X‖A, Y,D), yielding: which corresponds to A = {Y, X} and H = {A, D}. If An(A) ⊆ W, then the given distribution P ∗ (w) includes all variables that are ancestors of the set A in the graph G ∗ , and P ∗ (y | x) is easily estimated from P ∗ (w). If this is not the case, it is possible to leverage data from the source domain Π, namely, P(v). The key observation is that both domains Π and Π∗ share some commonalities. The following lemma formalizes this notion. Lemma 3. [C*-invariance] Let G, G ∗ be a pair of graphs for 〈M,M ∗ 〉, then Q∗ [C‖H] = Q[C‖H] if G ∗ does not contain a selection node Ti pointing to any Vi ∈ C ∪ H. ## Algorithm 2 Transport*(G, G ∗ , Y, X, W) Input: G, G ∗ causal diagrams over a set of variables V, Y, X ⊆ V disjoint subsets of variables, W ⊆ V. Output: P ∗ (y|w) in terms of P(v), P ∗ (w) or Fail. - 1: Let (A‖H) be defined as in Lemma 2 with G ∗ . - 2: Let D ⊆ A∪H be the set of vars. pointed by T -nodes. - 3: Let I be the set of c*-components (Ai‖Hi), i = 1, . . . , k of G ∗ [A∪H] , relative toA∪(W∩H), such that (Ai∪Hi)∩ D = ∅, and Identify*(Ai,Hi,V, ∅, P(v), G) ̸= Fail; and let N be the rest of them. - 4: NA ← ⋃(Ai‖Hi)∈N Ai and NH ← ⋃(Ai‖Hi)∈N Hi. - 5: if NA ̸⊆W then return Fail. - 6: Q∗ [NA ‖NH] ← ∑w\nA P ∗ (w). - 7: Q∗ [A‖H]← ∑ w∩h Q∗ [NA‖NH] ∏ (Ai‖Hi)∈I Q[Ai‖Hi]. In words, if there is no T-node pointing to any variable in a set C ∪ H in G ∗ , the c*-factor Q∗ [C‖H] is invariant and can, therefore, be transported from the source domain. In example 3, the c*-factor Q∗ [Y ‖D]=Q[Y ‖D], while Q∗ [X, A ‖ ∅] may be different than Q[X, A ‖ ∅]. Let D ⊆ A ∪ H be the subset of variables involved in Eq. (19) that are pointed by T-nodes in G ∗ . Then, factors involving variables in D need to be obtained from P ∗ (w), which is equivalent to Q∗ [W‖An(W)\W]. Let N be the set of c*-components in the graph G ∗ [An(A∪H)] , relative to A∪(W∩H), that intersect any variable in D or those that cannot be identified from P(v). Let NA = ⋃(Ai‖Hi)∈N (Ai) and NH = ⋃(Ai‖Hi)∈N (Hi). In Example 3, G ∗ [A∪H] (Fig. 3(c)) has, relative to {Y,X,A}, c*-components (Y ‖D) and (X,A‖∅). The only variable pointed by a T-node is A, so (NA‖NH) = (X,A‖∅). That need to be obtained from P(x, a); the following lemma characterizes this operation. Lemma 4. Given a causal diagram G, let C,H ⊂ V be two disjoint subsets and W ⊂ V such that H ⊆ An(C)GW . If C⊆W, then Then, if NA and NH satisfy NA ∪NH ⊆ An(W)G∗ and NA ⊆W, Lemma 4 licenses Let I be the c*-components of G ∗ [A∪H] not in N, that by definition, are all identifiable from P(v). Consequently, the quantity Q∗ [A‖H] is identifiable from P(v) and P ∗ (w) as: For Example 3, we can obtain Q∗ [Y ‖D]=Q[Y ‖D], using Identify*(Y, D, V, ∅, P (v), G) and in terms of P (v) as And the final expression is We incorporate the discussion so far in the procedure Transport* shown in Alg. 2, which is complete for this task as given by the following statement. Theorem 2. [Completeness] The relationship R = P ∗ (y|x) is transportable from P(V), P ∗ (W) and G, G ∗ if and only if Transport*(G, G ∗ ,Y,X,W) does not fail. ## 5 Identifying Dynamic Plans In this section, we investigate the identifiability of dynamic plans [Pearl and Robins, 1995; Pearl, 2000; Didelez et al., 2006] and show that it can be reduced to the problem of transportability of marginals. We further show that the procedure introduced in [Tian, 2008] is not only sound but complete. This closes the problem of identifiability of dynamic sequential plans since all sequential plans that are computable from observational data can be algorithmically determined. In this setting, we assume that the observational data P (V) is collected from a SCM that induces a causal diagram G with observed variables V in domain Π. The goal is to determine the behavior of Y ⊂ V under a hypothetical intervention that changes the mechanisms of variables X ⊂ V, which we call domain Π∗ . The probability distribution over V in the intervened system is P ∗ (V) and the associated graph is G ∗ . The identifiability task amounts to computing P ∗ (Y) in that hypothetical world using P(V), the assumptions encoded in G, G ∗ , and knowledge about the interventions. There are different ways of performing an intervention and changing the value of the corresponding variable, say X ∈ X. Atomic or do-intervention. The variable X is set to a constant value x′ in its domain, i.e., P ∗ (x | pa ∗x , u∗x ) = 1X=x′ . Conditional Intervention. The value of X is determined as a function g(pa ∗x ), that is, P ∗ (x | pa ∗x , u∗x ) = 1X=g(pa ∗x ). Stochastic Intervention. X will take value x in its domain according to an externally specified probability distribution P ∗ (x | pa ∗x ), namely, P ∗ (x | pa ∗x , u∗x ) = P ∗ (x | pa ∗x ). We note that these different types of interventions can be encoded in a similar fashion using the formalism of transportability by adding T-nodes pointing to each variable in the interventional set, X. This indicates that their functions are different that those in the original system Π. Since the new intervention is part of the input of the problem, Q∗ [X] = ∏X∈X Q∗ [X] is available in the target domain. Example 4. Consider the the dynamic plan first studied in [Pearl and Robins, 1995] and shown in Fig. 4(a). With the new transportability mapping, the goal is to assess the distribution P ∗ (y) in two hypothetical environments where: - C1 the values of (X1,X2) have been fixed to (x1, x2), in standard do-form, i.e., P ∗ (x1, x2) = 1(X1,X2)=(x1,x2). The corresponding G ∗ is shown in Fig. 4(b). - C2 the value of X1 is fixed to x1 and X2 is set conditionally on Z based on a function g(z). That is, P ∗ (x1) = IX1=x1 and P ∗ (x2 | z) = 1X2=g(z). The corresponding G ∗ is shown in Fig. 4(c). Figure 4: Causal diagrams associated with Example 4. ![Image](https://ijcai.org/proceedings/2019/fulltext/230/image_000003_8d0c27602d19d7a02d824ab01f58b4e6f24d093f6710aeab1556a12da8060e44.png) In [Pearl and Robins, 1995], the impact of the plan in the outcome variable Y is denoted as P(y | ˆ x1, . . . , ˆ xn) (written as P(y; σx) in [Tian, 2008]). The following follows: Definition 5 (Plan Identifiability). A sequential plan is said to be identifiable if P(y | ˆ x1, . . . , ˆ xn) (equivalently P(y; σx)) is uniquely computable from the joint distribution P(v), for every assignment (x1, . . . , xn). We show next that the reduction from plan identification to transportability is indeed valid and that the corresponding completeness follows. Theorem 3. The effect P(y| ˆ x1, . . . , ˆ xn) (or, P(y; σx)) is equivalent to P ∗ (y) where Π∗ is related to G ∗ and Q∗ [X] is determined by the corresponding intervention on X. Corollary 1. Transport* is complete for plan identification given P (v) and Q∗ [X]. Corollary 2. The condition in Thm. 1 from [Tian, 2008] is also necessary for dynamic plan identification. Using this result, one can immediately see that contrary to previous beliefs [Pearl, 2000, pp.120], and as hinted by [Tian, 2008], the plan in Example 4(C2) is not identifiable from P(v) and Q∗ [X]. While case (C1), associated with Fig. 4(b), can be solved using do-calculus [Pearl, 1995], the extra edge Z → X2 in Fig. 4(c) (C2) makes X1 and Y dependent conditional on X2, hence the same derivation strategy does not work (see non-identifiability proof in Appendix C). ## 6 Conclusions We developed a procedure (Alg. 2) that is complete (Thm. 2) for the task of estimating a distribution P ∗ (y|x) in a target domain Π∗ using limited data from Π∗ and a probability distribution collected in a different source domain Π. The algorithm uses a canonical factorization of marginal and conditional distributions, and a procedure to identify such factors (Alg. 1 & Thm. 1). Also, we showed that identifying the effect of plans can be reduced to a statistical transportability task for which our method is complete (Thm. 3). We hope that these results provide a better understanding of the assumptions and trade-offs involved in the construction of more robust and generalizable learning systems. ## Acknowledgments This research was supported by grants from IBM Research, Adobe Research, NSF IIS-1704352, and IIS-1750807 (CAREER). We thank Amin Jaber for useful discussion and feedback on a early version of this manuscript. ## References 1. [Aldrich, 1989] John Aldrich. Autonomy. Oxford Economic Papers, 41:15-34, 1989. 2. [Bareinboim and Pearl, 2012] Elias Bareinboim and Judea Pearl. Transportability of causal effects: Completeness Results. In Proceedings of the 26th AAAI Conference on Artificial Intelligence, CA, 2012. Department of Computer Science, University of California, Los Angeles. 3. [Bareinboim and Pearl, 2013] Elias Bareinboim and Judea Pearl. A general algorithm for deciding transportabil- ity of experimental results. Journal of Causal Inference, 1(1):107-134, 2013. 4. [Bareinboim and Pearl, 2014] Elias Bareinboim and Judea Pearl. Transportability from Multiple Environments with Limited Experiments: Completeness Results. In Z Ghahramani, M Welling, C Cortes, N D Lawrence, and K Q Weinberger, editors, Advances in Neural Informa- tion Processing Systems 27, pages 280-288. 5. [Bareinboim and Pearl, 2016] Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion prob- lem. Proceedings of the National Academy of Sciences, 113(27):7345-7352, 2016. 6. [Dawid et al., 2010] A Philip Dawid, Vanessa Didelez, and others. Identifying the consequences of dynamic treatment strategies: A decision-theoretic overview. Statistics Sur- veys, 4:184-231, 2010. 7. [Didelez et al., 2006] Vanessa Didelez, A Philip Dawid, and Sara Geneletti. Direct and indirect effects of sequential treatments. In Proceedings of the Twenty-Second Confer- ence on Uncertainty in Artificial Intelligence, pages 138- 146. AUAI Press, 2006. 8. [Lee and Honavar, 2013a] Sanghack Lee and Vasant Honavar. Causal Transportability of Experiments on Controllable Subsets of Variables: z-Transportability. In A Nicholson and P Smyth, editors, Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI), pages 361-370. AUAI Press, 2013. 9. [Lee and Honavar, 2013b] Sanghack Lee and Vasant Honavar. m-Transportability: Transportability of a Causal Effect from Multiple Environments. In M desJardins and M Littman, editors, Proceedings of the Twenty-Seventh National Conference on Artificial Intelligence, pages 583-590, Menlo Park, CA, 2013. AAAI Press. 10. [Magliacane et al., 2018] Sara Magliacane, Thijs van Om- men, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij. Domain Adaptation by Using Causal Inference to Predict Invariant Conditional Distributions. In Advances in Neural Information Processing Systems, pages 10846-10856, 2018. 11. [Pearl and Bareinboim, 2011] Judea Pearl and Elias Barein- boim. Transportability of Causal and Statistical Relations: A Formal Approach. In Proceedings of the Twenty-Fifth Conference on Artificial Intelligence (AAAI-11), pages 247-254, Menlo Park, CA, 8 2011. 12. [Pearl and Mackenzie, 2018] Judea Pearl and Dana Macken- zie. The Book of Why. Basic Books, New York, 2018. 13. [Pearl and Robins, 1995] Judea Pearl and J M Robins. Prob- abilistic evaluation of sequential plans from causal models with hidden variables. In P Besnard and S Hanks, editors, Uncertainty in Artificial Intelligence 11, pages 444-453. 14. Morgan Kaufmann, San Francisco, 1995. 15. [Pearl, 1995] Judea Pearl. Causal diagrams for empirical re- search. Biometrika, 82(4):669-688, 1995. 16. [Pearl, 2000] Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, USA, 2nd edition, 2000. 17. [Quiñonero-Candela et al., 2009] Joaquin Quiñonero- Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. The MIT Press, 2009. 18. [Rojas-Carulla et al., 2018] Mateo Rojas-Carulla, Bernhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Ma- chine Learning Research, 19(1):1309-1342, 2018. 19. [Spirtes et al., 2001] Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, Prediction, and Search. MIT Press, 2nd edition, 2001. 20. [Tian and Pearl, 2002a] Jin Tian and Judea Pearl. A General Identification Condition for Causal Effects. In Proceed- ings of the Eighteenth National Conference on Artificial Intelligence (AAAI 2002), pages 567-573, Menlo Park, CA, 2002. AAAI Press/The MIT Press. 21. [Tian and Pearl, 2002b] Jin Tian and Judea Pearl. On the Testable Implications of Causal Models with Hidden Vari- ables. Proceedings of the Eighteenth Conference on Un- certainty in Artificial Intelligence (UAI-02), pages 519- 527, 2002. 22. [Tian, 2008] Jin Tian. Identifying Dynamic Sequential Plans. Uncertainty in Artificial Intelligence, 2008. 23. [Zhang et al., 2013] Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adapta- tion under target and conditional shift. In Proceedings of the 30th International Conference on International Conference on Machine Learning -Volume 28, ICML'13, pages III-819-III-827. JMLR.org, 2013. 24. [Zhang et al., 2015] Kun Zhang, Mingming Gong, and Bern- hard Scholkopf. Multi-source Domain Adaptation: A Causal View. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI'15, pages 3150-3157. AAAI Press, 2015.