Year: 2021

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 te  ̋X 1 not observed in training, as in training we observe T tr  ̋X 1, where X 1 is a hidden variable. This work argues that when the transformations in train T tr and test T 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 simulated physics tasks and six image classification tasks.

text: 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 te ˝X 1 not observed in training, as in training we observe T tr ˝X 1, where X 1 is a hidden variable. This work argues that when the transformations in train T tr and test T 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 simulated physics tasks and six image classification tasks.

heading: 1 INTRODUCTION
text: A significant challenge in classification tasks happens when the test distribution differs from the training distribution (i.e., the task requires out-of-distribution (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 a classifier invariant to the distribution shift can still be a data-driven task (e.g., classical domain adaptation Ben-David et al. (2007); Muandet et al. (2013); Zhao et al. (2019)). This includes cases such as invariant risk minimization (Arjovsky et al., 2019) and its generalizations (Bellot & van der Schaar, 2020), where the training data and the test data distributions overlap in a 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 pY tr, X trq, where X tr :“ T tr ˝ X:, with X: as a hidden variable with distribution P pX:q and T tr P T is a random input transformation in training T tr : X Ñ X , where t ˝ x is the application of transformation t P T on x P X . The difference between train and test is a change in input transformation with Y te :“ Y tr and X te :“ T te ˝ X:, where P pT trq ‰ P pT teq. We are interested in learning an invariant classifier that generalizes well in held out examples from the training and test distributions.
The definition of transformation matters in this task. We first seek to generalize the existing literature on transformation invariances, e.g. (Shawe-Taylor, 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 also explain why the task of learning an invariant OOD classifier is not, in general, solvable via traditional (interventional) 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., 2020)) 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. (2020)). 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, is observational (Layer 1). Traditional domain adaptation is a Layer 1 task. Note that a classifier that performs well OOD is itself a Layer 1 classifier, since it tries to predict P pY te|X teq. Layer 2: Without observations from P pX teq and/or P pY te|X teq, learning an OOD classifier requires some assumptions about the data generation process (Layers 2 or 3 assumptions). Data augmentation is traditionally an interventional task (Layer 2), with new interesting methods increasingly using causal language (Ilse et al., 2021; Teney et al., 2020). For instance, in a task predicting an image’s foreground, knowing how to act on an image in training X tr to change the background seen in training to the backgrounds seen in test X te “ T ˝X tr with a transformation T , implies we know how to predict P pY |X, dopT qq. Following the recent literature, we will define the do operator as Y pT “ tq :“ Y |dopT “ tq. Layer 3: Counterfactuals are the most challenging task. We start our description with an example. Consider a random continuous transformation T tr2 (in training) which changes to random transformation T te2 (in test). Let X
: describe a hidden variable such that X tr :“ T1 ˝ T tr2 ˝ T3 ˝ X: and X te :“ T1 ˝ T te2 ˝ T3 ˝X:, where T1 and T3 are independent continuous random transformations and P pT tr2 q ‰ P pT te2 q. Assume the target variable Y depends only onX:, T1, and T3. To counterfactually ask what would have happened to the observed input x if we had forced dopT tr2 “ t̃2q, we are inquiring about XpT tr2 “ t̃2q|X tr “ x. Note that dopT tr2 “ t̃2q does not change Y . Also note that the knowledge of X tr “ x is an indirect statement about T tr2 since P pT tr2 |X tr “ xq ‰ P pT tr2 q. That is, for x, x1 P X ,
P pXpT tr2 “ t̃2q “ x1|X tr “ xq “ ż
t P pXpT tr2 “ t̃2q “ x1|T tr2 “ t,X tr “ xqdP pT tr2 “ t|X tr “ xq. (1)
Equation (1) 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 a generalization of transformation groups via symmetry transformations tied to equivalence classes that removes the requirement of invertible transformations common in definitions using transformation groups.
2. We introduce the concept of counterfactual invariant representations for symmetry transformations and show how it can be described as a counterfactual task for causal structure discovery.
3. Finally, we introduce asymmetry learning, which describes a representation regularization that, under a set of assumptions, learns the correct counterfactual invariant OOD classifier.

heading: 2 SYMMETRIES AND TRANSFORMATIONS
text: 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, a square is symmetric with respect to rotations. The notion of symmetry however is not restricted to geometric notions. In general, we can define a mathematical object as 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 we first need to define what we 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.
We define an input symmetry in a space X with at least two elements as an equivalence relation „. An equivalence relation in X is a binary relation „ such that for all a, b, c P X , we have (i) a „ a,
(ii) a „ b ðñ b „ a, and (iii) (a „ b and b „ cq ùñ a „ c. Equivalence relations allow us to define equivalent objects in X : a „ b means a is equivalent to b. The set of all objects equivalent to some a P X is called the equivalence class of a, defined as ras :“ tx P X : x „ au. Note that one can define m ě 2 equivalence relations on the same input space. The equivalence class of x with respect to equivalence relation k is denoted rxspkq, k “ 1, . . . ,m. Two inputs a, b P X might be equivalent under one equivalence relation „1, but not equivalent under a different equivalence relation „2, that is, we can have both b P rasp1q and b R rasp2q. Still, even in this last case it is possible that a is equivalent to some other input c ‰ b in both equivalence relations, i.e., it is possible Dc P X , c ‰ a, s.t. c P rasp1q X rasp2q. We denote the collection of equivalence classes of X under the equivalence relation „k as the quotient space X { „k:“ trxspkq | x P X u. Transformation group example. Consider the bijective transformations t : X Ñ X of a transformation group G, t P G. We now define an equivalence relation over G as t ˝ x „G x for all t P G. The equivalence class rxspGq is x’s orbit defined as rxspGq :“ tx1 : Dt P G,x1 “ t ˝ xu. For example, if G is the group that permutes the elements of vectors in R3, then p1, 2, 3q „G p2, 1, 3q. Property functions example. Another way of deriving an equivalence relation is via functions of the input space z : X Ñ Rp, where the output zpxq is a particular property of the vector x P X . For example, given an observation of length T from a dynamical system, x P RdˆT , a possible property function could be zenergyp¨q that computes the energy of the dynamical system. Assuming there are m known properties z1, . . . , zm with zi : X Ñ Rpi , we can construct corresponding equivalence relations „1, . . . ,„m such that for any x,x1 P X , x „i x1 if zjpxq “ zjpx1q,@j ‰ i. In words, two inputs are equivalent under „i if they have the same properties for all zj , 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 a 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 @t P T ,@x P X , t ˝x „ x. We call T the set of symmetry transformations of „. Similar to transformations groups, T always has the identity transformation tid ˝ x “ x, but in contrast, all the transformations in T need not be bijective. Join of equivalence relations. Similar to how two groups can be joined to form a larger group, two equivalence relations can be joined to form a coarser equivalence relation. Given two equivalence relations, „1 and „2, their join „1 _ „2 is defined as: for all x,x1, xp„1 _ „2qx1 if and only if there exists a chain of equivalence relations x „k1 x1, . . . , xh´1 „kh x1 with all kj P t1, 2u. It is easy to check that „1 _ „2 is an equivalence relation. We are now ready to define a general causal model that defines the training and test distributions in our setting.

heading: 3 SCM FOR SYMMETRY-BASED OOD TASKS
text: Let X ,Y denote the input and output spaces respectively. We define our general structural causal model (SCM) as follows. We define X: P X as the unobserved canonically ordered input
X: :“ gpUuq , (2)
with Uu a background random variable and g : Uu Ñ X is a measurable map. This definition is general enough to define any task.
There are m possible symmetries given in the form of equivalence relations „1, . . . ,„m over the input space X . Let T pkq denote a set of symmetric transformations t on X corresponding to the equivalence relation „k, 1 ď k ď m. In other words, for all x P X and t P T pkq, we have pt ˝ xq „k x. Similarly, let T be the set of all symmetric transformations with respect to the join equivalence relation „1,...,m”„1 _ . . ._ „m. We can think of transformation t P T as a path x t pk1q ÝÝÝÑ x1 ¨ ¨ ¨xh´1
tpkhqÝÝÝÑ xh that starts at x, applies a transformation tpk1q P T pk1q to get x1 P rxspk1q, and so on until it stops and outputs a value xh, h ě 1. Let U1, . . . , Um be independent background variables associated with the m symmetries, where Ui P Ui, i “ 1, . . . ,m. These background variables together select a function tpU1, . . . , Umq from the set T as follows. Each Uk independently selects a countable sequence of transformations
t pkq 1,Uk , t pkq 2,Uk , . . . P T pkq. Then, tpU1, . . . , Umq is defined by interleaving these transformations tpU1, . . . , Umq :“ ptp1q1,U1 ˝ ¨ ¨ ¨ ˝ t pmq 1,Um q˝ ¨ ¨ ¨ ˝ ptp1qr,U1 ˝ ¨ ¨ ¨ ˝ t pmq r,Um
q˝ ¨ ¨ ¨ to construct the path described above. Since T p1q, T p2q, . . . contain the identity transformation, tpU1, . . . , Umq can be described by a finite sequences of transformations. The observed X is the result of a transformation of X:
X :“ tpU1, . . . , Umq ˝X: . (3)
Finally, the label Y is defined as a function of the untransformed canonical input X: as
Y :“ hpX:, pUiqiPD, UY q , (4)
where D Ď t1, . . . ,mu is unknown. This means that Y is not invariant with respect to equivalence relations „i, i P D, i.e., examples x and x1 P rxspiq can have different labels. A distribution over the variables Uu, tUiumi“1, UY entails a joint distribution P pX,Y q over the observed variables.
Illustrative SCM example. Figure 1 illustrates our data generation process. The training data Figure 1(a) has X: defined as a centered upright brown rod (i.e., X: is deterministic). The label Y is defined by the rotation transformations T rot “ tT rot0˝ , T rot90˝u. The image can also be horizontally translated by t´5, 0, 5u units via transformations T trans “ tT trans´5 , T trans0 , T trans`5 u (only 0 and `5 translations are depicted), but Y does not depend on these horizontal translations. The transformations applied to X: are randomly chosen via Urot and Utrans, which are two bidimensional vectors indexing a sequence four transformations that interleave rotations and translations (see Figure 1). A representation that counts the number of brown pixels in the green shaded area of X tr is enough to achieve 100% accuracy in the training distribution. We formally define OOD distribution shifts next using Figure 1 for illustration.
OOD distribution shift. Let sD “ t1, . . . ,muzD be the complement of the set of symmetry relations D that Y depends on. We define the OOD distribution shift between train and
test as a shift in the distribution of P ppUiqiPsDq, influencing the distribution of input transformations in Equation (3), which in turn can shift the distributions P pX trq, P pY tr|X trq, P pY tr, X trq to P pX teq, P pY te|X teq, P pY te, X teq respectively. Since X does not causally affect Y in our structural causal model (Equation (4)), changes in input transformations are able to shift P pY |Xq. For example, in Figure 1(b) the test data (only a single example shown) could suffer an OOD shift due to a different distribution over P pUtransq 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 tr, will achieve poor accuracy in the test inputs X te.
Learning OOD classifiers. Equation (4) shows that the label Y is invariant to changes in the distribution of pUiqiPsD in the test distribution, but we do not know sD. Hence, if our representation of X is invariant to changes in the distribution of pUiqiPsD, we will be able to perform the OOD task.

heading: 4 ASYMMETRY LEARNING & FINDING THE RIGHT REPRESENTATION SYMMETRY FOR THE OOD TASK

heading: 4.1 FINDING OOD-INVARIANT REPRESENTATIONS AS CAUSAL STRUCTURE DISCOVERY
text: We first define the process of finding an OOD invariant representations for the symmetries t„iuiPsD our classifier should be invariant to in the test data. Since Y does not depend on tUiuiPsD, we will make a representation of X that is invariant to transformations driven by tUiuiPsD. Definition 1 introduces the concept of counterfactual invariance for symmetry transformations. We note that our Definition 1 of counterfactual invariance is equivalent to the parallel work of Veitch et al. (2021, Definition 1.1) but it more clearly states the role of the training and test data in the definition of counterfactual representation invariance. We need this clearer statement to avoid likely mistakes that could come from the more ambiguous notation of Veitch et al. (2021, Definition 1.1). Definition 1 (Counterfactual-invariant representations for symmetric transformations). Assume the SCM defined in Equations (2) to (4). A representation Γi : X Ñ Rd, d ě 1, is counterfactualinvariant to the transformations T1,Ui , T2,Ui , . . . of equivalence relation „i, 1 ď i ď m, if
Γipxq “ ΓipXpUi “ ũiq|X “ xq almost everywhere, @ũi P supppU tei q,@x P supppX trq, where supppAq is the support of random variable A. A representation ΓS : X Ñ Rd, d ě 1, is counterfactual-invariant to a subset S Ď t1, . . . ,mu if it is jointly counterfactual-invariant to the transformation indices tUjujPS of equivalence relations t„jujPS.
We refer the reader to Equation (1) for the relationship between the counterfactual variables XpUi “ ũq|Ui “ u and XpUi “ ũq|X “ x. Figure 1(d) illustrates why counterfactual language is important for our task: It states that given an input X tr “ x we need to know how it would have been different if we had chosen a different distribution P pUtransq resulting in a different sequence of transformations T1,Utrans , T2,Utrans . From Figure 1(c) it is clear that we cannot simply data-augment our training data with translations, since we would think that counting brown pixels in the green shaded area is an invariant representation for Utrans.
Up until now we have not imposed restrictions on the types of transformations T piq, i “ 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 { „i is the set of equivalence classes of X with respect to equivalence relation „i, i “ 1, . . . ,m. Let rxspiq P X { „i be the equivalence class of x P X with respect to equivalence relation „i. Then, X { „i is said to be lumpable with respect to a transformation set T if @rxspiq P X { „i and @t P T with t not identity,
Drx1spiq P pX { „iqztrxspiqu s.t. x˚ P rxspiq ùñ t ˝ x˚ P rx1spiq.
In words, if the lumpability condition in Definition 2 holds for an equivalence relation„i with respect to a set of transformations T , then every transformation in T maps all points within an equivalence class rxspiq P X { „ to points in a strictly different equivalence class rx1spiq P pX { „qztrxspiqu. To illustrate the lumpability condition, consider two transformation groups G1 and G2 whose transformations commute, i.e., @pt1, t2q P G1 ˆG2, t1 ˝ t2 “ t2 ˝ t1. Then the equivalence classes
imposed by Gi, i.e., the orbits rxspiq “ tti ˝ x : @ti P Giu, are lumpable with respect to the transformations Gj , for i, j P t1, 2u and j ‰ i. Figure 2a(i) shows our structural causal graph where an edge Ui Ñ Y exists only if i P D. Then, we use the definition of lumpability to prove that, under certain conditions, a most-expressive counterfactual invariant representation Γi allows us to identify if there is no edge Ui Ñ Y in the causal DAG. Theorem 1 (Counterfactual invariance & causal DAG identification). Let X { „i be lumpable given every T pjq, j ‰ i as in Definition 2. Then, the structural causal DAG implied by Equations (2) to (4) (depicted in Figure 2a(i)) does not contain the edge Ui Ñ Y iff
|P pY |ΓipXq, UY q ´ P pY |X,UY q|TV “ 0, (5)
@P pX:q,@P pU1q, . . . ,@P pUmq, where Γi is a most-expressive representation that is counterfactually-invariant to Ui (Definition 1).
The proof is in the Appendix. We now use Figure 2a(ii) to describe the result in Theorem 1. We first note that the representation Γ
sD depicted in the figure is counterfactual invariant to sD, and hence also counterfactual invariant to k P sD. Next we see that since the representation Γ
sD is counterfactual invariant to Uk, there is no arrow Uk Ñ ΓsDpXq in Figure 2a(ii). If there is no arrow Uk Ñ Y , the missing arrows from Uk to ΓsDpXq will have no influence in the ability of ΓsDpXq to predict Y , assuming Γ
sD is most-expressive. If there is an arrow Uk Ñ Y , cutting the arrow Uk Ñ ΓsDpXq creates a loss in predictive performance from Γ
sDpXq to Y for some distribution of the background and observable variables. If Γ
sDpXq never loses any predictive power over Y for any distribution of the background and observable variables, then there is no arrow Uk Ñ Y . Assumption 1 (Asymmetry learning training data). In asymmetry learning we assume that every X { „i, i P t1, . . . ,mu is lumpable given T pjq, j ‰ i, and that in a large training dataset sampled from pY tr, X trq, an arrow Uj Ñ Y in the causal DAG of Figure 2a(i), j P t1, . . . ,mu, contains observations of tUjujPD that violate Equation (5). Hence, if Equation (5) holds for some i P t1, . . . ,mu in this dataset, we can conclude that there is no arrow Ui Ñ Y in the true causal DAG. See Appendix A for a justification of this assumption.
Next we use Assumption 1 and the previous results to search for the right OOD invariance.

heading: 4.2 CAUSAL STRUCTURE DISCOVERY OF RELEVANT SYMMETRIES
text: We need a general procedure for obtaining the unknown set D, which is equivalent to finding all transformations indices tUiuiPD Ď tU1, . . . , Umu 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., Heinze-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 Ui, i “ 1, . . . ,m) while also maximizing the likelihood of the observed data. Accordingly, we take the score-based causal discovery approach (Chickering (2002); Huang et al. (2018)) that assigns scores to each allowed DAG based on the training data and the complexity of the DAG to find
a minimal causal structure that fits the training data. This idea is visualized in Figure 2a(iii) 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 Ui Ñ Y, i P t1, . . . ,mu. Next, we describe a scoring criterion that uses Theorem 1 to effectively use counterfactual-invariant representations and assigns scores to 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 “ tpxpiq,ypiquntri“1 under Assumption 1 for a classification task with C classes. Theorem 1 shows that there is a correspondence between a causal structure without the edge Ui Ñ Y and a predictive probability gap between the original input and a most-expressive representation Γi that is counterfactually-invariant to Ui. Thus, under Assumption 1, we can represent the causal search from Figure 2a(iii) in terms of a search over counterfactually-invariant representation function classes as shown in Figures 2a(iii) and 2b. Formally, we are given a collection of function classes F :“ tFS : S Ď t1, . . . ,muu,where FS is a family of functions ΓS that are counterfactuallyinvariant to all Ui, i P S (Definition 1). We wish to score each of the function classes FS P 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 F and the training dataset D, MDL finds the function class FS P 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 to be optimal (Shtarkov, 1987). NML code is computed as follows
LnmlpFS,Dq “ ´LpFS|Dq ` COMPpFS,Dq , (6)
where LpFS|Dq “ supΓSPFS řntr i“1 logP pypiq|ΓSpxpiqqq is the maximum log-likelihood of FS given the data and
COMPpFS,Dq “ log
»
—
—
—
–
ÿ
yp1q,...,ypn trq: ypiqPt0,...,Cu
sup ΓSPFS
ntr ź i“1 P pypiq|ΓSpxpiqqq
fi
ffi
ffi
ffi
fl
, (7)
measures the complexity of the function class FS by computing how well it can represent different label distributions for the given inputs txpiquntri“1 in training. We can estimate the combinatorial sum in Equation (7) by uniformly sampling random labels for all the training examples.
Since COMPpFS,Dq is computed using the training data, it may underestimate the complexity of function classes if, for instance, all the training examples are generated with Ui “ ui. Then, Ftiu and FH are given the same score even though Ftiu is clearly more invariant and thus, a simpler function class. This can happen in practice if, say, all images are upright in training with no rotations applied; both rotation-invariant and rotation-sensitive function classes get the same complexity score.
In order to break the above ties of our COMP score, asymmetry learning adds an additional term to 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) and useRpFSq :“ |tF 1 : F 1 P F ,F 1 ą FSu|, the number of function classes that are higher in the partial order than FS, as the tie-breaking term. For example, in figure RpFt1uq “ |tFt1,2u,Ft1,3u,Ft1,2,3uu| “ 3. We define the final score of each function class FS P F as
SpFS,Dq “ LnmlpFS,Dq `RpFSq . (8)
The score in Equation (8) can be minimized by a score-based 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 a 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 Ui Ñ Y, i P t1, . . . ,mu. In the first phase, GES adds these edges one at a time 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 is optimal in the large sample limit if the scoring function is locally consistent.

heading: 5 RESULTS
text: Pendulum task description. We evaluate the proposed method in a simulated classification task. Our input x is a motion vector over time pθt, dθtdt q T t“1 of a simple pendulum of an unknown length l after it is dropped from some initial angle θ0 with dθ0dt “ 0. After an 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: z1 : X Ñ R which computes the initial potential energy of the system and z2 : X Ñ R 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,x1 are equivalent with respect to „1, i.e., x „1 x1, if they have the same time of collision, z2pxq “ z2px1q. Then T p1q 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 θ0) while keeping the time of collision same. Similarly, x „2 x1 if their respective potential energies are the same and transformations in T p2q 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 T p2q and vice versa (Definition 2). Thus, by Theorem 1, we can use predictive performance of counterfactual-invariant 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 z1pxq, i.e, D “ t1u. Second, if the motion of the pendulum is damped, then Y depends on both z1pxq and z2pxq, i.e., D “ t1, 2u. The extrapolation test data is generated by shifting the distribution of the background variables tUiuiPsD. 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-invariant representations FS corresponding to each possible value of S Ĺ t1, 2u, where every ΓS P FS is invariant to tUiuiPS. For example, Ft1u is a family of feedforward neural networks that only take z2pxq as input, i.e., invariant to z1pxq, whereas FH is a sequence model (e.g., LSTM) with no invariance. Table 1 reports the estimated complexity {COMPpF ,Dq and the final scores SpF ,Dq for the different function classes for the two tasks. The bold values indicate the function class chosen by the GES algorithm. When D “ t1u, the greedy search stops after adding the edge U1 Ñ Y as adding the second edge U2 Ñ Y only worsens (increases) the score. When D “ t1, 2u, the greedy search is able to improve the score by adding both edges, first U1 Ñ Y and then U2 Ñ 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).

heading: 6 RELATED WORK
text: Counterfactual inference and invariances. Several recent works such as Invariant Causal Prediction (Peters et al., 2015; Heinze-Deml et al., 2018) and Invariant Risk Minimization methods (Arjovsky et al., 2019; Bellot & van der Schaar, 2020) learn representations that are invariant across multiple environments such that they generalize to new environments. 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 fpXq when X has a single parent Z and provide conditions such predictors must satisfy over the observed distribution (given an SCM). We generalize their definition for our setting where X has more than one parent in the causal graph, corresponding to different symmetries. Kaushik et al. (2020; 2021) propose counterfactual data augmentation for text datasets but they either require a fully-specified toy SCM or rely on humans-in-the-loop to 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 variables assuming that these are observed for every example in the data. In our setting, the transformation variables Ui responsible for generating the observed X are unobserved. A more 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 et al., 2013; Quionero-Candela et al., 2009; Rojas-Carulla et al., 2018; Shimodaira, 2000; Zhang et al., 2015) and others) consider observed or known shifts in the data distribution, for instance, given the test distribution P pX teq, rather than counterfactual questions. Instead, counterfactual inference accounts for hypothetical interventions that are never observed.
Causal structure discovery. The methods for causal structure discovery can be broadly classified into two categories. Constraint-based approaches (e.g., Spirtes et al. (2001); Sun et 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 (e.g., Chickering (2002); Huang et al. (2018); Ding et al. (2020); Zhu et al. (2020)) assign scores to 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., 2021) 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-breaking. Goudet et al. (2017) minimize the divergence between a distribution generated by a learnt causal DAG and the observed data distribution; however the method is limited to orienting edges over observed variables, whereas our transformation variables Ui are unobserved.
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 data-augmentation (Chen et al., 2020) 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 et 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 we show can be solved only under certain conditions. Mouli & Ribeiro (2021) 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. (2021) 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 to discover which equivalence relations (transformations thereof) affect the label.

heading: 7 CONCLUSIONS
text: This work considered an out-of-distribution (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 a causal structure discovery task and show that, under certain conditions, we can use the predictive performance of counterfactual-invariant representations on the observational data to predict whether an edge exists in the causal DAG (Theorem 1). We then proposed an MDL-based scoring for this causal structure discovery. Finally, we test our approach in two simulated physics tasks and six image classification tasks.

heading: A APPENDIX
text: A.1 JUSTIFICATION FOR ASSUMPTION 1.
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 D given F without ever seeing any such examples (Sidman et al., 1982). That is, if given D, action F produces a treat, the child assumes that given F, action D 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 can provide valuable information when they are 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 (Counterfactual invariance & causal DAG identification). Let X { „i be lumpable given every T pjq, j ‰ i as in Definition 2. Then, the structural causal DAG implied by Equations (2) to (4) (depicted in Figure 2a(i)) does not contain the edge Ui Ñ Y iff
|P pY |ΓipXq, UY q ´ P pY |X,UY q|TV “ 0, (5)
@P pX:q,@P pU1q, . . . ,@P pUmq, where Γi is a most-expressive representation that is counterfactually-invariant to Ui (Definition 1).
Proof. Notation (following Equation (3)): The observed input X is X :“ tpU1, . . . , Ui´1, ui, Ui`1, . . . , Umq ˝ X: where tpU1, . . . , Umq is obtained by interleaving the transformation sequences from each individual U1, . . . , Um and we have set Ui “ ui. Necessity: We wish to show that if the SCM does not contain edge Ui Ñ Y , then Equation (5) holds for all P pX:q, P pU1q, . . . , P pUmq. By this assumption, Y outputs the same label for any value of Ui. Consider the collection of equivalence classes X { „i. By the lumpability condition of Definition 2, all transformations tpjq P T pjq, j ‰ i, map all points in one equivalence class of„i to points in a different one. On the other hand, all transformations tpiq P T piq map points to other points within the same equivalence class under „i. Now, consider the equivalence class of X after all the transformations have been applied to X:. The equivalence class of X “ tpU1, . . . , Ui´1, ui, Ui`1, . . . , Umq ˝X: is the same as that of X˚ “ tpU1, . . . , Ui´1, uidi , Ui`1, . . . , Umq ˝X: where Ui “ uidi always selects identity transformations. This is because changing ui to uidi only impacts the transformations chosen from T piq, and these transformations do not change the equivalence class under „i. Thus, we have shown that we reach the same equivalence class „i for both X and X˚. Now let Γi be a most-expressive representation that is counterfactually invariant to Ui (Definition 1). By definition, ΓipXq “ ΓiptpU1, . . . , ui, . . . , Umq ˝ X:q “ ΓiptpU1, . . . , uidi , . . . Umq ˝ X:q “ ΓipX˚q almost everywhere. But since the equivalence classes under „i of X and X˚ are the same and hence have the same label always (by assumption that Ui Ñ Y does not exist), there is no loss of information incurred by Γi in predicting Y with the additional restraint ΓipXq “ ΓipX˚q. Thus, since Γi is most-expressive, we have P pY “ y|ΓipXq, UY q “ P pY “ y|X,UY q for all y P Y . This holds for all values of ui, and hence we get the desired result for any distribution P pUiq. Sufficiency: We wish to show that if Equation (5) holds for all P pX:q and P pU1q, . . . , P pUmq, then there is no edge Ui Ñ Y in the causal graph. We will prove by contrapositive: Assume there is an edge Ui Ñ Y , then we will show there exists distributions P pX:q and P pU1q, . . . , P pUmq such that Equation (5) does not hold.
Define P pX:q “ δx: for some x: P X where δ denotes a Dirac-delta function. Define P pUi “ uidi q “ 0.5 and P pUi “ uiq “ 0.5 for uidi , ui P supppUiq. As usual, uidi always selects the identity transformation, and ui selects a single transformation tui P T piq. Similarly, for all j ‰ i, define P pUjq “ δuidj for u id j P supppUjq that only select identity transformations. Now, there are two possible observed inputs: x “ tpuid1 , . . . , uidmq ˝ x: “ x: and x1 “ tpuid1 , . . . , ui, . . . , uidmq ˝ x: “ tui ˝ x:. Finally, define Y :“ 1pUi “ uidi q, thus x and x1 have different labels. But, any counterfactually-invariant representation Γi by definition has Γipxq “ Γipx1q since they belong to the same equivalence class. Thus, even if Γi is most-expressive, we have |P pY |ΓipXq, UY q ´ P pY |X,UY q|TV “ 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 Ui, i P D. The hidden transformation variables Ui, i P D 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 (2021) also require pinpointability of the cause of the observed X . In our setting, this is 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 U1, . . . , 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 a 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 can be seen as 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 we do not have access to such a collection of counterfactual examples. In this work, we consider the traditional automated interventional data augmentations under a mostly unknown data generation process, as opposed to the counterfactual data augmentation (Kaushik et al., 2020) that either considers a fully-specified toy SCM or relies on humans-in-the-loop to generate counterfactual data.
In Figure 1(c) we show that the interventional data augmentation is not sufficient for the OOD task. However, if one had access to the fully-specified causal model, one could generate the counterfactual data shown in Figure 1(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 a counterfactual invariant classifier can be constructed from interventional data augmentation alone if the lumpability condition (Definition 2) is satisfied. This is not the case in Figure 1(d).
Veitch et al. (2021) define counterfactual invariant predictors fpXq when X has a single parent Z and provide conditions such predictors must satisfy over the observed distribution (given an SCM). We generalize their definition for our setting where X has more than one parent in the causal graph corresponding to different symmetries. Note also that Veitch et al. (2021) assume that part of the observed input X (XKZ ) is not causally influenced by the confounder Z. In our scenarios this is not generally true. For example, under a 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. (2021, Lemma 3.1) of a counterfactually invariant predictor that requires a segment of X to not causally depend on Z, a fundamental result of their work, unfortunately does not apply to our setting (since X may have no such segment).
A.4 MNIST-t3, 4u EXPERIMENTS WITH FINITE TRANSFORMATION GROUPS
We test our proposed method on out-of-distribution tasks on images where the equivalence relations (symmetries) are provided as transformation groups (e.g., 90˝ rotations). We use the MNIST-t3, 4u (colored) dataset (Mouli & Ribeiro, 2021) that only contains digits 3 and 4, and follow their experimental setup. MNIST-t3, 4u is used to avoid any confounding factors while testing if the proposed method can learn the correct invariances, not for any practical considerations (e.g., rotated 6 is a 9 and would interfere with some experiments, etc.).
We consider equivalence relations obtained from 3 different transformation groups: rotations by 90˝ (denoted Grot), vertically flipping the image (denoted Gv-flip), and permuting the RGB color channels of the image (denoted Gcol). The 3 corresponding equivalence relations are lumpable (Definition 2) with respect to the transformations in the other two groups in almost all the cases. Only exception is the equivalence relation „v-flip, which is not lumpable with respect to the transformations in Grot. Consequently, we do not consider a task with invariance to vertical flip alone. We test our method on the same 4 classification tasks proposed by Mouli & Ribeiro (2021) 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 a collection of function classes F :“ tFS : S Ď trot, col, v-flipuu corresponding to various invariant representations. For example, Ftrot,colu is a space of functions (CNNs) that are G-invariant to the rotation and color-permutation groups (Grot and Gcol), and FH is the space of functions with no invariance (standard CNN).
Results. Our results are shown in Tables 2 to 5 for the four tasks respectively where the label is (i) invariant to all three groups, (ii) invariant to only rotation and vertical flips, (iii) invariant to colorpermutation, and (iv) invariant to none. We show the values for RpFq, {COMPpF ,Dq and SpF ,Dq as 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 SpF ,Dq). Test accuracy is computed on the extrapolated dataset after shifting the distribution of P ptUiuiPsDq (i.e., by applying the transformations that the label is invariant to).
In Tables 2 and 3, we see that the proposed method selects the correct model class in training and achieves the best OOD test accuracy. In Tables 4 and 5, the method is excessively invariant (to vertical flip) but still achieves within 1% of the best OOD test accuracy. The OOD test accuracy of a standard CNN with no invariance (FH) is typically very low except in Table 5 where sensitivity to all groups is required. We can also see the importance of RpFq for tie-breaking in these experiments.
Table 5: Results for different function classes on the MNIST-t3, 4u classification task with sD “ H,D “ trot, col, vflipu, i.e., task is sensitive to all three groups (D) and insensitive to none (sD). RpFq, {COMPpF ,Dq and SpF ,Dq 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 ptUiuiPsDq. We see that the SpF ,Dq loss selects a model that is excessively invariant in training, but the test accuracy is not that much penalized by the extra invariance (vertical flip).
Model class RpFq ` {COMPpF ,Dq `NLLpF ,Dq “ SpF ,Dq Train Acc Test Acc
Ftu 7 6639.165 1.195 6647.360 100.00 ( 0.00) 96.00 ( 0.60) Ftvflipu 3 6639.117 3.548 6645.665 100.00 ( 0.00) 95.18 ( 0.45) Ftcolu 3 6639.192 7536.167 14178.359 58.77 ( 3.34) 32.45 ( 2.18) Ftcol,vflipu 1 6639.184 7902.462 14542.645 52.50 ( 7.64) 31.21 ( 2.48) Ftrot,colu 1 6639.088 13628.356 20268.443 23.78 ( 2.25) 15.93 ( 0.71) Ftrotu 3 6639.153 5259.957 11902.110 58.12 ( 4.05) 47.23 ( 1.89) Ftrot,vflipu 1 6639.827 5267.771 11908.598 57.13 ( 1.38) 47.57 ( 2.15) Ftrot,col,vflipu 0 6639.055 13705.123 20344.178 22.97 ( 3.32) 16.13 ( 2.22)
Table 6: Results for different function classes on the CIFAR10 classification task with two sets of transformations (transformations that do not form groups) on images: arbitrary rotations (with cropping due to rotation) and arbitrary hue shifts. The task is invariant to both sets of transformations (sD) and sensitive to none (D). RpFq, {COMPpF ,Dq and SpF ,Dq 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 ptUiuiPsDq. We see that the SpF ,Dq loss selects the correct model class in training.
Model class RpFq ` {COMPpF ,Dq `NLLpF ,Dq “ SpF ,Dq Train Acc Test Acc
Ftu 3 27725.875 17496.615 45225.490 85.60 21.48 Ftcolu 1 27716.947 22715.956 50433.903 81.28 21.85 Ftrotu 1 -60894.145 20365.793 -40527.352 82.65 45.12 Ftrot,colu 0 -66262.157 23538.768 -42723.390 79.99 69.35
As discussed in Section 4.2, {COMPpF ,Dq is unable to distinguish between the different function classes because the training data contains a single example per equivalence class (see Figure 2c).
A.5 CIFAR10 EXPERIMENTS WITH INFINITE/NONGROUP TRANSFORMATION SETS
In this section, we test our proposed method on out-of-distribution tasks on CIFAR10 images (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 Trot), and (b) shifting the hue of an image (denoted Tcol). Note that for a bounded image, arbitrary rotation is not a group due to cropping. Further, transformations from the respective sets commute with each other, and hence, the lumpability condition is 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 F :“ tFS : S Ď trot, coluu 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, Ftrot,colu refers to CNNs that were trained by augmenting both arbitrarily rotated images and hue-shifted images. Once again, FH is the space of functions with no invariance (standard CNN with no data augmentations).
Results. We show in Tables 6 and 7 that our method is able to find the correct invariance and achieves the best OOD test accuracy whereas the standard CNN with no invariance has poor OOD performance.
Table 7: Results for different function classes on the CIFAR10 classification task with two sets of transformations (transformations that do not form groups) on images: arbitrary angle rotations (with cropping due to rotation) and arbitrary hue shifts. The task is invariant to arbitrary rotations of the image (sD) but sensitive to color (D). RpFq, {COMPpF ,Dq and SpF ,Dq 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 ptUiuiPsDq. We see that the SpF ,Dq loss selects the correct model class in training.
Model class RpFq ` {COMPpF ,Dq `NLLpF ,Dq “ SpF ,Dq Train Acc Test Acc
Ftu 3 27724.256 42166.993 69894.250 64.37 17.16 Ftcolu 1 27715.023 49744.680 77460.703 42.69 10.91 Ftrotu 1 -91370.533 46218.086 -45151.447 61.77 52.60 Ftrot,colu 0 -92009.184 50246.908 -41762.276 41.45 35.56

Review summaries:
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.

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).  The paper test this approach on tasks in a simple simulated physics environment.

Update  I 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.  ------------------------------------------------------------------  This 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.