Compositionality and Capacity in Emergent Languages (2020)

Abstract: Recent works have discussed the extent to which emergent languages can exhibit properties of natural languages particularly learning compositionality. In this paper, we investigate the learning biases that affect the efficacy and compositionality in multi-agent communication in addition to the communicative bandwidth. Our foremost contribution is to explore how the capacity of a neural network impacts its ability to learn a compositional language. We additionally introduce a set of evaluation metrics with which we analyze the learned languages. Our hypothesis is that there should be a specific range of model capacity and channel bandwidth that induces compositional structure in the resulting language and consequently encourages systematic generalization. While we empirically see evidence for the bottom of this range, we curiously do not find evidence for the top part of the range and believe that this is an open question for the community.

## introduction compositional language learning in the context of multi agent emergent communication has been extensively studied @xcite @xcite . these works have found that while most emergent languages do not tend to be compositional, they can be guided towards this attribute through artificial task-specific constraints @xcite @xcite . in this paper, we focus on how a neural network, specifically a generative one, can learn a compositional language. moreover, we ask how this can occur without task-specific constraints. to accomplish this, we first define what is a language and what we mean by compositionality. in tandem, we introduce precision and recall, two metrics that help us measure how well a generative model at * these two authors contributed equally. our paper is most similar to @xcite , which showed that compositional language arose only when certain constraints on the agents are satisfied. while the constraints they examined were either making their models memoryless or having a minimal vocabulary in the language, we hypothesized about the importance for agents to have small capacity relative to the number of concepts to which they are exposed. each of @xcite ; @xcite ; @xcite examine the trade-off between expression and compression in both emergent and natural languages, in addition to how that trade-off affects the learners. we differ in that we target a specific aspect of the agent (capacity) and ask how that aspect biases the learning. ## compositional language and learning we consider the problem of learning an underlying language l from a finite set of training strings randomly drawn from it: @xmath0. we assume |d| |l | and our goal is to use d to learn a language l that approximates l as well as possible. we know that there exists an equivalent generator g for l, and so our problem becomes estimating a generator from this finite set rather than reconstructing an entire set of strings belonging to the original language l * . we cast the problem of estimating a generator g as density modeling, in which case the goal is to estimate a distribution p(s). sampling from p(s) is equivalent figure 1: the grid above shows five shapes and five colors. agents with a non-compositional language can use this shared map to communicate "red circle" with only log 2 5 2 = 5 bits. if they instead used a compositional language, it would require log 2 5 = 3 bits for each concept for a total of 6 bits to convey the string. on the other hand, the agent needs 25 memory slots to store the concepts in the former case but only 10 slots in the compositional case. this trade-off exemplifies the motivation for our investigation because it suggests that a key driver of compositionality in language is the capacity of an agent relative to the total number of objects in its environment. evaluation metrics when the language was learned perfectly, any string sampled from the learned distribution p(s) must belong to l . also, any string in l must be assigned a non-zero probability under p(s). otherwise, the set of strings generated from this generator, implicitly defined via p(s), is not identical to the original language l . this observation leads to two metrics for evaluating the quality of the estimated language with the distribution p(s), precision and recall: our setup we simplify and assume that each of the characters in the string @xmath1. while the inputs are ordered according to the sequential concepts, our model encodes them using a bag of words (bow) representation. the speaker f θ is parameterized using a recurrent policy which receives the sequence of concatenated one-hot input tokens of s and converts each of them to an embedding. it then runs an lstm nonautoregressively for l timesteps taking the flattened representation of the input embeddings as its input and linearly projecting each result to a probability distribution over {0, 1}. this results in a sequential bernoulli distribution over l latent variables: the listener g φ receives z and uses a bow representation to encode them into its own embedding space. taking the flattened representation of these embeddings as input, we run an lstm for |n | time steps, each time outputting a probability distribution over the full alphabet σ: to train the whole system end-to-end @xcite via backpropogation, we apply a continuous approximation to z t that depends on a learned temperature parameter τ . we use the 'straight-through' version of gumbel-softmax @xcite to convert the continuous distribution to a discrete distribution for each z t . the final sequence of one hot vectors encoding z is our message, which is passed to the listener g φ . the prior p λ encodes the message z using a bow representation. it gives the probability of z according to the prior (binary) distribution for each z t and is defined as: p λ (z) = l @xmath2. this can be used both to compute the prior probability of a latent string and also to efficiently sample from p λ using ancestral sampling. penalizing the kl divergence between the speaker's distribution and the prior distribution encourages the emergent protocol to use latent strings that are as diverse as possible. hypotheses on compositionality under this framework for language learning, we can make the following observations. if the length of the latent sequence @xmath3, it is impossible for the model to avoid the failure case because there will be |l | -2 l strings in l that cannot be generated from the trained model. consequently, recall cannot be maximized. however, this may be difficult to check using the sample-based estimate as the chance of sampling @xmath4. this is especially true when the gap |l | -2 l is narrow. when @xmath5, there are three cases. the first is when there are not enough parameters θ to learn the underlying compositional grammar, in which case l cannot be learned. the second case is when the number of parameters |θ| is greater than that required to store all the training strings, i.e., |θ| = o(l|d|). here, it is highly likely for the model to overfit as it can map each training string with a unique latent string without having to learn any of l 's compositional structure. lastly, when the number of parameters lies in between these two poles, we hypothesize that the model will capture the underlying compositional structure and exhibit systematic generalization @xcite . ## experiments models and learning the task is to communicate 6 concepts, each of which have 10 possible values with a total dataset size of 10 6 . we train the proposed vae we gradually decrease the number of lstm units from the base model by a factor α ∈ (0, 1]. this is how we control the number of parameters (|θ| and |φ|). we obtain seven models from each of these by varying the length of the latent sequence l from {19, 20, 21, 22, 23, 24, 25}. these were chosen because we both wanted to show a range of bits and because we need at least 20 bits to cover the 10 6 strings in l * ( log 2 10 6 = 20). evaluation: residual entropy our setup allows us to design a metric by which we can check the compositionality of the learned language l by examining how the underlying concepts are described by a string. let p be a sequence of partitions of {1, 2, . . . , l}. we define the degree of compositionality as the ratio between the variabil-ity of each concept c i and the variability explained by a latent subsequence z[p i ] indexed by an associated partition p i . more formally, the degree of compositionality given the partition sequence p is defined as a residual entropy ## conclusion this paper opens the door for a vast amount of follow-up research. all our models were sufficiently large to represent the compositional structure of the language when given sufficient bandwidth. furthermore, while large models did overfit, this was an exception rather than the rule. we hypothesize that this is due to the large number of examples in our language, which forces the model to generalize, but note that there are likely additional biases at play that warrant further investigation.