Compositional languages emerge in a neural iterated learning model
Authors: Yi Ren
Shangmin Guo
Matthieu Labeau
Shay B. Cohen
Simon Kirby
Venue:  (2020)
Keywords: Compositionality
Multi-agent
Emergent language
Iterated learning

Abstract: The principle of compositionality, which enables natural language to represent complex concepts via a structured combination of simpler ones, allows us to convey an open-ended set of messages using a limited vocabulary. If compositionality is indeed a natural property of language, we may expect it to appear in communication protocols that are created by neural agents via grounded language learning. Inspired by the iterated learning framework, which simulates the process of language evolution, we propose an effective neural iterated learning algorithm that, when applied to interacting neural agents, facilitates the emergence of a more structured type of language. Indeed, these languages provide specific advantages to neural agents during training, which translates as a larger posterior probability, which is then incrementally amplified via the iterated learning procedure. Our experiments confirm our analysis, and also demonstrate that the emerged languages largely improve the generalization of the neural agent communication.

Published as a conference paper at ICLR 2020
COMPOSITIONAL LANGUAGES EMERGE IN A NEURAL ITERATED LEARNING MODEL
Yi Ren,' Shangmin Guo,² Matthieu Labeau," Shay B. Cohen,' Simon Kirby'
I University of Edinburgh, United Kingdom, 2 University of Cambridge, United Kingdom
3 LTCI, Télécom Paris, Institut Polytechnique de Paris, France renyi
com, scohen& inf ed. ac. uk, simon. ki kirbyyed. uk 2 sg9550 cam. ac. uk, m
ABSTRACT
The principle of compositionality, which enables natural language to represent complex concepts via structured combination of simpler ones, allows to con- vey open-ended set of messages using limited vocabulary. If compositionality is indeed natural property of language, we may expect to appear in commu- nication protocols that created by neural agents in language games. In this paper, we propose an effective neural iterated learning (NIL) algorithm that, when applied interacting neural agents, facilitates the emergence of a more structured type of language. Indeed, these languages provide learning speed advantages to neural agents during training, which can be incrementally amplified via NIL. We provide a probabilistic model of NIL and an explanation of why the advantage of compositional language exist. Our experiments confirm our analysis, and also demonstrate that the emerged languages largely improve the generalizing power of the neural agent communication.
INTRODUCTION
Natural language understanding (NLU), which is exemplified by challenging problems such as ma- chine reading comprehension, question answering and machine translation, plays crucial role in artificial intelligence systems. So far, most of the existing methods focus on building statistical associations between textual inputs and semantic representations, e-g. using first-order logic (Man- nin et al, (999) or other types of representations such as abstract meaning representation (Bag narescu et all 201E). Recently, grounded language learning has gradually attracted attention in various domains, inspired by the hypothesis that early language learning was focused on problem- solving (Krbyy & Hurford, 2112).. While related to NLU, it focuses on the pragmatics (Clark, (996) of learning natural language, as it implies learning language from scratch, grounded in experience.
This research is often practiced through the development of neural agents which are made to com- municate with each other accomplish specific tasks (for example, playing game). During this process, the agents build mappings between the concepts they wish to communicate about and the symbols used to represent them. These mappings are usually referred as 'emergent language'.
So far, an array of recent work (Havrylov & Titoy, 2017; Mordatch & Abheell 2018; Kottur et all 20T;; Foerster anl 2016) has shown that in many game settings, the neural agents can their emergent language to exchange useful coordinating information. While the best way to design games to favour language emergence is still open to debate, there a consensus on the fact that we should gear these emergent languages towards sharing similarities with natural language. Among the properties of natural language, compositionality considered to be critical, because it enables rep- resentation of complex concepts through the combinination of several simple ones. While work on incorporating compositionality into emergent languages is still in its early stage, several experiments have already demonstrated that by properly choosing the maximum message length and vocabulary size, the agents can be brought together to develop a compositional language that shares similarities with natural language (Li & Bowling 2019: Lazandou al. 2018 Cogswell et all 2019).
In a different body of language research literature, evolutionary linguists have already studied the origins of compositionality for decades (Kirby & Hurford, 2002 Kirby all, 2014) 2015). They

---

Published as a conference paper at ICLR 2020
C1
is softmax layer
(m))
m--
is the inner product
x
FC
52,
<Bluc, Circle
Alice
Bob
Figure 1: Referential communication game and architectures of the agents.
proposed a cultural evolutionary account of the origins of compositionality and designed a frame- work called iterated learning to simulate the language evolution process, based on the idea that the simulated language must be learned by new speakers at each generation, while also being used for communication. Their experiments show that highly compositional languages may indeed emerge through iterated learning, However, the models they introduced were mainly studied by means of experiments with human participants, which the compositional languages favored by the par- ticipants because human brain favors structure. Hence, directly applying this framework to ground language learning is not straightforward: we should first verify the existence of the preference of compositional language at the neural agent, and then design an effective training procedure for the neural agent to amplify such an advantage.
In this project, analyze whether and how the learning speed advantage of the highly composi- tional languages exists in the context of communication between neural agents playing a game. Then propose three-phar phase neural iterated learning algorithm (NIL) and probabilistic explanation of it. The experimental results demonstrate that our algorithm can significantly enhance the topological similarity (Brighton & Kirbyj, 2006) between the emergent language and the original meaning space in a simple referential game (Lewis, (162). Such highly compositional languages also generalize better, because they perform well held-out validation set. We highlight contribution
We discover the learning speed advantages of languages with high topological similarity for neural agents communicating in order play referential game.
We propose the NIL based those advantages, which is quite robust compared to most of the related works.
We propose a probabilistic framework to explain the mechanisms of NIL.
2 BACKGROUND
2.1 REFERENTIAL GAME
We analyze a typical and straightforward object selection game, in which a speaking agent (Alice, or speaker) and listening agent (Bob, or listener) must cooperate accomplish a task. In each round of the game, we show Alice target object selected from an object space X' and let her send a discrete-se sequeece message m to Bob. We then show Bob e different objects (r must one of them) and use cI...., C. E X' to represent these candidates. Bob must use the message received from Alice to select the object that Alice refers among the candidates. If Bob's 's selection correct, both Alice and Bob rewarded. The objects are shuffled and candidates each round to avoid the agents recognizing the objects using their order presentation.
randomly selected in
In game, each object in X' has N, attributes (color and shape are often used in the literature), and each attribute has N. possible values. To represent objects, similarly to the settings chosen in one-hot vector and concatenate the N. one-hot
(Kottur et all 20L2), we encode each attribute vectors to represent one object. The message delivered by Alice is a fixed-length discrete sequence (m.,.... mN,) ), in which each m. is selected from fixed size meaningless vocabulary V.
2

---

Published as a conference paper at ICLR 2020
2.2 NEURAL AGENT STRUCTURES
Neural agents usually have separate modules for speaking and listening, which we name Alice and Bob. Their architectures, shown in Figure II, are similar those studied in (Havrylov & Titov, 20177) and (Lazaridou et all 2018). Alice first applies a multi-layer perceptron (MLP) to encode into an embedding, then feeds it to an encoding LSTM (Hochreiter & Schmidhuben. 1997)). Its Bob
output will go through a softmax layer, which we use to generate the message m1, m2, uses a decoding LSTT to read the message and uses a MLP to encode 01, .... Ce. into embeddings. Bob then takes the dot product between the hidden states of the decoding LSTM and the embed- dings to generate scores 8, for each object. These scores are then used to calculate the cross-entropy loss when training Bob, When Alice and Bob are trained using reinforcement learning, we can use PA pammaa z;; aA) and P3 (c) m, C1, Ce; 8g) to represent their respective policies, where AA and 0g contain the parameters of each of the neural agents. When the agents are trained to play the game together, we use the REINFORCE algorithm (Willhmms. 1992) to maximize the expected reward un- der their policies, and add the entropy regularization term encourage exploration during training, as explained in (Mnih et all 2016). The gradients of the objective function J(OA, 03) are:
Vo v J = E [R(, V Pa [=] + AA (PA [m) Vog J = E [[(,, V log m, c1,-.. Ce)] + V pa(cmm, C1, c1,-,.e)) Ge),,
(1)
(2)
where R(2,x) (c, .r) is the reward function, H is the standard entropy function, and X AB are hyperparameters. A formal definition of the agents can be found in Appendix C.
2.3 MEASURING COMPOSITIONALITY
Compositionality is crucial feature of natural languages, allowing us use small building blocks (e.g., words, phrases) to generate more complex structures (e.g., sentences). with the meaning of the larger structure being determined by the meaning of its parts (Clark, 1996). However, there is no consensus on how to quantitatively assess it. Besides a subjective human evaluation, topological similarity has been proposed as possible quantitative measure (Brighton & Kirby, 2006).
To define topological similarity, we first define the language studied in this work as L(-) X' M.
Then we need to measure the distances between pairs of objects: D dx(#;, (0(x,,,z), where d- is a distance in X. Similarly, we compute the corresponding quantity for the associated messages my = [(x;) in the message space M with A = dM (m,,my) where (.) is a distance M. Then the topological similarity (i.e., p) defined as the correlation between these quantities across X. Following the setup of (1 (Lazaridou et all, MU)) and (Li & Bowling, 2019), we use the negative cosine similarity in the object space and Levenshtein distances (Levenshtein, (9666 in the message space. We provide an example in Appendix B to give better intuition about this metric.
3 NEURAL ITERATED LEARNING MODEL.
The idea of iterated learning requires the agent in current generation be partially exposed to the lan- guage used in the previous generation. Even this idea is proven to be effective when experimenting with human participants, directly applying it to games played by neural agents is not trivial: for example, we are not sure where find the preference for high-p languages for the neural agents. Besides, we must carefully design an algorithm that can simulate the "partially exposed" procedure, which is essential for the success of iterated learning.
3.1 LEARNING SPEED ADVANTAGE FOR THE NEURAL AGENTS
As mentioned before, the preference of high-p language by the learning agents is essential for the success of iterated learning. In language evolution, highly compositional languages are favored because they structurally simple and hence are easier to learn (Carr 2017). We believe that a similar phenomenon applies to communication between neural agents:
Hypothesis 1: High topological similarity improves the learning speed of the speaking neural agent.
We speculate that high-p languages are casier to emulate for a neural agent than low-p languages. Concretely, that means that Alice, when pre-trained with object- pairs describing high-
3

---

Published as a conference paper at ICLR 2020
p language at a given generation, will be faster to successfully output the right message for each object. Intuitively, this is because the structured mapping described by a language with high is smoother, and hence has a lower sample complexity, which makes resulting examples easier to learn for the speaker agent (Vapnik, 2013).
Hypothesis 2: High topologiaal similarity allows the listening agent successfully recognize more concepts, using less samples.
We speculate that high-p languages are easier for neural agent recognize. That means that Bob, when pre-trained with message-object pairs corresponding to a high-p language, will be faster to successfully choose the right object. Intuitively, the lower topological similarity is, the more difficult it will be to infer unseen object-message pairs from seen examples. The more complex mapping of a low-p language implies that more object-message pairs need be provided describe it. This translates as an inability for the listening agent to generalize the information it obtained from one mbeect- associated to a low-p language to other examples. Thus, the general performance of Bob on any example will improve much faster when trained with pairs corresponding to high-p language than with a low-p language, We provide experimental results in section I.]l to verify our hypotheses. We also provide a detailed example in Appendix D to illustrate our reasoning.
3.2 NEURAL ITERATED LEARNING AND PROBABILISTIC ANALYSIS
We design the NIL algorithm to exploit these advantages in a robust manner, as detailed in Algorithm
1. The algorithm runs for / generations: the beginning of each generation both the agents are re- initialized. As Alice and Bob have different structures, they are then pre-trained differently (see line 5-7 for Alice and line 8-12 for Bob): this is the learning phase, Alice pre-trained via categorical cross-entropy, using the data generated at the previous generation, which we denote D,. Bob is pre- trained with REINFORCE, learning from the pre-trained Alice. We note I, and T their respective number of pre-traue training iterations. With hypothesis 1, the expected p of the language spoken by Alice should be higher than that of D.. Meanwhile, Bob shold be more "familiar with" the language with a higher o than D., stated by hypothesis 2. Alice and Bob then play the game together for I, rounds in the interacting phase, in which both agents are updated via REINFORCE. In this phase, the languages used by them filtered to be more unambiguous information accurately to accomplish the task. Finally, in the transmitting phase, we feed all objects to Alice and let it output the corresponding messages to be stored in D++1 for the learning phase of the next generation.
their language must deliver
To better understand how NIL enhances the expected p of the languages generation by generation, we propose a probabilistic model for NIL in Appendix C, as well as a probabilistic analysis of the role played by Alice and Bob in every phase. Intuitively, expected p of language used by Alice (denoted by Ec(P(()) is quite low because of the random initialization. Then during the learning phase, Alice learns from D; and expected to have the same Ec(p([)] with D; if it perfectly learns that data set. However, as the high-p language is favored by neural agent during training, the [=C) of the weakly pre-trained Alice should higher than that of D.. A similar thing may happen when pre-training Bob. Then in the interacting phase, as the game performance has no preference for language with different p. EE[p(C)] will not change in this phase." Finally, in the transmitting phase, Di+1 is sampled based on the language with current Ec(p(C)), which is expected to be higher than that of D,. In other words, Ec(p(C) would increase generation by generation (the details for derivations are provided in Appendix C):
the beginning of each generation, the
Ec [c(C) 2 (p(C).
(3)
4 EXPERIMENTS AND DISCUSSIONS
In this section, we first verify hypotheses 1 and by directly feeding languages with different p to Alice and Bob. Then we examine the behavior and performance of the neural agents, as well as the expected p of languages, at each generation. We conduct an ablation study, to examine the effect of pre-training Alice and Bob separately. We then investigate more thoroughly the advantages
'The role of interacting phase is to filter out those ambiguous language. This may change Ee(p(C)), but without a preference for language with specific p.
4

---

Published as a conference paper at ICLR 2020
Randomly initialize D1
for 1,2,... do
Re-initialize Alice and Bob, get Alice; and Bob;
// =/====== Learning Phase
for ia 1.,,..., do
Randomly sample an example pair from D; and use it to update Alice, with cross-entrope
training end for
for is = 1,2, T do
Alice; generates message based on input objects
Bob; receives message and selects the target
Bob; updates its parameters if rewarded
end for
// ===-==-------------------------- Interacting Phase
for ig = 1,,2,...11, I
Alice, generates message based on input objects
Bob; receives message and selects the target
BOTH Alice, and Bob; update parameters if rewarded
end for
//
Transmitting Phase for 1 1, 2.,,...,/. 1. do
Generate object-message pairs by feeding objects Alice, and save them to data set D24.1
end for end for
Algorithm 1: The NIL algorithm. Ia. Is and Ig the number of iterations used to pre-train Alice, Bob, and to play the game at each generation.
brought by high-p languages, and highlight the 'interval of advantage' in pre-training rounds, which could help in selecting reasonable la and Ir. Finally, we conduct series of experiments held-out validation set to highlight the positive effect of high-p languages on the neural agents generalization ability which shows the potential of iterated learning for NLU tasks. Details about our experimental setup and our choice of hyper- parameters can be found in Appendix A. More experiments about the robustness of NIL are presented in Appendix
4.1 LEARNING SPEED ADVANTAGES
We first use the experimental results in Figure to verify hypotheses and 2. In these experiments, we randomly initialize one Alice and feed languages with different expected for it to learn (and repeat the same procedure for Bob). We generate perfect high-p language (p 1) using the method proposed in (Kirby et all 2015), and randomly permute the messages to generate low-p language with م 0.21. The other languages are intermediate languages generated during NIL. Note that there is no interacting nor transmitting phase in the experiment in this subsection: we only test the learning behavior of a randomly initialized Alice (or Bob) separately.
From the result in Figure (a and (b), we see that the high-p languages indeed has the learning speed advantage at both the speaker and the listener side. One important finding is in Figure (c),, which record the expected i.e., Ec(p(C)], during Alice's learning. From this figure, we find that when learning a language with low expected p. the value of [E)) will first increase, and finally converge to the p of D. This phenomenon, caused by the learning speed advantage, makes the weak pre-train the essential design for the success NIL: I, correctly chosen, we may expect a higher Eg (p() than that of the data set it learns from.
4.2 PERFORMANCE OF NIL
In this part, record the game performance (i.e., the rate of successful object selections) and mean of the meeect- pairs exchanged by the neural agents every 20 rounds. We run the simulation 10 times, with different random number seed each time. Although the results are different, they
5

---

Published as a conference paper at ICLR 2020
Learinn accuracy
Leaaming accuracy
mope Menlee
P-1.0
0-1.0
p
0.8.
pm6.2
p-0.21
0-0.21
0.33
Number pre-train rounds
Number of pro-train rounds
Numbar
3ea
(a) Learning accuracy of Alice.
(b) Learning accuracy of Bob.
(c) Alice's
Figure 2: Illustration the learning speed of Alice and performance improving speed of Bob when
pre-training done with various languages of different topological similarities.
1.0
Topological similarity:p
Game accuracy
0.8
Reset Alice and Bob Only reset Only reset
0.6-
2.4
None reset
Reset Alice Bob
0.2
Only
0.2
None reset
0.0
15
65
2.0
Number of generatoins
Number generations
(a) Game performance
(b) Average p of emergent language
Figure 3: Game performance and average topological similarity for the possible resetting strategies of our proposed iterated learning procedure of 80 generations. In these experiments, /=80 and =0000,,, with all other hyper-parameters following Table C.
all follow the same trend. this first series of experiments, we compare the following different methods:
Iterated learning, with resetting both Alice and Bob at the beginning of cach generation.
Iterated learning, only resetting Alice at the beginning of each generation;
Iterated learning, only resetting Bob at the beginning of each generation;
No iterated learning: neither Alice nor Bob are reset during training.
From Figure (a), we can see that for the 3 displayed variants of the procedure, neural agents can play the game almost perfectly after few generations. The curve of the no-reset method will directly converge while the curves of the other two iterated learning procedures will show loss of accuracy beginning of each generation. That is because one or both agents are reset, and are not able to completely re-learn from the data kept from the previous generation during the pre-training phase. However, at the end of each generation, all these algorithms can ensure perfect game performance.
While the use of NIL has little effect the game performance, given sufficient number of rounds, these procedures have a clear positive effect on topological similarity. In Figure (b)), we can see that the no-reset case has the lowest average P while the iterated learning cases all have higher means (and increasing). We provide extra experiments in Appendix E, which demonstrate the robustness of NIL under different scenarios. The discussion the specific impact of each agent and why the reset-Alice and reset-Bob behave differently is in Section EL
4.3 HIGH TOPOLOGICAL SIMILARITY AND INTERVAL OF ADVANTAGE
In this section, we explore further the phenomenon caused by the learning speed advantage on NIL. From the discussion in section [ and the experimental results in section I. know that I, and I, play an important role in NIL: they should not be too large nor too small. Intuitively, if I, is small, Alice will learn nothing from the previous generation, hence the NIL. amounts playing

---

Published as a conference paper at ICLR 2020
La
100
200
400
800
1200
1500
2000
3000
5000
8000
171:80
0.293
0.828
0.928
0.951
0.958
0.961
0.952
0.956
0.955
0.949
E P1:100
0.225
0.429
0.452
0.483
0.556
0.575
0.566
0.494
0.481
0.443
E
P71:80
0.203
0.706
0.836
0.886
0.899
0.935
0.936
0.929
0.889
0.837
In
I0
20
40
80
120
160
200
300
400
800
E 171:80]
0.954
0.946
0.961
0.954
0.962
0,959
0.962
0,957
0.961
0.944
E P1:10l
0.415
0.381
0.488
0.496
0.591
0.535
0.557
0.498
0.488
0.448
E
P71:80
0.927
0.937
0.929
0.928
0.936
0.891
0.888
0.897
0.891
0.880
Table I: Values of 3 metrics when varying La or 4. highlighting an interval where the topological similarity grows high.
only one interacting phase. If Ja is too large, from the trend in Figure (c(c), we may expect that the increase of expected p should be small in each generation, because Alice will perfectly learn D,, and hence have p similar to its predecessor. Hence we speculate that the value of la should have "bottleneck" effect, i.e., a too large one or too small one will both harm the performance of NII.. A similar argument can also applied in the selection of T..
To verify our argument, we run NIL with different values of La and Ib, examining the behavior of the following 3 different quantitive metries:
E[ The average reward of the last ten generations (game performance);
E| The average value of p for the first ten generations (converging speed);
[p The average value of p for the last ten generations (converged p).
From the results presented in Table I. we can see the importance of the number of pre-training rounds not being too large nor too small. The suitable la and I, are shown in bold. Furthermore, combining Figure @ and Table M. the interval of suitable La lies between 1000 to 2000 while it lies between 100 to 200 for I,, which provides an effective way to choosing hyper- parameters.
4.4 TOPOLOGICAL SIMILARITY AND VALIDATION PERFORMANCE
In this last series of experiments, we aim to explore the relationship between topological similarity and the generalisation ability of our neural agents, which can also indirectly reflect the expressivity restrict
of language. We measure this ability by looking their validation game performance: the training examples to a limited numbers of objects (i.c., the training set), and look at how good the agents playing the game on the others (i.e., the validation set). Figure (a) demonstrates the strength of the iterated learning procedure between p and validation performance, we randomly choose I, E [60, 4000) and E [5, 200] and conduct a series of experiments. Those for which Ja and Io are not in their optimal range will yield worse performance on both validation test and topological similarity. In Figure HI-(b), record the results from different experimental settings and draw the zero-shot performance given the topological similarity of the emergent language. This shows the linear correlation between these two metrics, and a significance test confirms it: the correlation coefficient is 0.928, and the associated p-value is 3.8 # 10-104, the topological similarity set increases, using iterated learning can always improve the validation performance: cases, both-reset algorithm always yields the best performance. The fact that the Alice-reset setting performs better than the Bob-reset setting also matches our analysis well.
a validation setting. To illustrate the relationship
104 Hence, under various experimental settings, the validation performance and strongly correlated. Table E shows that when the size of validation the
5 DISCUSSION: A PARALLEL WITH LANGUAGE EVOLUTION
We can observe an interesting phenomenon in Figure (bb) the topological similarity of the emer- gent language always increases at first, whether we use iterated learning or not. This akin the effect apparent for in Figure (c(c): continuing training will imply fine-tuning to examples that
Thiis he viewed in more details when looking the probabilistic analysis presented in Appendix D.

---

Published as a conference paper at ICLR 2020
Valid set size
16
32
Train
Valid
Train
Valid
Train
Valid
Train
Valid
No-reset
0.985
0.986
0.136
0.990
0.132
0.995
0.102
Bob-reset
0.967
0.943
0.094
0.962
0.152
0.947
0.116
Alice-reset 0,981
0.976
0.598
0.979
0.280
0.947
0.210
Both-reset
0.988
0.986
0.847
0.984
0.755
0.973
0.558
Table 2: Validation performance under different validation set sizes.
Validation performance
Topologica similarity.p
0.0
0.6
Only reset Alice
0.4
10
Number of generations
20
32
40
60
0.6
0.2
Validation performance
6.8
1.
(a) Validation performance, validation set size is 8.
(b) Results of validation performance and p.
Figure 4: Validation performance and topological similarity with validation size equals eight. NIL leads to the evolution of languages which allow agents to perform well on unseen items.
are not necessarily of good quality. However, through the generational resets and limited number of pre-training examples, iterated learning allows small generational improvements: this is because constraining the agent to learn with smaller amounts of data at each generation - through 'bot- tleneck' (Kirby & Hurford, -ОμZ) forces the emergence of more structured language. This limitation on the amounts of data available corresponds in our algorithm to limiting the number of number what we denoted the 'interval of advantage', In NIL, we use the weak pre-training to simulate this bottleneck, and achieve good result: the values of Ia and I, have an effect similar to the bottleneck studied (Kirby al,, 2015) (more details are provided in Appendix D). Extending this parallel with the evolution of natural language, we can relate the learning speed advantage provided by high-p languages the speaking agent to compressibility pressure (Kirby et al, MOTS) and the better ability generalize provided by high-p languages to the listening agent to the expressivity pressure (Kurby et al, 20155)
pre-training rounds of the agents,
This comparison allows to address important difference between neural iterated learning algorithm and the original version: our speaking and listening agents are not identical. Actually, the speaking module and listening module of human also not identical, but the works traditional iterated learning do not pay much attention to such differences. From Figure (i-(b) and Figure g (a), it clear that Alice and Bob affected differently by the generational resets, and thus do offer the same contribution to the final performance." From this parallel, we retain that iterated learning is also linked the emergence of certain form of compositionality when applied to neural agents. Besides, we believe that the correlation between topological similarity and validation performance that we highlight Section 4.4 another argument favor of relationship between compositionality and generalization, which has recently been explored (Kottur et all, 2017: Choil atal. 2018: Andreas, 2019).
'However, this parallel may not explain how differently they contribute to gains in topological similarity, since must factor in the differences between their pre-training procedures, and especially the fact that Alice pre-trained by minimizing cross-entropy.
8

---

Published as a conference paper at ICLR 2020
6 CONCLUSION
In this paper, we find and articulate the existence of the learning speed advantages offered by high topological similarity, with which, we propose the NIL algorithm to encourage the dominance of high compositional language in a multi-agent communication game. We show that our procedure, consisting resetting neural agents playing a referential game and pre-training them on data gener- ated by their predecessors, can incrementally advantage emergent languages with high topological similarity. We demonstrate its interest by obtaining large performance improvements in a validation examples. The robustness of the al-
setting, linking compositionality and ability to generalize gorithm also verified in various experimental settings. Finally, we hope the proposed probabilistic model of NIL could inspire the application of NIL in more complex neural-agents- saaseetttt---dddddde-e systems.
ACKNOWLEDGEMENT
We show our sincere gratitude to Kenny Smith, Ivan Titov, Stella Frank and Serhii Havrylov for their helpful discussion and comments that greatly improved the manuscript.
We would also like to thank the members from Prof. Jun Zhao's team at Institute of Automation, Chinese Academy of Sciences, e.g. Dr. Kang Liu, Xiang Zhang and Xinyu Zuo, for sharing com- puting resources to run some experiments as well as sharing their pearls of wisdom with us during the course of this research, and we thank 3 anonymous reviewers for their insights and comments.
REFERENCES
Jacob Andreas. Measuring compositionality in representation learning. arXi::1902.07181, 2019.
arXiv preprint
Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. Abstract meaning representation for sembanking. In Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse, pp. 178-186, 2013.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Henry Brighton. Compositional syntax from cultural transmission. Artificial life, 8(1):25-54, 2002.
Henry Brighton and Simon Kirby. Understanding linguistic evolution by visualizing the emergence of topographic mappings. Artificial life, 12(2):229-242, 2006.
Jon W Carr, Kenny Smith, Hannah Cornish, and Simon Kirby. The cultural evolution of structured languages an open- open-ended, continuous world. Cognitive science, 41(4):892-92) 2017.
Edward Choi, Angeliki Lazaridou, and Nando de Freitas. Compositional obverter communication learning from raw visual input. In International Conference on Learning Representations, 2018.
Herbert H Clark. Using language. Cambridge university press, 1996.
Michael Cogswell, Jiasen Lu, Stefan Lee, Devi Parikh, and Dhruv Batra. Emergence of composi- tional language with deep generational transmission. arXiv preprini arXiv: 19ee::904009900 2019.
Jakob Foerster, Joannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2137-2145, 2016.
Serhii Havrylov and Ivan Titov. Emergence of language with multi-agent games: Learning to com- municate with sequences of symbols. In Advances in Neural Information Processing Systems, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780, 1997.

---

Published as a conference paper at ICLR 2020
Simon Kirby and James R Hurford. The emergence of linguistic structure: An overview of the iterated learning model. In Simulating the evolution of language, pp. 121-147. Springer, 2002.
Simon Kirby, Tom Griffiths, and Kenny Smith. Iterated learning and the evolution of language.
Current opinion in neurobiology. 28:108-114, 2014.
Simon Kirby, Monica Tamariz, Hannah Cornish, and Kenny Smith. Compression and communica- tion in the cultural evolution of linguistic structure. Cognition, 141:87-102 2015.
Satwik Kottur, José Moura, Stefan Lee, and Dhruv Batra. Natural language does not emerge natural- lyin multi-agent dialog. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 2962-2967, 2017.
Angeliki Lazaridou, Karl Moritz Hermann, Karl Tuyls, and Stephen Clark. Emergence of linguistic communication from referential games with symbolic and pixel input. In International Confer- ence on Learning Representations, 2018.
Vladimir Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. In Soviel physics doklady, volume 10, pp. 707-710, 1966.
David Lewis. Convention: philosophical study. John Wiley & Sons, 1969.
Fushan Li and Michael Bowling. Ease-of-teaching and language structure from emergent commu- nication. arXiv preprint arXiv:1906.024000 02400, 2019.
Christopher D Manning, Christopher D Manning, and Hinrich Schütze. Foundations of statistical natural language processing. MIT press, 1999.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley. David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International Conference on Machine Learning, pp. 1928-1937, 2016.
Igor Mordatch and Pieter Abbeel. Emergence of grounded compositional language in multi-agent populations. In Thirly-Secone AAAI Conference on Artificial Intelligence, 2018.
Vladimir Vapnik. The nature of statistical learning theory. Springer science business media, 2013.
Ronald J Williams. Simple statistical frolient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-256, 1992.
10

---

Published as a conference paper at ICLR 2020
APPENDIX A: PARAMETER SETTINGS
Unless specifically stated, the experiments mentioned in this paper the hyper-parameters given in Table B The code is available at https: com Joshua Ren / Neural Iterated Learning.
Notation
Value
Description
Na
Number of all attributes
N
Number of possible values for each attribute
NL
2,
Message length
IV
16,3,4,8,66,32,64
Vocabulary size.
I
80, 100
Maximum number of generations Maximum pre-train rounds for Alice
L.
2 100, S 8000
I.
10, 800
Maximum pre-train batches for Bob
2 100, < 8000
Maximum interacting rounds
L
10, 100, 1000
Maximum rounds for transmitting phase
N
128
Hidden layer size
Nb
64
Batch size
C
2, 15, 30
Number of candidates (including the target)
Ir
2 10
< 10
Learning rate
Table Value of hyper-parameters.
APPENDIX B: DIFFERENT TYPES OF LANGUAGES: A TOY EXAMPLE
Group
Compsitional (8)
Holistic (16)
Other (232)
blue box red box = ba
blue box ba
blue box
Language Examples
red box = au
red box = bb
blue circle ab
blue circle ab
blue circle
red circle = bb
red circle = bb 0.5
red circle = bb
P
0.1 0.7
Table Different groups of language and their topological similarity.
High-p Language
Color
Object Space
Blue
Red
Blue Cincle
Red Cirgle
Box aa ba
Blue Red
Shape
aa
ba
Circle ab bb
bb
Message Space
Low-p
Color
Objject Space
Blue Box
Red Box
Language
Blue Circle
Red Sircle
Blue
Red
Shape na
ha
Box
ba
Circle
ab
ab
bb
Message Space
Figure 5: A simple representation of two languages corresponding to topological similarities of p (top) and p 0.5 (bottom).
To better understand how topological similarity can measure the compositionality of one lan- guage, and to give some intuitions on how languages having different p would like, pro- vide and illustrate a toy example in this appendix. In this example, the object space is = (blue box, blue circle, red box, red circle) and the message space M (aa, ab, ba, bb). Any
11

---

Published as a conference paper at ICLR 2020
set of mappings from four distinct objects to four messages (not necessarily distinet, i.c. same mes-
sage could correspond to different objects) forms a language. Hence, there exist 4 = 256 possible languages in this toy example. Following the principles provided in (Kirby et all 2015), we define the following concepts for describing a language:
Unambiguous language. type of language that can unambiguously describe all objects in X. In other words, the mappings between X' and M are bijectional. In this example, there exist 4 x x 2 x 24 such languages.
Compositional language. A type of unambiguous language that exhibits systematic com- positional structure when forming messages. Such languages can use different symbols to represent different attributes of meaning and combine these symbols in a systematic way to form a message such that the meaning of the whole message is formed from a simple combination of the meaning of its parts. For example, following the rules of S + XY, and X blue + b; X red :-d:>>> b; Y : box - a: X : circle :- b, we can derive compositional language like the example in Table 1 In this example, we have + 4 8 such languages.
Holistic language. A type of unambiguous language but does not exhibits full systematic structures. In other words, holistic languages are those unambiguous language who are not compositional languages. In this example, we have 24
16 such languages.
Degenerate language. A type of ambiguous language that maps all objects to the same message. In this example, we have such languages.
Degenerate component. Any ambiguous language having degenerate component, i.e., there may be more than one objects mapping to the same message. The existence of de- generate component makes the language ambiguous.
Note that the number of unambiguous languages is usually much smaller than that of ambiguous languages, and the number of compositional languages is usually smaller than that of holistic lan- guages. Using permutation and combination, we can calculate the numbers of all possible languages, unambiguous language, compositional language and holistic language as:
# all possible languages = (IV)Nz)) (OVN2)
(4)
(IVINE))
unambiguous languages (IVINO NONV--NNaa NoNo)!
(5)
No!
(iv)
V
N N.)!
compositional languages (N - (N)!
(6)
holistic languages # unambiguous languages # compositional languages
From the above equation, it is easy to that the gap between the number of compositional lan- guages and holistic languages would become larger when N,, Na. Nr. and [V] increase. Further, this means that it becomes even harder to pick compositional language when randomly sample language. That could explain why the expected topological similarity of the emergent language may increase when smaller NL and [V] are applied, as illustrated in Lzaridon all 2018: Cogswell et all 2019).
Besides the numbers of different languages, another key difference among these languages is the topological similarity (i.e., p). as illustrated in section D.L As the language studied in this paper defined as a mapping function from a meaning (i.e., an object) to a message, compositional language must ensure that the meaning of a symbol is function of the meaning of its parts. In other words, compositional languages are neighborhood related: nearby meanings tend be mapped to nearby signals. Or to say, nearby meanings that share similar attributes are likely to share similar message symbols (Brighton& & Kirby, 2006). Thus, as the difference between messages are measured by edit distance, the compositional languages will have higher p than the holistic ones. However, the existence of degenerate component also change the value of p. the p of a degenerate language might be higher than that of holistic language.
From the above discussions, we find that making the highly compositional languages dominate is challenging task: it occupies really small portion among all possible languages, and only using
12

---

Published as a conference paper at ICLR 2020
topological similarity also cannot tell them apart from those who are highly degenerate. However, the proposed algorithm can solve this problem almost perfectly: uses the learning speed advantage caused by high topologiaal similarity increase the posterior probability of high-p languages, and uses the interacting phase to rule out the degenerate components. The details of how the probability of languages changes in different phase of our algorithm are illustrated in Appendix C.
APPENDIX C: PROBABILISTIC MODEL OF THE SYSTEM
Probabilistic Model of Emergent Languages:
In section 23L we define a language as mapping function from object space X' to the message space M, i.e., L() X + M. Here discuss how to describe the probability of specific language, ie., P(C).
Suppose that have N possible different objects (I1, 22 ... IN), where N N.,, and the messages are conditionally independent given an object En (where n E
i.e.:
N
P(C) P(m mN I1, AN)
II
P(m, F1, ΣN) = II P P(m.
(8)
==1
Assume that messages are uniformly sampled from M whose size is M | we could have P(m, [T)) M. Vn {1,2. N}. Hence the initial probability (or prior probability) of any
possible language is )+) We define the posterior distribution of languages as the distribution after neural iterated learning algorithm (NIL), i.e. P(CINIL).
Then, our goal to enhance the posterior probability of the high-p languages, which is equivelant to enhance the expectation of p, i.e.:
[c-P EOCC))(CINIL
obvious that Ec]p(C)), the expected topological similarity of languages following the prior probability, is quite low, as the high-p languages only occupy extremely small fraction.
Definition of the Agents:
Following the structure provided in Figure MI we define the speaking agent (Alice) and listening
agent (Bob) formally here.
Alice is a bunch of neural networks that can map any input object to a discrete message m. So we define it as m = h(z), X' + M. As Alice generate discrete messages with softmax layers, the probabilistic distribution of different words m, can be obtained. In the example provided in Figure MI we can have P(milz) and P(m2/xz,m mi) by reading the distribution from softmax layers. more general cases, we could obtain P(mm[a, mi-1, (1--1,,-22...... following same method. Thus, we can directly calculate the probability of specific m given for Alice as follow:
Nu P m-...m........
P(m (z) = P(m, x)) II
(10)
1=2
we feed all possible x to Alice and calculate the corresponding P(m (r), we then could calculate the probability distribution of all languages after training Alice, following equation ( and (H).
Then, we can state our goal as to obtain a high Ec- by using NIL to update the parameters of the neural network.
13

---

Published as a conference paper at ICLR 2020
In setting, the posterior probability of languages is decided by Alice with its softmax layers. Bob plays role of assistant to ensure the robustness of NIL, which will be further illustrated in Appendix D and E. From Figure II could that the inputs of Bob are discrete message m and different objects. As Bob will calculate a score &e for each object ce. we can denote its function (), M X R
Probabilistic Description of Language Evolution in NIL:
Alice[il (C)
Generationi
Alice[i-1]
Alice[i] P(CC)D)
Alice[i] P((e)D;
Pt-1 (.1)
sample
sample
Po(4), x) Initial Prob. (mapping)
Di
Di+11
P,(C)D)). f)(,,x)
Bob[i] (m
Bob[i] f. x)
Bob[i] fi. f,,m,x)
Pre-trained Prob. (mapping)
Pi(CID; R(), xm,
Interacted Prob. (mapping)
Leariing Phase Interacting Phase
Transmitting Phase
Figure 6: Probabilitic explanation of different phases in NIL.
To avoid confusion, we specify all the probabilities involved in NIL in the left corner of Figure E. In the figure, the shadow regions with different colors represent the three phases of NIL in ONE generation. Thus, one generation of NIL could be described as:
Initialization: At the beginning of generation f, the initial probability of Aliceli] is Po(C),
which is same the prior probability of P(C) mentioned before, Alice(i] is always randomly initialized. The initial function of Bob[i] is represented as fo fo(m, 2)..
2. Learning Phase:
Then following Algorithm 1, Alice[i] will be pre-trained using the data sampled from the previous generation, i.e. D,. The pre-trained probability of languages is defined as (2( Bob[i] will then be pre-trained using the sample generated by P,(C)D)), using REINFORCE procedure. after which, its function becomes f(m,
3. Interacting Phase: The pre-trained Alice[i] and Bob[i] then interact and update their pa- rameters together following the REINFORCE procedure described in section 322 In each round of the game, Alicefi] would first use argmax select m with the highest proba- bility given randomly selected object both agents would then update their parameters if 1, i.c. the data pair (m, z) could assist them to accomplish the referential game successfully. We argure that this process has the same effect as the following procedure: we first sample a data set D. ~ P. (c) and then delete the data pairs that cannot unam- biguously deliver information to form refined data set R₃, Then, the interacted probability Alice(i] can be represented by (c D,, R2). As Bob also update its parameters this phase, we define its interacted function fi. (m,
4. Transmitting Phase: Finally, in the transmitting phase, we sample D(41 P,L R,) by: i)randomly feeding on to Alice[i]: ii) sample a message m., ~ P.(ml En, D,, Ra). Note that Bob[i] is not involved in this phase.
From all sections above, we argue that Alice plays an important role in all the phases in NIL while Bob only helps make the languages effective during interaction phases. As will discuss the role of Alice and Bob in further details in Appendix E, we only provide an intuition of how the language changes in NIL in the following paragraphs.
14

---

Published as a conference paper at ICLR 2020
Overall, the objective of our NIL design is to ensure the expected topological similarity of emergent languages would increase over generations, as expressed by equation (G). As the languages with higher p would be learned faster, which is stated as Hypothesis 1, expect those high-p languages to have a higher pre-trained probability P,)(D,) than in D, i...!
Ec-P(CID,)o(() (dx))
(11)
Note that this inequality is not a strict corollary, but it is very likely to hold as long as we have appropriate La- In the worst case, perfectly. However, we could verify it by the experimental results as well as the explanation in Appendix D that the weak pre-training indeed help us achieve a higher expected p. Then, in the interacting phase, we may expect:
chose extremely large Ia to make Alice leam D;
E [c-P(CID.,:) = -Cc-
(12)
as the compositional languages and holistic languages are both unambiguous and the game perfor- mance cannot tell them apart. Finally, during the transmitting phase, we have D++1 P,(C)D,, R,). Assuming that we sampled enough Di+1 to ensure it has a very similar distribution to P; Rz), it is reasonable to have:
Sc~D4,1l((0) Bc-PrarD.,)))(())))
(13)
Sum up from the above, equation (G) can be obtained by combining equation (I+))
APPENDIX D: MORE ON THE LEARNING SPEED ADVANTAGE
Amplifying mechanism and learning speed advantage are the two main elements for the success of NIL. The former on is elaborated in section 3.22 and Appendix C. under assumption that learning speed advantage of high-p language indeed exist. In this section, we will explain why such an advantage exist by experimental results and a toy example.
Hight
Lomned naxaal ageni
Language
True flaction that acocrate urininn samplee
Trirring cmplls
Predicting serplee
Low-p
Update directons at specific posticess
Bike smow mears denowing
Language
Influene the arighbochood conducting gradient descent (ascest)
Figure 7: Illustration of learning high-p language and low-p language.
Example for Supporting Hypothesis 1:
This hypothesis claims that high-p language would be leared faster than a low-p one on the speaker side. As can directly represent the posterior probability of any language from Alice's perspective, the assertion of "learned faster" can be converted to "the posterior probability increases faster". We use a toy example, i.c. two languages in Table to demonstrate how such an advantage emerges and how it works. To make the notation concise, we use "BB, RB, BC, RC" to represent "blue box, red box, blue circle, red circle" respectively. The probability of the compositional language and the holistic language in Table E can be represented as:
FFigure (2((e) might he good example
15

---

Published as a conference paper at ICLR 2020
P(Ccm))=P(mjaa//B P(mz=a BB, m==)) RRB) P(m2=u| RB, m m)=b)
(14)
P( P(m ( m)=b) P(m P(m RB, mi=a) C (15)
P(maza
C= C=P(m==||BC) BC) P(m2=b|BC,n mi=)
P(m)=b|RC) ((mg=b(RC.mm-
(16)
where C' the common part for both languages.
As we are using stochastic gradient descent algorithm to update the parameters of Alice, it straight- forward to see that the update of gradient from one point will 'pull up" the neighbourhood region of function h. which is shown in the left panel of Figure 7 Then, we can speculate that if one data sample belonging to both the two language comes, e.g. (ab, BC), the following probabilities would increase at the same time:
Pim1=a|BCy
P(m1=a|BB) P(mm=a|RC) RC),
(17)
as the input of them are similar with BC (only one attribute changes). As the conditional probabili- ties must sum to the following probabilities would decrease:
BCm; PBm)=b/BB;; R(M)=BRC).
(18)
Thus, when Alice learns the data sample (ab, BC), P(Camp) may have two terms increased, i.e., terms
and ! For P(Cnat) however, the decrease of term ! will harm the increase of term $ hence P(Cno) increases slower than P(Camp) (The fact that term decreases on both sides would not change our deduction).
Example for Supporting Hypothesis 2:
We can use similar explanation for the advantage at Bob. Recall that Bob is defined as mapping function f from M x X' to R'. Following the principle mentioned above, if Bob learns (ab, BB), bunch of function values would increase, i.e. [ab, BB), Jaa, [(bb, BB), J(b, BC), and [ab, CB), as they are all close to each other in the input space. Then is easy to find that two terms in the compositional language in Table @ are increased while only one term increases in the holistic language. That is, the score of high-p language would increases faster.
We can also think hypothesis 2 in the following way. With the intuition that language with higher tends to be smoother and to have fewer inflection points than one with lower p. the learning speed advantage given by highly compositional languages
be illustrated by the example provided in Figure M In the example, language is considered to be a one-dimensional mapping function, which represented by the dotted lines in Figure Ø. The object-message pairs, which represented by the cross marks, are the points that satisfy the mapping function. The solid line represents the mapping function of the learning agent. Suppose the target output (i.e. the third cross mark in each figure) is larger than the predicting output (i.c. the circle mark), the optimizer will update the parameters of the neural network following the direction of the gradient, as illustrated by the bold arrows in the figure. Such an update will also pull the neighbouring parts of the function up, as illustrated by the smaller arrows on the solid curve.
The smoothness of high-p languages implies that the MSE of neighbouring positions will also be reduced by this update, while the MSE of neighbors would be increased in the case of a low-p language. Such trend is represented by the blue arrows and red crossed-arrons in Figure lt the blue one means a decrease of the MSE at the specific position while the red one means increases of MSE. In other words, for high-p languages, to have a larger positive effect on other data samples, and hence ensure a higher learning speed. Meanwhile, for low-p language, one data sample would have both positive and negative effects its neighbors and thus lead to a lower learning speed.
update corresponding to one data sample is likely
16

---

Published as a conference paper at ICLR 2020
APPENDIX E: ROBUSTNESS OF NIL
In this section, we will provide experimental results to demonstrate the robustness of the proposed method. The influence hyperparameters (e.g. vocabulary size, message length) as well as the role played by Alice and Bob are both elaborated.
Robustness for Hyperparameters on Message Space:
The message space decided by the vocabulary size |V] and the message length Nr. Thus, first make experiments to see the effects of different [V] and Ny on ((cNN((N)))(((()))
From the discussion in Appendix B, we know that when [V] and Nº are large, making high-p language dominate in the posterior probability is very hard, as the compositional languages only occupy an extremely small portion. Such a trend could also be found in Table as the finally converged expectation of topological similarity becomes lower with larger [V or NL-
Our algorithm, however, very robust to different values of [V] and Ny. By comparing different columns in Table E ((CNN())))))) [PC)) decreases very slow with the increasement of [V] and Nu. An extreme example is that, the converged p can still be roughly 0.8 with [V] 72. The performance of validation accuracy seems more robust when [V] and Nr. changes: the NIL can always obtain more than 80% accuracy compared to the none reset case (roughly 15%).
Furthermore, compared with [V] Nr has a stronger impact on the performance in terms of all metrics but the validation performance, as it is shown in Table & that the performance with N2 3 is significantly lower than its counterpart when Nr = 2. One possible explanation is that the increasing of Nı brings an exponential change to the message space. However, no matter how [V] and Nz change, E (Ccii))((( is always significantly higher that the compositionality of emergent languages given by baseline model, i.e. 0.3.
N1
=
VV=12
VV=16
V|=24
V|=40
VV2
E P11:80
2
0.986+0001
0.937+0.02
0.933+0.01
0.854+0.02
0.830+0.02
0.793+00.02
3
0.712:1.01
0.83310.01
0.79811.02
0.777
0.793110.02
0.780-10.03
P1:10
0.76710.18
0.69011.18
0.68410.20
0.630-0.17
0.668
0.57210.14
0.12
0.647+0.15
0.640+0.11
0.664
0.6374+011
0.628+0.21
Go.s5
9
16
10
37
68
39
59
Valid Acc.
0.868=0.14
0.914:0000
0.833+0.11
0.866=0.11
0.801
0.82810.14
0.804
0.677+0.16 0.773+00.1
0.867+0.01 0.85
0.900+0.007
Table 5: Values of 4 metries when V and Nz changes. Metric Go.ss means the first generation that the average of the previous three generations exceed 0.85. The notation "_" means the agents never satisfy the requirement.
Robustness on Degenerate Components:
From the discussions in Appendix B, we know that the p language who has many degenerate components will also be high, and hence can be learned faster by Alice in the learning phase. Thus, is necessary to check whether our algorithm can avoid the mode collapse caused by the degenerate components. Intuitively, the degenerate components can be filtered out during the interacting phase, as the REINFORCE algorithm ensure that the parameters of the agent will only be updated with respect to R 1, i.c. the language is effective and thus unambiguous.
To verify our hypothesis, we first observe how the number of message types, i.c. the number of different messages used describe all 64 objects, changes during NIL. It is straightforward to see that a language without any degenerate component would have 64 different message types. As shown in Figure EL all methods could achieve high numbers if message types, which indicates that the REINFORCE algorithm could always filter out the degenerate components efficiently.
Furthermore, we design two challenging tasks for NII.:
17

---

Published as a conference paper at ICLR 2020
Number message types
60
30
Reset Alice and Bob
Only reset Alice
10
Only reset Bob
None reset
50 Number of generations
Figure 8: Numbers of message types from different settings.
1. Degenerate initialized: We let Alice learn from pure degenerate language at the begin- ning of each generation, before it learns from D;-
2. Degenerate mixed:
We mix the data pair generated by pure degenerate language D; and ensures the proportion of the degenerate pairs is more than 50%, which makes Alice easier collapse a degenerate language during learning phase.
We then compare the performance, i.e. the expected and validation accuracy, of agents in different tasks. The results shown in Figure E demonstrate that our NIL is very robust to the influence of degenerate component, as both (cc-P(()Nu))((C)) and the validation score much higher than the none reset baseline's 's performance.
Topological similarity:p
Validation performance
0.6
0.6
NIL baseline
NIL,, degenerate initialized
NIL, degenerate mixed
reset converged
NIL baseline....
0.2
NIL, degenerate initialized degenerate
0.2
None reset converged
10
70
80
10
30
90
Number generations
Number of generations
(a) Performance on topological similarity
(b) Performance on validation accuracy.
Figure 9: Two corner case test. NIL with degenerate initialized means Alice is initialized with degenerate language at the beginning of each generation. NIL with degenerate mixed means Alice initialized with a degenerate language, AND the D, is mixed with I, degenerate language pairs.
The Role of Bob's Pre-training
From the discussions above, it is easy to understand why Ec-P(cNU,IP(C) would gradually in- crease in NIL and how the REINFORCE applied interacting phase can filter the degenerate component. However, the role played by Bob, especially in the learning phase where Bob only update its own parameters, is not straightforward. In short, the pre- pre-training of Bob makes the al- gorithm more robust, especially at the beginning of the interacting phase. We record the value of Ec.-((C)m))) (p(C) every 20 iterations among learning phase and interacting phase, and plot the results of two generations in Figure III.
18

---

Published as a conference paper at ICLR 2020
0.6
Topological similarity:P
0.5
0.4
NIL with Bob Pre-train
NIL without Bob Pre-train Range of Bob Pre-train
0.0
1000
1500
2000
2500
3000
Time Index one generation
Figure 10: The change of [Cc-P(CNN)))(([C] in generation and
In this figure, the x-axis is the index of iterations. With I,=1000, /,=400, and 1,=1600, we split (by dotted lines) each generation to three parts: Alice pre-training, Bob pre-training, and interacting phase. The blue lines are generated by NIL with the pre-training of Bob while the red lines are generated when Bob is not pre-trained (here I,=2000 to make fair comparison). For the blue lines, ((ENn [P(]] will not change when Bob pre-training (begins at the 1000th iteration), because Alice do update parameters that time. However, for the red lines, [CCC((C [p(C)] begin to decrease at the 1000th iteration. That is because when Bob is not pre-trained, the language learned by Alice may be impacted by playing with a fresh new Bob the beginning of interacting phase! That is why the pre-training of Bob can make the NIL more efficient and robust. If Bob are pre-trained by the data generated by Alice in the current generation, Bob would more "familiar" with Alice's 's language, and hence ensures a more stable interacting phase.
Looking at the Emergent Languages
From the discussions above, we know that NIL can ensure high expected of the emergent lan- guage, and a high validation performance. Here we show the evolution of the distributions of emer- gent languages to provide a better intuition on how NIL works.
We first provide two examples converged language (i.e., the language generated by Alice in the last generation) using the none-reset method and the resetting-both method in Table B and A respec- tively. these examples, both languages can almost unambiguously represent all different types of objects in X, and hence they help Alice and Bob to play the game successfully. However, the language generated using iterated learning has clear compositional structure: the first position of the message represents different colors, and the second position represents the shape. Such structure is quite similar to what humans do, e.g., combine an adjective and noun to represent a complex concept.
To better illustrate the posterior probability of emergent languages as a function the corresponding value of p and the generation, provide the 3D views of P( R,) in 80 generations in Figure ID and [ The heat-map provided in Figure [ can be considered as the top views of these 3D illustrations.
these two figures, the x-axis and y-axis represent the index of generation and the topological similarity, and the z-axis represents the probability of languages with a specific value of p. in specific generation. To make the figures easier to read, we smooth the distribution of p in each generation using linear interpolation (Boyd & Vandenberghe, 2(04)).
Figure 44 (a) and (b) compare the posterior distributions at some typical generations, which can also be considered as the side views of the 3D illustration from the direction of x-axis. In these figures, we find that the initial distribution of p is not flat. That is because even the prior probability for each language is uniform, the amounts of languages with extremely high p and low p only occupy a small portion among all possible languages, as stated in (Bnghton) 2002). Hence the initial probability of p(C) is longer uniform and has bell shape which is similar the Gaussian distribution. One new trend provided by these figures is that, in the none-reset case, the width of the curves in different generations do not change much, while in the resetting-both case, the width of the curves
19

---

Published as a conference paper at ICLR 2020
will gradually decrease (i.e., becomes peaky). Such trends means when iterated learning is applied, language tend to converge to some high-p types.
Figure -S (a) and (b) track the ratio of languages with different values of p. which also be considered as the side views of the 3D illustration from the direction of y-axis. these figures, we divide all possible languages into five groups based
their topological similarity, i.e., languages with p I 0.2, 0.2 < p Σ 0.4, 0.4 < p I 0.6, 0.6 < p I 0.8, and 0.8 < p. We plot the ratio of these five different groups languages the end of each generation. From Figure (a)),, we can see that the high-p language, which is represented by the bold curve, always occupy a small portion. The topological similarity of the dominant languages are < 0.4. However, the resetting-bott case, as illustrated in Figure (B)()), the portion of high-p language will increase significantly, which further verifies that the iterated learning can gradually make the high-p language dominate posterior.
blue
green
cyan
brown red black yellow white
box
fh
hh
cg
ha hf
circle
da df
hb
db
fa
da
dh fb he ba
triangle
ge ff
ge
gf
gg
fg
ge
square
fb
be
bb
bg
fb
gb
star
fd
de
db
dg
ce
he
diamond
dd
dc
db
dg
fd
dc
dd
pentagon
fe
bd
eg
ee
ed
capsule
dd
de
db
dg
gd
de
fh
Table 6: Example of the converged language in none-reset case 0.23
blue
green ea
cyan
brown ba ga da ca ha fa
red
black
yellow
white
box
aa
circle
eb
bb
gb
db cb
hb fb he fe hf ff
triangle ae eb
be
ge
de
ce
square af ef
bf
gf
df
cf
star ec
bc
ge
de
dh
fc hd fd
diamond
ed
bd
gd
dd
pentagon
capsule eg
bg
2g
dg
hg fg
bh
gh
hc
hh fh
Table Example of the converged language in resetting-both case p = 0.93
1.0
Topological similaritysp
0.7 0. 0.9
Topological similarity;p
0.7 08 0.9
0.60
0.5 0.8
0.45
0.6
0.45
0.5
04
04
81 0. 0.3
0.3
0.15
011 0.2
0.15
20
00.00
10
0.00
Number of generations
Number of generations
(a) The none-reset case.
(b) The resetting- both case.
Figure 11: Distribution P(p(C)) R.) through 80 generations. Values of p are divided into ten groups. The distribution of in each generation is smoothed using linear interpolation.
20

---

Published as a conference paper at ICLR 2020
0.80
probabiiity 0f language
0.33
0.44
0.30
Topological similarity
Number of generations
60
70
80
0.0
Figure 12: Language evolution of none-reset case in 3D illustration.
0.80
0.1
ugge
0.44
0.36
0.27
0,09
0.00
Topological similarity
0.8
Og
10
0,4
Number generations
70
80
0.0
Figure 13: Language evolution of resetting-bott case 3D illustration.
Gonoration
Goneration
Probablity
Probability
0.5
0.4
0.4
0.5
0.2
0.1
0.1
0.0
0.0
Topological similarity:p
Topological similarity:p
(a) None-reset case.
(b) Resetting- both case.
Figure 14: Distribution of p(C) at different generations.
21

---

Published as a conference paper at ICLR 2020
6.8
Probabiltt
Probability
0.6
(ED4..
PERMA
((06.08
0.4
PE
8.0.8.1.0)
pE108.1.0
Number of generations
Number of generations
(a) None-reset case.
(b) Resetting-both case.
Figure 15: Evolution of language with different values of
22


Reviews:
[{"review_id": "SyeiU2UAtr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the emergence of compositional language in neural agents. They propose an iterated learning method that consists of three phases: a supervised learning phase for a randomly-initialized speaker and listener, a self-play phase (where both agents are updated together), and a phase where a new dataset is created based on the current speaker’s language. This dataset is then passed on to the next ‘generation’ of speaker and listener. The paper finds that this procedure, with the right hyperparameters, leads to the emergence of more compositional languages in a simple symbolic referential game.\n\nThe question of how to emerge a compositional language is indeed interesting. This paper does a good job of conducting a careful set of ablations and analyzing the results. In my mind, the main scientific contribution of this work is the empirical verification of the principle ‘compositional languages are easier to learn’. While this principle is intuitive, it’s good to see it confirmed via experiments. The paper’s description of the ‘interval of advantage’ --- the range of updates where a compositional language performs better on the task than a non-compositional language --- is insightful to me. \n\nI do have concerns for this paper around utility and novelty. As the paper mentions, it has already been shown that iterated learning procedures give rise to more compositional languages in non-neural models. While there are some things to consider in adapting this to neural networks, to my eye they seem rather straightforward (i.e. tuning the number of updates of the speaker and listener, the values I_a and I_b), contrary to the paper’s assertion.  From a utility perspective, the paper doesn’t go into how this might be practically applied in general to train neural agents to learn compositional languages in more complex environments (where they might be simultaneously speakers and listeners), as they stick to a very simple symbolic referential game. The main contribution of this paper is really: “studying how neural networks behave when trained in an iterated learning setting in a simple referential game“. I think this is a nice contribution, but the main question for me is whether this is enough for an ICLR acceptance. \n\nMy other concern is around the length of the paper. In my opinion, while the paper is well-written, it’s quite bloated and there is a lot of repetition. I think the paper could easily be condensed to 8 pages and retain the same information. Alternatively, some of the graphs in the Appendix (which are quite nice) could be added to the main paper to give more insight about how neural networks behave in this iterated learning procedure. \n\nFinally, the paper shows that compositional languages generalize better to the held-out validation set. While this is also an intuitive result, it’s nice to have in the paper. I’d encourage the authors to remove the ‘zero-shot’ terminology though (which usually refers to predictions on new samples outside of the training distribution), and just stick to what is actually being shown, which is improved generalization. \n\nOverall, I like the paper, but due to the concerns mentioned above I think it’s borderline, with a slight lean towards rejection. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "SkgR8TeAKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper \"Compositional languages emerge in a neural iterated learning model\" address the problem of language emergence in two-players games. In particular, the authors proposed a neural iterated learning model which seeks comopsitional languages. Authors claim that compositional languages are easier to be learned and that they allow listeners to more easily understand provided messages. \n\nThe problem of language emergence is interesting since it refers to the problem of finding efficient ways to communicate.  At first I was wondering why such compositional language messages would be desirable and was a bit negative on this work. But in Table 2 authors give results for zero-shot performance which emphasize the benefits resulting from finding such composition properties in language: compositional languages have greatly better generalization properties. I like the parallel that we can make with humans, that have to learn to understand language for achieving tasks when they are childs, which is simulated here in the reset and re-training performed  at the start of each generation, and which explains the natural emergence of such compositionality. This is not a big surprise, but I like the simple but clever idea of reset that the paper exploits. \n\nWhat I like less is the inequality (5) that not fully convinced me. I am not sure why this should hold. Moreover, authors claim that if Ia is too long, no improvement of the topology can be made. I cannot understand why. For instance if there are ambiguous messages in D, the interaction phase can radically change the language even if the pre-training has converged... And why should weak pre-training favor low-p languages? \n\nAlso, the considered learning scheme is that in the transmitting phase Alice records messages for all objects in D. But is it realistic ? \n\nA study of the impact of the size of vocabulary would also be useful (since it must have a big impact on the results)   \n\nAt last, why considering such discrete messages while for agents communication  would be easier with continuous messages ? When considering continuous messages, the problem relates with disentanglement which is a current hot-topic: having one factor controling one specific aspect of the object would also be useful for improving zero-learning.     ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Skev5xvMcB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a neural iterated learning algorithm to encourage the dominance of high compositional language in the multi-agent communication game. The author shows that the iterative training of two agents playing a referential game can incrementally increase the agent to use the language with high topological similarity. The authors also demonstrated that topological similarity is correlated with zero-shot performance. And Experiment results show the authors could propose alternative pre-training strategies for the neural agent can prefer high compositional language and achieve high task performance. \n\nEmerging the compositional language from uniform prior can be very challenging, as mentioned in the paper, \"high-\\rho language only represents a small portion of all possible unambiguous language\" and \"high-\\rho do not seem to be directly preferred during the interaction phase, they can be favored by the neural agent during the learning phase.\" I agree with the authors with respect to the difficulties of generating high-\\rho language, but I have questions about the designed learning phrase, especially how to avoid the mode collapse during training. \n\nWith the first hypothesis, \"high topological similarity improves the learning speed of the speaking neural agent\", I agree that high topological language has less low sample complexity compared to random sampled low topological language. However, low topological language didn't necessarily lead to low sample complexity, for example, given a D consists of {a, a, a, a ...}, the sample complexity can be quite low and also with a high topological score. I wonder is the hypothesis still true in this case? \n\nOn the second hypothesis, a high-\\rho language will be faster to success choosing the right object using fewer samples. I agree with the authors that compositional language can and will lead to better generalization ability. However, from Algorithm1, it seems Bob receives the message only update with its parameters. There is no change of language generation. I wonder how the update of Bob will help Alice to speak the more compositional language? More explicitly, to avoid mode collapse. \n\nExp 3 mainly tests the model with different \\rho as the posterior probability. In Exp 4, I assume the posterior probability of the mapping is random (uniform), is that correct? It will be great if the confirm this since this is my major doubt when reading the paper. \n\nAs mentioned above, I understand that high topological similarity language both benefit from the speaker and listener. However, there are some corner cases that mode collapse will happen and It seems the model will hardly recover from that. From Table 3, it seems the authors have fixed vocabulary size 8, I'm wondering what happens with a large vocabulary size? will the model still learn to emerge the compositional language with a large vocab size? ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper examines the correspondence between topological similarity of languages (correlation between the message space and object space) and ability to learn quickly in a situation of emergent communication between agents.

While this paper is not without issues, it does seem to present a nice contribution that all of the reviewers appreciated to some extent. I think it will spark further discussions in this area, and thus can recommend it for acceptance.
Decision: Accept (Poster)