Language Evolution and Computation Bibliography

Cross-situational learning has recently gained attention as a plausible candidate for the mechanism that underlies the learning of word-meaning mappings. In a recent study, Blythe and colleagues have studied how many trials are theoretically required to learn a human-sized lexicon using cross-situational learning. They show that the level of referential uncertainty exposed to learners could be relatively large. However, one of the assumptions they made in designing their mathematical model is questionable. Although they rightfully assumed that words are distributed according to Zipf's law, they applied a uniform distribution of meanings. In this article, Zipf's law is also applied to the distribution of meanings, and it is shown that under this condition, cross-situational learning can only be plausible when referential uncertainty is sufficiently small. It is concluded that cross-situational learning is a plausible learning mechanism but needs to be guided by heuristics that aid word learners with reducing referential uncertainty.

This methodological article serves as an introduction to this special issue, whose aim is to encourage more and better interaction between empirical studies and computer modeling with regard to the study of language evolution. We argue that research into the field of language evolution is so complex that computer modeling forms an essential tool to generate predictions based on some, possibly descriptive, theory in order to falsify that theory. Falsification should be carried out by comparing the generated predictions with empirical data. In order to improve the quality of the predictions and thus the reliability of the falsification process, we stress the importance of initializing the computer model with empirical data. The papers in this special issue provide some concrete examples and new proposals of applying the suggested methodology.

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.

This article presents a dense database study of child language acquisition from a usage-based perspective and a new analysis of data from an earlier study on simulating language evolution. The new analysis is carried out to show how computer modeling studies can be designed to generate predictions (results) that can be compared quantitatively with empirical data obtained from the dense database studies. Although the comparison shows that the computer model in question is still far from realistic, the study illustrates how to carry out agent-based simulations of language evolution that allow quantitative verification of predictions with empirical data to validate theories on child language acquisition.

In this article I provide a review of studies that have modeled interactions between language evolution and demographic processes. The models are classified in terms of three different approaches: analytical modeling, agent-based analytical modeling, and agent-based cognitive modeling. I show that these approaches differ in the complexity of interactions that they can handle and that the agent-based cognitive models allow for the most detailed and realistic simulations. Thus readers are provided with a guideline for selecting which approach to use for a given problem. The analytical models are useful for studying interactions between demography and language evolution in terms of high-level processes; the agent-based analytical models are good for studying such interactions in terms of social dynamics without bothering too much about the cognitive mechanisms of language processing; and the agent-based cognitive models are best suited for the study of the interactions between the complex sociocognitive mechanisms underlying language evolution.

This study investigates how more advanced joint attentional mechanisms, rather than only shared attention between two agents and an object, can be implemented and how they influence the results of language games played by these agents. We present computer simulations with language games showing that adding constructs that mimic the three stages of joint attention identified in children's early development (checking attention, following attention, and directing attention) substantially increase the performance of agents in these language games. In particular, the rates of improved performance for the individual attentional mechanisms have the same ordering as that of the emergence of these mechanisms in infants' development. These results suggest that language evolution and joint attentional mechanisms have developed in a co-evolutionary way, and that the evolutionary emergence of the individual attentional mechanisms is ordered just like their developmental emergence.

This paper presents computer simulations which investigate the effect that different group sizes have on the emergence of compositional structures in languages. The simulations are based on a model that integrates the language game model with the iterated learning model. The simulations show that compositional structures tend to emerge more extensively for larger groups, which has a positive effect on the time in which the languages develop and on communicative success, which may even have an optimal group size. A mathematical analysis of the time of convergence is presented that provides an approximate explanation of the results. The paper concludes that increasing group sizes among humans could not only have triggered the origins of language, but also facilitated the evolution of more complex languages.

This chapter discusses how Darwin's evolution theory can be applied to explain language evolution at a cultural level. So, rather than viewing language evolution as a process in which the users adapt biologically to learn language, languages themselves adapt to the learning abilities of individuals. Within this framework, languages evolve through variation, competition and selection. Invention and learning are identified as variation mechanisms; learnability, transmission bottlenecks and stability are pressures for competition; and optimising for success is a good selection mechanism. Rather than studying the language development in individual users, this chapter illustrates how artificial multi-agent systems equipped with these principles can self-organise a compositional language from scratch. It is argued that this model offers a good alternative to many standard approaches in linguistics.

This paper illustrates how external (or {\em social}) symbol grounding can be studied in simulations with large populations. We discuss how we can simulate language evolution in a relatively complex environment which has been developed in the context of the New Ties project. This project has the objective of evolving a cultural society and, in doing so, the agents have to evolve a communication system that is grounded in their interactions with their virtual environment and with other individuals. A preliminary experiment is presented in which we investigate the effect of a number of learning mechanisms. The results show that the social symbol grounding problem is a particularly hard one; however, we provide an ideal platform to study this problem.

In this paper we introduce a model for the simulation of language evolution, which is incorporated in the New Ties project. The New Ties project aims at evolving a cultural society by integrating evolutionary, individual and social learning in large scale multi-agent simulations. The model presented here introduces a novel implementation of language games, which allows agents to communicate in a more natural way than with most other existing implementations of language games. In particular, we propose a hybrid mechanism that combines cross-situational learning techniques with more informed feedback mechanisms. In our study we focus our attention on dealing with referential indeterminacy after joint attention has been established and on whether the current model can deal with larger populations than previous studies involving cross-situational learning. Simulations show that the proposed model can indeed lead to coherent languages in a quasi realistic world environment with larger populations.

We present a mathematical model of cross-situational learning, in which we quantify the learnability of words and vocabularies. We find that high levels of uncertainty are not an impediment to learning single words or whole vocabulary systems, as long as the level of uncertainty is somewhat lower than the total number of meanings in the system. We further note that even large vocabularies are learnable through cross-situational learning.

This paper investigates the dynamics of cumulative cultural evolution in a simulation concerning the evolution of language. This simulation integrates the iterated learning model with the Talking Heads experiment in which a population of agents evolves a language to communicate geometrical coloured objects by playing guessing games and transmitting the language from one generation to the next. The results show that cumulative cultural evolution is possible if the language becomes highly regular, which only happens if the language is transmitted from generation to generation.

This paper investigates the effect overextensions of words may have on the emergence of compositional structures in language. The study is done using a recently developed computer model that integrates the iterated learning model with the language game model. Experiments show that overextensions due to an incremental acquisition of meanings on the one hand attracts languages into compositional structures, but on the other hand introduces ambiguities that may act as an antagonising pressure.

Typically, multi-agent models for studying the evolution of perceptually grounded lexicons assume that agents perceive the same set of objects, and that there is either joint attention, corrective feedback or cross-situational learning. In this paper we address these two assumptions, by introducing a new multi-agent model for the evolution of perceptually grounded lexicons, where agents do not perceive the same set of objects, and where agents receive a cue to focus their attention to objects, thus simulating a Theory of Mind. In addition, we vary the amount of corrective feedback provided to guide learning word-meanings. Results of simulations show that the proposed model is quite robust to the strength of these cues and the amount of feedback received.

This paper describes a new model on the evolution and induction of compositional structures in the language of a population of (simulated) robotic agents. The model is based on recent work in language evolution modelling, including the iterated learning model, the language game model and the Talking Heads experiment. It further adopts techniques recently developed in the field of grammar induction. The paper reports on a number of different experiments done with this new model and shows certain conditions under which compositional structures can emerge. The paper confirms previous findings that a transmission bottleneck serves as a pressure mechanism for the emergence of compositionality, and that a communication strategy for guessing the references of utterances aids in the development of qualitatively `good' languages. In addition, the results show that the emerging languages reflect the structure of the world to a large extent and that the development of a semantics, together with a competitive selection mechanism, produces a faster emergence of compositionality than a predefined semantics without such a selection mechanism.

This paper investigates the effect of predefining semantics in modelling the evolution of compositional languages versus allowing agents to develop these semant ics in parallel with the development of language. The study is done using a mult i-agent model of language evolution that is based on the Talking Heads experimen t. The experiments show that when allowing a co-evolution of semantics with lang uage, compositional languages develop faster than when the semantics are predef ined, but compositionality appears more stable in the latter case. The paper con cludes that conclusions drawn from simulations with predefined meanings, which m ost studies use, may need revision.

In this paper we discuss issues relating to modelling language evolution in large populations of autonomous agents that are situated in a realistic environment where they have to evolve and learn means to survive for extended periods of time. As we intend to build such a model in relation to the recently started New Ties project, we identify three major problems that are expected for such a model. The paper proposes some solutions and discusses future directions.

This paper investigates the productive creativity of children in a computational model on the emergence and evolution of compositional structures in language. In previous models it was shown that compositional structures can emerge in language when the language is transmitted from one generation to the next through a transmission bottleneck. Due to the fact that in these models language is transmitted only in a vertical direction where adults only speak to children and children only listen, this bottleneck needs to be imposed by the experimenter. In the current study, this bottleneck is removed and instead of having a vertical transmission of language, the language is -- in most simulations -- transmitted horizontally (i.e. any agent can speak to any other agent). It is shown that such a horizontal transmission scenario does not need an externally imposed bottleneck, because the children face an implicit bottleneck when they start speaking early in life. The model is compared with the recent development of Nicaraguan Sign Language, where it is observed that children are a driving force for inventing grammatical (or compositional) structures, possibly due to a sparseness of input (i.e. an implicit bottleneck). The results show that in the studied model children are indeed the creative driving force for the emergence and stable evolution of compositional languages, thus suggesting that this implicit bottleneck may -- in part -- explain why children are so typically good at acquiring language and, moreover, why they may have been the driving force for the emergence of grammar in language.

This paper investigates the effect of scaling the population size in a simulation studying the emergence and evolution of compositionality in languages. The simulations are based on multi-agent systems that play language games in order to communicate, invent and learn language. The language games are integrated with the iterated learning model that simulates a population turnover, where the population contains adults and children. Experiments show that when the population size is increased, after an initial decrease in performance, the results show an important improvement when the population size is increased further. These results are explained by a hypothesised trade off between increasing difficulties in achieving a conventionalised system and an increased likelihood of finding structures that emerge by chance when the population size increases.

This paper illustrates how the Zipf-Mandelbrot law can emerge in language as a result of minimising the cost of categorising sensory images. The categorisation is based on the discrimination game in which sensory stimuli are categorised at different hierarchical layers of increasing density. The discrimination game is embedded in a variant of the language game model, called the selfish game, which in turn is embedded in the framework of iterated learning. The results indicate that a tendency to communicate in general terms, which is less costly, can contribute to the emergence of the Zipf-Mandelbrot law.

This paper presents arguments for approaching the anchoring problem using {\em semiotic symbols}. Semiotic symbols are defined by a triadic relation between forms, meanings and referents, thus having an implicit relation to the real world.Anchors are formed between these three elements rather than between `traditional' symbols and sensory images. This allows an optimization between the form (i.e. the `traditional' symbol) and the referent. A robotic experiment based on adaptive language games illustrates how the anchoring of semiotic symbols can be achieved in a bottom-up fashion. The paper concludes that applying semiotic symbols is a potentially valuable approach toward anchoring.

This paper presents a first investigation regarding lexicon grounding and evolution under an iterated learning regime without an explicit transfer of reference. In the original iterated learning framework, a population contains adult speakers and learning hearers. In this paper I investigate the effects of allowing both adults and learners to take up the role of speakers and hearers with varying probabilities. The results indicate that when adults and learners can be selected as speakers and hearers, their lexicons become more similar but at the cost of reduced success in communication.

The field of language evolution and computation may benefit from using efficient and robust simulation tools that are based on widely exploited principles within the field. The tool presented in this paper is one that could fulfil such needs. The paper presents an overview of the tool -- THSim v3.2 -- and discusses some research questions that can be investigated with it.

This paper presents a new computational model for studying the origins and evolution of compositional languages grounded through the interaction between agents and their environment. The model is based on previous work on adaptive grounding of lexicons and the iterated learning model. Although the model is still in a developmental phase, the first results show that a compositional language can emerge in which the structure reflects regularities present in the population's environment.

This paper investigates how different modes of social interactions influence the bootstrapping and evolution of lexicons. This is done by comparing three language game models that differ in the type of social interactions they use. The simulations show that the language games which use either joint attention or corrective feedback as a source of contextual input are better capable of bootstrapping a lexicon than the game without such directed interactions. The simulation of the latter game, however, does show that it is possible to develop a lexicon without using directed input when the lexicon is transmitted from generation to generation.

This paper investigates how different types of non-verbal input influence the bootstrapping and evolution of lexicons. This is done by comparing three language game models that differ in the type of input they use. The simulations show that the language games that use either joint attention or corrective feedback as a source of contextual input are better capable of bootstrapping a lexicon than the game without such precise and directed input. The simulation of the latter game, however, does show that it is possible to develop a lexicon without using directed input when the lexicon is transmitted from generation to generation.

This paper presents an approach to solve the symbol grounding problem within the framework of embodied cognitive science. It will be argued that symbolic structures can be used within the paradigm of embodied cognitive science by adopting an alternative definition of a symbol. In this alternative definition, the symbol may be viewed as a structural coupling between an agent's sensorimotor activations and its environment. A robotic experiment is presented in which mobile robots develop a symbolic structure from scratch by engaging in a series of language games. In this experiment it is shown that robots can develop a symbolic structure with which they can communicate the names of a few objects with a remarkable degree of success. It is further shown that, although the referents may be interpreted differently on different occasions, the objects are usually named with only one form.

In this paper an experiment is presented in which two mobile robots develop a shared lexicon of which the meanings are grounded in the real world. The robots start without a lexicon nor shared meanings and play language games in which they generate new meanings and negotiate words for these meanings. The experiment tries to find the minimal conditions under which verbal communication may begin to evolve. The robots are autonomous in terms of computing and cognition, but they are otherwise far simpler than most, if not all animals. It is demonstrated that a lexicon nevertheless can be made to emerge even though there are strong limits on the size and stability of this lexicon.

This paper presents a series of experiments in which two mobile robots develop a shared lexicon of which the meaning is grounded in the real world. The experiments investigate the impact of non-verbal communication on lexicon formation. Non-verbal communication is used to establish joint attention or to evaluate feedback. The experiments implement adaptive language games in which two agents try to communicate some real world object. When the agents fail, they can adapt their memory in order to improve performance on future occasions. As the experimental results show, the quality of the evolved lexicon is better when feedback is used rather than joint attention.

The thesis presents research that investigates how two mobile robots can develop a shared lexicon from scratch of which the meaning is grounded in the real world. It is shown how the robots can solve the symbol grounding problem in a particular experimental setup. The model by which the robots do so is explained in detail. The experimental results are presented and discussed.

The paper addresses the question how a group of physically embodied robotic agents may origi- nate meaning and language through adaptive language games. The main principles underlying the approach are sketched as well as the steps needed to implement these principles on physical agents. Some experimen- tal results based on this implementation are presented.