Partial transportability for domain generalization
Authors: Alexis Bellot
Elias Bareinboim
Venue: Submitted to ICLR 2023 (2023)
Keywords: Causality
domain generalization

Abstract: Learning prediction models that generalize to related domains is one of the most fundamental challenges in artificial intelligence. There exists a growing literature that argues for learning invariant associations using data from multiple source domains. However, whether invariant predictors generalize to a given target domain depends crucially on the assumed structural changes between domains. Using the perspective of transportability theory, we show that invariance learning, and the settings in which invariant predictors are optimal in terms of worst-case losses, is a special case of a more general partial transportability task. Specifically, the partial transportability task seeks to identify / bound a conditional expectation $\mathbb E_{P_{\pi^*}}[y\mid\mathbf x]$ in an unseen domain $\pi^*$ using knowledge of qualitative changes across domains in the form of causal graphs and data from source domains $\pi^1,\dots,\pi^k$. We show that solutions to this problem have a much wider generalization guarantee that subsumes those of invariance learning and other robust optimization methods that are inspired by causality. For computations in practice, we develop an algorithm that provably provides tight bounds asymptotically in the number of data samples from source domains for any partial transportability problem with discrete observables and illustrate its use on synthetic datasets. 

We show that Under review as a conference paper at ICLR 2023
PARTIAL TRANSPORTABILITY FOR DOMAIN GENERALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Learning prediction models that generalize to related domains is one of the most fundamental challenges in artificial intelligence. There exists a growing literature that argues for learning invariant associations using data from multiple source domains. However, whether invariant predictors generalize to given target domain depends crucially on the assumed structural changes between domains. Using the perspective of transportability theory, we show that invariance learning, and the settings in which invariant predictors are optimal in terms of worst-case losses, a special case of a more general partial transportability task. Specifically, the partial transportability task seeks to identify bound a conditional expectation Eps [Y] x] in unseen domain π using knowledge of qualitative changes across domains in the form of causal graphs and data from source domains n ,.,,, n². solutions this problem have much wider generalization guarantee that subsumes those of invariance learning and other robust optimization methods that are inspired by causality. For computations in practice, provides tight bounds asymptotically in the number of data samples from source domains for any partial transportability problem with discrete observables and illustrate its use on synthetic datasets.
develop algorithm that provably
INTRODUCTION
Generalization guarantees are central to the design of reliable machine learning models as the predictions and conclusions obtained in one or several source domains π ...., x (c.g. in controlled laboratory circumstances, from a specific study or population, etc.) are transported and applied elsewhere, in domain n²* that may differ in several aspects from that of source domains. It is apparent that what structure and what assumptions are imposed on the relationship between domains determines whether model will generalize as intended. For example, if the target environment is arbitrary, or substantially different from the study environment, transporting predictions is difficult or impossible.
structural account of causation provides suitable semantics for reasoning about the structural invariances across different domains, and has been studied under the umbrella of transportability theory (Pearl & Bareinboim, 2011; Bareinboim et al., 2013; Bareinboim & Pearl, 2016). Each domain x' is associated with different structural causal model (SCM) M' that differs in one or more of its component parts with respect to other domains and defines different distributions over the observed variables. In practice, the SCMs are usually not fully observable, which leads to the transportability challenge of using data from one (or more) SCMs to make inference about distributions from another SCM. query, e.g. E [Y x]. said to be point identified if it can be uniquely computed given available data (from one or more domains) and qualitative knowledge about the causal changes between domains in the form of selection diagrams. However, problems of transportability, especially when no data in the target domain can be collected, the combination of qualitative assumptions and data often does not permit one to uniquely determine a given query, which is said to be non-identifiable. In such cases, partial identification methods deal with bounding given query e.g. 1< Ep [Y] x] < u in -on-identifiable problems and may still serve an informative purpose for decision-making if 0 < I
< 1. Both settings have been studied in the literature. In particular, there exists an extensive set of graphical conditions and algorithms for the identifiability of observational, interventional, and counterfactuals distributions across domains from combination of

---

Under review as a conference paper at ICLR 2023
datasets in various settings (Pearl & Bareinboim, 2011; Bareinboim et al., 2013: Bareinboim & Pearl, 2014; 2016; Lee et al., 2020; Correa & Bareinboim, 2019). For example, Lee et al. (2020) investigate the transportability of conditional causal effects, while Correa & Bareinboim (2020) investigate the transportability of soft interventions or policies, from an arbitrary combination of datasets collected under different conditions. Several methods exist also for partial identification of causal effects and counterfactuals (Balke & Pearl, 1997; Chickering & Pearl, 1996; Zhang et al., 2021) that aim at bounding insead of point-identifying particular causal effect. Despite the generality of these results, there is still no treatment or algorithms for the partial identification of transportability queries.
In the machine learning literature, notably, a version of the transportabilityy task is also widely studied as the problem of domain generalization (Wang et al., 2022). The objective is to learn prediction function with a minimum performance guarantee on any distribution in some uncertainty set that includes potential test/ / target distributions (Ben-Tal et al., 2009; Gulrajani & Lopez-Paz, 2020). This problem has implicit connections to causality and SCMs if uncertainty sets of distributions are defined on the basis of "invariant correlations", such stable conditional expectations Ep- [Y] x =.... Ep. [Y x] across training domains x² ....... T²
to be used for prediction in a target domain x and that may be learned from data sampled across sufficiently many different domains with statistical tests (Peters et al., 2016; Subbaswamy et al., 2019; Subbaswamy & Saria, 2020) or custom loss functions (Magliacane et al., 2018; Arjovsky et al., 2019; Rojas-Carulla et al., 2018; Bellot & der Schaar, 2020). For instance, Arjovsky et al. (2019) argue for learning representations that define an invariant optimal classifier across several training datasets. Subbaswamy et al. (2019); Subbaswamy & Saria (2020) use causal graphs and identifiable interventional distributions to define invariant prediction rules across domains. Notwithstanding their wide applicability. there is little theoretical understanding of the extrapolation guarantees that can be expected from invariant prediction rules given a finite set of domains. Correlations invariant across source domains need not be invariant in a target domain; and performance guarantees, in general, depend on the structural invariances assumed for their respective SCMs.
In this paper, we start by describing the conditions under which invariant prediction rules can be expected to perform well in an arbitrary target domain from first principles using the semantics of structural causal models (Pearl, 2009; Pearl & Bareinboim, 2011). 1). We then introduce broader optimization problem - the task of partial transportabilitty whose objective is to bound, instead of point estimate, query in an arbitrary target domain of interest, such Ep [Y x], given data from one or more source domains and qualitative knowledge about the causal changes between domains in the form of selection diagrams. We demonstrate that solutions to this problem subsume various instantiations of invariant predictors (in the conditions where these are adequate) and have a wider distributional robustness guarantee to any distribution in the target domain that compatible with the assumed selection diagrams. For computations in practice, we show that the partial transportability task can be solved approximately for systems of variables with finite domains with a Markov Chain Monte Carlo sampling approach. The resulting bounds are sound and tight, and provide the most informative inference on a target query given the available information.
1.1 PRELIMINARIES
We introduce in this section some basic notations and definitions that will be used throughout the paper. We use capital letters to denote variables (X), small letters for their values (x), bold letters for sets of variables (X) and their values (x), and use Ω to denote their domains of definition (I E Ωx). conditional independence statement in distribution P written as (X IL Y Z)p. A d-separation statement in some graph G is written as (X IL Y Z)g. For convenience, we denote by P(x) probabilities P(X- x), and 1(} for the indicator function equal to if the statement f-) evaluates to true, and equal to 0 otherwise. All proofs are given in the Appendix.
We use the language of structural causal models (SCMs) (Definition 7.1.1 (Pearl, 2009)) to deñin the semantics of causality. An SCM M is tuple M = (V, U,F. where V is a set of endogenous variables and U is a set of exogenous variables. Each exogeneous variable U E U is distributed according to probability measure P(u). F is a set of functions where each fv F determines the deterministic dependencies of V on other parts of the system. That is, e := (pav. uy), with Pay = V, and Uy U, the exogeneous sources of variation that influence V. With this construction, we define the potential response V(u) to be the solution of V in the model M given U u. Moreover, drawing values of exogenous variables U following the probability measure P
2

---

Under review as a conference paper at ICLR 2023
Sx
X2
Sx,
X1 Sw
W
X1 W
X1
Sw
(a) g
(b) g
(c) 9
(d) g
Figure 1: Example of graphs: (a) Causal graph of target domain x t (b) selection diagram that compares domains
with π (c) selection diagram that compares domains x* with x² (d) selection diagram that compares domains n with n
induces joint distribution over observables given by,
P(v) _ II L[fv(pav, uv) v)dP(u). JAU VeV
An SCM induces causal graph G in which each variable in V is associated with node; we draw directed edge between two variables X Y if E Pay appears as an argument of fy in the SCM, and bidirected arrow X e Y if Ux Uy # Ø. that is X and Y share unobserved confounder. The set of parent nodes of X in 9 is denoted by pa(X) = Uxex p Its capitalized version Pn includes the argument well, e.g. Pa(X), pa(X)g X. Similar definitions are used for children ch, descendants de, etc.
2 DOMAIN GENERALIZATION THROUGH THE LENS OF TRANSPORTABILITY
We adopt the setting of domain generalization. We assume access to k source domains It xt, 2²
xk with associated data distributions over a common set of variables V denoted (v),,, P2 (v),...., (v)). Our focus is on query, such as Eps[Y x]. to be evaluated in target domain n (potentially) different from source domains, where typically Y is an outcome variable, X is set of covariates, and Y X = V.
For concreteness, consider medical study where patient data was collected under different treatment protocols in attempt to assess, in target hospital x* the prognosis of neurodegenerative diseases such as Alzheimer's 's in patients with a number of existing conditions. In the causal graph in Fig. la, X1 and X2 are treatments for hypertension and clinical depression, respectively, both known to be causes of neurodegennerative diseases Y. In the case of hypertension, the effect is mediated by blood pressure W. whose effect on neurodegenerative diseases is confounded, since both conditions share important confounding factors such as physical activity levels and diet patterns (Skoog & Gustafson, 2006) (graphically encoded through the bidirected arrows). Hypertension and clinical depression are not known to affect each other (no direct link between them), although it's common for patients with clinical depression to simultaneously be risk of hypertension (Meng et al., 2012). In this example, we have access an observational study conducted in hospital x", and to hospital n following different guidelines for the administration of X,, both which however are known to have different high blood pressure W incidence than that in π². These differences are called domain discrepancies (Pearl & Bareinboim, 2011).
Definition (Domain Discrepancy, (Pearl & Bareinboim, 2011)). Let na and n. be domains associ- ated, respectively. with SCMs M and M and causal diagrams G and Gh. We denote by An.b V a set of variables such that, for every V₁ E aa,, there might exist a discrepancy if fv. # f or Pa (U.) # (U,)))
Definition 2 (Selection diagram, (Pearl & Bareinboim, 2011)). 1)). Given domain discrepancies A between two domains nO and Th and a causal graph go = (V, E), let S [Sy : V E Aa.b) be called selection nodes. Then, selection diagram ga.b defined graph (V U. (Sy Sves).
Selection nodes locate the mechanisms where structural discrepancies between the two domains are suspected to take place. The absence of a selection node pointing to a variable represents the assumption that the mechanism responsible for assigning value to that variable is identical in both domains. In the medical example above, Fig. 1b shows a selection diagram comparing domains T and in which the Sw node indicates structural difference in the assignment of W. either
3

---

Under review as a conference paper at ICLR 2023
Sx.
Sx
Sx
5x
Sxa
Sx,
X2
X2
X2
(a) ga.b
(b)
(c) g
(d) gz.2
Figure 2: Graphs used Sec. 2.1.
fwy * Jür and / or (*ww) * pa ("(w), but not in the assignment of other variables, for instance fÿ fy and P* (uy) pa (uy). Fig. Ic and Fig. 1d are selection diagrams that compare domains (x" x²) and (*",x") respectively.
2.1 INVARIANCE LEARNING FOR DOMAIN GENERALIZATION
is apparent that there is a degree of unidentifiability optimal prediction rules in a target domain depending the structural differences between it and the available data. A natural objective for chosen prediction function is to minimize worst-case losses over an uncertainty set of potential target distributions that are compatible with a set of selection diagrams (g 1....,
arg min max Ep [[Y f(X)) McM(g*)
(2)
where M(G*) is the family of SCMs compatible with the causal graph G*. In the literature on domain generalization, selection diagrams (GL*
... are mostly implicit, and common to the underlying causal structure of the target domain,
define predictors agnostic of assumptions
and instead exploit invariances with respect to source domains, see c.g. the proposals of (Arjovsky et al., 2019; Peters al., 2016; Lu et al., 2021: Rojas- Mojas-Carulla et al., 2018; Magliacane et al., 201 8). This section studies the generalization guarantees a common class of invariant predictors in the language of selection diagrams.
Definition 3 (Invariant predictor). Given selection diagrams (G i.j 1,... k), invariant predictor is given by Ep[Y z] where (Y IL S Z) for i.j = 1,.... & and the expectation is taken with respect to any P among souree domain distributions.
Invariant predictors define stable conditional expectations, i.e. Pp: [Y = Ep [Y z).. We
use the notion of domain-inde conain-indeeendent Markov blankets to define optimal invariant predictors.
Definition 4 DDomain-indepentee
Markov blankets). Given set of selection diagrams (g : l...., k), the set of domain indeppnndntt Markov blankets for Y E V is given by the set of Z c V such that (1) (Y 11 Z)gus for i,j 1,...,A , and (2) (W 4 Y Z Z(W)gss for i.j 1 1...... and all W e Z.
Domain-independer Markov blankets are designed to be minimal, in the sense that no proper subset of them satisfies conditions (1) and (2), and informative for predicting Y while defining stable conditional distributions across source domains. In general, such set is not guaranteed to exist. For example, in Fig. 1b there no set (and by implication no invariant predictor) that separates Y from all selection nodes, i.e. condition (1) in Def. 4 is violated for any subset of V. Moreover, contrary to not guaranteed to unique. For example, in Fig. 2a both (X1. X2, X5) and (X X3, X₂} are domain invariant Markov blankets. Which one is most informative to predict Y is undecidable from the graph structure alone, i.c. it depends the exact functional associations between variables.
conventional Markov blanket (Pearl Paz, 1985),
Proposition 1 (Optimal invariant predictor). Given selection diagrams (ghd :i 1,..., k), the optimal invariant predictor is defined as the minimizer of E. [[ - f(Z)) across all = 1, .........
'Oter invariance assumptions have also been made, e.g. (Z 11 g) and (Y Il S X)gr, for problems where only the distribution of some covariates expected change across domains (Muandet et al., 2013). such as (Z IL S g) (Li al., 2018). Problems where magnitude of changes assumed to be bounded.
i.c. p* (y x) Pi(y (y | x) & instead of restricting the d-separation statements involving S have been studied by (Rothenhäusler al., 2021).
4

---

Under review as a conference paper at ICLR 2023
and belongs to the set of invariant predictors for which Z is a Comain-indeeendee Markov blanket for Y V.
Invariant predictors may be desirable due to their stability, although, it is apparent that the extent to which predictors will generalize outside of source domains depends on the structure of M((*) and, in particular, differences in structure with respect to source domains. In general, structural invariances across source domains need not hold outside of source domains. For example, given two source domains x . described by g 1/2 in Fig. 2b, holds that Ep [Y F1, 21]
Ep z1, ø2]
is the invariant predictor, which may not be optimal in a target domain x² if the same invariance doesn't hold. For example, for the selection diagrams G and G. given in Fig. 2c and Fig. 2d
Epi [Y]
[2] px [Y] Ø2]
In fact, the generalization error of the optimal invariant predictor, here denoted Epi [Y] z/ can be written
max McM((*) Eppr [(V - Epi [V] ?])
max MeM(
- Epp [Y] x]) + [par[[(par [Y]
X Ep: [Y] Z])²)
(3)
where the first term on the RHS is the expected conditional variance and in general irreducible, and the second term on the RHS quantifies the difference between the invariant predictor and the optimal prediction rule. This second term may be arbitrarily large for general class of SCMs M(g*) with arbitrary differences with source domains. As a consequence, optimality of invariant predictors as solutions to Eq. (2) is limited in general specific scenarios.
Proposition 2 (Generalization guarantees of optimal invariant predictors). Given set of selection diagrams (g i,j = 1,....,)), let = U,,A A'd be the set of variables in V whose causal mechanisms differ between any two source domains, and let S = (Sv : V E A}. Consider the robust optimization problem Eq. (2). The optimal invariant predictor is solution if selection nodes in all
selection diagrams (g ii= 1....,k) k) are given by S with edges (Sy Visves.
In words, an optimal invariant predictor has lowest generalization error in the sense of Eq. (2) only in the space of target SCMs M(G*) with the same structural invariances observed across source domains. Otherwise, in general better predictors are achievable. This observation includes predictors using causal parents which, similarly, define robust predictors for a target domain if invariance in the association between causal parents and outcomes is assumed. For example, in Fig. 1, Ep [Y pay]] pxp[[ pay], EP=[Y" pay] yh Ep+ [Y] p, and E pay] yt IEps [Y' pay]]and thus predictors based on causal parents may not be robust or optimal, in general. In particular, a prediction function of the form Ep1 [Y pay] is a solution to the robust optimization problem in Eq. (2) if and only if it is the optimal invariant predictor and (g
conditioning set (often understood desirable for domain generalization)
1,....,,, k) is defined as in Prop.
Moreover, independently of whether solutions to a worst-case optimization problem can be found, they say nothing about the range of values optimal prediction functions Eps [Y x] may take in other distributions p* away from the worst-case. In the following section, we attempt to define predictors and ranges of predictors with guarantees to arbitrary sets M(G*).
PARTIAL TRANSPORTABILITY OF STATISTICAL RELATIONS
The uncertainty and inherent under-identing iddtifiidentiiiabiiity of solutions to domain generalization problems motivates define the task of partial transportability. that extends the literature domain generalization by considering bounds on the value of arbitrary queries Ep [Y x in arbitrary target domains n defined by set of selection diagrams (g
1,...,k) k).
Task (Partial Transportability). Derive a tight bound [1. u] over a query of the form Eps [Y x] with knowledge of selection diagrams (G+.3 : = 1.... k), a corresponding collection of data distributions (Pi (v) : d,...,k) k). and set of intervals {1, : VV E U,A*. that define potential constraints on probabilities in the target domain. Algorithmically, this may be written as solution
5

---

Under review as a conference paper at ICLR 2023
the following optimization problem, min / max EpM [Y] x]] such that VV A 1 -V, Pe (uv)) P'(v)),
MEM((**
and AV E U (* pav) E Iv.
(4)
In words, the task is to evaluate the minimum and maximum values over all possible SCMs M compatible with (G : i 1, ....... }} that define the structurally invariant mechanisms in the system and (potentially uninformative, i.e., Tv E [0, 1J assumptions about target-specific probabilities.
For example, given the causal description of the protocols presented in the introductory medical example and Fig. 1, the question might be how to combine these various datasets to predict an individual's risk of developing neurodegenerative diseases in π The optimal prediction function is given by px [Y]
w, 01111 (under mean squared eπтоr losses), which may be written as,
Eps [Y| W. L1, x22] = Σ
y (y,, w. x2)/
Σ (", w, 21,1
(5)
yelly
yelly
where pa (",,, w. 22) is equal to,
11f F2, (wyy = yt 1(f (01, uw)
w) w 1 X2 (Mz, = x1, 122
d dP*
(6)
Du
matches RCT**
specific to n
matches hospital x
This mixture of terms for which data from source domains can be leveraged, for example J& (w, 22, uhyy) J [ #2, Mary) (superscripts denote domain), but also involves unobserved confounders Mwy and 2yiwa that cannot be marginalized out, and terms that are specific to n** In addition, although p* (w | 21) is known to differ in our target medical study it may be the case that we have some domain knowledge that constrains it, c.g. P (w (w x1) E [0.2, 0.7] =: Lw left undetermined, In [o, 1),, and can be used further inform target query.
The following proposition show that the solution of the partial transportability task defines an interval that contains the invariant predictor and, by definition, also the optimal "worst-case" predictor across ((*).
Proposition 3. For given set of selection diagrams, let [[x),, u(x)] denote the solution of the partial transportability task for the query E Epm [Y |x], M E M(G*) and Epr(Y 22) Z S X be
the invariant predictor. Then, Epp [Y 2] e [[x), (x)] Moreover, by definition Epm (Y x]
[[(x), u(x)] for a particular "worst-case" member M E (M(").
In general, there is no reason believe that the invariant predictor has any special performance
guarantee among other solutions in [[(x), ((x))x(()) [x)]. For example, the worst-case loss in Eq. (3) is not, in
general, smallest when E [Y] x] * Ep [Y z]. An alternative
exploit the solutions to the
partial transportability task to define the median of [((x), u(x)] as a general predictor for domain generalization problems.
Proposition 4. For given set of selection diagrams and data, let [1xx), ul u(x)] denote the solution of the partial transportability task for the query Eppre [Y x], M E M(G*). Then,
max Epae[( - med Eps [Y [ McM(G*)
McM(g*)
I x1) (Bpar[(u(X) -(x)))((())))
[(Y - EpM (Y [P--
max McM(S*)
4
Epw [Y | x])2] is constant across M E M(g*), Epd Eps [Y] X] provably solves the robust optimization problem Eq. (2).
Under the condition that the irreducible error Epp [[Y
This proposition says that the error of the median is, at most, off from the optimal predictor by "half the range of possible values of pax [Y x] compatible with the data and assumptions" and that this error is optimal in the worst case (under some assumptions on how the expected conditional variance is allowed to vary). This result is important because it applies to any set of target causal graph, source domains, and selection diagrams. Note, however, that this does not mean that the median is always superior to the optimal invariant predictor: in selected settings where the expected conditional variance changes across domains we may still have the optimal invariant predictor being better worst-case solution.

---

Under review as a conference paper at ICLR 2023
4 ALGORITHMS FOR PARTIAL TRANSPORTABILITY
This section presents algorithms to solve the partial transportabilityy task for SCMs with discrete observables, that is each V V taking values in finite space of outcomes, while each U U associated with an arbitrary probability density function P(u).
A first step in our argument will be to decompose chosen query into smaller factors to infer which factors can be matched across domains and point-identified from data, and subsequently re- ee-aaramterrize unmatched factors by special family of SCMs make the bounding problem tractable. We use the concept of c-components and C--fctors developed by Tian & Pearl (2002). The set V can be partitioned into c-components such that two variables are assigned the same set Cc V if and only if they are connected by bi-directed path in G. In addition let Uc = Uviec U; denote the set of exogeneous variables that are parents of any V C. For example, the graph in Fig. la induces c-components {2) and (W,Y)
For any set C = le Q'(CI(pa(C) C)) denote the C-factor of C in domain xO which defined by,
Q'[C](pae)
II
()d))
Duc VeC
Moreover, let C denote the collection of c-components, then P(v) = Icc Q[C] and Q[C] = P(c pac) (we omit the dependence of each C-factor on pa( (C) for readability). This construction is useful because the joint distribution may be factorized according to the e-components of g and its factors matched across domains (Tian & Pearl, 2002; Correa& & Bareinboim, 2019).
Lemma 1. Let ga.b be selection diagram for the SCMs M and M then ["[C]= Q2[C] irgab does not contain selection nodes Sv pointing to any variable in V C.
[2] Y] where by Lem. 1 [*[X, X2] = [,, X2] = (x111, x2), since the is no S-node pointing to X1 or X2. In turn, Y" * Q"(W,]] because of the selection node pointing to W. Note, however, that [W, Y] defined as in Eq. (7) involves terms, e.g. 1 ( (w, I1, Mwyy) = y). that are invariant across domains since the absence of an S-node into Y denotes invariance in causal mechanisms, and for which po (v) may be used for estimation. We discuss next a re-parameterization of C-factors [*[C) that cannot be matched across domains with the goal of defining a tractable constrained optimization problem to bound [*[C].
For example, for the selection diagram in Fig. lb, (*(v)=
Proposition 5. Let M be an arbitrary SCM with graph G and let C be any c-component. Then, there exists a corresponding SCM N with finite exogeneous domain compatible with G such that QM [C] = QN [C), where for every exogenous vuriable U Uc, its cardinality du [P(()))
This proposition shows that SCMs with discretely- valued exogeneous variables are expressive enough to represent C-factors Q[C] irrespective of the true underlying data generating mechanism. From an optimization perspective, this is useful because it allows us to consistently parameterize C-factors and make inference on its distribution in a well-defined latent variable model (Rosset et al., 2017; Zhang et al., 2021). As example, consider the introductory example with {X1, Y, W) binary and causal graphs in Fig. 1. Q* Y defined using Eq. (7) can also be written as:
Σ Manr Myy Mboc
11f
(ff (w, X2, uwy, Un) = y) 1ff (x1, uwy, uw) = w P ) (uw):
(8)
where |20m.y Do 1 12x,
[ayl |0yl = 16; the function fy is a mapping between finite domains Spay x Suu - 2y for V E [ Y). Moreover, we have used the structural invariances encoded by the selection diagrams in Fig. 1 to match causal mechanisms and exogeneous probabilities between domains. In particular, pd(u,) = (u,,) p*(u,, by definition of the selection diagrams ga.* and gb Although discretely-valued causal mechanisms and exogeneous probabilities imply well-defined parameters to optimize over, the partial transportability task remains difficult constrained optimization problem.
[2x 1
4.1 APPROXIMATIONS VIA GIBBS SAMPLING
We follow (Chickering & Pearl, 1996; Zhang et al., 2021; Bellot et al., 2022) and take a Bayesian perspective to approximating bounds [[xx),(x)) We evaluating credible intervals P(I(x)
7

---

Under review as a conference paper at ICLR 2023
Eps x] < u(x) v) [[] < Ep [Y
the posterior of Ep [Y x by approximating the expectation.
x]
<
u
[ v] = P(((x) < pp [Y] x] < u(x) v)
(9)
provided with finite samples
1, ..... n are n independent sampled collected in domain nO and set of selection diagrams {g* i 1, 2, ........ k)
(V..,..., vx+), where /.
{v ()) x
using Gibbs sampling. Following the arguments in the previous section the query may be reduced to bounding a C-factor of the form,
Wobj = Q*[C]= = Σ Σ
II UsUC u= VEC
( pav (pav,uy) uv) = v} II
1
O..
(10)
U'Uc
that are parameterized by & 15v (g(pav, V CaPav V. C Uc} and 0 18w U e Uc} that represent causal functional assignments and exogeneous probabilities, respectively. We have dropped the domain indicator from the definition of parameters for readability.
For every V E V, Vpay, uy, the functional assignment parameters < ((pay,vv) are drawn uniformly in the discrete domain Sty. For every U U, exogenous probabilities Oy with dimension dy [Ppa(C)] are drawn from a prior Dirichlet distribution,
Ou = (01,.... 0gg) Dirichlet (01,...,,ad
(II)
with hyperparameters ai..... Odgy The Gibbs sampler starts with some initial value for all latent quantities (u, &. 0) in the expression of Wobj. and iterates over the following sampling steps, each parameter conditioned the current values of the remaining terms in the parameter vector.
1. Sample Let u Ly U Uc. For each observed data example across all domains v(v) v, n = =11,... 1,..., ES ns. we sample corresponding exogeneous variables e Uc from the conditional distribution,
((u(*) (m)) E) o ((u(") (n) (,)
II Vec
1
(pa (e) ,u .ali))
v(m)
II O.. UeUc
(12)
2. Sample &. Parameters & define deterministic causal mechanisms. For given parameter <V <(pay,ay, uv) & its conditional distribution is given by P(c(pay,ar)
v, û) 1 if there
exists a sample (y("), pay step and associated with the subset of domains in which exogeneous probabilities match the
(n) ()) for some n, where iterates over the samples of u from
target domain, such that EV uniform discrete distribution over its domain Ωty
(pall") (n) (ppal""
v(*), Otherwise, P(g) P(c(pav.wy) = v v, û) is given by a
3. Sample O. Let OF (01,...,0au possible values of variables U Uc. Its conditional distribution given by,
0 be the parameters that define the probability vector of
0 01....,aa; Vva Dirichlet
a1
L =u1) w.)..... adu + Σ El(
udd
(13)
where, similarly, n iterates over the samples u from step associated with the subset of domains in which exogeneous probabilities match the target domain.
In the above, we have described the conditional distributions of parameters that can be matched across domains, and therefore estimated from the subset of relevant available data. By the definition of the partial transportability task, parameters that are specific to the target domain n are constrained to lie in assumed interval, e.g. P*(E E pay) Σny 1 (igp uv) (2 I Ilvetv 0a E Iv S [o, 1], or else left unspecified. In the first case, parameters are sampled independently and uniformly in the space defined by the constraints and in the second case, they are sampled independently and uniformly in their domain of definition, i.e. < s(pav.uv) e Qv, E Ly. in every step of the sampler.
Iterating this procedure forms Markov chain with the invariant distribution to be the target posterior distribution P(u. E. v). P(wary v) is then approximated by plugging the MCMC samples into Eq. (10). The upper and lower quantile among T samples of P(wary v), when combined with the
8

---

Under review as a conference paper at ICLR 2023
Sw
Sw
57 FR
Ss
Ss
.1502 (.005)
Epux [c]o, w.
.148 (.004)
med uo)
.1361 (.005)
(a) O
(b) FRRSS
(c) GSWUK
(d) Performance comparisons.
Figure 3: (a-c) selection diagrams that compare domain FK with n n with Rw and ww with UX respectively. (d) gives mean squared error for cancer prediction on sample of data from peR.
identified C-factors that form Ep* [y/ x]. gives us a (1- a.) credible interval la < Epo x] da defined by.
(x) sup(2: Σ
[1Epp11 [Y
x] (1) & < = a/2],
(14)
(x(x)) = inf(x: 1Ep (4) & = =1-=1-a22
(15)
The following Theorem shows that credible intervals [((()), (x)] converge to the true bounds [((x), u(x)] for the unknown query [p=[Y [Y] x] and are, moreover, maximally informative, in the sense that that are compatible with our current knowledge of the world such that E E [Y x = 1 and
always construct two data generating mechanisms M' .2 for the target domain
Ep ly x]
Theorem 1. The solution [(xx), u(x)] the partial transportability task defined over discrete SCMs tight bound over target query Epp [Y x]. The credible interval [fo(x), (x(x)] coincides with [1(x), u(x)] as ny - op in all observable domains π², i. 1, 1,...,k. ki
5
EXPERIMENTS
5.1 SMOKING AND LUNG CANCER
Our first experiment is inspired by the debate around the relationship between smoking and lung cancer in the 1950's (US Department of Health and Human Services, 2014). We use a scientifically- grounded variation of the front-door graph that includes an individual's smoking status S, presence of tar in the lungs T, wealth W, and lung cancer status C, using the fact that smoking and lung cancer may be confounded by an individual's unobserved genetic profile. In this example, the objective is to make inference
cancer probability distributions in the French population HR from corresponding data in π _K where the prevalence of smoking is known to be lower. The selection diagram is given in Fig. 3a and details on the SCMs used generate data are given in Appendix B.
Probability of cancer among smokers (CR (C== 1 = 1) The C'-fctor decomposition and parameterization is given by the following derivations,
(c, Σr, PFR (c,
Σn Q QQRR [w]
(CR (FR((,, Ee,t,o PFR (,, w. Ln QHR & cQQHR [
(16)
where Q'"(E]] = QUK[t]] = puk(t) 8, w) and [ = [UK[w] = puk (w), and,
QUR[s,c]= Σ
1
1(elwit tusc
c) (
(w, (ee)))))
s)OuK gFR uye
In Fig. 4, we report estimated 100% credible intervals to < (C = 1| S= < ûg as function of the number of samples without prior information (purple) and with the prior information that PfR w) lies in interval of width 0.1 around its true value (pink). The black and gray dotted lines are the actual values
0.45
06
0.40
0.5
2000
4000
5000
8000
20000
0
200
43D
4C0
RED
1000
Number samples
MCMC iterations
Figure 4: Bounding the probability of cancer.

---

Under review as a conference paper at ICLR 2023
P 1) and ( 1) respectively. Notice that a relatively small number of samples is required to converge stable bounds, and that the prior information narrows the credible interval reflecting this additional constraint. We also show for illustration that our Gibbs sampler recovers the true values PPR(C 1 = 1) (pink) and (FR
S 0) (purple)
when trained on data from π i.c. when probabilities are identified.
Prediction performance across domains. Consider the task of designing cancer prediction rules for optimal performance in the french population , We introduce an additional training domain to be able to define invariant predictors: data from the Swedish population 55 whose structural Tuk
differences with π. UKK and with π are given in Fig. 3. Across I/ and x55 the optimal invariant predictor (Def. 3) is given by I2 pux [C] l, w. 8] = Epsw [C L, w. s] which, however, is not equal to pm [C f. w, s] as no set blocks the open path between the selection node Sş and the cancer variable C' in GFR.UK We consider also the common strategy of using causal parents for prediction, i.e. using the prediction rule px [C| w] (which, similarly, is not equal to Epr [C] t, wl). For comparison, we consider the median value med ún) for the optimal prediction rule E. [C] w,W,, s] computed using data from π and x55_ We observe in Fig. 3d that indeed the prediction rule E [C] f, w, s] underperforms in पF. for reference E [C é, w, s] has a mean error of .1220, cautioning against naively transporting invariant prediction rules across domains. Similarly, using causal parents for prediction underperforms. In contrast, the median of the derived bound proves to be a slightly better predictor in this case and has guarantee of optimal performance in the "worst-case" domain compatible with the selection diagrams (Prop. 4).
5.2 PREDICTION OF NECRODEGENERATIVE DISEASES ACROSS HOSPITALS
Our second experiment reconsiders the introductory example that described the design of prediction rules for the development of neurodegenerative diseases in a target hospital x² in which no data has been recorded. Instead, we have access to data from two related studies conducted in hospitals n² and N² that, however, are known to differ with respect to the target domain notably in the distribution of blood pressure W, known cause of neurodegenerative diseases. The causal protocol is given in Fig. 1 and is described in more depth in Sec. 2. Details on the SCMs used to generate data are given in Appendix B.
Given this information, we consider the task of designing a prediction rule for optimal mean squared error in the target hospital x². Here, invariant predictors are well defined and given by the function .I, x22) = Ep [Y w2 x1222 = Ep [Y w, x22] although note that, in this example, f(w,z1,2
this conditional expectation not invariant in the target domain due to the difference in the causal mechanisms associated with blood pressure W, see Fig. 1d. Similarly, we can define causal predictors as p= [Y] w,, x2] and E.p x2, which in this case are not equal across hospitals nO and n due to the open path between Sx, and Y once we condition on W. The partial transportabilityy task instead argues for approximating Ep [Y W. 21, x1, which, using the C'factor dccomposition, is X2] pa (21, x22) by
parameterized by pd (y, 21, x2) [*[X, X2|Q*IW [W where [*[XX,
Lem. 1 and
Q= Σ
11 (w.
y) (
(
w0on 0
Chary Ma
The median value of the resulting interval that encodes the un- certainty in the computation of Ep* [Y] w. Z1, x22] as well as all baseline predictors are given in Fig. We add the actual optimal (not computable) prediction rule Ep+ w, 21; 22]] for reference. Fig. shows that the median outperforms and that baselines, although common strategies for prediction, can result in significantly worse out-of distriibbttitnioon perfor- mance in examples where unobserved confounding as well as structural differences between domains play a role.
x
Ep. Ep-[w/ur,11 01,
.3640 (.003)
Ep. [2]
.4244 (.002)
Ep [u]
.4013 (.002)
med(/o, uo)
.2961 (.008)
Eps [y] (0, 21,
.2434 (.002)
Figure 5: Performance comparisons.
6 CONCLUSIONS
This paper investigated the problem of domain generalization from the perspective of transportability theory. We introduced the task of partial transportability that seeks to bound the value of an arbitrary
10

---

Under review as a conference paper at ICLR 2023
conditional expectation Eps [Y x] in unseen domain x² using selection diagrams and data from source domains. Using this formalism, we showed that invariant predictors and more general solutions robust optimization problems derived in the literature this task. Moreover, in systems of discrete observables, we showed that we can design provably consistent algorithms for inferring bounds that are sound and tight, and illustrated its performance synthetic data.
special cases of solutions to
REFERENCES
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint 1XX.:1997.00293 2019.
Alexander Balke and Judea Pearl. Bounds treatment effects from studies with imperfect compliance. Journal of the American Statistical Association, 92(439):1 171-1176, 1997.
Elias Bareinboim and Judea Pearl. Transportability from multiple environments with limited experi- ments: Completeness results. Advances in neural information processing systems, 27, 2014.
Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 113(27):7355-7352, 2016.
Elias Bareinhoim, Sanghack Lee, Vasant Honavar, and Judea Pearl. Transportability from multiple environments with limited experiments. Advances in Neural Information Processing Systems, 26, 2013.
Alexis Bellot and Mihaela van der Schaar. Accounting for unobserved confounding in domain generalization. arXiv preprint arXiv:2007.10553, 2020.
Alexis Bellot, Junzhe Zhang, and Elias Bareinboim. Scores for learning discrete causal graphs with unobserved confounders. Technical Report R-83, Causal Al Lab, Columbia University, 2022.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization, volume 28.
Princeton university press, 2009.
Constantin Carathéodory. Über den variabilitätsberecch der fourier'schen konstanten von positiven harmonischen funktionen. Rendiconti Del Circolo Matematico di Palermo (1884-1940), 32(1): 193-217, 1911.
David M Chickering and Judea Pearl. A clinician's tool for analyzing nom-oompee In Proceedings of the National Conference on Artificial Intelligence, pp. 1269-1276, 1996.
Juan Correa and Elias Bareinboim. General transportability of soft interventions: Completeness results. Advances Neural Information Processing Systems, 33:10902-10912. 2020.
Juan Correa and Elias Bareinboim. From statistical transportability estimating the effect of stochastic interventions. In IJCAI, pp. 1661-1667, 2019.
Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. arXiv preprint arXiv:2007.01434, 2020.
Sanghack Lee, Juan D Correa, and Elias Bareinboim. Generalized transportability: Synthesis of experiments from heterogeneous domains. In Proceedings of the 34th AAAI Conference Artificial Intelligence, 2020.
Ya Li, Mingming Gong, Xinmei Tian, Tongliang Liu, and Dacheng Tao. Domain generalization via conditional invariant representations. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Chaochao Lu, Yuhuai Wu, Jose Miguel Hernández-Lobate and Bernhard Schölkopf. Nonlincar invariant risk minimization: causal approach. arXiv preprint a0Xiv:2 12355, 2021.
Sara Magliacane, Thijs Van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij. Domain adaptation by using causal inference to predict invariant conditional distributions. Advances in neural information processing systems, 31, 2018.
11

---

Under review as a conference paper at ICLR 2023
Lin Meng, Dongmei Chen, Yang Yang, Yang Zheng, and Rutai Hui. Depression increases the risk of hypertension incidence: meta--nnalyis prospective cohort studies. Journal of hypertension, 30 (5):842-855 851, 2012.
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International Conference on Machine Learning, pp. 10-18. PMLR, 2013.
J Pearl and Paz. Graphoids: A graph- based logic for reasoning about relevance relations technical report 850038 (r-53-l), Cognitive Systems Laboratory, University of California, Los Angeles, 1985.
Judea Pearl. Causality. Cambridge university press, 2009.
Judea Pearl and Elias Bareinboim. Transportability of causal and statistical relations: A formal approach. In Twenty-fifth AAAI conference on artificial intelligence, 2011.
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant
prediction: identification and confidence intervals. Journal of the Royal Statisticul Society: Series B (Statistical Methodology), 7845)994-11112 2016.
Mateo Rojas-Carulle Bernhard Schölkopf, Richard Tumnrr and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, (11):1309--3422 2018.
Denis Rosset, Nicolas Gisin, and Elie Wolfe. Universal bound on the cardinality of local hidden variables in networks. arXiv preprint arXiv:1709.0070) 2017.
Dominík Rothenhäusler, Nicolai Meinshausen, Peter Bühlmann, and Jonas Peters. Anchor regression: Heterogeneous data meet causality. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 83(2):215-246, 2021.
Herman Rubin and Oscar Wesler. A note on convexity in euclidean n-space. In Proc. Amer. Math. Soc, volume 9, pp. 522-523, 1958.
Ingmar Skoog and Deborah Gustafson. Update hypertension and alzheimer's disease. Neurological research, 28(6):605-66) 611, 2006.
Adarsh Subbaswamy and Suchi Saria. From development to deployment: dataset shift, causality, and shift-stable models in health ai. Biostatistics, (1:3)3345-352, 2020.
Adarsh Subbaswamy, Peter Schulam, and Suchi Saria. Preventing failures due to dataset shift: Learning predictive models that transport. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 5118-3127. PMLR, 2019.
Jin Tian and Judea Pearl. A general identification condition for causal effects. eScholarship, University of California, 2002.
US Department of Health and Human Services. The health consequences of smoking- years of progress: report of the surgeon general, 2014.
Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yigiang Chen, Wenjun Zeng. and Philip Yu. Generalizing to unseen domains: A survey on domain generalization. JEEE Transactions Knowledge and Data Engineering, 2022.
Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data, arXiv preprint arXiv:2110.05690, 2021.
12

---

Under review as a conference paper at ICLR 2023
A PROOFS
Proposition (Prop. 1 restated). Given selection diagrams (g : ; = = 1.....kk, k), the optimal invariant predictor defined as the minimizer of E - ][ across all i 1...., k. and belongs to the set of invariant predictors for which Z is a domain-independen Markov blanket for Y V.
Proof. Assume not such that there exists optimal invariant predictor Ep:[Y - I,..,,k K, distinct from any invariant predictor defined conditional on nomain-independent Markov blanket, with Z not independent Markov blanket, either (Y 4. S g for i. 1...., k; in which case Ep. [Y Z] not invariant across source domains, there exists W Z such that (W IL Y Z g for j = I.....k. in which case Ep-[Y Z = Ep- [Y Z Z.W]. Now if Z W is not domain- independent Markov blanket we can continue removing independent variables from Z W to reach domain-indepent independent Markov blanket concluding that Ex [Y Z] is not distinct from an invariant predictor defined conditional on a domain domain-indepenn independent Markov blanket.
Markov blanket for Y V. Then, by definition of domain-
Proposition (Prop. restated). Given a set of selection diagrams ;.. let A Un, A be the of variables in V whose causal mechanisms differ between any two source domains, and let S {Sv : V A}. The optimal invariant predictor solves the robust optimization problem in Eq. (2) if selection nodes in all selection diagrams i * ii= ===1...... I,...,k) k} are given by S with edges {Sv V) Syvs.
Proof. Given set of selection diagrams (g i.j = I,..., k), let A U., A be the set of variables in V whose causal mechanisms differ between any two source domains, and let S (Sv V E A).
Assume that selection nodes in all selection diagrams (gi.* : 1,..., k) are given by S (and with edges (Sy - ssss). . In that case, the optimal invariant predictor, written Ept [Y Z] = EpM [Y] Z] for any M MMg). Any additional variable W in the conditioning set is either irrelevant for prediction, i.c. p [Y] Z] = Ex [Y Z, WJ. or breaks the independence between Y and selection nodes, which implies that Epa [Y] Z, W] varies as a function of M. Since the the functional form of M (besides the arguments of functions) are not constrained by selection diagrams, for any fixed prediction function Ep [Y] Z. W1, we can always find a domain M' e MM()) that makes the error Epwr((Y - pM [Y Z, W])*] arbitrarily large, and thus higher than Ex [(Y EpM [Y = which is fixed for any M'.
Proposition (Prop. restated). For a given set of selection diagrams, let [((x), u(x)] denote the solution of the partial transportability task for the query Epu [Y x], M _M(g)) and Epi z], Z = X be the imvariant predictor. Then, Ep [Y z] e [1(x), u(x)]. Moreover, by
definition Epu] [Y] |x] E [[xx), ((x)]foor particular "worst-case" member M E MMG*).
Proof. The set M(G*) represents all SCMs compatible with target causal graph Go that is only constrained by selection diagrams {G*** = ...... k). A selection node indicates a potential change between two domains and therefore, in principle all source domain SCMs [M' i 1,.... k) are possible candidates for the target domain and thus M M(G*) 1,..., k. Then, by the definition of the partial transportability task, Ep [Y] z] [1(x), u(x)] where z is the value of Z in X.
Proposition 9 (Prop. 4 restated). For a given set of selection diagrams and data, let [[xx), u(x)] denote the solution of the partial transportabillty task for the query Eps [Y x). e M( Then,
max MeM(G*)
EpM[(Y- med E EpM [Y] x
McM(g*)
1 Epai((Y EPM [Y] x)) + 1 BPM ((x)))
max MEM(G*)
Under the condition that the irreducible error Ep [(Y Epss(Y | x is constant across M M(G*), Epd X] provably solves the robust optimization problem Eq. (2).
13

---

Under review as a conference paper at ICLR 2023
Proof. For given set of selection diagrams and data, let [M(x), u(x)] denote the solution of the partial transportability task for the query Epxr [Y x], e M(g*). Then,
max Epw [(Y MEM(g*)
med Epa/ [Y] x
McM((*)
Bpw[ (Y Epar [Y| X] + Epar [Y
med Epm [Y xx] MEM(g.)
X
MEM((*)
EpM - Bpu(y XJ)* Epar [(pM [Y X]
med MeM(s*)
EpM (Y xI)*
MeM((*)
max MEM(g*)
[Epa[(( Epxr [Y
x]) (((X)) -((x)) 1(x))))
The second equality holds because the cross term in the expansion of the square equal 0 as Epar [(Y par [Y X]]] = O. The incquality holds because the largest distance between Epxr [Y X] and the
median of values E [Y] X] can reach as function of M E .M(g*) is half the distance between maximum and minimum values of Ex [Y] X] across M e M(G*), that is (u(X) - 1(X))/2.
-UY-Epa E YY| X))² equal constant value independent of M, it can be taken out of the maximization and we are left with the optimization problem,
E -
arg min
max MEM(C*)
EpM [[Epx Y X - f(X))²
(17)
f
For any æ and any f. we can always choose M such that [EpM][ x-- xx)]((xl > [E [Y x] med Epar] [Y x]|. For example, by choosing M such that EpM [Y x]
MeM(g*)
max MeMiss) Epx [Y x] or Epu x]
min Ep x] depending on what
distance is larger. Therefore, f(x)= = med Epa [Y x] minimizes the robust optimization
MEM(c*)
problem.
Theorem 2 (Prop. 5 restated). Let M be an arbitrary SCM with graph G and let C be any component. Then, there exists a corresponding SCM N with finite finte exogeneous domain compatible with G such that Qar[C] QN|C], where for every exogenous variable U e Uc. its cardinality dy = [Ppacs)
Proof. The proof follows from Rosset et al. (2017) and Zhang et al. (2021). We include it below for completeness.
We first introduce some necessary notations and concepts. The probability distribution for every exogenous variables U U is characterized with a probability space. It frequently designated Fu, where Oy is sample space containing all possible outcomes; Fu is a ralleebra containing subsets of P2y; Pt probability measure on Fu normalized such that Po- Elements of Fü are called events, which are closed under operations of set complement and unions of countably many sets. By means of Pt a real number (A) E [o, 1] is assigned to every event A E Fo; it is called the probability of event A. For arbitrary set of exogenous variables U, its realization inferring whether sequence of events A for every U U occurs. Such event represented by subset X Ueu Au S X Ueu Py which in turn generate product of r-algebras & Fu. Define the product measure & Py to satisfy the following mutual independence condition given by the definition of the SCM,
u an element in the Cartesian product X Ueu Gy. We may be interested in
P
X Av
πl Po(Ag).
(18)
UEU
UeU
Such P is probability measure. Moreover,
X
Su.
Fu,
X Pe
(19)
(eUU
UeU
UeU
14

---

Under review as a conference paper at ICLR 2023
defines product of probability spaces (No, Po) that describes measurable events over all exogeneous variables U partitioned into c-components.
Let C be the collection of all c-components in G. c-components in C form partition {Uveg Uv C E C} over exogenous variables U. Therefore, for every U E U. there must exist a unique e- component denoted by Cy containing U. For any c-component C C, let Uc Uvec Uv the set of exogenous variables affecting (at least one of) endogenous variables in C. By the definition of c-components, the exogeneous variables do not overlap between e-components and it holds that,
P
P
p( UEU
n
)o)=
Au
II PU
(n Au )u)
(20)
CEC(C)
1UEC
For any SCM M compatible with the causal graph 9 the joint distribution may be factorized into e-components,
P(v) II QIC)(c,
(21)
Cet
where Q[C] a C-factor and is function of (c, pac).
To parameterize this joint distribution it is thus sufficient to look at each C-factor separately. Let C be a generic c-component in G. Denote by m |Ucl the number of exogeneous variables related to C. For convenience, consistently write (S; Fi, P.) as the probability space of i-th exogeneous variable C. The product of these probability spaces is thus written,
m
m
X
Ω
P
(22)
Each C-factor may thus be written,
QCC - X 94 Vec
II 1(v (pav, uv) = vld X P.
(23)
Our goal is show that all probabilities Q[C). induced by exogenous variables described by arbitrary probability spaces could be produced by a "simpler" generative process with discrete exogenous domains. Q[C] defines mapping between the space of possible realizations of the variables Pa C) to the [o, 1] interval. Since Pa(C) are discrete variables with finite domains, the cardinality of the class of probability assignments that must be defined is also finite. It is given at most by the number of possible combinations of realizations of Pa(C) which is given by lIVEP(C)) [Ωvl.
Let P be vector representing probabilities QLCJ(c, pac). Counting all possible combina- tions of outcomes for all possible conditioning sets, P is therefore a vector of at most size [V [[2]. And since Q[C[(c. pac) is a probability mass function, it only takes vector with d 1 dimensions to uniquely determine it. P may thus be interpreted as a point in the (d didmeensso real space. Similarly, (P, 1) is vector in d-dimensional space where the d-th element is equal to 1.
Now consider sampling a value Ui My from the underlying SCM and let Qu, be the probability model with U,
[
m
Qu [C](c) pac)
II 11f uv) a)d VEC
P.
(24)
X
1=2
U.=u:
and Pu, is a (d -idmenssion probability vector representing the probabilities of each one of the combinations (C given that U, u1. We will show that P1 may equally well be represented by a discrete distribution. For this, let (Pu, : u1 E 22} c Idd be the of probability points that can be constructed as U1 varies in Ω2. The average Sa, Pu, dPi is convex mixture of points in 2/ by (Rubin & Wesler, 1958) that equals Q since.
m
P =
II 1(fv(pay, uv) o
P {=2
dP..
(25)
X Di VEC
U1
15

---

Under review as a conference paper at ICLR 2023
By construction, P itself is convex mixture of at most d + 1 points in 4. That is, by using Carathéodory's theorem (Carathéodory, 1911),
d+1 P
wk P
(26)
Replacing the definition of P Par, we obtain,
wk J
P
II
1lʃv (pay, = x
(27)
x Or VeC
This means that we can replace the continuous measure P1 with a discrete probability set with outcomes (u1.1...., (1.d) and corresponding probabilities [wr,..... wa) with cardinality d and obtain a probability model that equivalent the original P. This procedure can be repeated for all m exogeneous variables in the c-component C. We are thus left with model.
QlC](c,pac = =S
II
[[v(pav, uv) = old x Pi
(28)
x Th O VEC
equivalent to its discrete counterpart,
Q[C](c,pac)
= Σ Σ
Σ weUe u......,ddV VEC
II [I v} 11 P(u),
(29)
where d = II [Ivera(C) [Qyl-
Theorem 3 (Thm, restated). The solution [7, u] to the partial transportability task defined over discrete SCMs is a tight bound over a target query Ep [ x]. The credible interval [lo ūol coincides with [L, u] n4 - ap in all observable domains x i = L,...,k. k.
Proof. The proof strategy follows (Zhang et al., 2021) and shows convergence of the posterior by way of convergence of the likelihood the data given one SCM M e M()). We look at "convergence" in frequentist way, for increasing sample size the posterior will, with increasing probability, be low for any parameter configuration, i.e. for any SCM M M(G).
By the definition of the optimal bounds [t, u] given by the solution to the partial transportability task,
P(v < Ep, [y x] < u) > 1.
(30)
Therefore if the prior on parameters (g, 0) defining SCMs non-zero for any M M(g), also the posterior converges,
P(I Ep Ly x]
v) + 1,
(31)
which is the definition credible intervals [/,, 4n] as the 9th and 100 quantiles of the posterior distribution which coincide with [1, u] asymptotically.
B EXPERIMENTAL DETAILS
All experiments 1000 burn-in MCMC samples that discarded and 5000 MCMC samples considered as independent samples from the posterior distribution and used for the approximation of target queries.
16

---

Under review as a conference paper at ICLR 2023
B.1 SCMS FOR THE SMOKING AND LUNG CANCER EXAMPLE
Using the functional dependencies specified by the selection diagram in Fig. 4, we define the SCMs for domains UU R and S- follows.
For UK we generate samples from P(uw), P(us), P(ue) and P(use) given by independent Gaus- sian distributions with mean and variance 1. Each generated (Wwr Ug Ue, Usc) leads sample
(w, 8, E, c) as follows: w - 1 uu > 0}, - 1 + use + - 2 > 0}, - 1{s 0.5u, 0} ltt 0.5w Usc
0}.
For 7 we generate samples from P(uw), P(u,), P(u) and P(use) given by independent Gaus-
sian distributions with mean and variance 1. Each generated (ww Ug Ue Use) leads sample (w, 8, tt c) as follows: w - u > 0}, + 1(w + Use + 1.5u, - > 0}, + 1 0.5u, >> 0) <- 1f 0.5t + Use > 0}. Notice that the causal mechanism for S has changed while everything else is unchanged.
For 555 we generate samples from P(uw), P(ug), P(we) and P(usc) given by independent Gaus- sian distributions with mean 0 and variance 1. Each generated (uw: Mgy Me, Uso) leads to sample (w, 8, c) as follows: w [u > 0.5]; 8 1(w + Use + Ug 2 0}, 1(s 0.5u,
0) 1 0.5w + Usc > 0}.
B.2 SCMs FOR THE NEURODEGENERATTIN DISEASE PREDICTION EXAMPLE
Using the functional dependencies specified by the selection diagrams in Fig. 1, we define the SCMs for domains x* प., and nO as follows.
For the target domain π we generate samples from P(uwy), P(ugz P(uy) and P(un) given by independent Gaussian distributions with mean and variance 1. Each generated (Uayy M21, Mry Uy,) leads to a sample (œ1, 22, w, y) as follows: œ1 - 1(ug, > 0). 22
(ur,, + U22 > 0}, w ( + "wyy" 1.5u
0}.y 1( thy + 0.1x; 1 0}.
For source domain n", the distribution of exogenous as well as structural assignment agree with n² except in the assignment of W which given by [xr + dwy tw > 0}.
For source domain Th the distribution of exogenous as well as structural assignment agree with n* except in the assignment of W and X₁. The selection diagram specifies that the assignment of W agrees with x" and is thus given by w 1 {2: + "uyy uh + 0} while the assignment of X1 changes and is given by 2 1 (u,, - 0.5 > 0}. All other components of the SCM are the same.
17


Reviews:
[{"review_id": "XXG7YjJZqq", "reviewer": "Reviewer_D5NR", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "The paper presents the analysis of characterizing invariance learning with lowest worst-case loss as a special case of partial transportability tasks. The paper introduces the notion of \"selection diagram\" and considers domain generalization problems from the perspective of transportability analysis. Theoretical analysis on the bounds and some empirical analysis on the discrete variable case are also presented.", "summary_of_the_review": "Overall, the paper makes an effort on connecting certain domain generalization problems to transportability analysis. Considering the lack of clarity in definition and configuration, there are worries about the correctness and the significance of the contribution (as detailed in \"Strength and Weakness\").", "strength_and_weaknesses": "## Strength\n\nThe strength of the paper originates from the effort of trying to analyze a specific type of domain generalization problem via transportability modeling. I believe the utilization of the appropriate causal modeling (if feasible) is of crucial importance when pursuing principled analysis towards domain generalization, and the paper makes an effort along this direction.\n\n## Weakness\n\nThe weakness of the paper results from the lack of clarity of the definition and configuration, as well as the worry about the overall significance of the results.\n\n### 1. w.r.t. Definition 2: Selection diagram\n\nSelection diagram is the core definition with respect to which major theoretical results in the paper are presented. While I agree with authors that we need some structural assumptions on domain generalization so that we can perform analyses, I am hesitant to agree with the way assumptions are introduced with \"selection diagram\". In my opinion, the definition is confusing. If the $S$ variable is an additional cause for the observed variable (e.g., Figure 1b - 1d), this is essentially changing the underlying causal semantics among the observed variables, which is not the setting described in the paper. In the medical study example in Section 2, what is the additional cause for $W$ (Figure 1b) in this context? Shouldn't it be $W \\rightarrow S_W$ since it is a (general) kind of selection? Figure 1c - 1d share the same problem.\n\n### 2. the modeling of domain generalization\n\nAs a follow-up to 1., a very relevant notion in the medical study context is selection bias (e.g., \"A structural approach to selection bias\" by Hernán et al., 2004). While I understand the fact that in this paper the domain generalization may not be limited to selection bias, the practical example presented (e.g., observational study vs. randomized trial) seems to be more aligned with the selection bias analysis. Further clarifications will be very helpful.\n\n### 3. the limited significance of theoretical results\n\nWhile it is nice to see a formalized connection between (certain types of) domain generalization to transportability theory, there is a worry about the significance of the theoretical results. For instance, Theorem 1 is directly applying Definition 3. Theorem 2 and Theorem 3 are, to a certain extent, direct outcomes of observational and interventional equivalences between different SCMs. The analysis on relative robustness is essentially just hierarchical relations between equivalence, observational equivalence, and interventional equivalence, which are established results in causal inference literature (e.g., \"Elements of causal inference\" by Peters et al., 2017).\n\n### Some additional minor questions/comments:\n\n- Is $Y$ limited to binary?\n\nIn introduction, what is the reason behind the \"informative purpose\" served by $0 < l < u < 1$?\n\n- Before Section 2, \"share an unobserved confounder\", maybe \"at least one\" is more rigorous (just a minor thing, though).\n\n- Typo: Section 2.1, \"instead optimizing over\" -> \"instead of optimizing over\"\n\n- Typo: Section 2.1, \"a chosen uncertainty set\" -> \"a chosen uncertain set\"\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "K-7rGwS1xP", "reviewer": "Reviewer_wQrN", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "Based on the existing formulation of the domain generalization problem, the authors proposed to find both the upper and lower bound performance on the empirical distribution of data from an unknow domain. \nvia MCMC method. The authors demonstrated that, following the notation of causal models, the gap between the upper and the lower bound characterizes the transferability towards a target domain.", "summary_of_the_review": "It seems this work is well conducted. Under certain assumptions, the proposed method provides a new perspective to view the domain generalization problem. ", "strength_and_weaknesses": "Pros:\n- The paper is well-written and this work is, in general, of high quality. \n- The authors introduced the proposed method in a comprehensive way with sufficient notations, definitions and theoretical claims.\n\nCons:\n- It seems the authors considered discrete observations and finite domains. However, this setting is maybe too restrictive for many real-world problems.\n- The proposed method originated from the robust optimization problem in Eq.(2), which optimize for the best predictor under the worst-case causal graph. While the authors claimed the bound leads to a distributional robust guarantee, they didn't explain the connection of robust g\n\nMinor issues:\n- Section 2, first paragraph: [What does the / mean?]\n- Section 2, second paragraph, typo: factors such [as] physical activity levels \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HtIqSsxbo2", "reviewer": "Reviewer_KuxZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper introduces the partial transportability task. Unlike standard transportability, where a target quantity in a target domain must be point-identified, in partial transportability, it may be bounded instead. The theoretical development in the paper connects this new notion to existing theory. An algorithm for this task is introduced, based on Gibbs sampling.", "summary_of_the_review": "Interesting idea, but I recommend rejection until the problems with the theoretical results can be resolved.", "strength_and_weaknesses": "The paper introduces an interesting new task, allowing progress to be made in cases where the usual notions of transportability are too restrictive.\n\nUnfortunately, I encountered problems with several of the theoretical results in this paper.\n\n* Definition 3: The condition that the subset is \"the maximal subset\" makes this ill-defined, and it is too simplistic for what you want to show in Theorem 1. The definition is ill-defined if there are multiple subsets that are each maximal w.r.t. inclusion, e.g. for the graph S -> A <-> B <-> Y. Then the Markov blanket of Y includes both A and B, but conditioning on both make Y and S dependent. Conditioning on either one gives a \"maximal subset\" that satisfies dependence. But for most distributions of the source domains, I expect that only one choice (usually Z={B}) will solve the worst-case optimization problem (2).\n\n* Theorem 2: The phrase \"the maximal subset\" also appears here, making the statement of the theorem unclear if  there are multiple maximal subsets. (The proof of this theorem refers to two theorems in an earlier paper, but those make no mention of maximal subsets or Markov blankets.)\n\n(The same phrase also appears in propositions 1 and 2.)\n\n* Theorem 3: This is a suspect result - why would the lower bound have this special status? In the proof, I don't see why you can split the maximization over the terms when going from (16) to (17), or how the theorem's conclusion is drawn from (17). Also, (16,17) treats x as constant and then maximizes over it, while in (2), an expectation is taken over it inside the maximization. Can you explain these points?\n\nMinor comments:\n\n* (page 2) \"is the statement\" -> \"if the statement\"\n\n* (page 4) \"neurodegenrative\" -> \"neurodegenerative\"\n\n* final equation of section 3: $A \\neq B \\neq C$ does not imply $A \\neq C$. I think the latter is what you want to say though. (I saw a similar construction elsewhere.)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ASIFG5H2Iq", "reviewer": "Reviewer_pRFj", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The paper formulates partial transportability to bound the query in the target domain in the domain generalization problem. The authors show that invariance learning is a special case of partial transportability tasks and show that invariant predictors and more general solutions to robust optimization problems. They evaluate the algorithm on a synthetic dataset.", "summary_of_the_review": "This paper tackles the domain generalization problem with an under-studied causal method and models each domain as a different causal graph (SCM). Considering this paper researching an under-studied method in the DG field, I vote for a weak accept. ", "strength_and_weaknesses": "Pros: \n\n1. It’s novel to introduce partial transportability to the DG problem.\n\n2. Instead of the point estimate, deriving a tight bound of the conditional expectation in the unseen domain is novel.\n\n3. Illustrating invariance learning as a special case of partial transportability task is novel.\n\n\nCons:\n\n1. A related work is necessary to demonstrate the background of the methods used in this paper, for example, transportability problem, etc.\n\n2. Lacking datasets in experiment evaluations. The authors only evaluate the algorithm on one dataset. \n\n3. The author should review [1] in detail and describe the differences because their proposed method has some overlaps with this paper. \n\n[1] Zhang, Junzhe, Jin Tian, and Elias Bareinboim. \"Partial counterfactual identification from observational and experimental data.\" International Conference on Machine Learning. PMLR, 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject