Year: 2021

Abstract:
Researchers are using deep learning models to explore the emergence of language in various language games, where simulated agents interact and develop an emergent language to solve a task. We focus on the factors which determine the expressivity of emergent languages, which reflects the amount of information about input spaces those languages are capable of encoding. We measure the expressivity of emergent languages based on their generalisation performance across different games, and demonstrate that the expressivity of emergent languages is a trade-off between the complexity and unpredictability of the context those languages are used in. Another novel contribution of this work is the discovery of message type collapse. We also show that using the contrastive loss proposed by Chen et al. (2020a) can alleviate this problem, compared with the standard referential loss used by the existing works.

heading: 1 INTRODUCTION
text: Language games were first introduced by Wittgenstein (1954) to explore the meanings of language utterances. Instantiating this concept with the signalling game design from Lewis (1969) enables linguists to explore the emergence of linguistic structure (Kirby, 2001; Kirby & Hurford, 2002) where artificial languages are represented as symbolic systems. The success of deep learning (DL) models on complicated cognitive tasks (Krizhevsky et al., 2012; LeCun et al., 2015; Silver et al., 2016) then inspired researchers to apply DL-based models to language games for investigating agents’ ability to invent communication protocols without preset rules.
In language games implemented in existing works (e.g. Lazaridou et al., 2018; Graesser et al., 2019; Zhang et al., 2019; Lee et al., 2018; Yuan et al., 2020), there are usually two types of agents, speakers that emit messages based on their observations (i.e. target objects) and listeners that receive messages and take actions accordingly, as illustrated in Figure 1. Based on the goals for listeners, we can categorise most of the games into the following three types: 1) referential games where listeners need to select the target object observed by the speaker among a set of candidate objects (candidates for short) (e.g. Lazaridou et al., 2017; Ren et al., 2020); 2) reconstruction games where listeners need to reconstruct the speaker’s observation (e.g. Chaabouni et al., 2020; Kharitonov et al., 2020); and 3) navigation games where listeners need to go to the location specified by the speaker (e.g. Lowe et al., 2017; Kajić et al., 2020). We focus on referential games, illustrated in Figure 1a, which have been well investigated in both the linguistic community (e.g. Winters et al., 2018; Kirby et al., 2014) and emergent communication community (e.g. Lazaridou et al., 2018; Li & Bowling, 2019).
It is reasonable to assume that listeners in referential games can differentiate the target object from the other distractors in the context as long as the speaker’s message encodes some unique feature of the target. Therefore, the speaker’s messages must convey different amount of information for listeners to complete their task in games with candidates that are similar in different degree. For example, to distinguish two very similar objects in the candidates set, e.g. blue wide-stripped shirt and blue narrow-stripped shirt, it requires more information about the target to be encoded by the speaker’s message than to distinguish a shirt from a cup. Experiments with human participants show that emergent languages are sensitive to the requirements of the communicative tasks for which they are used, with languages developing in which only the necessary discriminatory information is encoded
Speaker Listener
Message
(a) Illustration of the referential game we investigate in this work. Observations are concatenations of two 5-digits-long one-hot vectors. The objective of the listener in to select among a set of candidate inputs (the context).
Speaker's Encoder (MLP) Speaker's Message Generator (LSTM)
Listener's Message Encoder (LSTM)
Speaker Modules
Listener Modules
Listener's Candidate Encoder (MLP)
Input
target
distractor
Listener's Action Module (Softmax)
Message
output distribution
Candidate set (context)
(b) Illustration of the architecture of agents we implement for referential games. Blue modules are components of the speaker, and green modules belong to the listener. Orange and grey indicate the vectors generated by agents and input samples respectively.
Figure 1: Diagram of referential game and the architecture of our agents.
(Winters et al., 2018). Following Kirby et al. (2015), we refer to such ability to encode information about input space (e.g. structure, dimensionality, distribution of samples) as expressivity. In this work, we explore the factors that influence expressivity in the framework of DL-based language games, and we argue that it is important to understand these factors such that agents could develop languages that are useful in general.
Our contribution in this work is threefold. First, we propose and verify a hypothesis about the determining factors of expressivity of emergent languages under the DL-based framework. Following Winters et al. (2018), we show that context size (i.e. the number of candidates the listener must select among when interpreting the speaker’s message) influence both the complexity and unpredictability of that context. Complexity refers to the similarity between the items in the context: in order for the listener to select the target, more information needs to be encoded in the speaker’s signal if the context contains more similar distractors for a given target. Unpredictability refers to the extent to which the information that needs to be encoded by the speaker is stable across contexts in successive episodes of communication: in games where the information required by the listener differs from trial (training epoch for DL agents) to trial, the speaker needs to encode more information on every trial in order to be sure to encode the information the listener needs.1 As we show in Section 3.1, complexity and unpredictability are affected differently by the context size: as context size increases, complexity increases but unpredictability decreases. Therefore, we propose and verify the following hypothesis about the determining factors of expressivity:
The expressivity of emergent languages is a trade-off between the complexity and the unpredictability of context in language games. [1]
Our second contribution is a novel measure of expressivity based on partial ordering of languages in terms of their generalisation performances across tasks. Although expressivity is related to the amount of information encoded in a language, we illustrate that mutual information (MI) is not an appropriate measurement for expressivity in Section 3.2. Considering that one of our objectives is to facilitate a universally useful emergent language, we propose to measure expressivity of a language based on the generalisation performance of agents trained with it across different games. Since it is more challenging to quantitatively measure it, we focus on the partial ordering between languages in this first work towards understanding it.
Our final contribution is the discovery of message type collapse, i.e. the number of unique messages is significantly less than the size of input space in relatively easy games, which further leads to highly ambiguous emergent languages. To overcome the technical limitations imposed by GPU memory size on large-scale referential games, we introduce the contrastive loss proposed by Chen et al. (2020a) in referential games. While comparing the behaviour of the contrastive loss and the loss function by previous work (e.g Havrylov & Titov, 2017; Li & Bowling, 2019; Ren et al., 2020; Guo et al., 2020), we find that this contrastive loss could greatly alleviate the collapse of message types, thus lead to more disambiguous emergent languages.
1Context, complexity, and unpredictability are defined and discussed in depth in Section 3.

heading: 2 GAMES, AGENTS AND LEARNING METHODS

heading: 2.1 GAME ENVIRONMENT AND ARCHITECTURE OF AGENTS
text: Environment Components As shown in Figure 1b, the environment in our referential games have the following components: 1) input space X from which the speaker’s observations are drawn, which consists of 10, 000 possible inputs2 where each x P X is a concatenation of 4 one-hot vectors whose length is 10; 2) message space M consists of 106 6-tokens-long sequences m (called as a message type) where the size of the token inventory is 10; note that the tokens are initially meaningless, and meaning emerges through the negotiation of a communication protocol between speaker and listener; 3) candidate set C which contains a target input xt and |C| ´ 1 distractors txd1 ,xd2 , . . . ,xd|C|´1u sampled uniformly at random from X without replacement. Agents The architecture of the agents we implemented is also illustrated in Figure 1b: 4) speaker S consists of both a multi layer perceptron (MLP) for encoding the 40-digits-long target input xt onto a 256-digits-long embedding hS , and a decoder for generating a message m based on long-short term memory (LSTM) network (Hochreiter & Schmidhuber, 1997). 5) listener L is constituted by an LSTM-based sequence encoder which encodes m into a 256-digits-long embedding hLpmq, and an MLP for encoding the inputs which can be denoted by fLcencp¨q. Definition of an emergent language: following e.g. Ren et al. (2020), we can then define an emergent language L as a mapping function from the input space X to the message space M, i.e. L : X ÞÑ M, thus it can be represented as tpxi,Lpxiqq|@xi P X u. Note that L could be a noninjective mapping function, i.e. it is possible for two different inputs to be mapped to an identical message thus the number of message types might be less than the number of unique inputs.

heading: 2.2 LEARNING METHODS OF AGENTS
text: In the previous works (e.g. Havrylov & Titov, 2017), the action module of L is usually a softmax function that would produce a categorical distribution over the candidates based on the distance between hLpmq and embeddings of each candidate fLcencpxiq obtained through another MLP-based candidate encoder. By comparing the loss function used in Havrylov & Titov (2017) and the contrastive loss function proposed by Hadsell et al. (2006), we find that the aim of both functions is the same, i.e. to make the distance between positive pairs (xt and m) closer while keeping the embedding for negative pairs (xd and m) as far apart as possible. To effectively validate our hypothesis, we need to make the whole input space X as candidate set C in which case the batch is too large to be stored in GPU memory (since the space complexity is Op|X |2q). Therefore, to overcome this issue, we adapt the contrastive learning method proposed by Chen et al. (2020a) to referential games. Suppose that we have a batch of input samples B “ tx1,x2, . . . ,xi, . . . ,x|B|u and the corresponding messages from the speaker are tm1,m2, . . . ,mi, . . . ,m|B|u which would be further encoded into thLm1 ,h L m2 , . . . ,h L mi , . . . ,h L m|B|
u by the listener L. Then the loss function for a sample xi is defined on a softmax function:
`i “ ´ log exp
´
hLmi J ¨ fLcencpxiq
¯
ř|B| j“1 exp
´
hLmi J ¨ fLcencpxjq
¯ . (1)
In this way, the number of candidates |C| is exactly the batch size |B| during training. More details about the comparison between referential loss and this contrastive loss can be found in Appendix A.
As for updating the parameters, we use the Adam algorithm introduced by Kingma & Ba (2014), and the learning rate is set to 10´4. To allow the gradients being propagated through the discrete channel to overcome the sampling issue of messages, we apply the Gumbel-Softmax trick proposed by Jang et al. (2017), and the temperature hyper-parameter τ is set to 1.0.
Our implementation3 of games bases on the framework EGG developed by Kharitonov et al. (2019). The experiments across 6 random seeds, 18 source games, 11 target games took 4, 216 hours in total, on Nvidia Tesla P100. Definition of “source/target games” are given in the following Section 4.2.
2According to the results from Chaabouni et al. (2020), an input space containing 10, 000 possible inputs is large enough for neural models to achieve ą 99% generalisation accuracy.
3Codes are provided in the supplementary materials.

heading: 3 CONTEXT AND EXPRESSIVITY

heading: 3.1 CONTEXT, AND ITS COMPLEXITY AND UNPREDICTABILITY IN DIFFERENT GAMES
text: Context: Communication between humans always takes place w.r.t. some context (Winters et al., 2018). For humans, that context includes: 1) features of the environment that can be directly perceived by the dialogue participants and used for comprehending an utterance (e.g. “cup” is interpreted as an object in the immediate physical context); and 2) information that cannot be directly perceived but can affect the interpretation of utterances (e.g. using and interpreting “cup” assumes some shared knowledge of what counts as a “cup”; once a particular cup has been established as salient in particular dialogue, further utterances of “the cup” or “it” will be interpreted as referring to that specific salient cup).
Inspired by this conclusion from pragmatics, in the DL-based language games, we define context as the supervision information involved in the calculation of losses, i.e. the context of a specific input xt, denoted as Cpxtq, is the space of samples involved in the calculation of loss. As for in referential games, the cross entropy loss is calculated based on the distance between the message embedding hLpmq and candidate embedding fLcencpxiq where xi P C, thus Cpxtq “ C Ď X in referential games.
Complexity of context: We assume that the goal of communication is to distinguish a target object from other possibilities in the context (as defined above). It therefore follows that the similarity of distractors in the context to the target influences the communicative precision required, and that greater precision is required to distinguish the target from a more similar distractor. For example, it is relatively easy in natural language to distinguish e.g. a cat from a table (a relatively general label like "cat" or "animal" would suffice), but harder to make fine-grained distinctions between very similar objects e.g. a Scottish Fold Cat and an American Shorthair Cat (a specialist vocabulary or a lengthy description is necessary).
Following the assumption (described verbally above) that a context which contains more similar objects makes the game harder because there are fewer unique features which distinguish the target from the distractors, we first define a neighbour set in k-th degree of a given target xt as Nkpxtq “ txj : dpxt,xjq ď kuwhere d is a distance function that can properly capture the similarity between inputs, e.g Hamming distance in our setting. The complexity of Cpxtq is then defined as the expectation of the probability that Cpxtq contains an object from Nkpxtq, i.e.
Ext rg pCpxtq,Nkpxtqqs ,where g pCpxtq,Nkpxtqq “ " 1, if Dxi P Cpxtq s.t. xi P Nkpxtq 0, otherwise (2)
In our referential games, since the sampling procedure is independent Bernoulli without replacement,
the value of the above expectation is then 1´ ´ |X |´1´|Nkpxtq| |X |´1 ¯|C| which is a monotonically increasing function w.r.t |C| and a fixed k (i.e. larger contexts are more complex since they are more likely to include items which are more similar to the target).
Unpredictability of context: Our notion of unpredictability comes from experimental work with human participants, e.g. Winters et al. (2018). Suppose the aim is to distinguish a striped t-shirt from a number of distractors, and there are two sequences of context: i) three runs of games where distractors are all cups; ii) three runs of games where distractors are a cup, a plain t-shirt, and a pencil. In the first sequence of games, participants would become certain that “t-shirt” is enough for distinguishing the target, whereas in the second sequence participants would learn that a more overspecified utterance (e.g. "striped t-shirt") is required to guarantee comprehension after a failure on the trial involving the plain t-shirt distractor. That is, the context in the first sequence is more predictable than the second. Winters et al. (2018) show that human participants are sensitive to this kind of unpredictability, and adapt their communicative strategies accordingly.
In DL-based games, we refer to the context at the e-th trial, i.e. the e-th training epoch, of a target xt as Cepxtq. Following the above example, the unpredictability of context is then defined as the
proportion of Ce`1pxtq that are not from Cepxtq, i.e.
Ext
»
–
1
|Ce`1pxtq| ÿ xjPCe`1pxtq I pxj R Cepxtqq
fi
fl (3)
In referential game, since the sampling procedure is independent Bernoulli without replacement, the proportion of objects not from Cepxtq in Ce`1pxtq is then simply 1´ |C epxtq| |X | “ 1´ |C| |X | (i.e. smaller contexts are more unpredictable, since contexts on successive trials are more likely to differ in their composition).
More details about the above discussion can be found in Appendix B.

heading: 3.2 MEASURING EXPRESSIVITY IN LANGUAGE GAMES
text: Following the intuition that the different types of games require messages to convey different amount of information about input space X , Mutual Information may seem to be a good candidate measure for expressivity. However, we found that even for two emergent languages that are both deterministic and bijective mapping functions, i.e. they have the same MI value logp|X |q, their expressivity can still be different. Further discussion about MI can be found in Appendix D.
Since it is more challenging to directly quantify the expressivity of emergent languages, we instead focus on the partial orders between them in this work. Considering that the purpose of the emergent communication is to complete tasks, we therefore propose to measure the partial order between expressivity based on game performance. This leads us to a common practice in the transfer learning community (e.g. Pan & Yang, 2009), i.e. train models on source domain but evaluate them on different target domains. Inspired by this practice, here we propose a definition of partial order between the expressivity of two emergent languages LA and LB , i.e. ELA and ELB :
Definition 3.1 (EGLA ą E G LB ). Let g be an instance of language game, and G be a set of language game instances. Then, given G, if the generalisation performance of LA is better than LB on some language games G1, i.e. @g P G1, PgLA ą P g LB , where ∅ Ă G
1 Ď G and P denotes the generalisation performance, while there is no statistically significant difference between the converged generalisation performance of LA and LB on the remaining games, i.e. Pg 1 LA « P g1 LB@g 1 P GzG1 4, we then say that expressivity of LA is higher than LB on G, i.e. EGLA ą E G LB . The metric of generalisation performance could be varied according to different types of games.
Briefly speaking, if one language performs better than the other on some games while they perform approximately the same on the remaining games, we then say the expressivity of that language is higher than the other. Following this definition, there are several possible relationships between the expressivity of two languages LA and LB: 1) EGLA ą E G LB , defined as above; 2) E G LA “ E G LB , if PgLA « P g LB , @g P G; 3) E G LB ą E G LA , defined as above; 4) E G LA is incomparable to E G LB (ELA £ELA), if propositions Dg 1 P G, s.t. Pg 1 LA ą P g1 LB and Dg 2 P G, s.t. Pg 2 LB ą P g2
LA are both true.

heading: 4 PREDICTIONS AND EXPERIMENT DESIGNS

heading: 4.1 PREDICTIONS FROM OUR HYPOTHESIS
text: It has been shown by Chen et al. (2020a) that harder task can lead to better representation with contrastive loss. By using complexity as a measure for the difficulty of games and treating the emergent language as a special kind of discrete representation, we then have the following prediction:
1. higher complexity in games having same contextual unpredictability can facilitate emergent languages having higher expressivity;
4Note that « in this work means that there is no statistically significant difference between means of two sequences.
Meanwhile, following the hypothesis from Winters et al. (2018) that higher contextual unpredictability leads to higher signal autonomy, i.e. more comprehensive information about input space is encoded in the emergent languages, we then have the following prediction:
2. higher unpredictability in games having same contextual complexity can facilitate emergent languages having higher expressivity;
Following the above two predictions, both higher complexity and higher unpredictability can lead to better expressivity. However, with an input space whose size is finite, changing context size always affects the two factors in an inverse way, which leads to our Hypothesis 1 and gives the following prediction:
3. if the size of X is fixed, a language which emerges in a game with moderate complexity and unpredictability should have the highest expressivity.

heading: 4.2 LANGUAGE TRANSFER EXPERIMENT
text: To verify the above three predictions and thus our hypothesis, we evaluate the generalisation performance of languages emerging in various games following the procedure outlined in Procedure 1. Briefly speaking, we first train a pair of speaker and listener to complete a referential game, i.e. a “source game” gs, and obtain an emergent language. We then train a new listener in another referential game, i.e. a “target game” gt, with only 90% of the messages, and use the game performance of this listener on the remaining 10% of messages as the generalisation performance of gs on gt.
Procedure 1: Procedure for the language emergence and transfer experiment Input: A set of source game Gs, a set of target game Gt for every game gis in Gs do
1. initialise a new speaker and listener for gis, and train them to play g i s with the whole X ; 2. after the agents converge on gis, record L “ tpx,mq|x P X u; 3. randomly shuffle and split L into 2 disjoint sets Ltrain and Ltest s.t. |Ltrain| “ 90% ¨ |L|; 4. for every game gjt in Gt do
1. initialise a new listener for gjt ; 2. train the listener with Ltrain to complete gjt ; 3. record the accuracy of listener on Ltest as the generalisation performance of gis on gjt ;
end end
Since our hypothesis concerns the size ofC, we propose to experiment on a series of referential games with varying candidate set size |C| (“referX” where X“ |C|). Meanwhile, as these referential games have both different complexity and unpredictability, we also implement a series of referential games with different |C| but the batches are fixed during training such that there is no unpredictability of the context (“referXf” where X“ |C|). To sum up, in our experiment, Gs “ t“refer2/f”, “refer10/f”, “refer100/f”, “refer1000/f”, “refer2500/f”, “refer5000/f”, “refer7500/f”, “refer10000”u5. Since language games with fixed context are not good simulation of human communication , we keep only the ones having varying batches from Gs in Gt. As a naming convention to allow us to refer easily to the factors that influence a language’s expressivity, we refer to emergent languages by their parameters of their source game, e.g. ‘refer10’6 represents the language which emerges in referential games whose |C| “ 10 (with context varying across epochs). More details about the naming of games and languages can be found in Appendix E.1.

heading: 5 RESULTS & DISCUSSION
text: To alleviate the effect from randomness as much as possible, all the following results are obtained with 6 different random seeds. All values are averaged across the seeds, and the corresponding standard deviation (SD) are also provided (either in this section or appendices).
5There is no “refer10000f” since no unpredictability is possible when |B| “ |C| “ 10, 000 “ |X | 6“referX” is a game while ‘referX’ is an emergent language from it.

heading: 5.1 UNDER FIXED UNPREDICTABILITY, HIGHER COMPLEXITY LEADS TO HIGHER EXPRESSIVITY
text: To verify the Prediction 1, we compare the generalisation performance of games with fixed context, i.e. the unpredictability of their context are the same, on Gt, and the results are shown in Figure 2. Languages which emerge in source games whose contexts have higher complexity consistently perform better on tasks from Gt than those which emerge in source games with lower-complexity contexts, since all lines keep growing with the increase of values on x-axis (i.e. complexity). That is, the generalisation performance is a monotonically increasing function of |C| if there is no unpredictability in the context, which matches with the prediction of our hypothesis.

heading: 5.2 UNDER FIXED COMPLEXITY, HIGHER UNPREDICTABILITY LEADS TO HIGHER EXPRESSIVITY
text: To verify the Prediction 2, we compare the difference between generalisation performance of all games in Gs (“referX”) and their corresponding fixed-batch version (“referXf”). As indicated by that all points in Figure 3 are positive, languages from context with varying objects always perform better than the corresponding fixed-context version on all target games. Since all “referXf” has lower unpredictability of context than the corresponding “referX” games, this indicates that higher unpredictability can unilaterally lead to better generalisation performance of emergent language across various target games, which matches with the prediction of our hypothesis.

heading: 5.3 EXPRESSIVITY IS A TRADE-OFF BETWEEN CONTEXTUAL COMPLEXITY AND UNPREDICTABILITY
text: To verify the Prediction 3, we compare performance for all source games with varying context on all target games, and the results are shown in Figure 4 (see also Appendix E.3 for more details).
As shown in Figure 4, on whichever type of game, the peak of the curves is always among ‘refer1000’, ‘refer2500’, or ‘refer5000’, which means that the best expressivity always emerges in these 3 types of games. Considering that the complexity of context in referential game is a monotonically increasing function of the |C||X | while the contextual unpredictability is a monotonically decreasing of it, the results shown in Figure 4 support our hypothesis, i.e. the expressivity is a trade-off between the contextual complexity and unpredictability.
To be specific, although context of ‘refer2’, ‘refer10’, and ‘refer100’ have high unpredictability, their complexity is low thus the languages have lower expressivity. On the other hand, context of ‘refer7500’ and ‘refer10000’ have high complexity, but expressivity of neither language is the highest due to the high predictability of the context in these games. Unpredictability of context incentivises the agents to encode more information into the messages such that the messages could overcome the uncertainty of contexts and be interpreted in various contexts. Therefore, the three languages (‘refer1000’, ‘refer2500’, and ‘refer5000’) from context with both moderate complexity and unpredictability perform better than the others. To make it more straightforward to compare the expressivity between these languages, we also provide another view of the above results in Figure 9 in Appendix E.3, which shows that ‘refer1000’ £‘refer2500’ « ‘refer5000’ ą ‘refer7500’ « ‘refer10000’ ą ‘refer100’ ą ‘refer10’ ą ‘refer2’. To eliminate the possibility that the above phenomena are caused by the hyperparameters we used in our games, we also run the language transfer experiment with varying communication channel capacity and agent capacity (i.e. the size of hidden layers). As shown in the figures in Appendix F, both ‘refer1000’ and ‘refer2500’ perform better than ‘refer10000’ across varying hyperparameters, which shows that the trade-off phenomenon is consistent over game settings.

heading: 5.4 THE COLLAPSE OF MESSAGE TYPES
text: As we use our contrastive loss instead of the conventional referential loss applied by (e.g. Havrylov & Titov, 2017; Ren et al., 2020), we also compare the behaviours of both loss functions on G1s “ G1t “ t“refer2”, “refer10”, “refer100”u. We discover that the number of message types is some times greatly less than the size of input space. We refer such phenomenon as “message type collapse”, and the mappings that maps several different inputs to a same message type as “degeneracy components”.
While comparing the two loss functions, we observe that contrastive loss is more efficient on removing degenerate components in large-scale games (where |C| ě 100), and can better avoid the collapse of the number of message types. To be specific, as shown in Figure 5a, the numbers of message types collapses to less than 500 on games with conventional referential loss. They, however, would only decrease to roughly 5, 000 on ‘refer10’ and ‘refer1000’ with contrastive loss as shown in Figure 5b. The contrastive loss can also make the training of referential game more stable, as illustrated by the smaller variance in Figure 5b.
Our results indicate that it is necessary to establish a referential game with candidate sets containing enough many distractors to guarantee that the emergent language will be relatively unambiguous. As far as we know, the existing works do not investigate the effects of the size of candidate sets, e.g. Lee et al. (2018) set |C| “ 2, Li & Bowling (2019) set |C| “ 5, and |C| ď 20 is used by Lazaridou et al. (2018). Given our results, our heuristic is that |C| should be higher than either 1, 000 for large input spaces or 110 |X | for smaller ones. We also explore more about the degeneracy degree (as well as structure degree) of the mappings constituting different languages, and the results and discussion are provided in Appendix C.

heading: 6 CONCLUSION & FUTURE WORK
text: To our knowledge, this is the first work exploring the expressivity of emergent languages from language games involving DL-based agents that have different context size. We first proposed a hypothesis about the factors influencing the expressivity of emergent languages, and defined a partial ordering between expressivity of different emergent languages based on the generalisation performance across a set of games. Through a series of experiments on referential games with varying numbers of candidates, we then validated the three predictions from our hypothesis, which furthers indicates that expressivity is indeed a trade-off between the complexity and unpredictability of context in language games. To overcome the memory inefficiency issue caused by the conventional referential loss function, we introduced a contrastive loss into our implementation. In the comparison between this contrastive loss and the referential loss, we found the message type collapse problem, and also showed that using contrastive loss can alleviate this problem.
Since this is a first step towards defining and understanding the expressivity of emergent languages, there are still some questions unanswered by this work. For example, some properties of our emergent languages are surprising given the simplicity of some of our referential games. In the simplest setting (|C| “ 2), we see emergent languages with more than 2, 000 message types, whereas an optimal strategy requires a language consists of only 40 unique messages (since there are only 40 different values for all properties in X and two items in the context always differ on at least one property). Thus, it needs further investigation of how redundancy helps during the communication between agents. More importantly, we lack understanding of the structure of mappings constituting a language, especially when the languages are generated or encoded by neural networks. We believe that the expressivity of languages still needs further exploration in order to maximise the generalisation performance of emergent languages across various tasks.

heading: A MORE DETAILS ABOUT COMPARISON BETWEEN DIFFERENT LOSS FUNCTIONS
text: In this section, we give more details about the comparison between the referential loss used by previous works and the contrastive loss we propose in Section 2.2.
Following the same notations used in Section 2.2, the referential loss used by (following e.g. Havrylov & Titov, 2017) written as:
ppci|xi,mq9 expEphLm, fpxiqq “ exp ´ hLm J ¨ fpxiq ¯
(4)
where hLm is the embedding for the message m obtained from the sequence encoder of listener L, and fp¨q is encoding function of L for candidates x P C. From the above equation, we can see that if a candidate has an embedding closer to message m, the probability mass for predicting it would then be higher. Hence, the predicated probability mass is inversely proportional to the distances, e.g. the dot product in the above equation, between the embeddings of m and all candidates.
The contrastive loss function proposed by Chen et al. (2020a) with τ “ 1 is given as follow:
`i,j “ ´ exp psimpxi,xjqq ř
k Irk‰is exp psimpxi,xkqq (5)
where I is an indicator function. By comparing the above loss function with Equation 4, we find that the aim of them is the same, i.e. make the distance between positive pairs (targets and their corresponding messages) closer while keeping the embeddings for negative pairs (distractors and the messages) as far apart as possible. While negative sampling has been deeply investigated in the self-supervised learning (SSL) community, (e.g. Chen et al., 2020a;b; Grill et al., 2020), it has not been discussed in the emergent communication community yet, thus we simply use all randomly sampled distractors as negative examples. As mentioned in Section 2.2, we need to make the whole input space as candidate set, thus the above contrastive loss which has lower space complexity is preferred.
In the following, we give a bit further derivation to show that Equation 1 is computationally equivalent to Equation 5. By substituting k in the denominator of Equation 5 with j, we can see that:
`i,j “ ´ log exp psimpxi,xjqq ř
j Irj‰is exp psimpxi,xkqq
“ log ř j Irj‰is exp psimpxi,xkqq exp psimpxi,xjqq “ log ř
j Irj‰is exp psimpxi,xkqq exp psimpxi,xjqq ` log exp psimpxi,xiqq exp psimpxi,xiqq
loooooooooooomoooooooooooon
“0
“ log ř j exp psimpxi,xjqq exp psimpxi,xjqq
“ ´ log exp psimpxi,xjqqř j exp psimpxi,xjqq
(6)

heading: B MORE DETAILS ABOUT CONTEXTUAL COMPLEXITY/UNPREDICTABILITY
text: In this section, we give more details about the definition of context and its complexity/unpredictability.
B.1 CONTEXT
As defined in Section 3.1, the context for a target object xt is the space of samples involved in the calculation of its loss. We know that the prediction of the listener is calculated based on the distance between the message received (mpxtq) which is a function of the target input (xt), i.e. softmax pd1 pmpxtq,xdqq where xd is a distractor and d1 is a distance function for embeddings.
Cross entropy loss is then calculated based on softmax function. Thus, we can also write the loss function as Lpmpxtq, txdu; θq. As shown in the equation, the calculation is based on samples from candidate set C. Therefore, in referential game, Cpxtq “ txdu “ C Ď X Ă O.
B.2 COMPLEXITY OF CONTEXT
As defined in Section 3.1, the k-th degree neighbour set is Nkpxtq “ txj : ddpxt,xjq ď ku where k P Z`. As described in Section 2.1, there are 4 features in our synthetic data set and each of them can take 10 different values. Therefore, for a specific target xt, the k in the definition of neighbour set can take only the following 4 values:
• k “ 1: samples in N1pxtq differ only in 1 feature from xt. For the only different feature, there are only 9 possible values a distractor can take. Thus, |N1pxtq| “ 4ˆ 9 “ 36.
• k “ 2: samples from N1pxtq and sample that differ at exactly 2 features from xt. For the later case, there are first `
4 2
˘
“ 12 possible combinations of such two features, and there are 9ˆ9 “ 81 possible samples for each combination. Thus, |N2pxtq| “ 12ˆ81`36 “ 1008.
• k “ 3: samples from N2pxtq and sample that differ at exactly 3 features from xt. For the later case, there are first `
4 3
˘
“ 4 possible combinations of such three features, and there are 9 ˆ 9 ˆ 9 “ 729 possible samples for each combination. Thus, |N3pxtq| “ 4ˆ 729` 1008 “ 3924.
• k “ 4: all samples in X except xt are in this neighbour set, thus |N4pxtq| “ 10000´ 1 “ 9999
Since we use independent Bernoulli sampling, for each draw, the probability to get a sample from Nkpxtq is simply Nkpxtq|X |´1 where |X | ´ 1 is due to excluding xt from X . Meanwhile, since we define Cpxtq as the candidate set in referential games. Therefore, for |Cpxtq| “ |C| draws, the probability of having at one sample from Nkpxtq is:
1´ ˆ 1´ |Nkpxtq||X | ´ 1 ˙|C| “ 1´ ˆ |X | ´ 1´ |Nkpxtq| |X | ´ 1 ˙|C| .
B.3 UNPREDICTABILITY OF CONTEXT
In this section, we first give further explanation about Equation 3 and its simplified form. Since we use Bernoulli sampling for each individual object in candidate set, the overall sampling of candidate set is thus a binomial procedure. As the probability of getting a sample from Cepxtq in X is |C epxtq| |X | , the overall proportion of objects from Cepxtq in Ce`1pxtq is the same, i.e. |C epxtq| |X | . Therefore, the probability of the complementary event, i.e. getting an object not from Cepxtq in Ce`1pxtq, is 1´ |C
epxtq| |X | .

heading: C MORE RESULTS AND DISCUSSION ON EXPRESSIVITY
text: In this section, we provide two more intermediate properties of emergent languages that are also decided by complexity and unpredictability of context, and may influence the expressivity.
C.1 DEGREE OF DEGENERACY AFFECTS BUT DOES NOT FULLY DETERMINE THE EXPRESSIVITY
Inspired by Kirby et al. (2015), the first intermediate factor we explore is the degree of degeneracy (i.e. the degree of ambiguity) of the languages. As a language is defined as a mapping function L : X ÞÑ M, the degree of its degeneracy could be measured by the number of distinct message types.
As shown in the Table 1, in referential languages, the degeneracy degree decreases rapidly with the increase of the contextual complexity of the source games, and reaches a ceiling around |D| ě 1, 000.
There is a positive correlation between the number of message types and expressivity for the languages with low complexity, which indicates that degree of degeneracy could be an intermediate factor that is correlated with the expressivity of these languages. However, the fact that the average number of message types on refer10000 is higher than refer1000, while the expressivity of ‘refer1000’ is higher than ‘refer10000’, i.e. emergent languages having lower level of degeneracy does not necessarily have higher expressivity, indicates that degeneracy degree of one language cannot fully determine its expressivity.
C.2 STRUCTURE DEGREE OF MAPPINGS OF DIFFERENT LANGUAGES
Since the degenerate degree is not the only factor determining expressivity, another factor to be considered is how the mappings of a language L are structured after the training procedure of agents on source games. According to the cardinality of the mappings of L, we can divide them into two disjoint sets: i) one-to-one mappings, i.e. an input is mapped to a unique message; and ii) many-to-one mappings (a.k.a degenerate components), i.e. several inputs are mapped to the same message instance. Between this two types, the structure of one-to-one mappings has been explored under the view of compositionality in the previous works, e.g. (Brighton & Kirby, 2006; Andreas, 2019). However, as illustrated by Chaabouni et al. (2020), a good generalisability does not require a good compositionality, which means that measurements for compositionality are not good predictors for expressivity either. In this work, we only focus on the many-to-one mappings.
Given the objectives of games, for the degenerate components in an emergent language, a message m being mapped to several closely-related inputs could imply that it captures common features among these inputs. Suppose that several inputs XK “ tx1, . . . ,xKu are mapped to the same message m in a converged language L, we hypothesise that the average distances between every pair of messages, e.g. 1|XK | ř
i,jPt1,...,Ku dpxi,xjq, would become smaller after training, compared with their random initial values. Therefore, we compare the averaged distances between meanings of degenerate components as well as the frequency of degenerate components at the beginning and end of training. To make the plots more readable, we only plot the statistics about the top-10 most frequent ambiguous message types, where the frequency of a message type is defined as the number of inputs that are mapped to it in a languages. Results on ‘refer1000’ (one of the most expressive language in our experiments) are shown in Figure 6.
By comparing the data of beginning and end of training in Figure 6b, we can easily observe that the averaged distance decreased throughout the training, which indicates that the degenerate components
actually became more although not fully structured. Another observation we have limited understanding of is that ‘refer1000’ becomes more ambiguous after training (shown by that the red bars representing the statistics at the end of training are lower than the bars representing the statistics at the beginning of training), although its accuracy does improve to 100%. However, limited by the scope of this work, we will leave further exploration of it to future works.

heading: D MUTUAL INFORMATION IS INSUFFICIENT
text: In Section 3.2, we mentioned that MI cannot completely reflect the expressivity of an emergent language. Here, we provide more detailed explanations. On one hand, a higher MI value does not necessarily mean more task-relevant information, e.g. encoding colour in messages is unnecessary for tasks involving only the shapes of inputs although it provides more information. On the other hand, not only the determinacy of the mappings matters for generalising them, but also the structures, e.g. it would be easier for humans to extrapolate compositional languages to novel concepts than holistic ones although they are both unambiguous and therefore have the same MI. In the following paragraphs, we will give more reasoning and empirical evidence to support our claim.
Following the mapping function definition of emergent languages illustrated in Section 2.1, suppose that we get a message type collection M ĂM in some training epoch, the calculation of the mutual information between M and X is given as follows:
IpM |Xq “ ÿ
xPX
ÿ mPM ppx,mq log ppx,mq ppxqppmq ppx,mq “ 1|X |“ ÿ xPX ÿ mPM1 1 |X | log ppx,mq ppxqppmq
“ 1|X | ÿ
xPX
ÿ
mPM log
ppx,mq ppxqppmq “ 1 |X | ÿ
xPX
ÿ
mPM plog ppx,mq ´ log ppxq ´ log ppmqq
ppxq “ 1|X |“ 1 N ÿ
xPX
ÿ
mPM
ˆ
log 1 |X | ´ log 1 |X | ´ log ppmq ˙ “ 1|X | ÿ
xPX
ÿ
mPM p´ log ppmqq
“ ´ ÿ
mPM log ppmq “ ´
ÿ
mPM log
|Lpmq| |M | “ ´ ÿ
mPM plog |Lpmq| ´ log |M |q
“ ÿ
mPM plog |M | ´ log |Lpmq|q
(7)
where ppxq “ 1|X | as x follows a uniform distribution over the input space, ppx,mq “ 1 |X | since every x is mapped to a message, and |Lpmq| is the appearance number of m in one language. By observing the above equation, it is straightforward to see that the MI value is decided by the number of message types, i.e. the degeneracy degree of one language. Therefore, if two emergent languages have approximately the same number of messages types (as shown in Table 1 and degeneracy degree, the MI values for these two languages should also be the same. However, as we illustrate in Section C.1 that degree of degeneracy cannot fully determine the expressivity of emergent languages, we can then deduce that MI cannot fully measure the expressivity of emergent languages.
To provide more empirical evidence to support our claim, we tracked the MI values over training epochs, and the results are shown in the following Figure 7. As we can see, there is no statistically significant difference between the MI values of ‘referX’ (where Xě 1, 000) while we can show that their expressivity is different in Section 5.3.

heading: E LANGUAGE TRANSFER EXPERIMENT RESULTS
text: E.1 NAMING OF GAMES AND LANGUAGES
In this section, we give more details about the naming of games and corresponding languages we used in Section 5 as follows:
• “referX”: this refers to the referential games with candidate sets whose size is X (which itself is an integer), note that we use double quotation marks to indicate that this is a specific type of game. For example, “refer2500” refers to referential games with 2, 500 candidates for listeners.
• ‘referX’: this refers to the emergent languages from “referX”, note that we use apostrophes here in order to differentiate it from the notations of the corresponding games. For example, ‘refer2500’ refers to emergent languages from referential games with 2, 500 candidates for listeners.
• “referXf”: this refers to the referential games with candidate sets whose size is X, but the partition of batches is identical over epochs, thus giving the game a fixed context. For example, “refer2500f” refers to referential games with 2, 500 candidates for listeners, but the batches of data are kept identical through the whole training procedure.
• ‘referXf’: this refers to the emergent languages from “referXf”, note that we use apostrophes here in order to differentiate it from the notations of the corresponding games. For example, ‘refer2500f’ refers to emergent languages from referential games with 2, 500 candidates for listeners with fixed context. Regarding the meaning of “fixed-batch” or “fixed context”, we give an example below where the whole input space is ta, b, c, du and batch size is 2:
– varying batch/context: ta, bu, tc, du is the partition for the 1st epoch; then ta, cu, tb, du is used for the 2nd epoch; and random partitions are used in the following epochs;
– fixed batch/context: whichever epoch it is, ta, bu, tc, du is always used as the partition of context;
• “referX/f”: this equals a “referX” and a “referXf”, both of them have same complexity but different unpredictability. To be more specific, contextual unpredictability of “referX” is higher than “referXf”.
• Gs: the universal set of source games which is defined as t“refer2”, “refer10”, “refer100”, “refer1000”, “refer2500”, “refer5000”, “refer7500”, “refer10000”, “refer2f”, “refer10f”, “refer100f”, “refer1000f”, “refer2500f”, “refer5000f”, “refer7500f”, u.
• Gt: the universal set of target games which is defined as t“refer2”, “refer10”, “refer100”, “refer1000”, “refer2500”, “refer5000”, “refer7500”, “refer10000”u.
E.2 RAW RESULTS OF COMPLEXITY EXPERIMENT
In this section, we provide the raw data of Figure 2 in the following Table 3. Not that although “refer1000f” performs the best on “refer10” than all other languages, we argue this outlier doesn’t influence conclusion of our prediction considering the simplicity of “refer10”.
E.3 MORE RESULTS OF TRADE-OFF EXPERIMENT
In this section, we first provide the complete version of Figure 4, i.e. Figure 8. Since the performance of ‘refer2’, ‘refer10’, and ‘refer100’ are too bad on complex target games, it is very clear that their expressivity are much lower that the rest. Therefore, to emphasise the difference between the other languages, we limit the range of y-axis to r0.7, 1.0s in Figure 8. We also illustrate the partial order between the expressivity of different languages in Figure 9. It is very clear that the ‘refer2’, ‘refer10’, and ‘refer100’ performs worse than the others on referential games with more candidates than their sources. Combining this fact with the fact that ‘refer7500’ and ‘refer10000’ perform worse than ‘refer1000’, ‘refer2500’, and ‘refer5000’ shows that increasing the size of candidate set |C| would not always benefit the expressivity. As for ‘refer1000’, ‘refer2500’, and ‘refer5000’, there is no statistically significant difference between their performance on the simpler referential games, and they intersect on some games, thus their expressivity are approximately the same.
At last, we give the precise values of both Figure 9 and 4 in the following Table 4. All the results are obtained by multiple runs, thus both mean and standard deviation (σ) are given.
To better support our claim, we also provide p-values of testing the statistical significance between the generalisation performance of two different source games across all types of target games in the following Table 5.
F VARYING THE CAPACITY OF CHANNEL AND NETWORK
To verify that our findings are robust to the capacity of the communication channel and agents, we also run some extra experiments on the following different configurations of referential games:
1. larger channel capacity: set the length of messages to 8 and size of token inventory to 20, thus the size of message space becomes 208;
2. larger agent capacity: set the hidden layer size to 128, thus the capacity of both speaker and listener become larger than the original setting (256);
3. larger channel&agent capacity: do the above two changes at the same time.
Since our key findings are about the generalisation performance between refer1000, refer2500, and refer10000, we just run these extra experiments on a game set Gextra “ t‘refer1000’, ‘refer2500’, ‘refer10000’u with multiple runs. The results of configuration 1, 2, and 3 are given in Figure 10, 11, and 12 respectively. It can be observed in all figures that ‘refer1000’ or ‘refer2500’ always perform better than ‘refer10000’ on all kinds of target games, i.e. ‘refer1000’
or ‘refer2500’ both have higher expressivity than ‘refer10000’ . Therefore, we believe the key observation from Figure 9 hold for varying configurations of communication channel and capacity of agents, which means that our conclusions are robust to the configuration of language games.

Review summaries:
This paper studies the expressivity, complexity and unpredictability of emergent languages in referential games. The authors demonstrate that the expressivity of emergent languages is a trade-off between the complexity and unpredictability of the context that the languages are used in. They also introduce a contrastive loss based training method for referential games that alleviates the collapse of message types often seen when using other standard training methods.

The authors investigate what aspects of scenario design affect the resultant communication protocol in emergent communication. Specifically, the authors investigate whether scenario complexity (in terms of having many similar distractors) and scenario unpredictability (in terms of future batches not containing items to previous batches) affect the expressivity (measured in terms of learnability) of the resulting protocol.  Further, the authors show that defining a softmax loss over the entire batch of possible references (dubbed the 'contrastive' loss) outperforms the 'referential' loss used in previous works. 

This paper studies the "expressivity" of emergent language in language games. To my understanding, "expressivity" is empirically the transferring ability of the language to unseen data. In this paper, the authors propose two factors of the underlying language game that can affect the expressivity of emergent language: context complexity and unpredicability. In referential games, the context is the distractor candidates for a sample. Complexity denotes how likely a "close" distractor will be included in the candidates. Unpredictability is how likely the context for a single sample will be different among epochs. This paper proposed hypotheses that both context complexity and unpredicability can improve language expressivity, but these two factors are "contradictory" and we need to have a trade-off between them. The hypotheses are supported by empirical experiment results.

The paper studies the properties of emergent languages in DL-based language games. In particular, they look at referential games where speakers emit messages and listeners need to identify the target object observed by the speaker from some set of candidate objects.    They define the expressivity of an emergent language as the amount of discriminatory information required to encode the inputs so that a listener can correctly decode them. In this setting, complexity refers to the similarity between different objects in a given context. In a context with higher complexity, more similar objects will be present, and more discriminatory information will have to be encoded so that a listener is capable of identifying the correct target. In their definition, the notion of unpredictability can be thought of as how stable the information necessary for encoding is across different trials.    Their primary contribution is to support the hypothesis that the expressivity of emergent language is determined by (and a trade-off between) the complexity and unpredictability of context in language games. The authors introduce a new measure to evaluate expressivity based on partial ordering between languages in terms of their generalization across tasks. They argue that mutual information is not the most appropriate measure to evaluate the expressivity of languages. They propose a contrastive loss which they show helps mitigate the issue of the collapse of message types.