Compositionality and Generalization In Emergent Languages (2020)

Abstract: Natural language allows us to refer to novel composite concepts by combining expressions denoting their parts according to systematic rules, a property known as compositionality. In this paper, we study whether the language emerging in deep multi-agent simulations possesses a similar ability to refer to novel primitive combinations, and whether it accomplishes this feat by strategies akin to human-language compositionality. Equipped with new ways to measure compositionality in emergent languages inspired by disentanglement in representation learning, we establish three main results: First, given sufficiently large input spaces, the emergent language will naturally develop the ability to refer to novel composite concepts. Second, there is no correlation between the degree of compositionality of an emergent language and its ability to generalize. Third, while compositionality is not necessary for generalization, it provides an advantage in terms of language transmission: The more compositional a language is, the more easily it will be picked up by new learners, even when the latter differ in architecture from the original agents. We conclude that compositionality does not arise from simple generalization pressure, but if an emergent language does chance upon it, it will be more likely to survive and thrive.

## introduction most concepts we need to express are composite in some way. language gives us the prodigious ability to assemble messages referring to novel composite concepts by systematically combining expressions denoting their parts. as interest raises in developing deep neural agents evolving a communication code to better accomplish cooperative tasks, the question arises of how the emergent code can be * contributed equally. endowed with the same desirable compositionality property @xcite @xcite @xcite . this in turn requires measures of how compositional an emergent language is @xcite . compositionality is a core notion in linguistics @xcite , but linguists' definitions assume full knowledge of primitive expressions and their combination rules, which we lack when analyzing emergent languages @xcite . also, these definitions are categorical, whereas to compare emergent languages we need to quantify degrees of compositionality. some researchers equate compositionality with the ability to correctly refer to unseen composite inputs (e.g., @xcite . this approach measures the generalization ability of a language, but it does not provide any insights on how this ability comes about. indeed, one of our main results below is that emergent languages can attain perfect generalization without abiding to intuitive notions of compositionality. topographic similarity has become the standard way to quantify the compositionality of emergent languages (e.g., @xcite @xcite . this metric measures whether the distance between two meanings correlates with the distance between the messages expressing them. while more informative than generalization, topographic similarity is still rather agnostic about the nature of composition. for example, when using, as is standard practice, levenshtein distance to measure message distance, an emergent language transparently concatenating symbols in a fixed order and one mixing deletion and insertion operations on free-ordered symbols can have the same topographic similarity. we introduce here two more "opinionated" measures of compositionality that capture some intuitive properties of what we would expect to hap-pen in a compositional emergent language. one possibility we consider is that order-independent juxtapositions of primitive forms could denote the corresponding union of meanings, as in english noun conjunctions: cats and dogs, dogs and cats. the second still relies on juxtaposition, but exploits order to denote different classes of meanings, as in english adjective-noun phrases: red triangle, blue square. both strategies result in disentangled messages, where each primitive symbol (or sym-bol+position pair) univocally refers to a distinct primitive meaning independently of context. we consequently take inspiration from work on disentanglement in representation learning @xcite to craft measures that quantify whether an emergent language follows one of the proposed composition strategies. equipped with these metrics, we proceed to ask the following questions. first, are neural agents able to generalize to unseen input combinations in a simple communication game? we find that generalizing languages reliably emerge when the input domain is sufficiently large. this somewhat expected result is important nevertheless, as failureto-generalize claims in the recent literature are often based on very small input spaces. second, we unveil a complex interplay between compositionality and generalization. on the one hand, there is no correlation between our compositionality metrics and the ability to generalize, as emergent languages successfully refer to novel composite concepts in inscrutablly entangled ways. (order-dependent) compositionality, however, if not necessary, turns out to be a sufficient condition for generalization. finally, more compositional languages are easier to learn for new agents, including agents that are architecturally different from the ones that evolved the language. this suggests that, while composition might not be a "natural" outcome of the need to generalize, it is a highly desirable one, as compositional languages will more easily be adopted by a large community of different agents. we return to the implications of our findings in the discussion. ## generalization emerges "naturally" if the input space is large we also considered the relation between channel capacity |c| and language emergence. note that |c| ≥ |i| is a prerequisite for successful communication, and a perfectly compositional language could already generalize at the lower |c| = |i| bound. indeed, limiting channel capacity has been proposed as an important constraint for the emergence of compositionality @xcite . however, we find that, when |i| is sufficiently large to support generalization, our deep agents need |c| > |i| in order to even converge at training time. the minimum |c|/|i| ratio across all converging runs for each configuration with |i| ≥ 625 (the settings where we witness generalizing languages) is on average 5.9 (s.d.: 4.4). concretely, this implies that none of our successful languages is as compact as a minimal fullycompositional solution would afford. appendix 8.5 reports experiments focusing, more specifically, on the relation between channel capacity and generalization, showing that it is essential for |c| to be above a large threshold to reach near-perfect accuracy, and further increasing |c| beyond that does not hamper generalization. ## generalization does not require compositionality having established that emergent languages can generalize to new composite concepts, we test whether languages that generalize better are also more compositional. since bosdis and topsim correlate with |c| (appendix 8.6), we compute spearman correlations between test accuracy and compositionality metrics across all converging runs of each (i att , i val , c len , c voc ) configuration separately. surprisingly, in just 4 out of 141 distinct settings the correlation is significant (@xmath0.01) for at least 1 measure. 4 we further analyze the (i @xmath1, i @xmath2, c @xmath3, c @xmath4, as it has a large number of generalizing runs, and it is representative of the general absence of correlation we also observe elsewhere. fig. 2 confirms that even non-compositional languages (w.r.t. any definition of compositionality) can generalize well. indeed, for very high test accuracy (> 98%), we witness a large spread of posdis (between 0.02 and 0.72), bosdis (between 0.03 and 0.4) and topsim (between 0.11 and 0.64). in other words, deep agents are able to communicate about new attribute combinations while using noncompositional languages. we note moreover that even the most compositional languages according to any metric are far from the theoretical maximum (= 1 for all metrics). we observe however that the top-left quadrants of fig. 2 panels are empty. in other words, it never happens that a highly compositional language has low accuracy. to verify this more thoroughly, for each compositionality measure µ, we select those languages, among all converging runs in all con-figurations, that have µ > 0.5, and compute the proportion of them that reaches high test accuracy (> 0.80). we find that this ratio equates 0.90, 0.50, and 0.11 for posdis, bosdis, and topsim respectively. that is, while compositionality is not a necessary condition for generalization, it appears that the strongest form of compositionality, namely posdis, is at least sufficient for generalization. this provides some evidence that compositionality is still a desirable feature, as further discussed in section 6. we gain further insights on what it means to generalize without full compositionality by taking a deeper look at the language shown in red in fig. 2 , that has near-perfect generalization accuracy (>99%), and whose posdis score (0.70), while near the relative best, is still far from the theoretical maximum (we focus on posdis since it is the easiest compositional strategy to qualitatively characterize). as its behavior is partially interpretable, this "medium-posdis" language offered us clearer insights than more strongly entangled cases. we partially analyze one of the latter in appendix 8.7. note that, with (i @xmath5, i @xmath6, a (c @xmath7, c @xmath8. why does the analyzed language use (c @xmath9, we observe that positions 2 and 3 (pos2 and pos3) are respectively denoting attributes 2 and 1 (att2 and att1): pos3 has high mutual information with att1 and low mutual information with att2; the opposite holds for pos2. the remaining position, pos1, could then be simply redundant with respect to the others, or encode noise ignored by receiver. however, this is not quite the case, as the language settled instead for a form of "leaky disentanglement". the two disentangled positions do most of the job, but the third, more entangled one, is still necessary for perfect communication. to see this, consider the ablations in in sum, pos2 and pos3 largely specialized as predictors of att2 and att1, respectively. however, they both have a margin of ambiguity (in pos2 and pos3 there are 96 and 98 symbols effectively used, respectively, whereas a perfect 1-to-1 strategy would require 100). when the symbols in these positions do not suffice, pos1, that can refer to both attributes, serves a disambiguating role. we quantified this complementary function as follows. we define the cue validity of s p (symbol in position p) w.r.t an attribute a as cv (s p , a) = max ā p (ā|s p ), where ā iterates over all possible values of a. cv (s pos1 , att2) is significantly higher in those (train/test) messages where cv (s pos2 , att2) is below average. similarly, cv (s pos1 , att1) is significantly higher in messages where cv (s pos3 , att1) is below average (p ≈ 0 in both cases). we might add that, while there is a huge difference between our simple emergent codes and natural languages, the latter are not perfectly disentangled either, as they feature extensive lexical ambiguity, typically resolved in a phrasal context @xcite . att1 att2 both atts fixing pos1 1 3 0 1 position pos2 1 68 0 pos3 89 1 1 shuffling pos1 89 69 61 1 position pos2 100 3 3 pos3 1 100 1 ## compositionality and ease of transmission the need to generalize to new composite inputs does not appear to constitute a sufficient pressure to develop a compositional language. given that compositionality is ubiquitous in natural language, we conjecture that it has other beneficial properties, making it advantageous once agents chanced upon it. compositional codes are certainly easier to read out by humans (as shown by our own difficulty in qualitatively analyzing highly entangled languages), and we might hypothesize that this ease-of-decoding is shared by computational agents. a long tradition of subject studies and computational simulations has shown that the need to transmit a language across multiple generations or to populations of new learners results in the language being more compositional (e.g., @xcite @xcite @xcite @xcite . our next experiments are closely related to this earlier work, but we adopt the opposite perspective. instead of asking whether the pressure to transmit a language will make it more compositional, we test whether languages that have already emerged as compositional, being easier to decode, are more readily transmitted to new learners. 5 specifically, we run 30 games in the largest input setting (i @xmath10, i @xmath11, varying the channel parameters. we select the pairs of agents that achieved a high level of generalization accuracy (≥0.80). next, following the paradigm of @xcite , we freeze sender, and train a new 5 @xcite established this for hand-crafted languages; we extend the result to spontaneously emerging ones. receiver from scratch. we repeat this process 3 times per game, initializing new receivers with different random seeds. once the newly formed pair of agents is successful on the training set, we measure its test accuracy. we also report speed of learning, measured by area under the epochs vs. training accuracy curve. we experiment with three receiver architectures. the first two, gru (500) and gru (50), are grus with hidden layer sizes of 500 (identical to the original receiver) and 50, respectively. the third is a two-layer feed-forward network (ffn) with a relu non-linearity and hidden size 500. the latter receiver takes the flattened one-hot representation of the message as its input. this setup allows probing ease of language transmission across models of different complexity. we leave the study of language propagation across multiple generations of speakers to future work. results in the same setting studied in section 5 are presented in ## discussion the natural emergence of generalization there has been much discussion on the generalization capabilities of neural networks, particularly in linguistic tasks where humans rely on compositionality (e.g., @xcite 2003; van der @xcite @xcite @xcite @xcite . in our setting, the emergence of generalization is very strongly correlated with variety of the input environment. while this result should be replicated in different conditions, it suggests that it is dangerous to study the generalization abilities of neural networks in "thought experiment" setups where they are only exposed to a small pool of carefully-crafted examples. before concluding that garden-variety neural networks do not generalize, the simple strategy of exposing them to a richer input should always be tried. indeed, even studies of the origin of human language conjecture that the latter did not develop sophisticated generalization mechanisms until pressures from an increasingly complex environment forced it to evolve in that direction @xcite .