The Emergence of Compositional Languages in Multi-entity Referential Games: from Image to Graph Representations (2024)

Abstract: To study the requirements needed for a human-like language to develop, Language Emergence research uses jointly trained artificial agents which communicate to solve a task, the most popular of which is a referential game. The targets that agents refer to typically involve a single entity, which limits their ecological validity and the complexity of the emergent languages. Here, we present a simple multi-entity game in which targets include multiple entities that are spatially related. We ask whether agents dealing with multi-entity targets benefit from the use of graph representations, and explore four different graph schemes. Our game requires more sophisticated analyses to capture the extent to which the emergent languages are compositional, and crucially, what the decomposed features are. We find that emergent languages from our setup exhibit a considerable degree of compositionality, but not over all features.

## introduction in language emergence research, jointly trained artificial agents develop their own communication protocol to solve a task, the most popular of which is the referential game -a version of the classic signaling game @xcite . in such games, a sender agent composes a message to communicate about a target, and a receiver agent tries to identify which target was the sender referring to, by selecting it from a set of items (e.g. @xcite @xcite . this setting has shown to be a successful environment for a communication protocol to emerge from scratch @xcite . agents learn to successfully communicate about target items which represent entities, e.g. chairs, bicycles, dogs, or cats. however, while accurate communication appears to be achieved with relative ease in these systems, the emerged languages miss some of the interesting properties of natural language. in particular, human languages exhibit a strong bias towards compositionality, a type of systematicity according to which parts of a message (for example morphemes, words, or phrases) systematically refer to parts of the input @xcite . crucially, choices in the representation of input items have an influence on the emergence of compositionality, such that image-based setups have been less successful than settings that use manually coded feature-based vectors @xcite . notwithstanding the current successes of the systems described above, a relevant limitation of such games is that they are trained to communicate about single entities e.g., one cat or one bicycle) or higher-level descriptions of single entities (or concepts, @xcite . while this simplification has proved to be useful to investigate basic requirements for emergence of a communication protocol, clearly single entities alone are not sufficient to represent world knowledge, let alone support communication about any state of affairs that goes beyond entity naming. however, introducing multiple entities in a referential game is not trivial, in particular when it comes to input representations. to the best of our knowledge, only @xcite addressed this challenge using items involving two entities (agent and patient), but their agents require supervised training over a hand-crafted miniature language. one reason behind the complexity of a multientity game comes from the input representations: although image-based input would be naturally suited to seemingly represent multiple entities, compositionality does not seem to emerge easily in such systems. on the other hand, feature-based vectors do exhibit more tendency to encourage compositional languages, but they do not scale gracefully to represent multiple entities. to tackle this challenge, we propose the use of graphs to represent inputs. graphs are naturally suited for encoding relationships between multiple entities, which can coexist within the same graph. like feature-based vectors, they have the advantage of being disentangled (i.e. the structure of the input is explicit), hence a priori they have potential to encourage the emergence of compositionality. and like images, neural graph embeddings scale gracefully, such that graphs of different sizes can be seamlessly integrated within a vector of fixed size. since there is no standard way to encode information in a graph, we propose four different schemas and analyze their relative contributions to accuracy of communication and compositionality. to perform our experiments, we present a new, simple game in which two entities coexist in a 4positional grid. these entities are spatially related, such that one may be, for example, above or to the left of the other. we choose spatial relations because they can also be visually represented. thanks to this, our game allows us to compare graph representations, which have a higher level of abstraction, to image-based input, which is a lower-level representation. loosely speaking, these representations can be interpreted as conceptual (in the case of graphs) and perceptual (in the case of images). albeit simple, our representations incorporate an additional level of complexity by introducing multiple entities, as well as the relation between them. this entails that the analyses of the emergent language also comes with new challenges, since there are multiple ways in which a language could exhibit a degree of compositionality -depending on which features of the input are decomposed. to address this challenge, we present a methodology for tracking compositionality that builds on previously used metrics, but applies an extension that allows for more fine-grained analyses. our work combines these three ingredients (a new multi-entity game, a variety of input representations, and an extended analysis method) to explore the requirements for communication success and compositionality to emerge in a scenario involving multiple entities. ## background in this section we briefly introduce referential games and agent architectures, with special focus on input representations -since that is particularly relevant to our work. ## multi-entity game we postulate that language emergence setups need to eventually account for games that represent more than one entity, such that more complex languages can potentially emerge -after all, some of the most common constructions in human language use involve a subject and (at least) one object. however, extending current referential games to handle multi-entity input is not trivial, as we first need to explore which type of input representations support multi-entity representation while ensuring commu-nication success and favoring compositionality. we now present our proposal of a simple multi-entity referential game and describe the input representations we experiment with. ## experimental setup we implement our setup in python, using the egg library @xcite for the agents and pytorch-geometric @xcite for graph neural networks. each experiment is performed with five different random seeds. data. we use a collection of 50 black shapes (see appendix a), which we combine into 4-positional grids. from 14700 distinct items, we generate 11760 game rounds for training and 2940 game rounds for testing. ## communication success communication success measures how well the two agents successfully solve the game together, i.e. how often the receiver correctly selected the target described by the sender. it is computed as the ratio of the number of successful game rounds over the total number of game rounds played (see, e.g. lazaridou et al. (2017)). this is the first metric that requires attention because if the communication success rate is low, the emergent language is not helping to solve the game, and is therefore uninteresting to us. obviously, this metric is influenced by the difficulty of the game, which we can control with the number of distractors (such that a greater number of distractors leads to more difficult games). figure 2 shows communication success rate for different game sizes and maximum message lengths. as we can see, the rate drops when the game size increases. nevertheless, even when there are 19 distractors, the (test) rate is often higher than 70%, much higher than the 5% rate that would be achieved with random guessing. this demonstrates the effectiveness of our agents as well as the used input representations. overall the different input representations behave similarly in terms of communication success, although differences start to become noticeable for games with more distractors. the image and the graph-edge representations perform best overall, with the graph-edge representation performing better in larger game sizes. we also note that graph-functor and graph-leaves exhibit more variance between model runs, possibly due to the use of position-nodes (which is what distinguishes these two type of graphs from other graph encodings). ## compositionality we are now ready to ask whether the emergent languages show any degree of compositionality. this is not a trivial question to answer, given that the messages are not readily interpretable to humans. the widespread approach in the field is to use a metric called topographic similarity (topsim from here on; @xcite . the goal of this metric is to capture the similarity between the topologies of two sets of items. mathematically, the topology of a set of items i is characterized by the distance metric d i which measures dissimilarity between every two items. similarly, we use the distance metric d m to characterize message dissimilarity for the set of messages m. the topsim metric is calculated as the negative spearman correlation ρ between the two lists (d i (i i , i j )) and (d m (a s (i i ), a s (i j ))) where i i , i @xmath0. an attractive property of topsim is that it is agnostic to the type of input, as long as it can be characterized by a distance metric. a common choice is cosine distance for d i and minimum edit distance for d m (see e.g. @xcite ). here, we note that we can actually make use of this degree of freedom to further explore the type of compositionality (or lack of) of the emergent languages. as explained above, topsim measures the topological similarity between two sets; therefore, if one set is compositional due to factor a, a high topsim value should imply that the other set should also be compositional due to the same factor a. in other words, topsim will only capture compositionality in the message space if d i (i) provides a topological ordering of items that is based on the same feature(s) that were decomposed in the messages. this has implications for the choice of i and d i ; in particular, we observe that the usual method applied over image input (cosine distance over image embeddings) is not guaranteed to capture compositionality over conceptual properties of the input, since the items that are deemed more similar according to cosine distance may be so due to coincidences at the raw pixel level (which could even be noise, @xcite . thus, we opt for a choice of i that allows us to interpret what are the compositional features that we are measuring -as done in other work that uses semantic attributes for i @xcite . to this aim, we design a script-like representation that can be easily manipulated to incorporate or remove certain features, thus influencing the topology created with d i (for which we use hamming distance). we refer to this representation as item-script, and provide examples in the upcoming sections and in appendix c. ## language evolution the languages emerging from our agents evolve over time. figure 5 shows the evolving compositionality (i.e. topsim for shape-disentangled and position2d-disentangled item-script) and communication success of five models trained on the same game. as training progresses, we observe an increase in communication success. interestingly, even though we observed a preference to decompose positions rather than shapes for image-based and graphfunctor/leaves/posattr-based agents, this analysis reveals that this preference is not constant over time; in fact, the composition over position decreases over time while compositionality over shapes increases, albeit slightly. ## discussion altogether, our analyses suggest that our games are more challenging than traditional single-entity games, at least in terms of analyzing compositionality. as we showed in section 6, multiple factors can potentially be decomposed; in particular, shape and position. in our game, shape is the identity factor of entities (that is, that is the only property that is distinct between entities), while position can be seen as an attribute of an entity (such that the same entity can be in different positions accross targets). in a game with a single entity, compositionality would be limited to decomposing shape and position. however, in a multi-entity game, this does not suffice, since even a perfectly compositional language requires an additional mechanism to link each entity (shape) with their positional attribute. in natural languages, this may be achieved with word order or case marking. the moderate scores topsim scores that we observe for disentangled conditions (paired with the high accuracy scores) suggest that some initial instances of this basic level of syntax may be emerging, but the higher scores for position entangled indicate that agents occasionally conflate the positions of both entities in one single token. in our view, this showcases that multi-entity games provide an interesting and linguistically relevant challenge to tackle. we expected that graph representations, which can transparently represent which features (positions) connect to which entities (shapes), would be better suited for the emergence of this basic level of syntax; however, in our simulations we found that images are similarly competitive (and even better than some of the graph schemes). this is not entirely surprising in the case of compositionality over entangled positions (for which we do not anticipate any advantage from graphs) but it is somewhat unexpected for disentangled positions. we must note that the simplicity of our grid-based targets may have obscured the advantage of providing structure representations in graphs, since the image model could likely learn a similarly structured representation from our black-and-white images with clearly separated shapes. thus, it is entirely possible that our current setup did not manage to fully exploit advantages of graphs. we expect these become more relevant when extending our game to more visually complex targets holding a varying number of entities per target.