Neural Networks for Learning Counterfactual G-Invariances from Single Environments
Authors: S Chandra Mouli
Bruno Ribeiro
Venue: ICLR 2021 Poster (2021)
Keywords: Extrapolation
G-invariance regularization
Counterfactual inference
Invariant subspaces

Abstract: Despite —or maybe because of— their astonishing capacity to fit data, neural networks are believed to have difficulties extrapolating beyond training data distribution. This work shows that, for extrapolations based on finite transformation groups, a model’s inability to extrapolate is unrelated to its capacity. Rather, the shortcoming is inherited from a learning hypothesis: Examples not explicitly observed with infinitely many training examples have underspecified outcomes in the learner’s model. In order to endow neural networks with the ability to extrapolate over group transformations, we introduce a learning framework counterfactually-guided by the learning hypothesis that any group invariance to (known) transformation groups is mandatory even without evidence, unless the learner deems it inconsistent with the training data. Unlike existing invariance-driven methods for (counterfactual) extrapolations, this framework allows extrapolations from a single environment. Finally, we introduce sequence and image extrapolation tasks that validate our framework and showcase the shortcomings of traditional approaches.

Published as a conference paper at ICLR 2021
NEURAL NETWORKS FOR LEARNING COUNTERFAC- TUAL G-INVARIANCES FROM SINGLE ENVIRONMENTS
S Chandra Mouli
Bruno Ribeiro
Department of Computer Science
Department of Computer Science
Purdue University
Purdue University
chandr@purdue.edu
ribeirofcs wwwrooccssuuuuu....ee. edu
ABSTRACT
Despite -or maybe because of their astonishing capacity to fit data, neural net- works are believed to have difficulties extrapolating beyond training data distribu- tion. This work shows that, for extrapolations based finite transformation groups, a model's inability to extrapolate is unrelated to its capacity. Rather, the shortcom- ing is inherited from learning hypothesis: Examples not explicitly observed with infinitely many training examples have underspecified outcomes in the learner's 's model. In order endow neural networks with the ability extrapolate over group transformations, we introduce a learning framework counterfactually- -gudded by the learning hypothesis that any group invariance to (known) transformation groups is mandatory even without evidence, unless the learner deems it inconsistent with the training data. Unlike existing invariance-diee driven methods for (counterfactual) extrapolations, this framework allows extrapolations from single environment. Finally, we introduce sequence and image extrapolation tasks that validate our framework and showcase the shortcomings of traditional approaches.
INTRODUCTION
Neural networks are widely praised for their ability to interpolate the training data. However, in some applications, they have also been shown to be unable to learn patterns that can provably extrapolate
fuitrf-distribution (beyond the training data distribution) (Arjovsky et al. 2019 D Amour et al.)
2020 de Haan et al. 2019: Geirhos et al. 2020 McCoy et al. 2019 Schölkopf 2019).
Recent counterfactual based learning frameworks for extrapolation tasks such as ICM and IRM (Ar jovsky et al. 2019 [Besserve et al.) 2018 Johansson et al. 2016 Louizos et al. 2017 Peters et al. 2017. Sc17:Schölkpptt
Krueger et al. (020) detailed in Section 2 assume the learner is given data from multiple environmental conditions (say environments El and E2) and is expected to learn patterns that work well over an unseen environment E3. In particular, the key idea behind IRM is to force the neural network learn internal representation of the input data that is invariant environmental changes between E1 and E2, and, hence, hopefully also invariant to E3, which may not be true for nonlinear classifiers (Rosenfeld al. 2020). While successful for a class of extrapolation tasks, these frameworks require multiple environments in the training data. But, are we asking the impossible? Can humans even perform ennlle-eviroomeen extrapolation?
Young children, unlike monkeys and baboons, assume that a conditional stimulus F given another stimulus D extrapolates to symmetric relation given F without ever seeing any such examples (Sid) man et al. 1982). F.g.,, if given D, action F produces treat, the child assumes that given F, action also produces treat. Young children differ from primates in their ability to use symmetries to build conceptual relations beyond visual patterns (Sidman and 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 evidence when they broken.
Unfortunately, envoomenv extrapolations have not been addressed the literature. The challenge comes from learning framework where examples not explicitly observed with infinitely many independent training examples are underspecified in the learner' 's statistical model, which is shared by both objective (frequentist) and subjective (Bayesian) learner's frameworks. For instance,

---

Published as a conference paper at ICLR 2021
consider supervised learning task where the training data contains infinitely many sequences xxth) -A.B) associated with label y(t =C, but no examples of a sequence yو' -BBA). If given a test example x²1e)) =BBA),, the hypothesis considers it to be out of distribution and the prediction P(y = CJ X = [)) is undefined, since P(X = (B.A)) = 0. This happens regardless of prior over P(X This unseen-is-undenn -isundersppecifeed learning hypothesis is not guaranteed to push neural networks to assume symmetric extrapolations without evidence.
Contributions. Since symmetries are intrinsically tied human single-environment extrapolation capabilities, this work explores a learning framework that modifies the learner's 's hypothesis space to allow symmetric extrapolation (over known groups) without evidence, while not losing valuable antisymmetric information if observed to predict the target variable in the training data. Formally, a symmetry is an invariance to transformations of group, known as G-invariance. In Theorem [ we show that the counterfactual invariances needed for symmetry extrapolation denteed Counterfactual G- G-invariaaness (CG-invariances)- are stronger than traditional G-invariances. Theorem 2 then, intro- duces condition in the structural causal model where G-invariances of linear automorphism groups are safe to use as CG-invariances. With that, Theorem defines a partial order over the appropriate invariant subspaces that use to learn the correct G-invariances from a single environment without evidence, while retaining the ability to be sensitive to antisymmetriees shown to be relevant in the training data. Finally, we introduce sequence and image counterfactual extrapolation tasks with experiments that validate the theoretical results and showcase the advantages of our approach.
2 RELATED WORK
Counterfactual inference and invariances. Recent efforts have brought counterfactual inference to machine learning models. Independent causal mechanism (ICM) and Invariant Risk Minimization
(IRM) methods (Arjovsky et al. 2019 Besserve et al., [2018] Johansson et al.) 2016]] Parascandolo al. 2018 Schölkopt] 2019), Causal Discovery from Change (CDC) methods Tian and Pearl 2001) and representation disentanglement methods (Bengio et al. 2020 Goudet et al. 2017) broadly look for representations, classifiers, or mechanism descriptions, that are invariant across multiple environments observed in the training data or inferred from the training data (Creager et al. (020). They rely on multiple environment samples in order to reason over new environments. To the
best of our knowledge there is no clear effort for extrapolations from a single environment. The
key similarity between the ICM framework and our framework is the assumption of independently sampled mechanisms (the transformations) and causes.
Domain adaptation and domain generalization. Domain adaptation and domain generalization
(e.g. (Long et al. 2017 Muandet et al. 2013 Aationero-Candele et al. 2009 Rojas-Carulla et al.
2018: Shimodaira 2000 Zhang et al. 2015) and others) ask questions about specific observed or known changes in the data distribution rather than counterfactual questions. A key difference is that counterfactual inference accounts for hypothetical interventions, not known ones.
Forced G-invariances. Forcing G-invariance may contradict the training data, where the target variable is actually influenced by the transformation of the input. For instance, handwritten digits are not invariant 180" rotations, since digits and 9 would get confused. Data augmentation is type of forced G-invariance (Chen et al. 2020 Lyle et al. (2020) and hence, will fail to extrapolate. Other works forcing G-invariances that will also fail include (not an extensive list): Zaheer et al. (2117) and Murphy et al. (2019a b) for permutation groups over set and graph inputs: Cohen and Welling (2016),
Cohen et al. (219) for dihedral and spherical transformation groups over images.
Learning invariances from training data. The parallel work of Benton et al. (2020) considers learning image invariances from the training data, however does not consider extrapolation tasks. Moreover, it does not provide concrete theoretical proof of invariance, relying on experimental results over interpolation tasks for validation. Another parallel work (Zhou et al. 2021 uses meta- learning to learn symmetries that are shared across several tasks (or environments). The works of van der Wilk et al. (2018) and Anselmi et al. (2019) focus on learning invariances from training data for better generalization error of the training distribution. However, none of these works consider the extrapolation task. In contrast, our framework formally considers counterfactual extrapolation, for which we provide both theoretical and experimental results.
2

---

Published as a conference paper at ICLR 2021
3 EXTRAPOLATIONS FROM A SINGLE ENVIRONMENT
Geometrically, extrapolation can be thought as rea- soning beyond a convex hull of set of training points (Haffner 2002, Hastie et al. [012 Xu et al. 2021). However, for neural networks with their arbitrary representation mappings- this geometric interpre- tation can be insufficient. Rather, we believe extrap- olations better described through counterfactual reasoning (Neyman 1923 Rubin 1974] Pearl [209)] Schölkopi 2019). Specifically in our task, we ask: After seeing training data from environment A, the learner wants to extrapolate and predict what would have been the output if the training environment were B. Extrapolations differ from traditional domain adaptation due to its counterfactual nature -a what-if question of an intervention that can only imagined if given offline data (Bareinboim et al., 2220;; Pearl and Mackenzie| 2018)). rather than a known distribu- tional change.
Ur
Up
Y
X
X
U2
Figure 1: Illustration of our structural causal model (SCM), where gray nodes indicate observed variables (in training). X and X Uz-ūū are obtained from X and are coupled by sharing Up. However, Uz and Uz can have different support, resulting in different distributions over X and X Üy
Specifically, our framework follows the independent causal mechanism principle (Schölkopf 2019 Peters et al., (017): Y A mechanism describing variable given its causes is independent of all other mechanisms describing other variables. For instance, in the causal model Ux + X - Y <- Uv, this implies that the conditional distribution P(Y|X) is not influenced by any change in P(X).
3.1 TRANSFORMATIONN GROUPS
We focus on extrapolations tied to finite linear automorphism groups acting on the input data. We start with an example. Consider an input æ X 333 representing a vectorized n RGB image. We can define at least three linear automorphism groups: (1) G (T(()) kkE 1000,1000,0..........00000000.00 1rp,00000700 which rotates the image by & degrees, (2) Geolor = (T(() Jaess. which permutes the RGB channels of the image, and (3) Gvtlip = (T(()) T. which flips the image vertically. More generally, a linear automorphism group 9 satisfies six properties: (automorphism) VT E G, T X + X:iidentity) I(x) = x, E G; (is closed under composition) VI, YI,T" T E 9, To T' E G, where T o (x) = (x)); (associative) VT, T", Tt G, T (T' o Tt) (T T') Tt; (has inverses) VT E G,
37 E s.t. T-1 o T = I; and (is linear) T E G is a linear function.
Besides images, sequences
(I1, .2)...) are another input of interest, where x E X for some appropriately defined set X. Here, the symmetric group (permutation group) S,, is the set of all permutations S, { क : [1, [1,....7.
(1, n is bijection) equipped with the composition
operator. Attributed graphs (A, X) E X, where A is tensor of edge properties and X is a matrix of node attributes, are also of interest for the permutation group S,,-
Subgroups and overgroups. Just as we can compose image transformations to make new image transformations, we can also compose automorphism groups into larger automorphism groups (overgroups). For instance, we can compose rotations and image flips to form linear automorphism group (rop = (Grm (gviip) containing all such compositions, where (-) is the group join operator. Following standard notation, we say Gau S [Ino to indicate that Gru is subgroup of (rotviipp) or, equivalently, G(oorvtiip) is an overgroup of Goo-- Henceforth, we use ( (U to denote the group generated by the groups Gi,..., 9m.
3.2 THE CAUSAL MECHANISM AND AN ECONOMICAL DATA GENERATION PROCESS
We assume that a fundamentally economical process created the training data, where the focus was on sampling diverse environments in a way that mattered to the task. For instance, image datasets will contain mostly upright pictures, rather than images over all possible orientations, but we will assume the dataset curators strive for a somewhat diverse set of subjects for each label (e.g., a good representation of different types of subjects and environmental conditions). Hence, the absence of variation over image orientations in the dataset can be counted as evidence against its effect on the image labels.
3

---

Published as a conference paper at ICLR 2021
We describe the data generation with the help of structural causal model (SCM) (Pear 2009 Defi- nition 7.1.1) illustrated in Figure [ Consider a supervised task over inputs X and their corresponding outputs Y, which are random variables defined over suitable space. The hidden random variable
x (hidd g(Un),
where g 4 - X' is a measurable map (deterministic function) that describes the input X in some unknown canonical form, where U. is random variable (e.g., Un ~ Uniform 1)). Next, define how (hhdd) is modified by transformations into the observed input X.
Transformation of ( into X. Consider collection of finite linear automorphism groups 9m. Let I S (1..... m} be a subset and D S {1....,m) m) Z be a subset of its complement. We will later define the target variable to be dependent only on the groups indexed by D. Consider independent and identically distributed random variables Un and U' that select transformations in the respective overgroups Go - (WeDDy)) and GI - (i). We note in passing that we allow GD gz # {Tidemity) even though GD n = {Tidonity) } makes the counterfactual task easier. The observed imput is defined as
(2) where TUp,Uz is transformation in Gouz indexed by two independent hidden environment back- ground random variables UD, Uz. The reader can roughly interpret UD and Uz as the random seeds of random number generator that gives ordered sequences of transformation, from Go and Gz re- spectively. If these ordered sequences are, say, T Thoe) and T ,T"h then Tun, UU the transformation obtained after interleaving the two sequences of transformations and composing them
X == TUDU2 o X(hii)
in order: Tüp.Uz T TD T c.... Note that T or T could be identity transformations.
Appendix B.I shows that this indexing is surjective, i.e., it can index every transformation in Gpuz.
Target variable. The output Y associated with X is given by
Y :- (( UD, Ur),
where h is a deterministic function and Uy is an independent random variable.
A distribution over the set of background random variables Uan (Uu, Uy, UD, Uz) along with Equations 2 and (3) induces a joint distribution XX) If the support of Uz is a singleton set {c} for some constant c, then (Y, are said to be sampled using an economical data generation process. In other words, the training data can contain just one value for the variable Uz since the outputs Y do not depend on Uz. For instance, if 9z is the rotation group, and the image label Y does not depend on image rotation, then the observed images can be all upright since the sampling is economical. This is not a required condition for our method to work, however.
Extrapolation as counterfactual reasoning. We can now ask "what would have happened to Y if we had given specific values of Uz to the data generation process in Equations (2) and (3) rather than sampling from P(Uz)". For instance, would the class of an image change if we had flipped the image along the vertical axis? Would we re-classify outlier events if we changed the order of events in a stationary time series? These counterfactual queries
environment background variables Uz.
We now describe the counterfactual variable in our task via variable coupling (Pitman 1976 Propp and Wilson 1996). which we believe gives -aanddrd-ttaistiis---e frrenndde--reellly description of counterfactual SCMs (Shpitser and Pearl 2007). The coupling of two independent variables Dj and D2 is a proof technique that creates random vector (D), D.), such that D, and D have the same marginal distri- butions, i = 1, but makes DJ and DJ structurally dependent. For instance, consider independent 6-sided and 12-sided dice, denoted D, and D2 respectively. Let D (U + e1) mod 6 + 1 and DJ = (U + (2) mod 12 + 1, where U is a 12-sided die roll and 61, <2 E {0, 1} are two independent coin flips. Then, the tuple (D), D.) has coupled the variables D, and D2 via the common random variable U.
Definition 1 (Counterfactual coupling (CFC)). The counterfactual coupling of the observed data (Y,X) is a vector (Y,X, XY,XXXU,+UU) where Y = (hii( UD, Uy), X = Tüo,Uz (hidd, and X U = "UDDD"" X(hidi, for appropriately defined Un, Up, Uv Uz, Üz. The subscript Uz +- Üz denotes the counterfactual variable to X when Üz replaces Uz in the data generation process. For a constant u, Xugru gives the same definition as the twin network method of Baake and Pearl (1944.
4

---

Published as a conference paper at ICLR 2021
The support of Uz in Definition can be very different from that of Uz, potentially inducing different distribution over X UU+- Ü2 than X even the variables X Xūz+ūz and X are structurally dependent via UD. Armed with Definition
we are now ready to describe our task.
3.3 EXTRAPOLATION MODEL
We start by defining counterfactual G-invariant (CG-invariant) representations.
Definition 2 (CG-invariant representations). Let the vector (X, XUZ<ūz ) denote the counterfactual coupling of the random variable X given in Definition for any Uz. A representation function : Rd, d 2 deemed CG-invariant if
T(X) U(x
(4)
where the equality implies that U( = I ((X Yu supp(Ur), Vu' supp(Uz) and supp(A) is the support of random variable A.
Extrapolated model from training to test data. Let (()) ~ X( and (Y, x ~ P(Y, U, for some appropriately defined Uz 10:~PPM P(Uz), be the random variables describing the training and test data, respectively. We do not have access to test data at training time. Let T true X + R2d 2 1, be representation of the input data. Consider a function Gine RRd Im P(Y = y ( -hheee Im P(-) is the image of P(-)- (e.g., flvee could be feedforward network with softmax output) and
Y|X"> & "ix"", with 8| ~ Irme (T (Pinue (x(1))),
(5)
where means the random variables have the same distribution. Then, if I (X)= (X U2+
then we have that, by our definition of X and X("",, Itre I tree extrapolates:
Y (te) (t)))
( with {| ~ Irme (I (T
(6)
Alas, learning I' mr is the real challenge: (i) We do not know I (and, hence, we do not know the group Gz which is related to the CG-invariance); (ii) this would also require knowing P(Ūz), which we don't. Without observed X U the statistical assumption that examples not explicitly observed with infinitely large training data have underspecified outcomes in the learner's statistical model does not push the model towards learning T Tiree. We must change this assumption.
4 CG-INVARIANCES FOR EXTRAPOLATION
In this section introduce our learning framework, which seeks to use the training data to approx- imate Tume and Juue Equation (6). Our framework regularizes neural network weights towards representations that are invariant groups that negligibly impact training data accuracy. We over- come some key challenges: (a) Theorem T below shows that CG-invariances (Definition 2 are stronger than G-invariances. After that, Theorem Sooremm@eeinn defines conditions under which G-invariances suffice as CG-invariances, and (b) We derive an optimization objective where all G-invariances are mandatory, except the ones deemed inconsistent with the training data, replacing the traditional unseen-is sireen-is-une -inee-sssenerreiiffeee learning hypothesis.
Our first question is whether CG-invariances are just G-invariances. Theorem shows they are not. Theorem 1 (CG-invariance is stronger than G-invariance). Let the vector (X, X Xuzeūū) denote the counterfactual coupling of the observed variable X given in Definition 7 For a representation T: X Rd. d > let
G-inv: VTz 9z, T(X)=T(Tzo)
CG-inv: r(X) = r(Xuxrüx))
denote the conditions on I for Gr-invariance and CG-invariance respectively. Then, CG-im inc, but G-iny + CG-inv
G-
The proof in Appendix B.2 constructs task over images and representation I' that is Gr invarriitn but is not CG-invariant (for appropriately chosen Gz and Gp). The following condition ensures that a Gz -z-invariance is also CG-invariance.
5

---

Published as a conference paper at ICLR 2021
Theorem 2. If 9z is normal subgroup of GDuz, then CG-inv G-inv.
A subgroup H of a group G is called normal (denoted H 4 G) if for all h E H and E G, ghi-- E H. Proof in the Appendix B.2 utilizes the fact that if Gz GDUZ, then any T &Duz can be written as T = TI o Tp for some TI E Gr, TD E Gp. Throughout the rest of the paper, we will assume that Gz is normal subgroup of GDUZ in the SCM Equation
4.1 CONSTRUCTING SUBSPACES OF VEC(X') PARTIALLY ORDERED BY INVARIANCE STRENGTH
As discussed before, we do not know Gr. In this subsection, we build neural network weights that are invariant to GM for different subsets M S (II.....m) m. detailed step-by-step example of this construction for 3 x 3 images is shown in Appendix [ We start by restating the Reynolds operator, which has been extensively used in the literature of G-invariant representations without attribution:
Lemma 1 (Reynolds operator (Mumford al. (194)), Definition 1.5)). Let G be a (finite) linear automorphism group over vec(.)). Then.
T
Σ T
99
TEG
a G-invariant linear automorphism, i.e., VT, E 9 and Vo E vec(œ), must be that T(Txx) = Tx.
Since T is a projection operator (i.e., T = T), all the eigenvalues of T are either 0 or 1. Using this fact, we now describe G-invariant neurons using the left eigenspace of T corresponding to the eigenvalue
Lemma 2. If W denotes the left eigenspace corresponding the eigenvalue I of the Reynolds operator T for the group G, then vb E R, the linear transformation <(x; w, b) = w x + is invariant to all transformations T E G. i.e. y(Tx;; x; w. b) (2; w. b). if and only if w W.
The above property of the Reynolds operator can be leveraged to build neural networks that adhere to particular group symmetries, as done by Yarotsky (2018) and van der Pol al. (2020). If we knew Gz. restricting the parameters of each neuron to the left T-eigenspace of the Reynolds operator of Gz would give us a way to build a -ziinvariant neural network.
Alas, we do not know Z. and consequently we do not know Gz. Instead, we want to construct bases for the complete space vee(X') such that they are partially ordered by their invariance strength: From most invariant bases to least. In other words, we construct bases for subspaces B for M C {1..... m] such that any weight vector w E By is (a) invariant to the groups G, for i E M, and (b) not invariant M. Later, we will use this partial order define regularization term for our method. Theorem 3 shows how these bases can be constructed inductively, where we start with the most invariant subspace (when M {1, ... m)) }) and judiciously work our way over increasingly less invariant subspaces. A reader more interested in the algorithm can first refer to the pseudocode in Appendix D or the example in Appendix (Step 2).
any group 9j for j E (1. (1...., m]
Theorem 3 (G-invariant subspace bases can be partially ordered by invariance strength). Let W, S vec(X)) be the left eigenspace corresponding to the eigenvalue I of the Reynolds operator T, for group Gi. i 1, 1...., m. We construct the invariant subspace partitions
BM W,; BM = orth (Bar), VM E p((l.....m)) (m)
(8)
iEM
where p is the power set, B-M = DNDM BN, orth (A2) removes from the subspace A2 its orthogonal projection onto the subspace As, and ① is the direct sum operator: Then, the linear transformation y(x; w. b) w" x bb be RR, vw E BM (10), is -iv-iraaiann but not Gj-invariant Vj E (1...., m) M.
The proof in Appendix B.3 shows that Bar contains all the vectors w that are invariant to Gas but could also contain vectors that are invariant to some overgroup of 9M- Thus, each step of our inductive method performs a Gram-Schmidt orthogonalization in order to satisfy condition (h) above: need to remove from B& all weight vectors that are invariant to more groups in addition to those indexed by M (i.c., supersets of M). In addition, if needed, we obtain the basis for the rest of the space through Bg = orth (vec( the orthogonal complement of B B-0-

---

Published as a conference paper at ICLR 2021
Note that if E BN. then is never GH -ivvariatt for H N remove all such from By- Hence, the partial order of nested subsets in strengths in the bases of the input domain vec(X') (see Figure 5 for an example). We define level of invariance (or invariance strength) of subspace BM as the size of (i.e., [M).
m)) induces a partial order of invariance
Practical aspects. Our algorithm should output dx dim(vee(XX)) basis vectors covering the entire space (i.e., our new neuron, described later in Equation (TO), still has dx + parameters as the original one). Thus we stop the algorithm in Theorem 3 Once dx basis vectors the algorithm needs to run only once for groups G1, ,.... 9m. and the results can be reused for other neural architectures. While the worst-case runtime of finding the bases could be exponential in m, is unclear whether this exponential runtime can actually happen in practice (all of our experimental runtimes take less than one minute in commodity machines).
found. Moreover,
4.2 LEARNING CG-INVARIANT REPRESENTATIONS WITHOUT KNOWLEDGE OF Gz.
We are now ready to learn a CG-invariant representation using neural networks I' and Let 91,..., 9m be known linear automorphism groups. Under the assumption of Theorem 2 we just need I' to be Gz-invariant, with Gz (Usez94), but I C (1,..., m) is unknown to us. We achieve the correct Gr-invariance by redefining the neuron weights of I' using the subspaces of Theorem 3 and proposing regularized objective that pushes I' towards the strongest overgroup G-invariance that does not significantly hurt the training data, where significantly is controlled by a regularization strength À 0.
1, be a neural network layer with H neurons, parameterized by free parameters Ω RdxxH and b E R" The H neurons arranged in an appropriate architecture as descrihed in Section5) but reader can imagine a feedforward layer for now. Let g Rd + i ) be a link function. The training data D = {(v, (tr)
More formally, let I:: vec(XX) x R x -R.
(tr) L
ii=1 is
assumed to be sampled according to the SCM data generation process in Equations
with
the hidden Gz satisfying the conditions in Theorem
Let BM xdw be matrix whose columns are the orthogonal basis of subspace BM * {0} (from Theorem with dimension dys Any vector w E B& can be expressed as linear combination of these basis columns. The coefficients of the linear combination form our learnable parameters. These neuron weights Z have a correspondence to the nonzero subspace bases B BM, BM...... BMA:
WM, .
where B S dx.
wM 3
and WM.A E Rdd, x1 represents the learnable parameters for the subspace BM, and the h-th neuron. The h-th neuron in h e {l...., HH), has the form
p()) (w) = -o a(80T Σ
=0
B BM.WW.R) + bn bm)
(10)
o(-) is a nonpolynomial activation function, and by E R is a bias parameter. Our optimization objective is then
arg min S,b,W,
Σ
L mn "n b)b); Ws)) + AR((2)
(11)
(0 2e JED
where L : y x I +
Rz0 is a nonnegative loss function, and > 0 is regularization strength. The regularization penalty R(2)) is given by,
R(Z2) = {M: M > 4 isis BY +
1|
0},
(12)
M. 188B
where = (M 11IWM,,-11
0}.
1
Intuition behind the penalty in Equation 12 : A subspace Ba, is said to be used in the computation
of neuron h (Equation (00) if the corresponding parameter WM,, is nonzero. Then, let BM, be the
least invariant subspace used by any neuron (i.e.. [Mp] is the lowest among all used subspaces) and | = I. The first term in the penalty counts the number of subspaces BMg, (used unused) that
7

---

Published as a conference paper at ICLR 2021
Mgg).. This term ensures that the optimization tries to use subspaces that are higher in the partial order with invariance to more groups. The second term in the penalty counts the number of subspaces BM, that have the same level of invariance
invariant to more groups than BMg (i.e., |M,
as BM, (i.e., |M = |M& ), and also have the corresponding coefficients WM,A nonzero (i.e., the subspace BM, is used). The larger the second term, farther away the optimization is from increasing the least level of invariance from to / + 1. We present a differentiable approximation of the penalty in Appendix F along with an example computation of Equation (22 in Figure g
Limitations of Equation (2 Recall that we stop the algorithm in Theorem once the basis for vec(X) is found. In such cases, there could be parameters S2 and S2" that assign positive weights corresponding to the same subspace bases, but with S2' invariant to more groups than St".. The penalty in Equation (12) however cannot distinguish between these two sets of weights as they use the same subspaces and thus, R(S2'= R(S2"). We provide an example in the case of sequence inputs in Appendix F3 and leave the solution as future work.
Selecting regularization strength X: We use a held-out training set to find the best validation accuracy achieved by any value of X. Then, among all the values of À that achieve validation accuracy within 5% of the best validation accuracy, we choose the largest À (i.e., we opt for maximum invariance without significantly affecting validation performance).
5 CG-INVARIANT NEURAL ARCHITECTURES
For image tasks: We can apply the CG-regularization of Equations 10) and in the convolu- tional layers of CNN architecture like VGG (Simonyan and Zisserman 2014). Mostly, the VGG architecture remains the same with the exception that the convolutional filters are obtained using the subspaces from Theorem 3 for the given groups. Once the filter obtained as linear combination of the bases, it is convolved with the image or the feature maps. This will ensure that the model is CG-invariant to the transformations of smaller patches in the image. A sum-pooling layer over the entire channel is applied after all the convolutional layers to ensure that the model can be CG- to the transformations on the whole image. See Appendix T. for an example architecture
For sequence and array tasks (sets, graph & tensor tasks), the architecture is more direct: One can simply apply a feedforward network with as many hidden layers as needed. Each neuron of the first layer given by Equation (1O), ensuring that the first layer can be CG-invariant the given groups if needed. Other layers can have regular neurons since stacking dense layers after a CG-invariant layer does not undo the CG-invariance. See Appendix F.2 for an example architecture.
EMPIRICAL RESULTS
We now provide empirical results of 12 different tasks to showcase the properties and advantages of framework Due to space limitations, our results are only briefly summarized here, with most of the details described in Appendix G Appendix [A] allso shows a task where CG- ii-iaaariance is stronger than G-invariance, showing the practical relevance of Theorem T
Validation of our learning framework (CGreg): In 12 different image and sequence tasks, we confirmed that our CG-regularization of Equation (11) is able selectively learn to be invariant to the largest overgroup that doesn't t contradict the training data, all of this without any evidence in the data supporting the invariance. The results are summarized in Table I which also shows that both standard neural networks and forced G-invariant networks do not extrapolate to new environments when I + 0 and I _ (l.....m, m), respectively.
(hid) and Transformation groups: (hid) is the canonically ordered input (c.g.. upright images, sorted sequences). Our task considers m linear automorphism groups G..... 9m. We generate Gr from a subset I S } of the groups, i.e., Gr = (Giez). We construct GD using a subset of (1. I, while ensuring that Gz 4 Gouz in order to fulfill the conditions in Theorem 2
For image tasks, (hhdd) is an upright MNIST image and the m 3 groups are Grot, Geoloe. Gventical-lip- For sequence tasks, we sample (hid) as a sequence of n sorted integers from a fixed vocabulary and consider m = (²) permutation groups for all the pair-wise permutations: 91,2, G2 -1,3,... . In-1,n where Gi.j := { ideiityy } and Tijj swaps positions and j in the sequence.
Public code available https:: htttpp///githusee hwtp://w.ooooooo/a/oa WDD/NN_OO//NNNDO Www.o//liaaraaaaaeeeeeeeeeeeeeae wesiiiaaiinnnn
8

---

Published as a conference paper at ICLR 2021
Table I: Extrapolation accuracy (# 95% confidence interval, bold means p < 0.05 sigmificant)
Image tranefomation groupe (G.,, a f Tisk: Predict digit & which trunsformations Sp was upplied imagge
Seqpences (C) to Tasks depend on 2 (see Appendis
MNIST (5.4) images
MNIST images
Sequcni
7.
VOG
4Giin
.CGreg
VGG
+fwine
.CGrrg
Tannformer
Best FF4Civiy
FF+OGrg
6
96.86
1596:2.17
94,49201249
89.3==11552
15.6411555
90299:0033
100000:00000
23,58::188
US 70 05
color
15,06:6.70
500552.17
94.16106.33
1.51
47.6110445
0.85:0.37
0,9710.00
7188526611
rot.dlip
54.87=0.90
32.05:1.16
95,78-07.11
25.91-095
44.4+1228
62.68:6.122
12 12.15+16.05
10.68:11449
42.08-18.99
rotcollitii
49.52-2.37
97.19=1022
94899007449
11.27:0:34
68.461283
64.9922.76
20.26:132.08
100,00:0000
10000000000
Training data: The training data is sampled via the SCM equations using an economical data generation process. We decompose the transformation T'zzUUp into a transformation TUp E GD followed by another transformation Tuglus Up E G9 to obtain X = Tugju' Tüp o X This decomposition is made possible from our assumption that 9I is a normal subgroup of Gouz (Theo- remb 2). Under the assumption of economic sampling of the training data, in all our experiments we simply set ToglU2 = Tademity E 9I, whereas TUp is randomly sampled from Go. Finally, following Equation 3 the label Y is a combination of the original label of X(hid) and the transformation TÜp
Example (Table T row: rot,vflip): For image tasks, if Gr 91ot, vertical-flip and gp Gooler then the training data consists of upright and unflipped images (as Tuglu, Ticerity) with different permutations of the color channels (random transformations Tu,, E &eolor are chosen). The task is to predict the original label of the image (i.e., the digit) and the transformation TD (i.e., the color).
Extrapolation task: The extrapolated test data consists of samples from the coupled random variable X UUz-Üü= Uz o ((hiid) (Definition 1.. As before, we decompose T2 = Ty o Tup with TUp E GD and Tūp Up E Gz. However, there is no economic sampling for the test data: Tūg WP and Tüp are sampled randomly from 9z and GD respectively. The task is the same as in the training data.
Example (Table T row: vflip:::)): For image tasks, if 9r = Grot. vertical-flip and Gv = Scolors then the extrapolation test data consists of images randomly rotated, flipped and color permuted, while the task is the same: predict the digit and its color.
Results: Standard neural networks such as CNNs (e.g.. VGG (Simonyan and Zisserman 2014)
(for images) and GRUS/rranffrreers (Cho et al. 2014: Vaswani et al. (017)) (for sequences) fail whenever the extrapolation task requires some invariance (I * 0). but excel at the interpolation task (I = 0). Adding forced -iva-invariances via G-CNNs (Cohen and Welling 2016) (for images) and permutation-ineee -nvarriant models (Lee et al. 2019 Murphy et al. 2019a Zaheer et al. (017) (for sequences) clearly fails when D * 0 but succeeds when D = D. Our CG-regularizes neural network representations, on the other hand, achieve high extrapolation accuracy across all tasks for choices of I C (1....,,)) , and D C (1, (1,..., m) \ Z. These results plainly show that our approach is able to selectively learn to be invariant only to the appropriate groups. Furthermore, this Gr-in Griinvariance is achieved without any evidence in the training data, thanks to our novel learning paradigm that considers all G-invariances mandatory unless contradicted by the training data.
7 CONCLUSION
This work studied the task of learning representations that can extrapolate beyond the training data distribution (environment), even when presented with a single training environment. We considered the case of (counterfactual) extrapolation from linear automorphism groups and described a framework where all G-invariances (and CG-invariances via Theorem 2 are mandatory, except the ones deemed inconsistent with the training data (i.e., rather than learning G-invariances, we unlearn them). Our framework reframes the standard statistical learning hypothesis that unseen-data means underspecifiedd-oon models with a learning hypothesis that forces models to have all (known) G-invariances (symmetries) that do not contradict the data, with our empirical results supporting the proposed approach. Finally, this learning paradigm offers a promising novel research direction for neural network extrapolations.
ACKNOWLEDGMENTS
This work was funded in part by the National Science Foundation (NSF) Awards CAREER IIS- 1943364 and CCF- CCCF-1918483 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.

---

Published as a conference paper at ICLR 2021
REFERENCES
Fabio Anselmi, Georgios Evangelopoulos, Lorenzo Rosasco, and Tomaso Poggio. Symmetry-adapted representation learning. Pattern Recognition, 86:201-208, February 2019, ISSN 0031-3203. doi: paatcog.2018.07....
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint (wXXiv:907.0289) 2019.
Alexander Balke and Judea Pearl. Counterfactual probabilities: Computational methods, bounds and applications. In Uncertainty Proceedings 1994, pages 46-54. Elsevier, 1994.
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.
Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Nan Rosemary Ke, Sebastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher Pal. A meta-transfer objective for learning to disentangle causal mechanisms. In International Conference on Learning Representations, 2020. URL net lttee/oorrmmmdd=yyyee
httts:://peereew/
Gregory Benton, Mare Finzi, Pavel Izmailov, and Andrew Gordon Wilson. Learning invariances in neural networks from data. NeurlPS, 2020.
Michel Besserve, Naji Shajarisales, Bernhard Schölkopf, and Dominik Janzing. Group invariance principles for causal generative models. In International Conference on Artificial Intelligence and Statistics, pages 557-565, 2018.
Shuxiao Chen, Edgar Dobriban, and Jane Lee. group-theoretic framework for data augmenta- tion. Journal of Machine Learning Research, 21(255):1-71, 2020. Uttppttp:///mir org/
papers/v21/29 163. html
Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder decoder approaches. Syntax, Semantics and Structure in Statistical Translation, page 103, 2014.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference machine learning, pages 2990-2999, 2016.
Taco S Cohen, Mario Geiger, and Maurice Weiler. A general theory of equivariant cnns on ho- mogeneous spaces. Advances Neural Information Processing Systems, pages 9145-9156, 2019.
Elliot Creager, Jöm-Henrik Jacobsen, and Richard Zemel. Exchanging Lessons Between Algorithmic Fairness and Domain Generalization. arXiv:2010.07249 [cs], October 2020.
Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D Hoffman, al. Undenspecification presents challenges for credibility in modern machine learning. arXiv preprint arX1v:2011.03335, 2020.
Pim de Haan, Dinesh Jayaraman, and Sergey Levine. Causal confusion in imitation learning. In Advances in Neural Information Processing Systems, pages 11698-1 1709, 2019.
Robert Geirhos, fom-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. Shortcut learning in deep neural networks. Nature Machine Intelligence, 2(1 1):66)6673, 2020.
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, Isabelle Guyon, David Lopez-Paz, and Michèle Sebag. Causal generative neural networks. arXiv preprint arXiv:1711.089.0 2017.
Patrick Haffner. Escaping the convex hull with extrapolated vector machines. In Advances in Neural Information Processing Systems, pages 753-760, 2002.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning, volume 1. Springer series in statistics, 2012.
10

---

Published as a conference paper at ICLR 2021
Fredrik Johansson, Uri Shalit, and David Sontag. Learning representations for counterfactual inference. In International conference on machine learning, pages 9020-3029, 2016.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv 69800, 2014.
David Krueger, Ethan Caballero, Joem--eerik Jacobsen, Amy Zhang, Jonathan Binas, Remi Le Priol, and Aaron Courville. cittrf-Distribution Generalization via Risk Extrapolation (REx). 0rXiv:2003.00688 [cs, stat], March 2020.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek, Seungjin Choi, and Yee Whye Teh. Set Transformer: A Framework for Attention- based Permutation-Invant Neural Networks. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Mingsheng Long, Han Zhu, Jianmin Wang, and Michael Jordan. Deep transfer learning with joint adaptation networks. In International conference machine learning, pages 2208-2217. PMLR,
2017.
Christos Louizos, Uri Shalit, Joris M Mooij, David Sontag, Richard Zemel, and Max Welling. Causal effect inference with deep latent-variable models. In Advances in Neural Information Processing Systems, pages 1446-6456, 2017.
Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy, On the benefits of invariance in neural networks. arXiv preprint arXiv:2005.00172 2020.
R Thomas McCoy, Junghyun Min, and Tal Linzen. Berts of feather do not generalize together: Large variability in generalization across models with similar test set performance. arXiv preprint arXiv:1911.02969 2019.
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International Conference on Machine Learning, pages 10-18, 2013.
David Mumford, John Fogarty, and Frances Kirwan, Geometric invariant theory, volume 34. Springer Science & Business Media, 1994.
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- fions, 2019a
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In Proceedings of the 36th International Conference on Machine Learning, 2019b.
Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy Pool- ing: Learning Deep Permutation- Invariant Functions for Variable-Size Inputs. In International Conference on Learning Representations, September 2018.
J Neyman. Sur les applications de la theorie des probabilites experiences agricoles: essai des principes (masters thesis); justification of applications of the calculus of probabilities to the solutions of certain questions in agricultural experimentation. excerpts english translation (reprinted). Stat Sci, 5:463 472, 1923.
Giambatrista Parascandolo, Niki Kilbertus, Mateo independent causal mechanisms. In International Conference on Machine Learning, pages 4036- 4044. PMLR, 2018.
and Bernhard Schölkopf. Learning
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, pages 23-52, 2018.
Judea Pearl. Causality. Cambridge university press, 2009.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference. The MIT Press, 2017.
11

---

Published as a conference paper at ICLR 2021
JW Pitman. On coupling of markov chains. Zeitschrift für Vohnschhemnicckkettshheoeee und verwandte Gebiete, 35(4))315533) 322, 1976.
James Gary Propp and David Bruce Wilson. Exact sampling with coupled markov chains and applications to statistical mechanics. Random Structures & Algorithms, (11-))223-25 1996.
Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. The MIT Press, 2009.
Mateo Rojas-Carulla, Carulla, Bernhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer learning. The Journal of Machine Learning Research, 19(1):1309-1383 2018.
Flan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. arXiv preprint arXiv:2010.0576/ 2020.
Donald B Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of educational Psychology, 66(5):688, 1974.
Bernhard Schölkopf. Causality for machine learning. arXiv preprint arXiv: 2019.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-
likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Ilya Shpitser and Judea Pearl. What counterfactuals can be tested. In Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence, 2007.
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-22, 1982.
Murray Sidman, Ricki Rauzin, Ronald Lazar, Sharon Cunningham, William Tailby, and Philip Carrigan. A search for symmetry in 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 140xv::409.15555 2014.
Jin Tian and Judea Pearl. Causal discovery from changes. UAI, 2001.
Elise der Pol, Daniel Worrall, Herke van Hoof, Frans Oliehoek, and Max Welling. Mdp homomorphic networks: Group symmetries in reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
Mark van der Wilk, Matthias Bauer, ST John, and James Hensman. Learning invariances using the marginal likelihood. In Advances in Neural Information Processing Systems, pages 9938-9948, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances neural information processing systems, pages 5998-6008, 2017.
Gesche Westphal-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, 367(1559))220722022,, 2012.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanic Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Representations, 2021. URL httpps::/opeeeeeiiiiii
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. arX4v:/804 10306 [cs), April 2018
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. Gamett, editors, Advances in Neural Information Processing Systems 30, pages 3391-3401. Curran Associates, Inc., 2017.
12

---

Published as a conference paper at ICLR 2021
Kun Zhang, Mingming Gong, and Bernhard Schölkopf. Multi-source domain adaptation: A causal view. In AAAI, volume 1, pages 3150-3157, 2015.
Allan Zhou, Tom Knowles, and Chelsea Finn. Meta-learning symmetries by reparametcrization. In International Conference on Learning Representations, 2021. URL / net / worumorriii Qx QxT4mJdijq
13

---

Published as a conference paper at ICLR 2021
Supplementary Material of "Neural Networks for Learning Counterfactual G-Invariances from Single Environments"
A
THE PRACTICAL IMPORTANCE OF THEOREM
1
27
Yw
yimil
F
[
F
yolll
y0l0) 11:20
10 y0ax
H
Figure 2: An example task where CG-invariance is stronger than G-invariance. The task is predict the orientation of the image while being CG-invariant to horizontal translations.
There are real tasks where CG-invariance is stronger than G-invariance. We consider a task with 60 60 image shown Figure 2 and two transformation groups: the rotation group Gis and the cyclic horizontal--rannslttioo group Inttrassate _ Loo. Each transformation T(0") E Gou rotates the image along its center by 0%, whereas every transformation T(+h) E Insmanlate translates the image horizontally by h pixels while wrapping around the edges. Let GI = Gro and GD = Ih-mmnslate- The training data consists of images X = T(0") o ( for all T(8)) E Gro. whereas the test data consists of images X Uz+0z = T(()) (++20) o (hidd) for all (T()) E 9ro. The task is to predict the orientation of the image, i.c., degrees of rotation. It is easy to see that the label requires CG- invariance to Gn-translate but sensitivity Grot- We train strictly Gn-translate eh-cannsae--nvvaiian invariant model on this dataset; whereas the model is able to achieve a 100% accuracy on training, does poorly with 75% on test dataset, showing that is not enough be Gz-invariant achieve CG-invariance.
B PROOFS
B. GENERATING ANY T' E GDUZ USING NOISES Uz AND UD
The structural causal model for X in Equation (2) requires that any T GDUZ can be indexed by the hidden background variables Uz and Up- We first interpret Up (or UT) as the random seed of random number generator that gives ordered sequence of transformations of GD (or Gr). We assume that these background noise variables can generate any sequence of transformations from
within their respective groups. Let T(() ..... T(e) and T((I) ......". T
be those ordered sequences respectively generated by Un and Uz. Then we can obtain transformation in GDur by interleaving -...,T
these two sequences (in order): TU..U, T I Iff) ... Note that U' and Upp always sample the identity transformation from the respective groups in the corresponding sequences, i.c.,
(p(() or (())) can be identity.
Now, a known result in group theory that any T E (GD U9z) is such that T, where T: is in either Gz or GD. Then, if T, E Go. we can write T, T T with T
.....
Tidenityy E Gr and T = Ti E Gp. Continuing from Gz and the other from Gp. such that interleaving and composing the
similar fashion, we can find two sequences
of transformations, resultant sequence transformations gives us any transformation from GD.IT This property of the noises appropriately index any T E GDuz will be used in the proof of Theorems and
14

---

Published as a conference paper at ICLR 2021
B.2 PROOF OF THEOREMS 1 AND
Theorem (CG-invariance is stronger than G-invariance). Let the vector (X, X Xur-Ü denote the counterfactual coupling of the observed variable X given in Definition 7 For a representation T: X Rd, d 2 lel
G-in: : VTI E Gr, f(X)= -(T X); CG-inv: T(X) r(X (z+)))))
denote the conditions on I for Gr-invariance and CG-invariance respectively, Then, CG-inv = G- inv, but G-inv + CG-inv.
Label: Upright
Label: Flat
+
2-+9)
2700%) 2r/-8)
Label: Upright
Label: Fiat
2n-=1
2n #-1
2n +1
Figure 3: Counterexample to show that Gr-invariance does not imply CG-invariance. Given images of a rod (shown in brown), we wish to predict the orientation of the rod, i.e., whether the rod is upright flat. In this example, does not affect the orientation of the rod. I X + R sums the pixel values across the green shaded region, and is clearly G-invariant to horizontal translations. However, is CG-invariant.
have GD Guo and Gz I-uaasltte any horizontal translation
Proof. First, we will show that CG-invariance + G-invariance, i.c., for any CG-invariant repre- sentation I' X Rd. we will show that I' is also G-invariant Gr.
Consider any E supp(Uz) and say the input was generated as XUze-u = TUD.UT-- (hid), In other words, Uz took the value u in the structural causal equation for generating the observed input (Equation 2 We will prove G-invariance for this input Xuzta, i.e., I(T] o Xuzem) = T(X for any T E Gz.
Recall that Tüp.Uzeu was generated by interleaving two separate sequences transformations obtained via the background variables Up and Uz respectively (Appendix B.I). In other words, can write Tup,uzen T(l)) T(!)) T(2) o.... T(*), where T(0) Gr and T GD
and T++)) depends upon which of the respective sequences before interleaving is longer. Then, Tt TÜp.Uzzu = Tf T(2), T(1) o T o... o (+)), Further, we write Tx)) T (())) then we have TI Tuo.Urer T(() T(l)) TT(2) o(.).
Now we can find ö such that Uz + ū generates the sequence of transformations T((1) (2) Interleaving this sequence with the sequence generated by UD. we get Tup.U++ = T o T
TT(2) T(t) Denote Xuzra Tup,Uraā (hhdd) Since I is CG-invariant, have from
15

---

Published as a conference paper at ICLR 2021
Definition that
r(XUz+u) I(XUz+a)
= =I(Tuo,Uzea o X
=I(T) o UUo.Uzeu X(hill)
(from construction of i))
= =T(T) o XUztuu.
Since this holds for all E supp(Uz), we have that ((X) - - x).
Next, we will show G-invariance + CG-invariance by constructing a counterexample, Let X ( 12 (2n++1 be the (2n + x (2n + 1) grayscale image of upright rod as shown in Figure
Consider two groups that act on this image: the rotation group 9 {T(()) tik 1000,100_,000000 .2700) and the cyelic and the label of the image Y deterministically given by the orientation of the rod: upright (Y = 0) or
group 9n translate {T(+*) JuEz. Let GD G and 9z Gn ransatee
flat (Y 1). The top row of Figure depicts the data in training which is transformed by In-ranstate
only via the identity T++0) (i.e., no translation).
Now consider representation r 1(2 R such that T(X) 2i=1 X,,i finds the sum of the middle row of the image. Note that (a) I' is able to distinguish between the labels for the training data, and (b) I' is -n-tooslae-inaarin
We can define the random variables Uz and Üz such that 7r(90%) (hhid) and UUr-ūz Tr(90) T(+5) (hid)) Then, as shown in Figure 3 r(xu,+ I(T(90%) r(+5) ox X(liio)) *
I(T(900) a X(iid)), thus showing that I is not CG-invariant.
Theorem 2. Gz is normal subgroup of GDuZ, then CG-inv
G-inv.
Proof. The proof that CG-invariance = G-invariance (from Theorem T still holds here. We only need to prove the converse: G-invariance = CG-invariance when Gr is normal subgroup of GDUZ. We begin with a representation I' that is Gr-invariant and consider the simpler case when UD generates transformation sequence of length I (from GD). In other words, X is obtained by:
X
T())
To o T o X for arbitrary transformations To GD and T TT() E Gr.
Then for any Ür we have that XU--ūz -T( o TD T(22 (hid) with T TT(2) Gr. Note that Uz only affects the transformations from Gz. The condition for CG-invariance with respect to Gr requires that
requirement:
T(X)= = T(T()) o TD o T o x(hid) = -(( o TD (22) X(hid) = r(x ((Uz<ū))
(13)
Since 9r is normal subgroup of GDuz and GD S GDUZ, we have
vTD E GD, VTI E Gr. To Tr T 9z,
or equivalently.
VTD E GD. VTz E Gz, ET s.t.
Tp o Ty To' =T-s To e TTeT T TD
(14)
(A special case when the groups ID and Gz commute, as then Tp Tı = TI Tp.)
Then,
T(X) I(T(") To T(2) (hidd)
-T(T T((2 o xchidl
(T is invariant to Gr)
=T(T' o Tp o X(idd))
(there exists such T E Gr) ( is invariant Gz)
=[(Tp X(hid)
16

---

Published as a conference paper at ICLR 2021
Similarly, can prove for the coupled variable that T(X I(Tp X ) thus satisfying the requirement of CG-invariance in Equation (13).
U2+002 r(Tz)) To o Ti.) X(hid)
Extension to the case when UD generates transformation sequences of length greater than one is trivial. Any transformation TUp.Uz = " T T T(*) can be written in the form
T o TT" Th
by repeatedly applying the normal subgroup property in Equation (14 Then T(TUp.Uz o x = r(T TDO) o T o ..... o X = r(T o T о ..... X(hidt)
as r is GT-
invariant. Using similar argument, we can show for the coupled variable that [(T C(TUp. Up.Uz o x
T(T TTL o...o (, thus proving that I is CG-invariant, i.e., T(X) I(X (Xx U2
B.3 PROOFS OF LEMMA LEMMA
AND THEERRMM
Lemma (Reynolds operator Muumford al. 1994). Definition 1.5)). Let G be a (finite) linear automorphism group over vec(.²). Then.
Στ T
9
TEG
a G-invariant linear automorphism, i.e., VT, E 9 and Va E vec(2)) it must be that T(Txx)) Tx.
Proof. Consider an arbitrary transformation Ti E G. Then
ToT: =
ToR
9
TEG
Σ T'
G
T'ES,
where define 9. (T TT VT E 9}. Now, in order prove To T, T, we only need to show that G. G. Since groups are closed under compositions, we have VT' E G. T Ti E G, and thus St S G. Finally, since 72 bijection and Ta o T7 T7 only Tf T. for any Ta Th E G, must be that |9 = | Hence, 9 G.
Lemma 2. If W denotes the left eigenspace corresponding to the eigenvalue 1 of the Reynolds operator T for the group then vb E R. the linear transformation >(x; w. b) w² x is invariant to all transformations T E G, i.e., (Txx; w. b) = (x; w. b), if and only if w E W.
J==1 Proof. Sufficiency: Let ( dw be the set of left eigenvectors of T with eigenvalue and constitute
the orthogonal basis for W. Consider any non-zero w' W, then
dw
dw Σ a
(w/)T =
(15)
for some coefficients {ar " where we used the fact that w/ = w S i S dw. For any vec(X') and any T E G we have,
<Tw;; w/, b) = (w)) (To'T((Ta) (Tx)TT)))))))) +
dw
a T(Tar) (TTT)++++ +
(using Equation 15
Σ Ja Tx
(from Lemma I
(x:; w/, b))
17

---

Published as a conference paper at ICLR 2021
Necessity: Given non-zero w W and b E I, let ((x;; w. ((;; b) for all E vec(A)) and all T E G. Then,
w T Tx = w x, Va, VT
w" T = w², VT
w" Σ T g w
(summing over all T' E G)
TEG
T w
Hence proved that w" is a left eigenvector of T with eigenvalue 1.
Theorem 3 (G-invariant subspace bases can be partially ordered by invariance strength). Let W, S vec(X) be the left eigenspace corresponding to the eigenvalue I of the Reynolds operator T; for group gú, i ,...., We construct the invariant subspace partitions
BM
N W.; BM = (o iEM
VM p(L....., \0,
where t is the power set, BзM - ① N BN, orthA, (Az) removes from the subspace A2 its orthogonal projection onto the subspace AI, and ① is the direct sum operator. Then, the linear transformation y(x; w.b) = w" bbb b RR Ya E BB \ (0), GMa -ivviraaia but not Gi-invariant dj E (l,...., m} M.
Proof. Throughout this proof, we will slightly abuse notation by calling w vec(X) as G-invariant for some group G, where we mean the transformation 7(: w, b), b E R is G-invariant.
Consider the subspace B B2M- = Q N2M By, where + is the direct sum operator. Essentially, B2M the direct sum of all the subspaces corresponding the strict supersets of M. Using induction on the size of M, we first show that B 2aar = θ N2ar By. The statement trivially holds for (2()....m))
Then the induction hypothesis is: for all sets M such that [M] k, have B3 Mr We prove that the statement holds for any set M with [ le as follows,
NZM BN
32M= BN
N
(Bx @ B2N)
MM N I
orthg 2N (Bx) + B2N)
(Definition of Bx)
N N2M IN M1+1
(BN + B2N) (For vector subspaces V and W. orthw(V) V v
2M
BN B2N)
(Inductive hypothesis holds for sets N |N| k)
N
N M
+ B
N
This proves our claim that B2M = D By = DNgM By-
Now we are ready to prove the theorem. We begin by showing that any nonzero w E vec(2') is Gar -nvainiar where GM (U) iff w E BB-- Since w E BM + w E W., Vi E M, have from Lemma that any BM Gy-invariant for all M. Then it is easy that
18

---

Published as a conference paper at ICLR 2021
Puli basis:
eigeneectors
Hall selgeneettre
Nchunnel
Gehomal
Achhnnn
Kchumnn
Gavanal
(a) Win
(h) Wenl
Figure 4: (a) 1-eigenspace of the Reynolds operator for the rotation group. The eigenspace has nine basis vectors v E I!?? (stacked). We are representing these eigenvectors [xx33x3 instead to emphasize that these are rotation-invariant. (b) l-eigenspace of the Reynolds operator for the color-permutation group. The eigenspace again has nine basis vectors v E R but we represent them in 3x3xx to emphasize that these are invariant to permutations of color channels.
any nonzero is GM-invariant iff it is G--invariant for all i M. It is possible to have Bar {0) implying that there is no nonzero w vec(X) that is -iviirarian
Next note that for all N M, we have Bx C Bar (using the definition of Bm). Then, their direct sum is the smallest subspace containing all such By and thus, @N2M BN BM From claim earlier, this implies that 32M NDM By S Bas. Finally, we have Bar orth (BM) S Ba for all M. Thus, we have proved that any nonzero w By also lies in By and hence is invariant to Ga.
In the sequel, we will prove that any w E Bas is not Gj Gy-invariant for any j E {l...., m} \. M. Let P 2 M. Then is clear that 22M + N2N BN 2 Br, which implies from the first part of our proof that any w E vec(A')) that is Gp-invariant lies inside BJM. The orthogonalization step ensures that Ba B2M and thus, Ba Bp and B& O Bpp = {0). Hence there is no nonzero w E BM such that w Gp-invariant. This applies for all supersets P224 M.
Finally, we consider supersets of M of the form P = M U {i} for j {l..... m} } \ M. If nonzero BM invariant to Gj. then will hold that is invariant Gpr, P' M, resulting in contradiction. Hence, we have that if BM * {0), any w E BM \, {0} is -invariria but not Gy fy-invariant for any {l.....m} M.
C EXAMPLE CONSTRUCTION OF CG-INVARIANT NEURONS
In this section, we will present a detailed example of the construction of CG-invariant neurons. Consider 3 image with 3 channels, thus X' 3x333 Then, convolutional filter X R3x3x3 multiplies elementwise with the image x E X.
Consider groups Grot and Geot. the former rotates the image patch by 90-degree multiples and the latter permutes the color channels of the image. Our goal is to enforce invariance to rotation and color channel unless contradicted by training data. Note that vec(X') R27__
Step 1: Construct I-eigenspace of Reynolds operator for each group. Since we only consider linear automorphism groups, each transformation T in the group can be written as T(x) Tw, where T is matrix of size 272722 and æ E vec(X') Lemma t to construct the Reynolds operator by averaging over all the linear transformations (or corresponding matrices) in the group. Then, we can use standard methods in linear algebra to find the 1 1-eigenspace of the Reynolds operator (i.e., find the eigenvectors with corresponding eigenvalues equal to 1).
2? Given group, we can directly use
Let Wix and West be the I-eigenspaces of the Reynolds operator the groups Gos and Gool re- spectively, Figure shows these eigenspaces with the eigenvectors arranged in g3x3x3 instead of 2² The figure shows that the eigenvectors in Wist are invariant to rotations of 90-degree multiples whereas the eigenvectors in Wool have the same values across the RGB channels, and thus invariant to permutation these channels. Lemma proves this invariance-prope property for the I-eigenspaces of the Reynolds operator of any finite linear automorphism group.
19

---

Published as a conference paper at ICLR 2021
M {rot, col}
basis vectors
Rehunnei
M {rot}
M {col}
6 husts sectors
6 bosis becfors
Gohmee
Rehenel
Gehonna
Reheneo
M 0
12 basis weetors
Rchammal
Gehanna
#ohannel
Figure 5: The subspaces Ba for all M S col). For instance, [(roc on the top has basis vectors (represented in R3x3x3) and each of these vectors are both rotation-invarian and channel-peree peemuttttr invariant. the other hand, [ree (of dimension 6) is rotation invariant but strictly not Shaannel-permttaiie nor channel permuttttoo invariant. All the basis vectors together cover the entire space R27 (i.e., dim col)) dim (B(r0)) (io(B( dim(Ba) 3 6 27).
invariant. Finally, the vectors in B3 neither
Step Construct BM for all M C {rot, col). Now, given Wfa and Woats will construct basis for the subspaces By for all M S {rot, col} using Theorem
1. Set M = (rot, col}.
B [rot,col) = Wsot Weol
B [rot,col) B (nor,col)
(because (rot.oo))) {())
The intersection of subspaces Wiot Wool be computed using standard methods in linear algebra. The subspace B [rotccol) with basis vectors is visualized in the topmost level of Figure 5) As before the basis vectors of the subspace are represented in 3x3x3x3 It is clear that the basis vectors are invariant both rotation and permutation of the channels. This property will hold for any linear combination of the basis vectors, i.e., for any w E cool.
2. Set M (rot).
B [roi) = Wixc
mo) orthg (1x) (B (ml))
orthy (10) (B(rot)
(because B B1((e) ((oot,ol)))
The subspace Bi consists of vectors that are invariant to rotation but also includes vectors that are invariant to both rotation and channel-permutation. Thus, need to remove from B (or) the projection of (ree) B [rooccol)--
20

---

Published as a conference paper at ICLR 2021
The subspace B (mo) with basis vectors is visualized in middle level of Figure 5 It is clear that the basis vectors are invariant to rotation but not invariant to Again, this property holds for any linear combination of the basis vectors.
3. Set M {col}.
[col] Weol
B [col} orthg (oo)) (coo))
orth (ee (col))
(because [3 = (rot,coo))
The subspace [col)) is obtained in a similar fashion. [ has 6 basis vectors and is visualized in middle level of Figure 5 It is clear that the basis vectors are invariant to Channel-permutationn but not invariant to rotation. This property holds for any linear combination of the basis vectors.
4. Set M U.
Bg = orth (vec(x)))
where B2 crot. + (rot) @ [col)- The subspace By represents the rest of the space that neither rotation-invariant channel-pent secpinl--eemmttttnn-nnaarrae This subspace has 12 basis vectors and is visualized in the bottommost level of Figure
Finally, we have B = 4 subspaces (enumerated above) with a total of 27 basis vectors covering the entire space vec(.t) IR."
Step 3: Neuron construction. For each subspace Bas M C {rot, col}, we denote BM as the corresponding matrix with columns the basis vectors of the subspace Bas. As described above any linear combination of the basis vectors of Ba are invariant to all groups indexed by MM and nothing more (e.g., (ro) consists of vectors invariant rotation but not invariant to -hrmnal--ermutaatoon)
In the following, we consider single neuron and drop the subscript from WM.h (where h repre- sented the h-th neuron in Equation (10)). Recall that war E Rd are the learnable parameters of the neuron corresponding to each basis vector of the subspace Ba, and dx is the dimension of the subspace By. Then, W (ror, E IR3 represents the coefficients in the linear combination of the basis vectors B [rotcool) The linear combination given by the matrix-vector product B soot w crot.co)) Similarly, w (mi) E R6, (col) E RR, wg E I represent the coefficients the basis vectors in the columns of B [ma). B (uul] and Bg respectively.
Then, a CG-invariant neuron is given by,
[(x) = x w b,
where
w B coll W (rot.ol)) + B (1o1) (rat + (col) + Baws
and W coo, - (col), Wp. R are the only learnable parameters. The total number of parameters 28, same as that of the standard neuron with input æ E R?7
Now, if for example the optimization finds w (not.col) + 0, w (m)) 0, (col) 0 and wy 0, then the neuron r(.) is invariant to both rotation and channel-permuuatiion.
Our regularization in Equation [T forces the optimization to find maximum invariance as long as
training performance is unaffected. A more comprehensive example of the computation of the penalty given Appendix
D PSEUDOCODE FOR THEOREM 3
We present the algorithm for Theorem 3 in Algorithm[1 I The loops in the algorithm iterate over the different subsets M C .1,...,7 m) in descending order of their sizes. The worst-case complexity of the algorithm is exponential m (to iterate over all subsets). However, since the algorithm stops after finding all the basis for the space vee(X'), ), it is unclear if the worst-case runtime occurs in practice.
21

---

Published as a conference paper at ICLR 2021
128x26x26
128x24x24
Image: 3x28x28
64x28x28
64x28x26
128x1
50x1
Output: 10x1
Convolution (3x3)
Convolution (3x33 gui S
Max- Pool (2x22
Sum-pool (24x24)
(2x2)
Oun Ouise Surtinich
Figure 6: example architecture of CG-invariant CNN architecture.
Moreover, the algorithm only needs to run once for given collection of groups and the results can be reused in all experiments.
Algorithm I: Procedure to construct basis for the subspaces BM of Theorem
Input: Left 1eiggenspaces of the Reynolds operator Wi, W2...., Wm for groups G1, G2..... Gm respectively.
Result: Basis for nonzero subspaces Ban Baaa...... ......... BMM with dx and M, C [1.....m,
// Initialization
1 <- m:
< 0:
// counter for the subspaces. /* will denote the size subsets M S fl....,,m, m), denoting the level of invariance,
1;
while / 2 do
P: (M M M (1]....
for M in do
if M + then
BM t ;
/* Intersection of 1-eigenspaces.
else
Used to find the subspace Bp. // Direct sum of subspaces of supersets of M.
BM < vee(X")
end
BэM + UNMM Bx
Вм + orthg (BM);
if B& # 0 then
Mr M
Record current subspace to return x/
k + k 1
end C
C + Ba if dim(C) dim(vec((X) then break while:
/* Found basis for the entire space. x/
end end 1 1-1 end
k - 1: return BM B BMs
B t-
/x Number of subspaces.
E
ARCHITECTURES
E.1 IMAGES
An example CG-invariant CNN architecture is depicted in Figurelo Majority of the CNN architecture remains the same with the exception that the filters are obtained using the bases of the subspaces obtained in Theorem for the given of groups. Figure 5 shows example subspaces along with
22

---

Published as a conference paper at ICLR 2021
r()
Input Sequence E gaxp
Output
r
Pointwise FF network
Fully Connected
CG-Invarian FF Layer
layer
Figure 7: An example architecture of CG- CG-invariant feedforward network.
their basis vectors when the groups are just Gror and Goolors and the kernel size 3 x 3 applicd over input with 3 channels. One can similarly obtain these subspaces for other groups, different kernel sizes and different number of input channels. Then, the filter is obtained as a linear combination of these basis vectors, where the coefficients form the learnable parameters. The G-invariance of the filter then depends upon which of these coefficients are nonzero. Once the filter is obtained, it is convolved with the image or the feature maps. This will ensure that the model can be CG-invariant to transformations of smaller patches in the image if needed.
Max-pooling layers function in the standard way. After all the convolutional and max max-pooling layers, we use a sum-pooling layer over the entire channel to ensure that the model can be invariant to the transformations (e.g., rotations) on the whole image needed. Finally, any number of dense layers can be added after the sum com-pooing layer.
In our experiments, we use the three groups Gree Gester and @vertical flip construct the subspaces for the filters of the first convolutional layer, but remove Geolor in the further layers we do not wish to be invariant channel permutation after the first layer.
E.2 SEQUENCES
A CG-invariant architecture for sequences is depicted in Figure 7
Consider a sequence X ........ E..]] E Tg* of length n and groups GI...., 9m as before. the following discussion, we will assume that the groups are permutation groups over the sequence elements. However, one could also consider other groups over X.
First, each element of the sequence is passed through shared feedforward network Ø that returns representation Z E IPp xm, Then, Theorem finds the bases for BM, M S {L,..., m) until all the p'n basis vectors are found covering the space Rp'xn, The weight vectors for the h-th neuron of the CG-invariant layer is obtained as a linear combination of these basis vectors via the learnable parameters Z (Equation (I0). Finally, any number of dense layers can be stacked after the CG-invariane layer for the final output.
REGULARIZZTION
F.1 EXAMPLE
Figure shows an example computation of the penalty in Equation (12) The example considers an image task with M C {rot, col, vflip). The subsets are arranged according to their levels of invariance, i.c. by the size of M). For example, the topmost cell {rot, col, vflip) denotes the subspace with all the invariances whereas the bottommost cell & denotes the subspace with no invariance.
3 groups: Giot Gool, Gitip- Each cell in the figure shows subset
The colors indicate the state of the parameters Ω at single point in the optimization. The cells colored green or red depending on whether the subspace is used or unused respectively, i.c., whether the parameters corresponding the subspace nonzero not. The least invariant subspaces used
23

---

Published as a conference paper at ICLR 2021
(rot, vilipp
LEVEL
+1
+1
+1
col)
feot, vilip)
{col, vilipp
LEVEL
(rot)
(col)
+1
(vilip)
LEVEL.
0
LEVEL
Figure 8: (Best viewed in color) Describing the computation of the penalty. The cells denote different subsets M S {rot, col, vflip). Red colored cells denote that the parameters corresponding these subspaces are zero (i.e., the subspaces are unused) and the green colored cells denote otherwise (i.e., the subspaces
used). In this example, the least invariant subspaces used are in Level The penalty counts all the subspaces (used or unused) that are in higher levels (i.e., with M > 1) and adds it to the number of subspaces of the same level that are used.
at this point are in Level (i.e., invariant single group). The penalty counts (a) all subspaces with higher levels of invariance irrespective of whether the subspace is used not, and (b) counts all the used subspaces with the same level of invariance. The former penalizes the use of subspaces lower in the partial order and ensures that subspaces with higher levels of invariance used. The latter approximates the effort to reach higher level of invariance.
F.2 DIFFERENTIABLE APPROXIMATION
Recall that the regularization penalty R(22) in Equation
12 is given by,
R(22) = f(()) = (M,: M. > 4 1 isis + Σ M 18i8
Hlw.M..111 11 0}, (16)
where min [M 1(|lM, 0}, IsisB:.
R(22) is clearly discrete but can be approximated by a differentiable formula. First, we replace the indicator function 1f2 > 0} in Equation 16) with the approximation i > 0} = 72/(T2 + 1), where > 1 temperature hyperparameter.
Then, in order to obtain R(2)) = (S2) for the minimum defined in Equation 16 we use the following recursion: R(S2) Rt, (52), and
(2)) = (1 - (22) R + 3(( 1,
with the base case (12) 0, and ((( i1E N.IN 15KB I 0}. ((2) is
approximately one if least one neuron h has nonzero NN parameters for some N; {1. (1..... m) of size (i.e., with I groups). Then the recursion finds (S2) with defined as the size of the least invariant subspace used.
F.3 LIMITATION OF R(22)
As explained in Section 4.2 there could be overgroups (out of the total 2 groups considered) with different levels of invariance, but penalized similarly by Equation (12) This scenario arises only in cases when Theorem does not construct subspace basis for all the nd overgroups, i.e., the basis for vec(Xt) is found prior to that. In this section, we provide such an example scenario with sequence inputs and the transposition groups considered in Section
24

---

Published as a conference paper at ICLR 2021
M (1,55 sid (ol.
Levels of zero subspacrs
= ((6.))) ( (1)
M = ((. (6.j: (a) (m-1)
basis vocton
basis toteton
busiá Lsectoo
basis weteon
indexing the (2) transposition groups Gü,j over sequences of length n= 5 and dimension d = 1. Each of the subspaces Bas is of dimension For each basis vector shown above, elements sharing the same color have the same value. At the topmost level, we have the subspace with most invariance, i... invariant to the full permutation group S,,. Following many levels with empty subspaces, we have subspaces BM, for Mp = f(i,j) j.j [n] (p), é < 5). where [n] (1...., ..) In other words, the subspace MM, is invariant to all transpositions except those that move index p. Note
Figure 9: (Best viewed in color) The subspaces BM for different M S ((i,))
that we have covered the entire space R with these independent subspaces of dimension 1.
Let E X Rd be a 1-dimensional sequence of length n. The transposition groups are (G., Seiiiinnnnn where Gi.j = (Tuemuyy Tiy} and Te, swaps positions and j in the sequence. Given these (²) groups, we can use Lemmas 1 2 and Theorem 3 to find the invariant subspaces By for subsets M C ((,,) 1 < < S n indexing the transposition groups. The basis vectors for these subspaces constructed for sequence length n 5 are visualized in Figure
There are n I-dimensional subspaces. Let the vectors bio b b (n-11 denote these n basis vectors. The notation \A means that the vector has the same value for all positions & E (1,...,,)} \ (cf. Figure 9p. Let and note that any weight vector R can be written as,
on o + azb asbye2) + aab asb
(17)
where R
From a quick read of Figure we see that the weight w' obtained by substituting a' in Equation (17) is such that w/ w/ Wi and w/ w/. For any input E R$, the neuron a (w x + is invariant to any permutation #1, 4g and æıs and, transposition of æ2 and 344. The penalty R(w") = 3 as there are 2 subspaces used at the lowest level and there subspace above the lowest level (see Equation (12).
Let a' = -1,,0,,0,11
Now let ax (1, 0, 1, 1.5)" The weight w" obtained by substituting a in Equation 17 is such that w/" = w = w but w/y + w/. For input æ E R the neuron a (w x + b) is invariant to any permutation of x² 2n and zz but sensitive the transposition x2 and x4. The penalty R(w") as the same subspaces are used as before.
In the first case, with all the parameters being equal (especially ag ag)) w' lies in a smaller (more invariant) subspace of span(b.g. (((2). b (4)). In the second case, since oy A og the same does not hold for w". The penalty R((.), which only counts the subspaces used (in this case, bia. (,2 and b (4) ), is unable to distinguish between these two weight vectors w' and w", one clearly more invariant than the other.
25

---

Published as a conference paper at ICLR 2021
In this specific case with transposition groups over sequences, one could add another penalty term that regularizes the parameters a; to share the same value (e.g,, entropy regularization of the parameters). We leave further investigation into the general scenario with other groups for future work.
G DATASETS AND EMPIRICAL RESULTS
G.1 IMAGES
Datasets. We consider the standard MNIST dataset and its subset MNIST-34 that contains only the digits 3 & alone. We chose to experiment on the MNIST-34 dataset since it does have digits that can be confused with a rotation transformation (e.g., 6 and 9) or are invariant to some rotations (e.g.. 0, and 8), thus avoiding any confounding factors while testing our hypothesis. We also experiment on the full MNIST dataset to depict the scenario when the data does contain these contradictions. First, we modify all the images the dataset to have three RGB color channels and color each digit red initially, i.e., all active pixels in the digit are set to (255, O, 0). We sample X(hid) from this dataset with the target digit as its original label.
Groups. We consider m = 3 linear automorphism groups on images: the rotation group Goot (7((0)) T(90"), TT180"), (T(270")) } that rotates the entire image by multiples of 90' the channel- permutation group Goolor = (T JogSs that permutes the three RGB channels of the image, and the vertical flip group Ivertical-fiip = (T(0) T(0) that vertically flips the image.
Tasks. For both MNIST and MNIST-34 datasets, consider 4 classification tasks where each task represents the case when the target Y is invariant to a different subset of {9ru, Ivertiall Geoler i.e. invariant to all three groups, to two, to one, invariant to none (and sensitive to the remaining groups). We consider the following subsets I: i) {rot, color, vertical-flip). ii) {rot, vertical-flip) iii) {color), iv) 0. and generate GI (UsezG,) as the join of the respective groups. Setting D = {rot, color, vertical- flipp I, we generate GD = (UzEDG,) from the join of groups in the complement set (our choices ensure that Gr I 9DUZ, thus satisfying the conditions of Theorem 2).
Training data: X is the canonically ordered (standard) image in the MNIST datasets. Recall that the training data is sampled via an economical data generation process. Thus the training data consists only of images under transformations that have an effect on the label, i.e., transformations from GD.
Recall from Equation 2 that the observed input is obtained as X = TUzUU ( transformation of the canonical input X Since Gz < GD (by construction). we have that any Tüg,Up Toy UUp Tu,, i.e., the transformation can be decomposed into one transformation from GD followed by another transformation from GI- U+ Up the subscript indicates that the transformation Tuguup E Gz also depends on Up. Under the assumption of economic sampling of training data, in all our experiments we sample single value for Tuş Up E Gz: we simply use Tuguo = Tuleniit (one could consider any other transformation in G7 as well).
In conclusion, we obtain the observed image X in the training data by applying random transfor- mation from Gp to (hid) and then applying constant transformation (c.g., Tidemiit) from Gr to the result. The task is to predict the original label of the image (i.c., the digit) and the transformation Top that was applied to obtain X (recall from Equation (3) that Y is a function of both (hid) and Up).
For instance, if Gz = Goo vertical-liip and GD Geolor. then the training data consists of upright and unflipped images (as Teg is chosen to be identity transformation) with different permutations of the color channels (since random transformations are sampled from GD) resulting in digits with different colors. Then, the task is to predict the digit and its color.
Extrapolation task: The extrapolated test data consists of samples from the coupled random variable X U (Definition IT. Unlike the training data that was economically sampled (i.e., with a single transformation from Р7). the extrapolated test data is obtained via the full range of transformations
in Gz. Recall from Definition that X XU,-Ü, = Tū o (hid) As before, we decompose T TrrU0 T Ug Tüp. However, there is no economic sampling for the test data: T T Tyur and Top are sampled randomly from Gz and GD respectively.
26

---

Published as a conference paper at ICLR 2021
Table 2: (MNIST-34.) Validation and Extrapolation test accuracies (%) with 95% confidence intervals for different CG-regulariattion strength À in Equation (TT). À is chosen only based on the validation accuracy: maximum À with validation accuracy within 5% of the best validation accuracy (bold values indicate the performance of this choice of X).
I [rot, color, vilip)
rolpooor,xllip
roLvflip
color
8
Model
Val. ace (5)
Test acc (5)
Val, acc (9)
Test acc (5)
ace (5)
Test ace (8)
ncc (5)
Test aoc (9))
VGG CG-reg
0.0
99.94 (0.17)
49.51 (.36)
99.83 (0.09)
43.57
97.15 (0.27)
15:71 (5,46)
95.65 (0.39)
96.30 0.68)
0.1
99.92 (0.09)
78. (25 75)
99.86
73.98(16.35) 35)
96.88 (0.77)
96.27 (1011
94.95 (0.54)
95.56 ( (0.61)
1.0
99.71 (0:22)
85.42 (29.00 66)
99.77 0.25)
75.64 (20.52)
96.12 1.26)
96.20 1.11)
94.01 1.51))
94,42 ( 1.38)
2,0
(0.33)
94.88 (0.84)
99.56 0.66)
82.59 (28.92)
95.23 (0.99)
95.61
94,05 (1.50)
94.49 L.49)
10.0
99.00 ( 1.18)
94,89 ( 7.499) 98.43 2,00)
(7.11)
93.34 (842)
94.16 (644)
88.42 (19,36)
88, 68 (20.13)
Table 3: (MNIST.) Validation and Extrapolation test accuracies (%) with 95% confidence intervals for different CG- CG-reuularization strength À in Equation [II). À is chosen only based the validation accuracy: maximum À with validation accuracy within 5% of the best validation accuracy (bold values indicate the performance of this choice of X).
(rot, color, vElip)
yotp
rot.yflip
color
Modal
Val. aoc (5)
Test ace (9)
Val. agz (96
Test scc (9)
Val. uoe (SB)
Test ace (%)
Val. apc (58
Test sox (9)
VGG + OGi-reg
0.0
(0.17)
11,93 (1.87
98.80 0.14)
25.81 (0.92)
91.50 (.35)
(219))
91.80 (0.60)
(1.60))))))
91 (1 (0.32)
(.05)
(0.17)
30.12 (4.05)
90.11
88. 88.30 (3.66
(1177)
1.0
98.49 0.24)
44.23 (15.45)
98.29 (0.21)
40.13(4.8)
90.24 ( 0.46)
(0.29(0.99)
88.76 (.28)
88.65 11,00)
2.0
98.45 0.13)
(2.29)
98.34 0.34)
47.14 (15.17)
89.98 ( 0.24)
89.71 (0.89)
89.50 L.35)
89.45 1.43)
10.0
0.74)
(2.76)
95.21 6.55)
6.02)
88.80 2.11)
$8.69 (2.11)
1.04)
0.44)
In conclusion, we obtain the observed image X in the test data by applying random transformation from GD to ((hdd) and then applying a random transformation from Gr to the result. The task is the same as in the training data: to predict the original label of the image (i.e., the digit) and the transformation Top that was applied to obtain X. Note that the label does not depend on the transformation Tūy E Gr that was applied.
Once again, if Gr- = Grot, vertical-lipp and Gp = Gcolor, then the extrapolated test data consists of images randomly rotated, flipped and channel permuted, while the task is the same: predict the digit and its color.
In order to evaluate the models, we use 5-fold coss-validation procedure as follows. We divide the training and test datasets that are pre-split in MNIST and MNIST-34 datasets into 5 folds each. We use the above procedure to transform the training data and the test data. Then in each iteration i of the cross-validation procedure, we leave out i-th fold of the transformed training data and i-th fold of the extrapolated test data. Further, we use 20% of the training data as validation data for hyperparameter tuning and early stopping.
Baselines and Architecture. For all methods, we use a VGG architecture (Simonyan and Zisser man 2014) with 8 convolutional layers each having 128 channels except the first layer which has 64 channels. All convolutional layers have a receptive field of size 3 x 3. stride I and padding I. max-pooling layer is added after every two convolutional layers. Two feedforward layers the end give the final output. We compare our approach with the standard CNNs and CNNs (G-CNNs) [Cohen and Welling 2016) with the p4m group. We modified G-CNN such that has invariances to all the 3 groups strictly enforced via a) coset-pooling (Cohen and Welling (016) after each layer and b) adding together the input RGB channels. For our approach, we replace the standard convolutional layer in the VGG architecture by CG-invariant layers with bases constructed from Goor, Goolor and Avenical-fip- An example architecture with only 2 convolutional layers is shown in Figure
We optimize all models using SGD with momentum with learning rate in {10-3 2,0-2.0-33 10-3, 10 10-4) and a batch size of 64. We use early stopping on validation loss to select the best model. Further, use validation loss to select the best set of hyperparameters for each model. We choose the maximum value of À with validation accuracy within a 5% threshold of the maximum validation accuracy
27

---

Published as a conference paper at ICLR 2021
Table Sequence tasks. The first column defines the target Y for given sequence (X;) The second column denotes Gz, the group of transformations to which Y is invariant. Recall that Gz is constructed as the join of subset of (22 transposition groups.
Target Y
Gz
GD
Y 1
10
Xi
(f9., ((iish)
{Id}
2 = 21-22 Xi
{Id}
Ymsk-3 - - (X2i X2--1)
((9 ( (5icH42R55)
{Id]
Y 1usk-4 = -i -oi-ITT==1 1(x; , 2 20)
[Id]
((9ghhssss)))
obtained from any value of Tables 2 and performance of the model. We observe that X
show the effect of regularization strength on the 10 performs considerably well across all tasks.
G.2 SEQUENCES
For sequence tasks, we generate (hid) = (x:)) as a sequence of n = 10 canonically ordered integers uniformly sampled with replacement from fixed vocabulary set .1....,99 99). The canonical ordering is fixed for a given set of integers sampled: the corresponding sequence (hidd) is always either in an increasing order decreasing order.
Datasets.
Groups. We consider m = (g) permutation groups for all the pair-wise permutations: 91,2, 92,3, $1,3.... In-Ln, where Gi.j (Tubenity Tast and Ti,j swaps positions é and j in the sequence. For I ()), (2, (1.3)..... (n 1, n)], }. 9r is defined before as the join (U(,)) Gig)- We choose 4 different subsets I of the given m groups indicated by the second column of Table 4 For our choices I + 0. we set = 0 to ensure that Gz I GDUZ, i.c., Gr is normal subgroup of Gouz-
Tasks. The label for the sequence X(hdd) is obtained by applying an arithmetic function to (hidd that invariant the chosen group Gz. The arithmetic functions are given the first column of Table Yusk-1 is invariant to any permutation of the input elements X, 1 < S n. Yusk-2 is invariant to any permutation of input elements X, with indices > but sensitive to permutations that move X1- Y is invariant to permutations that move elements at even indices to even indices and elements at odd indices to odd indices respectively. Finally, Yusk-4 is sensitive to all permutations (i.e., no invariance).
Training data: Recall that ( a sorted order. Since the training data sampled economically, consists only of sequences under transformations that have effect the label, i.c., transformations from Gp. The observed input is obtained as X = Tuz,Up (hid), a transformation of the sorted input X (hid), Since Gz GD (by construction), we have that any TUz,Up = Toglos Tu. ie.. the transformation can be decomposed into one transformation from GD followed by another transformation from Gr. U/ Up in the subscript indicates that the transformation TUgiu E Gr also depends on Up. Under the assumption of economic sampling of training data, in all our experiments we sample single value for Tuşiup Gz: we simply use Tegiu Tideniity
In conclusion, obtain the observed sequence X in the training data by applying random transformation TV E GD to (hid) and then applying a constant transformation (e.g., Teteminy) from Gr to the result. The target Y is computed by applying the arithmetic function corresponding the task (see Table 4 to Tup o X (hid) (recall from Equation (3) that Y is a function of both ( and Up).
Extrapolation task: The extrapolated test data consists of samples from the coupled random variable X U (Definition T). Unlike the training data that was economically sampled (i.e., with a single transformation from Рт). the extrapolated test data is obtained via the full range of transformations in Gz. Recall from Definition that X XU = Tū o (bid), As before, we decompose T Tr T Uz Tüp- However, there is no economic sampling for the test data: T T Touu and Top are sampled randomly from G7 and GD respectively.
28

---

Published as a conference paper at ICLR 2021
Table 5: (Sequence tasks) Extrapolation test accuracies (%) with 95% confidence intervals for all the models (bold means p < 0.05 significant). The standard sequence models cannot extrapolate when I + 0 whereas the forced G-invariant models cannot unleam the invariances and fail when I & m...
Gz.
((Gaphssessn)
((G,hhs ((
(Id)
Model
DeepSets Zaheer al. 2017
100,00 ( 0.00)
2.36 (2.37)
0,97 ( (0,60)
16.12 ( (8.21)
Janossy pooling Murphy
2018
96.64 3313)
9.55 (1.61)
0.78 (0.52)
21.22 ( (2.94)
Set Transformer (Lec ct al.
2019
99.57 ( 0.33)
10.68 ( (1.4))
0,75 ( (0.28)
23.38 ( 1188)
Transformer Vaswani
2017
20.26 (32.08)
12.15 (16.05)
0.85 0.37)
100.00 ( 0.000)
GRU (ho al 2014
0.48 0.48)
0.47 (0.38)
0.90 ( (0.77)
99.41 ( 1.58)
FF + CG-reg. (ours)
100.00 ( 0.00)
42.08 (18.99)
71.85 (26.61)
95.70 ( (3.05)
Table 6: (Sequence Tasks) Validation and Extrapolation test accuracies (%) with 95% confidence intervals for different CG-regularization strength in Equation (TT). À is chosen only based on the validation accuracy: maximum À with validation accuracy within 5% of the best validation accuracy (bold values indicate the performance this choice of X).
6r
((0tg)ggeeee Iigeesid
[[R
(Md)
Mudel
Vall aue (9)
Test scc (9)
Val. noz (9)
Test avc (R)
Vall. acc (5)
Text ace
Val. ocz (S)
Test axc (56
CG-reg.
0.0
(34.15)
(87.19)
100.00 0.00)
(74.04)
99.95 (0.10
22.78 (14.52)
99.92 0.27)
99.86 (0.15)
0.1
80,83 (81.04)
59.18 (91.12)
100.00 0.00)
65.13 (80.45)
99 99.99 (005)
60.66 (19.83)
99.95 00100)
99.98 (0.05)
1.0
80.72 (84.48)
80.03 (87 .2)
99.04 (.22))
61.81 (66.24)
100,00 0.00)
68.34 (36.98)
99.81 0.55)
99.76 (0.65)
2.0
(72.85)
77.97 (48,87)
0.05)
69,20
(0.53)
10.0
80.97 (74,10)
62.83 (100.17)
98.14 (2.71)
42,08 (18.99)
100.00 0.00)
71.85 (26.61)
95.56 3.34)
95,70 (3.05)
100.0
100.00 ( (0.00)
100.00 ( 0.00)
15.65 (3.63)
2.29 (0.96)
93.42 (14.90)
27. 64 (24.85)
65.92 (10.38)
65.42 (10.30)
In conclusion, we obtain the observed sequence X in the test data by applying random transformation Tup E GD to (hid)) and then applying random transformation from G7 to the result. The target Y is computed in a similar fashion as in the training data by applying the appropriate arithmetic function to TUo o X(bid), Note that Y is invariant to Gz-
Example: Consider the the first row of Table with I ((.J)hsisssm i.e., contains all the m = (?) groups. Then, the group Gr is simply the full permutation group over n elements. The The sequences in
target is defined as the sum of elements (which is fully permutation-invariant the training data are always sorted (because of the economic sampling of training data), whereas the sequences in test data have arbitrarily different permutations (by sampling random transformations from Gz). The task is simply to compute the sum of the elements of the sequence.
Sizes of the training data and the extrapolated test data are fixed at 8000 and 2000 respectively. We repeat all the experiments for 5 different random seeds.
Baselines and Architecture. We compare our approach with a) standard sequence models, specifi- cally Transformers (Vaswani et al. 2017) and GRUs (Cho et 2014), and b) forced permutation- invariant set models, specifically DeepSets Zaheer et al.) 2017) ), SerTransformer (Lee et al. 2019)
and Janossy Pooling (Murphy et al. 2018). An example of the proposed CG-invarintt feedforward
architecture is depicted in Figure 7
We optimize all models using Adam (Kingma and Ba 2014) with an initial learning rate in No-ptimiie (10-2.10 100-,,00,1100-- 10-1) and batch size of 128. We use validation loss for early-stopping and to select the best hyperparameters for all models. Once again, we choose the best value for the CG- regularization strength À by choosing the maximum value of À with validation accuracy within 5% of the maximum validation accuracy obtained from any X. Tshles the effect of regularization strength the performance of the model. We observe that although À 10 performs comparably to the rest in validation accuracy and is chosen consistently. it does not achieve the best possible extrapolation accuracy.
29

---

Published as a conference paper at ICLR 2021
Table 5 shows the complete set of results for all the models. The table clearly shows the issue with standard sequence models (cannot extrapolate when I * 0) and the issue with forced G-invariant models (fail when I fl...., m)). In Table 4 of the main text, show the results for the best model out of all the permutation-invariaa models in the column Best FF+G-inv.
shoow
30


Reviews:
[{"review_id": "OhfiOPbsiDk", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an interesting and potentially quite impactful and valuable idea, which I believe is novel.\nThe idea is: instead of specifying invariances by hand in the architecture of a network, we can instead specify a set of possible invariances, and regularize the model to favor more invariance.\nThe authors describe how to structure and regularize a DNN in this way, and provide proof-of-concept experiments.\nThe experiments show that the proposed method outperforms networks that are fully-invariant or non-invariant when the true data is partially-invariant.\n\nUnfortunately, there are a number of weaknesses which lead me to recommend against acceptance.  In no particular order:\n1) The crucial \"unseen is forbidden\" hypothesis is vague and seems to be a bit of a strawman.  \n2) The framing of the paper seems to oversell the method in a way that makes the contribution less clear. \n3) The writing is not very clear.\n4) The experiments seem to be only proof-of-concept in scenarios where the method is designed to work.  \n5) The method seems to incur an exponential cost, but this is not discussed.\n\nElaborating:\n1) The authors claim that, because DNN behavior is undefined on unseen datapoints, the \"unseen-is-forbidden learning hypothesis is currently preventing neural networks from assuming symmetric extrapolations without evidence.\"  This claim is stated in various forms several times, but never made very precise, and it is crucial in motivating the authors' approach.  Roughly, I take the authors to be claiming that (i) the correct way to \"extrapolate\" is to assume that: transformations that were not observed to change the target distribution should be assumed to NOT change the target distribution, (ii) DNNs will not extrapolate in this way by default, and must be explicitly designed to do so.  \nThese claims (or whatever the authors actually mean) need(s) to be stated explicitly, and with appropriate modesty.  After all, both (i) and (ii) seem contentious.  \nThe claim about an \"economical data generating process\" supports (i), but is itself somewhat vague and dubious, and should be discussed in the introduction as motivation for (i).\n\n2) The authors claim that their method can discover invariances without any data supporting them.  And their abstract claims: \"Any invariance to transformation groups is mandatory even without evidence, unless the learner deems it inconsistent with the training data.\"  But in reality, the authors specify a small number of possible invariances which the method selects among (in a soft way).  And the data is used to guide this selection process.  So in reality, the designer is in charge of specifying a (restricted) set of (possible) invariances.  So like previous works on enforcing invariances, it places a  burden on the designer to identify plausible invariances.  Overall, I found the framing in the work to be \"the model discovers invariances by itself without any data!\" whereas a more neutral version would be \"instead of enforcing a set of invariances, we propose a set of *possible* invariances, and assume that any input transformations that are not observed to affect the label should be enforced\"\n\n3) Besides the above issues (vagueness of \"unseen-is-forbidden\" and related discussion (1), overselling (2)), there were several other issues of clarity.  The paper is not poorly written overall, but is much harder to read and understand than it needs to be.  Some specific issues are: \n- The results in Section 4 are presented with insufficient context or intuition.  Theorems are stated without any proof intuition and should reference proofs in the appendix.  The intuition for the penalty arrived at (eqn13) is unclear.\n- The flow is sometimes unclear.  For instance, \"Learning CG-invariant representations without knowledge of G_I. \" should be a subsection, not a (latex) paragraph, and should explain what the point of the subsection is before diving in.  The authors seem to be using (latex) paragraphs (i.e. beginning with bolded phrases) as subsections and paragraphs beginning with italicized phrases as (latex) paragraphs.  I suspect the paper was edited to fit into 8 pages without removing sufficient content.  This impedes the flow and sacrifices clarity.\n- I think a graph showing the data generating process would be much clearer than the current explanations (e.g. eqn4/5)   \n- it is unclear what equation 7 is saying... the text above makes it seem like a definition of a goal, but the following paragraph treats it as an assertion that the goal is possible to achieve.  \n...Overall, I recommend stripping out some of the mathematical details and using more words and diagrams in the main text to describe the underlying issues/motivations/methods.\nThe overall story should be made clearer (e.g. by addressing (1) and (2)), and more space should be devoted to linking each part of the paper into the overall story.  \n\n4) The experiments are synthetic tasks where the correct invariance group is included in the set of invariances being searched over.  I don't think that showing that this method can bring some benefits on a real task is an absolute requirement, given the novelty of the approach.  But without more meaningful results, the paper is held to a much higher standard.  Even for synthetic experiments, these are rather weak; for instance, it would be interesting to see whether/how the method degrades when we consider much larger sets of possible invariances.\n\n5) It seems like the method might require including a set of parameters for each of the possible 2^m invariances.  Is this in fact the case?  If not, why not?  If so, it should be discussed as a limitation. \n\n\n-------------------------------\nSuggestions/Questions:\n- In Section 4 paragraph 1, are G-invariance and G_I-invariance used interchangeably?  This was confusing.\n- say what I and D are as soon as they are introduced (top of page 4).\n- Typo: \"a somewhat a\"\n- Why a \"nonpolynomial\" activation function?\n- The definition of \"almost surely\" at the bottom of page 4 is not correct (it is possible to sample probability 0 events), and also it should say that samples of Gamma(X^(obs)/(cf)) (not X^(obs)/(cf)) are equal with probability 1 (these are not the same statement!).\n- \"level of invariance\" and \"non-extrapolated validation accuracy\", and several other phrases are not defined and should probably be replaced by something more clear and explicit.\n- It seems like you might need to assume that that different x^(hid) can't be used to generate the same x^(obs) or x^(cf).  If so, this should be explicit.", "extra_scores": {}, "extra_text": {}}, {"review_id": "O6jKFmLOo2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "POST REBUTTAL UPDATE: I am increasing my confidence in this paper from 2 to 3 - I still believe the paper can use some more clarity but enough points have been explained and updated in the draft for me to feel more confident in my evaluation.  I think the ideas in this paper are quite interesting - for this reason I continue to recommend acceptance.\n\nSummary: This paper describes an approach to embedded invariances in learned neural networks through defining linear automorphism groups. They define a fair amount of theoretical machinery for this task, proposing a model of image generation which includes a number of transformations from these defined groups, and defining the notion of a counterfactual G-invariance for the task. They discuss a method for practically learning a useful invariance even if that exact invariance you wish to have is unknown, by ordering subspaces which may be invariant, and discusses the practicalities of embedding these into neural architectures. Some experiments are described in an MNIST setting and on simulated experiments, showing success at embedding these invariances in toy-ish settings.\n\nRecommendation: I’m recommending acceptance for the paper, since the ideas seem interesting, there appears to  be theoretical contribution and empirical evidence, and it is obviously written with care. My hesitance comes on two fronts: I may be lacking some background in the relevant group theory/invariance literature, and it is hard for me to understand a number of important ideas due to the information density in the writing (a result of ICLR restrictions but also some fault of the authors).\n\nStrong points:\n-\tThe paper is very detailed and interesting – while I am not particularly familiar with the group theory side of the literature, it seems like a good idea from a robustness perspective and the authors lay out their ideas carefully\n-\tThe notion of assuming an invariance unless contradicted is interesting at a high level, and provides some meat to the oft-discussed notion of “extrapolation from a single environment”\n-\tI appreciate the bridge made from the theory to the practical implementation\n-\tThe experiments mostly back up the point the authors assert in their theory – larger experiments for a mostly theoretical paper like this are not necessarily required \n\nWeak points:\n-\tMy sense is the authors are having a lot of trouble fitting their ideas into the 8 pages. I sympathize but I also think they can do better on this front – the first two pages can be much more compact, with more space to explicate complex ideas that get swept over quickly\n-\tIdeas which do not receive enough attention or explanation (but should) include: Eq 2, Theorem 3, the design of neural network weights, and even the bare minimum of experimental details. I know the format is short but some of this stuff is necessary, and I believe the authors can do better in terms of fitting important information in. As it is I am confused about some central ideas, even after checking the appendix\n-\tThe notion of “forbidding examples in the learner’s statistical model” carries some intuitive weight but is not precise – what is this model for a discriminative classifier? This can be more clearly explicated\n-\tIt’s not clear how much is packed in the “economical data generation” assumption, or how that is really connected to the method. Please be more clear.\n-\tThe definition of $T_{{U_D, U_I}}$ is not really clear – need another sentence on this indexing in the main body, as well as discussion of ordering!\n-\tDef 1: you don’t actually define what it means for 2 variables to be counterfactually coupled, you just show what a counterfactual coupling is. Please reword this definition.\n-\tThm 3 – this is incredibly dense and I have a lot of trouble parsing this. I’m not sure how to interpret the direct sum – you’re combining all the subspaces which are supersets of M? Also not sure about the end – this is not G_j -invariant for j \\in M-bar. What is M-bar? Is that a Reynolds operator? Then what does it mean for j to be an element of it?\n-\tHow should I pick my groups G_1 … m? Not clear if this is important\n-\tBottom of p6: not clear how these neuron weights are specified – does it matter which layer we are in? what does the product of B_m \\omega_M,h mean – it looks like a subspace times a real number\n-\tSec 5: I really am confused about the relationship between architecture and which invariances can be realizable. There’s not a lot of explanation on this.\n-\tSec 6: it’s very hard to interpret anything in this section without the appendix – work more to make it stand alone\n-\tProof of Thm 1: maybe I am missing some group theory background but I don’t understand this. For instance, there is no explanation of why this $\\tilde{U}_I$ can always be found to couple X^cf with X^obs.\n-\tProof of Lemma 1: Again, may be missing some background. But neither x nor $\\bar{T}$ is mentioned in this proof, so I don’t know where it is going – please be more verbose.\n\nClarifications:\n-\tMiddle of p3 – we can “compose rotations and image flips” – do you mean a union of the two sets of transformations? That’s what is shown in the notation but I may be missing some group theory background here\n-\tTop of p4: not clear how $G_D \\cap G_I \\neq 0$ is possible – is the idea that $G_i \\cap G_j$ might be nonempty?\n-\tBelow Eq 3: “the training data may contaion on a few samples of the variable” – do you mean only a few values of the variable may be observed?\n-\tBelow Eq 3: you use the term environment without defining it, not sure how to interpret it in this context\n-\tBelow Eq 7: should the samples of $\\hat{Y}  \\ X^{(obs)}$ be Y instead?\n-\tBelow Eq 7: in (i) you say you don’t know the group – do you mean for which group Y should be considered invariant? If so, state that explicitly\n-\tIt’s not clear how the statistical assumption at the end of Sec 3 really fits in with the argument, if you’re going to use it need more here\n-\tTop of p6 – you say the eigenspace of the Reynolds operator gives us a way to build an invariant NN, but the Lemma is about a linear operator. Need more description here\n-\tYou say the method in Thm 3 is fast but the power set should grow exponentially – is that a problem?\n\nOther feedback:\n-\tNot sure why you define g as going to the image of the probability – can’t it just be [0, 1]?\n-\tNot sure “unseen is forbidden” is quite right – wouldn’t it be “unseen is irrelevant” or something?\n-\tSpecify whether Thm 1 only applies to linear automorphisms or if it is more general\n-\tThe recursion at the bottom of Sec 4 is unreadable – just put this in the appendix\n-\tBottom of p17 – describe more how the transformations are sampled. I shouldn’t have to work so hard to understand the experiments\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "DiNMrunTgGA", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nA method is given for training neural networks in the presence of a group of transformations, such that the network weights are invariant with respect to any transformation on the inputs which doesn't contradict the training data. Experiments on MNIST and toy sequence data are used to verify that this training method leads to improved extrapolation of predictions to unseen environments.\n\nStrengths:\nThe method introduced seems promising, as it doesn't require training data to exhibit symmetry, but can still verify (or reject) the invariance of data with respect to a collection of candidate symmetry groups. The training method also seems quite lightweight, and shouldn't require significant additional resources to check for the presence or absence of symmetry.\n\nAlthough the experiments are a bit limited, the authors include a detailed experiments section in the appendix with a larger selection of baselines and more information about choosing the magnitude of the applied CG-regularization.\n\nCritiques:\nThe explanation of the results has a lot of room for improvement, and I would recommend the authors revise the writing to follow standard best practices, such as defining/explaining new variables when they are introduced, giving the steps associated with novel algorithms, etc. I give a few specific examples below where this lack of clarity makes the authors' results hard to understand, but there are many other examples of this not listed.\n\nThe description of the underlying causal model in section 3 (from the end of page 3 to the start of page 5) is hard to follow owing to a lack of explanation in many places. For example, the overgroups $G_D$ and $G_I$ are introduced without any insight into the distinction between these groups, or what role they play in the context of extrapolation tasks. \n\nSimilarly, the central concept of CG-invariance lacks some crucial details in its definition (Def 2), making the following material harder to follow. In particular, it isn't stated if CG-invariance is defined relative to a specific $\\tilde{U}_I$, or else requires Eq. 6 to hold for any choice of $\\tilde{U}_I$ (the latent distribution which determines the counterfactual samples $X^{cf}$).\n\nTheorem 3 is difficult to make sense of, with the subspaces $B_M$ appearing at first glance to be circularly defined (the projection in Eq. 9 used to define the $B_M$ is itself defined in terms of these subspaces). The text below and above Theorem 3 helps to interpret this circularity as an inductive algorithm for calculating these subspaces, but it would have been much clearer to define this algorithm explicitly in terms of pseudocode (along with a runtime), and then reference this definition in Theorem 3.\n\nRecommendation:\nAlthough the techniques seem like a timely and useful contribution, the poor presentation makes these techniques difficult to follow, and limits the usefulness of the paper for readers. I'm recommending a weak accept, but this can be improved by clarifying the presentation and making the results easier for readers to understand.\n\n\n**UPDATE AFTER THE REBUTTAL:** The new material in the paper clarifies things quite a bit, especially the intuitive explanations appearing below Equation 2 and at the bottom of page 4. Thank you for adding that, I have changed my score accordingly :)", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Pros:
- All reviewers agreed that the idea was particularly interesting/novel. I personally appreciated the perspective of unlearning invariances that prove inconsistent with the training data, rather than learning invariances that are demonstrated by the training data.
- The authors significantly improved clarity during the rebuttal period, and two out of three reviewers raised scores or confidence as a result.

Cons:
- There were significant concerns raised by reviewers about clarity of presentation, and some concern around whether the specific instantiation of the high level idea was the most sensible. From a *lightweight* reading of the paper on my part, I also feel that the writing style is unnecessarily dense, though I believe the underlying ideas are solid.
- One of the reviewers (AnonReviewer4) continues to have serious concerns. I believe the authors and AnonReviewer4 may have both become more entrenched in their positions during the discussion, in a way that wasn't particularly productive.

This paper is borderline score-wise. I believe it is particularly important to reward and encourage unusually novel work. Primarily for this reason I bias my decision upwards, and recommend acceptance.

nit: belive --> believe
Decision: Accept (Poster)