Improving Compositional Generalization using Iterated Learning and Simplicial Embeddings
Authors: Yi Ren
Samuel Lavoie
Mikhail Galkin
Danica J. Sutherland
Aaron Courville
Venue: NeurIPS 2023 poster (2023)
Keywords: compositional generalization
systematic generalization
iterated learning
representation learning
graph neural networks

Abstract: Compositional generalization, the ability of an agent to generalize to unseen combinations of latent factors, is easy for humans but hard for deep neural networks. A line of research in cognitive science has hypothesized a process, "iterated learning," to help explain how human language developed this ability; the theory rests on simultaneous pressures towards compressibility (when an ignorant agent learns from an informed one) and expressivity (when it uses the representation for downstream tasks). Inspired by this process, we propose to improve the compositional generalization of deep networks by using iterated learning on models with simplicial embeddings, which can approximately discretize representations. This approach is further motivated by an analysis of compositionality based on Kolmogorov complexity. We show that this combination of changes improves compositional generalization over other approaches, demonstrating these improvements both on vision tasks with well-understood latent factors and on real molecular graph prediction tasks where the latent structure is unknown.

Improving Compositional Generalization using Iterated Learning and Simplicial Embeddings
Yi Ren
Samuel Lavoie Université de Montréal & Mila samuel llaoiie. 1aw.ii..mmmailll....aa.......... com
University of British Columbia" renyi. joshua@gmail com
Mikhail Galkin
Danica J. Sutherland University of British Columbia & Amii dsuth0cs culeccs.ubb.co ca
Intel AI Lab
mikhail mithaill.eallki@iinee..comm
Aaron Courville
Université de Montréal & Mila aaron. wow.ooollvlleemaiii.. com
Abstract
Compositional generalization, the ability of agent to generalize to com- binations of latent factors, is easy for humans but hard for deep neural networks. A line of research in cognitive science has hypothesized a process, "iterated learning," to help explain how human language developed this ability; the theory rests on si- multaneous pressures towards compressibility (when an ignorant agent learns from an informed one) and expressivity (when uses the representation for downstream tasks). Inspired by this process, we propose improve the compositional gener- alization of deep networks by using iterated learning on models with simplicial embeddings, which can approximately discretize representations. This approach is further motivated by an analysis of compositionality based on Kolmogorov complexity. We show that this combination of changes improves compositional generalization over other approaches, demonstrating these improvements both on vision tasks with well-understood latent factors and on real molecular graph prediction tasks where the latent structure is unknown.
Introduction
Deep neural networks have shown an amazing ability to generalize new samples on domains where they have been extensively trained, approaching or surpassing human performance on tasks including image classification [62]. Go [70], reading comprehension [13], and more. A growing body of literature, however, demonstrates that some tasks that be easily solved by a human can be hard for deep models. One important such problem is compositional generalization ([18), comp-gen for short). For example, Schott al. [65] study canually-createe vision datasets where the true generating factors are known, and demonstrate that a wide variety of current representation learning methods struggle to learn the underlying mechanism. To achieve true "artificially intelligent" methods that succeed at a variety of difficult tasks, it seems necessary to demonstrate compositional generalization. One contribution of this paper to lay compositional generalization, and argue that most currently-common training methods fall short.
framework towards understanding and improving
Work done in part during an internship at Mila.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In wondering how deep networks can learn to compositionally generalize, we might naturally ask: how did humans achieve such generalization? Or, as particular case, how did human languages evolve components (typically, words) that can systematically combine to form new concepts? This has been a long-standing question in cognitive science and evolutionary linguistics. One promising hypothesis is known as iterated learning (IL., procedure simulating cultural language evolution [41]. Aspects of this proposal are supported by lab experiments [42]. a Bayesian model [7], the behavior of neural networks in simple emergent communication task [60], and real tasks like machine translation [50] and visual question answering [76].
To link the study in cognitive science and deep learning, we first analyze the necessary properties of representations in order to generalize well compositionally. By linking the compositionality and the Kolmogorov complexity, we find iteratively resetting and relearning the representations can introduce compressibility pressure to the representations, which also the key to the success of iterated learning. To apply iterated learning in general representation learning problem, we propose to split the network into a backhone and a task head, and discretize the representation the end of the backbone using simplicial embeddings (SEM. [45]). This scheme is more practical than LSTM [34] encoders previously used for neural iterated learning [60]. We observe in various controlled vision domains that SEM-IL can enhance compositional generalization by aligning learned representations to ground-trui truth generating factors. The proposed method also enhances downstream performance on molecular graph property prediction tasks, where the generating process is less clear-cut.
2 Compositional Generalization
Generalization is lonn-itanding topic in machine learning. The traditional notion of (in-dittibuttion) generalization assumes that training and test samples come from the same distribution, but this is insufficient for many tasks: we expect a well-trained model to generalize to some novel scenarios that are unseen during training. One version of this is compositional generulization (comp-gen) [17], which requires the model to perform well on novel combinations of semantic concepts.
2.1 Data mata--gnerating assumption and problem definition
Any type of generalization requires some "shared rules" between training and test distributions. We hence assume simple data-generating process that both training and test data samples obey. In Figure 1, the semantic generating factors, also known as latent variables, are divided into two groups: the task-relevant factors (or semantic generating factors) G [Gi,.... Gm]. and task-irrelevant (or noise) factors O. This division depends on our understanding of the task; for example, if we only want to predict the digit identity of an image in the represents the digit identity. All the other generating factors such as color, stroke, angle, and possible noise are merged into O. If we want predict a function that depends on both identity and color, c.g. identifying blue even numbers, we could have G = |G1, G2) with G1 the identity and G2 the color.
dataset [3], then m and G1
Each input sample E X is determined by deterministic function GenX O). The task label(s) y E y only depend on the factors G and possible independent noise according to the deterministic function GenY(G, e). Note (x, O) .. (y,e) G, and that O, G, and are independent. The data- generating distribution P(x, y) is determined by the latent distributions P(G) and P(O). along with the GenX and GenYY We assume GenX and Gen' are fixed across environments (the "rules of production" are consistent), while P()) and P(O) might change between training and test.²
For compositional generalization, wish to model the problem of generalizing new combinations of previously seen attributes: understanding "red circle" based on having seen "red square" and "blue circle." Thus, may assume that the supports of P(G) are nve-overlgp between train and test. (If this assumption is not true, it only makes the problem easier.) In summary, our goal is to find an algorithm A such that, when trained on dataset Devain Pn Pirasn A achieves small test risk R P (A(Dtrain)) )). Here Perain and Ptest should satisfy these conditions:
* Ptrain and Prest have G, O, c jointly independent, and x = GenX(G, O). y GenY(G, c).
GenX and Gen' are the same deterministic functions for Perain and Ptest-
*
In challenging cases, we may have supp Prrain (G) S/sp/uuuppppoo. PPtese (G) 0.
This differs from the classical setting of covariate shift: P(y x) might change due to the shift in P(G).

---

Stage
Cononna
Eoooorph Wiection
Ganx(o.
Gent(G, c)
Stage II!
Casa Crraaggreeatc
HiG30) - by Plelk)) -
x only has nén. a (xpectiont
sur ther sinatuns can dffinent
X
Stage 1I
R(GG))
Hon lorg
nDK
7.
((R.))
baper modd
Stage
cantanns iruuficaent ric. about
R(GR)
(2). Data generating assumption
(bl. Ladder of com postiiotiinallt
Figure I: Left: the data-generating assumption and typical representation learning method (in red). We use the model (x) x) for downstream predictions. Right: the ladder of compositionality stating the requirements of z using the entropy-related measurements; see Appendix A for more.
2.2 Representationl Learning and Ladder of Compositionality
For compositional generalization, we expect that the model must extract atomic semantic features from the training data, and systematically re-combine them in procedure akin how the data is generated [41]. We thus consider a typical representation learning framework, which resembles the inverse of the data generation process (Figure (a), bottom). We a backbone h X 2 to convert the input signal x into a representation z, and task head 2 y to solve the given task based on that representation The prediction of the model is y (g (x).
Intuitively, we would like our learned z to uncover the hidden G, and g(z) to recover GenY(G, e). We thus analyze how the relationship between and G influences the model's generalization capability, building off principles such as information bottleneck [74]. Inspired by the "ladder of causation" " [55], propose "ladder of compositionality" in Figure 1(b), which outlining series of conditions and G. We hypothesize that comp gen roughly requires reaching the highest rung of that ladder:
To generalize compositionally, the learned z should capture exactly the information in G and nothing more (G to z should be a bijection), and moreover it should preserve the "structure" of G (i.e. the mapping from
Hypothesis 1.
should be an isomorphism).
More this hypothesis, the ladder, and relationship to models of disentanglement [32] discussed in Appendix A. In short, we find that a model trained using common learning methods relying on mutual information between input and supervision y cannot reliably reach the final stage of the ladder - it is necessary to seek other inductive biases order to generalize compositionally.
3 Compressibility pressure and Compositional mapping
From the analysis above, we need to find other inductive biases to obtain compositional mappings. Inspired by how compositionality emerges in human language," we speculate that the compressibility pressure is the key. Note that this pressure does not refer to compressing information from x to z (as in Stage III does), but whether mapping can be expressed in compact way reusing common rules. In this section, we will first link compressibility pressure to Kolmogorov complexity by defining different mappings using group theory. As the Kolmogorov complexity is hard to compute, making explicit regularization dificult, we propose to implicitly regularize via iterated learning. a procedure in cognitive science proposed increase compositionality in human-like language.
3.1 Compositional mappings have lower Kolmogorov complexity
From Occam's razor, we know efficient and effective mappings are more likely to capture the ground truth generating mechanism of the data, and hence generalize better. The efficiency is determined by how compressed the mapping is, which can also measured by Kolmogorov complexity [47, 71].
Human languages are examples of compositional mapping [35]: words are composed of combinations of reusable morphemes, and those words in rules. These properties make our language unique among natural communication systems and enable humans to convey an open-ended set of messages in compositional way [42]. Researchers in cognitive science and evolutionary linguistics have proposed many explanations for the origin of this property; one persuasive method for simulating is iterated learning [41].
combined to form complex sentences following specific stable
3

---

To build link between compositionality and Kolmogorov complexity, we can first describe different bijections between and G using group theory, and then use the description length to compare the complexity of a typical element. Specifically, assuming Z E Z. G E 9 and |2] = [9] the space of all bijections between Z and is an isomorphism of symmetric group Sig.- If G [Gi,... Gm] and each Gm has e different possible values, [9] vt For clarity in the analysis, we assume also has the same shape. Then, any bijection between and G can be represented by an element in S.m.
The space of compositional mapping, which is subset of all bijections, has more constraints. Recall how a compositional mapping is generated (see Appendix A.4 for more details): we first select 2; for each Gj in non-overlapping way. Such process can be represented by an element in S.. After that, we will assign different "words" for each 2;, which can be represented by an element in S,, As have different 2,, this procedure will be repeated m times. In summary, any compositional mapping can be represented by an element in the group S x S E S,m, where x is the semidirect product in group theory. The cardinality of S.m is significantly larger than S S., and so randomly selected bijection is unlikely to be compositional. Thus
Proposition (Informal), For m, G 2 2, among all bijections, any compositional mapping has much lower Kolmogorov complexity than a rypical non-compositional mapping.
We prove this by constructing descriptive protocols for each bijection. As compositional mapping has more reused rules, its description length can be smaller (see Appendix B.1 for more details).
3.2 Compressibility pressure is amplified in iterated learning
Now, our target is finding bijections with higher compositionality and lower Kolmogorov complexity, which are both non-trivial. Because the ground truth G is usually inaccessible and the Kolmogorov complexity is hard to calculate. Fortunately, researchers find that human language also evolved to become more compositional without knowing G. Authors of [42] hypothesize that the compressibility pressure, which exists when an innocent agent (e.g.. a child) learns from an informed agent (e.g., an adult), plays an important role. Such pressure is reinforced and amplified when the human community repeats this learning fashion for multiple generations.
However, the aforementioned hypothesis assumes that simplicity bias is inborn in the human cognition system. Will deep neural agents also have similar preferences during training? The answer is yes. By analyzing an overparameterized model simple supervised learning problem, we can strictly prove that repeatedly introducing new agents to learn from the old agent (then this informed agent becomes the old agent for the next generation) can exert non-trivial regularizing effect on the number of "active bases" of the learned mapping. Restricting the number of active bases encourages the model to reuse the learned rules. In other words, this regularization effect favors mappings with lower Kolmogorov complexity. which is exactly what we expect for compositional generalization. Due to the space limits, we left the formulation and proof of this problem in Appendix B.2.
3.3 Complete the proposed solution
We thus expect that iteratively resetting and relearning can amplify the compressibility pressure, which helps to reach the final rung of the ladder from the third. Before that, need another pressure to reach third rung (i.e., ensure a bijection between Z and G). Expressivity pressure, constraining the learned mapping to be capable enough to accomplish the downstream tasks, is what we need.
The complete iterated learning hypothesis of Kirby et al. [42] claims that the compositional map- ping emerges under the interaction between the compressibility pressure (i.e., efficiency) and the expressivity pressure (i.c., effectiveness). Inspired by this, we propose to train a model in generations consisting of two phases. At the t-th generation, we first train the backbone h in an imitation phase, where a student hy learns to imitate Z sampled from a teacher hi" As analyzed above, iteratively doing will amplify the compressibility pressure. Then, in the following interaction phase, the model 9t o hā follows standard downstream training to predict y. The task head 9r is randomly initialized and fine-tuned together with the backbone in this phase. By accomplishing this phase, the expressivity pressure is introduced. The fine-tuned backbone hā then becomes the teacher h?T, for the next generation, and we repeat, illustrated in Figure 2 and Algorithm 1.
Another problem with applying iterated learning to deep neural networks how to create the discrete message, i.c., Discretization is not necessary: for example, the imitation phase could use La loss to

---

uumbaar
Apent
Imiitton phaner
Teacher Proeent
SEM bottleneck
Ceullogta Rea)
ecomrall
Agent
Student
SEM
Tnghs
Z
Intereed on phase
Agene h+31
Baskacnn
SPM
FC
leaming
Ibi. Intagration
lcarning
Figure 2: An illustration of iterated learning and SEM layer design.
match student's continuous representations the teacher's. We find greatly improved performance with our discretization scheme, however, due to much-increasee compressibility pressure. is also possible [60] use e.g. an LSTM encoder at the end of hxx) produce discrete Z, and an LSTM decoder at the start of g (z). The interaction phase is then not directly differentiable; though many estimator options exist 16, 39, 78], training tends to be difficult due high bias and/or variance.
Instead, we consider a simplicial embedding layer (SEM, [45]), which has proven effective on many self-supervised learning tasks. As illustrated in Figure 2(c), dense representation h (the output of the original backbone) is linearly transformed into m vectors 2, E IR". Then we apply a separate softmax with temperature each 2; yielding which are, if the temperature not too high, approximately sparse; the 2; are then concatenated to long vector z. The overall process
e
2 Softmax, (21)
R
E ER
(1)
k= BaiR/T
By using an encoder with a final SEM layer, we obtain an approximately-sparee z. In the imitation phase, we generate discrete pseudo-labels by sampling from the categorical distribution defined by each 2,, then use cross-entropy loss so that the student is effectively doing multi-label classification to reconstruct the teacher's ' representations. In the imitation phase, the task head operates directly on the long vector The full model g o is differentiable, so we can use any standard task loss. Pseudocode for the proposed method, SEM-IL, is in the appendix (Algorithm 1).
Analysis on Controlled Vision Datasets
We will first verify the effectiveness of the proposed SEM-IL method on controlled vision datasets, where the ground truth G is accessible. Thus, we can directly observe how z gradually becomes more similar to G, and how the compressibility and expressivity pressures affect the training process. In this section, we consider a regression task on 3dShapes [9], where recovering and recombining the generating factors is necessary for systematic generalization. The detailed experimental settings and results on additional similar datasets, dSprites [52] and MP13D-real [23], are given in Appendix C.
4.1 The Effectiveness of SEM-IL
Better comp-gen performance We first show the effectiveness of the proposed method using results on 3dShapes, containing images of objects with various colors, sizes, and orientations against various backgrounds. Here G numerically encodes floor hue, wall hue, object hue, and object scale into discrete values, and the goal to recover a particular linear function that G. (Results for simple nonlinear function were comparable.)
We compare five algorithms:
Bascline: directly train a ResNet18 [31] on the downstream task.
SEM-only: insert an SEM layer to the baseline model.
IL-only: train a baseline model with Algorithm 1, using MSE loss during imitation.
SEM-IL:: train an SEM model with Algorithm
Given-G: train an SEM model to reproduce the true (which would not be known in practice), then fine-tune on the downstream task.
5

---

Tuiring formencce
performance
With SEM
bustleneck
10F
Deceline
10a
Danaline SEN-only
0.34
10-1
SEX0-enty
L-anty
Il-ony
Topetogical similatty
198
10nd
10
SEN-L
Givan-C
0.20
0.30
0.28
10a4
0.10
Basstin
5E5VL
Iuorty
0
500
1000
1500
2000
500
1000
1500
2000
10000
1.00
2000
500
1000
2500
2000
Traising spochs
Thaining epachs
Thaining epachs
Training epochs
Figure 3: Left: compositional generalization performance similarity for II. and non-Il. methods. Note the values of p in the two panels are not comparable, as the structure of in the two settings (with or without SEM) is different.
regression task. Right: topological
In the first panel of Figure 3, we see that the baseline and SEM-only models perform similarly on the training set; IL-based methods periodically increase in error at the beginning of each generation, but are eventually only slightly worse than the baselines on training data. On the test set, however, evaluating compositional generalization by using values of G which did not appear in training. SEM-IL brings significant improvement compared with other methods. Using only SEM or only IL gives no improvement over the baseline, however; it is only their combination which helps, as we will discuss further shortly. The (unrealistic) oracle method Given-G is unsurprisingly the best, since having& Z similar to indeed helpful for this task.
How Z evolves during learning To see if better generalization ability is indeed achieved by finding z that resembles the structure of G, we check their topological similarity*
p(z, fz. G) Corr (dz(z)), z(0)), do (G (
where de and de are distance metrics, z is the predicted representation of x(*), and G is the corresponding ground-truth generating factors. This measurement is widely applied to evaluate the compositionality of the mappings in cognitive science [8] and emergent communication [60]. Following existing works, we use the Hamming distance for and discretized in SEM-based methods, and cosine distance for continuous in non- Non-SEM methods. We expect h(x) to map x with similar to close z, and dissimilar x to distant Z, so that p(z, G) will be high.
The third panel of Figure 3 shows that the SEM-only model quickly reaches a plateau after 200 epochs and then slowly decreases, while SEM-IL, after briefly stalling at the same point, continues to increase to a notably higher topological similarity. In the last panel, however, the IL-only method doesn't 't improve p over the baseline: it seems both parts are needed.
4.2 Discretized Representation is Beneficial for the Imitation Phase of IL
To explain why SEM and II. cooperate well, we need to look deeper into how the compressibility pressure influences the learning of representations. This pressure induced by iterated learning, which helps us to find mappings with lower Kolmogorov complexity, leads to representations that are more compositional and systematic [42]. However, in prior works, these mappings were only considered in conjunction with some discretized representation [54, 60]. While IL could be used with continuous representation during the imitation phase, similar born-again networks [19], we found that our algorithm benefits a lot from the discretized representations.
To get a clear picture of why discretized representations are so important, we divide h(() into m sub- mappings (x), which map x to 2 E [0. 1ja. We can understand each ž; as a categorical distribution over different possible values. As such, during training, the model learns discrete features of the dataset and assigns confidence about each feature for every sample. The neural network will tend to more quickly learn simpler mappings [5, 24], and will assign higher confidence according the mapping it has learned. In other words, if a mapping does not align well with G. it is more likely to give idiosyncratic learned 2, and will lead to low confidence for most samples. On the contrary. z belonging to compositional mappings will be more general, and on average tend towards higher confidence.
'This measure is also known as the distance correlation [72]; it is special case of the Independence Critierion (HSIC, (25]) for particular choice of kernel based on d, and de [66].

---

High confidence
Intermed monddence
mididence
Leaming soreet couudeee
Prod cina probbblig
1.3
consitmen dffeeen:
5.0
320
2020
2000
2202
0.0
502
1003
2000
0.5
500
3000 1530
2000
Taininn
epoccss
Figure 4: First panel: correlation between teacher's ' confidence and student's learning speed for each (x, Z.); & the prediction of the 1-th attribute in imitation phase. "Consistent" means the student makes the same prediction as the teacher. Other panels: learning curves of the student's 's predictions.
The imitation phase reinforces this bias when the new student learns from the sampled pseudo labels g; from the teacher's prediction 2, As such, confident predictions, which are more likely belong to the compositional mappings, will be learned faster (and harder to forget) by the student. On the contrary, for less confident features where P(z, x) flat, g; could change across epochs. This makes it hard for the student to remember any related (x, g, to build a stable mapping between "red" and 21 if the teacher communicates ("red square", .g = =), ("red square", 81 1), ("red square". 81 2) in three consecutive epochs.
). For example, student will be reluctant
Furthermore, using the sampled pseudo-labels can help the student align the learned (x, g.) better. Assume during training, the student already remembers some pairs like ("blue circle", 81 0), ("blue square". g1 = 0), ("blue star", g 0), but the teacher is not confident in ("blue apple" g1). perhaps because apples are rarely blue. Following the analysis above, as P(ž1 blue apple) is flat, the teacher may generate gi * significant portion of the time. However, if the teacher happens to generate g = 0 at some point, the student would learn ("blue apple" gı = 0) faster than those with 8 * 0, because aligns well with the other information stored in the student network. The parameter updates caused by the learning of other ("blue [shape]", g1 0) will also promote the learning of ("blue apple", 81 = 0), similar to how "noisy" labels are fixed as described by [61].
To support the explanations above, we can first observe the correlation between the teacher's con- fidence and the model's learning speed for (x, g.). Specificallyy, for each x. the teacher makes m predictions with the corresponding categorical distribution E;, i E [m]] For each (x, a),, the confidence measured by the negative logarithm of the teacher's 's predicted probability, - log[ where ) E argmax, (Z:lg- The learning speed of (x. g,) is measured by the integral of the student's prediction with training time f, i.e., (&. where j is the value provided by the teacher and (t) is student's prediction time As illustrated in the first panel of Figure 4, the (x, g,) with higher confidence are usually learned faster by the student.
We also provide the learning curves of (x. g;) with high/intermediate/loow confidence (each with 10 samples) in the other three panels of the figure. The curves for high-confidence samples all converge to [()] less than 0.3. This means the student might make predictions that are different from the teacher's supervision. By highlighting such low-confidence (x. g,) pairs in the scatter plot, we find they are all low-confidence samples. Another interesting observation from the high-con cogghccnfieeece curves is that some (x, g,) pairs are not remembered by the student the first generation: they emerge some point and gradually dominate as the training goes on. This phenomenon matches our analysis of how the sampled peudo-labees help the student align (x. g,) to its knowledge well. To further support this explanation, Appendix C shows that performance is substantially harmed by taking pseudo-labed from the argmax, rather than sampling from ž,
value 1 while those for low-confidence predictions could converge
To recap, this subsection provided an explanation (along with some supporting evidence) for why the combination of SEM and IL is important, based the perspective of sample difficulty, which believe to be a significant factor in the success of this algorithm.
5 Application: Molecular Property Prediction
Given the success in controlled vision examples, we now turn to a real problem where the true generative process is unknown. We focus predicting the properties of molecular graphs, for several
7

---

reasons. First, molecular graphs and their labels might follow a (chemical) procedure akin to that in Figure 1: for instance, one G; might be the existence of a specific functional group, or the number of specific atoms. Different molecular properties could then be determined by different subsets of Gs, as we desired in the compositional generalization problem. Furthermore, the generating mechanisms (GenX and GenY) should be consistent and determined by nature. Second, benchmark datasets in this community contain various types of tasks (e.g., binary classification, multi-label classification, and regression) with similar input signals: performing well on different tasks will broaden the scope of our algorithm. Furthermore, the scaffold split used by most molecular datasets corresponds well to the compositional generalization setup consider here. (We also try some more challenging splits, using structural information.) Last, learning meaningful representations that uncover the generating mechanisms of molecules is important, of practical significance, and difficult: it can potentially help predict the properties of unknown compounds, or accelerate the discovery of new compounds with specific properties, but scaling based massive datasets in recent work vision language seems more difficult. We hope our analysis can provide a new perspective on this problem.
5.1 Improvement on the Downstream Performance
Table I: Downstream performance different tasks. The numbers of AUROC and average precision are in percent form. For PCQM, we report the validation performance, as the test set is private and inaccessible. Means and standard deviations of seeds are given. Valid/test-ull means the standard train/val/test split provided by the dataset. Valid/test-half means we train the model on half of the training data which is less similar to the validation and test sets. See Appendix D for more.
Model
(AUROCT)
molpcha (Avg. Precttion
PCOM IMAE U3
Algoristm
Valid-foll
Test-full
Valid-hair
Tes-hail
Valid-iall
Valid-hull
Test-all
Valid
Buscline
1241=1114
38
7545-091
72311130 20
21.3610:25
22.3100:6
21.1310.33
20.7810.22
0.125
OCN
SEM-only
Roselines
11.00=110
81661-063
7840=00.7
75.58=100
72.17+102 1484
75:23-075
7281+232
26. 26.39
22.51+0.54 54
22.68+0.30
25 25.89
22.79:00911
21.01+0255
22.09:1002
20.60+0.37
0.118+000044
0.106=20.002
SEM--L.
84.89 0.68
79.09-067
7848-0066
74.02-0.78
28.1 +0.72
27.15-0.74
22.59-0084
21 1190--081
0.102 00,02-0.085
Raseline
81.76-10
8:39-142
1655-144 440
25.990.32
22.04:0129
20:32:0039
20.15:0-22
GIN
SEM-only
Haselines
03:05-0000
78.1-00.8
72.1-0044
14.77=1622
76.29-2006
69.75-3.100
22.70=44.94 94
26.01
23.85+0.29
25.66::0.47
22.91=0.40
22.36+00.39
21.71=0012
21. 21.50:2-0444
20.98=0.27
0.108=00:003
0.106
SEM-1..
83.32- 1.51
78.61-0.73
78.06
72.89-0.48
29.30-0.48
28.02-1161
24.41
23.89+0077
0.098 1.098-0.005
We conduct experiments on three common molecular graph property datasets: ogbg-molhit (1 binary classification task), egbg-molpcbbr ( (128 binary classification tasks), and PCQM4Mv2 (1 regres- sion task); all three come from the Open Graph Benchmark [37]. We choose two types of backbones, standard GCN [40] and GIN [80]. For the baseline experiments, we use the default hyperparameters from [37]. As the linear transform added in SEM-based method gives the model more parameters, we consider "baseline+" " to make a fair comparison: this model has an additional embedding layer, but no softmax operation. Detailed information on these datasets, backbone models, and byper-parameten is provided in Appendix D.
From Table 1, see the SEM-IL method almost always gives the best performance. Unlike in the controlled vision experiments (Figure 3), however, SEM alone can bring significant improvements in this setting. We speculate that compressibility pressure might be more significant in the interaction phase (i.e. standard training) when the generating mechanism is complex. This suggests it may be possible develop a more efficient algorithm to better impose compressibility and expressivity pressures at the same time.
5.2 Probing Learned z by Meaningful Structures
In the controlled vision examples, we know that SEM-IL not only enhances the downstream per- formance, but also provides z more similar to the ground-trutt generating factors, as seen by the improvement in topological similarity. However, as the generating mechanism is usually inaccessible in real problems, we indirectly measure the quality of z using graph probing [2]. Specifically, we first extract some meaningful substructures in a molecule using domain knowledge. For example, we can conclude whether a benzene ring exists in x by directly observing its 2D structure. With the help of the RDKit tool [44], we can generate a sequence of labels for each x, which is usually known as the "fingerprint" of molecules (denoted FP FP(x) E 10, indicating whether each specific structure exists in x). Then, we add a linear head on top of the fixed z and train it using a generated training set (x, FP(X)), x ~ D train and compare the generalization performance on the generated test set
8

---

(x. FP(x)). ~ Drest. For fair comparison, we set m 30 and v = 10 to make z and h be the same width, excluding the influence of the linear head's 's capacity.
Table 2: AUROC for graph probing based on different z; random guessing would be R
0.5.
Soi.King
Aing
CyclCyclc
Aniline
Ketone
Bieye.
Methoxy
ParaHydrax.
Pyridine
Banzene
Avg.
Init. base
0.870
0.958
0.811
0.629
0.595
0.615
0.627
0.705
0.692
0,312
0.232
SEM
0.72
0.958
0.812
0.655
0.597
0.638
0.613
0.892
0.683
0.15
0.71
Train
Baseline
0.916
0.703
0.93
on
SEM-caly
0.779
0.763
0.988
0.36
Mellbiv
SEM-II.
0.977
0.900
0.967
0.794
0815
0.869
0.965
0878
Train
Baseline
0921
0.985
0.968
0.366
0.875
0.835
0.755
0.855
0.856
03683
0.901
on
SEM-colly
0.942
0
0:981
0.888
0.916
0.854
0.921
0.888
0.897
0.800
0.926
Molpcha
SFM-II
0.40
0.988
0.982
0.910
0
0.849
0.912
0
0.912
0.981
0.931
Tram
Baseline
0.90
0.66
03322
0366
0.995
SEM-oaly
6.443
0.933
0.835
0.900
0.989
0.922
10% pchn
SFM-II
0938
0.994
0.985
0.918
0.847
0.937
0.844
0.907
0
0.927
Tram
Kascline
0.92
0.944
0.048
0.721
0.750
03689
0.325
0.758
0.782
03347
0X11
on
SEM-only
0.906
0.989
0:958
0.772
0.509
0.755
0.876
0.770
0.835
0.957
0.861
peba-Ttakk
SEM-IL
0
0.988
0,963
0.741
0,851
0.744
0.887
0.765
0.869
0.962
0.867
In the experiments, we use the validation split of molhiv as D and the test split as Diests each of which contain 4, 113 distinct molecules unseen during the training of z. The generalization performance of ten different substructures is reported in Table 2. The first block (first two rows) of the table demonstrates the performance of two types of models before training. They behave similarly across all tasks and give a higher AUROC than random guess. Then, comparing the three algorithms in each block, we see SEM-based methods consistently outperform the baseline, which supports our hypothesis well. SEM-IL outperforms SEM-only on average, but not for every task; this may be because some structures are more important to the downstream task than others.
Comparing the results across the four blocks, find that the task in the interaction phase also influences the quality of z: the z trained by molpcba is much better than those trained by molhiv. To figure out where this improvement comes from, we first molpcba to make the training sizes similar, then make the supervisory signal more similar by using only one task from molpcba. As illustrated in the last two blocks in the table, we can conelude that the complexity of the task in the interaction phase, which introduces the expressivity pressure, plays a more important role in finding better Z.
only 10% of the training samples in
Based on this observation, we can improve SEM-IL by applying more complex interaction tasks. For example, existing works on iterated learning use referential game reconstruction task in the interaction phase, which could introduce stronger expressivity pressure from a different perspective. Furthermore, [45] demonstrates that SEM works well with most contrastive learning tasks. We hope the fundamental analysis provided in this paper can shed light on why SEM and II. collaborate so well and also arouse more efficient and effective algorithms in the future.
Related Works
Iterated Learning and its Applications. Iterated learning (IL) is procedure that simulates cultural language evolution to explain how the compositionality of human language emerges [41]. In IL., the knowledge (i.e., the mapping between the input sample and its representation) is transferred between different generations, during which the compositional mappings gradually emerge and dominate under the interaction between compressibility and expressivity pressures. Inspired by this principle, there are some successful applications in symbolic games [60], visual question answering [76), machine translation [50], multi-label learning [58], reinforcement learning [54]. etc.
There are also many algorithms training a neural network for multiple generations, which could possibly support the principles proposed in iterated learning. For example, [19] proposes to iteratively distill the downstream logits from the model in the previous generation, and finally bootstrap all the models to achieve better performance on image classification task; this can be considered as an IL algorithm merging the imitation and interaction phases together. [82] proposes to re-initialize the latter layers of a network and re-train the model for multiple generations, which is similar to an II. algorithm that only re-initializes the task head. [54] extends such a reset-and-relearr training to reinforcement learning and shows that resetting brings benefits that cannot be achieved by other regularization methods such as dropout or weight decay. In the era of large language models, self- refinement in-context learning [51] and self-training-basss reinforcement learning [26] can also

---

benefit from iteratively learning from the signals generated by agents in the previous generation. We left the discussion and analysis on these more complex real systems in our future work.
Knowledge Distillation and Discrete Bottleneck. Broadly speaking, the imitation phase in SEM-II, which requires the student network to learn from the teacher, can be considered as knowledge distillation method [33]. Different from the usual setting, where the student learns from the teacher's prediction on a downstream task, we assume a generating mechanism and create a simplex space for the generating factors. By learning from the teacher in this space, we believe the compressibility pressure is stronger and is more beneficial for the compositional generalization ability.
For the discretization, there are also other possible approaches, e.g.. [28] uses an LSTM to create a discrete message space, and [48] proposes method using vector quantized bottleneck [75]. We choose SEM [45] for its simplicity and universality: it is easy to insert it into a model for different tasks. Besides, SEM has proved to be effective on self-supervised learning tasks; we extend it to classification, regression, and multi-label tasks.
Compressibility, learning dynamics, and Kolmogorov complexity Recently, with the success of large language models, the relationship between compressibility and generalization ability gradually attracted more attention [12]. Authors of [57] propose that how well model is compressed corre- sponds to the integral of the training loss curve when negative logarithmic likelihood loss is used. Although this claim assumes the model sees each training sample only once, which might not be consistent with the multiple-epochs training discussed in this paper, the principles behind this claim and our analysis are quite consistent: the mappings generalize better and are usually learned faster by the model. Furthermore, authors of [71] link the generalization ability to Kolmogorov complexity. Our analysis in Appendix B also supports this claim well. Hence we believe the evolution of the human cognition system can provide valuable insights into deep learning systems.
Graph Representation Learning. Chemistry and molecular modeling are some of the main drivers of neural graph representation learning since its emergence [21] and graph neural networks, in particular. The first theoretical and practical advancements [27, 40, 80] in the GNN literature were mostly motivated by molecular use cases. Furthermore, many standard graph benchmarks [15, 16, 37] include molecular tasks on node, edge, and graph-levels, e.g.. graph regression in ZINC and PCQM4Mv2 or molecular property prediction in ogbg-mo molhiv and ogbg-molpche datasets. Graph Transformers [14, 43, 59] exhibit significant gains over GNNs in molecular prediction tasks. Self- supervised learning (SSL) on graphs is particularly prominent in the molecular domain highlighted by the works of GNN Pre Preirrii [38], BGRL [73], and Noisy Nodes [22]. We will extend the proposed method to different models and different pretraining strategies in our future work.
7 Conclusion
In this paper, we first define the compositional generalization problem by assuming the samples in the training and test sets share the same generating mechanism while the generating factors of these two sets can have different distributions. Then, by proposing the compositionality ladder, we analyze the desired properties of the representations. By linking the compositionality, compressibility. and Kolmogorov complexity together, we find iterated learning, which is well-studied cognitive science, is beneficial for our problem. To appropriately apply iterated learning, we attach an SEM layer to the backbone model to discretize the representations. On the datasets where the true generating factors are accessible, we show that the representations learned by SEM-IL can better portray the generation factors and hence lead to better test performance. We then extend the proposed algorithm to molecular property prediction tasks and find it improves the generalization ability.
The main drawback of the current solution is the conemconu training: we must run multiple generations and some common features might be re-learned multiple times, which is inefficient. Hence a more efficient way of imposing compressibility desired.
Overall, though, our analysis and experiments show the potential of the SEM-II. framework on compositional generalization problems. We believe a better understanding of where the compress- ibility bias comes from in the context of deep learning can inspire more efficient and non-trivial IL framework designs. Clearly defining the compositional generalization problem and finding more related practical applications can also promote the development of IL-related algorithms.
10

---

References
[1] Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Jean- -hrrisoit Gagnon-Audet Yoshua Bengio, Ioannis Mitliagkas, and Irina Rish. "Invariance principle meets information bottleneck for out-of-distribution generalization." NewrlPS. Volume 34. 2021, pages
[2] Mohammad Sadegh Akhondzadeh, Vijay Lingam, and Alcksandar Bojchevski. "Probing Graph Representation." AISTATS, 2023.
[3] Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. "Invariant risk mini- mization" (2019). arXiv: 0007.22893.
[4] Hangho Bao, Li Dong. Songhao Piao, and Furu Wei. "BEiT: BERT Pre-Training of Image Transformers." " ICLR. 2022.
[5] Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Nan Rosemary Ke, Sebastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher Pal. "A Meta-Transfer Objective for Learning to Disentangle Causal Mechanisms." ICI.R 2020.
[6] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. "Estimating or propagating gradients through stochastic neurons for conditional computation" (2013). arXiv: 1308.3432.
[7] Aaron Beppu and Thomas Griffiths. "Iterated learning and the cultural ratchet." Proceedings of the Annual Meeting of the Cognitive Science Society. Volume 31. 2009.
[8] Henry Brighton and Simon Kirby. "Understanding linguistic evolution by visualizing the emergence of topographic mappings." Artificial Life 12.2 (2006), pages 229-242.
[9] Chris Burgess and Hyunjik Kim. 31) Shapes Dataset. 2018. URL: https: // github..coo com/ deepmind/ saspminnddddshhpppee shapee..
[10] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. "Emerging properties in self-supervised vision transformers." " CVPR. 2021.
[11] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. "A simple framework for contrastive learning of visual representations." JCML. 2020.
[12] Grégoire Delétang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christopher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. Language modeling is compression. 2023. arXiv: 2309. 10668.
[13] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. "BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding." NAACL-HLT. 2019, pages 4171-4186.
[14] Vijay Prakash Dwivedi and Xavier Bresson. "A generalization of transformer networks to graphs." AAAI 202/ Workshop on Deep Learning on Graphs: Methods and Applications. 2020. arxiv: 09699.
[15] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. "Benchmarking graph neural networks." Journal of Muchine Learning Research 24.43 (2023), pages 1-48.
[16] Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. "Long Range Graph Benchmark." Neural Information Processing Systems (NeurIPS 2022), Track Datasets and Benchmarks (2022).
[17] Jerry Fodor and Ernest Lepore. The compositionallty papers. Oxford University Press, 2002.
[18] Jerry Fodor and Zenon W Pylyshyn. "Connectionism and cognitive architecture: critical analysis." Cognition 28.1-2 (1988), pages 3-71.
[19] Tommaso Furlanello, Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandku- mar. "Born again neural networks." ** ICMI.. 2018. 8.
[20] Robert Geirhos, JenJJöönHHennt Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. "Shorteut learning in deep neural networks." Nature Machine Intelligence 2.11 (2020), pages 665-673.
[21] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. "Neural message passing for quantum chemistry." ICML. 2017.
[22] Jonathan Godwin, Michael Schaarschmidt, Alexander L Gaunt, Alvaro Gonzzlzz. Yulia Rubanova, Petar Veličkovié, James Kirkpatrick, and Peter Battaglia. "Simple GNN Regularisation for 3D Molecular Property Prediction and Beyond." ICLR. 2022.
11

---

[23]
Muhammad Waleed Gondal, Manuel Wuthrich, Djordje Miladinovic, Francesco Locatello, Martin Breidt, Valentin Volchkov, Joel Akpo, Olivier Bachem, Bernhard Schölkopf, and Stefan Bauer. "On the Transfer of Inductive Bias from Simulation to the Real World: a New Disentanglement Dataset." NeurlPS. 2019.
[24] Anirudh Goyal and Yoshua Bengio. "Inductive biases for deep learning of higher-level cogni- tion." Proceedings of the Royal Society A 478.2266 (2022).
[25] Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. "Measuring Statistical Dependence with Hilberr-Schmidt Norms." Algorithmic Learning Theory. 2005.
[26] Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang. Chenjie Gu, Wolfgang Macherey, Arnad Doucet, Orhan Firat, and Nando de Freitas. Reinforced Training (ReST) for Language Modeling. 2023. arXiv: 2308. 08998..
[27]
Will Hamilton, Zhitao Ying, and Jure Leskovec. "Inductive representation learning on large graphs." NeurIPS. 2017.
[28] Serhii Havrylov and Ivan Titov. "Emergence of language with multi-agent games: Learning to communicate with sequences of symbols." NeurIPS. 2017.
[29] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. "Masked autoencoders are scalable vision learners." CVPR. 2022.
[30] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. "Momentum contrast for unsupervised visual representation learning." " CVPR. 2020.
[31] Kaiming Hc, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. "Deep Residual Learning for Image Recognition." CVPR. 2016.
[32] Irina Higgins, David Amos, David Pfau, Sebastien Racaniere, Loic Matthey, Danilo Rezende, and Alexander Lerchner. "Towards a definition of disentangled representations" (2018). arXiv: 1812.02230
[33] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. "Distilling the knowledge in a neural network." 2.7 (2015). arXiv: 1503. 02531.
[34] Sepp Hochreiter and Jürgen Schmidhuber. "Long short-term memory." Neural computation
9.8 (1997), pages 1735-1780.
[35] Charles F Hockett. "The origin of speech." Scientific American 203.3 (1960), pages 88-97,
[36] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. "OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs." NeurIPS Datasets and Benchmarks Track. 2021.
[37] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. "Open graph benchmark: Datasets for machine learning on graphs." NeurlPS. 2020.
[38] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. "Strategies for Pre- Pre-training Graph Neural Networks." ICLR. 2020.
[39] Eric Jang, Shixiang Gu, and Ben Poole. "Categorical reparameterization with Gumbel-
(2016). arv::: 1611. 01144.
[40] Thomas N. Kipf and Max Welling. "Semi-Supervised Classification with Graph Convolutional
Networks." ICLR. 2017.
[41] Simon Kirby, Hannah Cornish, and Kenny Smith. "Cumulative cultural evolution in the laboratory: An experimental approach to the origins of structure in human language." PNAS 105.31 (2008), pages 10681-10686
[42] Simon Kirby, Monica Tamariz, Hannah Cornish, and Kenny Smith, "Compression and com- munication in the cultural evolution of linguistic structure." Cognition 141 (2015), pages 87-
102.
[43] Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. "Rethinking Graph Transformers with Spectral Attention." " NeurIPS. 2021.
[44] Greg Landrum et al. "Rdkit: Open-source cheminformatics software" (2016).
[45] Samuel Lavoie, Christos Tsirigotis, Max Schwarzer, Ankit Vani, Michael Noukhovitch, Kenji Kawaguchi, and Aaron Courville. "Simplicial embeddings in supe-vupe learning and downstream classification" (2022). arXiv: 2204. 00616.
12

---

[46] Bo Li, Yifei Shen, Yezhen Wang, Wenzhen Zhu, Dongsheng Li, Kurt Keutzer, and Han Zhao. "Invariant information bottleneck for domain generalization." AAAI Conference on Artificial Infelligence. 2022.
[47] Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. 4th edition. Springer, 2019.
[48] Dianbo Liu, Alex M Lamb, Kenji Kawaguchi, Anirudh Goyal, Chen Sun, Michael Curtis Mozer, and Yoshua Bengio. DDicrete-valued neural communication." NeurIPS. 2021. Ilya Loshchilov and Frank Hutter. "Decoupled Weight Decay Regularization." ICLR. 2019. Yuchen Lu, Soumye Singhal, Florian Strub, Aaron Courville, and Olivier Pietquin. "Countering language drift with seeded iterated learning." " ICMI_ 2020.
[49]
[50]
[51] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye. Yiming Yang. Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with seldafee 2023, arXiv: 2303. 17651.
[52] Loic Matthey, Irina Higgins, Demis Hassabis, and Alexander Lerchner. dSprites: Disentan- glement testing Sprites dataset. 2017. URL: https::/ggtiiii com/ deepmindddsdpppeeeeeed dataset/.
[53] Hossein Mobahi, Mehrdad Farajtabar, and Peter Bartlett. "Self-distillation amplifies regular- ization in Hilbert space." NeurIPS. Volume 33. 2020, pages 3351-3366
[54] Evgenii Nikishin, Max Schwarzer, Pierluca D' D'Oro, Pierre- Bacon, and Aaron Courville. "The primacy bias in deep reinforcement learning." ICML. 2022.
[55] Judea Pearl and Dana Mackenzie. The Book of Why: The New Science of Cause and Effect. Basic Books, 2018.
[56] Aahlad Puli, Nitish Joshi, He He, and Rajesh Ranganath. "Nuisances via Negativa: Adjusting
for Spurious Correlations via Data Augmentation" " (2022). arXiv: 2210.020000... 01302.
[57] Jack Rae. Compression for AGI. Stanford MLSys Seminar. 2023. URL: https : / www
youtube.
wwutube.cco//ttccc//.... com/watchhvvaD4TS JkeaaU.
[58] Sai Rajeswar, Pau Rodriguez, Soumye Singhal, David Vazquez, and Aaron Courville. "Multi- label iterated learning for image classification with label ambiguity." CVPR. 2022.
[59] Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. "Recipe for a General, Powerful, Scalable Graph Transformer." " NeurIPS. 2022.
[60] Yi Ren, Shangmin Guo, Matthieu Labeau, Shay B. Cohen, and Simon Kirby. "Compositional languages emerge in a neural iterated learning model." ICLR. 2020.
[61] Yi Ren, Shangmin Guo, and Danica J. Sutherland. "Better Supervisory Signals by Observing Learning Paths." ICLR. 2022.
[62] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy. Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. "ImageNet Large Scale Visual Recognition Challenge." IJCV 115.3 (2015), pages 211-252.
[63] Sandro Salsa. Partial differential equations in action: from modeling to theory. Volume 99. Springer, 2016.
[64] Bernhard Schölkopf and Alexander J Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, 2002.
[65] Lukas Schott, Julius Von Kügelgen, Frederik Träuble, Peter Vincent Gehler, Chris Russell, Matthias Bethge, Bernhard Schölkopf, Francesco Locatello, and Wieland Brendel. "Visual Representation Learning Does Not Generalize Strongly Within the Same Domain." " ICLR. 2022.
[66] Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu. "Fquivalence of distance-based and RKHS-based statistics in hypothesis testing." " The Annals of Statistics 41.5 (2013), pages 2263-2291.
[67] Yuge Shi, Imant Daunhawer. Julia E Vogt. Philip HS Torr, and Amartya Sanyal. "How robust are pre-trained models to distribution shift?" (2022). arXiv: 2206. 08871.
[68] Rui Shu, Yining Chen, Abhishek Kumar, Stefano Ermon, and Ben Poole. "Weakly Supervised Disentanglement with Guarantees." " ICLR. 2020.
[69] Ravid Shwartz-Ziv and Naftali Tishby. "Opening the black box of deep neural networks via information" (2017). arXiv: 1703. 00810.
13

---

[70] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche. Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kaichbrenner, llya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. "Mas- tering the game of Go with deep neural networks and tree search." Nature 529.7587 (2016), pages 484-489.
[71] llya Sutskever. An observation on Generalization. Simons Institute workshop on Large Lan- guage Models and Transformers. 2023. URL: https:///// /tt///smmossss//////////////...s http:/...o.ob...ee....ee.eeee edu/ talks/
www.aattkeverroppeaa--2-00 08-14-
[72] Gábor J. Székely, Maria L. Rizzo, and Nail K. Bakirov. "Measuring and testing dependence by correlation of distances." " The Annals of Statistics 35.6 (2007), pages 2769-2794
[73] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. "Large-Scall Representation Learning Graphs via Bootstrapping." ICLR. 2022.
[74] Naftali Tishby, Fernando C Pereira, and William Bialek. "The information bottleneck method." Allerton Conference on Communication, Control, and Computing. 1999. arXiv: physics/ 0004057.
[75] Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. "Neural discrete representation learning." NeurIPS, 2017.
[76] Ankit Vani, Max Schwarzer, Yuchen Lu, Feshan Dhekane, and Aaron Courville. "Iterated learning for emergent systematicity in VQA." ICLR. 2021.
[77] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and fierre-Antoine Manzagol. "Extracting and composing robust features with denoising autoencoders." ICML. 2008
[78] Ronald J Williams. "Simple statistical gradient-followin algorithms for connectionist rein- forcement learning." Reinforcement Learning (1992), pages 5-32.
[79] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. "MoleculeNet: a benchmark for molecular machine learning." Chemical Science 9.2 (2018), pages 513-530.
[80] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. "How Powerful are Graph Neural
Networks?" ICLR. 2019.
[81] Zhenlin Xu, Mare Niethammer, and Colin A Raffel. "Compositional generalization unsu- pervised compositional representation learning: A study disentanglement and emergent language." NeurIPS. 2022.
[82] Hattie Zhou, Ankit Vani, Hugo Larochelle, and Aaron Courville. "Fortuitous Forgetting in Connectionist Networks." ICLR. 2022.
[83] Jinghao Zhou, Chen Wei, Huiyu Wang, Wei Shen, Cihang Xie, Alan Yuille, and Tao Kong. "Image BERT Pre-trate Pre-training with Online Tokenizer." ICLR. 2022.
14

---

Algorithm 1: Proposed IL-SEM algorithm
Split the network into hx(x) and g(z), then add an SEM bottleneck discretize
for & = O to T gen. do
Initialize the student speaker h (x)$
#
Imitation Phase (start from the second generation)
if >>>>>>> 0 then
for 0 to Timit do
Sample batch from the training set DDrrain
Sample the pseudo labels from teacher's prediction (one-hot vectors) 8im ~ h1 (x)
Calculate the student's 's prediction [&1, .... 2m] hi (x)
Update h (-) with multi-label cross-entropy loss Lml Σ m
2i=18 8:
log 2
end for end if
Interaction Phase (regular training on the downstream task) for i 0 to Jint do
Initialize the listener 9: (z) randomly
Sample batch (x. y) from the training set Dtroin
Calculate the downstream prediction y = (ge hig (x)
Update the parameters of fi and gr to minimize the downstream loss LJ. end for
The student becomes the teacher for the next generation: h h end for
Return the last (or the best) (g: hhf)) (x) for the downstream task
A The Ladder of Compositionality
Table 3: What information contained in the ladder and their corresponding capabilities. H() is the entropy, <> means bijection, < means isomorphism bijection.
OOD-gen with
Infor.
Train acc.
ID>gen
Comp-gen
concepts
Stage I
H z) > 0
X
X
H z)
Stage II
H(z G) > 0
Stage III
Z ++ G
X
Stage IV
z G
To figure out what z we need in order to generalize well compositionally, we propose the "ladder of compositionality" in Figure 1. To justify claims, this appendix will discuss how could climb the ladder step by step by analyzing how the corresponding requirements are generated. A formal definition of the compositional mapping in terms of group theory, which is necessary for reaching the final stage of the ladder, is also provided. In short, we find only relying on the mutual information between and G (or between x and y) cannot reach the final rung of the ladder: need other inductive biases, which is the main motivation this paper.
A.1 Stage I: misses some important information in G
The learned representation would have H(G > O at this stage. As Y GenY c) and Ý g(z) are assumed to be invertible (here Y and Y are random variables), this condition can be rewritten as / (Y;;)) < (Y)) 6, Hence following the analysis in [69], model with such an encoder z = h(x) even cannot achieve high enough training performance, let alone generalizing to unseen
"In practice. we can choose randomly initialize the speaker (usually when the model is small), copy the pretrained checkpoint (when the model is large), copy the parameters of the teacher previous generations (the seed iterated learning variant mentioned in [50]).
Using the fact that H (G z) H(Y Y Y) H(Y) .).
15

---

test distributions. This condition might occur when the model underfits the training data, e.g., at the beginning of training or the model's 's capacity is too small. To make an improvement, one can increase the model size or train longer.
A.2 Stage II: z not only contains all information in G but also some in O
At this stage, the learned representation would have (G z) 0 and Hz |G) O. This means h(x) remembers additional information that G doesn't 't have, e.g., noisy information in O. From ( z) = O, we know H (Y Y)= = O and hence IY; 8)= = (Y)) Then the model would have perfect training performance and could also be able to generalize well when training and test datasets share the same distribution. However, when facing the out-o--distribution generalization problem, especially when a spurious correlation exists between some factors in O and G, the extra information learned by Z can mess the predictions up. Such phenomenon is named "short-cut learning" and is quite common in many deep-learning systems [20]. For example, if the background strongly correlates with the object in the training set (e.g.. Cow usually co-occurs with the grass while seagull usually co-occurs with the beach), the DNN then tends to rely more on these "short-cut" features (e.g., the background rather than the object) during training. If such correlations disappear or reverse the test set, the models relying on factors O cannot generalize well to a new distribution.
Making improvement- - loss based on seformatton-botttleeekk To make an improvement, the model should eliminate the task-irrelevant information much as possible. Based on this principle, authors of [74] propose to minimize the following information bottleneck equations:
max I(Z 3I X), B>0.
which means the learned should extract much as information from Y (or equivalently, G) and forget as much as irrelevant information about X (i.e., those in O). This method is also widely applied in other relevant tasks, like domain adaptation [46], invariant risk minimization [1], and etc.
Making improvement- data augmentation Another simple and efficient way make improve- ments is data augmentation: one can identify some irreeittll factors in O and design specific data augmentation methods to teach the model be insensitive to them. For example, if we believe that the label of an image should be irrelevant to color jittering, random cropping, rotation, flipping, etc., we can apply random augmentations during training and treat the differently augmented x and x' as the same class. Then the model would inherently learn to be insensitive to such factors and hence forget the corresponding information. One interesting thing about data augmentation that it can be designed and applied in reverse direction, i.e., we can break some semantic factors and train the model to be insensitive to the broken samples. For example, believing the shape of the image and order of the words are semantic factors in G. the authors of [56] propose to randomly rotate the image patches or words to make negative samples. Those models that perform well on such negative samples more likely to rely the factors in O.
Making improvement - auxiliary task design, e.g., SSL Furthermore, one can also consider designing auxiliary tasks in addition to the downstream task, e.g., pretrain using self-supervised learning (SSL) and finetune on the target task. In [67], the authors empirically show that the representations learned via SSL usually generalize better than those learned via supervised learning when facing OOD downstream problems, even though the models are trained using a similar amount of data samples. There are also some works demonstrating that SSL representations encode more semantic information about the input image [10], which is a sign that auxiliary tasks like SSL can introduce extra biases that favor information in G.
Consider the first group of SSL methods, which are usually based on contrastive loss, e.g., SimCLR [11]. MoCo [30], etc. These methods usually require h(x.) and hx(()) to be similar while h(x;) and h(xx),, A j to be distinct, where x; is the anchor input, x/ is the augmentation of it, and x, is another different image. The carefully designed augmentation can encourage the model to ignore some task-irrelevant factors that belong to O. Imagine x is generated by deleting the background of x; As the training enforces d. (h(xx, h(x')) to be small, the learned model will then become insensitive to the information in the background, and hence avoid relying on this "short-cut" feature. Note that the contrastive SSL is utilizing the bias from data augmentation in more aggressive way: the SSL algorithm will tell the model that x and x' are the same image while the supervised learning only inform the model that x and x' belong to the same class.
16

---

Another line of SSL is built on reconstruction tasks, like denoising auto-encoder (DAE [77]) and masked auto-encoder (MAE [29]). The h(x) in these methods usually trained an auto-encoder
fashion: using reconstruction network r(z) 2. + X. we require the reconstructed Xyecon = (r (x) to be similar to the original input x. As the above equation has a trivial solution, i.e., (r I.)(.) identity, which means h((x) copies every details about (including all O and G), some early works like denoising auto-encoder propose to add noise on x to encourage non-trivial solutions. Depending on the noise we introduce, the model will learn to ignore different factors accordingly, which seems quite similar to the data augmentation mentioned in contrastive SSL methods. To encourage h(x) to extract more useful semantic information in G, methods like MAE [29] propose to mask most of the patches of the input image and try to make reconstructions based on the remaining patches. Such methods exhibit amazing reconstruction performance (not in terms of high resolution, but the precise semantic reconstruction), which also implies that the n(x) trained this way is capable of extracting high-level semantic generating factors (those are likely in G). Furthermore, methods like BETT [4] and iBOT [83] also patchify and mask the input images, and concurrently, impose extra constraints by comparing them with the descriptions generated by the big language model. Such designs also encourages h(x) to extract high-level semantic information, as illustrated in [10].
In summary, as the SSL algorithms learn good z by designing loss or tasks on it, we can introduce extra inductive bias via auxiliary tasks. By requiring to be invariant when adding noise conducting data augmentation on x, the task irreleeet information can be ruled out during learning. By requiring contains the necessary information for reconstruction when only part of is observable, the task- relevant semantic information can be highlighted during learning. By combining these principles, it is possible for us learn good h(x) that only extracts information in G. With the help of these methods, our z might learn exactly all information in G, which means the third rung is achieved.
A.3 Stage III: z learns exactly all information in G, i... h(-) leads to a bijection
Starting from Stage II, if we can design clever training methods (e.g., adding regularization, data augmentation, auxiliary task, etc.) and make our hx() to insensitive to some O, ideally, we can learn an almost perfect encoder that extracts exactly all information contained in G. In this case, we have (G z) = and H (z G) = 0, i.c., h(-) leads to a bijection between z-space and G-space, which denoted as Z ++ G. Ideally, such
generalize well even when Preain of Ptests long as all the concepts in the test set are seen by (x(x) during training, i.e., supp/ ( [G] S supp Ptrein (G)]. However, we speculate that even h(x) on Stage III will struggle in the comp-gen problem, as the problem assumes supp / [G] n supp Pirain (G) = 0. In other words, we need the model to decompose and recombine the leamed concepts in systematic way, which is similar to the ground- truth-generating mechanism. To achieve this goal, we need to consider how to achieve Stage IV.
A.4 Stage IV: h(-) leads to a isomorphism bijection between z and
To generalize well compositionally, we not only need contains exactly all information in G, the structure of G should also be embodied in z, which means h(.)) should lead to an isomorphism bijection between z-space and G-space (i.e., z <> G). Specifically, we need:
Hypothesis in detail.
To generalize well compositionally, we need z + G, which requires:
1. z < G, i.e., At-)) leads to bijection between Z and G;
2. P(z) and P(G) factorize in a similar way;
3. Each 2; maps to some Gwi- where w is permutation vector of length m, and such mapping is invariant";
4. For each 2;, the mapping between 2 k and Gw: Uy is invariant where is permutation vector of length Vw.
We call such mappings compositional and call the other bijections holistic. To better understand the difference between these two types of mappings, we consider simple example where the generating factors are = [G1, G2], G = {blue, red} and G2 = {circle, box), and the representations are
7 For example, 21 always encnde color and 22 always encode shape. For example, 21 O always means blue and 21 always means red.
17

---

Color
Shape
Z1
10
01
01
Z2
(a). Compositional Mapping
(b). Holistic Mapping
Figure 5: A compositional mapping and holistic mapping. Although holistic mapping in this example seems to have fewer "crossings", it has lower topological similarity.
Table 4: An example of coding the mappings, where a is how many characters (including space and unique symbol, e.g., - and :) used express the grammar.
A compositional mapping
A holistic mapping rules, a 56
rules, a 43
S
72, z.
72:
+
blue
S:
> blue circle
z2:
+
red
S: red circle
zl:
+
circle
S:
4 red box
zl:
box
S: blue box
2 = [21, 22]. 21 = {0, 1} and 22 = { 1). Hence the space of G is { blue circle, blue box, red circle, red box and the space of z is {00, 01, 10, 11]. To generate compositional mapping, can first decide the meaning of 2,, e.g., 21 represents the shape and 2/ represents the color. After that, box, 22 = + blue, and 22 = + red. Combining these two steps, we generate a compositional mapping, illustrated in Figure 5(a). Any bijections that cannot be decomposed in this way are holistic mappings, like Figure 5(b). Obviously, the compositional mappings can generalize compositionally while the holistic ones cannot. However, finding compositional mapping from all possible bijections is a hard problem, as the number of compositional mappings is much smaller than the holistic ones: assuming we have m different G, and each with 3 possible values, there are roughly 1 compositional mappings (m!(!!)")) and 1028 holistic mappings ((v")) 1o30-mil m!(u!)").
assign vocabularies in 2; to denote different meanings, e.g., 21 = O circle,
Another important characteristic of compositional mappings is the "distance-preservveee other words, they will map two x with similar G to two similar in the representation space, i.e., z preserve the topological structure of G. We can topological similarity (p, defined in Equation 2) to quantify how compositional a mapping is. Usually, for all bijections, mappings with larger are more compositional.
ability. In
To sum up the aforementioned four stages of the learned z, we list the conditions that must satisfy and their capabilities in Table 3.
18

---

A.5 Relationship with disentangled representations
Readers might notice that our problem settings and the requirements for z mentioned in Hypothesis 1 are quite similar to those discussed in disentanglement representation learning [32]. Here we explain the connections and differences between them.
We care more about downstream tasks. In disentanglement representation learning, people focus more on a general property of the learned representation by assuming the existence independent semantic generating factors. Disentanglement is then considered a desired property of such represen- tations. Works in this line try to formalize this property and believe this property is beneficial for multiple downstream tasks. However, as the downstream task is not incorporated in such analysis, is hard to conclude whether specific factors are semantic or not (remember the split of and G highly depends the task). On the other hand, this paper focuses more the generalization ability of the learned representations on specific downstream task(s). We directly optimize the loss of the downstream task in the interaction phase, which we believe can regularize the representations more efficiently.
We don't strictly require disentangled Although representations with properties like con- sistency or restrictiveness mentioned in [68] could be beneficial for the downstream tasks, it seems not necessary to have all of them. In other words, disentanglement is sufficient but not necessary requirement for a model to generalize well in downstream tasks. That is because the factorization of G could be non-trivial (as nature is not simple). We believe that capturing the hidden structure of G and Gen'(()) using& Z and g(-) is more important than mapping an involved generating mechanism to disentangled system. Additionally, implicitly splitting O from G is rather crucial in our settings, which is rarely discussed in the fields of disentanglement representation learning.
We mainly consider discrete factors. Inspired by how human language evolves, it is natural to start from the discrete factors and representation due to the discreteness of human language. Our experimental results also benefit a lot from the discreteness, e.g., using cross-entropy loss amplify the learning speed advantage. sampling pseudo labels to strengthen the inductive bias, using group theory to formalize the compressibility and Kolmogorov complexity, etc. However, as nature might not be purely discrete, incorporating the continuous latent space is crucial to enlarge the scope of our study. We would leave this in our future work.
B Compositionality, Compressibility, Kolmogorov complexity, and number of active bases
This appendix links several key concepts related to compositional mappings together, i.e., com- pressibility, Kolmogorov complexity, and number of active bases. The analysis here provides good intuition on why we might expect iterated learning to be helpful in comp-gen.
B.1 Higher compositionality, lower Kolmogorov complexity
We first complete the proof of Proposition 1.
Proposition (Informal). For m, v 2 2, among all bijections, any compositional mapping has much lower Kolmogorov complexity than a typical non-compositional mapping-
Proof. Recall the fact that any bijection from to G can be represented by an element in the symmetry group S.m. From the definition of the symmetry group, we know each element in S.m can be represented by permutation matrix of size n' As there is only one 1 in each row and column of a permutation matrix, any permutation matrix can be uniquely represented by a permuted sequence of length v'', Specifically, assume we have sequence of natural numbers (1, .... vn each permuted sequence Perm (1, ..., )m"}) represents a distinct permutation matrix, and hence represents a distinct bijection from G. In other words, we can encode one bijection from to G using a sequence of length tm i.e., Perm((1,2) 2, e }), and bound the corresponding Kolmogorov complexity (in bits) as
K ((bijcction) S S. .log, TT = n logg U,
(4)
19

---

As an arbitrary bijection from Z to G doesn't 't have any extra information to improve the coding efficiency, Equation (4) provides an upper bound of the minimal Kolmogorov complexity.
On the contrary, as each compositional mapping can be represented by an element in Sy x Sm. we encode the mappings more efficiently. Specifically, we need to first use m sequences with length v, i... Perm(1 [1, 2...,u) v})) to represent the assignment of "words" for each 2i. After that, we need one sequence of length m, i.e., Perm (1,, ..., m)) to encode the assignment between 2j and Gj. The corresponding Kolmogorov complexity is then bounded as
K(comp) S V log, v + m -lgg2 m.
(5)
Although this is only an upper bound, by a counting argument most such mappings must have complexity no less than, say, a constant multiple of that bound.
To compare the Kolmogorov complexity, we can define a ratio as y - KCDbijcction) K(comp)
Obviously, when
m U, mm which is larger than 1 as long m, 2 2. When m 0, 2 also larger than when m, 2
c logg v which 21ogg m
Actually, there might be some mappings that are not purely compositional or holistic. For example, we can have mapping with 2ig10 sharing the reused rules while other 2;>10 doesn't. Then this type of mapping can be represented by an element in S. x $10 X Sym-1n. As a mapping in this subset shares 10 common rules, its Kolmogorov complexity is between K(bijection) and K(comp). Intuitively, for all bijections, smaller K(.)) means higher compressibility and higher compositionality.
B.2 Regularize the Kolmogorov complexity using iterated learning
From the analysis in Appendix A.4 and B.I, we know that finding mappings with lower Kolmogorov complexity is the key to generalizing well compositionally. From existing works in cognitive science, we know iteratively introducing new agents learn from old agents can impose the compress- ibility pressure and hence make the dominant mapping more compact after several generations [42]. Although iterated learning reliably prompts the emergence of compositional mapping in lab experiments, directly applying it to deep learning is not trivial: as we are not sure whether the preference for compositionality still exists for the neural agents. Hence in this subsection, we study simple overparameterized linear model can indeed introduce a non-tr non-trivial regularizing effect. Combining with the fact that mappings with lower Kolmogorov complexity are more likely to capture the ground truth generating mechanism and hence generalize better [71], we can conclude that iterated learning is helpful for compositional generalization problems.
0/1 classification task to show that iterated learning
Consider a general supervised learning problem, in which we want to learn a mapping f F : that could approximate the underlying relationship between random variables X and Y. As we usually have a finite number of training samples and the space of all possible mappings large, the model could just remember all (x, y) pairs in the training set to achieve perfect training performance. To avoid this trivial solution, we usually expect the optimal f to have specific properties, e-g.. smoothness or Lipschitz continuousness, etc. Hence usually, want to optimize problem with corresponding regularization term:
N 1 E - 1n Se.
arg min R() s.t. fEr
(6)
where R: F + R is regularizing of and is the training loss tolerance. This regularization term is usually the inner product of f on the functional space, i.e., R((f) = || where H. is a reproducing kernel Hilbert space (RKHS) determined by some kernel function k(-,-). -). For example, if we consider v(r,y) [0, 1]2 and k(x,, y) min(x, y), then Ilf lax = |/ [64]. In other words, the regularizer will penalize functions with higher first-order derivatives.
In order make the analysis generalize other properties of S, we define linear differential operator L as [T,]] e fx u(x, (x) dx, where u(;s)) is kernel function. Then, the regularization term is:
R(f) = 11 = (f. = Lff, = [ u(x, (x)x())(() dx
(7)
20

---

Substituting this definition back to Equation 6 and then applying the Karush-Kuhn Kuhn-Tucker (KKT) conditions, the closed-forn solution for this optimization problem (i.e., Proposition in [53]):
(x) - 9x (cI G)-
(8)
where bounded constant, |n 1........ lyn] T the stacked training labels. The matrix G' E R N and its vector Ix E R RNx1 is defined as:
Gli (x(x,xx))
9xlk
N gx, Xx).
The g(x, q) is the Green's function [63] of this operator and is defined by:
Jo u((xxx (xx, q) dx = =6(x q),
(10)
where d is the Dirac delta function. Following the definition of Green's function, we know G is positive definite and hence decompose it as:
G V-VTDV.
(11)
where D = (diag(dd,...... didd.....ddaa dx]) ] is determined by its eigenvalues and V contains N corresponding eigenvectors. Now, vector form solution of problem 6:
stack the model's prediction for different input samples x,, and get the
f* (x:) - (C D'd
(12)
With this solution, following the settings in [53], explain where the compressibility pressure (the one that favors mappings with lower Kolmogorov complexity) comes from. Specifically, the optimal model for the first generation f V D(cpl + -)-- Then in the following generations, the model in generation will learn from the predictions of the model in the previous generation. As the problem is identical (the only difference is the labels) for different generalizations, we can have the following recursion formulas:
f = V D(G. + GG) and Y, =
(13)
Solving this yields the expression of the labels in the (-th generation:
Y, = V A VT
II 1==
A VY
(14)
where A, A Dial + D)-1 is N x N diagonal matrix. Substituting this back to Equation 12, we finally obtain the following expression:
f1(x) 9 D-
I[ A 1=0
VYo
(15)
1 II A j=0
= GV-TTD--
VY,
=V
|[ 1=0
A
VYo
(16)
From this solution, the model's prediction at t-th generation can be considered as weighted combination of transformed Yo. The matrix V will first map Y, to a space determined by the Green's function. Different dimensions of this space are then rescaled by diagonal matrix I A.. After that, the vector transformed back to the origin space by multiplying VT. Among these terms, IT'= A; is the only one that depends on f. Recall the definition of A, = D(c,T + D)-1, we can conclude that Ii A, is also diagonal matrix where each entry has the form like II, ci (here d, is the j-th eigenvalue of G). As c > 0, Vt, as stated in [53], all the diagonal entries will gradually decrease when t grows. The dimensions with smaller I[. o,td,
d,
di_ decrease faster, and vice versa. Recall
21

---

the role played by this diagonal matrix, we can imagine that the number of active bases in V is decreasing when grows, which a strong and unique inductive bias (i.e., compressibility pressure) introduced by this recursive training fashion'.
Now, link these theoretical analyses the Kolmogorov complexity and compressibility pressure. The crux is the understanding of "active bases". Consider a toy example where G G2], where each G; has 4 possible values (there are N 16 different objects). Then, to memorize these 16 samples, the model needs 16 bases like "S 00 + blue circle". However, for compositional mappings, only 9 bases are enough 10; because the model reuse some rules.
In summary, when is small, there no preference for compositional mappings because the number of active bases is large enough to remember most of the training samples. As t increases, the model then needs to be clever enough to reuse some bases, where the structure of the mapping emerges. t is too large, where the compressibility pressure is too strong, the model will degenerate into very naive solution, which is harmful for generalization (hence we need the interaction phase iterated learning, discussed later).
C Experiments on Controlled Vision dataset
C.1 Experimental Settings
G2
dSprites
3dShapes
MP13D-Real
Train split
split
Others
The toy vision datasets and train/test split example. All images have size 64*64. Pixels in dSprite are binary values while those in 3dShape and MPI3D contain 3 channels.
Figure 6:
Table 5: Vision datasets considered in this paper. The numbers in the parentheses represent how many different values of the attribute. The last column means how many different samples select for each G. Hence the number of samples in both training and test sets of these three datasets would be 9000, 8000, and 7200.
G
G2
Gs pos-x
G2
[G]
# per
dSprites
shape
scale
pos-y (10 out of 32)
1600
orientation (40)
object shape (4)
3dShape
floor huc (10)
wall buc (10)
object (10)
object scale (8)
8000
orientation (15)
horizontal (10 out 40)
vertical y (10 out of 40)
size (2) camera (3)
MPI3D
object color
object shape (6)
3600
background (3)
Data generating factors In this paper, we conduct experiments on three vision datasets, i.e., dSprites [52], 3dShapes [9], MPI3D-real [23], where the ground truth G are given. The summary and examples of these datasets are provided in Table 5 and Figure 6.
Here specify how to split the dataset and generate the downstream labels using 3dShapes as an example. We denote the hue of the floor, wall, and object as G1, G2, and G3. respectively: each has 10 possible values, lincarly spaced in j0, 1]. The object scale. G4, has 8 possible values linearly spaced in [0, 1]. The remaining two factors, object shape (4 possible values) and object orientation (15 possible values), are treated as other factors and merged into O. Data augmentation methods such as adding Gaussian noise, random flipping, and so on, are also merged into O. Under this setting, the universe of G, i.e., G. has 8000 different values, which is further divided into Gtrain and Gteat- For
'hhe authors [53] also prove that such a regularization cannot be achieved by other forms of regularizations. "Seeiifically, we need one basis like "S + zl z2",, four bases like "z0 - some color", and four bases like "zlj j + some shape". Please refer to Table 4.
22

---

the sys-gen problem, we assume Itaan n Gtest = 0. One measure of the difficulty of the problem is the split ratio, a | smaller a generally means more challenging problem.
Data generating mechanisms For the training set, we first select G Itrain and then generate multiple input signals using GenX(G, O), where uniformly random. The x in the test set generated in similar way, but without including data augmentation in O. Labels for all pairs in the dataset are generated by y = GenY(G, c). The main downstream task we study here regression: + e, where a [a....., .... am]]
column vector and all o; are chosen from [0, 1..1) These examples assume is generated by a simple combination of different G2, where recovering the generating factors necessary to generalize well compositionally.
GenY(G,
Model and training settings The model structure for this section is illustrated in Figure 2. We consider using randomly initialized 4-layer CNN for dSprites and ReNe118 [31] for 3dShapes and MPI3D. Unless otherwise specified, we consider linear head g and typical Cde. i.c., cross-entropy loss for classification and mean square error loss for regression. The networks are optimized using a standard SGD optimizer with learning rate of 10 and weight decay rate of 10-4, Actually, we find the results are insensitive to these settings.
C.2 More Results
C.2.1 Some interesting observations
Gat
107
Gct
Get g
Emvory
camtalo
402 600 500 Thainin spochs
1000
432
CC5
Tratiing spectts
trllon
Predkcting prossti
Figure 7: Left to right: 1.) zoom in on the curves of training and test loss; 2.) demonstration of what will happen to test loss when replacing the sampling by argmax the imitation phase: 3.) how the average predicting entropy, i.e., (2;),, changes; 4.) histograms of predicting probabilities in different generations. All panels come from experiments of SEM-IL on 3dShapes.
See the first panel in Figure 7, which demonstrates the training and testing loss when training model using SEM-IL. In the first generation, we see the training loss is always smaller than the test one. The test loss then plateaus after some epochs, which matches our expectations. However, in the following generations, the test loss would decrease faster than the training one at the beginning of the interaction phase, which quite counter-intuitive. We would explore why this happens and whether it is sign of increased topological similarity in the future.
Another observation is about the sampling mechanism applied in the imitation phase. Remember in Algorithm 1, the pseudo labels used in the imitation phase are sampled from the teacher's 's prediction attributes, the generated labels would be consistent in
2₁. Hence if the teacher is confident in different epochs, and vice versa. From Figure 4, we provide the scatter plot of the correlation between the teacher's s confidence and the student's 's learning speed. Here verify this hypothesis through an ablation study. Specifically, we replace the sampling procedure with an argmax function, i.c., the teacher always provides the label with the largest predicting probability regardless of its confidence. As illustrated in the second panel in Figure 7, the test performance of the argmax-case is much worse than the standard SEM-IL method.
The benefits introduced by sampling pseudo labels can also be interpreted as we are making self- adapting for different input samples in SEM. In the origin SEM, we only have one to control the average entropy of the backbone's 's prediction (lower r leads to peakier predicting distributions, and vice versa). However, model trained using SEM-IL equivalently has different for different
"e also tried simple non-linear mapping from G to y. i.c., GenY(G, = a1 G. ao- -G + ag GGGa + and a multi-tas task scenario, where [glv|xm is matrix. The resulting trends in these settings are quite similar.
23

---

To understand this, we can compare the entropy of hı (x) and h1 (x'), where the teacher is confident in (x. 81 0) and less confident (x's gi 0). Then during imitation, the student will remember (x. 81 0) much faster than (x' = 0) and hence assign ž = 0 higher probability when the input On the contrary, for the input x', as the student might receive different corresponding pseudo labels during imitation, it would assign lower probability for & = 0 given x'. As result, the entropy (21 x) and (21 x') of the student model would be very different as the teacher have different confidence when generating the pseudo labels, which is equivalent automatically selecting different 7 for x and x'.
The last two panels in Figure 7 demonstrate how the entropy of the model's prediction on G changes in different generations. (Remember the output of the backbone after SEM, i.e., Z = [....... .......... 2m] are m simplicial vectors with length v.) From the figures, we see the entropy gradually decreases as the training goes on, which means the model becoming more and more confident in its predictions on average. However, the last panel shows that there are still many unconfident predictions even after converging on the downstream task performance: we speculate that these factors contain little information on G as they might have high entropy.
C.2.2 Influence of task difficulty
As the ground-truth generating factors are accessible for these vision datasets, we could explore how the difficulty of the task, i.e., a, influence the performance gap among different methods. As shown in Table 6, SEM-II brings significant enhancement when or is not too big nor too small. When a is big, the test loss might be very small and there is no room to make considerable improvement. On another extreme, if is too small, some attributes might be never observed during training, which is hard for the model extract correct generating factors. Remember we expect to generalize "red circle" by knowing the concept of red and circle from other combinations: if there is only "blue" and "box" in the training set, is impractical for a model learn such concept (maybe the model can extrapolate, but that is another topic). We speculate most real tasks are in relatively small regime, as the generating factors and their possible values can be very large. Please note that as the train/test split and GenY all depend on the random seeds, the variance of the numbers in these tables could be large. However, we observe the SEM-II. consistently outperforms other methods under each task generated by different random seeds.
Table Relative improvement comparison for different a on three datasets. We report the average and standard error of different runs. A is caleulated by -asellBaseline while A₂ is calculated by
Baseline
Baselnn The test MSE for different settings are the numbers multiplying 10-3, Note that the SEMIL numbers of different datasets are not comparable, the model structure and generating factors of them are different. When a is too small, the model fails to converge on MPI3D, which means MPI3D might be more challenging dataset.
0.8
0.5
0.2
0.1
0.02
Baseline
3.778-0.792
7.902=2.000
18.01=11.75
57.87+9.8852
355.5+136.00
NIL-only
3.866=00.733
1.936
13.18+15.16
12.46
330.5+183.1
SEM-only
2.531=1.772
5.15=00.15
21.4115.224
15.48
292.711188.0
3dShapes
SEM-IL
0.633=001117
1.27=0.112
5.165=0.697
17.52:13.03
221.0+
Relative A
0.8324
0.8396
0.8156
0.6972
0.3783
Relative Ag
4.968
5.236
4.423
2.303
0.6086
Baseline
45.42-110.97
61.95=17.80
125.9+-29.00
234.0++34.94
Not Converge
NIL-only
43.38-114.03
57.34=17.35
110.8133.06
203.3:13.62
Not Converge
SF.Monly
42.91-110.05
57.69+18.34
116.5+38.50
204.1+72.68
Not Converge
MPI3D
SEM-II.
-8.05
40.33-12.12
73.43+22.63
137.8+
Not Converge
Relative A
0.313
0.349
0.417
0.411
Relative A
0.456
0.536
0.714
0.698
Baseline
0.172=00.145
7.906=2.309
109.2+10: 10.28
313.5+228.47
839.7+73.85
NIL-only
0.136=0.123
3.678-10.869
56.42.17.169
241.0:124.68
630.2-132.53
SEM-only
0.126-10.119
7.667-1.937
108.8-18,533
315.2
658.0-18.522
dSprites
SEM-IL IL
0.045
2.877
40.11
213.1138.11
596,8:t41.94
Relative A
0.506
0.685
0.633
0.320
0.289
Relative Ag
1.023
2.179
1.722
0.471
0.407
24

---

C.3 Other baselines from disentangled representation learning
Most related works consider sys-gen as an NLP or emergent language problem rather than general representation learning problem, so the best of our knowledge. there are no specific advanced baselines for this concrete problem. The most related works are some VAE-based methods in disentanglement learning. In this part, we re-implement 3-V and compare them with the baseline method in our setting. Specifically, we first pre-train the encoder of VAE on the same training set and then attach a task head for the downstream task to the "μ--part" of the encoder's prediction (note that the encoder will output "/ı-part" and "o-part" together). We observe that the VAE-based method performs worse than the baseline method, even though they seem to recover some disentangled factors when conducting latent traversal. This observation is consistent with the findings in [65] and [8 1], where the authors claim that the disentangled representations are incapable of reliably generalizing to new conceptual combinations. We also speculate that the challenging requirement of the comp-gen problem, i.c., Gtrain n Grest = 0. exacerbates this: there will not be enough variations in x to make the VAE model capture the latent vectors precisely. However, as VAE is also encoder-decoder system, it is possible to combine SEM-IL with it, which is left for our future work.
D Experimental Settings and More Results on Molecular Graph Dataset
Train:
Valid:
Test:
Fingerprint
Step1:
01010001011
CHs
Step2:
calculate the similarity score for each x in training set using the fingerprint vector
HyC
CH2
CHs
CliyOii
CHly
Step3: order all training by the score
100
CHs
Step4: prune 77% training samples with highest scores
(a). The standard scaffold split
(b). A more challenging comp-gen split
Figure 8: Left: an example of the scaffold split, the figures are copied from [79]. Right: the procedure of a more challenging few-shot split used in Table 1.
In this part, we provide an overview of the molecular graph learning dataset we used in this paper. igbg-molhiv and ogbg-mo mmb.a [37] are molecular property prediction datasets proposed by MoleculeNet and then adopted by open graph benchmark (OGB) project [79]. The molhiv dataset contains roughly 40K samples, and the task is to predict whether a molecule is capable of inhibiting HIV replication (i.c., binary classification task). The molpcba dataset is more complex, as it contains roughly 400K samples, and the target to predict 128 different bioassays, which multi-task binary classification task. 0gb-PCQM4Mv2 [36] is a large-scale molecular dataset that contains roughly 4000K samples. The task to predict the HOMÓ-LUMO gap (i.e., regression task), which is a quantum physical property that is hard to calculate in traditional methods. As the test split private, we treat the original validation split as the test split and only report the performance on it in the paper. All of the aforementioned datasets use scaffold splitting, which separates structurally different molecules into different subsets, as illustrated the left panel in Figure 8. Under such a split, some specific structures in the test set might never occur during training, which makes it good testbed for systematic generalization ability.
To make the task more challenging, which could simulate the scenario where supp Prrii (G) n supp[[ttsst (G) = 0. we prune the training set following procedure demonstrated in the right panel of Figure 8. Specifically, we first calculate the fingerprint of each x in both training, validation, and test sets using RDKit (please refer to Section 5.2 for more details). Similar to the settings used in Table 2, the fingerprint of each x is defined as FP E {0, 1 In this vector, FP: = means the molecule contain the i-th structure. Then, the score for each x the training set is defined as how many samples in the validation and test sets share the identical FP(x) with it. To prune the training samples which are similar to the validation and test set, we delete 17% samples with the highest scores (for Table 1, 7 50). If we believe these 10 structures are part of G. the remaining training samples
25

---

are more likely to have non-overlapping G compared with the test set, which makes the task better testbed for systematic generalization.
The implementation of the GCN/GIN backhone used in this work is taken from the open-source code released by OGB [37]. We use the default setting of hyperparameters for all experiments (including baseline, baseline+, and interaction phase of SEM-only and SEM-IL). For the backbone structure, hidden embedding is 300, the pooling method is taking the mean, etc. For the training on downstream tasks, we use the AdamW [49] optimizer with a learning rate of 10-3 and use a cosine decay scheduler stable the training. For the SEM layer, we search from [10, 200] and V from [5, 100] on the validation set. For the IL-rrelated methods, we select the imitation steps from (1,000; 5,000; 10,000; 50,000; 100,000).
the depth of the GCN/GIN
26


Reviews:
[{"review_id": "VsGzps9JL1", "reviewer": "Reviewer_eFnA", "summary": "Iterated learning is hypothesized to help human language develop representation ability. The paper proposes to use iterated learning with deep network models containing simplicial embeddings to obtain approximately discrete messages. They show that this combination of changes improves systematic generalization over other approaches, demonstrating these improvements both on vision tasks with well-understood latent factors and on real molecular graph prediction tasks where the latent structure is unknown.", "questions": "1. A more detailed explanation for iterated learning, which is currently lacking in the paper, will be appreciated.\n\n2. The intuition of using iterated learning in this paper is merely from results in cognitive science. I have not seen convincing reasons why it is appropriate to incorporate iterated learning in deep neural networks, and what limitations of previous works can be tackled by doing so. The introduction should be rewritten to highlight these points.\n\n3. As illustrated in Figure 3 and Table 2 (and the authors also notified), iterated learning alone may not be enough. This again raises a question: Is iterated learning really necessary for this framework?\n\n4. I have not seen a clear connection between iterated learning and simplicial embedding. As far as I understand, the main theme of the paper is about iterated learning, and simplicial embedding empirically improves the performances further (as mentioned in Section 3.2). That is to say, the combination of iterated learning and simplicial embedding in this paper may come from trial and error rather than a thorough theoretical justification. It would be beneficial if the authors can highlight this connection in their paper. \n\n5. The paper mentions compressibility and expressivity pressures throughout the main text. Can we quantify these pressures to show that the proposed method really helps them emerge through iterated learning?\n\nI would happily increase my score if the authors carefully tackle my concerns.", "limitations": "The authors have included some discussions regarding the limitations of their work in the conclusion section.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper aims to improve the systematic generalization capability of deep neural networks, which is currently an important topic in the field. The writing and figures are clear and quite easy to follow.", "weaknesses": "Please see in Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s feedback and comments. Please also refer to the overall response for some common concerns, and here is the piece-to-piece response.\n> Q1. A more detailed explanation …\n\nThanks. We will fix it in the revision.\n> Q2. The intuition of using …\n\nWe can start from the ladder of systematicity. By analyzing the information among OGXYZ, we conclude that only focusing on the mutual information between G and z is not enough for sys-gen. In the colored-MNIST example (lines 100-111), there are many possible bijections (with maximal MI), but only sys-mappings allow for sys-gen to unseen combinations of factors. Compressibility pressure finds simpler mappings, e.g. those based on fewer “bases” as discussed in lines 941-951 in the example of Appendix B.3 or those with shorter description lengths as in Table 4. In general, this should find more systematic mappings, considering arguments based on Occam’s razor or e.g. Kolmogorov complexity. Note that the term \"compressibility\" here does NOT refer to compressing information from X into z, as is used to go from stage 1 to 3, but to learning rules which themselves can be compressed, i.e., from stage 3 to 4.\n\nWhere does compressibility pressure come from? Here are two independent lines of work that guide us to IL. One is from a line of work stemming from cognitive science but with some existing applications in deep learning: [44] claims the role of two pressures; [66] extends this to neural agents; [83] adapts this to a seemingly different application, i.e., VQA. Another line is multi-generation self-distillation, which is also known as Born Again Networks (BAN); these can be framed as IL without an interaction phase. As discussed in [56] and Appendix B.3, BAN can impose a strong regularization on the number of “active bases”, which is proven to be hard to achieve via other explicit regularizers. BAN alone lacks the expressivity pressure given by an interaction phase, though, as discussed in Appendix B.3.\n> Q3. As illustrated in Figure 3 …\n\nWe certainly do not believe that iterated learning is the only conceivable way to achieve systematic generalization. The theoretical arguments of [56] establish that the way in which IL/BAN enforces compressibility pressure (via \"active bases\") is difficult to achieve through standard regularizers, however, giving some credence to the idea that some form of interaction is helpful. Their analysis is in a simplified setting compared to neural network learning, though, and there is no guarantee that this particular pressure is the only useful way to achieve sys-gen. In cognitive science, [Raviv et al. (2019)](https://eprints.gla.ac.uk/281145) showed a single-generation model (with its own complexities) can achieve similar results. IL, however, is certainly vital to the approach we explore in this paper (as shown by the improvements over SEM-only in our experiments).\n> Q4. I have not seen a clear connection …\n\nTo apply IL in a general representation learning system, we must divide the network into an encoder and a decoder, as discussed in section 3.2. We should also discretize the messages; discrete messages allow us to sample pseudo-labels and use cross-entropy loss during the imitation phase, which substantially enhances compressibility pressure, as discussed in Section 4.2 and Appendix B.3. \n\nPreviously, [66] used an LSTM encoder and decoder and trained the whole system with REINFORCE for an emergent communication task. However, we found this method to be quite unstable: non-differentiability of the learning objective leads to huge gradient variance. Similar problems exist with other training methods such as Gumbel-Softmax or straight-through estimators. Thinking about this problem led us to SEM, previously proven to be effective on SSL methods [49]. (Interestingly, [Dessì et al. (2021)](https://arxiv.org/abs/2106.04258) drew parallels between Lewis's referential game, used in iterated learning, and SimCLR, a popular SSL method.) Furthermore, as illustrated in Figure 6 of [49], SEM can help to learn representations with higher semantic coherence (i.e., higher topsim).\nThis gives three different pathways to SEM:\n\n- IL → Lewis’s game → SimCLR → SSL → SEM\n- IL → discrete message → differentiable → SEM\n- IL → compressibility → high topsim → SEM.\n\nWe will emphasize these connections in revision to make it clearer that this did not simply emerge from plugging together random ideas until something worked.\n> Q5. The paper mentions …\n\nQuantifying these pressures is important. Besides observing the learning behavior, it could also help to design explicit regularizers to avoid time-consuming iterative training.\n\nFor expressivity, the training loss of the downstream task in the interaction phase is a good measurement. If there is no specific target task, cognitive science applications use Lewis’s game, analogous to SimCLR (mentioned above); thus conducting SSL in this phase and using its objectives is also a reasonable choice.\n\nWhen the ground truth G is accessible, topsim is a reasonable measurement of compressibility pressure. For unknown G, things are more difficult, but there are various possibilities for measuring the “simplicity” based on learning theory or algorithmic information theory. For instance, see the survey of [Jiang et al. (2019)](https://arxiv.org/abs/1912.02178); many of these measures correspond at least loosely to a notion of description length as illustrated in our Table 4. The number of “active bases,” as discussed by [56], is also related to “sparsity” in the function computed by the network, but is nontrivial to measure in complex settings. Learning speed might also be a good measure; it has some support in learning theory, and the integral under the curve of NLL through learning is related to compression ratio (see e.g. [Rae (2023)](https://www.youtube.com/watch?v=dO4TPJkeaaU). Our Figures 10 and 11 also show more compressed mappings are learned faster by practical networks."}, {"review_id": "ywFPr4AoDf", "reviewer": "Reviewer_r5b6", "summary": "This paper aims to develop methods to improve systematic generalization. The paper proposes several theoretical criteria related to representation learning to improve systematic generalization. Motivated by these principles, the paper then studies whether two methods, iterative learning (IL) and simplicial embeddings (SEM), and their combination can improve systematic generalization. They evaluate these methods on synthetic vision tasks and several tasks related to modeling molecules. They find that the combination of these two methods leads to the highest performance, on average, across these tasks.", "questions": "See weaknesses above.", "limitations": "I more explicit discussion of limitations could be useful.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "* I appreciated the formal treatment of the problem in section 2, the intuition offered in section 3, and the empirical analysis connecting the proposed methods to the various hypotheses in these sections. Otherwise it would have been non-obvious how SEM and IL would be expected to improve systematic generalization.\n* The paper is well written and does a nice job connecting various bodies of work. While the empirical results for the specific proposed methods are not overly convincing (see weaknesses), I could see this work potentially inspiring new ideas.\n* Different from prior work on systematic generalization that proposes specialized models with task-specific inductive biases, SEM and IL are relatively general methods that do not necessarily limit the expressiveness of the underlying model.\n", "weaknesses": "* While I liked the intuition-building and \"ladder of systematicity\", I have two concerns with it. First, Stages 1 to 3 seem to directly follow from prior work, e.g. the information bottleneck principle (to the author's credit, this appears to be acknowledged in the appendix). Second, maybe misunderstanding on my part, but I was not fully satisfied with the definition of stage 4. As informal intuition, it makes sense that we would want to learn representations `z` that are similarly \"structured\" to the latent factors of the data generating procedure `G`. But it wasn't clear to me which operations are expected to be preserved through the proposed \"isomorphism\". Additionally, while `G` informally represents \"semantic factors\" it wasn't clear if this can be translated to a formal constraint on the structure of `G`, which we want `z` to be isomorphic to? I think it's fine to leave this mostly informal, but since the paper seemed to attempt to formalize this, I was left a bit unsatisfied.\n* It seems like most of the intuition offered for SEM and IL corresponds to stages 1 to 3 of the ladder, which per the first point is closely aligned with criteria proposed by prior work. It wasn't clear why these methods should help achieve stage 4, which seemed more unique to the systematic generalization problem setting.\n* The proposed methods seem to assume a `z` with fixed dimensionality. While this seems reasonable for one of the motivating examples (e.g. `z` representing color and shape), it is less clear how this could be applied to systematic generalization in natural language, which is referenced multiple times in the text. Prior work on systematic generalization in natural language has often considered dynamically-sized tree-structured latent variables.\n* The overall effectiveness of SEM and IL is hard to gauge. The experiments show improvements on synthetic vision tasks and 3 tasks related to modeling molecules. However, it's unclear whether the proposed methods are effective on real-world vision or NLP tasks that are more popularly studied within the ML community.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for pointing out the potential of our work. Please also refer to the overall response.\n> Q1a: While I liked … \n\nThe analysis of this part originates from the information bottleneck principle (we will make this clearer in revision), but there are also some distinctions. This principle is proposed to explain different stages of GD-based supervised learning, while our ladder applies it to rank the capability of the representations learned via different methods (e.g., supervised learning, SSL, etc.) The goal of this analysis is to propose stage 4.\n> Q1b: Second, maybe misunderstanding …\n\nFor stage 3→4, we believe the toy 2*2 example mentioned in Appendix A.4 and B.2 can provide a good intuition. Compare sys-mappings to arbitrary (holistic) bijections. As a sys-mapping can be decomposed into some shared rules while a holistic one cannot (see Table 4), the former can generalize to unseen combinations, while the latter cannot. Such rule **decomposition** is the **isomorphism** mentioned by the reviewer: imagining we have 2 attributes, each with 4 possible values, a sys-mapping can be decomposed into 9 rules while a holistic one needs 16 rules. Based on Occam's razor (simplicity bias), the ground truth generating mechanism is likely to have only 9 rules.\n\nRegarding the formal definition of this isomorphism, we do have one using the Wreath product in group theory (the detailed definition of Hypothesis 1 is its informal form). However, this definition requires the same $|G_i|$ for different i, and also different $G_i$ have to be independent of each other. Under this definition, we can formally prove that the isometry group of mappings is Hamming-distance preserving, which means the topological similarity between G and z of a sys-mapping should be highest among all possible groups (this can be proved using Corollary 4.2 of [Panek and Panek (2017)](https://arxiv.org/abs/1705.09987)).\n\nIn the end, we deleted this proof from the submission, for the following two reasons. First, we don’t want to make strong assumptions on $G$ which aren’t satisfied by real problems, e.g. in graph problems where $G$ has complex structures and dependencies, since these assumptions are not necessary for IL: compressibility pressure still exists when $G$ is complex. Second, although we have a formal definition of the problem in the simplified setting, we find our analysis doesn’t depend on that. We thought that including these formal results in a simple setting might distract the readers from the greater generality of our intuitive analysis. This setting is similar to that of [34] for disentanglement, which we believe has similar issues. We will restore these results in the appendix in revision if it would be helpful, however.\n> Q2. It seems like …\n\nThere might be a misunderstanding here. As discussed in Q1b, we know the main difference between mappings of stages 3 and 4 is how well they can be compressed. But this compression does not describe compressing information in X to representation z: it describes _compressing the mapping G→z to fewer rules_, which brings us from stage 3 to stage 4. The term “compressibility” is probably the source of this misunderstanding; we will clarify this in revision. This compressibility pressure is assumed to be “built-in” in the human cognition system, and has different origins in deep learning. Please refer to Append B.3 for more details.\n\n> Q3. The proposed method …\n\nFirst, the fixed $z$ won’t harm the performance too much as long as the gap between the dimensions of $z$ and $G$ is not so big: some dimensions of $z$ can encode multiple features or noise. This can be verified by the graph experiments: we don’t know the ground truth $|G|$, but the performance doesn’t change much for a wide range of $|z|$ values. \n\nWhat indeed matters is the structure of $G$ and $z$, which comes to the second point. For text input, which might have a more complex structure on $G$, we agree that yes, the SEM bottleneck may not be enough. The SEM structure simulates a $G$ without any hierarchical structure, simply different discrete factors. For inputs with more complexly-structured $G$, it might help to upgrade the bottleneck to a more complex (e.g., attention-based) structure, as well as measuring with more complex metric such as TRE of [Andreas (2019)](https://arxiv.org/abs/1902.07181) or HSIC [27] with more complex kernels. This adds substantial complexity, however, and since the current submission already has significant complexity and major concepts to explain we thought it better to defer this to future work.\n> Q4. The overall …\n\nIL has previously proven effective in many real applications, including multi-label image classification ([Rajeswar et al. 2022](https://arxiv.org/abs/2111.12172), machine translation [54], and VQA in [83]. However, these related works lack careful discussions on why IL works and how to apply IL to more general problems; they all rely on the inherent encoder-decoder structure. On the other hand, our submission first analyzes the key building blocks of IL. To achieve this, we chose synthetic vision datasets because knowing $G$ makes analysis much easier, and graph data because we can use RDKit to extract structural information to verify what was learned in $z$. Second, we show how to convert a general representation learning problem into an encoder-decoder style for IL, which we believe is crucial to enlarge the scope of IL. By the way, the datasets we considered, though controlled, are quite “real”: MPI3D is generated by taking pictures of a real mechanical arm, and PCQM analyzes millions of real molecules.\n\nRegarding large-scale NLP tasks, many traditional solutions already have encoder-decoder structures and discrete messages, as in [54]. Directly applying IL would be fine. For the more advanced decoder-only structure, like GPT, we are still exploring the potential of IL (we tried a small example on GPT2; please see Q3 in the general response)."}, {"review_id": "Agi9Bt2XKk", "reviewer": "Reviewer_7GSE", "summary": "This work addresses the challenge deep neural networks face with systematic generalization. Systematic generalization refers to the ability to apply learned concepts to new, unobserved combinations. The authors draw on a cognitive science theory known as \"iterated learning\", a hypothesized process explaining how human language developed this representation ability. The theory is based on simultaneous pressures towards compressibility and expressivity when transmitting messages. The researchers propose using iterated learning, in combination with deep network models that incorporate simplicial embeddings, to generate nearly discrete messages, thereby improving systematic generalization. The effectiveness of this approach is demonstrated in vision tasks with known latent factors and in molecular graph prediction tasks with unknown latent structures, where it outperforms other methods.\n", "questions": "1. There are three analysis provided in Appendix B to explain IL. It is a bit confusing why we need so many explanation here. In particular, it is hard to related different explanation, e.g., connecting the Bayesian analysis with the KRR analysis.\n\n2. How do we guarantee the predictor g is a good classifier in IL? Do we also train g in the IL procedure?\n\n3. Why can’t IL alone improve the performance? According to Appendix B, it seems that IL alone can address the proposed problem in representation learning.\n\n", "limitations": "There is no obvious potential negative social impact of this work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written. The motivation is clear and the problems are stated clearly.\n\n2. The problem addressed in this work is important, and could be particularly interesting to many communities such as causal learning or domain generalization. \n\n3. The empirical performance looks promising, where the gap between the baseline and the proposed approach is non-negligible.\n", "weaknesses": "1. The method section is not described clearly. In particular, in section 3.1, the authors did not explain why IL can be used to improve the performance. Similarly, in section 3.2, I cannot understand the motivation of adopting SEM. Most of the details are deferred to Appendix B, however, it is still important to briefly explain why IL and SEM can lead to the desired results.\n\n2. The main experiments are done with synthetic dataset such as 3dShapes or dSprites dataset. It would be interesting to see how the proposed problem can address the distribution shift problem in domain generalization benchmark such as DomainBed. \n\n3. The model attempts to learn the minimal feature to perform prediction. This could fail when there is “short-cut” presenting in the dataset. In particular, there might be “easy feature” that is highly correlated with the true target feature, where the model could learn to use those easy features instead in the proposed setting.\n\n4. The main theoretical results in Appendix B.3 are adopted from previous work [56], where they consider a distillation setting.\n\n5. The main motivation is based on compressibility and expressivity. The same concept is also proposed in various previous works such as Variational Information Bottleneck (VIM), supervised contrastive learning, invariant risk minimization (IRM), or works in causal representation learning. Nevertheless, there is no discussion or comparison to previous works.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for pointing out the potential of our work. Please also refer to the overall response part.\n> Q1: The method section …\n\nThanks for highlighting this issue; as mentioned in the general response Q1, we had trouble conveying these aspects within the space limitations, but in the final version we will emphasize the most important points of the argument. For what this will roughly look like, please see the response to reviewer eFnA (Q2 to Q4).\n> Q2: The main experiments are …\n\nFirst, we’d like to summarize what is shown by the experiments in the current version:\n\n1. A toy setting for the Bayesian agents in Appendix B.2&3, which is helpful for understanding how iterated learning works in an idealized case. We can directly observe the influence of the two pressures on the belief of different mappings.\n2. Controlled vision tasks (section 4). With the generating factors, we can observe topsim, the learning dynamics, and the influence of pseudo labels. We cannot do such an analysis if ground truth G is inaccessible; we’d like to highlight, however, that MPI3d-real in particular is a “real” problem based on actual images, not synthetic ones like dSprites or 3dShapes.\n3. Diverse molecular graph tasks (section 5). The datasets we considered have different scales and a variety of targets. With the help of the structural features extracted by the RDKit tool, we can further verify that the representations learned via IL-SEM capture the structure of generating factors well.\n\nThe general response also gives some initial experimentation with GPT2.\n\nFor the distribution shift on G, we would expect some improvements, because the sys-gen is indeed a hard distribution shift problem: remember the support of P(G) of train and test sets are non-overlapping in our setting, which is a big shift. \n\nHowever, we are not sure whether IL-SEM brings enhancement to domain adaptation problems as in DomainBed, because of their different settings. In particular, methods run on DomainBed typically know which examples come from which domain, and try to find some kind of invariance or similar properties across domains. That is, in our framework, the domain is (a) explicitly observed and (b) belongs in the “irrelevant” O factors, not in G. Our method, however, does not do much about O; it is designed for a different setting.\n\nIt may be possible to build approaches for DomainBed-type problems based on IL. For instance, we could perhaps begin with a general-purpose interaction task (as in SSL), treating all semantic features as G. We could then try to explicitly identify which factors of z correspond to the domain ID, and remove them. It also could be possible to directly incorporate domain adaptation approaches into the interaction phase. This seems beyond the scope of the present submission, however.\n> Q3: The model attempts to learn …\n\nRelying on the “short-cut” features is a long-standing problem in machine learning, which is unavoidable for any learning algorithm without extra information, including IL-SEM. In this paper, we assume there is no spurious correlation between factors in O and G. However, as in the response to Q2, most methods designed to alleviate the short-cut problem would be simple to add into the interaction phase. This version of IL-SEM would then still combine compressibility pressure from the imitation phase and ideally would gain the advantages of both frameworks.\n> Q4: The main theoretical results …\n\nThe analysis of Appendix B.3 is indeed built off of [56], but we would like to highlight that in addition to bringing their theoretical analysis to this setting, we also give some theoretical insight via our definition of sys-gen, the analysis of the ladder of systematicity based on mutual information, and the Bayesian agent analysis. Please also see our discussion of the theoretical contributions in our response to Reviewer 7owJ (Q1).\n> Q5: The main motivation is based on …\n\nThere might be a misunderstanding here: the term “compressibility” used in this paper is different from those used in IRM or VIM. In their setting, this word means compressing information contained in X into z, corresponding to moving from stage 1 to 3. Our use of “compressibility” measures whether a bijection can be compressed to a simpler function, i.e., stage 3→4. For causal representation learning, Figure 1 is similar to a causal diagram: we can consider all factors in G causally determine the labels Y. We will add some discussions in revision.\n> Q6: There are three analyses provided …\n\nSorry for not clarifying that. The Bayesian analysis aims to propose a theoretical guarantee for the converging behavior of the agents involved in iterated learning. However, this theory is not perfect: one of the most important facts about compressibility pressure, the prior distribution $P_0(h)$, must be manually designed. Appendix B.3 justifies where this bias comes from when using gradient descent in deep learning without an explicit prior. The KRR in this part explains that in a simplified setting, the compressibility pressure can be considered as regularizing the “active basis” used to explain the training data, which is one form of compressibility.\n> Q7: How do we guarantee the predictor …\n\nYes, $g$ will be trained together with $f$ in the interaction phase. We can treat the interaction phase here as a standard supervised learning process – the whole $g\\circ f$ is differentiable thanks to SEM – with a special initialization of the backbone part. We don’t use $g$ in the imitation phase.\n> Q8: Why can’t IL alone improve …\n\nThe main difference between IL-only and IL-SEM is the representation space. The discrete message will amplify the compressibility pressure for different reasons. First, it enables us to use the sampled pseudo labels from the teacher during imitation (discussed in section 4.2). Second, it enables us to use cross-entropy loss rather than MSE loss during imitation (discussed in Appendix B.3)."}, {"review_id": "SqmMxaegVj", "reviewer": "Reviewer_7owJ", "summary": "This paper proposes an iterated learning method with simplicial embeddings (SEM-IL) for systematic generalization.\nThe method is inspired by iterated learning for humans, encouraging compressibility and expressivity.\nThe empirical experiments show the improvement in vision tasks (known latent factors) and real molecular graph prediction tasks (unknown latent factors).\nIt better portrays the generation factors in vision tasks.\nIt also finds that the success of iterated learning may be caused by discrete messages.", "questions": "Please address the points in the weakness section.", "limitations": "The limitations are mentioned but not in a dedicated section.\nIt does not have a dedicated section for social impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The analysis and experiments show the potential of the SEM-IL framework on systematic generalization problems.\n\n- It is based on the cognitive science of iterated learning for humans.", "weaknesses": "(1) As mentioned in the conclusion section, it is still unclear why the SEM-IL method enables systematic generalization from a theoretical perspective for deep learning.\n\n(2) More experiments will be helpful.\nThe paper would be more convincing with a strict theoretical explanation or comprehensive experiments.\n\n(3) As mentioned in line 88, the decomposition into G and O is fundamentally unidentifiable because there can be different ways to define factors that work equally well on training data.\nSo it would be helpful to summarize what additional information SEM-IL provides to identify them.\n\n(4) It seems source codes are not provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for pointing out the potential and shortcomings of our work. Please also refer to the overall response part for some common concerns.\n> Q1: As mentioned in the conclusion section …\n\nOur claim that “a theoretical understanding is still missing” might be too conservative. Under some assumptions, we do have theoretical guarantees of the behavior of neural agents involved in iterated learning. What we want to strengthen here is that the theoretical analysis for a real IL-SEM system is hard, as we don’t have enough theoretical tools to describe the behavior of a non-trivial network on a multi-label problem where the pseudo labels are sampled from some dynamic and unknown distributions (i.e., imitation phase is complex). Hence we try to highlight the intuition of the method and use carefully designed experiments to verify them.\n\nFor the theoretical guarantees, we can start from the analysis of Bayesian agents in Appendix B.2. If we assume the agents involved in IL update their belief of all possible $h$ in a Bayesian way, we can then theoretically guarantee that the peak of the posterior is $h^* → argmaxP_0(h | h\\in H_{eff})$, where $H_{eff}$ contains all the hypotheses that satisfy the requirements of the interaction phase. The proof is not hard; we did not provide it in this version, since we think that might distract the readers from the experiments. In this toy 2*2 example, $H_{eff}$ contains all bijections. In real applications, $H_{eff}$ contains those $h$s who are capable of accomplishing downstream tasks. In short, $H_{eff}$ is the embody of expressivity pressure, while the compressibility pressure is incorporated in $P_0(h)$. We assume the prior of the mappings are negatively correlated to its coding length, as illustrated in Table 4. This is a big assumption, which motivates us to claim that “the theory for IL-SEM is still missing.” However, this assumption is likely to be true for many intelligent agents, as it is exactly what Occam’s razor claims (see also formalizations via algorithmic information theory). We then discuss where this pressure comes from in deep learning in Appendix B.3. In this part, we find for overparameterized models, the multi-generation self-distillation can bring the simplicity bias of “active bases” to the model. Although most of the theoretical analysis in this part comes from [54], we believe our application here to explain IL is also a theoretical contribution.\n\nIn summary, we can guarantee the behavior of Bayesian agents in iterated learning with the assumption of $P_0(h)$. Such an assumption could have different forms in deep learning, one of which can be proved in an overparameterized setting.\n> Q2: More experiments will be helpful …\n\nYeah, we agree that more experiments will be helpful, but we'd also like to summarize what is shown by the experiments in the current version (please also refer to the response to Reviewer 7GSE-Q2):\n\n1. A toy setting for the Bayesian agents is in Appendix B.2&3, which is helpful for understanding how IL works in an idealized case. We can directly observe the influence of the two pressures on the belief of different mappings.\n2. Controlled vision tasks (section 4). With the generating factors, we can observe topsim, the learning dynamics of different pairs, and the influence of sampled pseudo labels. We cannot do such an analysis if ground truth G is inaccessible, hence we use settings where it is known; we’d like to highlight, however, that MPI3d-real in particular is a “real” problem based on actual images, not synthetic ones like dSprites (indeed quite simple) or 3dShapes (also simple, but requiring some real visual processing).\n3. Diverse molecular graph tasks (section 5). The datasets we considered have different scales and a variety of targets. With the help of the structural features extracted by the RDKit tool, we can further verify that the representations learned via IL-SEM capture the structure of generating factors well.\n\nThe general response also gives some initial experimentation with GPT2, which we will add to the revised version.\n> Q3: As mentioned in line 88 …\n\nIndeed, the decomposition into G and O is fundamentally unidentifiable. However, we believe all the correct decompositions should capture the Hamming distance relationships among samples, which is determined by the ground truth generating mechanisms. For example, no matter how we decompose a specific G (e.g., the color could be {”blue”, “red”} or RGB value), the distance between “blue box” and “blue circle” should be smaller than that of “blue box” to “red circle”: the two objects in the first pair share some similarity we care about. If one decomposition cannot capture this distance relationship, it will not help with systematic generalization. Correct decompositions should be “isomorphic” (see further discussion in the response to r5b6, Q1b).\n\nFor the concern about “additional information”, our answer is that there is no additional information provided. The algorithm only **amplifies the simplicity bias** to distinguish mappings from stages 3 and 4. Recalling the toy 2*2 example from Appendix B, both systematic mappings and “holistic” mappings are bijections — mutual information between G and z cannot distinguish them. One separation, however, is the simplicity of the mapping; see the discussion in lines 941-951 for an example. For the origin of this simplicity bias in deep learning, please refer to the response to Q1, Appendix B.3, and the response to reviewer eFnA (Q5).\n\nIn summary, we don’t care much about the specific decomposition of G; it is not used in the algorithm. Rather, the compressibility pressure will guide our model to the most compressed mappings. Based on Occam’s razor, we believe these mappings are likely to capture the ground truth generating mechanisms and hence are able to generalize systematically.\n> Q4: The code …\n\nWe have sent an anonymous link to the code to the AC, following the instructions."}]

Author rebuttal:
We appreciate the reviewers’ feedback and comments, which are quite helpful for us in improving the paper. In this overall response, we summarize some common concerns from different reviewers and provide links to the corresponding responses. Some new experimental results are also discussed in this part. 
> Q1. Why do we expect iterated learning to work in deep learning, and why do we choose SEM?

In short, our solution follows 4 steps:

1. From the ladder of systematicity, we expect sys-gen to need a form of simplicity bias (compressibility pressure).
2. Iterated learning can impose compressibility pressure in some simple settings (particularly, with discrete messages).
3. To extend iterated learning to general machine learning problems, we need an encoder-decoder system and discrete message space. We also need the training to be stable.
4. Using SEM in our encoder-decoder helps create a discrete message bottleneck while keeping the whole model differentiable.

There are also more subtle connections between SEM and IL that motivated us to propose this solution; please see our response to reviewer eFnA, under Q4 (as well as Q2/Q3) for more details.

This paper uses three major concepts (sys-gen, IL, and SEM) that are not widely-known to machine learning audiences. Hence, it is not easy to give all of the necessary backgrounds in 9 pages. In the current version, we probably erred too much on the side of describing the context in detail while relegating too much explanation and intuition to the appendix, which made the paper a bit hard to follow. We will do our best in revision to emphasize the main ideas behind these choices (as discussed above) in the main body, while still explaining the necessary background in enough detail.
> Q2. What are the theoretical contributions of this paper?

The theoretical contribution of this paper starts from the formal definition of the sys-gen problem (mentioned in response to Reviewer r5b6-Q1b) and the analysis of the four stages of the systematicity ladder. By analyzing the mutual information among different variables involved in the sys-gen problem, we claim that stage 3→4 needs non-trivial systematicity bias. We then analyze the behavior of Bayesian agents in iterated learning with a manually designed systematicity bias on $P_0(h)$: the behavior of these agents can be theoretically guaranteed (mentioned in response to Reviewer 7owJ-Q1). To find whether this systematicity bias exists in deep learning, we propose Appendix B.3. The KRR analysis adopted from [56] provides a theoretical guarantee of the existence of a specific form of systematicity bias, the number of “active bases”, in a simplified setting.
> Q3. Experiments

Please also refer to the response to Reviewer 7GSE-Q2. This part explains the role played by different experiments in our previous work. We didn’t consider some common vision data like CIFAR or ImageNet, because we found it hard to fit them into the sys-gen problem: they usually contain only one multi-class label, which is hard for us to extract G. Work on disentangled representation learning also rarely considers these datasets. Compared with the vision tasks, we find molecular graph is a good test-bed for sys-gen, as discussed at the beginning of section 5.

For the NLP problems, many traditional solutions already have encoder-decoder structures and discrete messages. There is no need to insert an SEM layer to discretize messages, hence directly applying IL would be fine, as discussed in [54]. For the more advanced decoder-only structure, like GPT, we are still exploring the potential of IL; we tried a small example on GPT2, shown in the attached PDF.

Meta-review: This paper combines iterated learning with simplicity embeddings to develop algorithms that improve systematic generalisation over other approaches. It demonstrates benefits of this scheme on vision tasks with clear latent factors and a molecular graph prediction task.

Strengths:

-Tackles an important problem

-The empirical results show promising improvements

-The experiments show some intuitions for why these combined approaches aid systematic generalisation

Weaknesses:

-Several reviewers were unclear on the intuition for adding the SEM mechanism. (However, while better intuition is valuable, so long as the performance improvement is robustly demonstrated, it is optional)

-More experiments would be helpful in making a robust case for performance benefits, particularly in real world settings

-The paper would benefit from more complete comparison to other approaches based on compressibility ideas
Decision: Accept (poster)