On The Specialization of Neural Modules
Authors: Devon Jarvis
Richard Klein
Benjamin Rosman
Andrew M Saxe
Venue: ICLR 2023 poster (2023)
Keywords: Systematic Generalization
Linear Neural Networks
Neural Module Networks

Abstract: A number of machine learning models have been proposed with the goal of achieving systematic generalization: the ability to reason about new situations by combining aspects of previous experiences. These models leverage compositional architectures which aim to learn specialized modules dedicated to structures in a task that can be composed to solve novel problems with similar structures. While the compositionality of these architectures is guaranteed by design, the modules specializing is not. Here we theoretically study the ability of network modules to specialize to useful structures in a dataset and achieve systematic generalization. To this end we introduce a minimal space of datasets motivated by practical systematic generalization benchmarks. From this space of datasets we present a mathematical definition of systematicity and study the learning dynamics of linear neural modules when solving components of the task. Our results shed light on the difficulty of module specialization, what is required for modules to successfully specialize, and the necessity of modular architectures to achieve systematicity. Finally, we confirm that the theoretical results in our tractable setting generalize to more complex datasets and non-linear architectures.

Published as a conference paper at ICLR 2023
ON THE SPECIALIZATION OF NEURAL MODULES
Devon Jarvis Richard Klein', Benjamin Rosman & Andrew M. Saxe School of Computer Science and Applied Mathematics, University of the Witwatersrand "Gatsby Computational Neuroscience Unit & Sainsbury Wellcome Centre, UCL *CIFAR Azrieli Global Scholar, CIFAR {devon. jarvis, richard. klein, ben rosmann @ewtssswwwww...... ac. a. s saxe@ucl......... ac.
ABSTRACT
A number of machine learning models have been proposed with the goal of achiev- ing systematic generalization: the ability to reason about new situations by com- bining aspects of previous experiences. These models leverage compositional architectures which aim to learn specialized modules dedicated to structures in a task that can composed to solve novel problems with similar structures. While the compositionality of these architectures ís guaranteed by design, the modules specializing is not. Here we theoretically study the ability of network modules specialize to useful structures in dataset and achieve systematic generaliza- tion. To this end we introduce a minimal space of datasets motivated by practical systematic generalization benchmarks. From this space of datasets present mathematical definition of systematicity and study the learning dynamics of linear neural modules when solving components of the task. Our results shed light the difficulty of module specialization, what is required for modules to successfully specialize, and the necessity of modular architectures to achieve systematicity. Finally, we confirm that the theoretical results in our tractable setting generalize to more complex datasets and non-linear architectures.
INTRODUCTION
Humans frequently display the ability systematically generalize, that is, to leverage specific learning experiences in diverse new settings (Lake et al.) 2019). For instance, exploiting the approximate compositionality of natural language, humans combine finite set of words or phonemes into near-infinite set of sentences, words, and meanings. Someone who understands "brown dog" and "black cat" also likely understands "brown cat," take one example from [Szabó] (2012) The result is that a human's 's ability to reason about situations or phenomena extends far beyond their ability to directly experience and learn from all such situations or phenomena.
Deep learning techniques have made great strides in tasks like machine translation and language prediction, providing proof of principle that they can succeed ever, these methods are typically data hungry and the same networks often fail to generalize in even simple settings when training data are scarce (Lake Baroni 2018b Lake al.. 2019). Empirically, the degree of systematicity in deep networks is influenced by many factors. One possibility is that the learning dynamics in a deep network could impart an implicit inductive bias toward systematic structure (Hupkes et al. 2020); however, number of studies have identified situations where depth alone is insufficient for structured generalization (Pollack] 1990] Niklasson & Sharkey 1992, Phillips
coapiicomposiiional domains. How-
& Wiles 1993 Lake & Baroni 2018b; Mittal al. (022).. Another significant factor architectura modulanity, which can enable a system to generalize when modules are appropriately configured (Vani et al. 2 Phillips 1995). However, identifying the right modularity through learning remains challenging (Mittal et al. (0222. In spite of these (and many other) possibilities for improving systematicity (Hupkes et al. 22220), it remains unclear when standard deep neural networks will exhibit systematic generalization (Dankers et al. 2021), reflecting a long-standing theoretical debate stretching back the first wave connectionist deep networks (Rumelhart & McClelland 1986
Pollack 1990, Fodor & Pylyshyn 1988 Smolensky
[99] 1990 Hadley 1993 1994).
In this work we theoretically study the ability of neural modules to specialize to structures in a dataset. Our goal is to provide formalism for systematic generalization and to begin to concretize some of
"Corresooniigg author

---

Published as a conference paper at ICLR 2023
the intuitions and concepts in the systematic generalization literature. To begin we make a careful distinction between the compositionality and systematicity of a neural network architecture. Specif- ically, in this work we maintain that compositionality is a feature of an architecture, such as a Neural Module Network (Andreas et al. 2016 Andreas, 2018), or dataset where modules components can be composed by design. Systematicity is a property of a (potentially compositional) architecture exploiting structure in the world (dataset) such as the compositional structure of natural language from the (212) example. Intuitively, if a dataset does not have structure which can be exploited for generalization then no compositional architecture will be able to systematically generalize. As a result in this work we are concerned with formalizing both the dataset and neural network learning dynamics to study this interplay between domain and architecture. The main approach of this work can be summarized as follows: we introduce a reflective space of datasets that contain composi- tional and non-compositional features, and examine the impact of implicit biases and architectural modularity on the learned input-output mappings of deep linear network modules. In particular,
We derive exact training dynamics for deep linear network modules as a function of the dataset parameters. This is a novel, theoretical means of analysing the effect of dataset structure neural network learning dynamics.
We formalize the goal of modularity finding lower-rank sub-structure within dataset that can be exploited to improve generalization.
We show that for all datasets in the space, despite the possibility of learning a systematic mapping, mon-modular networks do not do so under gradient descent dynamics.
We show that modular network architectures can learn fully systematic network mappings. but only when the modularity perfectly segregates the underlying lower-rank sub-structure in the dataset.
In Section show that our findings, which rely on simplified setting for mathematical tractability, generalize to more complicated datasets and non-linear architectures by training a convolutional neural network to label handwritten digits between 0 and 999. Overall, our results help clarify the interplay between dataset structure and architectural biases which can facilitate systematic generalization when neural modules specialize.
2 BACKGROUND
Systematic generalization has been proposed as a key feature of intelligent learning agents which can generalize to novel stimuli in their environment (Hockett & Hockett 1960, Fodor & Pylyshyn 1988.
Hadley 1993 Kirby et al., 2015 Lake et al.] 2017]|Miton et a (022). In particular, the closely related concept of compositional structure has been shown to have benefits for both learning speed
(Shalev-Shwartz & Shashua 2016 Ren et al. 2019) and generalizability (Lazaridou al. 2018).
There are, however, counter-exampl les which find only a weak correlation between compositionality and generalization (Andreas 2018) or learning speed (Kharitonov & Baroni 2022)). In most cases
neural networks do not manage to generalize systematically (Ruis et al. [2200] Mittal et al. 2022). or systematic generalization occurs only with the addition of explicit regularizers
degree of
supervision on the learned features "Shalev-Shwarte et al. 2017 Wies et al. 2022) which is also
termed "mediated perception" (Shalev-Shwartz Shashua 2016).
2017 2018) have become one successful method of creating network architectures which generalize systematically. By (jointly) training individual neural modules on particular subsets of data or to perform particular subtasks, the modules will specialize. These modules can then be combined in new ways when an unseen data point is input to the model. Thus, through the composition of the modules, the model will systematically generalize, assuming that the correct modules can be structured together. [Bahdanau cet al. (2019b) show, however, that strong regularizers are required for the correct module structures to be learned. Specifically, it was shown that neural modules become coupled and as a result do not specialize in manner which can be useful to the compositional design of the architecture. Thus, without sask-fceccfic regularizers, systematic mappings did not emerge with NMNs.
Neural Module Networks (NMNs) (Andreas et al. 20166] Hu et al.
Similar problems arise with other models which are compositional in nature. Tensor Product Networks (Smolensky et al., 2022) for example aim to learn an encoding of place and content for features in data point. These encodings are then censor-producted and summed. By the nature of separating
2

---

Published as a conference paper at ICLR 2023
Command
Actions
Key Tay Num Comp lapurs
9
Kug matrices lapor
Tay: Comp Ouipus
kRl.
0
O
O
Kiy Nam lē matrices Ouapui
0
0
Q
Scale of muiiess
2
0
0
0
0
Rg: Compp lnpus Matris
0
Non comp lnput Marzo
0
0
0
0
0
1
0
0
0
0
By Coop Ourput Mazis
0
0
O
0
0
0
y Non-ccorp Ourpu Marric
0
0
0
O
0
O
2
f2 3 2x hz
By 3 S2y
a b C
f e 1
d
= 1
y
ki
Figure I: Problem setting and dataset space. (a) When navigating maze towards a target, an agent might extract various input features, mapping these to a sequence of actions. (b) We schematize this setting with space of datasets containing compositional (52) and non-compositional (I) features in the input (middle panel) and output (right panel). Rows contain examples and columns contain features. In this case objects are identified with both a compositional component (based on features: size, shape and colour) and non-compositional component (based on absolute position).
"what" and "where" it possible to systematically generalize when seen objects appear in unseen positions. For example, in language a noun which has only been seen as the subject in sentence can be easily understood as the object of novel sentence as the word meaning is separate from its position. These models, however, require coherent encodings to be learned for similar unseen objects which is conceptually similar to requiring neural modules to specialize and not guaranteed. Similarly, Recurrent Independent Mechanisms (RIMs) (Goyal et al.) 2019) and Compositional Recursive Learners (CRLs) (Chang et al., 2018) experience difficulties with the network modules becoming coupled and only worked consistently when paired with the same modules that were used for the training data. Thus, a number of questions remain unanswered. What is required for neural modules to specialize? Is there natural tendency for neural modules to specialize in the absence of strong regularizers? ? How much does the dataset structure matter for systematic generalization? These are all questions we aim to help address in this work. To this end now define the space of datasets used in our analysis and provide definition of systematicity for this space.
A SPACE OF DATASETS WITH COMPOSITIONAL. SUB- SUB-STRUCTURE
The notion of systematic generalization is broad, and has been assessed using a variety of datasets and paradigms (Hupkes et al. 2020). Here we introduce a simple setting motivated by the SCAN (Lkke & Baroni 2018a) and grounded-SCAN (gSCAN) datasets (Ruis et al., 2020) commonly used to evaluate systematic generalization with practical neural models. Other similar benchmarks have also been used in prior work (Hupkes et al., 2 [Bahdanau et al. 2019a). In the SCAN and gSCAN datasets command is given to an agent such as "jump left twice" or "walk to the red small circle cautiously". In the case of gSCAN an image of grid-world is also presented depicting the agent and number of objects sharing similar features. These features include small vs large, red vs blue vs green vs yellow, circle vs square vs rhombus. The agent is then tasked with producing a sequence of primitive actions such as "L turn", "R turn", "WALK". In the case where agent is told to carry an action in a specific manner (an adverb is used in the command) a sequence of memorized actions must also be completed, For example perform an action "cautiously" means that the action string "L.tum, R_ R.turn, R_turn, L.turn" must be output before each step forward.
For our space of datasets we aimed to imitate the primary features of these established benchmarks while making sure the task remains linearly solvable to allow for our theoretical analysis. An example of one dataset from the space of datasets is depicted in Fig. [ Conceptually the task is for an agent to navigate series of paths to reach the desired object in the domain as specified by command. The command which input to the model specifies the features of the object to be found where the features are "large vs small", "square vs circle", "red vs blue". The agent is also told the index of the object in the 1-dimensional space of objects and so it also knows the absolute position in the environment. The agent must then output a string of three actions where each action is either "L.tumn" or "R.tum "tuut.". . Finally, in the agent's 's output we also include a set of unique actions which correspond to the agent executing an entire memorized behaviour (one per object in the environment). These full-behaviour outputs are reminiscent of the agent in gSCAN remembering that the "cautiously" command maps to sequence of four actions (looking left and right).
3

---

Published as a conference paper at ICLR 2023
To formalize this setting, we define a parametric space of datasets with input and output matrices X = [S2 r=ll and Y = [ r y respectively, where Rg: By, Rgy
Ky: r' E Z+ are the parameters that define a specific dataset. Figure [b) visualizes one of the simpler datasets in the space. The compositional imput feature matrix 22 E {-1, 11,11 x xRz consists of all binary patterns with ny bits. Here nhr is a key parameter determining the number of bits in the compositional input structure. Overall, the dataset contains 2 examples. The compositional output feature matrix By {-1, 1, 1)22 2 xny is a uniform sampling (although any sampling method would work) of ny features (columns) from Ueg and is the compositional component of the output matrix. By using only a sampling of 22g features for S2 we account for the case where some visually distinct features are not necessary for navigation. Next, the non-compositional input feature matrix r = [r/, ... r/.,] consists of k; scaled identity matrices, J, E 10, x2"= Similarly, the non-compositional output matrix r, = [r/ r/k,) has hy scaled identity matrices I E {0, 1]," x2" with scale factor r. These identity matrices provide a single feature for each pattern which is only on for that pattern. This space of datasets is consistent with numerical notions of compositionality in previous works (Andreas) 2018). which define compositionality as homomorphism between the observation space and the naming space (since the amount of compositional structure can be titrated by adjusting n, and ny. Similarly, lig, hi and r control the frequency and intensity of the non-compositional features, which are both factors that can promote non non-coppositionll language being used by humans (Rogers et al. 2004).
2
mappings are linear they are homomorphic). Crucially for our analysis, the
3.1 SYSTEMATICITY AS EXPLOITING LOWER- HOWER-RANK RANK SUB-STRUCTURE
Novel to our analysis, datasets in this space allow redundant solutions: the compositional output com- ponent can be generated based on compositional input features alone (systematic mappings), but they can equally be generated using conscooposiiional features alone, some mixture of the two (non- systematic mappings). This formalization of the datasets is motivated by common systematicity bench- marks, but it is also reflective of more general fact: that in many settings there multiple ways to solve a problem. However, it is not the case that all approaches generalize equally well. This means that the inductive biases placed upon model which influence the kinds of mappings it learns is key consideration, even if the difference is not apparent on training data. In Sections [aand we aim to for- malize and study the architectural inductive biases which push a model towards systematic mappings. We begin in this section with a mathematical definition of systematicity for our space of datasets.
While some prior theoretical works have defined systematic generalization, such as the grading from weak to semantic systematicity (Hadley 1994 [oden & Niklasson 2000), these works have remained behavioural and relied on linguistic notions of syntax. Thus, general mathematical definition of systematicity has remained elusive. In more recent empirical studies (Bahdanau et al., 2019b] Lake & Baroni 2018b) intuitive based on the domain what systematicity would be. However, this context dependent nature of systematicity is the root of the difficulty in defining it. Thus, Definition
3.1 offers a formal definition of systematicity for our space of datasets.
Definition 3.1. Systematic generalization is the identification and learning of lower-rank sub-structure (22,, S.y, in the full dataset (X, Y) such that the rank of the population covariance on the sub-structure: 2 F 222.222 [27] is lower than the rank of the population covariance on the dataset as a whole:
X E[Y x. Consequently, is more probable that training sample will be full rank on the sub-structure than on the full dataset, which facilitates generalization on the sub-structure.
The definition above relies on the rank of the covariance matrix to define systematicity. It is important then to note that by partitioning portions of the feature or output space it is possible to change the rank of the sub-problems which emerge. Take for example the dataset shown in Figure [ The rank of the entire dataset covariance matrix is 8 due to the identity block being orthogonal. Thus, for the network to learn the full mapping it must see all 8 data points. However, if we only consider the compositional inputs and outputs the rank of this portion of the covariance matrix (the compositional covariance) Thus, even though there are unique data points a model would only need to see 3 data points which are not linearly independent to learn that portion of the mapping if learned in isolation. For 3 binary variables the probability of obtaining a full-rank compositional covariance matrix from 3 samples is 57% and from 4 samples is 91% (see Appendix B for the calculation of the sample probabilities for and compositional features). Thus, if the model were to learn the mapping between compositional sub- aob-struutures in isolation it would be nearly certain to generalize to the entire dataset having seen only half of the data points in the training set. This is our notion of systematicity: the ability to learn portions of mapping with lower-rank sub-structure distinct from
4

---

Published as a conference paper at ICLR 2023
the rest of the mapping which increases the rank of the problem. The benefit of this is that the network will generalize far better the structured portions of the input output space (see Appendix A for a motivating example of this point and for more intuition on Definition B.I). This benefit also grows with the number of compositional features since adding more compositional features results
in an exponential increase in the number of data points which can be generalized to, relative to the number training examples needed (shown in Appendix [B. With the space of datasets defined, we now describe the primary theoretical tool in this work. That is to calculate the training dynamics of both shallow and deep linear networks for all datasets in our space.
LEARNING DYNAMICS IN SHALLOW AND DEEP LINEAR NETWORKS
While deep linear networks can only represent linear input-output mappings, the dynamics of learning change dramatically with the introduction of one or more hidden layers (Fukumizu) 1998 Saxe et al.
2014 2019 Arora et al., 2018 Lampinen & Ganguli 2019), and the learning problem becomes non-convex (Baldi & Hornik 1989). They therefore serve as a tractable model of the influence of depth specifically on learning dynamics. which prior work has shown to impart a low-rank inductive bias on the linear mapping (Huh et al., 2021).
We leverage known exact solutions to the dynamics of learning from small random weights in deep linear networks (Saxe et al. 2014] (2019) to describe the full learning trajectory analytically for every dataset in our space, We take the novel theoretical approach of writing these dynamics in terms the dataset parameters for our space of datasets (Equations Ind
and 12). This allows us to analyse
the effect of dataset structure on the training dynamics and learned mappings. In particular, consider single hidden layer network computing output w x in response to input z, trained to minimize the mean squared error loss using full batch gradient descent with small learning rate (full details and technical assumptions are given in Appendix C). The network's ' total input-output map after t epochs of training is
(t) = UA(VV
(1)
where A(t) is diagonal matrix of singular values. The dynamics of A(t), as well as the orthogonal matrices U and V, depend on the singular value decomposition of the input- and input-output correlations in the dataset. If the input- and input-output correlations can be expressed
E = F|XX VDVT, ΣE = FIY x =USV
where U and V are orthogonal matrices of singular vectors and S, D are diagonal matrices of singular values/eigenvalues, then the diagonal elements of A(t)aa (t) evolve through time as
To (4)
- Avc 0, To
exp 21
where Aa and 8a are the associated onput-output singular value and input eigenvalue (Saa and Davo respectively), To denotes the singular value at initialization, and T = 2nze is the learning time constant. These dynamics describe a trajectory which begins at the initial value no when 0 and increases to the correct asymptotic value T = Aa/ō as t - x. This trajectory corresponds to the network learning the covariance between the input and output data the correct mapping.
In essence, the network's total input-output mapping at all times in training is function of the singular value decomposition the dataset statistics. We find that there are three distinct input-output singular values which we denote Åι, X2 and As; two distinet input singular values 8, and 82; and therefore three asymptotes nं, πΣ and σड (the final point for each SV trajectory Tı, T2 and πÿ):
(Regr2 + 2m [kog 2 + 2nx))
kgy + 2m
\
(4)
A1/61
(5)
22n,
k2p2 + 2
(Kigh + 2nd (kkg
kiy
22
(6)
T5 = X2/01 =
(7)
22n=
2 2 + 2
ky
lig
A3 =
(8)
333 = -xa/52 =
(9)
22
hizz
5

---

Published as a conference paper at ICLR 2023
By writing this decomposition in terms of the dataset parameters, substituting these expressions into the dynamics equation (Equation B) gives equations for the networks mapping and full learning trajectories at all times during training for all datasets in the space. Full derivations, including explicit
expressions for singular vectors, are deferred Appendix
similar derivation for a shallow network (no hidden layer) shows that the singular values of the model's 's mapping follow the trajectory
Ta (t)
6a (1 exp exp (-6at/T) + To exp (xpp--5.0 (-5at/T),
(10)
such that the time course depends on the singular values of the input covariance matrix, >x The unique singular values are
81 (12 + 2
kgr
(11)
82
(12)
2
2
To empirically verify our theoretical results in Equations to we simulate the full training dynamics for deep and shallow linear networks trained using gradient descent instantiation from the space of datasets in Figure 2 While training. we compute the singular values of the network after each epoch of training. These simulations of the training dynamics for each unique singular value then compared to the predicted dynamics. We see close agreement between the predicted and simulated trajectories] | In the following sections utilise these equations for the training dynamics to analyse to what extent neural networks naturally specialise and display systematicity.
Pridted Lalelon
15
(a)
(b)
(c)
(d)
Figure 2: Unlike shallow networks, deep networks show distinct stages of improvement over learning. (Panels a-d): Analytical learning dynamics for deep (a.b) and shallow (c,d) linear networks. (a,c) Com- parisons of predicted (dotted) and actual (solid) singular value trajectories over learning, for one dataset's singular values. (b,d) Comparisons of predicted (dotted) and actual (solid) Frobenius norms of the input-output mapping to/from compositional (52,, P2y,) and non-compositional (Tz; [y) features. Parameters: n2 3, Kn 3, nl = 1, ky 1,r 1.
5 THE EVOLUTION OF SYSTEMATICITY OVER LEARNING
With the decomposition of the training dynamics and definition of systematicity for our space of datasets in hand we now look to understand the extent which a network comes rely on lower- rank sub-structure in dataset to generalize systematically. To do this we calculate the Frobenius norm of the network's mapping (the function implemented by the network transforming inputs to outputs) between different subsets of input and output components. To account for all datasets in the space and obtain the full dynamics over training, the norms are expressed in terms of the modes of variation. In particular we split the input-output mapping into four partitions: compositional inputs (Ω2) to compositional outputs (22y); non non-compositionss inputs (T,)) to compositional outputs (S2,); compositional inputs (S2z) to non-compositional outputs y.y): and non-compositional inputs (T,) to non-compositional outputs (T,,). These norms provide precise measure of the network's 's association between input and output blocks. For example, Roy-Nor depicts how much the network relies on the non-compositional input component (T' .) to label the compositional output component (92y). Thus, by analysing the partitioned norms we are able to determine how much the model relying on certain sub-s sub-structures in the data, and as a result, how systematic the model is at all times during training.
Analytical expressions for these norms over training (which rely on both singular value dynamics and the structure of the singular vectors) are given in Appendix Eqns.
20 due to space constraints.
All experiments are run using the Jax library (Bradbury et al.
2018 8 Full code for reproducing all figures
be found https::////t... //gi thub. com/ rai
izat ion_oon__oooooooo _n__ff_eura______ __molleemmeeeeee

---

Published as a conference paper at ICLR 2023
However, Figure (d) depicts these dynamics for one specific dataset and Figure B a) summarizes the mappings between each input-output partition well which modes of variation contribute to each mapping. This leads to Observation [.I and the corresponding proof presented in Appendix H.T
Observation 5.1. For all datasets in the space it is impossible for a dense architecture to learn systematic mapping between compositional componenis.
Proof Sketch: For a network to be systematic the compositional output needs to be independent of the non-compositional input. Similarly, the compositional input should not influence the non- compositional output (to avoid the non-compositional output influencing the features learned by the systematic mapping). However, in B we see that the mode т contributes to all partitions of the network mapping. This shows that non-compositional components affect the compositional mappings (T -.rl--Nom>>> 0 and Ω2 P.Tyy-Norm' 0). Because of this the mapping is not systematic.
In sum, the implicit bias arising from depth, small random initialization, and gradient descent (Appendix ! considers alternate learning rules to GD which do not change the outcome of the analysis) is insufficient to learn fully systematic mappings for any dataset the space, since the mapping between compositional components shares mode of variation with mappings involving non-compositional components. Thus, we note a necessary condition for systematicity; the mapping between lower-rank (compositional) sub-structure must be orthogonal (rely on different modes of variation) from the rest of the network mapping. In dense networks this is not the case as any correlation between sub-structures in the dataset will couple the mappings. Thus, also consider whether modular architectures may form decoupled mappings between sub-structures.
Network
Systemabi Mapping
Output Partitioned
Non-systemaric Mapping Fully Partitioned
22
2y
r y
r
y
y
π
2 2
3
π
T3
T
2
T
2 D x
P
(a)
(b)
Ø
R
(c)
Figure 3: Graphical representation of the deep network mapping. The dynamical modes Tı, 42, and T3 contain contributions from compositional and non-compositional input components and they make contributions to compositional and non-compositional output components. Systematic portions of the mapping which rely only on compositional sub-structure are depicted as green. To be able learn systematic mapping all modes connected to the compositional output (input) component must not con- nect to the non-composiiiona input (output) component.
(a) For the dense network we see that mode T is the only mode which impacts the mapping to the compositional output (corresponds to the 22 and T 22, norms in @ggure2bbeing learned at the same time as the म, mode Figure 2aj, however m also contributes to the non-compositional output mapping (,,r, and I T norms also rise with m1). Thus by learning the systematic mapping some -on-systematic mapping is also being learned. (b and c) Impact of architectural biases. Architectures that partition compositional and non-compositional features in different ways with the corresponding graphical representation of the resulting network mappings. The output partitioned network is able remove the impact of non-compositional output features on mode I, but does not result in a systematic mapping. Only the fully partitioned network achieves systematicity. Comparing to Figure aa) both graphical representations have less connections, particularly to/from the アi mode, reflecting the inductive bias imposed by modular architectures.
MODULARITY AND NETWORK ARCHITECTURE
We now turn to modularity and network architecture as a prominent approach for promoting systematicity in a network's 's mapping (Bahdanau et al. 2019b: Vani et al. 2021). Architectures such as NMNs (Andreas et al. 2016 Hu et al.J 2017; 2018) learn re-configurable modules that implement specialized (lower-rank in accordance with Detinition 3.1 aspects of a larger problem. By rearranging existing modules to process a novel input, they can generalize far beyond their training set. Here investigate whether simple forms of additional architectural structure can aid in module
7

---

Published as a conference paper at ICLR 2023
specialization and yield strong enough inductive biases to learn systematic mappings. From our results in Section 5 we know that necessary inductive bias is for the partitioned norms to rely on different modes of variation in the data.
Instead of dense network, we consider architectures in which compositional and non-compositional components are processed in separate processing streams, as depicted by the partitioned networks of Figure3Jo and (c). The norm equations for the architecture which only partitions along output structure is summarized in Figure 3jb) (equations are presented in Appendix Fj. From this we make Observation 6. with a corresponding proof in Appendix H.
Observation 6.1. Modularity does impose some form of bias towards systematicity but if any non-compositional structure is considered in the input then a systematic mapping will not be learned.
Proof Sketch: We note that by separating the hidden layers from portions of the input and output space network modules will be learning on special cases of the datasets. For example, a module with no hidden layer connections the non-compositional output components is learning on dataset with ky = 0. Thus, our norm equations from Section 5 still hold, just with the additional structure in the network limiting the potential datasets a module may see (the range of full input-output mappings is the same as before). In Figure ())) we see that the mode πı connects concooppoiiiional input components to compositional output components (T (tasty-Norm>>>> O). Because of this the mapping is not systematic. We note that modularity has removed the connection between the compositional input and non-compositional output y 0). Because of this there is a step towards systematicity.
Finally, we consider the case where two modules are used and fully partition the compositional and non-compositional structure in the input-output mapping (the strategy employed by NMNs). The norms are summarized in Figure 3(.). From these equations we make Observation 6.2 and prove the result in Appendix [H.3
Observation 6.2. The fully partitioned network achieves systematicity by learning the lower-rank (compositional) sub-structure in isolation of the rest of the mapping.
Proof Sketch: In Figure 3 c) we see that compositional input only connects to compositional output (T, -Nomm- 0). SimiTarly, non-compositional input only connects to non-compositional output (R2,I, y -Norm- 0). The portion of the network mapping from compositional input to compositional output is solving a lower rank problem than if the full feature spaces were considered. Because of this the network will generalise on this portion of the mapping and is systematic in terms of Definition 3.1
Finally, partitioning hidden layers is not possible for shallow networks, and so we are unable to obtain partial benefits from modularity with shallow networks. Thus, shallow networks also require the perfect architectural biases to partition the input and output structure to become systematic. Hence we find that architectural biases (modularity) can enforce systematicity, when the bias perfectly segregates compositional and con-coopositional information. How to achieve the correct segregation remains an open question in the NMNs literature, where reinforcement learning is often used (Hu et al. 2017] 2018), and we do not discuss this here. We merely aim to show the necessity of modularity. which has been hypothesized (Hadley 1994) and demonstrated (Andreas et al.) 2016) but not theoretically shown. In Appendix G we consider the effects of imperfect output partitions and find that if any non- compositional components are grouped with compositional components then the network will behave the same as in Section 5 and no longer be able to learn a systematic mapping. Taken together, the ob- servations of this section demonstrate the difficulty of learning specialized neural modules, as if any in- formation not of the desired lower-rank sub-structure is seen by module then it will fail to specialize. We now empirically verify if this generalises to a more naturalistic setting and non-linear architectures.
7 COMPOSITIONAL MNIST (CMNIST)
To evaluate how well our results generalize non-linear networks and more complex datasets, in this section we train a deep Convolutional Neural Network (CNN) to learn a compositional variant of MNIST (CMNIST) shown in Figure (4a) In this dataset three digits from MNIST are stacked horizontally, resulting in value between 0 and 999. The systematic output encodes each digit in a 10-way one-hot vector, resulting in a 30-dimmnsional vector. The non-systematic output encodes the number as whole with d000-dimeniional one-hot vector. This task is similar to the SVHN dataset Netzer et al. 2011) with added non-systematic labels.
8

---

Published as a conference paper at ICLR 2023
Imputs
Network
Labels
We compare results of using a single dense CNN and a split CNN, in which two parallel sets of convolutional layers with half the convolutional filters of the dense network each connect separately systematic and non-systematic labels. Full details of the two network architectures and hyper- parameters used for the CMNIST experiments are given in Appendix J The effect predicted by our theoretical work is that the non-compositional 1000-dimensional one-hot label will interfere with the network's s learned hidden rep- resentations for the compositional 30-dimensional label. This will decrease the compositional generalizability of the network on this structured portion of the output. This prediction is shown to be true in Figure which shows the mean-squared error for the composi- tional and non-compositional network predictions over the course of training, normalized so that the initial error is at 1.0. Firstly, in dense networks the error of the compositional mapping is tied to the error of the non-compositional mapping. This is seen in Figure 4b where the blue curve cannot converge until the orange curve has become sufficiently low. This effect is not observed with the split network. Secondly, comparing Figure 4b and 4c we demonstrate the lack of generalization which occurs when using conposoposiii components. This is seen as the orange and red curves achieving a lower training error while the test error increases. Lastly, again by comparing Figure 44 and [4c] we see that the compositional mapping of the split architecture is the only mapping which generalizes well (near training and test error). Thus, even in this more complex setting, see the negative effect shared hidden layer has the generalization of the network (comparing the blue and green curves).
5 157 7
557
(a)
1.0
03-
Conpectioal syift Nonoooppoil
Notelbe Vrow
044
000
4
92
116
150
361
751
301
Tppci Natche
(b)
1.2
Dena Compartiena
10-
Thea Nor-coryseivool fire
08-
Spli Caspesiienn Erse
5ytt non-corrpomnnall Iim
64-
02-
Narthe
(c)
Figure 4: (a) Visual descrip- tion of the CMNIST task, (b-c) normalized training loss (b) and test loss (c) of a deep CNN with ReLU activation on the Compositional-MNNN dataset averaged over 10 runs. Error bars reflect one standard-deviatinn
8 DISCUSSION
In this work we have theoretically and empirically studied the ability of simple NN modules to specialize and acquire systematic knowledge. We found that this ability is challenging even in our simple setting. Neither implicit biases in learning dynamics, nor all but the most stringent task-specific modularity, caused networks to exploit compositional sub-structure in the data. Our results complement recent empirical studies, helping to highlight the complex factors influencing systematic generalization. For example, in more complex datasets such as CLEVR (Johnson al. 2017), a module which should specialise to identifying the colour red would not specialise if Ferrari logo (a non-compositional identifying feature) was present in many of these images- the network would not identify sub-structure in Στ, Similarly, if many images containing red features mapped to a particular label, for example the "car" label, this would also affect which features the module specialised to. When the module is then used to "find the red ball" it would be looking for stercotypical car features to identify the colour red - it does not identify sub-structure in Σ0e_ Thus, in more natural settings our proposed notion of rank extends describing the complexity of the correlations being learned. Idemtifying and using the colour red in images is less complex than identifying and using the presence of Ferrari; requiring many different input features (higher rank Σ²) to be identified and correlated to a certain label (higher rank Σ Importantly for Definition [.1 if a task is specific to Ferraris, then having a specialised Ferrari module is useful (all test images will also contain Ferrari). But in gen- eral scene description tasks it is not. Consequently, Definition 3.] describes systematicity in terms of the task structure at hand: Σx and E Thus, as our theoretical module-centrie perspective displays, modules must be allocated perfectly; such that the only consistent correlation presented to module is the one must specialise to. A natural question emerges: which inductive biases are flexible enough to achieve systematicity without being tailored to specific problem? A neuroscientific perspective is that sparsity plays a role in producing systematic representations, particularly in the cerebellum (Cayco- Gajic & Silver 2019). Thus, exploring the utility of sparsity for systematicity is an important direction of future work. We hope that the formal perspective provided in this work will lead to greater understanding of these phenomena and aid the design of improved, modular, learning systems.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We would like to thank the reviewers for their time and careful consideration of this manuscript. We sincerely appreciate all their valuable comments and suggestions, which helped in improving the quality of the manuscript. This work was supported by Sir Henry Dale Fellowship from the Wellcome Trust and Royal Society (21638)/7/19/Z2) to A.S., and the Sainsbury Wellcome Centre Core Grant from Wellcome (219627/7/19/7) and the Gatsby Charitable Foundation (GAT3755). DJJ. a Google PhD Fellow and Commonwealth Scholar. A.S. and B.R. are CIFAR Azrieli Global Scholars in the Learning in Machines & Brains program.
REFERENCES
Jacob Andreas. Measuring compositionality in representation learning. In Internatiionl Conference on Learning Representations, 2018.
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 39-48, 2016.
S. Arora, N. Cohen, and E. Hazan. On the optimization of deep networks: Implicit acceleration by overparameterivation. 35th International Conference on Machine Learning, ICMI. 2018, 372-389 2018. arXiv: 1802.06509 ISBN: 978 9781510867963.
Dzmitry Bahdanau, Harm de Vries, Timothy J O' O'Donnell, Shikhar Murty, Philippe Beaudoin, Yoshua Bengio, and Aaron Courville. Closure: Assessing systematic generalization of clevr models. arXiv preprint 19X.vv99/2.007000 2019a.
Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: What required and can it be learned? In International Conference on Learning Representations, 2019b.
P. Baldi and K. Hornik. Neural networks and principal component analysis: Learning from examples without local minima, Newral Networks, 2( 2()):33-58, January 1989. ISSN 08936080. doi: 10. 1016/ 0893-608808999001433
0893608089900142
Mikacl Bodén and Lars Niklasson. Semantic systematicity and context in connectionist networks. Connection Science, 11(2):111-42, 2000.
James Bradbury. Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne. and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL com//oogle/jaaaeeooooooo
Yinan Cao, Christopher Summerfield, and Andrew Saxe. Characterizing emergent representations in space of candidate learning rules for deep networks. Advances in Neural Information Processing Systems, 33, 2020.
N Alex Cayco-Gajic and R Angus Silver. Re-evaluating cireuit mechanisms underlying pattern separation. Neuron, 101(4):5846602 2019.
Michael B Chang, Abhishek Gupta, Sergey Levine, and Thomas L Griffiths. Automatically composing representation transformations as a means for generalization. arXiv preprint arXiv: 04640, 2018.
Verna Dankers, Elia Bruni, and Dieuwke Hupkes. The paradox of the compositionality of natural language: a neural machine translation case study. arXiv preprint arXiv:2 2021. URL
https::/arxxvv org
/bs////////// a https//10.....8100
Jerry A Fodor and Zenon W Pylyshyn. Connectionism and cognitive architecture: A critical analysis. Cognition, 28(1-)):--7, 1988.
K. Fukumizu. Effect of Batch Learning In Multilayer Neural Networks. In Proceedings of the 5th
International Conference Neural Information Processing, pp. 67-70, 1998.
10

---

Published as a conference paper at ICLR 2023
Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy training in deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2020 (1I):113311, 2020.
Anirudh Goyal, Alex Lamb, Jordan Hoffmaann, Shagun Sodhani, Sergey Levine, Yoshua Bengio, and Bernhard Schölkopf. Recurrent independent mechanisms. arXiv preprint arXiv:1909. 10893, 2019.
Robert F Hadley. Connectionism, explicit rules, and symbolic manipulation. Minds and machines, (2):183-200, 1993.
Robert F Hadley. Systematicity in connectionist language learning. Mind & Language, 933):247-272 1994.
Charles F Hockett and Charles D Hockett. The origin of speech. Scientific American, 203(3):88-97, 1960.
Ronghang Hu, Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Kate Saenko. Learning to reason: End-to-end module networks for visual question answering. In Proceedings of the IEEE International Conference on Computer Vision, pp. 804-813, 2017.
Ronghang Hu, Jacob Andreas, Trevor Darrell, and Kate Saenko. Explainable neural computation via stack neural module networks. In Proceedings of the Earopean conference on computer vision (ECCV), pp. 53-69, 2018.
Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola. The low-rank simplicity bias deep networks. arXiv preprint arXiv:2103. 10427, 2021.
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni The compositionality of neural networks: integrating symbolism and connectionism. arXiv preprint arXiv: 1908.085,, 2019.
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2901-2910, 2017.
Eugene Kharitonov and Marco Baroni. Emergent language generalization and acquisition speed are not tied to compositionality. arXiv preprini urXiv:2004.03420 2020.
Simon Kirby, Monica Tamariz, Hannah Cornish, and Kenny Smith. Compression and communication in the cultural evolution linguistic structure. Cognition, 141:87-102, 2015.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of
recurrent networks. In International conference on machine learning, pp. 2873-2888 PMLR, 2018a.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequennc recurrent networks. In Proceedings of the 35th International Conference on Machine Learning, pp. 4487-4499. International Machine Learning Society (IMLS), 2018b.
Brenden M Lake, Tomer D Ullman, Joshua B 'Teeenbau, and Samuel Gershman. Building machines that learn and think like people. Behavioral and brain sciences, 40, 2017.
Brenden M Lake, Tal Linzen, and Marco Baroni. Human few-shot learning of compositional instructions. Proceedings of the 41st Annual Conference of the Cognitive Science Society, 2019.
A.K. Lampinen and S. Ganguli. An analytic theory of generalization dynamics and transfer learning in deep linear networks. In T. Sainath (ed.), International Conference Learning Representations, 2019. ISBN 0-51-85,8, doi: (080000115119888600 1809. 10374 arXiv: 1809.10374.
URL htttp://a http///xxivvv/. org/abs/

---

Published as a conference paper at ICLR 2023
Angeliki Lazaridou, Karl Moritz Hermann, Karl Tuyls, and Stephen Clark. Emergence of linguistic communication from referential games with symbolic and pixel input. In International Conference on Learning Representations, 2018.
Sarthak Mittal, Yoshua Bengio, and Guillaume Lajoie. Is modular architecture enough? arXiv preprint arXiv:2206. 02713, 2022.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Lars Niklasson and Noel Sharkey, Systematicity and generalisation in connectionist compositional representations. Citeseer, 1992.
Steven Phillips and Janet Wiles. Exponential generalizations from polynomial number of examples in combinatorial domain. In Proceedings of 1993 International Conference on Neural Networks Japan), volume pp. 505-508. IEEE, 1993.
Steven Andrew Phillips. Connectionism and the problem of systematicity. PhD thesis, University of Queensland, 1995.
Jordan B Pollack. Recursive distributed representations. Artificial Intelligence, 46(1-2):77-105. 1990.
Yi Ren, Shangmin Guo, Matthieu Labeau, Shay B Cohen, and Simon Kirby. Compositional lan- guages emerge in a neural iterated learning model. In International Conference on Learning Representations, 2019.
Timothy T Rogers, James L McClelland, et al. Semantic cognition: A parallel distributed processing approach. MIT press, 2004.
Laura Ruis, Jacob Andreas, Marco Baroni, Diane Bouchacourt, and Brenden Lake. A benchmark for systematic generalization in grounded language understanding. Advances in Neural Information Processing Systems, 33, 2020.
D. E. Rumelhart and J. L. McClelland. On Learning the Past Tenses of English Verbs, volume II, pp. 216-271. MIT Press, Cambridge, MA, USA, 1986. ISBN 0222132184.
A.M. Saxe, J.I. McClelland, and S. Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In Bengio and Y. LeCun (eds.), International Conference on Learning Representations, Banff, Canada, 2014. Oral presentation. arXiv: 1312.6120v3.
Andrew M Saxe, James L McClelland, and Surya Ganguli. A mathematical theory of semantic development in deep neural networks. Proceedings of the National Academy of Sciences, 116(23): 11537-11546, 2019.
Shai Shalev-Shwartz and Amnon Shashua. On the sample complexity of end-to-end training vs.
semantic abstraction training. arXiv preprint arXiv:1604. 00905,, 2016.
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In International Conference on Machine Learning, pp. 3067-3075. PMLR, 2017.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A law of
large numbers. SIAM Journal Applied Mathematics, 80(2):225-52, 2020.
Paul Smolensky. Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artificial intelligence, (661-2)):59-222 1990.
Paul Smolensky. Connectionism, constituency, and the language of thought. In Barry M. Loewer and Georges Rey (eds.), Meaning in Mind: Fodor and His Critics. Blackwell, 1991.
Paul Smolensky, R Thomas McCoy, Roland Fernandez. Matthew Goldrick, and Jianfeng Gao. Neurocompositional computing: From the central paradox of cognition to new generation of ai systems. arXiv preprint arXiv:2205.01 128, 2022.
12

---

Published as a conference paper at ICLR 2023
Zoltan Szabó. The case for compositionality. The Oxford handbook of compositionality, 64:80, 2012.
Ankit Vani, Max Schwarzer, Yuchen Lu, Eeshan Dhekane, and Aaron Courville. Iterated learning for emergent systematicity in vqa. International Conference on Learning Representations, 2021.
Noam Wies, Yoav Levine, and Amnon Shashua. task decomposition enables learning in sequence to sequence tasks. arXiv preprint 22X1::2204.02892, 2022.
A MOTIVATING EXAMPLE
0
GOOOO 0 00000
1000R
0000000
000000000
0
2+
Y
1,4g
2.
Y
000 0
0
0
0 0
0
9
N
y
334
000000
0000
0
1
0
0
0
0
0
0000
0
0
0
0
0
00000
0
0
B
D
11
00000
0000000
0
0
0
0
0
0
0.
0.
(Rt
3.
N c
3
ky
A
X
Y
X
Y
-1
11 -1 -
0
0 0
0
0 0
2
2
1 1
0
0
0
0
0
O
Ty
Ty
O
1
-
O
0
0
1
1
O
O
O
0
0
0
0
O
A
O
O
O
0
0
E
(nz 3, 0,79, 2,4,
0.r
(ny 9,
1,0g
k,
0
nix
3
0
Ng
3
K
0
1
Figure 5: Example the space datasets with five exemplar datasets. Datasets range in the number of compositional components (the inner axes of ng and ny) and the number of non-compositionall identity blocks (outer axis of k2 and ky). Note n. and ny vary the number of compositional features, while k2 and ky vary the number of non-compositional blocks of features. In this case the scale parameter the identity blocks r fixed at 2.
In this section present a motivating example which is designed provide more intuition on the space of datasets presented in Section and our definition of systematicity; Definition 3.1 We consider five different exemplar datasets from the space, depicted in Figure present the empirical training and test accuracy of a simulated linear network and take note of the generalisation of each trained network. Ultimately, we demonstrate that systematic generalisation, in accordance with Definition 3.1. does not just imply an ability correctly label unseen data points; but also relies on identifying sub-structure in the feature space to do so.
For these simulated trainings we use the first 3 out of a total 8 data points as training data, leaving the remaining data points as test dataset. We term these as the "training dataset" and "test dataset" respectively and term the combination of both with all 8 data points as the "full dataset". All networks contain 50 hidden neurons, are trained with a learning rate 0.02 and are initialised with a 0 centered normal distribution with standard deviation 0.001. We emphasise that possible datasets in our entire space and have chosen these datasets to make the images and arguments convenient and intuitive. Whether trained network will effectively generalise the test dataset
presenting just five
13

---

Published as a conference paper at ICLR 2023
3.0
Compositional Training Loss
Compositional Test Loss
Logs
2.0
Quacraate Loss
1.3
2-
0.5
1-
0.0
Epoch number
Epoch number
(a)
(b)
Figure 6: Training (a) and Test (b) loss of linear network trained dataset A (nz 3, Kx
0, ny = 2, ky = 0, 0) with 3 5 train-test split of the dataset averaged over 50 runs.
2.5
1.25
2.0
1.00
2.5
Non-commprstional Training
Quadratic
Noncompostioon
1.0
0.50
0.25
10
15
20
25
30
10
15
20
25
Epach number
Epoch number
(b)
Figure 7: Training (a) and Test (b) loss of a linear network trained on dataset B (nz = 0, kn
Ml = 0, bi -,, 2) with 3 5 train-test split of the dataset averaged over 50 runs.
depends the rank of the full dataset and number of training data points observes. Simply put: the network must be trained on as many (unique) data points as the rank of the full dataset. We now demonstrate this point with the examples and simulations.
Take for example our first dataset with only compositional input and output components corresponding point in Figure 5 ( k; in the full dataset but the covariance matrices Σ E 3x3 E IR2x3 have ranks of 3 and 2 respectively. Thus, by using a training set of 3 data points the network will effectively learn the input- output mapping: W2W1 mapping for the full dataset. Thus, the network will generalise to the test dataset. This is displayed for simulated training in Figure 6 Importantly, even though the network generalises, this is not yet systematic generalisation as we have defined it in Definition 3.
ny = 2, k. 0, 0). In this case there are data points
-- As result the network has learned the correct input-output
In comparison, consider a dataset with data points of only non-compositional input and output components corresponding to point B in Figure 5 (n2 0, k2 = 1, ny = 0, ky 1, 2). In this case the covariance matrices ΣR E 8888 ΣV E R both have a rank of 8 and if training dataset of 3 data points is use then network will fail learn the covariance matrix (and mapping) appropriate for the full dataset, As result the network trained on the training set will not generalise. Since there are only data points learn the rank 8 covariance matrices, generalisation is not possible for this dataset (the network needs to be trained on the full dataset). Figure 7 displays the simulation for this case. Note that the test error does not decrease during training.
Now consider putting the two settings together (n,, = 3, k2 = 1, n, 2, ky = 1,r 2) which corresponds to point C Figure 5 We have the compositional dataset being appended with a non-compositional dataset to arrive at dataset of 8 data points with both compositional and non- compositional sub-structure (on both the input and the output). If we were to calculate the covariance matrices (Σ* E 1l1x1 y E 10x for this full dataset we would see that both have a rank of 8 due to the non-compositional sub-structure being of rank above generalisation from a training dataset of 3 data points is not possible. This case is displayed in Figure g Note than, even though compositional features are present on the input and output the network does not generalise well, even when considering the test performance for compositional
Thus, for the same reasons as
14

---

Published as a conference paper at ICLR 2023
3.0
Compositional Training Loss
Compositional Test Loss
Non compositional Traiiin
Non-composition Test Loss
Loge
Quadraate Loss
1.3
2
1
0.0
30
15
20
30
Epoch number
Epoch number
(a)
(b)
Figure 8: Training (a) and Test (b) loss of linear network trained dataset C (nz 3, kr
1, Ray = 2, ky 1, = 2) with a 3 5 train-test split of the dataset averaged over 50 runs.
1.50
Soon-compostiinnllalae Loss
3.0
2.5
0uaaranc.oo LO3S
1.00
2.0
0.75
1.5
Non-compositiona Test Loss
1.0
0.25
0.5
0.00
0.0
10
15
20
25
30
10
15
Epoch number
Cooch number
(a)
(b)
Figure 9: Training (a) and Test (b) loss of linear network trained on dataset D (nz 3, kgg 1, ny = 0, by = 1,r 2) with a 3: 5 train-test split of the dataset averaged over 50 runs.
outputs in isolation. However, we know that if we were to consider the compositional sub-structure independently it would be rank 3 problem and would support generalisation. The easier task of mapping compositional input to compositional output (the first dataset we considered) exists within the larger problem of learning the full input-output mapping of this combined dataset. This was just obscured by the inclusion of the composposiii components. This is our notion of systematic generalisation: identifying sub-structure in larger problem (which does not support gencralisation) such that we can learn the sub-structure separately to support generalisation. Thus, our definition of systematicity requires finding the sub-structure as much exploiting it for generalisation.
We display two more cases corresponding to points D (ng 3, h2 = 1, = 0, ky = 1,r 2) and E (ng = 3, k. 1, Fy 2, ky 0, r 2) in Figure 5 The simulations for each dataset presented in Figures 9 and 10 respectively. In both cases non-compositional input components are present and the network does not learn rely solely on the lower-rank compositional sub-structure. As result the network does not systematically generalise.
Compositiona Training
Compositiona Test Loss
Quadratic Loss
2.0
Quadratic Loos
3
1.5
2
0.3
10 15
20
25
30
10
15
20
25
30
Epach number
Epoch number
(a)
(b)
Figure 10: Training (a) and Test (b) loss of linear network trained on dataset E (nz = 3, hig
1, my = 2, by 0,r 2) with a 5 train-test split of the dataset averaged over 50 runs.
15

---

Published as a conference paper at ICLR 2023
B RANK OF COMPOSITIONAL DATASET SUB-STRUCTURES
In this section provide the caleulations of the chance of sampling full-rank matrix for the compositional partition of the input and output space. We will begin by considering the case where the number of compositional input and output features are both d We emphasize that this section aims to demonstrate the benefit of relying and is not meant to be general to all forms of binary matrices. Since we are using three input and output features there are 2 = 8 unique data points in the input and output. We are concerned then with the rank of the empirical covariance matrix Σn2 3x3 We use the empirical covariance matrix since we only use samples of the dataset to train a network and not the full dataset.
compositional sub-structure to learn network mapping
For neural network to learn generalizable mapping it needs to learn from a batch of data with a full-rank covariance matrix that has the same rank as the full dataset. If this the case then the network will learn the same mapping from the training sample it would the full dataset and will generalize to all unseen data points from the same space. We note that for sample sizes of n = 1 and 2 it is impossible to obtain full-rank empirical covariance. Thus, we first consider sample size of n = 3. In the 3-dimensional case the only way to obtain a singular matrix from 3 samples is if the opposite data point an earlier data point sampled. For example, for the data point [-1, -1, the opposite will be [1, 1, -1]. With this observation we can determine the probability of not sampling an opposite data point as follows:
P(fullrank|| n 3, d 3) = ((thrrowwthhouuu p(tro P(throu)
=(4/6)(6/))888) = 0.57
For sample of n 4 data points a similar procedure applies, except we need to account for the fact that we are able to sample one opposite data point now. Thus, there are four cases: the second data point is an opposite, the third data point an opposite, the fourth data point is an opposite, or there are no opposites (we also drop P(throw)) 8/8 to lighten notation):
P( P[fullrnk||n = 4, 3)
P(throw, | throw,, hhh.
+ + httroo////hhrrryry therroowwthrow,...o throw,,
http://hwwwoowwwwooooo (throm:))))))) +P( http://wwww.....h.....//////hh/e
+P(- throw, http://www....................o.
=0.91
For a sample size of n = 5 or more we are guaranteed to have at least linearly independent data points and full-rank covariance matrix. Thus, the network module trained on this sub-structure will always generalize. A similar set of calculation can be done for the case of 4 compositional features and the same conelusions hold. The calculations, however, become large due larger sample sizes being used and more possibilities to sample lincarly dependent vectors. Thus, we present the andd
probabilities from empirical results for the 3 features and feature cases For these empirical results 5000 samplings from the dataset are used for each sample size to calculate a covariance matrix and determine if is singular.
Sample Size
Probability of mall-Rank Covariance
3
57.5%
4
91.9%
5....8
100%
Table 1: Probability of sampling full-rank covariance matrix for the binary compositional component of the input and output with 3 features each (n, = ny = 3)
16

---

Published as a conference paper at ICLR 2023
Sample Size
Probability of Full-Rank Covariance
4
29. 29.74%
5
84.76%
6
93.82%
7
99.2%
8
99.72%
{9.... 16}
100%
Table 2: Probability of sampling a full-rank covariance matrix for the binary compositional component of the input and output with 4 features each (Ng
Thy 4)
C LEARNING DYNAMICS IN DEEP LINEAR NETWORKS
The dynamics of learning for shallow and deep linear networks derived in Saxe et al. (2019). We state full details of our specific setting here. We train a linear network with one hidden layer W X using gradient descent. This to minimize the quadratic loss L(W1, W2) - I|
gives the learning rules E|AW"] = 2nd W (Y w X)Xx and E[AW?] = 2 (Y
w² By using small learning rate and taking the continuous time limit, the mean change in weights is given by r de W W (Σ W2W'E") and d W (E
de W= where 20 [[XX" is the input correlation matrix, y = E X is the input- output correlation matrix and r 2 - Here, measures units of learning epochs. It is helpful to note that since we using small learning rate the full batch gradient descent and stochastic gradient descent dynamics will be the same. Saxe et al. (2019) has shown that the learning dynamics depend on the singular value decomposition of v USVT
E uau and Σ VDVT
Ee= o To solve for the dynamics we require that the right singular vectors V of V are also the singular vectors of Σ² This is the case for any dataset in our space, shown in Appendix D Note, we assume that the network has at least 2 hidden neurons (the number of singular values in the input-output covariance matrix) so that it can learn the desired mapping perfectly. If this is not the case then the model will learn the top Tiy singular values of the input-output mapping where ny is the number of hidden neurons (Saxe et al.) 20144). Given the SVDs of the two correlation matrices the learning dynamics can be described explicitly as W (1 (t) = A(L)VT =
2 To (t) where A(t) is the effective singular value matrix of the network's 's mapping. The trajectory of each singular value in A(t) described as Ta (t)
exp( .) From these dynamies it is helpful to note that the time-course of the trajectory is only dependent on the E singular values. Thus, n affects the stable point of the network singular values but not the time-course of learning.
An
1-(1
We have chosen our datasets to be simple and interpretable for clarity and tractability. However, fundamentally, our analysis with deep linear networks applies to a more general situation for which other theoretical techniques relying on random initialisation fail (Geiger et al. 2020: Jacot et al. 2018, Sirignano & Spiliopoulos, 2020). In particular, consider the broader space datasets in which compositional inputs, compositional outputs, con-cooposiiional inputs, and non-compositional outputs are each rotated by individual orthogonal mappings. As one specific example, consider the dataset formed by applying a permutation to the compositional outputs. This change affects only the singular vectors of the task (also permuting them relative to the original task), not the singular values. This dataset can no longer be solved by learning possible solution for all datasets in the original space), as the network must learn to implement the required permutation-bal but it will do with identical learning dynamics and systematicity properties. raadomm initialisation cannot know this desired permutation, which can only be learned through error feedback. This, further, motivates the use of the linear network dynamics which incorporates feature learning into the analysis.
identity transformation (which is
17

---

Published as a conference paper at ICLR 2023
D SINGULAR VALUE DECOMPOSITION EQUATIONS
In this section provide the general formulas for the singular value decomposition of the I and Σn covariance matrices for any dataset the space of datasets. As stated in Section 4 the right singular vectors 2 must match the singular vectors of 2 which is the V matrix below. Thus, D" = V DDV and D USV
Let:
(2,
B 2200
C-= 2222
THP = kg
x2 - ky
2
12 S2
Where THP is the SVD of ky,,
)
II
20x x2
kg )2 2 2
)2g and H =
(kkky ) x2
Then the following the matrix formulas for the components of the SVD for EVe and E².
Ony kk 20
20 (
U =
(13)
2²
B
(C- B)
2 12 +2nx)
2 (kum2)
VT_
(M2 (22m2
200
I Xnx
2 422
(14)
Ok2 2nx xnx
pst
(ket 1krr+2"0 [kky 4200)
(ker (2ar" (2r) (ki
2 A)
On xkku o² (kanky)
S
20n
220
0 nnx xnx
2nz Ik x
(15)
(
In x
On 2
D =
2
(16)
2k,2"x Xmx
hgt² 2nz
I2 x2
We note that each distinct singular value occurs multiple times in the dataset: A has multiplicity nh - Byy A2 has multiplicity Rl.. and Aa has multiplicity n -hg. Correspondingly 8 has multiplicity Dr and 02 has multiplicity 2 Pzz
D.1 PROVING THE CORRECTNESS OF THE SVD
Proving the correctness of the above SVD is easier than deriving Thus we do so here by showing that L USVT:
SVT = ( (kar++2"*
+2 (kkrr +2 422m)
A +
) 22n5
$
(I
22nz 11_A) A)
On 2 ,
Ok 2 xnx
(kipkin)
Ik 20x x xkk 2
201
(2
2nd
In xax
x² 2
Ok2 2nx xDx
px
SVT
R 42"0 gn
20n
A +
kyp 2
(1 zame A)
y (k,,,,4220
2
AΩ +
20nz
(1 1
22m
A)
ny ky 2ax
(ky) 2n
PT
0 Ony 2
USVT
2nx (ke, r2 +24))))
B+C
22
(C- B)
( )
Ti (ky +2m))
Ton (kyr
ky 2.r2+22 42 25rz
A +
kyp
(I
1 A)
1kky +220)) ))
AΩ2 +
(I 1
A)Ω
2nx
zan
2
20me
24n
On, x xk,2n
(kiy) $ PT
18

---

Published as a conference paper at ICLR 2023
From here we will solve each quadrant separately (Q1 to Qs below). Firstly, we mention some useful identities:
A -0,00 "
B 20
C 2
0,7 =2 Ing xhy
)z 2 2g02 =2 Dyyl
BA (0,,0) 22 2 Poglf =2 B
CA
22 O2 =22n B
We now solve for each quadrant of the USV matrix:
1 $
kyr
1/2
1
Q1
A)
26n=
22 (Ky, + 22xx)
2
k
kiy
02y0
+
22
n
22 (Kig 12 + 2nnn)
(Rig
kgr2
+ 2m
22y0
2n
22
Q2 =
22 A52 +
22n A)22z
28m,,
2 + 24m (ky
2na)
kyrd
7
22 Al +
P 1. AS
24n,
24m (Kyr + 2nx)
28n (kiy 2 + 22n2))
22m
24m (ky + +222)
24m= (ky + 2m12
2, S2
S2y
22n
2n=
22
1/4
22
2 + 2
kyr?
1/4
1
Qs-
B+
(C - B)
A
(1
A)
23nr (ky 2n²)
23m= (ky)z)
25m
2
23n
p2
1/2
x²
7/
kyr? + 2
7/2
B+
(C'- B)
A
23nz ( + 2nx)
23m (k)))2)
25mz
p2
1
y2
kiyx2)
7/4
+
B +
(C B)
(1
A)
23nz (k., r2 + 22z)
23m (k),
2n
22n
,2
1/
72 (ky + 2nm)))
BA +
- (CA
28m
28n 12)
kynd
1/
p2
1/2
+
B(I
A) +
(C-B)(I A)
2 (Riy + 2nx)
22n
24m=
22n
2
1/2
2² (2( + 2n
1
1 (ky 22 + 2n=))
BA+
CA
BA
28n
28 (kig)
28n (k2y
ky
1/
Rig
+
B
BA
24m (kiy + 2nx))
28mz (key 2 + 2m²))
19

---

Published as a conference paper at ICLR 2023
r²
1
x²
1
+
C(1
A)
B1
A)
2
22m
2
22n
22
( r2 + 2
(1ig)
12
2nl1)
2
B
+
B
B
2dm=
24 (k)
21n
(kyr
Kyr
3
hig
7/4
+
B
B
2 (Nig 2 + 2nx)
22m (k (kug22
+ 2nz)
1
22
1
+
C(I
A)
B(I
A)
2
2
24n
2
y2
n²
22
B
+
C
CA
2dm
2
24ma
y2
2
B
+
BA
24m,
2dm
1/2
x2
C - rB + Br
24m=
r
22 2
r
Ω2
22
n
22
1
2
Q1
B+
(C (C--3)
28nz 1 + 2nz
23m= 2k)
12
(kgr + 2nx)
hightd 23n
$
1
+T 12
1Ω2 +
(I
A)
pm
2?n=
2
2
22
72
(C- B)
(r² (r²(kyr² + 2nx)
B+
AQ2
23n, r
+ 2mm)
23ma ( 2k))2)
27ma
23m (kep + 2mx) )
x2
1/2
x2
1
+
B+
(C B)
(I 2
A)12
20n.
T y2
+
pt
2
1
(ky + 2
BAQ
+
(C - B)AΩ,
210na
210na (kyr2)
kyrB
B(T 22n, A)12
20n
(ke, + 2
1
22 PT
+
(C-- B)
22n A)l, + T 2
26n=
1
1/4
r
+ )" )
CAR - y (ky, + 2nd)
4/4
BAQ
+
BAΩ
210m=
210n= (k2,
210m, (2)
ky
kyno
BΩ
BAΩ
26n
(ky, 2
210na (kyy + 22a)
1
1
1
A)S2, + T y22
+
C(T
A)S2
B(T
pT
26n
22m
26n
22n
2
1
(r
+ 22==))
(ra(ky) + 2nz²)
1/2
BRx +
B22
BΩ2
20n=
20n
(k)
26n (ki
20

---

Published as a conference paper at ICLR 2023
Kyr
B2
BRL
26nz
(Kyp
+
2nx))
226
(kyr² + 2mz)
pd
1
1
r2 2
+
C
A)52z
B(
A)52
+ T
pT
26n
2
20
2
pd
pd
1
1
B
+
CΩ2
CAΩ
26n=
26n
26m
22n
r
rd
$
p2
BΩ
BAΩ
+T PT
26nz
28mxx
2
2
=(
1
,4
r
1
BR
+
CU2
BΩ
26n
26m
26m
r4
y
2²
BΩ₂ + _ pT
B
26n
26n
n
2
x²
CΩ2 +
pd
23n
2
2
p2 2
0- Q2 + T
pr
23
Dh + ' p2
PJ
20n
2 222 (k kig)
Ω
+
T
) pt kighy
20n
2n
y² (Ka
2 (kgkky)
22n
2m
kig
2ax x
n
high
2n
,2
2
72
7.2
20n
22 P2y
+
n
1
20x
22n
S2p
2n
1
2
Thus the final SVD of y0 is (note that quadrants 2,3 and 4 repeat based on the values of le and ky):
T0 Py
2 Py
20g
USV
YXT
n
I x 2
12nx 2
We now show that the V and matrices are orthogonal:
2
28x (k,r2+20z)
I x
0 One x 2 2
V
(hx +2
Xnx
2 (he 4 22
Ok 20x
3/ PT
52
[ (L)
2" (kark=r--00
(k, x 420=
2
nx Xnx
Kn
2oz (22x
1227
3 [ka))
D2P
PTΩT
(kt) pT p
2nx 42 (2
[Je 4 20
n
I n, xnx
(hy 42
(hr
kop2
In x
2 2h +2 (2nr
P
7
PT
I2 x
(k.r2 20x [(ke]
On X 1 x2
Ozex X
21

---

Published as a conference paper at ICLR 2023
(2 (kgr"
BT + 22n (kyrtt) )
7 (C B)T
UTU = 2 (Nig 2n0)
Ok x
1 )²TT
xky
(k,
+ +
2 (R(y
(0- B)
( (
We first consider Quadrant I:
1
Q = 2n (2 + 2m²²)
(23m (220m
x2
2²
) (C-
3/ (C-B)T B)7
+ biy
BT +
+ +2m))
23m (kyr)2)
n
n.
7/4
B
(C B)
23m, (Kin)² 22 +2n,)
23n (kigg()
1
2 (Ki, + 2nx)
x2
2²
1/
x2
1/4
+ ky
BT +
(C (C- B)²
B
23m (kyp² + +mm)
20m (k2,
2Bn (kyp2 + +2m=)
+ kig
x2
BT
+
n²
1/2
(C - (C-B)7
23 (k. (20m)((),))))
x2
)
2/2
(C B)
23n (ky, + 2mx)
23 (ky,
2 (ks, + 2n.)
1.2
1
1
+ Aiy 23 (R:y) 2 + 2
BT B + lig
(C B)TB B
20m= (ky, (Ray 2
+ by
(C - B)
20 (ky 2) (ky, x2 + 2
+ ky
(C-B)² (C B)
23ma (k2
is helpful to note that (C - BBTTT B = On xn, and S.S.DyD = =5-11) BBTT B
2nd
kyy
Q =
BT B + 23nz (ky, 2 + 2nz)
BTD B
23m= (22y + 2
kyr²
+ 23n (kyr2)
(C-B)T(CC CCC-B B)
23m k2y + t
1
Q
B² +
(C BB) -B)
(ky + 22xx)
23m
Q
1
BT
(C- B)
23mz
23m²
Q =In XDx
Where we used the fact that BT B + (C- (C-B) B) 23 I Xnx Thus:
$
) 7 (c (C-BBr) 7)
BT + (
UTU= =
2n (Ky
20nz (k,
0 20x X
Rg 2TT
22

---

Published as a conference paper at ICLR 2023
2n (ky
Ony ky 20
2a (kg 2nz)
2
B +
25mx (ky
p²
(C-B) B)
kgy
)
3
I xxx
BºT (2tTT) (C- BY
2 (Rigit +2mx)
2y
T + 2anz
1 (C
Ky Rig
IT
2 (2
3/
I Xnx
Ry
B
1 )² (C- B
2dmz (Rg 2
kyr
T
TT
Kig Koy
1T
2 (Ri x2"x)
2
I Xnx 02ox x
On x2
1 x 20x
Thus, the have proven that USVT E and that the singular vector matrices are or- thogonal. Since the SVD of the Σ" matrix a special case of Σnee with ny nr then this also proves that the SVD for E" = VDVT with orthogonal singular vector matrices.
E INPUT AND OUTPUT PARTITIONED FROBENIUS NORMS
We partition the input-output mapping along the compositional and non-compositional input and output components. Figure II shows this partitioning and how it relates to the SVD of the covariance matrix, while the time-courses for these norms can be seen in Equations [7 to 20 From these equations we see that the mappings to both components of the output rely on all inputs. Thus, the non non-compositional inputs still offer some benefit to the compositional output and are used in the network mapping. Likewise the compositional inputs are used for the non-com con-copposiiooall mapping.
2 nl
1..2y-Norm.
xi(t)
(17)
(kip + n (ku 2n
2 p
T m7(11)
(18)
(Ri + 2 [kin T2 2 + 2m=²
1
n kig
mt( + n (nz nly)
DgTy D-rm-Norm
m²{())
(19)
(korr + 2n (ke 2 + 2m
h + n
1/4
(1) + (ne ny kor? (1( + +2 -1=))
T T-ry-Norm-
r
2 )( (kur 2 2=2
22 + n
(20)
shows the simulated and predicted training dynamics for these norms deep linear network. We note that the mapping to the compositional output relies evenly on both the compositional and non-compositional inputs, with slight preference the compositional inputs. Similarly, the mapping to the non-compositional outputs also uses the compositional and non-compositional inputs evenly, with preference towards the con-compositional inputs towards the end of training. In Appendix F we consider the same norm equations for the split network architectures.
Figure 12
23

---

Published as a conference paper at ICLR 2023
Multiply Weight
2
W
Matrices
W
WWW
b
b
SVD
2
+T
W
V.
U2V
U3
22 22 Frob
= Frob(TT
r x 2y-ormmmm= = FFrmm
Frob(
2x r y y = = Frob I I =Frob
Frob(TT
2
= Frob
2
T
Figure 11: Representation of the partitioned norms and their relation to the SVD of the covariance matrix. Specifically, we consider the norm of pieces of the network mapping individually, but these pieces only depend certain modes of variation. By analysing the time-scale of learning and final value of the norms we can determine the network's 's ability to systematically generalise.
1.75
22Oy-Norm
Predicted P2 Norm
2,rm-Norm
Predicted I' 1222y-Nou Norm
1.50
Oor,,-Nrm
Predicted y Norm
Norm
Predicted r g-orm
Frobenius Norm
1.25
1.00
0.75
0.50
0.25
0.00
0
50
100
150
200
250
300
Epoch number
Figure 12: Frobenius norms of the deep network mapping partitioned by the compositional and non-compositional inputs and output on dense linear neural module.
F MODULARITY AND ARCHITECTURE
In this Section we now consider the norm equations for the modular network architectures. In Figure 13b we depict the Frobenius norms of the mapping for the output-partitionel network (the network's 's Singular Values are shown in Figure 13a). The dynamics of this case can equally be seen as using one neural module responsible for the compositional output (Ω2,) mapping and another for the non-compositional output (Ty) mapping. From the perspective the I, mapping the compositional output features (92,) not present (n, is effectively set to 0 for this module), and the mapping will no longer be dependent on म. The compositional output mapping is still only dependent on the m. effective singular value. The time-courses for the resultant Frobenius norms for the module
24

---

Published as a conference paper at ICLR 2023
mapping to the compositional output are given in Equations 21 and 22 (by substituting ky = 0 in the norm Equation from Appendix E). Similarly, the time-courses for the resultant Frobenius norms for the module mapping to the conposopoiii output are given in Equations 23 and 24 (by substituting By = 0 in the norm Equation from Appendix H.. From these equations we see that the two mappings use entirely different modes of variation, and as a result the learning of one mapping does not imply any progress in the learning of the other. However, even with the output partitioning, the norm connecting non-compositional input to compositional output is not O. Nor is the norm for the compositional input to conpoooposii output mapping. Thus the output partitioned network will still not learn systematic mapping for all datasets in the space.
2n nt((t
(21)
22 + 2n
Nyker
Ta
kgr + 2 nt())
(22)
2u
PgT y
(1)
(23)
kgr +
Ngker? kgr
Ta
(t()) + (2 n2 (Tz))(()) 2n
(24)
Finally, we consider the fully partitioned network. In this case there are two modules, one connecting compositional input and output components and another connecting the non-compositional input and output components. The module connecting the compositional components is restricted to working with effective datasets with the hyper-parameters of k, = ki O. Substituting this into the norm equations from Appendix E produces single norm shown in Equation 25 Similarly, the non- compositional module trains on effective datasets with n, = ny = O and has single norm shown in Equation 26 We note that this, very strict architectural bias of perfect partitioning of compositional and non- compositoiii components, is enough for the network to systematically generalize, since no non-compositional components affect mappings to/from compositional components. Thus, only the most perfect modularity is able to achieve systematicity as defined by Definition We consider the case of imperfect output partitions Appendix G and find the network will no longer be systematic.
22rr /ny (t)
(25)
T
= (t)))
(26)
Real
Prediction
1.75
T.By-Noeu
Predicted D2
Predicted I. Norm
Real
Prediction
1.50
N.TyyNorm
Prodicted Norms
Real
Prediction
Siagoler Valte
0.6
1:25
T,T, Norm
Predicted T. Norm
Foohaita
1.00
0.1
0.75
0.2
0.50
0.25
0.0
0.00
30
1000
200
250
300
50
100
150
200
250
300
Epach mumber
Epoch uumber
(b)
Figure 13: Training dynamics of the deep network mapping partitioned by the compositional and copposoposiii inputs and output on two linear neural modules. One module maps exclusively to the compositional output, while the other maps exclusively to the non-compositional output. a) Learning trajectories of the three unique Singular Values learned by the output-split network. b) Frobenius norms of the output partitioned network.
25

---

Published as a conference paper at ICLR 2023
G IMPERFECT OUTPUT PARTITIONS
We now investigate the case where the split network architecture does not perfectly partition the output into the compositional and non-compositional components. In this case some of the non- compositional identity output blocks are grouped with the compositional outputs (we only consider partitioning along the compositional and non-compositional blocks keep the closed form solutions tractable). Thus, we separate the number of non-compositional outputs ky into the number of non-
compositional outputs of the left network branch kiyll and right network branch kyg such that k.let
i.right kiy
Kig.
Equations 27 to 32 show the set of norms which emerge. In the extreme cases when k-gn ky we recover the dense network equations shown in Equations 17 to 20 since T2 = 33 for Equations 32 This is apparent from the singular value equations for л22 and T3 shown in Equations 7 and with ky in the numerator which is replaced by 4.jeh 0 for the right module. Thus, Equation
31 and
31 and 32 fall away completely, In the other extreme case of hn ky we recover the split network equations shown in Equations to to 24 This is again because T22 TT 0 but this time from the left network branch's perspective. By definition A.len
this case and so all components of Equations 29 and 30 fall away, leaving just Equations 27 and 28 with Equations 31 and 32 The most important conclusion to be drawn, however, that if any non non-compositional components are partitioned with compositional components then the module will behave similarly the dense network of Section 5 This can be shown the same way as in the proof for Observation 5.1] by noting that Equations 29 and 30 will be non-zero for any case where the compositional input to compositional output is learned (due to a shared mode of variation). Thus, only the most stringent and perfectly allocated network modules will be able to specialize.
1
22 Bl
Og.2y-Norm=
mf(1)
(27)
(kig 2 (eeett 2
1/2
2 2
Ta.2y-Nrm-
x?(1)
(28)
(krr2 + 20 (ky (1lefl pel 2n
2d kleft nyg
2 (nz nly
1/2
2g pleft -Nors-Nomm-- "1
(t)
T2 (t)
(29)
12 + 2 (kibe 12 + 2m
k + 2m
ke t
nyy
(t( + (nz ny kay?
T plest -Norm
T2 + (2 - n mT)))((
(k,r2 + 2n [kiy Ness, + 2
k + 2
(30)
n,
22g Drighttht_Na -Nom
k2r + n x2(()
(31)
I a right -Nrm
T2(1) + (2 n2 n33)m((()
(32)
y
1 + 2n
H PROOFS OF OBSERVATIONS
H.1 PROOF OF OBSERVATION 5.1
In this section we prove Observation 5.1.: For all datasets in the space it is impossible for a dense architecture to learn systematic mapping between compositional components.
Proof: To prove this we are required to show that: For all points in the space of datasets: Tay Bay Riz ky,r r z that O. 0 = -orm>> and P.T 0 for & Z
26

---

Published as a conference paper at ICLR 2023
Thus, we assume that Og2y-Norm>> 0 and use the fact that singular values are positive semi-definie to show that:
2 nl
Bg -Norm
at(()
(k, 2 nh [Kit 2n
ftt((t
>0
since a = (k,, ".,r"+2' +2 1k +2
2
> 0. Given that (1(1) > 0 and mry ny. ka Kig E Z+ then for the
Ta and y.rrmssss
n kin
Tas2y-Norm
(kpr2 2 (Ky p2 + 2n.) x7(()
(t)
>
+ I 22 -Nrm >0.
and
nn nyy
2nd (n2 nyy
DgT TgTyy-Nn -Norm
1i +
n2 (t)
rkiz2 + n (kig 12 + 2
knr + 2
2 My
(1i, + n (Kig 2 (1())
(t)
>0
Q2T y-orm >0
where (h, +2 (e, +222)))
n2, Ro
> 0 and c
2 Ry nyr
+2
>
H.2 PROOF OF OBSERVATION 6.
In this section prove Observation 6.1.: Modularity does impose some form of bias towards systematicity but if any non-compositional structure is considered in the input then a systematic mapping will not be learned.
Proof: To prove this we are required to show that: For all points in the space of datasets with the output partitioned network: T2z Tlys kas ky: r ž that - > + R2T',,-om 0 for t E = and f2,52y-Nom -Nomm > 0) + I-22y-Norm
0 for E Z This shows that, while modularity removes the guaranteed association between compositional input and non-compositional output is still impossible to remove the association of non conn-oomositionall input and compositional output.
We assume that
0 and use that the singular values are positive semi-definite to show:
2nd ny =1)
2ormy-Norm
k2 + 2
-am (1)
>0
since
n 4222
Given that mf(()= > and nz:; Ruys koy ky + then for the I' 1222y-Norm
Rykkr?
P 1ooom-Nomm
(t)
k2 2n
(t)
+ r Ta >0
22 22
where
>
27

---

Published as a conference paper at ICLR 2023
However for the y-
2 x²)(t k2r + 2n
RgT y
=CT (t)
The value of (t) is not certain at time just from knowing that 2222y-Nrm 0. Thus, 92202 Norm > 0 + y-Norm- > 0 for t e Z However, it is still the case that 22 > 0 + Tas2y-Norm > for E Z+ Thus, the network will still not learn systematic mapping from the compositional input to compositional output.
H.3 PROOF OF OBSERVATION 6.2
Finally prove Observation 6.2 The fully partitioned network achieves systematicity by learning
the lower-rank (compositional) sub-structure in isolation of the rest of the mapping.
Proof: To do this we show that: For all points in the space of datasets with the fully partitioned network: Tiz Pay kn, ky, E = that 2= = y-orm = 0 E Z+
The norm equations for the fully split network are shown in Equations 25 26 Clearly from these equations there are no I 12 and 12.1 -Normms More specifically, the neural modules learn on restricted datasets based on their connectivity. For example by substituting Kg = Ky 0 for the left module into the full norm equations shown in Equations to 20 the Tu T2.T and I y -Nrrss in Equations [8] 19 and 20 become 0. Similarly, the right module is restricted to f2 ny the only norm equations which are not O will be the S2, -Norm for the left module and the r,T -Norm for the right module. The compositional mapping then is not affected by non-compositiionll components of the data. As result the sollly-paritionedd network is systematic by Definition
Thus,
I ALTERNATIVE LEARNING RULES TO GRADIENT DESCENT
In this work we have relied on gradient descent dynamics since it the most widely used optimization algorithm for training neural networks. However, a number of alternatives exist and previous work (Cao et al. 2020) has characterized two-dimensional space of learning rules. The two dimensions correspond to the two parameters y and 1) which determine which optimization algorithm is used. The update equations for the algorithms in the space for a one-hidden layer network are given by Equations 33 and 34, where ||Willlz depicts the L2 norm is taken along the rows of the W, matrix, leaving column vector of dimension equal to the number of hidden neurons.
[1/T)W/T (Enz WWW, (W, XTWFW,) AW
if otherwise
(33)
(1/T) (E W,W,E,... 111 II)
AW₂ (Enn W2W E, ExH. WF -
(34)
As in (Cao al. 2020
focus four learning rules within this space of learning rules, namely
anti-hebbian (7 + 0, < 0), contrastive hebbian (> = 1, = 0). hebbian (7 - 0, > 0) and quasi-predictive coding (7 1, = 0). is helpful note that gradient descent is also defined in and O. Figure depicts the singular value trajectories the space of learning rules with input/output norms for each learning rule compared gradient and the sesemaatc/non-systemmatit
descent. From these results we see one primary conclusion, while they cause the network to learn at different speeds, all learning rules result in the network learning along the same modes of variation as with gradient descent. This is evident since all networks achieve near () training error and converge to the same singular values and Frobenius norm values. Thus, they are ultimately learning the same mapping and confined to the dataset statistics. This means that regardless of the learning rule used, from any rule in the whole space defined in (Cao et al., 22220), a dense network will share the क mode of variation between the compositional and non-compositional components. Thus modularity is required for the same reasons as in Section 6
28

---

Published as a conference paper at ICLR 2023
1.75
Proficol B. NaxE
Roal To Roal
Prodetior
1.50
Prodiced R.F, Nam
Prodetion
1.35
NomyNemm
Sinpler Vale
Todoriss
0.75
0.70
0:55
0.0
0.00
750
1900
Rlech
(a) Simulated singular value and norm trajectorics for the anti-hebbian (AH) learning rule
(y + 0, 77 < 0) compared to the predicted gradient descent (GD) trajectories and norms.
1.75
R. Nanu
Prodictod Noeaa
0.5
Roal hn
Rosl
Prodiciau
Prodition
1.70
Norm
Frediceed N.rtrN
Prodicea NiirE
Narrz
Roal
Prodictass
Prodered Nomm
Valae
3.00
0.75
0.2
0.30
0:00
200
100
750
1000
1200
1000
250
900
750
1000
1230
1500
Rooch narche
Roech mimber
(b) Simulated singular value and norm trajectories for the contrastive hebbian (CH) learning
rule L, compared the predicted gradient descent (GD) trajectories and norms.
1.75-
R,0 Nomn
Preducte Noem
Roal
Prodeciou
Norm
Frodeted N.
1.50
Porm-Norm
Prodione O2 Nerr
Sugpler Vales
Real 9;
Predction
3.56
T.TyNan
Prodicted E Norm
Endentos
1.00
0.75
0.30
0.25
11:0
Spoch mands
(c) Simulated singular value and norm trajectories for the hebbian (Hebb) learning rule (7y ->
0, 1) > 0) compared to the predicted gradient descent (GD) trajectories and norms.
1.75
Froduced Noem
Beal 5,
Predetuor
T.0,, Noen
Prodicne E. Norr.
Rai 92 Raal
Prodstion Prodictans
Pustictod 12,7 Nuaa
Sigple Vilee
Nay.Nam
....
Froduced T.T Norm
3.00
0
0.75
0.50
0.25
0.00
2000
1000
.500
2000
2500
3000
500
.000
1500
2000
2000
3000
Spoch
Spech
(d) Simulated singular value and norm trajectories for the quasi-predictive coding (PC) learning rule (7 = -1,7 0) compared to the predicted gradient descent (GD) trajectories and norms.
Figure 14: Simulated singular value trajectories and eeeematic/noo-yystennne input/output partitioned norms for the four alternative learning rules compared to the predicted gradient descent trajectories and norms.
29

---

Published as a conference paper at ICLR 2023
J CMNIST ARCHITECTURE AND HYPER-PARE PEEER-PARAMETERS
In this section provide the network architectures for the CMNIST experiments well other details of the experimental setup. We scale the non-systematic output labels to help the network learn these labels. For the results of this section a scale of 10 was applied, however, the results are consistent for wide range of scale values. Increasing or decreasing the scale merely changes the time taken for the same effects occur. Both the dense and split networks are trained using stochastic gradient descent from small random initial weights sampled from an isotropic normal distribution. No regularization, learning rate decay or momentum is used. We aim to keep the setup simple as possible while reducing the effects of other implicit or explicit regularizers on the results, since we are comparing the systematic generalization of the networks. The simplicity also aids the comparison between the dense and split network architectures which is the goal of the experiment. Table 3 shows the hyper-parameters used to train both networks, which have the same parre-ppaaeters and the two architectures shown in Figures [5 (dense architecture) and 16 (split architecture).
Table 3: Table showing the hyper-parameters used for the CMNIST experiments.
Hyper-parameter
Value
Step Size
2e 3
Batch Size
16
Initialization Variance
0.01
We describe some further observations in addition to the discussion presented in Section of the main text. Consistent with results in linear networks, when training dense network there is portion of the compositional output mapping which is learned at the same time as the non-composittonal output mapping (particularly from around epoch 150). In contrast, when using a split architecture the compositional output mapping is learned independently of the non-compositional output mapping and faster, while the non-compositional output mapping struggles to learn. The non-compositional output mapping fails to reach a near-zero eиror and plateaus around 0.4 regardless of how long training lasts. Thus, without a compositional output mapping sharing the same hidden layer and helping learning, the non-compositional output mapping is ineffective even at fitting the training data in a reasonable amount of time.
Turning to Figure 4c we see that for both the dense and split networks the non-compositional output mapping does not generalize to test data. This is to be expected as unlikely that the same numbers in the training data would ever appear in the test data. Notably, comparing the compositional output mappings we see that the converged dense network generalizes far worse than the converged split network. It is interesting note that initially both networks generalize equally well, however, in agreement with our theoretical findings, the dense network is not able to fully learn the compositional output mapping while still maintaining low generalization error. By learning the non-compositional output mapping the network's 's hidden layer will become worse for generalization, even for the learned compositional output mapping. In contrast, the split network architecture sees generalization gap and maintains a near-zero test error from early on in the training. Thus, it is clear that the benefit of using the split network architecture is that it avoids the conflict its hidden layers from learning to accommodate both the compositional output and non composiosiii output mappings.
30

---

Published as a conference paper at ICLR 2023
Conv(9x27)
Conv(7x21)
Conv(5x15)
Flatten
Dense
5
84
20
38
24
32
32
10
1030
7680
Figure 15: Dense network architecture trained to perform the CMNIST classification task.
Conv(9x27)
Conv(7x21)
Conv(5x15)
Flatten
Dense
58
38
28
20
14
16
10
16
5 5
3840
Conv(9x27)
Conv(7x21)
Conv(5x15)
Flatten
Dense
84
28
58
24
20
16
16
10
1000
3840
Figure 16: Split network architecture trained to perform the CMNIST classification task.
31


Reviews:
[{"review_id": "cIG5FfSaZ_w", "reviewer": "Reviewer_83KP", "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": "The paper proposes a theoretical framework for studying systematic generalization that considers the relationship between the structure in the dataset and the neural network architecture used to learn its input-output mapping. It defines two kinds of input/output features, either combinatorial features that are binary values {-1, 1} values, or non-combinatorial features that map all combinatorial features to one large 2^n one-hot vector according to the binary string. The output corresponding to the input is defined as a random subset of the combinatorial features and the non-combinatorial features. In essence the task is to learn the identity function where the subset of features is unknown apriori, where both input and output space contain redundant representations of the same information (the one-hot vector exactly identifies the combinatorial features in the input).\n\nGiven this description of the input-output X, Y matrices, they define systematic generalization as leveraging a low-rank substructure of the correlation matrix YX^t. They then proceed to provide the optimization dynamics for deep linear networks using gradient flow type of analysis, and show how the dynamics depend on the singular values of the correlation matrices YX^t and XX^t, for which they provide an exact closed form description relating the singular values to the number of feature types the dataset is constructed of. Using these training dynamics, they proceed showing how the correlation between different input-output splits changes during training (combinatorial to combinatorial feature, combinatorial to non-combinatorial, etc.), and come to the conclusion that dense networks cannot learn a systematic mapping between combinatorial features (i.e., that does not depend on the non-combinatorial inputs). However, when defining a simplified form of a neural module network, where the network completely separates the handling of the two kinds of features, then the network is able to learn the systematic mapping. Finally, the authors propose a simple empirical demonstration of these ideas in the form of predicting 3 MNIST digits, where the authors consider two cases, where the goal is to predict the 1000 combinations as 1000 classes or as 3 separate 10 class problems. The authors test this setup both for the dense case as well as for the split-network case where networks process each digit separately. The experiments show a clear benefit to learning problems when they are presented in a decomposable fashion, both for the input-output representation and for the chosen architecture.", "summary_of_the_review": "In its current state, the submission is a bit below the threshold for acceptance. It has severe clarity issues that obscure its theoretical contributions, though I believe these could be corrected with a revision.\n", "strength_and_weaknesses": "Strengths:\n\n* The topic is of significant importance to the community. Many works have tackle this curcial topic of decomposable vs \"end to end\" learning, or systematic generalization as this paper calls it, and it is still an area where our understanding is lacking. Prior works have used more restrictive analysis, which this work (based on the recent development of gradient flow analysis) alleviates.\n\n* The paper contains many intermediate results that could be of independent interest for further investigating this topic.\n\nWeaknesses:\n\n* The paper is too dense and might be better served as a journal paper without a strict page limit. Most of the theoretical analysis is demoted to the appendices, and just reading the body of the paper can be very confusing. Some sections end without any point or context, for example, the training dynamics solely discuss the dynamics of the singular values, but they should've mentioned first why we care about the singular values (discussed in the next section), and how the asymptotic solution converges to the correct function for predicting Y given X (It's possible to show this with some basic linear algebra, but it's never mentioned). Alternatively, the authors should consider removing and simplifying its various sections, while providing proof sketches for the analysis. Even the problem setup is hard to understand and there are many things that are left poorly described or explained, e.g., what is the difference between the various non-combinatorial features (aren't they all the same identity matrices?)? How are the subset of the combinatorial features sampled, and how does this distribution affect the results? Does the number of non-combinatorial output features depend on the number of combinatorial output features?\n\n* The basic setup of the paper seems needlessly intricate. As I see it, this is simply the problem of learning the identity function, where we are given \"side information\" on the *preferred* binary representation of the input, and you examine how these input-outputs are represented and the relation to the architecture. The extra copies of the non-combinatorial features, or the subset selection seem like complications that don't really add anything to the discussion. Moreover, I think that there is some subtlety that the authors need to discuss more carefully. Namely, in their theoretical setup they merely consider learning the identity (though it is not presented as such), but simple random linear networks would \"learn\" such mapping over the \"challenging\" one-hot case immediately -- specifically, if W_1 is normally distributed with 1/sqrt(d) standard deviation, where d is the input dimension, and W_2 is constrained s.t. W_2 = W_1^T, then W_1 W_2 is approximately the identity even with the number of hidden units is as low as log(d). In other words, a randomly initialized network (not that far from the conventional initialization scheme) could approximately solve this case.\n\n* The paper does not cite or discuss highly related prior works. As mentioned above, there is not much difference between the topic of \"systematic generalization\" / compositionality to the slightly \"older\" (in ML terms) topic of \"decomposability vs end-to-end learning\" that has been studied by others (e.g., [1, 2, 3]). In fact, a very similar setup and experiment has been proposed in [2], and analysed both theoretically and empirically, albeit using a different analysis and a more limiting set of assumptions. A thorough discussion of these works is missing.\n\n[1] - Shalev-Shwartz et al., On the Sample Complexity of End-to-end Training vs. Semantic Abstraction Training, arXiv preprint arXiv:1604.06915, 2016.\n\n[2] - Shalev-Shwartz et al., Failures of Gradient-Based Deep Learning, ICML 2017.\n\n[3] - Wies et al., Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks, arXiv preprint arXiv:2204.02892, 2022. (Given it's a relative new preprint I don't expect it to be cited, but nevertheless I place it here for context).", "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": "aM_BcyHxgY", "reviewer": "Reviewer_rTdC", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper studies systematic generalization and the extent to which modular networks are better at learning systematic mappings relative to non-systematic mappings. Leveraging prior results on deep linear networks, the authors demonstrate that while non-modular networks learn a combined systematic and non-systematic mapping, a partitioned network can be biased towards learning a systematic mapping. Finally, the authors demonstrate that modularity enhances generalization on the CMNIST task.", "summary_of_the_review": "Overall, the paper makes a novel contribution to the field of systematic generalization by mathematically formulating systematicity, and showing theoretically and empirically a link between modularity and systematicity. I believe this paper can be a strong contribution to the field.", "strength_and_weaknesses": "**Strengths**\nThe paper is quite original. It provides a mathematical formalization of systematicity which to my knowledge is the first of its kind. Moreover, it demonstrates theoretically that modularity enhances the learning of systematic mappings in deep linear networks. Finally, the authors extend the results empirically to nonlinear networks, which boosts its significance. Overall, the paper appears very relevant to the field of systematic generalization.\n\n**Weaknesses**\nThe theoretical results are understandably limited to deep linear networks on simple datasets. However, the authors may wish to expand on how the definition of systematicity (3.1) could be interpreted for more complex datasets beyond the one presented in section 3. Similarly, the authors may wish to further discuss what the mapping partitions in section 5 could correspond to in more complex datasets.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "G8WZzdqMKzE", "reviewer": "Reviewer_tTiF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper works on expanding the exact training dynamics analysis of Saxe et al 2019, which considers interrelated semantic groupings, to also cover systematic behavior. For this analysis, they consider the effect of combinatorial behavior in the dataset on the resulting gradient dynamics. In particular, they consider how a deep linear model without internal modular structure compares to one with modular structure in its trajectories. The result is an attempt to precisely characterize the importance of implicitly modular network structure in systematic generalization.\n", "summary_of_the_review": "Because of the lack of clarity around the intuitions underlying the math, I don’t feel confident assessing the correctness of the paper. This is reflected in my confidence score, although I find the concepts and the general approach of the paper very exciting so my score reflects both the promising concept and the need for grounding and intuition.\n\n**After discussion:**\n\nI think I agree with reviewer 83KP that this would be better served by a journal where the authors could fully explain their work within the main body of the paper. I have raised my score from 5 to 6 in response to the authors' attempts to clarify the writing, but I just think that there is a ceiling on how good this paper can get with only nine pages. The work here is impressive, and I would rather see it published in a form that serves it well.", "strength_and_weaknesses": "Strengths:\n- The idea here is really exciting to me. I would love to see more of this kind of exact analytic result around compositional behavior. I remember originally reading Saxe 2019 and wondering how it would interact with compositional or systematic behavior, and this approach seems like a really solid attempt at that.\n- A number of steps taken to formalize modularity and systematicity, and the techniques for analysis that result, are innovative and likely to be useful in future work. In particular, I appreciate the use of the compositional properties of the dataset as a parameter when calculating gradient trajectories.\n- The authors do test whether the predictions theoretically made in the linear setting also apply in a nonlinear setting.\n- “For example, a module with no hidden layer connections to the non-compositional output components is learning on a dataset with ky = 0.” This is such a clean way of formalizing modularity!\n- Again, I want to restate the serious potential of the formalisms that they offer and the techniques that they are using in their analysis, even if I think their presentation definitely needs work and the definitions might need some refinement.\n\nWeaknesses:\n- The theoretical results are only in the linear setting. I think that they might still be really valuable as a starting point for understanding more realistic networks, but it’s certainly a limitation in this work, and it’s not obvious to me how future work might adapt these methods, given their reliance on the linearity of module interaction. Although there are empirical results in a nonlinear setting that, given that it is only MNIST, these interactions are likely to be more linear than they would be in a network that trained for a longer period of time, so they might align better with the predictions made in the theoretical setting than a modern network would.\n- “Neither implicit biases in learning dynamics, nor all but the most stringent modularity, caused networks to exploit compositional sub-structure in the data.” — again I’m not sure whether this is going to apply outside of these relatively low resource, somewhat linear, empirical settings.\n- I often struggled to follow the intuitions behind the definitions. Examples of dataset that are combinatorial only in the input or only in the output, and ones that are combinatorial in both input and output, would have helped a lot with this. Could you give me some examples now? I’m really still stuck on the intuitions behind some of these definitions.\n- I’m not even entirely clear on the intuition of the difference between the combinatorial and non combinatorial features, that could also really do with an example.\n- Likewise, it was hard for me to grasp the intuitions yielded by the trajectory results (eq 5-9). What are the implications in terms of data efficiency? Let’s assume that most readers are not particularly effective at simulating and comparing function curves in their heads. All we have to go on is Fig 2, and it’s clear something is going on there but it’s a lot harder to understand what it is that you want me to take away.\n- In general, I would really like to see examples of intuitions. Using the inspiration of Saxe 2019 as an example, there are running examples of specific hierarchical semantic classes throughout the text. This work would be greatly supported by an equivalent running example of compositional data of varying sorts.\n- In definition 3.1, it’s specified that systematic generalization is only present if it “facilitates generalization from fewer training examples”. However, the results give in don’t seem to have anything to do with data scarcity, so I’m not sure how they link into this part of the definition. Could you spell out the implications in particular of these results in figure 2 with respect to the data efficiency alluded to in definition 3.1?\n- I think that you really need to be testing generalization behavior or the amount of data required. In particular, you should be looking at splits that constrain the combinations exposed during training, as is typical in systematicity research.\n\nQuestions and minor issues:\n- Are the rules for each of these datasets randomly generated?\n- Without a more solid intuition about your definitions, it’s hard for me to say whether 3.1 would apply to behavior I wouldn’t think of as systematic personally. For example, if the matrix is a sum of the (non combinatorial?) “true” data and a noise matrix formed the covariance matrix, would that end up fitting into this definition? It doesn’t seem that effectively representing the underlying true data is a systematic behavior, but it seems like it might fit into this definition.\n- “it is possible to have a near infinite number of resultant combinations” — really?\n- Figure 3: There might be some notational inconsistency here. Previously, only the asymptotic bound was defined with $\\pi^{ss}$, and I don’t think I’ve seen this particular variable name show up already.\n- “To do this we calculate the Frobenius norm of the network’s mapping between different subsets of input and output components.” This needs a much more clear explanation of what form the mapping takes. What are you defining as a mapping?\n- I really don’t like how you index figure references! Every time I see “Figure 3b)” I cringe at the unmatched parenthesis.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "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: Accept: poster