Necessary and Sufficient Conditions for Compositional Representations
Authors: Yuanpeng Li
Venue:  (2021)
Keywords: Compositionality

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.


Under review as a conference paper at ICLR 2021
NECESSARY AND SUFFICIENT CONDITIONS FOR COMPOSITIONAL REPRESENTATIONS
Anonymous authors Paper under double-blind review
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. (I) What are the properties for 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 compositionallty. We hope this work will help to advance derstanding of compositionality and improvement of artificial intelligence towards human level.
INTRODUCTION
Humans recognize the world and create imaginations in 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 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 type of out-of-distribution generalization (Bengio 2017) which has different training and test distributions. In compositional generalization, sample combination of several components. For example, an image object may have two factor components of color and rotation. In language, 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 representations]] or disen- tangled 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 Section for details. Multiple methods have been proposed to learn composi- tional representations. However, little discussion has been made for some fundamental questions. be expressed in compositional representation? Though there
What kind of factor combinations are some common factor components such as colors and size, what property enable them? When a of components satisfy the conditions, what kind of mappings are available between the entan- gled 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 I.I 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.
'The word "representation" in this paper refers variables, group representation.

---

Under review as a conference paper at ICLR 2021
Proposition 1.1 (Compositional representation). A set of components be expressed composi- tionally 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 identity element.
Proposition 1.2 (Compositional mapping). Given compositional representation, mapping is com- positional if and only if each component has equivalent action in compositional and entangled rep- resentations, and for each element of the entangled representation, the orbits intersect only at the element.
Please Proposition 4.2 and Proposition 44.0 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.
RELATED WORK
Human-level compositional learning (Marcus) 2003 Lake & Baroni (018) 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
compositionaliiy for compositional generalization (Lake 2019 Russin et al. 2019 et al. 2019
Gordon et al. 2020 Liu al. 2020) and continual learning (Jin et al. 2020
Li al. 2020
Another line of related but different work is statistically and marginally independent disentangled representation learning (Burgess al. 2018 Locatello al.) 2019). This setting assumes marginal independence between underlying factors hence does not have compositional generalization prob- lem. On the other hand, compositional factors may not be marginally independent.
Understanding of compositionality has been discussed over time. Some discussions following Mon- tague (1970) uses homomorphism to define composition operation between representations. Re- cently, 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 al. (2019) defines compositionality probabilistically without discussing conditions to achieve it. Gordon el al. (2020) finds compositionality in SCAN task can be expressed as permutation group action equiva- lence. This equivalent action is on 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 the- ory in machine learning (Kondor 20088 Cohen & Welling 2016 Ravanbakhsh et al. 2017 Kondor & Trivedi 2018). However, the previous works do not prove conditions for compositional represen- lation or mapping.
In this paper, we provide and theoretically prove necessary and sufficient conditions for composi- tional 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.
3 REPRESENTATIONS
In this section, we introduce the definitions of representation and compositional representation used in this paper.
2

---

Under review as a conference paper at ICLR 2021
Representation in this paper is consistent with the concept in neural network literature. It is vari- able, 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 also called representations.
Compositional representation in this paper 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 underlying component, or generative factor. When a representation compositional, it is an entangled representation.
representation with several separated component
In the examples in Figure L the components are color and shape. The upper images are entangled representations, where color and shape are in the same image. However representation, because an image is not a concatenation of a color part and rotation part. The lower vectors are compositional representations, where the left vector is for color and the right vector is for shape.
compositional
Entangled Representation
Compositional
01 01
10 10
01 10
Representation
Figure 1: Compositional representations. There components of color and shape in this ample. A compositional representation can be separated to two component representations (below), but disentangled representations cannot (above).
NECESSARY AND SUFFICIENT CONDITIONS
In this section, 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 that, further study the conditions for mappings between two representations.
4.1 GROUPS ON REPRESENTATIONS
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 regarded as mappings, and since the changes are invertible, the mappings are bijec- tive. To study compositionality tion values the set itself, and construct group with the following Proposition 4.1
consider set of all bijections from set of possible representa-
Proposition 4.1. Let be any nonempty set and Sy be the set of all bijections from to itself. The set Sx is group under function composition Dummit & Foote 2004
P.29
Since Sx contains all bijections, the group Sx acts on the (Definition A.9 and the action is transitive (Definitin A.12). We consider two representations and corresponding sets. X is original entangled representation, and is compositional representation. We create group on set X, and group H on set Y.
4.2 COMPOSITIONAL REPRESENTATION
When multiple hidden variables live the same representation, and cannot be separated by simply splitting the representation, then these variables entangled in the representation. For example,
Function composition is different from compositionality being discussed.
3

---

Under review as a conference paper at ICLR 2021
rotation and color are two hidden variables and they are both in 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 set of compositional representations. Y has Cartesian product of K small sets ...... Yx. We hope to find the conditions the changes on can be expressed by the changes on the components in Y.
component corresponds to a set. For example, color component can take blue, green, etc., from set of colors. With Proposition 4.1 we can construct group for each component. With Defini- tion each of these groups is subgroup of the original group.
We consider K subgroups. We hope the changes the entangled representation X are equally expressed by changes on the compositional representation Y. This means group G should be iso- morphic with the external direct product (Proposition [A.I) of the subgroups H NN
Nk.
The following Proposition 4.2 has the necessary and sufficient conditions.
Proposition 4.2, N1,...,N, .N 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 Defini- tion A.8 we have the following.
G = NiN2...NN
(AI)
G N =
Nr 4G vi = =1...... 1...., K
(A2)
(N1 (N.....M) N {e}, Vi I,..., K - (A3)
Proof. " ": Theorem A.2
": G: and N1 x... Nx are isomorphism, and N1 X X x Nu
satisfies the conditions by construction 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 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.
4.3 COMPOSITIONAL MAPPING
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 isomorphism μ between group G and group H. G' is constructed from set X and H is constructed from set Y. oo is mapping between X and Y. We denote N/ {h E H/ E N,, hy = e, Vj # i}. Then the relations between subsets and subgroups are in Figure (right).
G
H
N
N
P
O
ON
X
p(x)
Figure 2: Equivalent group action. We break down conditions for equivalence action on whole representations (left) to each component representation (right) and their relations.
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 both representations.
Proposition 4.3, For any group G and any nonempty set X there is bijection between the actions of G on X and the homomorphisms of into Sx Dummmi Foote (2004) 1.4
Lemma 4.4. The function composition of homomorphisms is homomorphism. Clark (984 p.45.
4

---

Under review as a conference paper at ICLR 2021
Proposition 4.5. For groups G and H, G H with bijection μs, H acts on X with homomorphism a: - Sx. then G acts on X with homomorphism o μ G - Sx-
Proof. With Proposition 4.3 and μ are both homomorphisms (Lemma 4.4).
only need prove o ja is homomorphism. This is true because
L
With such action, we look into more details of the requirements. When action changes one rep- resentation, it should always changes the other representation uniquely, which means the mapping should be bijective. Also, the mapping +p 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 bijective.
We then consider how to make the action equivalent, with the conditions for compositional repre- sentations. We observe that is external group acting on Cartesian set Y, the action of on Y is product action (Definition A.I0). We look at related properties as follows.
Proposition 4.6. N1 X x Ne has production action X X1 x Xx, then Vo E X, Vi 1,..., K O O....N
N: 2 (r}.
Proof. A direct product is isomorphic to itself, so properties in Proposition 4.2 can be used.
Ve E X, Vi I,..., K - 1, Vn E N1.2... ... N.+1, E O n n E N ......NNN.,, Prop
{c} = = n(x) =
4.2 P.0
o No.... noN-+ = {
Proposition 4.7. NI...., Nu are subgroups of a group acting on a set X. If Vo E X,
1,..., K 1 1: O N....N no Ni+s = (x), then Vo E X, Vn, E Ni, 12 E N AKK Nk.
= xx n1n2 mx(x) = + 2,
K
Proof. = ": Repeat for i K,... .....,, 1: 11 ... n mg(x) n, 12 n2 - (z) =..==
" 11112 nx (x) = x + nx(x) = (n11122 11 1
7g (z) E O Ni NR...N--11.. n = (x) = ng (x(x)) and 712 Mk (2) =
Repeat for = 1,...,,, we have (x x. Vi 1,...,
Proposition 4.8. Ni x Ne has production action on X X1 x X then Vo E X, Vni N1, E N2,..., RK E Nk. we have 71 T. = x 4 nx(x) = x, Vi 1...., K.
Proof. Proposition 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 com- ponents. A natural condition on each component is that the action is equivalent for the component. On Y, by its structure, the orbits each component group action on element intersects only at y. we hope this condition also applies to X. With Proposition 4.9 we prove in the following Proposition 10 that the two conditions together is actually the necessary and sufficient condition for the equivalent action.
Proposition 4.9. If Va E X,Vi I,..., K -1 1 ON
No n O Ni+1
(z).
Vi E X
N; eq. acts on ON and N; then y X Y is one-to-one.
p(z)
5

---

Under review as a conference paper at ICLR 2021
Proof. Any component has bijective mapping, and preserves action. We prove by contradiction.
Vz, x' # x') X, ni E Ni ..... NK x' =(x) (transitive, Section 4.1
suppose xxx) = =p(x)) then p(x) = p(g(z)) = ((m1 ....nx())) press.
71 1x (x(((x))
(z) nx((p(())) presv
((m,(x)), Vi = l....., -
(1()), Vi ,,...,
Prop
bij.
.... (1....x(x)) = g(x) x' (contradiction)
((x)) c0x')
Prop
Proposition 4.10. G x
Ng. With 0 X
Ve X, Vi 1, ,,...., K O N...N n no
Ni11
{x}
(B1)
G eq. X and Y
4i, E X N₁ eq. acts on O and O (()
(B2)
Proof. " == ". From Definition A.13 an equivalent action is bijective and preserves action. We first prove the mapping preserves action.
V/g 7222.. ... nK G, Ve E (z))() p(n1n2 ... nx (x)))) = n1 ... (x((()) (
We then prove that is bijection X + Y. We prove it is one-to-one, onto, well-defined. One-to-one:
Proposition 4.9 Onto: Vy E Y, Va E X_n ... Rk (transitive, Section 4.1
n2 ... (x(()zz)
şp (2 ... (x)), so 3rd
n2 ... (x X y o (z).. Well-
defined: H has production action on Y, and yp is onto, and with Proposition and Proposition
40 Y - X is one-to-one, so yp 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).
Vr E X, Vi 1..... K 1, Va' N....... n N En E N1 ... ....N,, NN+1:
= n(x) nl n1(x) bij.
<((x)) = ((('x) 7 np(s)) = n'v(xx = n='n((()) = p(x)
prese.
n n'u((x) (p(r)
7 p(n'rr) p(x))
n' n'(x)
x' =x
Prople 4.8
presv.
bij.
To summarize, this proposition says that to find whether a mapping has equivalent action on both representations, 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 Propo- sition [.2 In cases both representations are entangled, and we hope have compositional rep- resentation to connect them, we can use the conditions twice for the mapping. We will discuss the relation machine learning and compositional generalization, and provide examples in the discus- sion section.
5 DISCUSSIONS
In this section, we provide examples for the conditions 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.
5.1 COMPOSITIONAL REPRESENTATION
We provide examples for the boundaries of compositional represectation conditions. Proposition 5.] used to test normal subgroups. Proposition 5.1 (Normal Subgroup Test). A subgroup H of G is normal in G if and only if -Hx C H, Vx e G. Dummit & Foote (2004) p.82 Theorem 6(5), Gallian (2012) 186 The-
orem 9.1.

---

Under review as a conference paper at ICLR 2021
Object transformation We think about examples violating conditions in Proposition 4.2 For two dimensional geometric object (e.g. image of letter "P"), we consider rotation group N1. and mirror reflection group N2-
G = N1. and N2 contains non-identity element, then G * N2, because any combination of rotation does not generate reflection. This violates (A1).
We set G = N2, and both rotation and reflection take all possible values. In this case, both Ni and N2 are normal subgroups of G, Ni, 4 G. However the intersection of Ni and N₂ does not only contain identity, N1 n N₂ * {e}. For example, rotating by is equivalent with vertical reflection then horizontal reflection. Therefore, this violates (A3).
we constrain reflection action to horizontal reflection, and leave rotation to have all possible values, then rotation N1 and horizontal reflection N2 form group G. this case, Ni and N2 only intersects at identity, N1 n N2 = {e). However, N2 is not normal subgroup of G. If we set rotation action ni to be rotate by n/2, nj is to rotate by - Action of horizontal reflection has n2 = n22- We find ni & N2. because rotate by x x/2. flip horizontally, and rotate - - -22 then does not recover the original by horizontal reflection. With Proposition 5.1 N2 is not 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 x), and reflection remains only horizontal. they form group G. In this case, rotation and reflection are both normal subgroups of G, N1, N2 a G. Also, N₁ and N2 only have identity their intersection Nı n N2 {e). Therefore, N1 and N2 can be expressed by compositional representation.
We have another example with color as N₁ and combination of rotation and reflection as N2. They form group G. In this case, regardless the elements in the sets, N1 and N₂ are always normal subgroups of G, and their intersection always only contains identity. So they can expressed as compositional representation.
From these examples, we see that whether the components can be expressed with compositional representation does not depend only each component itself, but also 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 grammar tree, each node G has multiple children. We regard each child component N;, I...,, We then consider whether the components can expressed by compositional representation.
For context free grammar, G = C N2. Each N; is normal subgroup of G, because change one children does not affect others. Also, the intersection them only contains identity, because each sub-tree is separated. Therefore, tree node with context free grammar is possible to be expressed with compositional representation.
We also look an example of root node in syntactic tree for fixed length sentences. When least one subgroup actions change the phrase length, the product of N; may be not a group, because may change the sentence length (G * N2 Nk). This means G does not fit the conditions. Note that such grammar is not a context free grammar.
5.2 COMPOSITIONAL MAPPINGS
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 miss- ing, but for each subset Y, the elements are complete. For condition (B2) in Proposition 40 each subset has complete samples, 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 (B I), may constraint the mapping yp that the images for each component intersect only element.

---

Under review as a conference paper at ICLR 2021
Attention mechanism Attention mechanism is used for compositional modelings (Goyal al, 2019 Russin et al., 2019 Li et al, 2019). We consider a problem that there are two components for 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 N2 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 .N and N₂ both normal subgroups of G. Also, N1NN2 = } 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 the orbits of images. Since the shape only changes locally, it does not change position, and position does not change shape. Therefore, the model 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 al. (019) 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 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. 2013) 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 10 to be compositional mapping.
However, if we consider rotation and shape, the network might not be compositional. For example, rotations by 0, 2nT 2//3 4x/3 map a triangle to itself, but this does not apply to a square. This means if a set of rotation contains both 0 and 2 2r/3,, it is not bijective for triangle. If it contains 0 but not 2T/ /3, it not bijective for square. Therefore, it violates (B2).
Ambiguous context free grammar We discussed that 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.
6 CONCLUSION
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.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jacob Andreas. Measuring compositionality in representation learning. In International Confer- ence on Learning Representations, 2019. URL httts::/ net/
forum? wwt./forttoottttoooooo
HJz05o0qK7
Yoshua Bengio. Deep learning representations: Looking forward. In International Conference on Statistical Language and Speech Processing, pp. 1-37. Springer, 2013.
Yoshua Bengio. The consciousness prior. arXiv preprint 1rXiv:1709.085585 2017.
Christopher P Burgess, Irina Higgins, Arka Pal, Loic Matthey, Nick Watters, Guillaume Des- jardins. and Alexander Lerehner. Understanding disentangling in B-vae. arXiv preprint arXiv:1804.03599 2018.
Peter Cameron, Daniele A Gewurz, and Francesca Merola. Product action. Discrete mathematics, 308(2-3):386-394, 2008.
Noam Chomsky. Syntactic structures. Walter de Gruyter, 1957.
Allan Clark. Elements of abstract algebra. Courier Corporation, 1984.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International confer- ence on machine learning, pp. 2990-2999, 2016.
David Steven Dummit and Richard M Foote. Abstract algebra, volume 3. Wiley Hoboken, 2004.
Joseph Gallian. Contemporary abstract algebra. Nelson Education, 2012.
Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. Permutation equivari- models for compositional generalization language. In International Conference on Learning Representations, 2020. URL
Anirudh Goyal, Alex Lamb, Jordan Hoffmann, Shagun Sodhani, Sergey Levine, Yoshua Bengio, and Bernhard Schölkopf. Recurrent independent mechanisms. arXiv preprint arXiv: 10893, 2019.
Irina Higgins, David Amos, David Pfau, Sebastien Racaniere, Loic Matthey, Danilo Rezende, and Alexander Lerchner. Towards a definition of disentangled representations. arXiv preprint arXiv: 2018.
Max Jaderberg, Karen Simonyan, Andrew Zisserman, et al. Spatial transformer networks. In Ad- vances in neural information processing systems, pp. 2017-2025, 2015.
Xisen Jin, Junyi Du, and Xiang Ren. Visually grounded continual learning of compositional seman- tics. arXiv preprint 2000:00000.00785 2020.
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. Measuring compositional generalization: com- prehensive method on realistic data. In International Conference on Learning Representations, 2020. httpst//t//
net. http://oommmmmmmmmmm wtwpemmmmm.dSSyeeennn
Imre Risi Kondor. Group theoretical methods in machine learning, volume 2. Columbia University New York, 2008.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. In International Conference Machine Learning, pp- 2747-2755, 2018.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of peruuecce-t--eqqeeee recurrent networks. In International Conference on Machine Learning, pp. 2879-2888, 2018.

---

Under review as a conference paper at ICLR 2021
Brenden M Lake. Compositional generalization through meta tow-eenee----squeeeee learning. In Advances in Neural Information Processing Systems, pp. 9791-9801, 2019.
Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel Gershman. Building machines that learn and think like people. Behavioral and Brain Sciences, 40, 2017.
Yuanpeng Li, Liang Zhao, Jianyu Wang, and Joel Hestness. Compositional generalization for prim- itive substitutions. In Proceedings of the 2019 Conference Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 4284-4293, 2019.
Yuanpeng Li, Liang Zhao, Kenneth Church, and Mohamed Elhoseiny. Compositional language continual learning. In International Conference on Learning Representations, 2020. URL
net wot.
Qian Liu, Shengnan An, Jian-Guang Lou, Bei Chen, Zeqi Lin, Yan Gao. Bin Zhou, Nanning Zheng, and Dongmei Zhang. Compositional generalization by learning analytical expressions. arXiv preprint arXiv:2006.1063 2020.
Francesco Locatello, Stefan Bauer, Mario Lucie, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentangled representations. International Conference on Machine Learning, pp. 4114- 4124, 2019.
Stephen Lovett. Abstract Algebra: Structures and Applications. CRC Press, 2015.
Gary Mareus. The algebraic mind: Integrating connectionism and cognitive science. MIT press, 2003.
Marvin Minsky, Society of mind. Simon and Schuster, 1986.
Richard Montague. Universal grammar. Theoria, 36(3) 1970.
Cheryl E Praeger and Csaba Schneider. Permutation groups and cartesian decompositions, volume 449. London Mathematical Society Lecture Note Series, 2018.
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Equivariance through parameter- sharing. arXiv preprint arXiv: 1702.08888, 2017.
Jake Russin, Jason Jo, and Randall C O'Reilly. Compositional generalization in a deep seq2seq model by separating syntax and semantics. arXiv preprint
2019.
Guangyu Robert Yang, Madhura R Joglekar, H Francis Song, William T Newsome, and Xiao-Jing Wang. Task representations in neural networks trained to perform many cognitive tasks. Nature neuroscience, pp. 1, 2019.
10

---

Under review as a conference paper at ICLR 2021
A PRELIMINARIES FOR GROUP THEORY
In this section, we go through some preliminaries for group theory. We provide widely used defini- tions, propositions and theorems, with references for more details.
A.1 GROUPS
Definition A.1 (Group). A group is an ordered pair (G,o) where G is a set and o 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 subset H of group G' is itself group under the operation of G, we say that H a subgroup of G. Gallian (0122) p.61 (also Dummit & Foote (2004) p.46)
Definition A.3 (Normal subgroup). A subgroup H of group G called normal subgroup of G aH = Ha, Va E G. We denote this by H 4 G. Dummit & Foote (2004) p.82, Gallian (2012) p.185
A.2 MAPPINGS
Definition A.4 (Group homomorphism). homomorphism y from a group G to group H is mapping from G into H that preserves the group operation, i.e., Va, b E G, (((aa) p(a)ş(b). Gallian 2012) p.208, Dummit & Foote (2004) p.36.
Definition A.5 (Group isomorphism). The map y G H is called isomorphism and G and H are said to be isomorphic or of the same isomorphism type, written = H, if so is a homomorphism and bijection. Dummit & Foote (2004) p.37. Gallian (2012) p.128.
A.3 PRODUCTS
Definition A.6 (Product of subgroups). Let HI...., H be subgroups of group and define H, H2.... HK = (h1h2... hh. h2 E H,, Vi 1,..., K}. Dummit Foote (2004) p.93 Definition A.7 (External direct product). Let Gi...., Gx be finite collection of groups The external direct product of GI...., Gk. written as G1 x ... x GK. is the set of all K-tuples for which the ith component Dty...,Gr
element of G; and the operation is component wise. In symbols,
G Gk ((......, .0.....9KK)) 19, G.),
(91....,9K)(6 (ok) ...))................ gK) ...g 9K9Kk)
Gallian 2012) p. 162 Dummit & Foote 2004) p.152
Proposition A.1 (External direct product a group). If G Gx are groups, their external direct product is group. Dummit & Foote (2004) p.133. Proposition 1.
Definition A.8 (Internal direct product). Let H1...., HK be a finite collection of normal subgroups of G. We say that G is the internal direct product of Hı...., HK. if
G H2...... H
and
H1 H2 ... H. n H441 = {e}, Vi = I....,n-1
Gallian 2012) 197, Dummit & Foote (004) 172.
Theorem A.2 (Recognition theorem). If group is the internal direct product of a finite number of subgroups H1 Hi..... HK, then G is isomorphic to the external direct product of Hı...., .H.. Gallian
2012) p. 198, Dummit Foote (2004) 1.171.
A.4 GROUP ACTIONS
Definition A.9 (Group action). A group action of group G on a X is map from G X to (written as g(x), Vg E G, c E X) satisfying the following properties: and
91 (g2 (x)) (1) V91.g2 E G
e(x) =I,
Dummit & Foote (2004) 112
Definition A.10 (Product action). G G1 x... GK is group, and X X1 X Xx is set.
G acts on X by the rule (g)...., ........K (Z),.... = (g) 9K xx). Cameron et al. 2008))
Praeger & Schneider (2018) p.71.

---

Under review as a conference paper at ICLR 2021
Definition A.11 (Orbit). Let G be group action the nonempty set X. The equivalence class OF = (9((z) g E G} called the orbit of containing x. Dummit & Foote (2004) p.115
Definition A.12 (Transitive action). The action of on X called transitive there is only one orbit, i.e., given any two elements y E X there is some y E G such that g(y). Dummit & Foote (2004) p.
Definition A.13 (Equivalent action). Two actions of a group G on sets and Y are called equivalent there is a bijection yp X + Y such that ((g(x)) = s(v(x)) for all G and x E X. We say G eq. acts on X and Y. Lovett (2015) p.385.
12


Reviews:
[{"review_id": "LJxy-mCca8", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Summary ** \n\nThe 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.\n\n** Strengths **\n\nThe paper addresses a highly relevant and important problem. In general, it would be extremely helpful for a broad range of ML and AI researchers and practitioners if we were to formally describe the conditions in which compositional representations can be obtained.\n\n** Weaknesses **\n\nUnfortunately, the proposed approach is not described clearly enough for it to be widely useful.\n\nIn general, I believe that when formal tools (like group theory) are applied to prove anything outside of their original domain (i.e. when we are using group theory to reason about compositional representations in machine learning), \nit is crucial to 1) clearly define all involved notions (not only mathematical, but also the ones to which mathematical tools are applied) 2) clearly motivate the application.\n\n** Clarity **\n\nUnfortunately, the clarity of the contribution is not up to the standards of ICLR conference. In general, I believe that clarity concerns are secondary to other evaluation components (experimental support, novelty, etc.). In this case, however, it becomes impossible for me to evaluate other components because I can not fully understand the approach from its description.\n\nFor example, while the paper is focused on compositional representations, the actual description/definition of what exactly authors mean by compositional representations comes only on the 4th page (after some formal results were already stated).\n\nThe description is as follows: \"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.\". At the same time, there was no formal definition of \"representation\" before that paragraph. In the very next paragraph, however, the authors say \"We consider two representations and corresponding sets. X is original entangled representation, and Y is compositional representation\".\n\nThe concerns I described above are related to the overall structure of the contribution. A separate and also a major concern is that the writing itself should be improved too. There are numerous confusingly phrased sentences which make reading difficult.\n\nFor example, we can take a look at the very first sentence in the abstract: \"Humans naturally use compositional representations for flexible recognition and\nexpression, but current machine learning lacks such ability\". It's not clear what is meant by \"recognition and expression\", it also seems unnatural to say that \"machine learning\" lacks a certain ability,\nbecause machine learning is a field of study. It may be better to rephrase it to \"machine learning methods\". While these concerns are minor, they are ubiquitous thoughout the paper, which substantially hinders readability.\n\n** Suggestions **\n\nThe direction may be promising, but unfortunately, the paper needs a thorough reorganization in order to be publishable.\n\nI would like to suggest moving the standard group theory definitions from the main text into appendix. Some of the proofs could be moved there too. The space obtained this way may be used to \n1) formally define a) what a \"representation\" is b) what a \"compositional representation\" is c) the general problem setting \n2) motivate the chosen definitions with some potential applications. I realize that the examples in the end of the article are intended to serve that goal, but in my opinion, neither of them is explored in enough detail.\n\nI understand that a lot of work went into this article, and I hope that the authors won't feel discouraged by the feedback, but use it as an opportunity to improve the paper.\n\n** Update after the authors' response **\n\nI have read the authors' response and other reviews. I still believe that my evaluation is correct at the moment. \n\nAt the same time, I believe that the research direction is very and promising, and I hope to see the updated version of the manuscript published in the future!", "extra_scores": {}, "extra_text": {}}, {"review_id": "BiQ7zEf1ZNW", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Post-revision update\n----------------------------\n\nThanks to the authors for their revision. Unfortunately, I still feel the contribution and value of the work is not well communicated. Many of my previous points still stand. It is not a sufficient response to just say that the two propositions are the main contribution and the critical summary of findings and their relevance.\n\nOriginal Review\n------------------------\n\nThis paper presents a group-theoretic approach to compositionality, and attempts to provide necessary and sufficient conditions for the possibility of compositional representations. While this is an admirable goal, I am concerned that the paper does not live up to it. I recommend rejection at present, unless the definitions and presentation are substantially clarified.\n\n* The authors have assumed a particular definition of \"compositional\" for \"compositional representations,\" but they have neither clearly stated a definition for compositional representations nor justified it. Section 4.2. does not clearly state a definition of compositionality.\n    * The authors cite Bengio (2013) as a reference when they introduce the idea of learning compositional representations, but this term is not defined there. In their mathematical definitions, they appear to assume compositional = componential.\n    * However, what it means for a representation to be compositional is actually quite difficult to assess, some of the papers that the authors cite (e.g. Andreas, 2019) discuss this. See also Zadrozny (1992). \n    * The authors definition of compositionality seems to my view to be closer to a notion of disentanglement. Indeed, their definition of compositionality itself seems to closely reflect the disentanglement definition given in Higgins et al. (2018). The authors note that representations could still be compositional even if the features are not statistically independent, which is valid, but does not contradict the point I am making here.\n    * My point is that, from Montague, we know we can define compositionality in terms of any composition operator in representation space. The authors do not justify that *any* composition operator could be specified in terms of their definition of compositionality. In fact, it seems clear that assuming a product of a finite number of subgroups could *not* capture the original linguistic goals of compositionality, which was *precisely* to allow *infinite recombination of elements to arbitrary depth*. For example, the grammar of arithmetic symbols allows arbitrarily long sequences of operations. How could this structure be experessed in this framework? \n    * It appears to me tha this article is therefore not about compositionality per se, but rather about disentanglement of a finite number of subgroups underlying the data. This is also a subject worth investigating, but the paper framing should reflect this, and the relation to prior work should clarify more fully how it differs from prior group-theoretic definitions of disentanglement (e.g. Higgins et al., 2018).\n\n* Other definitions are not clearly expressed either. For example, what are the \"original\" representations that the authors refer to, where do they come from? This entails certain assumptions about e.g. the mapping from possibly noisy data into the representational spaces that are essential to understanding whether these ideas have any meaning in practice.\n\n* In general, the authors focus too much on formal notation, without developing intuitions for what results mean and why they would be useful. The authors present a page of group theory definitions, but this seems almost certain to be unhelpful. Any reader who is not familiar with group theory will not be able to develop sufficient intuitions to understand the rest of the paper from reading these terse definitions without examples, and to those of us familiar with group and category theory this is space that could be much better spent on clarifying and elaborating the exposition of the contributions.\n\nIn summary, I think that while this work could present a useful contribution to understanding disentanglement, it would need substantial rethinking of the definitions, more connection with the prior work, and clarification of the writing and exposition for me to see it as ready to present.\n\nReferences\n---------\n\nZadrozny, Wlodek. \"On compositional semantics.\" COLING 1992 Volume 1: The 15th International Conference on Computational Linguistics. 1992.\n\n(Other references cited above are referenced in the article.)", "extra_scores": {}, "extra_text": {}}, {"review_id": "8yWJ9o3qSH", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Overall review\n\nThis 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.\n\nPros:\n* Seeks to clarify and precisify the definitions of compositional representations, and find necessary and sufficient conditions on their existence.\n* Contributes theoretical results on compositionality, a timely topic.\n\nCons:\n* The text is hard to follow without motivating examples of the definitions and theorems.\n* The applications in the discussion section are somewhat opaque.  The application to attention doesn't appear to make any explicit reference to the attention mechanism at all.\n* While theoretical understanding is extremely valuable, it's unclear how to use the results to detect or promote compositionality as usually understood.\n\n\n# Minor comments\n\n* \"In language, a sentence is a combination of grammar and lexicon.\"  It might be more informative here to say that the meaning of a whole sentence is composed from the meanings of the parts and the grammatical structure of the sentence.\n\n* At the end of the introduction, the statements of Propositions 1.1 and 1.2 are hard to understand without later background from the paper.  Is it possible to provide a more intuitive statement (even if not fully precise) for these?\n\n* \"We will provide examples and look into more details in discussion section.\"  For this reader at least, it would have helped to have examples more thoroughly laid out in Sections 3 and 4.  For example: what structure of groups is being assumed for X and Y in 4.1-4.2?  Y is assumed to be compositional representations, but we haven't been given a clear definition of that concept or an exact example.\n\n\n# Typographic comments:\n\n* I think e in definitions 3.8 and 3.9 refers to the identity element of the group, but this should be stated explicitly (e.g. in the definition of a group).\n\n* Defn 3.12: I'd use X instead of A here for consistency.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5yLJ5eeGXE2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##### Summary #####\nThis work uses group theory to investigate compositionality. It characterizes conditions (1) for a set of components to be composed and (2) for a mapping to be compositional.\n\n\n##### Reasons for score #####\nMy vote leans toward rejection. Compositionality has drawn the attention of researchers for many years and the goal to clarify what we mean by it is certainly worth pursuing. The consequence of Proposition 1.1, on the conditions of compositional components, that composition depends not only on each component, but also on their combination, is particularly interesting and highlights how this approach can fruitfully inform our understanding of compositionality. The results also look sound to me. However, I am ultimately not certain about the progress, conceptual or technical, this contribution makes toward our understanding of object of study. In other words, to my mind, there is a lack of motivations, discussion, or applications to contextualize Proposition 1.1 and Proposition 1.2. I see how both Section 1 and Section 5 could serve this purpose but they fall a bit short. I should stress that this project is quite interesting, but it would greatly benefit from working out --or clarifying, in case I missed it-- what we learn from these results.\n\n#### Pros ####\n+ Characterizing compositionality is fundamental to our understanding of human cognition. It might, consequently, also be important for the development of machine learning techniques. While, prima facie, compositionality is pretty intuitive, its formal definition has proven to be quite elusive. Efforts to formally characterize it are much needed\n+ Proposition 1.1 and Proposition 1.2, the main results of the paper, answer some fundamental questions and have a few interesting consequences.\n+ The exposition surrounding the main results (sections 3 and 4) is incremental and well-executed\n\n\n#### Cons ####\n- My main concern is that this work does neither succeed in linking obtained results to established literature and standing discussions nor in highlighting their relevance for researchers working on this topic. This is a major concern since it certainly has a lot of potential. Since this research addresses fundamental questions about the object of study, I would encourage the authors to clarify how the two propositions and their consequences inform our understanding of compositionality (i.e., what do we learn that we didn't before?). The conclusion is a good example of where this paper falls short: There is no critical summary of findings and their relevance, nor discussion of further research. Instead, it is an itemization of what was done.\n- The writing is, at times, hard to follow. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were clearly excited by the novel application of group theory to the problem of composition, and think the core idea is good.  However, the reviewers also expressed concern about the clarity of the paper, stating that in several places examples might help. Reviewers were also interested in seeing the work tied to real world applications, and how the work expands our existing knowledge about the composition of learned representations.  I hope their suggestions will help the authors to turn this into a stronger, clearer paper.
Decision: Reject