Asymmetry Learning for Counterfactually-invariant Classification in OOD Tasks
Authors: S Chandra Mouli
Bruno Ribeiro
Venue: ICLR 2022 Oral (2022)
Keywords: out-of-distribution classification
symmetries
counterfactual invariances
geometric deep learning

Abstract: Generalizing from observed to new related environments (out-of-distribution) is central to the reliability of classifiers. However, most classifiers fail to predict label $Y$ from input $X$ when the change in environment is due a (stochastic) input transformation $T^\text{te} \circ X'$ not observed in training, as in training we observe $T^\text{tr} \circ X'$, where $X'$ is a hidden variable. This work argues that when the transformations in train $T^\text{tr}$ and test $T^\text{te}$ are (arbitrary) symmetry transformations induced by a collection of known $m$ equivalence relations, the task of finding a robust OOD classifier can be defined as finding the simplest causal model that defines a causal connection between the target labels and the symmetry transformations that are associated with label changes. We then propose a new learning paradigm, asymmetry learning, that identifies which symmetries the classifier must break in order to correctly predict $Y$ in both train and test. Asymmetry learning performs a causal model search that, under certain identifiability conditions, finds classifiers that perform equally well in-distribution and out-of-distribution. Finally, we show how to learn counterfactually-invariant representations with asymmetry learning in two physics tasks.

Published as a conference paper at ICLR 2022
ASYMMETRY LEARNING FOR COUNTERFACTUAL- INVARIANT CLASSIFICATION IN OOD TASKS
S Chandra Mouli
Bruno Ribeiro
Department of Computer Science
Department of Computer Science
Purdue University
Purdue University
chandr@purdue.edu
ribeirofcs wwwrooecss.ruuu....ee. purdue. edu
ABSTRACT
Generalizing from observed to new related environments (out-of-distributiin) central to the reliability of classifiers. However, most classifiers fail to predict label Y from input when the change in environment is due a (stochastic) input transformation ~ o ' not observed in training, in training we observe 7 X', where X' is a hidden variable. This work argues that when the transformations in train 7 and test T are (arbitrary) symmetry transformations induced by collection of known m equivalence relations, the task of finding a robust OOD classifier be defined as finding the simplest causal model that defines causal connection between the target labels and the symmetry transformations that are associated with label changes. We then propose a new learning paradigm, asymme- try learning, that identifies which symmetries the classifier must break in order to correctly predict in both train and test. Asymmetry learning performs a causal model search that, under certain identifiability conditions, finds classifiers that perform equally well in-distribution and out-of-distribution. Finally, we show how to learn counterfattually-inaarr
representations with asymmetry learning in two simulated physics tasks and six image classification tasks.
INTRODUCTION
A significant challenge in classification tasks happens when the test distribution differs from the training distribution (i.e., the task requires out-of-distribbttio (OOD) generalization), since not accounting for the distribution shift can lead to poor generalization accuracy (Geirhos et al., 2020 Hu et al. 2020; Koh et al. 2020 D' Amour et al. 2020). If the learner sees examples from the test distribution, finding classifier invariant the distribution shift can still be data-driven task (e.g.. classical domain adaptation BBen-David et al. (200)); Muandet et al. (2013) y; Zhao et al. (2019)) This includes cases such invariant risk minimization (Arjovsky al.) 2019) and its generalizations (Bellot & van der Schaar] (2020), where the training data and the test data distributions overlap in way that can be exploited by data-driven algorithms (Creager et al. 2021 Krueger et al.
2021 Rosenfeld et al. 2020).
However, if the learner sees no examples from the test distribution, the task is not purely data-driven and requires assumptions about the data generation process. More formally, our work considers general OOD tasks with training distribution P[Y"r ))), where X 7 Xt, with Xt hidden variable with distribution P(Xt) and 7 T is random input transformation in training T X' X, where z is the application of transformation E on x X. The difference between train and test is change in input transformation with y : yu and X := 7 o Xt, where P(T") ee P. We are interested learning an invariant classifier that generalizes well in held out examples from the training and test distributions.
The definition transformation matters in this task. We first seek to generalize the existing literature on transformation invariances, e.g. (Shawe-Taye 1993 Kondor & Trivedi 2018 Finzi et al. 2021
Maron et al. 2018: Murphy et al. 2019b Mouli & Ribeiro 2021 Bronstein et al.) 2017). Our transformations are tied to equivalence relations rather than transformation groups, which frees them from the need to have inverses (in order to form a transformation group). Our transformations may not have inverses.

---

We define input symmetry in space X' with at least two elements An equivalence relation in X is a binary relation ~ such that for all a, b, c E X, we have (i) a ~ a. Equivalence relations allow to Published as a conference paper at ICLR 2022
We also explain why the task of learning invariant OOD classifier is not, in general, solvable via traditional data augmentation. Before we continue describing our OOD learning task, it is important to clarify the connection between Pearl's causal hierarchy and invariant representation learning.
Pearl's causal hierarchy and invariant representation learning. Pearl's causal hierarchy (Pearl Mackenzie 2018 Bareinboim et al. 2020g) has three layers: Observational (Layer 1). interventional (Layer 2), and counterfactual (Layer 3). Upper layers can perform lower layer tasks, but not vice-versa (see [Bareinboim et al. (020)). Tasks should be described using the lowest layer that can solve them.
Layer 1: Any task that can be performed without constraints on the causal model, i.e., by data alone, observational (Layer 1). Traditional domain adaptation is a Layer task. Note that a classifier that performs well OOD is itself Layer classifier, since tries to predict P(Y )x
Layer 2: Without observations from P(X") and/or P(Y ) learning an OOD classifier requires some assumptions about the data generation process (Layers 3 assumptions). Data augmentation traditionally an interventional task (Layer 2). with new interesting methods increasingly using causal language (Ilse et al.) [021]] Teney et al., (020). For instance, in task predicting an image' foreground, knowing how to act on an image training X to change the background seen in training to the backgrounds seen in test X o X with a transformation T, implies know how to predict P(Y do())).
Layer 3: Counterfactuals are the most challenging task. We start our description with an example. Consider a random continuous transformation T7 (in training) which changes to random transfor- mation The (in test). Let X describe a hidden variable such that X :- Ti o T o T3 o Xt and X == Ti o T.ee o T3 o Xt, where Ti and Ta are independent continuous random transformations and P(T)) P.TT)). Assume the target variable Y depends only on X1, Tī. and T3.. To counterfactually ask what would have happened to the observed input if had forced do( [2), inquiring about X(T x²)
æ. Note that do = f22 does not change Y. Also note that the knowledge of X = x is an indirect statement about Th since P(T x) * P.TT). That is, for x, x' X.
(f PIX i2) - T' t, X = r)dP(T =1 x a))
P(X(TT = 12) x x'1x" =.)
x)) =
(1)
Equation and the difference between the causal hierarchy layers will be relevant for our results.
Contributions. Our contributions can be described as follows:
1. We introduce generalization of transformation groups via symmetry transformations tied to equiv- alence classes that removes the requirement of invertible transformations common in definitions using transformation groups.
We introduce the concept of counterfactual invariant representations for symmetry transformations and show how it can be described as counterfactual task for causal structure discovery.
3. Finally, we introduce asymmetry learning, which describes a representation regularization that, under set of assumptions, learns the correct counterfactual invariant OOD classifier.
SYMMETRIES AND TRANSFORMATIONS
Geometrically, an object is called symmetric if there is a transformation on the object that does not change its shape (in some definition of shape). For example, square is symmetric with respect to rotations. The notion of symmetry however is not restricted to geometric notions. In general, we can define mathematical object symmetric if there is a transformation on the object that returns another object equivalent to the first (Rosen) 2008 Chapter 10). It is clear from this definition of symmetry that first need to define what mean by equivalent objects. For instance, we say two geometrical objects are equivalent if they have the same shape, but we need a more general definition.
equivalence relation
(ii) a
a, and (iii) (a. and e)
2

---

Published as a conference paper at ICLR 2022
define equivalent objects in X': b means is equivalent to b. The set of all objects equivalent to some a E X is called the equivalence class of a, defined as [a] := (a E X
x ~ a). Note that one can define m 2 equivalence relations the same input space. The equivalence class of æ with respect to equivalence relation k is denoted [xx](a] k L,.... m. Two inputs a, Ó X' might be equivalent under one equivalence relation ~1, but not equivalent under a different equivalence relation ~2 that is, we can have both E [a](] and $ [a][2]] Still, even in this last case is possible that a is equivalent to some other input o b in both equivalence relations, i.e., it is possible (2). We denote the collection of equivalence classes of X' under
3e E X, C. + a, s.t. C. [a]{) the equivalence relation ~ as the quotient space // ~ {[x:](A) I X.
(1) o [a]
Transformation group example. Consider the bijective transformations t group G, l E G. We now define an equivalence relation over G as t x ~G æ: for all L E G. The cquivalence class [=] [=][G] is x's e's orbit defined as [x]| ;= {æ' 3t G, x' = to
X' of transformation
For example, if æ). to...
G is the group that permutes the elements of vectors in R3, then (1, ~G (2, 1.3).
Property functions example. Another way of deriving an equivalence relation is via functions of the input space 2 X' I2, where the output 22x) is particular property of the vector I E X. For example, given an observation of length T from dynamical system, E RdxT a possible property function could be Zenergy(+) (-) that computes the energy of the dynamical system. Assuming there are m known properties 21..... Fm with 2 X - RP: we can construct corresponding equivalence relations ~i..... m such that for any x, x' E X. x ~ x' if 2z(x) = 2₁ (2'), Vjj * i. In words, two inputs are equivalent under ~; if they have the same properties for all 2j.J i.
Symmetry transformations. As seen above, symmetries can be defined without defining how the input is transformed to create the equivalence classes, although defining set of transformations is useful when describing the equivalence class. Given an equivalence relation ~ we can define a set of transformations T that respect the equivalence relation such that AA E T, Va: X, to T the set of symmetry transformations of ~ Similar to transformations groups, T always has the identity transformation fi o x, but in contrast, all the transformations T need not be bijective.
We call
Join of equivalence relations. Similar to how two groups can be joined to form larger group, two equivalence relations can be joined form coarser equivalence relation. Given two equivalence relations. ~1 and ~2, their join ~1 ~22 is defined as: for all æ, x', x(~1 V ~2 )x if and only if there exists a chain of equivalence relations æ ~ I1, is easy to check that ~ v ~2 is an equivalence relation.
0h-1 ~ kn. af with all ky E (1,
We are now ready define a general causal model that detines the training and test distributions in our setting.
3 SCM FOR SYMMETRY-BASHD OOD TASKS
Let X' denote the input and output spaces respectively. We define our general structural causal model (SCM) follows. We define X e X as the unobserved canonically ordered input
x = g(Uw),
(2)
with Un. background random variable and g Uu - X' is measurable map. This definition is general enough to define any task.
There are m possible symmetries given in the form of equivalence relations ~i,..., m over the input space X. Let (()) denote set of symmetric transformations on X' corresponding to the equivalence relation ~A,1 & k & m. In other words, for all æ E X' and / E T(k), we have (t 2) ~ æ. Similarly, let be the set of all symmetric transformations with respect to the join equivalence relation L..... =~1 V .... m- We can think of transformation E T as ((hn)
2., that starts at œ. applies a transformation ((k)) (Kk) to get æ [ar] and so on until it stops and outputs value æh h >
path æ e(k1)
..
Let UI,...,U ... be independent background variables associated with the m symmetries, where U, E U. = 1, I,..., m. These background variables together select function t(U,,..., U,) from the set T as follows. Each Up independently selects a countable sequence of transformations (k) (k)
1, --.. (k), Then, (UU1,.. Un) is defined by interleaving these transformations
3

---

Published as a conference paper at ICLR 2022
T
1
Trtaze
Training data
T
Titrons
Upright
(b)
T
Test dala exsmple)
Titrane
T
Tatans
Y= Flat
X²
Tatie Karr De Kil
x
Uoune 20l Ao (( "ha jey Tartoen
T
T Teraaa
T
T
Y=
Upright
(c)
y
Plat
Traditional augmentation
x
X
x
Treane
T
Terraw
T
Thtrane
Y Flat
Counterfactual data
X"
T
Thrass
T
Thtmos
Counterfacturt imputio we must be inveriant
Tul Yuuu. Pae
Talla moo
Toot
T Triaua
50"
T
X
Flat
(+5.0)-
Fitwerii Virue ong Po
X X-T.s. Tir Rapi
Figure I: Example that illustrates a few important concepts. (a) Training data shows how Equations 2 to
define the training distribution P(X", y"") Task: Given an image of rod (shown in brown), we wish to predict the orientation of the rod, i.e., whether the rod is upright or flat (Y := h(Um.)) In this example,
have TD {rot] (image rotations 0 and 90") and Bi [trans] (horizontal translations of -5,0, +5 units) as any horizontal translation does not affect orientation of the rod. (b) The test data (only a single example shown) suffers an OOD shift through a different distribution over P(Um))) where non zero translations can happen before the second rotation. (c) Here we illustrate why an invariance that is good for traditional data augmentation, such counting the brown pixels in the green shaded area, would fail in test if, say, +5 units horizontal translation happens before rotation. (d) Here illustrate why counterfactual language needed to define how the input data would change the presence changes to U Using counterfactuals, finally clear that the invariant representation must be able to also consider the number of brown pixels inside the horizontal purple and green bands (among other horizontal bands).
t(U1 .......,U))= = (fi,0, above. Since (1), T contain the identity transformation, tUU,,..., Um) can be described by finite sequences of transformations. The observed X is the result of transformation of X
1, )o.... (Ey,0, o.... of o.... construct the path described
(m))
X t(U1 Um) xt.
(3)
Finally, the label Y is defined as a function of the untransformed canonical input X as
; h(x*, (U)) Uy),
(4)
where (1,....,,, m) is unknown. This means that is not invariant with respect to equivalence relations ~,,, i E ID, i.c., examples æ and x' E [z) (+) can have different labels. A distribution over the variables Un. (U, ".)m,.U Uy entails joint distribution P(X, Y) over the observed variables.
Illustrative SCM example. Figure illustrates data generation process. The training data Figure [ (a) has X defined as a centered upright brown rod (i.c., X is deterministic). The label Y is defined by the rotation transformations To {T T translated by (-5,0, 5) units via transformations T 90º ). The image also be horizontally (Ttrans T T (only and +5 translations depicted), but Y does not depend on these horizontal translations. The transforma- tions applied to X are randomly chosen via Una and Urrans which are two bidimensional vectors indexing sequence four transformations that interleave rotations and translations (see Figure [T. A representation that counts the number of brown pixels in the green shaded area of X is enough to achieve 100% accuracy the training distribution. We formally define OOD distribution shifts next using Figure T for illustration.
OOD distribution shift. Let D {1..... m) ID be the complement of the set symme- try relations D that Y depends We define the OOD distribution shift between train and test as a shift the distribution of ((UU)),ef) influencing the distribution of input transforma- tions in Equation (3), which in turn shift the distributions P(X"), P(Y"IXu) P(yu, X") to
4

---

Published as a conference paper at ICLR 2022
P(X")), P(Y P(Y xx") respectively. Since X does not causally affect Y in our structural causal model (Equation (4). changes in input transformations are able to shift X)) For example, in Figure (bbb the test data (only single example shown) could suffer an OOD shift due different distribution over P(Urrans) that introduces non-zero translations before the second rotation. Note that the representation that counted the number of brown pixels in the green shaded area, which was perfect for the training inputs X", will achieve poor accuracy in the test inputs X
Learning OOD classifiers. Equation shows that the label Y is invariant to changes in the distribution of (Di) in the test distribution, but we do not know ID.. Hence, if our representation of X is invariant to changes in the distribution of (D. we will be able to perform the OOD task.
4 ASYMMETRY LEARNING & FINDING THE RIGHT REPRESENTATION SYMMETRY FOR THE OOD TASK
4.1 FINDING OOD-INVARIANT REPRESENTATION AS CAUSAL STRUCTURE DISCOVERY
We first define the process of finding an OOD invariant representations for the symmetries {~i)ief our classifier should be invariant in the test data. Since Y does not depend on {Ui] will make a representation of X that is invariant to transformations driven by {Ui)ee-
Definition 1 introduces the concept of counterfactual invariance for symmetry transformations. We note that this definition is less restrictive than the parallel work of Veitch et al.] (202T) Definition 1.1): whereas Veitch et al. 2021 Definition I.1) require invariance over the entire sample space, we only require invariance over the test support of transformation variable U.. The definitions are equivalent if the test support is the entire sample space of U..
Definition 1 (Counterfactual invariiainnnt representations for symmetric transformations). Assume the SCM defined in Equations 2 to (4) A representation I; X Rd. d > 1, counterfactual invariant to the transformations' Ti Ti. T2.u..... of equivalence relation ~i 1 & iiiinn m. if
rx(x) I,(X(U: xx)lx=))
almost everywhere, Vū; E Supp(U?(), Va supp ", where supp(A) is the support of random variable A. A representation Iss X RR, d 3 1, is counterfactual -nivariant to a subset
S = (1, [1,....,,, , if it is jointly counterfuctual-nnvan equivalence relations {~s)jes-
to the transformation indices (Uz)see of
We refer the reader to Equation 11 for the relationship between the counterfactual variables X(U a)|U? u and (U; X
Figure d illustrates why counterfactual language is important for our task: It states that given an input X = x we need to know how it would have been different if we had chosen a different distribution P(Urrms)) resulting in a different sequence of transformations T Tuuee T2, From Figure ()) it is clear that we cannot simply data-augment our training data with translations. since we would think that counting brown pixels the green shaded area is an invariant representation for Umans-
Up until now we have not imposed restrictions on the types of transformations ( i= 1,, 1,..., m, we consider in this work. Our next results require imposing conditions on these transformations.
Definition 2 (Equivalence class lumpability). The quotient space X/ ~; is the set of equivalence
classes of X with respect to equivalence relation ~i, i = -1..., m. Let [x](() E X/ be the equivalence class of X with respect to equivalence relation ~i. Then, 2/ ~ is said to be lumpable with respect to a transformation set T v( E X/ ~; and Vt E
3007700 e (X/ ~)) s.t. x= [
to x: [<77(00)
In words, if the lumpability condition in Definition 2 holds for equivalence relation ~; with respect to a set of transformations T, then every transformation in T maps all points within an equivalence class [x= E X/- ~ to points in a another cquivalence class [x'](t) e (x/ ~). To illustrate the lumpability condition, consider two transformation groups G1 and G2 whose transformations commute, i.e., v(1, t2) E G1 x G2, t o tz = t2 o f1. Then the equivalence classes imposed by G,, ie., the orbits [x] (1) {t, o x Vt, E G.), are lumpable with respect to the transformations Gj, for
j 21 and
5

---

Published as a conference paper at ICLR 2022
1
Label Y-0 Labol V=t X X
(1 Causal DAG
RV 35
60
120
Fiat
01
24
Asymmelry leeming: Caueal model seerch using Red arrows indicate the asymmetry being considered the causal model.
(1) Causal DAG with counterfactual invariant representation o
seymmelry (illuttration m=3).
(a)
(b)
(c)
Figure 2: (a) (i) Truc causal DAG; (ii) causal DAG counterfactual invariant representation; (iii) Causal model (c) An example figure where training data has single example per equivalence class in X/ ~- (green rectangles). Then, have COMP
search. (b) Partial order over invariant representations (arrows indicate higher invariance).
COMP(Fer D) even though F(1y more invariant (simpler) than Fg.
Figure 2a i) shows structural causal graph where edge U. Y exists only if E ID. Then, we use the definition of lumpability to prove that, under certain conditions, a most-expressive representation I; invariant with respect ~ allows to identify if there is no edge U; Y in the causal DAG.
Theorem (Counterfactual invariance & causal DAG identification). Let // ~a be lumpable given Then, the structural causal DAG implied by Equations to (depicted in Figure (a(i)) does not contain the edge U. Y iff
every TD,, jj * i as in Desinition2 [
IP(YII((X),u))
VP(X)),PPUU)).... V.(())) where I is most-expressive representation that invariant with respect ~..
The proof is in the Appendix. With the lumpability assumption of X/ ~i I; in Theorem counterfactual-invariat representation. We now use Figure Za (i) describe the result in Theorem We first note that the representation F depicted in the figure is counterfactual invariant to D. and hence also counterfactual invariant & ID. Next we see that since the representation Is is counterfactual invariant to UR. there is no arrow UR (X) in Figure Figure2altii. If there is no arrow Uk Y, the missing arrows from U2 to (X) will have no influence the ability of T (X) to predict Y, assuming I' is mose-sxpressive. If there is an arrow U2 - Y. cutting the arrow Us - (X) creates a loss in predictive performance from I (X) to Y for some distribution background and observable variables. If (xX)) never loses any predictive power over Y for any distribution of the background and observable variables, then there is no arrow Uk - Y.
the
Assumption (Asymmetry learning training data). In asymmetry learning we assume that every large training dataset sampled (atureeaat)) 2) j E {1....,m, m,, contains observations of jen that violate Equation 5p. Hence, if Equation (5) holds for some (1,...,m) ......m] in this dataset, we can conclude that there is no arrow U, - in the true causal DAG. See Appendix for a justification of this assumption.
X/ -i,2 (1...., m. lumpable given TW) # i, and that from "Y",X") an arrow Uj - Y in the causal DAG of Figure
Next we use Assumption D and the previous results search for the right OOD invariance.
4.2 CAUSAL STRUCTURE DISCOVERY OF RELEVANT SYMMETRIES
We need general procedure for obtaining the unknown set I, which is equivalent to finding all transformations indices (UD) S .U,,...,4u Um. that act as confounders between Y and X in the causal DAG in Figure 2a i). Finding whether an edge exists or not in the causal DAG is known as the causal structure discovery problem (e.g.. [einzee-eee Deml et al. (2017)). The principle of our search is learning the causal structure with the fewest possible edges into Y (i.e., where Y is invariant to most U,, 1,... m) while also maximizing the likelihood of the observed data. Accordingly, take the score-bate based causal discovery approach (Chickering) (2002); Huang al. (2018) that
assigns scores to each allowed DAG based on the training data and the complexity of the DAG to find minimal causal structure that fits the training data. This idea is visualized in Figure 2a iii)

---

Published as a conference paper at ICLR 2022
where causal graphs with more edges between the transformation indices into Y are defined to have higher complexity and are higher up in the partial ordering. Our search space is simpler than typical structure discovery tasks: The DAGs in our search space have the same structure for X and only differ in edges of the form U, - Y, E (1...., m). Next, we describe a scoring criterion that uses Theorem and counterfactuul--nvariin representations assign scores the corresponding causal structures.
Proposed DAG scoring criterion. For each DAG in the search space, we wish to assign a score based on the training data D = {(x((1) . "²) under Assumption for a classification task with C' classes. Theorem T shows that there is correspondence between a causal structure without the edge U; - Y and predictive probability gap between the original input and most-expressive representation I that is counterfacuually--mariinn to U. Thus, under Assumption]] [ we can represent the causal search from Figure 2aliri) in terms of a search over sounterfactually-inen -invarrian representation function classes as shown in Figures 2a ii) and (2b Formally, we are given a collection function classes & : {Fs S _ (1...... ..... m) where Fe 18 family of functions I'ss that are counterfactually- invariant to all U, E S (Definition] I]. We wish to score each of the function classes Fg E f to indirectly learn the correct causal structure.
The minimum description length (MDL) principle (Schwarz, 1978) is commonly used for causal structure discovery (Budhathoki & Vreeken 2016 2017) and comes with the key insight that learning from data can be viewed as compressing it. Given the collection & and the training dataset D, MDL finds the function class Fs f that compresses D the most. While there are several ways of encoding a dataset given the function class, normalized maximum likelihood (NML) code is known be optimal (Shtarkov 1987p. NML code computed as follows
Lami D) L(FslD + COMP D)
where L(FglD) = su M 1 log P(y (2(x())))))))))))))))))))))))))) is the maximum log-likelihood of F& given the data and
n2 sup 11
COMP(Fe, D) log
Σ
P(y P (T(((())))) Tye's f=1
(2) -... o.)) E(O,.....
measures the complexity of the function class F& by computing how well can represent different label distributions for the given inputs (x(*) ] in training. We can estimate the combinatorial sum in Equation 7 by uniformly sampling random labels for all the training examples.
Since COMP D) is computed using the training data, it may underestimate the complexity of function classes if, for instance, all the training examples are generated with U, u4. Then, F()) and Fø are given the same score even though F(g) is clearly more invariant and thus, a simpler function class. This can happen in practice if, say, all images upright in training with rotations applied; both rotation-invariant and rotation-sensitive function classes get the same complexity score.
In order break the above ties of our COMP score, asymmetry learning adds additional term the NML score that chooses models that have higher invariance based on the partial order (see Figure 2b). We extend the penalty proposed by Mouli & Ribeiro (2021) (2021) and use R(Fs) == |[F F E & F Fs)l, the number of function classes that are higher in the partial order than Fs. as the tie- tie-breaking We define the final score of
term. For example, figure R(F(1)) = (1.22)) F(1.3) F(12233)
each function class Fi F0
D) = Lumil (Fs, D) R(Fs).
(8)
The score in Equation (8) can be minimized by scsre- causal discovery algorithm to obtain the final DAG. We use Greedy Equivalence Search (Chickering 2002) to showcase a concrete instantiation of asymmetry learning- Other score-based structure discovery algorithms could also be used.
Greedy Equivalence Search. Greedy Equivalence Search (GES) is greedy search algorithm that optimizes a given scoring function over DAGs. In our setting, the search begins with a DAG with no edges of the form U; Y,i (1, (1....,m)) m). In the first phase, GES adds these edges one at a time
7

---

Published as a conference paper at ICLR 2022
Table 1: Results for different function classes on the pendulum task with = [1) and = (1, R(F),
COMP(F, D) and S(F, are discussed as Section Bold values indicate the function class chosen by GES method with the proposed scoring criterion. Test accuracy is computed on the extrapolated dataset after
shifting the distribution of ((UU))en))
(1]
[1,2)
Model closs
Architecture
R(F)
OUMP(F,2) S(F,1)
Train Ace.
COMPLEF 12)
S(F,
Train Acc.
Test Acc.
Fz
X
0.282
23,89
98.5 (0.9)
98.3 1.4
0.501
532.81
72.7 (0.4)
69.4 (0.5)
Fi
X x
Y
0
0.382
633,32
63.8 (7.0)
51.2 1.0)
0.292
284.75
85.2 (0.5)
84.6 (0.2)
F0
2
1.256
26,80
98.9 (0.8)
(1165)
0.995
4.54
99.7 (0.2)
99.5 (0.2)
that maximally improve the score in Equation {8 until there is no improvement. In the second phase, GES begins from the DAG obtained at the end of first phase and deletes edges one at a time until such deletions do not improve the score. The DAG obtained at the end of the second phase is the final output of the algorithm. Under the causal Markov and faithfulness assumptions, Chickering (2002) showed that GES optimal in the large sample limit if the scoring function locally consistent.
5 RESULTS
Pendulum task description. We evaluate the proposed method in a simulated classification task. Our input æ is motion vector over time (6c. 40, di )r_ 1 of a simple pendulum of an unknown length / after it is dropped from some initial angle 9 with d0g = O. After initial seconds of uninterrupted motion, we simulate an elastic collision by placing another object of same mass at the bottom. The classification task is to predict whether the kinetic energy imparted by the pendulum is enough to move the second object beyond a certain threshold.
Physical properties and equivalence relations. We consider the following two properties of the dynamical system described above: 21 X' - In which computes the initial potential energy of the system and 22 : X I which returns the time of collision. The equivalence relations ~ 1 and ~2 are defined using these properties as defined in Section 2 For instance, two pendulum motion curves x, x are equivalent with respect to ~,, i.e., a ~ x,, if they have the same time of collision, 2²(x) 22(x)). Then (1) consists of transformations that change the initial potential energy of the system (for example, by changing the length of the pendulum or the initial dropping angle 0n) while keeping the time of collision same. Similarly, ~ x' if their respective potential energies are the same and transformations in T change the time of collision while keeping the same initial potential energies. Note that the space of equivalence classes X/ ~1 is lumpable with respect to (2) and vice versa (Definition 2 Thus, by Theorem | we can use predictive performance of counterfactual -nvarraiannnnaannnnnaaaa representations for scoring the causal DAGs.
Unknown D' and OOD classification. We consider two scenarios for the label Y given X. First, if the motion of the pendulum is not damped by friction, then Y depends only on 21 (zx), i.e, ID (1). Second, if the motion of the pendulum is damped, then Y depends on both 21 (x)) and 2 (z). i.c., D = 21. The extrapolation test data generated by shifting the distribution of the background variables (U:) The task of a structure discovery algorithm is to correctly identify D.
Results. We use the greedy equivalence search (GES, Section 4.2) algorithm to search over the different causal graphs with the proposed scoring criterion defined in Equation
(8) We build classes
of counterfactual-innartt -nivarrian representations F3 corresponding to each possible value of S Σ {1, where every I's Fs is invariant to {Ur)es. For example, F(1) is family of feedforward neural networks that only take =x) as input, i.e., invariant to 2 (x=). whereas Før is sequence model (e.g., LSTM) (STM) with no invariance. Table I reports the estimated complexity COMP(F, D) and the final scores S(F, D) for the different function classes for the two tasks. The bold values indicate the function class chosen by the GES algorithm. When ID = (1), the greedy search stops after adding the edge U1_ - Y adding the second edge U2 Y only worsens (increases) the score. When D= 21, the greedy search is able to improve the score by adding both edges, first U1 - and then U₂ - Y. In both the cases, the extrapolation test accuracy achieved by the chosen model class is the highest.
Image classification task. Appendices A.4 and A.5 also offers an application to image classification using image transformation sets (groups and nongroups).
8

---

Published as a conference paper at ICLR 2022
6 RELATED WORK
Counterfactual inference and invariances. Recent efforts have brought causal inference ma- chine learning (extensively reviewed in Schölkopf et al. (202T): Schölkopl (2022). ). Invariant Causal al.] 2018) and Invariant Risk Minimization meth- ods (Arjovsky et al. 2019: Bellot & van der Schaar (020) learn representations that are invariant across multiple environments but have been shown to be insufficient for OOD generalization in classification tasks without additional assumptions Ahuja et al. (2021). Wang & Jordan (2021) use counterfactual language to formally define and learn non-spurious representations from a single environment that can extrapolate to new environments. Veitch et al. (2021) define counterfactual invariant predictors f'X) when X has a single parent Z and provide conditions such predictors must satisfy over the observed distribution (given SCM). Kaushik (CM)s.Kauhhik et al. (2020) 2021) propose counter- factual data augmentation for text datasets but they either require a fully-specified toy SCM or rely on numans-in-the-loo
Prediction (Peters et al. 2015 Meinze-Demm
generate the counterfactual data. Other counterfactual methods (Johansson) et al. 2016 Shalit et al. 2017: Qidong et al., 2020) learn representations to predict counterfactual change in some observed variables whereas in our setting, the transformation variables U/ that gener- ate the observed X are unobserved. In-depth comparison of our work with the existing counterfactual methods is presented in Appendix A.3
Domain adaptation and domain generalization. Domain adaptation and domain generalization (e.g. (Long et al., 2017 Muandet al. 2013] Quionero-Candela et al. 2009 Kojas-Carull et al.
2018: Shimodaira 2000; Zhang et al., (0155 and others) consider observed or known shifts in the data distribution, for instance, given the lest distribution P(X*), rather than counterfactual questions.
Causal structure discovery. The methods for causal structure discovery can be broadly classified into two categories. Constraint-based approaches (e.g.. (Spirtteeeees et al. (200T); [Sun al. (2007)) use conditional independence tests and reject causal graphs that impose more independence than what is observed in data. On the other hand, score-based causal discovery approaches (c.g.. Chickering (2002); ; Huang al. (2018) : Ding al. (2020); Zhuu et al. (2020) assign scores each allowed causal graph based on the data and find the one with best score. While there are several works (Budhathoki & Vreeken 2016 2017, Bornschein et al.) (021) that use minimum description length (MDL) (Schwarz) 1978) as a scoring criterion, we show why it is insufficient for out-of-distribution tasks and use an additional term for tie-brea [ooudt al. (2017) minimize the divergence between distribution generated by learnt causal DAG and the observed data distribution; however the method is limited to orienting edges over observed variables, whereas our transformation variables Ug are unobserved. Recently, GFlowNets Bengio et al. (2021a b) have been used to sample DAGs proportional to score function for Bayesian structure learning Deleu et al. (2022), however we are interested in finding the best DAG with the minimum score.
Group-invariant representations. Majority of the works strictly enforce G-invariances either within the architecture (e.g.. Zaheer et al. (2017); Cohen et al. (2016): Lyle et al. (2020); Murphy et al. (2019a)) or via aatt-augmentttion (Chen 20220) and do not handle the case when the target is actually influenced by the transformation of the input. Other works (Benton et al. 2020 Zhou cet al., 2020 van der Wilk et al., 2018 Anselmi et al. 2019) consider learning symmetries from the training data but do not consider the extrapolation task that show can be solved only under certain conditions. MMuli & Ribeiro (202T) consider the special case where the transformations are from normal subgroups and do not formally describe the causal task. These works rely on invertible transformations while we define symmetries more generally via equivalence relations. Dubois et al. (022)) also define invariances via equivalence relations and, under the assumption that all such invariances hold in the data, the authors design methods for data compression. Our goal is rather different: We want discover which equivalence relations (transformations thereof) affect the label.
CONCLUSIONS
This work considered an out-of distiiiiii (OOD) classification task where the shift between train and test environments is through different symmetry transformations of the input, where symmetry transformations are defined via equivalence relations over the input space. We described the task of finding symmetries that affect the label as causal structure discovery task and show that, under certain conditions, we can use the predictive performance of invariant representations on the observational data to predict whether edge exists in the causal DAG (Theorem I. We then proposed an MDL- based scoring for this causal structure discovery. Finally, we test our approach two simulated physics tasks and six image classification tasks.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was funded in part by the National Science Foundation (NSF) Awards CAREER IIS- 1943364 and CCF-1918433 the Purdue Integrative Data Science Initiative, and the Wabash Heartland Innovation Network. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors.
REFERENCES
Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Saan-Chisttophe Gagnon-Audet, Yoshua Bengio, Toannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out-of- distribution generalization. Advances in Neural Information Processing Systemx, 34, 2021.
Fabio Anselmi, Georgios Evangelopoulos, Lorenzo Rosasco, and Tomaso Poggio. Symmetry-adaptes representation learning. Pattern Recognition, 86:201-208, February 2019. ISSN 0031-3203. doi:
(0.tol pattco.2018.07.000
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint /907 97.009993, 2019.
Elias Bareinboim, Juan Correa, Duligur lbeling, and Thomas Icard. On Pearl's ' hierarchy and the foundations of causal inference. ACM special volume in honor of Judea Pearl, 2020.
Alexis Bellot and Mihaela van der Schaar. Accounting for unobserved confounding in domain generalization. arXiv preprint 0rXiv:2007.10653 2020.
Shai Ben-David, John Blitzer, Koby Crammer, Fernando Pereira, et al. Analysis of representations for domain adaptation. Advances in neural information processing systems, 19:137, 2007.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 34, 2021a.
Yoshua Bengio, Tristan Deleu, Edward J Hu, Salem Lahlou, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. arXiv preprint arXiv:2111.09260 2021b.
Gregory Benton, Mare Finzi, Pavel Izmailov, and Andrew Gordon Wilson. Learning invariances in neural networks from data. NeurIPS, 2020.
Jorg Bornschein, Silvia Chiappa, Alan Malck, and Rosemary Nan Ke. Prequential MDL for Causal Structure Learning with Neural Networks. July 2021.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
Kailash Budhathoki and Jilles Vreeken. Causal Inference by Compression. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 41-50, Barcelona, Spain, December 2016. IEEE. ISBN 978- 54733- doi: D0.1009/CDM.2206.00000
Kailash Budhathoki and Jilles Vreeken. MDL for Causal Inference on Discrete Data. In 2017 IEEE International Conference on Data Mining (ICDM), pp. 751-756, November 2017. doi: 10. 10.1109//CDM22217..8.
Shuxiao Chen, Edgar Dobriban, and Jane H. Lee. A group-theoretic framework for data augmenta- tion. Journal of Machine Learning Research, 21(245):1-71, 2020. URL hRLh:tt::// jmlr org/
papers/v21/20 12220111.hhh.. html
David Maxwell Chickering. Optimal Structure Identification With Greedy Search. Journal of Machine Learning Research, 3(Nov):507-55, 2002. ISSN ISSN 1533-7928.
Taco S Cohen, T S Cohen, and Uva NI. Group Equivariant Convolutional Networks. pp. 10, 2016.
Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. In International Conference Machine Learning, pp. 2189-2200 PMLR, 2021.
10

---

Published as a conference paper at ICLR 2022
Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew Hoffmann, et al. Underspecification presents challenges for credibility in modern machine learning. arXiv preprint arXiv:2011.03335, 2020.
Tristan Deleu, António Góis, Chris Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. Bayesian structure learning with generative flow networks. arXiv preprini DrXiv:2202.13903, 2022.
Chenwei Ding, Biwei Huang, Mingming Gong, Kun Zhang, Tongliang Liu, and Dacheng Tao. Score-based Causal Discovery from Heterogeneous Data. September 2020.
Yann Dubois, Benjamin Bloem-Reddy, Karen Ullrich, and Chris Maddison. Lossy compression for lossless prediction. arXiv preprint arXiv:2106. 100.::2006.10000,, 2021.
Marc Finzi, Max Welling, and Andrew Gordon Wilson. A practical method for constructing equivari- ant multilayer perceptrons for arbitrary matrix groups. arXiv preprint arXiv:2104.09459 2021.
Robert Geirhos, HonnHKerrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix Wichmann. Shortcut learning in deep neural networks. Nature Machine Intelligence, 2(1 (111)6666655 2020.
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, Isabelle Guyon, David Lopez-Paz, and Michèle Sebag. Causal generative neural networks. arXiv preprint 0rXiv:1711.089333 2017.
Christina Heinze-Demi Marloes H. Maathuis, and Nicolai Meinshausen. Causal Structure Learning. arXiv: /41 [stat], June 2017.
Christina Heinze-Deml, Jonas Peters, and Nicolai Meinshausen. Invariant Causal Prediction for 08576 [stat], September 2018.
Nonlinear Models. arXiv:/706. 770.08876
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, 2020.
Biwei Huang, Kun Zhang, Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized Score Functions for Causal Discovery. KDD proceedings. International Conference on Knowledge Discovery & Data Mining, 1018:1551-1566 August 2018. ISSN 2154-817X. doi: 10.1145/ 3219819.3220104.
Maximilian Ilse, Jakub M Tomezak, and Patrick Forré. Selecting data augmentation for simulating interventions. In International Conference on Machine Learning, pp. 4555-4562. PMLR, 2021.
Fredrik Johansson, Uri Shalit, and David Sontag. Learning representations for counterfactual inference. In International conference on machine learning, pp. -0220-3029, 2016.
Divyansh Kaushik, Eduard Hovy, and Zachary Lipton. Learning the difference that makes a difference with connterfccullly-angmeeteed data. In International Conference Learning Representations, 2020. URL htll:tttss//ppeeeeeiieee wwtt/eeotnnneieememo wtweee/oorumnad--lslssslll SK1gs0NF
Divyansh Kaushik, Amrith Setlur, Eduard H Hovy, and Zachary Chase Lipton. Explaining the efficacy of counterfactually augmented data. In International Conference on Learning Representations, 2021. URL httpp:://operretteeee
net. forum? (e QKWsOcV
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Sara Beery, et al. Wilds: A benchmark of in-the-wild distribution shifts. arXiv preprint arXiv:2012.07421, 2020.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks the action of compact groups. In International Conference on Machine Learning, pp. 2747-2755. PMLR, 2018
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.

---

Published as a conference paper at ICLR 2022
David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Outto--distribution generalization via risk extrapola- tion (rex). In International Conference on Machine Learning, pp. 5815-58266 PMLR, 2021.
Mingsheng Long, Han Zhu, Jianmin Wang, and Michael Jordan. Deep transfer learning with joint adaptation networks. In International conference on machine learning, pp. 2017.
PMLR,
Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy. On the benefits of invariance in neural networks. arXiv preprint wrXiv:2055.00778 2020.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXiv: 1812.09922 2018.
S Chandra Mouli and Bruno Ribeiro. Neural network extrapolations with g-invariances from single environment. In International Conference on Learning Representations, 2021. URL
htttps://openreiiee net http://fooumm11-7..cccce
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International Conference on Machine Learning, pp. 10-18, 2013.
R. Murphy, B. Srinivasan, V. Rao, and B. Ribeiro. Janossy pooling: Learning deep permutation- invariant functions for variable-size inputs. In International Conference on Learning Representa- tions, 2019a.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In Proceedings of the 36th International Conference on Muchine Learning, 2019b.
J Pearl and D Mackenzie. The ladder of causation. The book of why: the new science of cause and effect. New York (NY): Basic Books, pp. 23-52, 2018.
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference using invariant prediction: identification and confidence intervals. arXiv preprint vrXiv:/501.01.. 2015.
Liu Qidong, Tian Feng. Ji Weihua, and Zheng Qinghua. A new representation learning method for individual treatment effect estimation: Split covariate representation network. In Asian Conference on Machine Learning, pp. 811-822. PMLR, 2020.
Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. The MIT Press, 2009.
Mateo Rojas-Carulla, Bernhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, -3321 2018.
Joseph Rosen. Symmetry rules: How science and nature are founded symmetry. Springer Science & Business Media, 2008
Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. arXiv preprint arXiv:2010.05761, 2020.
Bernhard Schölkopf. Causality for machine learning. In Probabilistic and Causal Inference: The Works of Judea Pearl, pp. 765-804. 2022.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, 10965)6612-34, 2021.
Gideon Schwarz. Estimating the Dimension Model. The Annals of Statistics, 6(2):461 March 1978. ISSN 0090-5364, 2168-8966. doi: 10.1214/aos/1 1atta////763443666
Uri Shalit, Fredrik D Johansson, and David Sontag. Estimating individual treatment effect: general- ization bounds and algorithms. In International Conference on Machine Learning, pp. 3076 3085. PMLR, 2017.
12

---

Published as a conference paper at ICLR 2022
John Sayle-Taylor. Symmetries and discriminability in feedforward network architectures. 1EEE Transactions on Neural Networks, 4(5):816 16-88,, 1993.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):2272244, 2000.
Yurii Mikhailovich Shtarkov. Universal sequential coding of single messages. Problemy Peredachi Informatsi, 23(3)3-17, 1987.
Murray Sidman and William Tailby. Conditional discrimination vs. matching to sample: An expansion of the testing paradigm. Journal of the Experimental Analysis of behavior, 37(1):5 2-2 1982.
Murray Sidman, Ricki Rauzin, Ronald Lazar, Sharon Cunningham, William Tailby, and Philip Carrigan. A search for symmetry the conditional discriminations of rhesus monkeys, baboons, and children. Journal of the experimental analysis of behavior, 37(1):23 44, 1982.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1409::4409.15500 2014.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search, 2nd Edition. MIT Press Books, The MIT Press, 2001.
Xiaohai Sun, Dominik Janzing, Bernhard Schölkopf, and Kenji Fukumizu. A kernel-based causal learning algorithm. In Proceedings of the 24th International Conference on Machine Learning, ICML '07, pp. 855-862, New York, NY, USA, June 2007. Association for Computing Machinery. ISBN 978-1-59593
doi: 10.1 00.114//2773499.223366
Damien Teney, Ehsan Abbasnedjad, and Anton den Hengel. Learning what makes difference from counterfactual examples and gradient supervision. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK. August 23-28, 2020, Proceedings, Part X 16, pp. 580-599. Springer, 2020.
Mark der Wilk, Matthias Bauer, ST John, and James Hensman. Learning invariances using the marginal likelihood. In Advances in Neural Information Processing Systems, pp. 9938-9948, 2018.
Victor Veitch, Alexander D' Amour, Steve Yadlowsky, and Jacob Eisenstein. Counterfactual invariance to spurious correlations: Why and how to pass stress tests. arXiv preprint arXiv:2106.00044) 2021.
Yixin Wang and Michael I. Jordan. Desiderata for Representation Learning: A Causal Perspective. arXiv:2109.03795 [cs, stat], September 2021.
Gesche Westphal-Fiite Fitch, Ludwig Huber, Juan Carlos Gomez, and W Tecumseh Fitch. Production and perception rules underlying visual patterns: effects of symmetry and hierarchy. Philosophical Transactions of the Royal Society B: Biological Sciences, (10(55599)200722222 2012.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep Sets. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 3091-34011, Curran Associates, Inc., 2017.
Kun Zhang, Mingming Gong, and Bernhard Schölkopf. Multi-source domain adaptation: A causal view. In AAAI, volume 1, pp. 3150-330000 555500111,2000
Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representations for domain adaptation. In International Conference on Machine Learning, pp. 7523-7532. PMLR, 2019.
Allan Zhou, Tom Knowles, and Chelsea Finn. Meta-L.earning Symmetries by Reparameterization. arXiv:2007.0293: [cs, stat], October 2020.
Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal Discovery with Reinforcement Learning. pp. 17, 2020.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 JUSTIFICATION FOR ASSUMPTION
The above assumption is inspired by the deep relationship between symmetries and intelligence. Young children, unlike monkeys and baboons, assume that a conditional stimulus F given another stimulus D extrapolates to a symmetric relation given F without ever seeing any such examples (Sid) man et al. 1982). That is, if given D, action F produces treat, the child assumes that given F, action also produces a treat. Young children differ from primates in their ability to use symmetries to build conceptual relations beyond visual patterns (Sidman & Tailby 1982, Westphal-Fitch et al. 2012), allowing extrapolations from intelligent reasoning. However, forcing symmetries against data evidence is undesirable, since symmetries provide valuable information when they broken. Unsurprising, humans are generally able to quickly find and pay attention to some types of asymmetries.
A.2 PROOF OF THEOREM 1
Theorem 1 (Counterfactuaa invariance & causal DAG identification). Let X/ ~i be lumpable given every TD), j # i as in Definition2 Then, the structural causal DAG implied by Equations to (depicted in Figure 2a i)) does not contain the edge U, Y iff
IP(TIT((X),))) - P(Y |r O,
(5)
VP(Xt), vP((U)) where I; is a most-expressive representation that is invariant with respect to --.
Proof. Notation (following Equation t(U1,..., 11 Ui Us+1,..., Um o X where t(U1...., Um) is obtained by interleaving the transformation sequences from each individual U1,... Un and we have set U, Ug.
The observed input X is X
Necessity: We wish to show that if the SCM does not contain edge U. - Y, then Equation (5) holds for all P(X*), P(U P.Um) By this assumption, Y outputs the same label for any value of U, Consider the collection equivalence classes X/ ~;. By the lumpability condition of Definition 2 all transformations {66) E T j # i, map all points in one equivalence class of ~; to points in a different one. On the other hand, all transformations ((9) E ( map points to other points within the same equivalence class under ~, Now, consider the equivalence class of X after all the transformations have been applied to X1, The equivalence class of X = t(U1...... U²-1, Uj U++1..... Un. o X is the same as that of X t(U1, ..... U,-1, 1, u²" U++1, Um) o X where U, = ui!h always selects identity transformations. This is because changing w; to velf only impacts the transformations chosen from Tii, and these transformations do not change the equivalence class under ~ Thus, we have shown that we reach the same equivalence class under ~; for both X and X
Now let I be most-expressiv representation that is invariant with respect -, By definition, r; outputs the same value within an equivalence class, thus, Tx(X) = TT(X*), ). But since by assumption U, - Y does not exist, X and X have the same label always. Thus, there is no loss of information incurred by T, in predicting Y with the additional restraint T; = (x**). Since I; is most- expressive, we have P(Y (X), Uy) P(Y y y|X, Uy) for all y E Y. This holds for all values of ug and hence we get the desired result for any distribution P(U)).
Sufficiency: We wish to show that if Equation 5 holds for all P(Xt) and (UU)),..,P((U,,, then there is no edge U; - Y in the causal graph. We will prove by contrapositive: Assume there is an edge U, Y. then we will show there exists distributions P(Xt) and (UU))...,PPLL. such that Equation 5 does not hold.
Define P(Xt) = det for some xt E X' where denotes a Dirac-delta function. Define P(U, with) 0.5 and P(U; = u:) = 0.5 for uid u; E (U.) As usual, wtth always selects the identity transformation, and u, selects single transformation fu, e T Similarly, for all j # i, define P(U,) = ب,y for utd E supp(U,) that only select identity transformations. Now, there are two possible observed inputs: x t( uit ...., (id)) x² xx and x' t(uif... u...., u o x² by, xt. Finally, define Y := (U, w thus x and x' have different labels. But, any invariant
14

---

Published as a conference paper at ICLR 2022
representation F by definition has (z) [x(x') since they belong to the same equivalence class. Thus, even if I is most-expressive, we have (x) X( Uy)] 0.5.
A.3 ADDITIONAL RELATED WORK
Counterfactual invariances. Wang & Jordan (2021) use counterfactual language to formally define and learn non-spurious, disentangled representations from a single environment. Our work is different in the following ways. In the structural causal model (SCM) of their work, the authors assume that there are no confounders between the observed X and the label Y. However, in our SCM (Figure 2a(i)). we allow unobserved confounders X" and U,, D. The hidden transformation variables U,, E ID are confounders because they affect both the observed input X and the labels Y. We leverage the fact that the confounders are related to symmetries (and do not affect X arbitrarily) to resolve the issue with unobserved confounding, Wang & Jordan (202T) also require pinpointability of the cause of the observed X. our setting, this typically not possible since there are multiple paths of transformations from X to the same observed X. Thus, all the parents of X may not be pinpointable, specifically the transformation variables UI...., Um.
Kaushik et al. (2020) 2021) propose counterfactual data augmentation for text datasets where human annotators are asked to make minimal modifications to the input document so as to change its label (for example, by changing few positive words to negative words) while keeping style, etc. fixed. This type of augmentation essentially asks the labelers to identify all the causal features in the document and make modifications to those features alone. This be seen obtaining new counterfactual examples by simulating the causal model and requires knowing the true function that describes how the features affect the labels. We consider the more realistic setting where do not have access to such a collection of counterfactual examples. In this work, we consider the traditional automated data augmentations under mostly unknown data generation process, as opposed the counterfactual data augmentation (Kaushik et al., (020) that either considers a fully-specified toy SCM or relies on humans-in- commans-in-the-aee loophe-loop to generate counterfactual data.
In Figure [[]) we show that the standard data augmentation is not sufficient for the OOD task. However, one had access to the fully-specified causal model, one could generate the counterfactual data shown in Figure (d) and learn an OOD classifier with the counterfactually augmented data (as done by Kaushik et al. (2020)) But our work does not assume access to these counterfactual examples. Additionally, we prove that counterfactual invariant classifier can be constructed from traditional data augmentation alone if the lumpability condition (Definition is satisfied. This not the case in Figure d).
Veitch et al. (2021) define counterfactual invariant predictors f(X) when X has a single parent Z and provide conditions such predictors must satisfy over the observed distribution (given SCM). Note also that Veitch et al. 22021) assume that part of the observed input X (X²) is not causally influenced by the contounder Z. In our scenarios this is not generally true. For example, under color change, the entire observed image X changes. Still, we show that the notion of a counterfactual invariant predictor exists. Hence, the definition of Veitch et al. (202T] Lemma 3.1) of counterfactually invariant predictor that requires a segment of X to not causally depend on Z, fundamental result of their work, unfortunately does not apply to our setting (since X may have no such segment).
A.4 MNIST-(3, 4) EXPERIMENTS WITH FINITE TRANSFORMATION GROUPS
We test our proposed method on out-of-dee distribuutonn tasks on images where the equivalence relations (symmetries) are provided as transformation groups (e.g., 90" rotations). We use the MNIST-(3, 4) (colored) dataset (Mouli & Ribeiro 202T) that only contains digits 3 and 4, and follow their experi- mental setup. MNIST-(3, 4) is used to avoid any confounding factors while testing if the proposed method can learn the correct invariances, not for any practical considerations (c.g., rotated 6 is a and would interfere with some experiments, etc.).
We consider equivalence relations obtained from 3 different transformation groups: rotations by 90 (denoted Gya)) vertically flipping the image (denoted Gv-ntp). and permuting the RGB color channels of the image (denoted Gan)). The corresponding equivalence relations are lumpable (Definition ( with respect the transformations in the other two groups in almost all the cases. Only exception
15

---

Published as a conference paper at ICLR 2022
Table Results for different function classes on the MNIST-(3,- 4] classification task with frot, col, v D Ø, i.c., task is invariant to groups (D) and sensitive to none (D), R(F), COMP(F D) and S D) are as discussed Section[4.2 Bold values indicate the function class chosen by GES method with the proposed scoring criterion. Test accuracy is computed on the extrapolated dataset after shifting the distribution of RE(U))
We see that the S(F, D) loss selects the correct model class in training.
Model class
R(F)
+ +COMP(F,D)
+ +NLL(FF,) D)
S(F, 2))
Train Acc
Test Acc
Fo
6639.310
0.013
6646.324
100.00 (0.00)
48.38 ( (5.22)
F Flvlipt
6639.241
0.079
6642.320
100.00 (0.00)
47.08 ( (5.34)
F Flcol)
3
6639.241
0.029
6642.270
100.00 (.00)
53.92 (2.47)
F vool.
1
6639.241 241
0.099
6640.340
100.00 (0.00)
53.15 1.83)
F (1o0))
3
6639.241
0.037
6642.278
100.00 (0.00)
53.06 (10.00)
F (roty
6639.241
0.580
6640.821
100.00 (0.01)
54.86 (13.60)
F [rot,col)
1
6639.241
0.043
6640.284
100.00 (0.00)
90.29 6.76)
0
6639.241
0.210
6639.451
100.00 (0.00)
92.02 2.99)
Table 3: Results for different function classes on the MNIST-(3, 4] classification task with 13 {rot, vflip), ID
R(FF).CMPP(FF COMP(F, D) and (F, D) are as discussed in Section 4.2 Bold values indicate the function class chosen by GES method with the proposed scoring criterion. Test accuracy is computed on the extrapolated dataset after shifting the distribution of ((U))
fcol), i.e., task is invariant to rotation and vertical flip groups (ID but sensitive to color (D). R(F),
We see that the S(F, D))
loss selects the correct model class in training.
Model class
R(F)
COMP(F,
NNL((FF))
S(F,))
Train Ace
Test Acc
Fo
7
6639.241
0,010
6646.251
100.00 ( (0.00)
54.79 ( (0.4))
F F(smin)
3
6639.241
0.012
6642,253
100.00 ( (0.00)
55.05 ( 1.56)
F(col)
3
6639.240
8269.480
14911.720
41.98 ( (5.79)
18.81 ( (2.94)
F F(ep)))llip)
1
6639.241
8275.716
14915.957
42.71 ( (4.07)
18.62 (2.25)
F F(roa)
3
6638.946
0.132
6642.078
100.00 0.00)
91.40 33.19)
F F(ro))llip)
1
6638.428
0.504
6639.932
100.00 ( 0.00)
92.32 (1.84)
F ((oo).col)
1
6639.241
8412.954
15053.194
37.20 1.97)
29.25 ( (5.18)
F f(oo
0
6639.239
8389.719
15028.958
38.01 ( (2.02)
29.98 (3.96)
the equivalence relation <vlippp which is not lumpable with respect to the transformations in Grat Consequently, we do not consider a task with invariance to vertical flip alone. We test our method on the same classification tasks proposed by Mouli & Ribeiro (202T) where each task represents the case where the target Y has different invariances, i.e., invariant to all three groups, to two, to one, invariant to none (the task is sensitive to the remaining groups).
We use the VGG architecture (Simonyan & Zisserman, 2014) for image classification and construct collection of function classes :== FFs : S = (rot, col, v-flip)) corresponding to various invariant representations. For example, F foo),cool) is space of functions (CNNs) that are G-invariant to the rotation and color-permutation groups (Gmu and Geat), and Føz is the space of functions with no invariance (standard CNN).
Results. Our results are shown in Tables to 5o for the four tasks respectively where the label is (i) invariant to all three groups, (ii) invariant only rotation and vertical flips, (iii) invariant to color- permutation, and (iv) invariant to none. We show the values for R(F), COMP D) and S(F, D) as discussed in Section 4.2, Bold values in the tables indicate the function class chosen by GES method with the proposed scoring criterion (minimizing S(F, D)). Test accuracy is computed on the extrapolated dataset after shifting the distribution of P((U))e)) (i.e., by applying the transformations that the label is invariant to).
In Tables 2 and 3 achieves the best OOD test accuracy. In Tables 4 and [S] the method is excessively invariant (to vertical flip) but still achieves within 1% of the best OOD test accuracy. The OOD test accuracy of
that the proposed method selects the correct model class in training and
16

---

Published as a conference paper at ICLR 2022
Table 4: Results for different function classes on the MNIST-(3, 4) classification task with D [col), D frot, vflip), i.c., task is invariant color (C) but sensitive to rotation and vertical flips (D), R(F), COMP(F. D) and S D) are as discussed Section[4.2 Bold values indicate the function class chosen by GES method with the proposed scoring criterion. Test accuracy is computed on the extrapolated dataset after shifting the distribution of P(UU) We see that the (FF D) loss selects model that is excessively invariant in training. but the test accuracy is not that much penalized by the extra invariance (vertical flips).
Model class
R(F)
COMP(F,2) D)
+NLL(F,2)
S(F,D) D)
Train Acc
Test Acc
0
7
6639.241
2.395
6648.636
100.00 ( (0.01)
16.87 (5,88)
F(vtli))
3
6639.233
5,370
6647.603
99.99 ( (0.05)
15.71 ( (5,53)
F [col))
3
6639.196
2.315
6644.512
100.00 ( (0.00)
97.28 (0,28)
F (lep)
1
6639.240
3.098
6643.337
100.00 ( (..00
96.82 0.54)
F ((ox))
3
6639.228
5296.755
11938.984
56.17 (3.90)
6.20 (086)
F (roo..ffip)
1
6639.221
5325.008
11965.228
55.96 5.39)
7.24 (1.48)
F (oo)
1
6639.218
5322.015
11962.233
56.14 (3.31)
47.98 (1.44)
F y(oip
0
6639.230
5342.805
11982.035
55.32 (3.80)
49.25 (3.09)
Table 5: Results for different function classes on the MNIST-(3, 4) classification task with Ø frot, col, vflip), i.e. task is sensitive to all three groups (LD) and insensitive to none (D). R(F). COMP(F, D) and S(F, D) are as discussed in Section 4.2 Bold values indicate the function class chosen by GES method with the proposed scoring criterion. Test accuracy is computed on the extrapolated dataset after shifting the distribution of P((U))eD) We see that the S(F, D) loss selects model that excessively invariant in training, but the test accuracy is not that much penalized by the extra invariance (vertical flip).
Model class
R(F)
COMP(F,D)
(NL((F,D)
S(F,D)
Train Ace
Test Acc
Fo
7
6639.165
1.195
6647.360
100.00 (0.00)
96.00 (0.60)
F(vmli)
3
6639.117
3.548
6645.665
100.00 ( 0.00)
95.18 0..45)
F (col)
3
6639.192
7536.167
14178.359
58.77 (3.34)
32.45 ( (2.18)
F ((ol.ytlip)
1
6639.184
7902.462
14542.645
52.50 ( 7..4)
31.21 ( (2,48)
1
6639.088
13628.356
20268.443
23.78 (2.25)
15.93 ( (0.71)
F(ro)
3
6639.153
5259.957
11902.110
58.12 ( (4.05)
47.23 ( (189)
F F(oo).llip)
1
6639.827
5267.771
11908.598
57.13 ( 1.38)
47.57 (2.15)
F F(moreot,yllp))
0
6639.055
13705.123
20344.178
22.97 (3.32)
16.13 (2.22)
standard CNN with no invariance (Fz) is typically very low except in Table sensitivity to all groups is required. We can also see the importance of R(FF) for tie-breaking in these experiments. As discussed in Section 4.2 COMP(F, D) is unable distinguish between the different function classes because the training data contains a single example per equivalence class (see Figure
A.5 CIFARIO EXPERIMENTS WITH INFINITE/NONGRON TRANSFORMATION SETS
In this section, we test our proposed method on out-of-distribution tasks on CIFARIO im- ages (Krizhevsky et al. 2009) where the equivalence relations are provided as infinite sets of transformations that may not form a group. We used (a) arbitrary rotation transformations over an image (denoted Tro)). and (b) shifting the hue of an image (denoted Toa)). Note that for bounded image, arbitrary rotation is not group due to cropping. Further, transformations from the respective sets commute with each other, and hence, the lumpability condition satisfied (Definition 2 for the corresponding equivalence relations.
We tested our method on 2 classification tasks: (i) invariant to both sets of transformations (arbitrary rotations and hue shifts), and (ii) invariant to arbitrary rotations, but sensitive to hue shifts. As before, we use the VGG architecture (Simonyan & Zisserman 2014) for image classification and construct a collection of function classes 3 := (Fss S rott, ) corresponding to the various invariant representations. We use data augmentation to construct these invariant representations (this is possible since the lumpability condition holds). For example, F(ror.ool) refers to CNNs that were trained by
17

---

Published as a conference paper at ICLR 2022
Table 6: Results for different function classes the CIFARIO classification task with two sets of transformations (transformations that not form groups) on images: arbirrary rotations (with cropping due rotation) and arbitrary hue shifts. The task is invariant to both sets of transformations (DD and sensitive to none (D)). R(F). COMP(F, D) and S D) are as discussed Section 4.2 Bold values indicate
function class chosen by GES method with the proposed scoring criterion. Test accuracy is computed on the extrapolated dataset after shifting the distribution of P((U))eDD) We see that the S(F, D) loss selects the correct model class in training.
Model class R(F)
+ COMP(FF, D)
+ +NLL(F,D)
= S(F,
Train Acc
Test Acc
FB
27725.875
17496.615
45225.490
85.60
21.48
F(col)
27716.947
22715.956
50433.903
81.28
21,85
F (rot)
-60894. 145
20365.793
-00527.352
82.65
45.12
(rot.col)
-66262.157
23538.768
-42723.390
79.99
69.35
Table 7: Results for different function classes on the CIFARIO classification task with two sets of transformations (transformations that do not form groups) images: arbitrary angle rotations (with cropping due rotation) arbitrary lue shifts. The task invariant to arbitrary rotations of the image (D) but sensitive color (D). R(F), COMP(F, D) and S(F, D) are as discussed in Section 4.2 Bold values indicate the function class chosen by GES method with the proposed scoring criterion. Test accuracy is computed on extrapolated dataset after shifting the distribution of ((())) We see that the S(F, D) loss selects the correct model
class in training.
Model class
R(F) + COMP(F,
NLL((F,))
S(F,D)
Train Acc
Test Acc
F0
27724.256
42166.993
69894.250
64.37
17.16
Fluol)
27715.023
49744.680
77460.703
42.69
10.91
F (rod)
-91370.533
46218.086
-45151.447
61.77
52.60
F (no.col))
-92009.184
50246.908
-41762.276
41.45
35.56
augmenting both arbitrarily rotated images and hue-shifted images. Once again, Fg is the space of functions with no invariance (standard CNN with no data augmentations).
Results. We show in Tables 6 and 7 that method is able find the correct invariance and achieves the best OOD test accuracy whereas the standard CNN with no invariance has poor OOD performance.
A.6 MORE ON LUMPABILITY (DEFINITION 2
We show that the lumpability condition of Definition i equivalent to the normal subgroup condition of Mouli & Ribeiro (202T Theorem when the given equivalence relations are obtained from trans- formation groups However, unlike the normal subgroup condition, the lumpability condition applies in the general case when the equivalence relations are not necessarily obtained via transformation groups.
Proposition 1. Let ~G, and ~G, be two equivalence relations on the input space X obtained as orbits under transformation groups G1 and G2 respectively, i.e., for 1,2, x ~G, x' iff there exists {(() G; with x' = {()) æ. Then, ~G, is lumpable with respect to the transformations G2 (Defiittion) 2 and only if G normal subgroup of Gı G2, where is the join operator.
Proof. First, given ~G, lumpable with respect to G2, we wish to prove that G1 is a normal subgroup of Gi G2. By definition of the join operator transformation groups, G subgroup of G1 v G2-
Next, consider equivalence class [æ]G, X/ ~ Then, by the lumpability of ~a, with respect to G2, have that for all {(2) G2, there exists [æ'lo, with x* [[=],, {(?) x* [æ]]a, In other words, each ((2) maps all points in equivalence class [ to another equivalence class
18

---

Published as a conference paper at ICLR 2022
[ Specifically, t(2) maps [ale, to oz [al]ar Thus, set x' = +(2) z without loss generality.
Then, for all y(2) G2, we have from the lumpability condition that
x E [ = ((2) x* [1(2) m]
Recall from the definition of the equivalence class derived from a transformation group (i.e., the orbit) that x* [a]G, means that there exists transformation {(1 G1 that maps æ to x", i.e.. xx z(1) æ. Similarly, ((2) x* [t(2) a|G, means that there exists another transformation F(I)
such that {(2) x z(l) x(2) x.
Equation 99) then becomes
(+(*) G1 s.t. x* = 111) = 3800 Gr s.t. z(2) x* = (12) ((2)) ox, (10)
for {(2) G2-
Since Equation (10) holds for all x* E [x]c, and for all X, we have Vp(2) E G2, (t()
() G1 such that,
e (1) ((1) (2)
which implies that G₁ is normal subgroup of G G2. reversing the steps of the above proof.
The converse can be proved trivially by
19


Reviews:
[{"review_id": "tSgDs6DEBo7", "reviewer": "Reviewer_XTXH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThis paper does a good job of describing an interesting and important problem, invariance to OOD symmetry transformations, and motivates why existing approaches may not work well. The approach novel as far as I'm aware, and clearly describes relevant concepts such as defining what we would want our OOD-transformation invariant representations to satisfy and how learning them is linked to causal structure discovery.\n\nWeaknesses:\n- The method appears to identify which of some set of transformations one should be invariant to (and learn correspondingly invariant representations). But we must first have prepared a collection of all possible symmetry transformations, which seems like a limitation of the method. Additionally, is there a trade-off where considering more symmetry transformations makes the method slower?\n-  The experiments and comparisons are relatively minimal and are only in a toy environment. From the description of the method I assume there are computational difficulties in practically implementing this method for more \"real-world\" problems. The papers would be strengthened by either having larger more realistic experimental comparisons, or barring that an explanation of the practical difficulties of applying the method to larger problems and future steps that could resolve them.", "summary_of_the_paper": "This paper considers a class of out of distribution (OOD) problems where at test time there may be new symmetry transformations of the input X (i.e., they don't change the label Y). The authors explain why standard invariances learned by data augmentation may not be OOD invariant. Next, the paper presents a method for learning OOD-invariant representations through causal structure discovery. This hinges on the concept of being counterfactually invariant to the symmetry transformations that could appear at test time but don't affect Y. Next is an algorithm for discovering the structure of a causal DAG which largely revolves around deciding whether or not there is an edge U_i -> Y; this existence question corresponds to whether or not Y is invariant to the transformation U_i (IIUC).\n\nThe paper test this approach on tasks in a simple simulated physics environment.", "summary_of_the_review": "Interesting ideas with relatively toy empirical results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": {}}, {"review_id": "dYOi24Cyt9w", "reviewer": "Reviewer_RsMV", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Update**: After reading the rebuttal and the other reviews, I have decided to bump up my original score to an 8. Thank you to the authors for addressing our concerns in great detail.\n\n**Strengths**:\n- The methodology has a strong theoretical basis, and is a result of combining insight from different fields. The idea behind this approach, is in my opinion, quite elegant.\n- The paper is well-written and the work is well-placed in the literature, the illustrations are well-thought-out and facilitate understanding the method.\n\n**Weaknesses**:\n- The experimental section consists of only two simulated toy examples. While these showcase how the method is supposed to work, it remains unclear how well the method would work in a real-world, uncontrolled environment. How often are the assumptions made about the data generating process expected to hold 'in the wild'?\n\nOther comments:\n- The figures and table appear out of place. Table 1 is referenced in the Results section, but is shown two sections before without context. Figure 1 appears a bit too early in the paper (first mentioned in \"Illustrative SCM example\"), while Figure 2 appears much later (first mentioned before Figure 1, after that mentioned before Theorem 1).\n- The caption text for Figure 2a(iii) is clipped out. The subfigure is also way too small to be readable without zooming in.\n- Reference to \"Accounting for unobserved confounding in domain generalization\" appears to be duplicated.\n- page 2, Layer 1 - \"causal\" misspelled as \"casual\"\n- page 3, Symmetry transformations - Sentence starting with \"Although\" appears incomplete. I would suggest conjoining this sentence and the one before: \"... equivalence classes, although ...\".\n- page 8, Causal structure discovery, third row from the bottom: \"between distribution\" -> \"between **a** distribution\"\n- page 9, second row: add comma before \"under the assumption\"", "summary_of_the_paper": "The authors propose an approach for constructing classifiers that achieve out-of-distribution (OOD) generalization using a new learning paradigm they call _asymmetry learning_. They consider OOD tasks where the test input is obtained from the training input by applying a sequence of (random) input transformations. To obtain an invariant OOD classifier that generalizes well to both in-distribution and out-of-distribution samples, the authors introduce the concept of _counterfactual invariant representations over symmetric transformations_. They show how learning the invariant representations can be cast as a causal structure discovery task and propose a score-based (GES-based) algorithm for finding the causal directed acyclic graph (DAG) that best describes the invariances.", "summary_of_the_review": "The authors propose an interesting idea for constructing OOD classifiers starting from counterfactual invariance for symmetric transformation, an idea that is well-formulated in this paper. Despite the lack of real-world validation, I think the paper has a strong theoretical basis and is a decent contribution to the literature.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "0PqK1WvzhJ", "reviewer": "Reviewer_GzS3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "- The paper is well motivated, and examines an important problem of classifiers failing out-of-domain.\n- The paper's contributions could be significant to what is an emerging area of research. Other than [1, 2] and [3], I have not seen any other paper that offers a theoretical framing for the relationship between counterfactual invariance and OOD generalization and provides a way to achieve the same. \n- The paper flows smoothly and is easy to understand.\n- I wish the paper offered a greater discussion of prior work on counterfactual invariance as it relates to out-of-domain generalization. I hope the authors can address that in a future version. Additionally, while the authors have offered some discussion of [2] and [3], per my reading, [1] seems to offer a contradictory view (from this paper) of whether learning an invariant OOD classifier is solvable via interventional data augmentation or not. It would be great if the authors could share how one relates to the other. I'm not sure I found a convincing argument laid in this paper other than the example in Figure 1(c).\n- The experiments in the paper are on simulated tasks with limited number of variables. It is unclear how this method might work in high dimensional spaces, such as text. Though it's not necessarily a concern, I think it would be useful if the authors could comment on the same.\n\n[1] Kaushik, D., Setlur, A., Hovy, E. H., & Lipton, Z. C. Explaining the Efficacy of Counterfactually Augmented Data. ICLR 2021.\n[2] Veitch et al. (2021)\n[3] Wang and Jordan (2021)\n\nTypos and presentation: \n- Introduction Line 2: \"the task is requires\" -> \"the task requires\"\n- Break the second sentence of the first paragraph of introduction.\n- Layer 3 description of Pearl's causal hierarchy: \"X\\dagger describe an hidden variable\" -> \"X\\dagger describe a hidden variable\"\n- Your figures are blurry upon printing the paper. Please increase the font of the text in the figures.\n- Section 4.1: \"Our next results requires imposing\" -> \"Our next results require imposing\"\n- Section 4.1 under Definition 2: \"Definition 2 holds for a equivalence relation\" -> \"Definition 2 holds for an equivalence relation\"\n- Related Work should either be Section 6 or be Section 2 (right after introduction) and not be in between the theory and empirical results.\n- In justifying Assumption 1, can you provide a citation that is more recent considering the science in this area has evolved considerably since 1982?", "summary_of_the_paper": "Update\n\nI have read the author response and the updated version of this paper. I am delighted to see that the authors have incorporated my feedback and I believe this makes the paper stronger than its previous version. I have updated my scores and recommend that the paper be accepted.\n\n------------------------------------------------------------------\n\nThis paper proposes Asymmetry Learning, a new learning paradigm to obtain counterfactually invariant classifiers. If the observed covariates are a result of some transformations applied to a hidden variable, and these transformations differ between training and test datasets, a classifier may not generalize to the test set. The authors argue that when these transformations are a result of a collection of equivalence relations, finding OOD-invariant classifier boils down to finding the simplest causal model that defines the causal relationships between the labels and these symmetry transformations. To this end, the authors propose a scoring criterion to identify the simplest DAG in a DAG search space that ensures that the label is invariant of all transformations while maximizing the likelihood of the observed training set. Using their proposed scoring function, the authors employ Greedy Equivalence Search to identify the DAG with the highest score. Experiments on simulated physics tasks suggest that the method works as intended.", "summary_of_the_review": "Overall, I think the paper presents a good contribution but I do have some minor concerns that I would like the authors to address as I have mentioned above.", "strength_and_weaknesses": "", "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:

Meta-review: This paper proposes asymmetry learning for learning counterfactual classifiers, i.e. classifiers which are invariant to certain symmetry transformations w.r.t. hidden variables that differ between the training and test sets.

The reviewers universally agreed that the proposed setting, and theoretical contribution, were interesting and novel. They also praised the writing quality, but had some quibbles about the quality of the experiments, and discussion of prior work. Neither of these concerns were considered significant enough to be a barrier to acceptance, but the authors should try to improve them, if possible.
Decision: Accept (Oral)