Language Evolution and Computation Bibliography

Traditionally, the formation of vocabularies has been studied by agent-based models (primarily, the naming game) in which random pairs of agents negotiate word-meaning associations at each discrete time step. This article proposes a first approximation to a novel question: To what extent is the negotiation of word-meaning associations influenced by the order in which agents interact? Automata networks provide the adequate mathematical framework to explore this question. Computer simulations suggest that on two-dimensional lattices the typical features of the formation of word-meaning associations are recovered under random schemes that update small fractions of the population at the same time; by contrast, if larger subsets of the population are updated, a periodic behavior may appear.

We consider the problem of the evolution of a code within a structured population of agents. The agents try to maximize their information about their environment by acquiring information from the outputs of other agents in the population. A naive use of information-theoretic methods would assume that every agent knows how to interpret the information offered by other agents. However, this assumes that it knows which other agents it observes, and thus which code they use. In our model, however, we wish to preclude that: It is not clear which other agents an agent is observing, and the resulting usable information is therefore influenced by the universality of the code used and by which agents an agent is listening to. We further investigate whether an agent that does not directly perceive the environment can distinguish states by observing other agents' outputs. For this purpose, we consider a population of different types of agents talking about different concepts, and try to extract new ones by considering their outputs only.

This article describes research in which embodied imitation and behavioral adaptation are investigated in collective robotics. We model social learning in artificial agents with real robots. The robots are able to observe and learn each others' movement patterns using their on-board sensors only, so that imitation is embodied. We show that the variations that arise from embodiment allow certain behaviors that are better adapted to the process of imitation to emerge and evolve during multiple cycles of imitation. As these behaviors are more robust to uncertainties in the real robots' sensors and actuators, they can be learned by other members of the collective with higher fidelity. Three different types of learned-behavior memory have been experimentally tested to investigate the effect of memory capacity on the evolution of movement patterns, and results show that as the movement patterns evolve through multiple cycles of imitation, selection, and variation, the robots are able to, in a sense, agree on the structure of the behaviors that are imitated.

I describe the Utrecht Machine (UM), a discrete artificial regulatory network designed for studying how evolution discovers biochemical computation mechanisms. The corresponding binary genome format is compatible with gene deletion, duplication, and recombination. In the simulation presented here, an agent consisting of two UMs, a sender and a receiver, must encode, transmit, and decode a binary word over time using the narrow communication channel between them. This communication problem has chicken-and-egg structure in that a sending mechanism is useless without a corresponding receiving mechanism. An in-depth case study reveals that a coincidence creates a minimal partial solution, from which a sequence of partial sending and receiving mechanisms evolve. Gene duplications contribute by enlarging the regulatory network. Analysis of 60,000 sample runs under a variety of parameter settings confirms that crossover accelerates evolution, that stronger selection tends to find clumsier solutions and finds them more slowly, and that there is implicit selection for robust mechanisms and genomes at the codon level. Typical solutions associate each input bit with an activation speed and combine them almost additively. The parents of breakthrough organisms sometimes have lower fitness scores than others in the population, indicating that populations can cross valleys in the fitness landscape via outlying members. The simulation exhibits back mutations and population-level memory effects not accounted for in traditional population genetics models. All together, these phenomena suggest that new evolutionary models are needed that incorporate regulatory network structure.

This article adopts the category game model, which simulates the origins and evolution of linguistic categories in a group of artificial agents, to evaluate the effect of social structure on linguistic categorization. Based on the simulation results in a number of typical networks, we examine the isolating and collective effects of some structural features, including average degree, shortcuts, and level of centrality, on the categorization process. This study extends the previous simulations mainly on lexical evolution, and illustrates a general framework to systematically explore the effect of social structure on language evolution.

Deacon has suggested that one of the key factors of language evolution is not characterized by an increase in genetic contribution, often known as the Baldwin effect, but rather by a decrease. This process effectively increases linguistic learning capability by organizing a novel synergy of multiple lower-order functions previously irrelevant to the process of language acquisition. Deacon posits that this transition is not caused by natural selection. Rather, it is due to the relaxation of natural selection. While there are some cases in which relaxation caused by some external factors indeed induces the transition, we do not know what kind of relaxation has worked in language evolution. In this article, a genetic-algorithm-based computer simulation is used to investigate how the niche-constructing aspect of linguistic behavior may trigger the degradation of genetic predisposition related to language learning. The results show that agents initially increase their genetic predisposition for language learning—the Baldwin effect. They create a highly uniform sociolinguistic environment—a linguistic niche construction. This means that later generations constantly receive very similar inputs from adult agents, and subsequently the selective pressure to retain the genetic predisposition is relaxed.

In this this article we present a model of social learning of both language and skills, while assuming --insofar possible-- strict autonomy, virtual embodiment and situatedness. This model is built by integrating various previous models on language development and social learning, and it is this integration that, under the mentioned assumptions, provides novel challenges. The aim of the article is to investigate what socio-cognitive mechanisms agents should have in order to be able to transmit language from one generation to the next in such a way that it can be used as a medium to transmit internalised rules that represent skill-knowledge. The knowledge is about how to deal with the familiar poisonous food problem. Simulations reveal under what conditions regarding population structure, agents can successfully solve this problem. In addition to issues relating to perspective taking and mutual exclusivity, we show that agents need to coordinate interactions such that they can establish joint attention in order to form a scaffold for language learning, which in turn forms a scaffold for the learning of rule-based skills. Based on these findings we conclude by hypothesising that social learning at one level forms a scaffold to the social learning at another higher level, thus contributing to the accumulation of cultural knowledge.

We show how cultural selection for learnability during the process of linguistic evolution can be visualized using a simple iterated learning model. Computational models of linguistic evolution typically focus on the nature of, and conditions for, stable states. We take a novel approach and focus on understanding the process of linguistic evolution itself. What kind of evolutionary system is this process? Using visualization techniques, we explore the nature of replicators in linguistic evolution, and argue that replicators correspond to local regions of regularity in the mapping between meaning and signals. Based on this argument, we draw parallels between phenomena observed in the model and linguistic phenomena observed across languages. We then go on to identify issues of replication and selection as key points of divergence in the parallels between the processes of linguistic evolution and biological evolution.

We present the high-level language of relational growth grammars (RGGs) as a formalism designed for the specification of ALife models. RGGs can be seen as an extension of the well-known parametric Lindenmayer systems and contain rule-based, procedural, and object-oriented features. They are defined as rewriting systems operating on graphs with the edges coming from a set of user-defined relations, whereas the nodes can be associated with objects. We demonstrate their ability to represent genes, regulatory networks of metabolites, and morphologically structured organisms, as well as developmental aspects of these entities, in a common formal framework. Mutation, crossing over, selection, and the dynamics of a network of gene regulation can all be represented with simple graph rewriting rules. This is demonstrated in some detail on the classical example of Dawkins' biomorphs and the ABC model of flower morphogenesis: other applications are briefly sketched. An interactive program was implemented, enabling the execution of the formalism and the visualization of the results.

This paper investigates the problem of how language learners decipher what words mean. In most models of language evolution, agents are provided with meanings {\em a priori} and explicitly transfer them to each other as part of the communication process. By contrast, we investigate how successful communication systems can emerge without innate or transferable meanings, and show that this is dependent on the agents developing highly synchronised conceptual systems. We experiment with various cognitive, communicative and environmental factors which have an impact on the likelihood of agents achieving meaning synchronisation. We show that an intelligent meaning creation strategy in a clumpy world leads to the highest level of meaning similarity between agents.

Language is culturally transmitted. Iterated Learning, the process by which the output of one individual's learning becomes the input to other individuals' learning, provides a framework for investigating the cultural evolution of linguistic structure. We present two models, based upon the Iterated Learning framework, which show that the poverty of the stimulus available to language learners leads to the emergence of linguistic structure. Compositionality is language's adaptation to stimulus poverty.

Research in language evolution is concerned with the question of how complex linguistic structures can emerge from the interactions between many communicating individuals. Thus it complements psycholinguistics, which investigates the processes involved in individual adult language processing, and child language development studies, which investigate how children learn a given (fixed) language. We focus on the framework of language games and argue that they offer a fresh and formal perspective on many current debates in cognitive science, including those on the synchronic-versus-diachronic perspective on language, the embodiment and situatedness of language and cognition, and the self-organization of linguistic patterns. We present a measure for the quality of a lexicon in a population, and derive four characteristics of the optimal lexicon: specificity, coherence, distinctiveness, and regularity. We present a model of lexical dynamics that shows the spontaneous emergence of these characteristics in a distributed population of individuals that incorporate embodiment constraints. Finally, we discuss how research in cognitive science could contribute to improving existing language game models.

A growing body of work demonstrates that syntactic structure can evolve in populations of genetically identical agents. Traditional explanations for the emergence of syntactic structure employ an argument based on genetic evolution: syntactic structure is specified by an innate Language Acquisition Device (LAD). Knowledge of language is complex, yet the data available to the language learner is sparse. This incongruous situation, termed the ``poverty of the stimulus'', is accounted for by placing much of the specification of language in the LAD. The assumption is that the characteristic structure of language is somehow coded genetically. The effect of language evolution on the cultural substrate, in the absence of genetic change, is not addressed by this explanation. We show that the poverty of the stimulus introduces a pressure for compositional language structure when we consider language evolution resulting from iterated observational learning. We use a mathematical model to map the space of parameters that result in compositional syntax. Our hypothesis is that compositional syntax cannot be explained by understanding the LAD alone: compositionality is an emergent property of the dynamics resulting from sparse language exposure.

Many artificial life researchers stress the interdisciplinary character of the field. Against such a backdrop, this report reviews and discusses artificial life, as it is depicted in, and as it interfaces with, adjacent disciplines (in particular, philosophy, biology, and linguistics), and in the light of a specific historical example of interdisciplinary research (namely cybernetics) with which artificial life shares many features. This report grew out of a workshop held at the Sixth European Conference on Artificial Life in Prague and features individual contributions from the workshop's eight speakers, plus a section designed to reflect the debates that took place during the workshop's discussion sessions. The major theme that emerged during these sessions was the identity and status of artificial life as a scientific endeavor.

This paper aims to show that linguistics, in particular the study of the lexico-syntactic aspects of language, provides fertile ground for artificial life modelling. A survey of the models that have been developed over the last decade and a half is presented to demonstrate that ALife techniques have a lot to offer an explanatory theory of language. It is argued that this is because much of the structure of language is determined by the interaction of three complex adaptive systems: learning, culture and biological evolution. Computational simulation, informed by theoretical linguistics, is an appropriate response to the challenge of explaining real linguistic data in terms of the processes that underpin human language.

The Baldwin effect has been explicitly used by Pinker and Bloom as an explanation of the origins of language and the evolution of a language acquisition device. This article presents new simulations of an artificial life model for the evolution of compositional languages. It specifically addresses the role of cultural variation and of learning costs in the Baldwin effect for the evolution of language. Results show that when a high cost is associated with language learning, agents gradually assimilate in their genome some explicit features (e.g., lexical properties) of the specific language they are exposed to. When the structure of the language is allowed to vary through cultural transmission, Baldwinian processes cause, instead, the assimilation of a predisposition to learn, rather than any structural properties associated with a specific language. The analysis of the mechanisms underlying such a predisposition in terms of categorical perception supports Deacon's hypothesis regarding the Baldwinian inheritance of general underlying cognitive capabilities that serve language acquisition. This is in opposition to the thesis that argues for assimilation of structural properties needed for the specification of a full-blown language acquisition device.

In the research described here we extend past computational investigations of animal signaling by studying an artificial world in which a population of initially noncommunicating agents evolves to communicate about food sources and predators. Signaling in this world can be either beneficial (e.g., warning of nearby predators) or costly (e.g., attracting predators or competing agents). Our goals were twofold: to examine systematically environmental conditions under which grounded signaling does or does not evolve, and to determine how variations in assumptions made about the evolutionary process influence the outcome. Among other things, we found that agents warning of nearby predators were a common occurrence whenever predators had a significant impact on survival and signaling could interfere with predator success. The setting most likely to lead to food signaling was found to be difficult-to-locate food sources that each have relatively large amounts of food. Deviations from the selection methods typically used in traditional genetic algorithms were also found to have a substantial impact on whether communication evolved. For example, constraining parent selection and child placement to physically neighboring areas facilitated evolution of signaling in general, whereas basing parent selection upon survival alone rather than survival plus fitness measured as success in food acquisition was more conducive to the emergence of predator alarm signals. We examine the mechanisms underlying these and other results, relate them to existing experimental data about animal signaling, and discuss their implications for artificial life research involving evolution of communication.

For many adaptive complex systems information about the environment is not simply recorded in a look-up table, but is rather encoded in a theory, schema, or model, which compresses the information. The grammar of a language can be viewed as such a schema or theory. In a prior study [Teal et al., 1999] we proposed several conjectures about the learning and evolution of language that should follow from these observations: (C1) compression aids in generalization; (C2) compression occurs more easily in a smooth, as opposed to a rugged, problem space; and (C3) constraints from compression make it likely that natural languages eveolve toward smooth string spaces. This previous work found general, if not complete support for these three conjectures. Here we build on that study to clarify the relationship between Minimum Description Length (MDL) and error in our model and examine evolution of certain languages in more detail. Our results suggest a fourth conjecture: that all else being equal, (C4) more complex languages change more rapidly during evolution.

Using communication is not the only cooperative strategy that can evolve when organisms need to solve a problem together. This article describes a model that extends MacLennan and BurghardtOs [37] synthetic ethology simulation to show that using a spatial world in a simulation allows a wider range of strategies to evolve in response to environmental demands. The model specifically explores the interaction between population density and resource abundance and their effect on the kinds of cooperative strategies that evolve. Signaling strategies evolve except when population density is high or resource abundance is low.

We analyze a general model of multi-agent communication in which all agents communicate simultaneously to a message board. A genetic algorithm is used to evolve multi-agent languages for the predator agents in a version of the predator-prey pursuit problem. We show that the resulting behavior of the communicating multi-agent system is equivalent to that of a Mealy finite state machine whose states are determined by the agents' usage of the evolved language. Simulations show that the evolution of a communication language improves the performance of the predators. Increasing the language size (and thus increasing the number of possible states in the Mealy machine) improves the performance even further. Furthermore, the evolved communicating predators perform significantly better than all previous work on similar prey. We introduce a method for incrementally increasing the language size, which results in an effective coarse-to-fine search that significantly reduces the evolution time required to find a solution. We present some observations on the effects of language size, experimental setup, and prey difficulty on the evolved Mealy machines. In particular, we observe that the start state is often revisited, and incrementally increasing the language size results in smaller Mealy machines. Finally, a simple rule is derived that provides a pessimistic estimate on the minimum language size that should be used for any multi-agent problem.

The purpose of this article is to demonstrate that coordinated communication spontaneously emerges in a population composed of agents that are capable of specific cognitive activities. Internal states of agents are characterized by meaning vectors. Simple neural networks composed of one layer of hidden neurons perform cognitive activities of agents. An elementary communication act consists of theollowing: (a) two agents are selected, where one of them is declared the speaker and the other the listener; (b) the speaker codes a selected meaning vector onto a sequence of symbols and sends it to the listener as a message; and finally, (c) the listener decodes this message into a meaning vector and adapts his or her neural network such that the differences between speaker and listener meaning vectors are decreased. A Darwinian evolution enlarged by ideas from the Baldwin effect and DawkinsOmemes is simulated by a simple version of an evolutionary algorithm without crossover. The-ent fitness is determined by success of the mutual pairwise communications. It is demonstrated that agents in the course of evolution gradually do a better job of decoding received messages (they are closer to meaning vectors of speakers) and all agents gradually start to use the same vocabulary for the common communication. Moreover, if agent meaning vectors contain regularities, then these regularities are manifested also in messages created by agent speakers, that is, similar parts of meaning vectors are coded by similar symbol substrings. This observation is considered a manifestation of the emergence of a grammar system in the common coordinated communication.

This article reports on the current state of our efforts to shed light on the origin and evolution of linguistic diversity using synthetic modeling and artificial life techniques. We construct a simple abstract model of a communication system that has been designed with regard to referential signaling in nonhuman animals. We analyze the evolutionary dynamics of vocabulary sharing based on these experiments. The results show that mutation rates, population size, and resource restrictions define the classes of vocabulary sharing. We also see a dynamic equilibrium, where two states, a state with one dominant shared word and a state with several dominant shared words, take turns appearing. We incorporate the idea of the abstract model into a more concrete situation and present an agent-based model to verify the results of the abstract model and to examine the possibility of using linguistic diversity in the field of distributed AI and robotics. It has been shown that the evolution of linguistic diversity in vocabulary sharing will support cooperative behavior in a population of agents.

Language is a shared set of conventions for mapping meanings to utterances. This paper explores self-organization as the primary mechanism for the formation of a vocabulary. It reports on a computational experiment in which a group of distributed agents develop ways to identify each other using names or spatial descriptions. It is also shown that the proposed mechanism copes with the acquisition of an existing vocabulary by new agents entering the community and with an expansion of the set of meanings.

The tasks that animals perform require a high degree of intelligence. Animals forage for food, migrate, navigate, court mates, rear offspring, defend against predators, construct nests, and so on. These tasks commonly require social interaction/cooperation and are accomplished by animal nervous systems, which are the result of billions of years of evolution and complex developmental/learning processes. The Artificial Life (AL) approach to synthesizing intelligent behavior is guided by this biological perspective. In this article we examine some of the numerous open problems in synthesizing intelligent animal behavior (especially cooperative behavior involving communication) that face the field of AL, a discipline still in its infancy.