Equivariant Disentangled Transformation for Domain Generalization under Combination Shift
Authors: Yivan Zhang
Jindong Wang
Xing Xie
Masashi Sugiyama
Venue: Submitted to ICLR 2023 (2023)
Keywords: distribution shift
domain generalization
equivariance
invariance
disentanglement
algebraic theory
group theory
category theory

Abstract: Machine learning systems may encounter unexpected problems when the data distribution changes in the deployment environment. A major reason is that certain combinations of domains and labels are not observed during training but appear in the test environment. Although various invariance-based algorithms can be applied, we find that the performance gain is often marginal. To formally analyze this issue, we provide a unique algebraic formulation of the combination shift problem based on the concepts of homomorphism, equivariance, and a refined definition of disentanglement. The algebraic requirements naturally derive a simple yet effective method, referred to as equivariant disentangled transformation (EDT), which augments the data based on the algebraic structures of labels and makes the transformation satisfy the equivariance and disentanglement requirements. Experimental results demonstrate that invariance may be insufficient, and it is important to exploit the equivariance structure in the combination shift problem.

EQUIVARIANT DISENTANGLED TRANSFORMATION FOR DOMAIN GENERALIZATION UNDER COMBINATION SHIFT
Anonymous authors Paper under double-blind review
ABSTRACT
Machine learning systems may encounter unexpected problems when the data distribution changes in the deployment environment. A major reason is that certain combinations of domains and labels are not observed during training but appear in the test environment. Although various invariance-based algorithms can be applicd, we find that the performance gain is often marginal. To formally analyze this issue, provide unique algebraic formulation of the combination shift problem based on the concepts of homomorphism, equivariance, and a refined definition of disentanglement. The algebraic requirements naturally derive simple yet effective method, referred to as equivariant disentangled transformation (EDT), which augments the data based on the algebraic structures of labels and makes the transformation satisfy the equivariance and disentanglement requirements. Experimental results demonstrate that invariance may be insufficient, and is important to exploit the equivariance structure in the combination shift problem.
INTRODUCTION
The way humans perceive the world is combinatorial we tend cognize complex object or phenomenon combination of simpler factors of variation. Further, we have the ability to recognize, imagine, and process novel combinations of factors that we have never observed so that we can survive in this rapidly changing world. Such ability is usually referred to as generalization. However, despite recent super-human performance on certain tasks, machine learning systems still lack this generalization ability, especially when only a limited subset of all combinations of factors are observable (Sagawa al., 2020; Träuble et al., 2021; Goel et al., 2021; Wiles et al., 2022). In risk-sensitive applications such as driver-assistance systems (Alcorn et al., 2019; Volk et al., 2019) and computer-aided medical diagnosis (Castro et al., 2020; Bissoto et al., 2020), performing well only given subset of combinations but not on unobserved combinations may cause unexpected and catastrophic failures in a deployment environment.
Domain generalization (Wang al., 2021a) is problem where need deal with combinations of two factors: domains and labels. Recently, Guirajani & Lopez-Paz (2021) questioned the progress of the domain generalization research, claiming that several algorithms are not significantly superior to an empirical risk minimization (ERM) baseline. In addition to the model selection issue raised by Gulrajani & Lopez-Paz (2021), we conjecture that this due to the ambitious goal of the usual domain generalization setting: generalizing to completely unknown domain. Is it really possible to understand art if we have only seen photographs (Li al., 2017)? Besides, those datasets used for evaluation usually have almost uniformly distributed domains and classes for training, which may be unrealistic to expect in real-world applications.
A more practical but still challenging learning problem is to learn all domains and labels, but only given a limited subset of the domain-label combinations for training. We refer to the usual setting of domain generalization as domain shift and this new setting combination shift. An illustration is given in Fig. 1. Combination shift more feasible because all domains are at least partially observable during training but is also more challenging because the distribution of labels vary significantly across domains. The learning goal is to improve generalization with as few combinations possible.

---

1
2
3
4
2
3
4
1
2
3
4
2
4
2
#
(a) Domain shift: y/train (4, B3, Y = (C}. Y2rain
(b) Combination shift: Y Y/ (A, B. C).
Youa {0, 3,44
2 {,, 1,,,3, 4), 12 {0, 1,,1)
Figure 1: Domain generalization under domain shift (an unseen domain) and combination shift (unseen combinations of domains and labels). Domain: color, label: digit, training: 7, test: ia.
To solve the combination shift problem, straightforward way is to apply the methods designed for domain shift. One approach is based on the idea that the prediction of labels should be invariant to the change of domains (Ganin et al., 2016; Sun & Saenko, 2016; Arjovsky et al., 2019; Creager et al., 2021). However, we find that the performance improvement is often marginal. Recent works (Wiles et al., 2022; Schott et al., 2022) also provided empirical evidence showing that invariance-based domain generalization methods offer limited improvement. On the other hand, they also showed that data augmentation and pre-training could be more effective. To analyze this phenomenon, a unified perspective on different methods is desired.
In this work, we provide algebraic formulation for both invariance- methods and data augmentation methods to investigate why invariance may be insufficient and how we should learn data augmentations. We also derive simple yet effective method from the algebraic requirements, referred to as equivariant disentangled transformation (EDT), to demonstrate its usefulness.
Our main contributions are follows:
We provide an algebraic formulation for the combination shift problem. We show that invariance is only half the story and it is important to exploit the equivariance structure. We present a refined definition of disentanglement beyond the one based on group action (Higgins et al., 2018). which may be interesting in its own right.
Based on this algebraic formulation, we derive (a) what combinations are needed effectively learn augmentations; (b) what augmentations are useful for improving generalization; and (c) what regularization can be derived from the algebraic constraints, which can serve as guidance for designing data augmentation methods.
As a proof of concept, we demonstrate that learning data augmentations based on the algebraic structures of labels is promising approach for the combination shift problem.
2 PROBLEM: DOMAIN GENERALIZATION UNDER COMBINATION SHIFT
Throughout the following sections, we study the problem of transforming a set of features X to set of targets Y via a functiin f X + Y. Here, X can be set of images, texts, audios, or more structured data, while Y is the space of outputs. Further, the target may have multiple components. For example, Y, is the set of domain indices and Y2 is the set of target labels.
Ideally, all combinations of domains and target labels would be uniformly observable. However, in reality, it may not be the case because of selection bias, uncontrolled variables, or changing environments (Sagawa al., 2020; Träuble et al., 2021). Let Y, train and y denote the sets of i-th components (the support of the marginal distributions) observed in the training and test data. In the usual domain generalization setting (Wang al., 2021a; Gulrajani & Lopez-Paz, 2021), the goal is to generalize completely unseen domain, i.e., domain shift. We have Vztrain Ylest but
2

---

y n Y 2. However, it is unclear how different domains should relate and why model can generalize without the knowledge of the unknown domain (Wiles et al., 2022).
In this work, we focus where all test domains and labels can be observed separately during training, i.e., Y C Y (i
more practical condition, called combination shift and illustrated in Fig. 1,
1, 2), but not all their combinations. An example is the spurious relationship problem (Torralba & Efros, 2011), such the co-occurrence of the objects and their background (Sagawa al., 2020). In an extreme case, the combinations in the training and test sets could be disjoint, which requires completely -i-t--idittiitttionn generalization. We survey related problems and approaches more detail in Appendix D.
3 FORMULATION. EQUIVARIANCE TO PRODUCT ALGEBRA ACTIONS
This section outlines the concepts needed to formally describe the problem and our proposed method. See Appendices and C for in the proposed method itself may skip this section and directly jump to Section 4.
detailed review and concrete examples. Those who are interested
Because in the domain generalization problem, we have at least two sets, domains and labels, it is natural to study their product structure, which is manifested as statistical independence or operational disentanglement. We focus the latter and use the following definition:
Definition Let (A, (A,, (p) A A,tre,,)) be algebras indexed by E each of which consists of the underlying set A, and a collection of operations f/ of arity n, indexed by E Jr- Let A I A the product algebra whose underlying set is the product set = Ile A,. Let A act on sets X and Y via actions aclx A x X + X and acly : A f: X + Y is disentangled it is equivariant to actx and acty.
x Y - Y. A transformation
In short, disentangled transformation is function equivariant actions by product algebra. Note that a definition of disentangled representations based on product group action has been given in Higgins et al. (2018), which is special case when {Ather are all groups. We emphasize that the concept of disentanglement is rooted in product, not group nor action. We will unwind this definition and discuss the reasons for this extension well its limitations below.
3.1 HOMOMORPHISM AND EQUIVARIANCE
An algebra consists of one or more sets, a collection of operations on these sets, and a collection of universally quantified equational axioms that these operations need satisfy. A homomorphism between algebras is function between the underlying sets that preserves the algebraic structure.
(left) action of set A on another set is simply a binary function act : A X + X. An action equivalent to its exponential transpose or currying, a function act
X from A to the set of endofunctions x also known as a representation of on X. An action is faithful all endofunctions distinct, and trivial if all elements mapped the identity function id
Let actx and acty be actions of A on X and Y, respectively. A function f X + Y is equivariant actx and acty if
Va E f e act (a) (a) f. Specifically, if acty is trivial f is called invariant to actx:
Va E f (c)
In summary, for an underlying set X, an algebra over X describes the structure of the set X itself. while an action or representation of another algebraic structure A on X describes the structure of a subset of the endofunctions x Homomorphisms and equivariant functions describe how the structures of the set and endofunctions are preserved, respectively. An equivariant map can be also considered as homomorphism between two algebras whose operations are all unary and indexed by elements in the set A. Note that only the equivariance - the structure endofunctions - may not fully characterizes learning problem, because not all operations are unary operations. In some problems, it would be necessary to consider the preservation of the structure of other operations with the concept of algebra homomorphism. See also Appendices A to C.
3

---

3.2 MONOID AND GROUP
Let us focus on the endofunctions X for now. A way to describe the structure of subset of endofunctions X is to specify an algebra A and an action of A on X preserving the algebraic structure. For example, important operation is the function composition O: X x xx* which can be described by how an action preserves a binary operation :A A:
Va,, 02 A, act(a: 02) = act((i) act(
Since the function composition is associative, (A, should be a semigroup. If we also want to include the identity function idy then there should exist an identity element e E A (a nullary operation), which makes (A, :, e) a monoid.
Remark 1 (Group). we only consider invertible endofunctions, then becomes a group (Higgins et al., 2018). However, only considering groups could be too restrictive. For example, periodic boundary conditions are required (Higgins et al., 2018; Caselles- Dupré et al., 2019; Quessard et al., 2020; Painter et al., 2020) for two-dimensional environments (c.g., dSprites (Matthey et al., 2017)), so that all the movements are invertible and have a cyclic group structure. This is only possible in synthetic environments such games, not in the real world. Another example is the 3D Shapes dataset (Burgess & Kim, 2018), which consists of images of three-dimensional objects with different shapes, colors, orientations, and sizes. It acceptable model the shape, color, and orientation with permutation groups or cyclic groups. However, it is unreasonable if we increase the size of the largest object, then becomes the smallest. This is because we only consider the set of natural numbers, representing size, count, or price, and of which addition only has monoid structure. Therefore, it is important to consider endofunctions in general, not only the invertible ones. this work, we mainly focus on monoid actions that only describe the function composition and identity function.
3.3 PRODUCT AND DISENTANGLEMENT
Finally, we are in a position to introduce the concept of disentanglement used in Definition 1. For two objects Y, and Y2, we can consider their product Y = Y2 Yg, which is defined via pair of canonical projections P1 Y1 x Y, + Y₁ and P2 : Y, x Y2 - Yz This means that we can divide the product into parts and process each part separately without losing information. We reiterate that:
Product structure is the core of disentanglement.
Specifically, (a) Y, and Y2 are just sets, Y is their Cartesian product; (b) Y and Y, have algebraic structures, Y is the product algebra and the operations are defined componentwise; and (c) if A, and A, act on Y, and Yg respectively, then the product algebra A A₁ x A can act on Y = Y, x X, componentwise.
Additionally, if we let PY be the set of all measures on Y, then PY, X PY₁ is the set of joint distributions where two components are statistically independent, while PY = P(Y, x Y2)) is the set of all possible joint distributions. Product is the common denominator for all the definitions of disentangiement. In Definition 1, we only considered the product structure of endofunctions.
We can use this definition to formulate the domain generalization problem as follows. We assume that Y = Yi Yg has components, where Y, is the of domain indices and Yg is the set of other target labels. we choose a structure of subset of the endofunctions y described by two algebras A and A₂ and two actions acty, and acty, Then, we let the product algebra A A x A₂ act on Y= Y1 x Yz componentwise via an action acly. We also assume that there an action act of A on X that manipulates the features. After properly choosing the algebras and actions, the problem can be then formulated as finding a function equivariant to act x and acty.
Note that it is usually unnecessary and sometimes impossible to decompose X into product, i.e., X X, x X2 may not exist. For example, when X is a set of objects with different shapes and colors, there does not exist an object without color. In this case, we could only equip the endofunctions x with product structure.
4

---

4 METHOD: EQUIVARIANT DISENTANGLER TRANSFORMATION
In this section, we present our proposed method based on an algebraic formulation of the combination shift problem. The basic idea is that if we choose the algebra properly, the algebraic requirements of the transformation naturally lead to useful architectures and regularization.
In the following discussion, we assume that acly, (a,, V/) = v/ for some a, A, and Ui. v/ e Y,, i == 1,2. We denote an instance whose labels are y/1 and y2 by 2'
4.1 MONOID STRUCTURE
First, we discuss how to choose the algebra that is suitable for our problem and derive the algebraic requirements. As discussed in Section 3.2, we only require that algebras A and A₃ are monoids, which means that there exist associative binary operations : ::A x A, - A, and identity elements & A, for = 1, 2. Then, according to Eq. (3) (action commutes with composition), we can derive that a product action act( a2) on or can be decomposed in two ways:
act(a, 02) (ct 62) act(ee; 02) act(C1, 42) (c)
(4)
Or equivalently, the following diagram commutes (when the action on Y = Y1 Y2):
(y 122 actlen
(y1.3/2
ag)
(5)
(11. U2) act(er
(vá. V/22
Thus, we can focus on the endofunctions the form act (a1, C2) and act a2), whose compositions constitute all endofunctions of interest.
Remark (Size). Denoting the cardinality of set A by |A| and the image of a function f set X by f[X], i.e., set defined by {f(x)) x X}, we can prove that [[,]([A,], e2)l S [A1], [act([A]], e2) x |act(e1, (A2)] S [A, [Ag].
|act(e), [Ag]] < [Ag], and (et,(()),,4g)) The equality holds when the actions are faithful. Thanks to the monoid structure and the product structure, we can reduce the number endofunctions that we need to deal with from |A,l x |Ag to at most |A1 + [Ag). We further reduce the number if A₁ or Ag has smaller generator. For example, although the monoid (N, +) of natural numbers under addition has infinite elements, it can be generated from singleton {1}. In this case, can focus single endofunction that increases the value by a unit, and all other endofunctions are compositions of this special endofunction.
4.2 EQUIVARIANCE REQUIREMENT
Then, consider function f X + Y that extracts only necessary information and preserves the algebraic structure of interest. We require it to be equivariant to two actions act and acty- Recall that we can consider endofunctions only of the form act(a, e2) and (ct(e1, Based on Eq. (1) (action commutes with transformation), we derive the algebraic requirement shown in the following commutative diagram:
(V1.
P1
V1
actx (2))02)
acty (e))
2/2 v_..
ky,, Jacty (a1)
(6)
(gi. V2)
Vi
With the projections P1 and P2- can that this requirement results in the following four
conditions: (a) f1 Pi of equivariant act eg) and acty, (b) fi is invariant act (e1, -);
and dually, (c) f2 = P3 o is equivariant to act x (f1- -) and acty, (d) fa is invariant to a (2, The symbol is placeholder, into which arguments can be inserted.
5

---

Notation:
(R,
component 1
act(ar, 62)
component 2
1 act(e1, 02)
augmentation
act(a U2)
(R, 0)
prediction
f:X - 1ixxx X
Training:
[
Select suitable data pairs and learn component augmentations separately (Eq. (7));
Regularize augmentations (Eqs. (8) and (9)) simultancously or alternatively;
(B,0)
Train a prediction model (Eq. (10)).
Figure 2: Equivariant Disentangled Transformation (EDT), All diagrams commute.
4.3 ALGGRRIHHM
Finally, we present method directly derived from the algebraic requirements of the transformation, referred to equivariant disentangled transformation (EDT) and illustrated in Fig. 2. Since the formulation above naturally generalizes the case of multiple factors Y Y, -.. x Yn we present the method in the general form.
Architecture Since the output space Y and the selected endofunctions on it are manually designed, the action acty on Y is known and fixed. However, the action actx on X usually not available. So our first goal is to learn set of endofunctions af X X representing act x (e....., .......,, ...,, e,,) ......,,.
indexed by af E A,, i 1,..., n. These endofunctions can he considered as learned augmentations of data that only modify single factor while keeping other factors fixed. Second, approximate the cquivariant function f using a trainable function Φ X + Y. Due to the property of product, any function a product arises from component functions d; X + Y,, I,..., Therefore, we can train model for each component and make these models satisfy the algebraic requirements specified bellow.
need to
Data selection and augmentation To train an augmentation af, we need to collect pairs of instances and z'' such that actx actx((E).....,. ...... C, e,), x) = z', in other words, pairs of the form X F "............................... and x B'....''........... where acty, (a. v:) = 3/.- Then, denoting the set of all measures on X by P.,, we can learn the augmentations by minimizing a statistical distance d PX x PX- + Rzo
lo(a!) = (x),
(7)
With a slight abuse of notation, here and x' also represent the empirical distribution. Choices of the statistical distance d include the expected pairwise distance (Kingma & Welling, 2014), maximum mean discrepancy (Li et al., 2015; Dziugaite et al., 2015; Muandet et al., 2017), Jensen-Shannon divergence (Goodfellow et al., 2014), and Wasserstein metric (Arjovsky et al., 2017; Gulrajani et al., 2017: Miyato et al., 2018).
Remark 3 (Cycle consistency). It possible to use all pairs of the form Tg W. v. and T. Shi...hh V.......... i.e., pairs of instances whose i-th labels correspond the action, but other labels could be different. For example, if A, is group, we can simultaneously train inverse of each other with cycle consistency constraint (Zhu et al., 2017; Goel et al., 2021). With this constraint, the learned augmentation is likely an approximation of act ( ......, However, it is still possible to obtain approximations of (g), of ..... 9n) and its inverse where 91..... 4n. are not necessarily the identity elements. This happens especially when there are more than two factors and not all combinations available, which demonstrated in Section 5.
models that the

---

Compositionality of multi-scale augmentations
Commutativity of disentangled augmentations
Figure 3: Regularizing compositionality and commutativity (and other algebraic structures) of augmentations is way to introduce inductive biases and exploit the relationships between training examples, which is useful especially when the combinations of factors are scarce in the training data.
The rich algebraic structure yields various constraints, which can be used as regularization for augmentations. Next, we present three regularization techniques derived from the basic product monoid structure. Note that we can introduce more constraints if we choose richer algebra.
Regularization 1 (Compasitionality of augmentations) According to Eq. (3), if af is the approximated action of af 's a, we simply define it as og of oo, If we need approximate it directly, the algebraic requirement leads to the following regularization:
& (a oi of * d(aa) (a (z:). (x))
(8)
special case is when we know the composition is the identity function a.* = idx, i.e. of is the inverse of l This regularization is then equivalent to the "cycle consistency loss" in the CycleGAN model (Zhu et al., 2017) or the "isomorphism loss" in the GroupifiedVAE model (Yang et al., 2022). Another example for modifying instances with real-valued targets. We could
multi-scale
augmentations (e.g., a increases the value by 1 unit and a increases the value by 5 units) to reduce the cumulative error and gradient computation, and this regularization ensures that these augmentations are consistent with each other (e.g., (a x a²).
Regularization 2 (Commutativity of augmentations) According to the diagram in Eq. (5), can derive the following regularization, which means that the order of augmentations for different factors should not matter:
(a ; .a))aa))== d(a (a)) (s)),,(((d)) (d)()))..
This can be interpreted as a commutativity requirement: the augmentations are grouped by the factors they modify, and augmentations from different groups should commute, but augmentations within the same group are usually not commutative. Again, we point out that this is only based on the product monoid structure and is nothing group- specific.
In Fig. 4, we illustrate a concrete example of compositionality and commutativity regularization based on the dSprites dataset (Matthey et al., 2017). The movement of position can modeled via the additive monoid of natural numbers; while the change of shape can be formulated by permutation/cyclic group. Suitable training example pairs can be used for learning augmentations directly (Co), but such pairs may be limited. Algebraic regularization terms (e.g.. e, and Eg) introduce inductive biases so that more relationships between training examples can be used as supervision.
Regularization 3 (Equivariance of transformation) According to the diagram in Eq. (6), can derive the following equivariance and invariance regularization:
ddo (z)) acty (a), d(o (z)) (x))
k, i + k.
Lg(a, Φx)
(10)
It is good strategy learn the augmentations first and then them to improve the transformation (Goel et al., 2021). However, we can see from this regularization that if the transformation is well trained, it can be used for improving the augmentations too.
7

---

Table 1:
The classification accuracy (%, "mean (standard deviation)" of trials) on the colored MNIST data. For each setting (column), the method with the highest mean accuracy and those methods that are not statistically significantly different from the best one (via one-tailed t-tests with significance level of 0.05), if any, are highlighted in boldface.
AXIS
STEP (15/35)
RAND-0.5 (25/25)
RAND-0.7 (35/15)
RAND-009 (45/5)
(train/test)
(14/36)
ERM
56.74(12.40)
47.09(8.22 29)
91.13(3.70)
97.18(0.98)
98 08.61 (0.29)
IRM
55.40(7.23)
39.54(7.78)
(5.67)
96.89(2.44)
98. 98.20
CORAL
72.47(17.33)
49.72(10.53)
83,48(5.83)
94.61(3.62
98.21 0..
DANN
82.33(12.76)
45.02(3.79)
91.76(2.67)
97.99(0.32)
98.54 0.200)
Fish
69.06(14.50)
45.18(3.36)
79.93(5.12)
96.29
98. 98.13(0.45
Mixup
63.59(11.98)
36.30(4.42)
92.56(1.81)
97.62(0.99)
98.20(0.66
MixStyle
97.10(1.36)
95.73(1.83)
95.25(1.83)
97.57
98.13(0.76)
EDT
97.58(0.17)
98.13(0.155)
96.70(1.36)
98.55(0.133)
98.21(0.42)
EXPERIMENTS
As proof of concept, we conduct experiments to support the following claims:
Learning data augmentation is a promising approach for the combination shift problem.
Cycle consistency may be insufficient, and additional constraints need to be considered.
We should regularize the data augmentations so that they satisfy the algebraic requirements.
5.1 COMBINATION SHIFT
First, we experimentally demonstrate the insufficiency of the eevariane-bbsse approach and the potential of the nugmentation-basee approach for the combination shift problem.
Data We colored the grayscale images from the MNIST dataset (LeCun et al., 1998) with 5 colors to create semi-synthetic setting. Therefore, there are 5 domains (colors) and 10 classes (digits). We tested the methods the most extreme case where the combinations of domains and classes of the training and test sets disjoint. We selected five types of combinations the training set: AXIS: all red digits and zeros of all colors; STEP: three digits for each color (shown in Fig. 6 in Appendix E); BAND-0.55-0.77-0.. combinations randomly selected with fixed ratio.
ERM baseline, we evaluated four invariance-based methods: IRM (Arjovsky et al., 2019), CORAL (Sun & Saenko, 2016). DANN (Ganin et al., 2016), and Fish (Shi al., 2022); and two augmentation-basee methods: Mixup (Zhang et al., 2018) and MixStyle (Zhou et al., 2021). Model architectures and hyperparameters are given in Appendix
Method In addition
Results We can see from Table that the ERM baseline and invariance- wrasredce-bbseed methods perform poorly if only limited combinations of domains and classes are observable. The high variance indicates that the learned representation may still depend on the domains. become observable in training. the differences in performance of all methods become less statistically significant. On the other hand, the augmentation-bue improvements, although the mixup method may deteriorate performance depending the setting. MixStyle performs consistently well, partially because it is specifically designed for image styles and thus lends itself well to this setting. With the algebraic constraints, EDT may capture the underlying distribution better and offer larger improvements.
more combinations
methods usually provide higher performance
5.2
DATA AUGMENTATION
Next, we discuss potential issues of the augmentation-baat based method (Goel et al., 2021) based on CycleGAN (Zhu et al., 2017), which matches the bidirectionally transformed distributions and regularizes the composition to be the identity functions. There are two major issues of this approach. Firstly, it is designed only for domains (e.g., female and male). Secondly and more importantly,
8

---

Table 2: The misclassification rate (%) of shape and mean squared errors (x100) of scale, orientation, and positions on the dSprites dataset ("mean (standard deviation)" of 5 trials).
Shape
Scale
Orientation
Position X
Position
ERM MixStyle
(2.24)
3.76(0.24)
13.13(0.72)
(..6()
1.87(..25)
59.92 (2000
6.73(1.07)
13.04(0.54)
0.20(0.10)
0.21(0.06)
EDT (Eo, Ex) EDT
(4.36(0.75)
1.30(0.06)
2.09(0.07)
(.04(0.01)
0.04(0.01)
(Ep, li Eg. Eg)
0.59(0.01) (..2)
2.01(0.07)
0.02(0.00)
0.02(0.00)
(a) Without compositionality regularization, the error may accumulate after few compositions.
(b) Without commulativity regularization, pairs for learning augmentations may be insufficient.
Figure 4: Randomly selected 5 images (top row) in the dSprites dataset (Matthey et al., 2017) and augmented images (bottom 4 rows) of position (Fig. 4a, left ~- right) and shape (Fig. 4b, square ellipse ~4 heart ~ square), without (left) and with (right) regularization.
as discussed in Remark 3, when there are more than two factors, cycle consistency alone may not guarantee the identity of non-transformed factors. The comparison on the 3D Shapes dataset (Burgess Kim, 2018) shown in Fig. 8 in Appendix E. We can observe that although the floor hue is transformed as desired and the reconstructed images are almost identical to the original ones, other factors such as the object/wall hues are also changed. contrast, the algebraic requirements of EDT ensure the approximated augmentations are consistent with the desired actions.
5.3 ALGEBRACC REGULARIZATION
Finally, we further compare heuristic and learned data augmentations and demonstrate the usefulness of algebraic regularization. We used the dSprites dataset (Matthey et al., 2017) and considered one factor as target label and the others as domains. Some methods are no longer applicable because of the continuous even periodic values of factors and the multiplicatively increasing number of combinations. In Table 2, we can see that MixStyle provides no significant performance gain in this setting because the heuristic augmentation does not match the underlying mechanism anymore (See also Fig. 10 in Appendix E). In Fig. 4, we provide the results of an ablation study of the compositionality (&1) and commutativity (&2) regularization, showing that these regularization terms can reduce errors accumulated by compositions of augmentations and increase the number of supervision signals for learning augmentations, as illustrated Fig.
CONCLUSION
Unlike the usual goal of generalizing an unseen domain, formulated the problem of combination shift as learning the knowledge of each factor (domains and labels) and generalizing to unseen combinations of factors, which makes deployment more feasible but training more challenging. We found that anvariance-based methods may not work well in this setting, but augmentation- based methods usually excel. formally analyze data augmentations and provide guideline on augmentation design, we presented an algebraic formulation of the problem, which also leads to refined definition of disentanglement. We demonstrated the usefulness constraints derived from algebraic requirements, discussed potential issues of the existing augmentation method based on cycle consistency, and showed the importance of algebraic regularization. We then pointed out several promising research directions, such as incorporating algebra homomorphism and multi-sorted algebra to discuss a wider range of data augmentation operations. We hope that our algebraic formulation can be used to derive practical algorithms in applications and inspire further studies in this direction.

---

REFERENCES
Isabela Albuquerque, João Monteiro, Mohammad Darvishi, Tiago H Falk, and Ioannis Mitliagkas. Generalizing to unseen domains via distribution matching. arXiv preprint arXiv: 1.0.00044 2019.
D
Michael A Alcor,, Qi Li, Zhitao Gong, Chengfei Wang, Long Mai, Wei-Shinn Ku, and Anh Nguyen. Strike (with) a pose: Neural networks are easily fooled by strange poses of familiar objects. In Computer Vision and Pattern Recognition, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, 2017. 4.3
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:1907.02893, 2019. 1, D
Steve Awodey. Category theory. Oxford university press, 2010. B
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2019. D
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1):151-175, 2010. D
Aharon Ben- Tal and Arkadi Nemirovski. Robust optiiization-methdoolgg and applications. Math- ematical programming, 92(3)455-440, 2002. D
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3798):1798-1888, 2013. D
George M Bergman. An invitation general algebra and universal constructions. Springer, 2015. B
Alceu Bissoto, Eduardo Valle, and Sandra Avila. Debiasing skin lesion datasets and models? not so fast. In Computer Vision and Pattern Recognition Workshops, 2020.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to a new unlabeled sample. In Neural Information Processing Systems, 2011. D
Chris Burgess and Hyunjik Kim. 3D shapes dataset. https///gghhbbbcomm/eeemm////sss 2018. 1, 5.2, 8,
Hugo Raselles-Dupres Michael Garcia Ortiz, and David Filliat. Symmetry-based disentangled representation learning requires interaction with environments. In Neural Information Processing Systems, 2019. 1, D
Daniel C Castro, Ian Walker, and Ben Glocker. Causality matters in medical imaging. Nature Communications, 11(1):1-10, 2020.
Shuxiao Chen, Edgar Dobriban, and Jane Lee. A group-theoretic framework for data augmentation. In Neural Information Processing Systems, 2020.
Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. International Conference Machine Learning, 2021. D.
Pim de Haan, Taco Cohen, and Max Welling. Natural graph networks. In Neural Information Processing Systems, 2020. A.3
David S Dummit and Richard M Foote. Abstract algebra. Prentice Hall Englewood Cliffs, NJ, 1991. B
Gintare Karolina Dziugaite, Daniel M Roy. and Zoubin Ghahramani. Training generative neural networks via maximum mean discrepancy optimization. In Conference on Uncertainty in Artificial Intelligence, 2015. 4.3
10

---

Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François training of neural networks. 5.1,
Laviolette, Mario Marchand, and Victor Lempitsky. The journal of machine learning research, (7(1):2096-2033) 2016.
Leon A Gatys, Alexander S Ecker, and Matthias Bethge. Image style transfer using convolutional neural networks. In Computer Vision and Pattern Recognition, 2016. A.1
Karan Goel, Albert Gu, Yixuan Li, and Christopher Ré. Model patching: Closing the subgroup performance gap with data augmentation. In International Conference Learning Representations, 2021. 1, 4.3, 5.2, D,
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Neural Information Process- ing Systems, 2014. 4.3, E.1
Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021. 1,2
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein GANs. In Neural Information Processing Systems, 2017. 4.3
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. VAE: Learning basic visual concepts with constrained variational framework. In International Conference on Learning Representations, 2017. C.4,
Irina Higgins, David Amos, David Pfau, Sehastien Racaniere, Loic Matthey, Danilo Rezende, and Alexander Lerchner. Towards a definition of disentangled representations. arXiv preprint arXiv:1812.02233: 2018. 3, A.2, C.4,
Justin M. Johnson and Taghi M Khoshgoftaar. Survey on deep learning with class imbalance. Journal of Big Data, 6(1):1-54, 2019. D
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, 2015. E.I, E.3
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations, 2014. 4.3, D
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-basee learning applied to document recognition, 1998. 5.1,
Da Li, Yongxin Yang. Yi-Zhe Song, and Timothy M Hospedales. Deeper, broader and artier domain generalization. In International Conference on Computer Vision, 2017.
Yujia Li, Kevin Swersky, and Rich Zemel. Generative moment matching networks. In International Conference Machine Learning, 2015. 4.3
Xialei Liu, Joost Van De Weijer, and Andrew D Bagdanov. Leveraging unlabeled data for crowd counting by learning to rank. In Computer Vision and Pattern Recognition, 2018. A.1
Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentan- gled representations. In International Conference on Machine Learning, 2019. C.4,
Loic Matthey, Irina Higgins, Demis Hassabis, and Alexander Lerchner. dSprites: Disentanglement 2017. 4,4.3,4,5.33
testing sprites dataset. http://hhhh...oommeeemmm////sssd
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018
4.3, E.1
Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, Bernhard Schölkopf, et al. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends@ in Machine Learning, 1011-2):1-141 2017. 4.3
11

---

Matthew Painter, Adam Prugel-Benn Bengel,Bennet,,,,, and Jonathon Hare. Linear disentangled representations and unsupervised action estimation. Neural Information Processing Systems, 2020. 1, D
Robin Quessard, Thomas Barrett, and William Clements. Learning disentangled representations and group structure of dynamical environments. In Neural Information Processing Systems, 2020. 1, D
Joaquin Quinonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. MIT Press, 2008.
Alexander J Ratner, Henry Ehrenberg, Zeshan Hussain, Jared Dunnmon, and Christopher Ré. Learn- ing compose domain-specifee transformations for data augmentation. Neural Information Processing Systems, 30, 2017. D
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-Net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234-241. Springer, 2015. E.1
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang, Distributionally robust neural networks. In International Conference on Learning Representations, 2020. 1,2
Lukas Schott, Julius Von Kügelgen, Frederik Träuble, Peter Vincent Gehler, Chris Russell, Matthias Bethge, Bernhard Schölkopf, Francesco Locatello, and Wieland Brendel. Visual representation learning does not generalize strongly within the same domain. In International Conference on Learning Representationss 2022.
Yuge Shi, Jeffrey Seely, Philip Torr, Siddharth N, Awni Hannun, Nicolas Usunier, and Gabriel Synnaeve. Gradient matching for domain generalization. In International Conference on Learning Representations, 2022. 5.1,
Connor Shorten and Taghi M Khoshgoftaar. survey on image data augmentation for deep learning.
Journal of big data, 6(1):1-48, 2019. D
Rui Shu, Yining Chen, Abhishek Kumar, Stefano Ermon, and Ben Poole. Weakly supervised disentanglement with guarantees. In International Conference on Learning Representations, 2020.
C.4.D
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEEE Transactions Neural Networks and Learning Systems, 2022. D
Masashi Sugiyama and Motoaki Kawanabe. Machine learning in non-stationary environments:
Introduction to covariate shift adaptation. MIT press, 2012.
Masashi Sugiyama. Shinichi Nakajima, Hisashi Kashima, Paul Buenau, and Motoaki Kawanabe. Direct importance estimation with model selection and its application to covariate shift adaptation.
Neural Information Processing Systems, 20, 2007. D
Baochen Sun and Kate Saenko. Deep CORAL: Correlation alignment for deep domain adaptation. In European conference on computer vision, pp. 443-450. Springer, 2016. 1, 5.1, D
Raphael Suter. Djordje Miladinovic, Bernhard Schölkopf, and Stefan Bauer. Robustly disentangled
causal mechanisms: Validating deep representations for interventional robustness. International Conference Machine Learning, 2019. C.4, D
Seiya Tokui and Issei Sato. Disentanglement analysis with partial information decomposition. In International Conference Learning Representations, 2022, C.4, D
Antonio Torralba and Alexei A Efros. Unbiased look dataset bias. In Computer Vision and Pattern Recognition, 2011. 2
Frederik Träuble, Elliot Creager, Niki Kilbertus, Francesco Locatello, Andrea Dittadi, Anirudh Goyal, Bernhard Schölkopf, and Stefan Bauer. On disentangled representations learned from correlated data. In International Conference Machine Learning, 2021. 1,2
12

---

Georg Volk, Stefan Müller, Alexander Von Bernuth, Dennis Hospach, and Oliver Bringmann. Towards robust cnn- based object detection through augmentation with synthetic rain variations. Intelligent Transportation Systems Conference (ITSC), 2019.
Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John C Duchi, Vittorio Murino, and Silvio Savarese, Generalizing to unseen domains via adversarial data augmentation. In Neural Information Processing Systems, 2018. D
Hao Wang, Hao He, and Dina Katabi. Continuously indexed domain adaptation. In International Conference Machine Learning, 2020. D
Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Wenjun Zeng, and Tao Qin. Generalizing to unseen domains: A survey on domain generalization. In International Joint Conference on Artificial Intelligence, 2021a. 2,
Tan Wang. Zhongqi Yue, Jianqiang Huang, Qianru Sun, and Hanwang Zhang. Self-supervised learning disentangled group representation as feature. In Neural Information Processing Systems, 2021b. D
Yulin Wang, Gao Huang, Shiji Song, Xuran Pan, Yitong Xia, and Cheng Wu. Regularizing deep networks with semantic data augmentation. IEEE Transactions Pattern Analysis and Machine Intelligence, 2021c.
Olivia Wiles, Sven Gowal, Florian Stimberg, Sylvestre-Alvise Rebuffi, Ira Ktena, Krishnamurthy Dj Dvijotham, and Ali Taylan Cemgil. A fine-grained analysis distribution shift. In International Conference on Learning Representations, 2022. 1, 1, 2.2,E.4 E.4
Tao Yang, Xuanchi Ren, Yuwang Wang, Wenjun Zeng, and Nanning Zheng, Towards building group-based unsupervised representation disentanglement framework. International Conference on Learning Representations, 2022. 4.3, D
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018. 5.1, D, 10, E.4
Yifan Zhang, Bingyi Kang, Bryan Hooi, Shuicheng Yan, and Jiashi Feng. Deep long-tailed learning: A survey, arXiv preprini arXiv:21 2021. D
Kaiyang Zhou, Yongxin Yang. Yu Qiao, and Tao Xiang. Domain generalization with MixStyle. In International Conference Learning Representations, 2021. 5.1, D, 10, E.4
Jun Yan Zhu Taesung Park, Phillip Isola, and Alexei A Efros. Unpaired image-to-mmage translation using cycle-consistent adversarial networks. In International Conference on Computer Vision, 2017. 3, 4.3, 5.2,
13

---

fxf ((R, 0), (B,1))
P1 Xp2
(R, 1)
Figure 5: A homomorphism preserving binary operations @ and P1 x P2.
A LIMITATIONS AND FUTURE WORK
In this section, we discuss the limitations of this work and potential future work directions.
A.1 ALGEBRA НOMОMORPHISS
In this work, we only formulated data augmentations of the endofunction form a X - X, i.e., modifications of only one input. However, there are other operations that do not fall into this form. We suggest using algebra homomorphisms to capture their relations. Here we give three examples:
Component combination the instance can divided into multiple components, then we can recombine the components from multiple instances to generate new instance: a X - X. This is especially useful when there are many factors and the combinations the training set are sparse.
Style transfer Another example is when cannot divide the instances but can combine their characteristics, such as style transfer (Gatys et al., 2016). An example is given in Fig. 5, where X X - X is the binary operation that takes the "style" of the first image and the "content" of the second image, and X Y X Y + Y is the corresponding operation in the label space Y. Then, we need to ensure that this binary operation is compatible with other augmentations. For example, if the object in the content image changes, the object in the generated image should change accordingly; while the generated image should not change regardless of the object in the style image.
Crowd counting Counting the number of objects people in an image is example where can exploit the structure of natural numbers N. addition to the monotone function requirement induced by the total order of natural numbers N (Liu al., 2018), the free monoid structure (N, +) may induce other useful constraints. For example, the count of two parts should be the sum of the counts of each part. This requirement can be formulated as algebra homomorphism.
A.2 STATISTICS AND APPROXIMATION
Similarly to previous work (Higgins et al., 2018), we focused more on the algebraic aspect. We admit that there is still gap between formulation and practice, because algebra only describes exact equality (=), but sometimes we are more interested in approximate equality (>). It would be useful to define concepts such as commututivity over a metric space, so that we can analyze errors and introduce statistical tools, get the best of both worlds.
A.3 STATE AND MULTI-SORTED ALGEBRA
Another issue is that we only considered endofunctions X + X so all data augmentations are applicable all instances As future work, we may consider general functions X; - X, and define which functions are composable and which are not.
"stateless" way, which may not hold true more complex situations.
Also, it could be useful to discuss operations on multiple sets based on multi-sorted algebra, such as graphs (de Haan al., 2020).
14

---

B A BRIEF REVIEW OF ALGEBRA
In this section, we review the algebraic concepts used in this work. We refer the readers to Dummit & Foote (1991) (abstract algebra), Bergman (2015) (universal algebra), and Awodey (2010) (category theory) for further readings.
B.1 ALGEBRA
Definition (Algebra). (single-sorted) algebra consists of
a ser A, called the underlying set of the algebra,
collection of operations {f' A + Aher. and
a collection of universally quantified equational axioms that those operations satisfy.
For example, elementary algebra is the study of the set of numbers with arithmetic operations such as addition, subtraction, multiplication, division, and exponentiation. Linear algebra is the study of the set of vectors with operations vector addition and scalar multiplication.
Some algebras with only one binary operation are listed below.
Definition 3 (Magma). A magma is set A equipped with binary operation : A x A + A.
Definition 4 (Semigroup). A semigroup is a magma (S, whose binary operation is associative:
1, 82, $3 S, ($1 52) 83 51 (52 $3)
(11)
Definition 5 (Monoid). A monoid is semigroup (M,-) that has identity element e E M (a nullary operation e M)+ M):
Vm M,
m.
(12)
Definition 6 (Group). A group is monoid (G,,,e), e),, and every element has inverse (a unary operation (-)-1: G):
Vg E G,g g
g
(13)
Definition 7 (Abelian group). An Abelian group is a group (G,,,e, e, whose binary operation
commutative:
V9r.92 E G.91 .1 92 = 92 91
(14)
B.2 НОМОМОRРHISM
Definition 8 (Homomorphism). A homomorphism between two algebras (A, (Ahhr)) and (B, (er of the same type is function between the underlying sets h A + B such that
Vep...,,,, On E A. a... ffa((
(15)
holds for all corresponding operations S n A and l Td - B.
In other words, the following diagram commutes for all E T:
A
B
(16)
An invertible homomorphism is called an isomorphism. For example, exp and log functions form a pair of isomorphisms between (R, +) and (R+ x) because exp(x + y) = exp(x) x exp(y) and log(x y) log(æ:) log(v).
15

---

B.3 EXPONENTIAL
Definition 9 (Exponential), Given sets A and B, the function set BA is the set of all functions from
A to B. Given set A and a function set BA, there exists an evaluation map B x A + B that sends a function f + B and a value a E A to the evaluation eff,a) =(a)= E B. Definition 10 (Exponential transpose). For a binary function f A x B C, its exponential transpose (also known as currying) a function f A A C such that
Va E A, E B, f(a, = (b)
(17)
B.4 ACTION
Definition 11 (Action). A (left) action of set A on a set X is a binary function act :A x X + X. Definition 12 (Representation). A representation of a set A on a set X is a function act : A - X*
Definition 13 (Algebra preservation). A representation act A + xx preserves an algebra over A if it is homomorphism from A to x*
A magma/semigroup action preserves composition (a binary operation):
4a, a2 E A, Vx E x,act(a a2, x) = act(a, act(ag,
(18)
id x act A X
x Ax X
xidx x
act
(19)
Ax
X
act
Or equivalently,
Vaz, Q2 E A, act((a (2)) = act((a) ) act())))
(20)
A x
A
actxact
X X
(21)
A
X
act
A monoid action preserves identity (a nullary operation):
Vz E X, act((e,, x) = x.
(22)
(cl(e) = id
(23)
1
idx
(24)
A
X x
group action preserves inverse (a unary operation):
Ya E A, Vx E X, act(a -1 ,,ct(a, x)) = x.
(25)
Va E A, A,act(a -1 - -t) -1)
(26)
A x
(27)
(-)-1
A
X
act
16

---

B.5 EQUIVARIANCE
Definition 14 (Equivariance). A function /: X + Y is equivariant to two actions aclx AA X X and acby A x Y Y if
Va E A, X, factx (a, x)) acty f(x)).
(28)
ida xf
A x X
A x Y
(29)
act
acty
Or equivalently,
Va E A, ʃ act x (a) = aa) f.
(30)
X
Y (c)
a x (a)
(31)
X
commutes for all a E A. This justifies that an equivariant map is a homomorphism between two algebras whose operations are all unary and indexed by elements in the set A.
B.6 PRODUCT
Definition 15 (Product). A product A B of two objects A and B and the corresponding projections P1 B - A and P2 A + B satisfy that for any object C and morphisms Si - A and f2 C2 B, there is unique morphism f C + A B, such that fi Pı f and f2 P2 f. as indicated in
f1
fa
(32)
A
A X B
P2 B
Consider two morphisms f: C + A and
D + B. Based on the universal property of A x B,
there exists a unique morphism g C x
+ Ax B such that the following diagram commutes:
C P1
Cx
P2 D
(33)
A
A x B
P2 B
P1
For example, let both C and D be Y, Y2. f Pı. and g P2- Then, the following diagram
represents "recombination of components":
Y1 x Y2
xxx x 12) x x
Y x Y2
(34)
Pi
+
Y
Y, Y, Y
P
P2
17

---

C ALGEBRA IN SUPERVISED LEARNING
In this section, we look ahead to the application of algebraic theory to supervised learning.
C.I SUPERVISED LEARNING
Let X be the set of inputs and Y the set of outputs. In supervised learning, we want to find function f: f:X- + Y that satisfies some properties. Generally, this is achieved by collecting set of pairs {(T,, y:) X Jier as training examples and defining measure of "goodness" functions. For example, for pair (I,, V4), expect to map I; to y/-
Let us consider this procedure from an algebraic perspective.
Nullary operation First, we point out that identifying element x: from set X can be considered as a nullary operation 1 + X, and evaluating a function f X + Y at an element æ is simply function composition f o 1 Y. Then, requiring
f(z)
(35)
is equivalent to say that f should be an algebra homomorphism:
(36)
X
Y
Therefore, a function that can predict training examples perfectly is simply a homomorphism from algebra (X, (r, : + X) (te) to algebra (Y, {v4 - Y)ie) where all operations are nullary.
This perspective frames direct supervision an algebraic requirement. However, it is still not practically useful, because the training examples are usually finite and cannot enumerate the set of inputs, but we need machine learning only when the inputs in a test environment are not exactly missing: first,
the same the inputs for training. Two things training and test data; second, we need not only "yes or no" but also "how much". As discussed in Appendix A, pure algebra only deals with exact equality, so integrating algebra and statistical learning is an important research direction.
need assumption to relate
Unary operation Many works introducing algebraic theory, especially group theory, into machine learning, including this work, have focused on unary operations and their relations. A unary operation or an endofunction ax >> X transforms a set of states itself. homomorphism between (X, ax) and (Y, ay,ay just relates these unary operations:
X
(37)
x
Qy
X
Y
Usually, there are multiple unary operations, which themselves form an algebra. Magma/semigroup describes composition, monoid describes identity, and group describes invertibility. An invertible unary operation/endoounction is also called a symmetry. The structure of these unary operations can be described by action preserving the algebraic structure, which was extensively used in this work.
Binary and n-ary operations As also covered in Appendix A, not all operations are unary opera- tions. would be useful include n-ary operations and their relations as algebraic requirements for f:
x
n
(38)
0x
X
Y
18

---

Specifically, operad theory could be useful for analyzing a collection of finitary operations obeying equational axioms.
Moreover, future research could continue to explore n-ary functions from algebraic perspective. For example, f X + and g A may relate two binary functions ax X + and 0y Y x Y - B in the following sense:
Xx
fxf
Y Y
(39)
ax
ay
which could be used for formulating similarity) and order (learning to rank), or metrics, such as isometry, contraction, and Lipschitz continuous function.
functions, such as equality (learning from
C.2 BINARY CLASSIFICATION
Now, let consider concrete example, binary classification. Let be whose cardinality is n,, I a singleton (a set of a single element), + the disjoint union of sets (union of labeled/indexed elements), _ the isomorphism between sets bijective function). In binary classification, Y is simply a set of two elements 2 = +I+ I.
In other words, we only have a space with the concept of sameness or equality and other operations. The learning process is to find a function f X + 2. which decomposes into a pair of functions f= f2. where fi X, > I(i 1,2). This results in a decomposition of X into two sets X X1 + X2, i.e., classification of elements in X.
Let us examine the unary operations (endofunctions) on 2. There are in total four endofunctions on which forms monoid. There are only two invertible ones: the identity and the one that swaps two elements, which constitute a representation of the symmetric group S₂ on 2.
C.3 REGRESSION
To formulate regression, usually let Y be the set of real numbers R. However, from algebraic perspective, many operations of real numbers are not needed in the learning process. For example, rarely consider the product ratio of two target values. On the other hand, the order, scale, and zero point are of our central interest. Thus, if there exist minimal value and unit interval of targets, we can isomorphically transform the target and let be the set of natural numbers N. If we cannot determine minimal value but we are still able to quantize the target values, we can take step further and consider the algebra of integers Z and the negation operation.
There are two important operations of natural numbers: 1 - N as nullary operation that identifies the number zero and the successor function S N N unary operation that maps number n. to the next number (n)).
Let Fn X be an instance whose label n. If X also has the structure of natural numbers, then there exist element Tp that has the minimal value and unary operation T' X + X that takes an instance as input and outputs another instance whose label is one unit higher. The requirement of ff being homomorphism means that the instance with the minimal value is mapped to 0, i.e., f(,)) = 0, and the operation T corresponds to the successor function S in the following way:
In
(40)
T
T (())
S(n)
Given the number zero 0 and the successor function S of natural numbers N, define commutative monoid with 0 as the identity element and a monoid operation + defined recursively: S(b) S(a b). This is the free monoid (N, +) generated from generator S(0)).
19

---

Then, consider the case when the free monoid (N, +) acts on X and N itself. A function cquivariant to free monoid actions is a function f X + N such that the following diagram commutes:
Idy x
(m, Fnn
(m, n)
(41)
act
T n
+ m
Note that when m the generator this diagram can be reduced Eq. (40).
The crowd counting example in Appendix A can be illustrated in the following diagram:
fxf
(I Fnn
(m, n)
(42)
mm
m + n
which means that the count of two parts should be the sum of the counts each part. This requirement formulated homomorphism of binary operations @ x X X and ::N x N.
C.4 DISCUSSION
As discussed in Section 3.1, the equivariance alone may not fully characterizes learning problem. For example, in binary classification, if we only require the transformation f X + Y to be equivariant actions by the symmetric group Sz, then is only unique up permutation; Similarly, in regression, f is only unique up to shift by a natural number or an integer. This may not cause a problem, but still need some information determine the optimal solution, for example, the zero point (a nullary operation) in regression.
Similarly Higgins al. (2018), focused on the algebraic aspect of disentanglemennt It is worth noting that this formulation is not yet compatible with some definitions of disentanglement based on statistical independence, probability metric, or causal mechanisms (Higgins al., 2017; Suter et al., 2019; Locatello et al., 2019; Shu et al., 2020; Tokui & Sato, 2022). In statistical learning, we usually want to find conditional distribution f on Y, instead of merely a deterministic transformation f X - Y. To extend this framework and fully capture the statistical aspect of disentanglement we need to further incorporate the structure of probability measures, which is left for future work.
PY, where PY denotes all probability measures
20

---

D LITERATURE REVIEW: DISTRIBUTION SHIFT
In this section, we review related work in distribution shift in broader sense.
The difference between the training and test data in supervised learning is important problem and has been studied for years. The distribution shift problem (Quiñonero-Canded) et al., 2008) refers to the general case where the training and test data are drawn from related but different distributions:
train X, Y) + (X.Y)
The difference can be measured by some distribution divergence (Ben-David et al., 2010; A Albuquerque et al., 2019). Distribution shift can be subcategorized by the distribution assumptions:
Covariate shift: p train (Y X) = pp (Y X) (Sugiyama et al., 2007; Sugiyama & Kawanabe, 2012)
Label shift: train (X Y) test (X Y), e.g., class imbalance (Johnson & Khoshgoftaar, 2019)
and long-tailed class distribution (Zhang et al., 2021)
Concept shift: p
train (X) = =p" test (X), e.g., noisy labels (Song et al., 2022)
Distribution shift is also closely related to robust optimization (Ben-Tal & Nemirovski, 2002) and fairness in machine learning (Barocas et al., 2019).
Domain adaptation/geenrraizziii (Quinonero-Candell al., 2008), implying that the tasks are indexed by a categorical (Blanchard et al.. 2011) or continuous ( (Wang et al., 2020) domain variable, All three types of distribution shift mentioned above may happen when there are multiple domains. To solve this problem, domain- invariant representation learning (Ganin et al., 2016; Sun & Saenko, 2016; Arjovsky et al., 2019; Creager et al., 2021; Shi et al., 2022) has been widely used, which aims extract features invariant to domain change. In this work, we showed the limitations of invariance-biie methods in the combination shift problem.
(Wang et al., 2021a) is special distribution shift problem
A closely related concept is disentanglement (Bengio et al., 2013), which can be defined via statistical independence (Suter et al., 2019; Locatello et al., 2019; Shu et al., 2020; Tokui Sato, 2022) or product group action (Higgins et al., 2018; Caselles- et al., 2020; Wang et al., 2021b; Yang et al., 2022). Our work follows the latter direction. We provided refined definition of disentanglement based algebra in Definition 1, which can be as an extension of Higgins et al. (2018). We also discussed potential directions for further extension in Appendix A, including algebra homomorphism, statistics, non-endofunctions, and multi-sorted algebra.
al., 2019; Quessard et al., 2020; Painter
Various methods have been developed based the concept of disentanglement. On approach based on variants of the variational autoencoder (VAE) (Kingma & Welling, 2014; Higgins et al., 2017). Another promising approach is based on either heuristic (Zhang al., 2018: Shorten & Khoshgoftaar, 2019; Chen et al., 2020; Zhou et al., 2021) or learned (Ratner et al., 2017; Volpi et al., 2018; Wang al., 2021c; Goel et al., 2021) data augmentation. Learning data augmentation is the central interest of our work.
21

---

1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
0
2
3
4
S
6
7
8
9
0
1
2
3
5
6
7
8
q
/
3
4
5
6
8
9
7
Figure 6: A set of combinations of the colored MNIST data with only 15/50- 30% data for training. Shaded combinations are used for testing.
E EXPERIMENTS
E.1 MNIST
Data The MNIST' dataset contains grayscale hand-written digit images of size 28 x 28 in 10 classes. The size of the training set 60 000 and the size of the test set is 1000.. We only used the images in the training set and colored them with five colors (red, yellow, green, blue, and purple) with equal probabilities. The images were resized to 32 x 32 to fit the model. No manual data augmentation was used.
Data split
We selected five types of combinations as the training set:
AXIS: all red digits and zeros of all colors
STEP: three digits for each color, shown in Fig. 6
RRAND-055000.7000. 7/-0.9: combinations randomly selected with a fixed ratio 0.5, 0.7, or 0.9. All domains and classes were ensured to appear at least once.
The remaining combinations were used as the test set.
Model We used U-Net (Ronneberger et al., 2015) for the image-to-image data augmentations with 3 layers of downscale/upscale modules and sigmoid as the last layer. We used a convolutional neural network with spectral norm (Miyato et al., 2018) as the discriminator for distribution matching (Goodfellow et al., 2014) between images (fg. f,, and fz). To reduce the number of models, the discriminator was conditioned on the factors via additive embedding. We use the same architecture of the discriminator for the classifier except the dimension of output was set to 10. The learning likelihooodd
objective for the classifier (Eg) is the cross-entropy/negative
Optimization We used an Adam optimizer (Kingma & Ba, 2015) with batch size of 32, learning rate of 1 x 10 for the augmentations and 1 x 1 for the discriminator and the classifier. The model was trained for 10 000 iterations.
Infrastructure
The experiments were conducted on an NVIDIA Tesla V100 GPU.
'MIIST (LeCun et al., 1998) http::
st/
22

---

floor hue
orientation
orientation
orientation
floor
wall hue
shape
floor hue
floor hue
orientation
scale
orientation
floor
hue
hue
shape
wall
orientation
floor
wall hue
object
object hue
object hue
object hue
floor hue
object hue
wall hue
floor hue
scale
orientation
object hue orientation
shape
wall hue
shape
orientation
scale
object hue
floor hue
orientation
object hue
scale
object hue
orientation
orientation
orientation
wall hue
scale
scale
object hue
wall hue
orientation
scale
wall hue
orientation
scalle
Figure 7: path of transformations of data (left right, top bottom) of the 3D Shapes dataset.
Figure 8: (top row) 10 images from the 3D Shapes dataset (Burgess & Kim, 2018) with red floor; (middle rows) augmented data (red to orange) and reconstructed data (orange to red) transformed by CycleGAN model (Zhu et al., 2017; Goel et al., 2021); (bottom row) augmented data transformed by EDT, which satisfies the algebraic constraints.
23

---

E.2 3D SHAPES
Data The 3D Shapes" dataset contains images of three-dimensional objects with 6 factors (floor hue, wall hue, object hue, scale, shape, and orientation). whose dimensions are 10, 10, 10, and 15. The size of the dataset is 480 000.
Data selection Since the goal is to improve generalization using as few combinations as possible, we used set of properly selected combinations of factors. Concretely, we first randomly select an instance, and then randomly change a factor at a time. An example of a path of transformations is shown in Fig. 7. We used 10 random paths so there at most 570 training examples (only around 0.1% of all data).
Model and optimization Because there is only one image for each combination of factors, there is no need to use distribution matching. We used pixel-wise binary cross-entropy as the learning objective for lo. I, and 2z. Other hyperparameters are the same as those used above.
E.3 DSPRITES
Data The dSprites dataset contains images of 2D shapes generated from 6 ground truth independent latent factors: color, shape, scale, rotation, and y positions a sprite, whose dimensions are 1, 3, 40, 32, and 32. The size of the dataset is 737 280.
Data selection Note that there is no bijection between the factors and the images because of the intrinsic symmetries of the shapes, e.g., C4 of the square and C2 of the ellipse. To this end, we only considered a subset of the original dataset where the orientation only ranges from 0 to 90º, which resulted in a dataset of size 184 320. The split of training and data was similar to the above. Thus, we used only 830 1844/44433 320 z 0.5% data for learning augmentations.
Model and optimization We used a simple 3-layer MLP (64 x 64 + 256 - 64 + output) with ReLU activation the prediction model, cross-entiee cross-entropy (classification) mean squared error (regression) as the learning objectives, and an Adam optimizer (Kingma & Ba, 2015) with batch size of 32 and learning rate of 10
Results Additionally, show the augmented images in Fig. 9, We can see that these augmentations are not equally easy to learn: the shape and position augmentations perform relatively well, but modifying the scale and orientation may cause shape distortion.
23D Shapes (Burgess & Kim, http//////i.//////g/..//e/////er Apache License
2.0
"Sprrites (Matthey al., 2017) httph:ttt////tt.tt http::/tte///chhhhh..c.///ee///p http://eepppnn//srareeeeeedeee Apache
License 2.0
24

---

(a) Shaper square, ellipse, heart
(b) Scale: 6 values lincarly spaced in [0.5, 1]
(c) Orientation: 10 values in [0%, 90%]
25

---

(d) Position X: 32 values in [0,
(c) Position 32 values [0, 1]
Figure 9: Augmented training examples of the dSprites dataset
26

---

7
7
8
2
3
6
2
6
6
0
7
6
0
3
7
7
R
2
d
3
6
2
Figure 10: Mixup (Zhang al., 2018) and MixStyle (Zhou al., 2021) augmentations on the colored improves generalization the augmentation describes an attribute" from the empirical study of Wiles et al. (2022). When it is hard to design augmentations by hand, learning augmentations from data and regularizing these augmentations based on algebraic constraints is promising way improve generalization, which is the main claim of our paper.
MNIST, 3D Shapes, and dSprites datasets.
E.4 HEURISTIC AUGMENTATION
Fig. 10 shows the images from the colored MNIST, 3D Shapes, and dSprites datasets augmented by Mixup (Zhang et al., 2018 8) and MixStyle (Zhou et al., 2021). We can observe that MixStyle actually modifies the colors of the images the colored MNIST dataset, which may explain why its performance is good in Table 1. Thus, our results also support the claim "heuristic augmentation
27


Reviews:
[{"review_id": "tALHX5dHr0", "reviewer": "Reviewer_fyte", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies domain generalization, but not in its standard setting, in a new \"combination shift\" setting instead. The paper also proposes an algebraic formulation for the combination shift problem and proposes some augmentation methods. The paper also has some empirical results. ", "summary_of_the_review": "an interesting discussion, but probably needs further discussions (especially on the empirical end) to be considered for publication. ", "strength_and_weaknesses": "- strength\n    - the setting \"combination shift\" is reasonably new\n    - the algebraic formulation is interesting and might indicate some powerful methods in the future. \n- weakness\n    - whether the \"combination shift\" is important needs more discussion. It seems the entire motivation behind this new setting is that this setting is more feasible, which does not seem to be a good reason to study this problem. \n    - the empirical scope of this paper is quite limited. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rUBKEwQNDM", "reviewer": "Reviewer_CL9J", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper, authors present a new problem of combination shift (slightly different from the domain generalization problem) where examples from certain domain and label combination pairs are missing in the training data and the hope is to generalize to these examples. The authors discuss this problem with algebraic formulation and present a method that they call equivariant disentangled transformation (EDT). Experimental results highlight issues with some existing techniques and highlight the efficacy of the proposed approach in semi-synthetic settings on several datasets. ", "summary_of_the_review": "Overall, in its current form, the paper is very hard to read even with the preliminaries and setup in Section 3. In particular, it is unclear how EDT is simply followed by their algebraic requirements as claimed in the abstract. Experimental results are limited to small-scale (MNIST-like) datasets with marginal improvements over MixStyle. Authors are encouraged to include results on semi-synthetic in Domainbed datasets. ", "strength_and_weaknesses": "**Strength** \n- The proposed variant of the domain generalization problem is well-motivated, highly relevant and to the best of my knowledge seems original \n- Authors have taken a good effort in setting up preliminaries for algebra used in the paper \n\n\n**Weakness** \n- There are three major weaknesses of the paper: \n  -  The writing of the paper is complex and hard to follow for someone who is not well-versed in algebraic formulations. Starting in the abstract and introduction authors use terms like \"equivariance\", and \"disentanglement requirements\" without defining what they mean. \n  - It is also very unclear if the proposed EDT algorithm follows naturally as claimed in the abstract. While Figure 2 is clear, the cited equations do not naturally seem to follow to me. \n  - The experimental validation of EDT is limited to MNIST-like datasets. Authors are encouraged to simulate combination shift settings on Domainbed datasets [1]. Moreover, authors observe modest empirical improvements over MixStyle making it unclear how the proposed augmentation technique will work in other vision datasets. \n- Due to the algebraic notation used in the paper, most of the paper is spent on setting up the notation and authors come to the combination shift problem very late in the paper (page 6) which is still mixed with a lot of notations that at times gets hard to keep track of. \n\n\n[1] Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iN4a2UC57w", "reviewer": "Reviewer_ZeBu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors introduce the combination shift problem towards generalization - especially when the goal is to learn with as few combinations are observed in data. Towards this goal, the author extend the definition of disentaglement beyond of invariances to group actions - highlighting the necessity to exploit the equivariance structure. The authors then provide a strategy to effectively learn data augmentations towards the combination shift problem and improve generalization and subsequently provide proof of concept experiments.", "summary_of_the_review": "In my opinion, the strengths of the paper out weigh the weaknesses - and therefore recommend border line accept (initial review)", "strength_and_weaknesses": "**Strengths:**\n1. The combination shift problem is very well motivated, appropriately formulated and most importantly is an important problem in real world settings \n2. Most of the paper (and appendix) is very well written and clear\n3. The proposed algorithm (sub section 4.3) is simple, without losing the majorly desired properties\n4.  The proof of concept experiments are well designed and show the use case of the proposed approach\n\n**Weaknesses**:\n1. While in definition 1, the authors assume that the product algebra in not necessarily finite (via an indexing set), it is unclear  - (the ramifications) of what happens when product decomposition is not countable. The algebraic regularization subsection - maybe is indicative of this - but currently the clarity of that is on the lower side.\n2. It is unclear if there is a strategy to learn the product decomposition (without underlying knowledge about the data - and especially in relation to 1 above). Please include synthetic proof of concept experiments to showcase the same.\n\n**Minor:**\n1. Is there a citation for the 1st line of the introduction? From cognitive studies/ neuroscience ?\n2.  Work [1] which assumes invariance to all groups initially (unless evidence shows otherwise) and then narrows over the subspace lattice  to identify the groups to be not invariant to is relevant work\n\n\n**References**\n1. Mouli, S. Chandra, and Bruno Ribeiro. \"Neural Networks for Learning Counterfactual G-Invariances from Single Environments.\" ICLR 2021", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fQG5y69BN8", "reviewer": "Reviewer_W6bv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "1. The authors propose to study a problem that they call combination shift: a simplified version of domain generalization in which all environments and labels are available at test time, but not necessarily all combinations.\n2. Higgins et al [2018] define disentanglement based on equivariance wrt to the action of a product groups. This paper slightly extends that discussion from groups to more general algebraic structures, in particular semi-groups and monoids.\n3. Starting from this definition, the authors argue that one could solve the combination shift problem if the action of domain shifts and label shifts on the input data is known.\n4. They point out that this action can be learned from data pairs showing a sample before and after the domain or label has been shifted, but all other aspects are kept constant. They also and discuss learning these actions from unpaired datasets.\n5. They demonstrate the approach in experiments.", "summary_of_the_review": "Formulating disentanglement and domain generalization through algebraic structure is an excellent approach, and there are some good ideas in this paper. However, in its current form I don't think the paper meets the bar. The proposed approach hinges on identifying the (isolated) effect of domain and label shift on data representations from CycleGANs, and there is neither a theoretical guarantee for this to work nor an appropriate discussion of this step. I encourage the authors to discuss this further and to be clearer about their claims.", "strength_and_weaknesses": "Strengths:\n1. Domain generalization is a crucial and largely unsolved problem. Any progress on this question could be very impactful.\n2. It is sensible to extend Higgins et al's definition of disentanglements from groups to more general algebras.\n3. Phrasing invariance algebraically makes sense. The commuting diagrams illustrate the structure very clearly.\n4. The proposed regularizers allow for the practical operationalization of the algebraic structures.\n\nWeaknesses:\n1. The authors introduce the combination shift problem clearly. But it would be great if they could shed a bit more light on why this is a relevant problem. Are there any real-world problems that fall into this category? Or do they primarily consider this as a stepping stone to solving the full domain generalization problem? In the latter case, could they argue why progress on the combination shift problem should translate into progress on other domain generalization problems?\n2. The proposed method requires either knowing the action of domain and label shifts on the data space (act_X), or learning it from data. The authors correctly point out that such data can be learned from paired data of a sample before and after changing the corresponding factors without affecting any other sample details. But the existence of such data pairs is a strong requirement, and this requirement is not part of the problem setup (nor the introduction of the paper). Learning such augmentations from unpaired data is a much harder problem. The authors gloss over this difference around Eq. (7) and in Remark 3, but it is a crucial point. Without strong assumptions, the actions will in general not be identifiable from unpaired data. Therefore I believe that the entire approach hinges on what we could either call inductive bias or wishful thinking: ML algorithms somehow being able to identify act_X even in the absence of theoretical guarantees. Algorithms without theoretical guarantees are of course fine, but the authors could be more explicit about in which sense the algorithm is expected to work.\n3. I don't fully understand the experiment in section 5.1. How are the augmentations (act_X) learned here? Could the authors show the effect of the learned act_X somewhere in the appendix?\n4. The writing could at times be clearer.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject