Year: 2020

Abstract:
Humans leverage compositionality for flexible and efficient learning, but current machine learning algorithms lack such ability. Despite many efforts in specific cases, there is still absence of theories and tools to study it systematically. In this paper, we leverage group theory to mathematically prove necessary and sufficient conditions for two fundamental questions of compositional representations. (1) What are the properties for a set of components to be expressed compositionally. (2) What are the properties for mappings between compositional and entangled representations. We provide examples to better understand the conditions and how to apply them. E.g., we use the theory to give a new explanation of why attention mechanism helps compositionality. We hope this work will help to advance understanding of compositionality and improvement of artificial intelligence towards human level.

heading: 1 INTRODUCTION
text: Humans recognize the world and create imaginations in a supple way by leveraging systematic compositionality to achieve compositional generalization, the algebraic capacity to understand and produce large amount of novel combinations from known components (Chomsky, 1957; Montague, 1970). This is a key element of human intelligence (Minsky, 1986; Lake et al., 2017), and we hope to equip machines with such ability.
Conventional machine learning has been mainly developed with an assumption that training and test distributions are identical. Compositional generalization, however, is a type of out-of-distribution generalization (Bengio, 2017) which has different training and test distributions. In compositional generalization, a sample is a combination of several components. For example, an image object may have two factor components of color and rotation. In language, a sentence is composed of the lexical meanings and the grammatical structure. The generalization is enabled by recombining seen components for an unseen combination during inference.
One approach for compositional generalization is to learn compositional representations1, or disentangled representation (Bengio, 2013), which contain several component representations. Each of them depends only on the corresponding underlying factor, and does not change when other factors change. Please see Section 3 for details. Multiple methods have been proposed to learn compositional representations. However, little discussion has been made for some fundamental questions. What kind of factor combinations can be expressed in compositional representation? Though there are some common factor components such as colors and size, what property enable them? When a set of components satisfy the conditions, what kind of mappings are available between the entangled and compositional representations? Can we use the conditions to explain compositionality in conventional models such as attention?
In this paper, we mathematically prove two propositions (Proposition 1.1 and Proposition 1.2) for necessary and sufficient conditions regarding compositional representations. We construct groups for changes on representations, and relate compositional representation with group direct product, and compositional mapping with group action equivalence (Higgins et al., 2018). Then, we use theorems and propositions in group theory to prove the conditions.
1The word “representation” in this paper refers to variables, not group representation.
Proposition 1.1 (Compositional representation). A set of components can be expressed compositionally if and only if the subgroup product equals to the original group, each component subgroup is normal subgroup of the original group, and the group elements intersect only at identity element.
Proposition 1.2 (Compositional mapping). Given compositional representation, a mapping is compositional if and only if each component has equivalent action in compositional and entangled representations, and for each element of the entangled representation, the orbits intersect only at the element.
Please see Proposition 4.2 and Proposition 4.10 for symbolic statements. We also provide examples to better understand the conditions and how to use them (Section 5). For representations, we see that whether the components can be expressed with compositional representation does not depend only on each component itself, but also on their combination, and the possible values to take. We use the condition for compositional mapping to explain some existing neural network models and tasks, e.g., attention mechanism, spacial transformer and grammar tree nodes. We hope, with these examples, the conditions will be used for validating different compositional representations and mappings, and guiding designs of tasks and algorithms with compositionality. Our contributions can be summarized as follows.
• We propose and prove necessary and sufficient conditions for compositional representation and compositional mapping.
• We provide examples to understand and use the conditions, such as new explanation of attention models.

heading: 2 RELATED WORK
text: Human-level compositional learning (Marcus, 2003; Lake & Baroni, 2018) has been an important open challenge (Yang et al., 2019; Keysers et al., 2020). There are recent progress on measuring compositionality (Andreas, 2019; Lake & Baroni, 2018; Keysers et al., 2020) and learning language compositionality for compositional generalization (Lake, 2019; Russin et al., 2019; Li et al., 2019; Gordon et al., 2020; Liu et al., 2020) and continual learning (Jin et al., 2020; Li et al., 2020).
Another line of related but different work is statistically and marginally independent disentangled representation learning (Burgess et al., 2018; Locatello et al., 2019). This setting assumes marginal independence between underlying factors hence does not have compositional generalization problem. On the other hand, compositional factors may not be marginally independent.
Understanding of compositionality has been discussed over time. Some discussions following Montague (1970) uses homomorphism to define composition operation between representations. Recently, Higgins et al. (2018) proposes definition of disentangled representation with group theory. The definition is the base of this paper, and we focus on proving the conditions. Li et al. (2019) defines compositionality probabilistically without discussing conditions to achieve it. Gordon et al. (2020) finds compositionality in SCAN task can be expressed as permutation group action equivalence. This equivalent action is on a component subgroup, but it does not discuss equivalent action on the whole group and the relations between them. There are also other works related to group theory in machine learning (Kondor, 2008; Cohen & Welling, 2016; Ravanbakhsh et al., 2017; Kondor & Trivedi, 2018). However, the previous works do not prove conditions for compositional representation or mapping.
In this paper, we provide and theoretically prove necessary and sufficient conditions for compositional representations and compositional mappings. We use definitions, propositions and theorems from group theory. Please refer to Appendix A. Some of them are summarized in books, such as Dummit & Foote (2004) and Gallian (2012), and we refer to them in the later sections.

heading: 3 REPRESENTATIONS
text: In this section, we introduce the definitions of representation and compositional representation used in this paper.
Representation in this paper is consistent with the concept in neural network literature. It is a variable, and its value depends on each sample. For example, it can be activations for a layer in a neural network. The values of the activations depend on the network input. Network input and output are also called representations.
Compositional representation in this paper means a representation with several separated component representations. It is also called disentangled representation in some literature. “Separated” means that the representation is the concatenation of the component representations. Each component representation corresponds to a underlying component, or a generative factor. When a representation is not compositional, it is an entangled representation.
In the examples in Figure 1, the components are color and shape. The upper images are entangled representations, where color and shape are in the same image. However it is not a compositional representation, because an image is not a concatenation of a color part and a rotation part. The lower vectors are compositional representations, where the left vector is for color and the right vector is for shape.

heading: 4 NECESSARY AND SUFFICIENT CONDITIONS
text: In this section, we derive necessary and sufficient conditions for compositionality step by step. We first construct groups for representations. We then describe compositionality with group properties, and study the conditions for them. Based on that, we further study the conditions for mappings between two representations.

heading: 4.1 GROUPS ON REPRESENTATIONS
text: Compositionality arises when we compare different samples, where some components are the same but others are not. This means compositionality is related to the changes between samples. These changes can be regarded as mappings, and since the changes are invertible, the mappings are bijective. To study compositionality we consider a set of all bijections from a set of possible representation values to the set itself, and construct a group with the following Proposition 4.1. Proposition 4.1. Let X be any nonempty set and SX be the set of all bijections from X to itself. The set SX is a group under function composition2. Dummit & Foote (2004) P.29
Since SX contains all bijections, the group SX acts on the set X (Definition A.9), and the action is transitive (Definition A.12). We consider two representations and corresponding sets. X is original entangled representation, and Y is compositional representation. We create group G on set X , and group H on set Y .

heading: 4.2 COMPOSITIONAL REPRESENTATION
text: When multiple hidden variables live in the same representation, and cannot be separated by simply splitting the representation, then these variables are entangled in the representation. For example,
2Function composition is different from compositionality being discussed.
rotation and color are two hidden variables and they are both in a representation of image. We hope to extract the hidden variables by disentangling the representation. Suppose X is a set of entangled representations, and Y is a set of compositional representations. Y has Cartesian product ofK small sets Y1, . . . , YK . We hope to find the conditions the changes on X can be expressed by the changes on the components in Y .
A component corresponds to a set. For example, color component can take blue, green, etc., from a set of colors. With Proposition 4.1, we can construct a group for each component. With Definition A.2, each of these groups is a subgroup of the original group.
We consider K subgroups. We hope the changes on the entangled representation X are equally expressed by changes on the compositional representation Y . This means group G should be isomorphic with the external direct product (Proposition A.1) of the subgroups H = N1 × · · · ×NK . The following Proposition 4.2 has the necessary and sufficient conditions. Proposition 4.2. N1, . . . , NK are subgroups of group G. G is isomorphic to the external direct product of the subgroups if and only if G is internal direct product of the subgroups. From Definition A.8, we have the following.
G ∼= N1 × · · · ×NK ⇐⇒  G = N1N2 . . . NK (A1) Ni / G, ∀i = 1, . . . ,K (A2) (N1 . . . Ni) ∩Ni+1 = {e}, ∀i = 1, . . . ,K − 1 (A3)
Proof. “⇐= ”: Theorem A.2. “ =⇒ ”: G andN1×· · ·×NK are isomorphism, andN1×· · ·×NK satisfies the conditions by construction in definition.
(A1) means the subgroup product should cover the original group. (A2) means all the component subgroups are normal subgroups of the original group. (A3) means the intersection of a subgroup and the previous subgroups only contain the identity element. This corresponds to Proposition 1.1. We will provide examples and look into more details in discussion section.

heading: 4.3 COMPOSITIONAL MAPPING
text: We consider to create a mapping between the representations X and Y , which we can use to design models. We first consider what property the mapping should satisfy. We then explore conditions for the properties, based on the compositional representation conditions mentioned above. To make the ideas clear, we summarize the relations between sets and groups in Figure 2 (left). We have a isomorphism µ between group G and group H . G is constructed from set X and H is constructed from set Y . ϕ is a mapping between X and Y . We denote N ′i = {h ∈ H|hi ∈ Ni, hj = e, ∀j 6= i}. Then the relations between subsets and subgroups are in Figure 2 (right).
We first consider what property we hope the mapping ϕ to have. We hope both representations always change together. However, the actions are defined for different groups G and H . With Proposition 4.5 below, we define action of the same group on both representations. Proposition 4.3. For any group G and any nonempty set X there is a bijection between the actions of G on X and the homomorphisms of G into SX . Dummit & Foote (2004) p.43,p.114 Lemma 4.4. The function composition of homomorphisms is a homomorphism. Clark (1984) p.45.
Proposition 4.5. For groups G and H , G ∼= H with bijection µ, H acts on X with homomorphism σ : H → SX , then G acts on X with homomorphism σ ◦ µ : G→ SX .
Proof. With Proposition 4.3, we only need to prove σ ◦ µ is homomorphism. This is true because σ and µ are both homomorphisms (Lemma 4.4).
With such action, we look into more details of the requirements. When an action changes one representation, it should always changes the other representation uniquely, which means the mapping should be bijective. Also, the mapping ϕ should preserve the group action. This means the group actions on X and Y are equivalent. (Definition A.13). Note that mapping direction can be either way because the mapping is bijective.
We then consider how to make the action equivalent, with the conditions for compositional representations. We observe that H is external group acting on Cartesian set Y , the action of H on Y is product action (Definition A.10). We look at related properties as follows.
Proposition 4.6. N1×· · ·×NK has production action onX = X1×· · ·×XK , then ∀x ∈ X,∀i = 1, . . . ,K − 1 : ON1...Nix ∩O Ni+1 x = {x}.
Proof. A direct product is isomorphic to itself, so properties in Proposition 4.2 can be used.
∀x ∈ X,∀i = 1, . . . ,K − 1,∀n ∈ N1N2 . . . Ni+1, n(x) ∈ ON1...Nix ∩ONi+1x =⇒ n ∈ N1 . . . Ni ∩Ni+1 =
Prop 4.2 (C) {e} =⇒ n = e =⇒ n(x) = x
=⇒ ON1...Nix ∩ONi+1x = {x}
Proposition 4.7. N1, . . . , NK are subgroups of a group acting on a set X . If ∀x ∈ X,∀i = 1, . . . ,K − 1 : ON1...Nix ∩O Ni+1 x = {x}, then ∀x ∈ X,∀n1 ∈ N1, n2 ∈ N2, . . . , nK ∈ NK ,
n1n2 . . . nK(x) = x ⇐⇒ ni(x) = x, ∀i = 1, . . . ,K
Proof. “⇐= ”: Repeat for i = K, . . . , 1: n1n2 . . . nK(x) = n1n2 . . . nK−1(x) = · · · = x “ =⇒ ”: n1n2 . . . nK(x) = x =⇒ nK(x) = (n1n2 . . . nK−1)−1(x) =⇒ nK(x) ∈ ON1...NK−1x ∩ONKx = {x} =⇒ nK(x) = x and n1n2 . . . nK−1(x) = x Repeat for i = K − 1, . . . , 2, we have ni(x) = x, ∀i = 1, . . . ,K
Proposition 4.8. N1×· · ·×NK has production action onX = X1×· · ·×XK , then ∀x ∈ X,∀n1 ∈ N1, n2 ∈ N2, . . . , nK ∈ NK , we have n1n2 . . . nK(x) = x ⇐⇒ ni(x) = x, ∀i = 1, . . . ,K.
Proof. Proposition 4.6 and Proposition 4.7.
Since H and Y are composed by multiple components, we hope to explore whether the equivalence action property can be broken down to conditions on each component, and the relation between components. A natural condition on each component is that the action is equivalent for the component. On Y , by its structure, the orbits of each component group action on a element y intersects only at y, so we hope this condition also applies to X . With Proposition 4.9, we prove in the following Proposition 4.10 that the two conditions together is actually the necessary and sufficient condition for the equivalent action.
Proposition 4.9. If ∀x ∈ X,∀i = 1, . . . ,K − 1 : ON1...Nix ∩ O Ni+1 x = {x}. ∀i,∀x ∈ X : Ni eq. acts on ONix and O Ni ϕ(x), then ϕ : X → Y is one-to-one.
Proof. Any component has bijective mapping, and preserves action. We prove by contradiction.
∀x, x′(x 6= x′) ∈ X,∃g = n1 . . . nK ∈ N1N2 . . . NK : x′ = g(x) (transitive, Section 4.1) suppose ϕ(x) = ϕ(x′), then ϕ(x) = ϕ(g(x)) = ϕ(n1 . . . nK(x)) =
presv. n1 . . . nK(ϕ(x))
=⇒ Prop 4.7 ϕ(x) = ni(ϕ(x)) = presv. ϕ(ni(x)),∀i = 1, . . . ,K =⇒ bij. x = ni(x),∀i = 1, . . . ,K
=⇒ Prop 4.7 x = n1 . . . nK(x) = g(x) = x ′ (contradiction) =⇒ ϕ(x) 6= ϕ(x′)
Proposition 4.10. G ∼= N1 × · · · ×NK . With ϕ : X → Y ,
G eq. acts on X and Y ⇐⇒
{ ∀x ∈ X,∀i = 1, . . . ,K − 1 : ON1...Nix ∩O Ni+1 x = {x} (B1)
∀i,∀x ∈ X : Ni eq. acts on ONix and O Ni ϕ(x) (B2)
Proof. “ ⇐= ”. From Definition A.13, an equivalent action is bijective and preserves action. We first prove the mapping preserves action.
∀g = n1n2 . . . nK ∈ G,∀x ∈ X,ϕ(g(x)) = ϕ(n1n2 . . . nK(x)) = n1n2 . . . nK(ϕ(x)) = g(ϕ(x)) We then prove that ϕ is bijection on X → Y . We prove it is one-to-one, onto, well-defined. One-to-one: Proposition 4.9. Onto: ∀y ∈ Y,∀x ∈ X∃n1n2 . . . nK (transitive, Section 4.1) : y = n1n2 . . . nK(ϕ(x)) = ϕ(n1n2 . . . nK(x)), so ∃x′ = n1n2 . . . nK(x) ∈ X : y = ϕ(x′). Welldefined: H has production action on Y , and ϕ is onto, and with Proposition 4.6 and Proposition 4.9, ϕ−1 : Y → X is one-to-one, so ϕ is well-defined. “ =⇒ ”. We first prove (B2). Since subgroup has the same operation with the original group, the equivalent action holds for each component. We then prove (B1).
∀x ∈ X,∀i = 1, . . . ,K − 1,∀x′ ∈ ON1...Nix ∩ONi+1x ,∃n ∈ N1 . . . Ni, n′ ∈ Ni+1 : x′ = n(x) = n′(x) =⇒
bij. ϕ(nx) = ϕ(n′x) =⇒ presv. nϕ(x) = n′ϕ(x) =⇒ n−1n′ϕ(x) = ϕ(x)
=⇒ Prop 4.8 n′ϕ(x) = ϕ(x) =⇒ presv. ϕ(n′x) = ϕ(x) =⇒ bij. n′(x) = x =⇒ x′ = x
To summarize, this proposition says that to find whether a mapping has equivalent action on both representations, we only need to examine whether, for each element, the action is equivalent for each subgroup, and the intersections of orbits only contains the element. This corresponds to Proposition 1.2. In cases both representations are entangled, and we hope to have a compositional representation to connect them, we can use the conditions twice for the mapping. We will discuss the relation to machine learning and compositional generalization, and provide examples in the discussion section.

heading: 5 DISCUSSIONS
text: In this section, we provide examples for the conditions of compositional representation and mapping, and look into more insights for better understanding. These examples also serves as applications of the derived results, and we will also discuss about what we learnt from them.

heading: 5.1 COMPOSITIONAL REPRESENTATION
text: We provide examples for the boundaries of compositional representation conditions. Proposition 5.1 is used to test normal subgroups. Proposition 5.1 (Normal Subgroup Test). A subgroup H of G is normal in G if and only if xHx−1 ⊆ H,∀x ∈ G. Dummit & Foote (2004) p.82 Theorem 6(5), Gallian (2012) p.186 Theorem 9.1.
Object transformation We think about examples violating conditions in Proposition 4.2. For a two dimensional geometric object (e.g. image of letter “P”), we consider rotation group N1, and mirror reflection group N2.
If G = N1, and N2 contains non-identity element, then G 6= N1N2, because any combination of rotation does not generate a reflection. This violates (A1).
We set G = N1N2, and both rotation and reflection take all possible values. In this case, both N1 and N2 are normal subgroups of G, N1, N2 / G. However the intersection of N1 and N2 does not only contain identity, N1 ∩ N2 6= {e}. For example, rotating by π is equivalent with vertical reflection then horizontal reflection. Therefore, this violates (A3).
If we constrain reflection action to horizontal reflection, and leave rotation to have all possible values, then rotation N1 and horizontal reflection N2 form a group G. In this case, N1 and N2 only intersects at identity, N1 ∩ N2 = {e}. However, N2 is not normal subgroup of G. If we set rotation action n1 to be rotate by π/2, n−11 is to rotate by −π/2. Action of horizontal reflection has n2 = n −1 2 . We find n1n2n −1 1 /∈ N2, because rotate by π/2, flip horizontally, and rotate −π/2, then it does not recover the original by a horizontal reflection. With Proposition 5.1, N2 is not a normal subgroup of G, so this violates (A2).
We further think about an example, where we also constrain the rotation to be rotate opposite (by π), and reflection remains only horizontal. they form group G. In this case, rotation and reflection are both normal subgroups of G, N1, N2 / G. Also, N1 and N2 only have identity in their intersection N1 ∩N2 = {e}. Therefore, N1 and N2 can be expressed by compositional representation. We have another example with color as N1 and combination of rotation and reflection as N2. They form group G. In this case, regardless the elements in the sets, N1 and N2 are always normal subgroups of G, and their intersection always only contains identity. So they can be expressed as compositional representation.
From these examples, we see that whether the components can be expressed with compositional representation does not depend only on each component itself, but also on their combination, and the possible values to take. For some combinations, they are not influenced by possible values.
Grammar tree node We also look at an example for language grammar tree node. In a grammar tree, each node G has multiple children. We regard each child as a component Ni, i = 1, . . . ,K. We then consider whether the components can be expressed by compositional representation.
For context free grammar, G = N1N2 . . . NK . Each Ni is normal subgroup of G, because a change in one children does not affect others. Also, the intersection of them only contains identity, because each sub-tree is separated. Therefore, a tree node with context free grammar is possible to be expressed with compositional representation.
We also look at an example of root node in syntactic tree for fixed length sentences. When at least one subgroup actions change the phrase length, the product of Ni may be not a group, because it may change the sentence length (G 6= N1N2 . . . NK). This means G does not fit the conditions. Note that such grammar is not a context free grammar.

heading: 5.2 COMPOSITIONAL MAPPINGS
text: Conditions for compositional mapping can be used to design models for the relation between two representations. We first describe the connection with machine learning, and then use the conditions to explain some existing neural network models and tasks.
Model training and architecture for compositional generalization We consider samples in training. For compositional generalization, some elements in the whole set Y (or X) are missing, but for each subset Yi, the elements are complete. For condition (B2) in Proposition 4.10, each subset has complete samples, so it is satisfied. For condition (B1), the set has missing elements, so we do not have information to tell whether it is satisfied. To address this problem for condition (B1), we may constraint the mapping ϕ that the images for each component intersect at only one element.
Attention mechanism Attention mechanism is used for compositional modelings (Goyal et al., 2019; Russin et al., 2019; Li et al., 2019). We consider a problem that there are two components for an object. One component is the position of the object, and the other is the local shape (or word for language processing) of the object. We look into an attention network that combines the two components to generate output.
We first check whether the two components can be expressed as compositional representation. Set N1 is group for position, N2 is group for shape, and G = N1N2. For an object, if we change shape, position, and shape back, the shape does not change. Similarly, change position, shape and position back, the position does not change. With Proposition 5.1, N1 and N2 are both normal subgroups of G. Also,N1∩N2 = {e} because changing position does not change shape, and changing shape does not change position. This means the components can be expressed as compositional representation.
We then check whether the model is compositional mapping. First, we look at each component. For both position and shape, the mapping is bijective and preserves action. Second, we look at the orbits of images. Since the shape only changes locally, it does not change position, and position does not change shape. Therefore, the model is compositional.
Note that we do not assume that the attention is sparse for each sample. This is different from some conventional explanations (Bengio, 2017; Goyal et al., 2019) of attention mechanism. The attention helps compositional generalization not because it is dynamically sparse, but it fits the conditions. For example, when there are multiple positions to attend in one attention map, it may still fit the conditions.
Spatial transformer In the example of attention mechanism, position is aligned with one build-in dimension of data structure. However, this is not necessary. Here, we provide another example with Spatial Transformer (Jaderberg et al., 2015) for such a case. We focus on the transformations for rotation and scaling. The data structure does not have such build-in dimensions. We see that rotation and scaling satisfy Proposition 4.2 to be expressed with compositional representation, and the mapping satisfies Proposition 4.10 to be compositional mapping.
However, if we consider rotation and shape, the network might not be compositional. For example, rotations by 0, 2π/3, 4π/3 map a triangle it to itself, but this does not apply to a square. This means if a set of rotation contains both 0 and 2π/3, it is not bijective for triangle. If it contains 0 but not 2π/3, it is not bijective for square. Therefore, it violates (B2).
Ambiguous context free grammar We discussed that a node for context free grammar is able to be expressed with compositional representation. However, when there is syntactic ambiguity, we are not able to get the compositional mapping. This violates the condition (B1), because the orbits have more than one elements in the intersection.

heading: 6 CONCLUSION
text: We use group theory to prove necessary and sufficient conditions for compositional representation and mapping. We discuss examples for the conditions, and understand the boarders of them. We also provide new explanations for existing methods. We expect the conditions will help validating compositional representations and mappings, and guide designs of tasks and algorithms. We hope this work will help to advance compositionality and artificial intelligence research.

heading: A PRELIMINARIES FOR GROUP THEORY
text: In this section, we go through some preliminaries for group theory. We provide widely used definitions, propositions and theorems, with references for more details.
A.1 GROUPS
Definition A.1 (Group). A group is an ordered pair (G, ◦) where G is a set and ◦ is a binary operation on G satisfying associativity, identity e and inverses. We say G is a group if the operation ◦ is clear from the context, and we also omit ◦. Dummit & Foote (2004) p.16 (also Gallian (2012) p.43) Definition A.2 (Subgroup). If a subset H of a group G is itself a group under the operation of G, we say that H is a subgroup of G. Gallian (2012) p.61 (also Dummit & Foote (2004) p.46) Definition A.3 (Normal subgroup). A subgroupH of a groupG is called a normal subgroup ofG if aH = Ha, ∀a ∈ G. We denote this by H / G. Dummit & Foote (2004) p.82, Gallian (2012) p.185
A.2 MAPPINGS
Definition A.4 (Group homomorphism). A homomorphism ϕ from a group G to a group H is a mapping from G into H that preserves the group operation, i.e., ∀a, b ∈ G,ϕ(ab) = ϕ(a)ϕ(b). Gallian (2012) p.208, Dummit & Foote (2004) p.36. Definition A.5 (Group isomorphism). The map ϕ : G→ H is called an isomorphism and G and H are said to be isomorphic or of the same isomorphism type, writtenG ∼= H , if ϕ is a homomorphism and a bijection. Dummit & Foote (2004) p.37, Gallian (2012) p.128.
A.3 PRODUCTS
Definition A.6 (Product of subgroups). Let H1, . . . ,HK be subgroups of a group and define H1H2 . . . HK = {h1h2 . . . hK |hi ∈ Hi,∀i = 1, . . . ,K}. Dummit & Foote (2004) p.93 Definition A.7 (External direct product). Let G1, . . . , GK be a finite collection of groups. The external direct product of G1, . . . , GK , written as G1 × · · · × GK , is the set of all K-tuples for which the ith component is an element of Gi and the operation is component wise. In symbols,
G1 × · · · ×GK = {(g1, . . . , gK)|gi ∈ Gi}, (g1, . . . , gK)(g′1, . . . , g′K) = (g1g′1, . . . , gKg′K) Gallian (2012) p.162, Dummit & Foote (2004) p.152 Proposition A.1 (External direct product is a group). IfG1, . . . , GK are groups, their external direct product is a group. Dummit & Foote (2004) p.153. Proposition 1. Definition A.8 (Internal direct product). LetH1, . . . ,HK be a finite collection of normal subgroups of G. We say that G is the internal direct product of H1, . . . ,HK , if
G = H1H2 . . . HK and H1H2 . . . Hi ∩Hi+1 = {e}, ∀i = 1, . . . , n− 1 Gallian (2012) p.197, Dummit & Foote (2004) p.172. Theorem A.2 (Recognition theorem). If a groupG is the internal direct product of a finite number of subgroupsH1, . . . ,HK , thenG is isomorphic to the external direct product ofH1, . . . ,HK . Gallian (2012) p.198, Dummit & Foote (2004) p.171.
A.4 GROUP ACTIONS
Definition A.9 (Group action). A group action of a group G on a set X is a map from G×X to X (written as g(x),∀g ∈ G, x ∈ X) satisfying the following properties:
g1(g2(x)) = (g1g2)(x),∀g1, g2 ∈ G, x ∈ X and e(x) = x, ∀x ∈ X Dummit & Foote (2004) p.112 Definition A.10 (Product action). G = G1×· · ·×GK is a group, andX = X1×· · ·×XK is a set. G acts on X by the rule (g1, . . . , gK)(x1, . . . , xK) = (g1x1, . . . , gKxK). Cameron et al. (2008), Praeger & Schneider (2018) p.71.
Definition A.11 (Orbit). Let G be a group action on the nonempty set X . The equivalence class OGx = {g(x)|g ∈ G} is called the orbit of G containing x. Dummit & Foote (2004) p.115 Definition A.12 (Transitive action). The action of G on X is called transitive if there is only one orbit, i.e., given any two elements x, y ∈ X there is some g ∈ G such that x = g(y). Dummit & Foote (2004) p.115 Definition A.13 (Equivalent action). Two actions of a groupG on setsX and Y are called equivalent if there is a bijection ϕ : X → Y such that ϕ(g(x)) = g(ϕ(x)) for all g ∈ G and x ∈ X . We say G eq. acts on X and Y . Lovett (2015) p.385.

Review summaries:
The paper attempts to formally explore the necessary and sufficient conditions for compositional representations, leveraging the formal tools from group theory. While the ideas look potentially promising, the presentation is fundamentally flawed, with certain key notions left without formal definitions. As a consequence, it becomes impossible to estimate the theoretical significance of the contribution or use the obtained results in practice.

This paper applies concepts from group theory to help find necessary and sufficient representations on the presence of compositionality in representations and on mappings between them.  This topic is very important, as people tend to use "compositional" in many ways, often not explicitly defined.  The paper, however, is hard to follow, because the main concepts and theorems are not adequately illustrated with examples.  In the final section, when examples are provided, it's still not clear how they apply to representation learning, the topic of this conference.  Thus, while the topic is very relevant and the approach welcome, it is hard to know what lesson we have learned from the theorems in the paper.