Language Evolution and Computation Bibliography

The well-established framework of evolutionary dynamics can be applied to the fascinating open problems how human brains are able to acquire and adapt language and how languages change in a population. Schemas for handling grammatical constructions are the replicating unit. They emerge and multiply with variation in the brains of individuals and undergo selection based on their contribution to needed expressive power, communicative success and the reduction of cognitive effort. Adopting this perspective has two major benefits. (i) It makes a bridge to neurobiological models of the brain that have also adopted an evolutionary dynamics point of view, thus opening a new horizon for studying how human brains achieve the remarkably complex competence for language. And (ii) it suggests a new foundation for studying cultural language change as an evolutionary dynamics process. The paper sketches this novel perspective, provides references to empirical data and computational experiments, and points to open problems.

It is well accepted that languages change rapidly in a process of cultural evolution. But some animal communication systems, in particular bird song, also exhibit cultural change. So where exactly is the difference? This article argues that the main selectionist pressure on human languages is not biological-that is, related to survival and fecundity-but instead is linked to producing enough expressive power for the needs of the community, maximizing communicative success, and reducing cognitive effort. The key question to be answered by an "evolutionary linguistics" approach to language is, What are the causal mechanisms sustaining an evolutionary dynamic based on these selection criteria? In other words, what cognitive mechanisms and social interaction patterns are needed, and how do they allow a language to emerge and remain shared, despite profound variation and never-ending change?

Human languages are extraordinarily complex adaptive systems. They feature intricate hierarchical sound structures, are able to express elaborate meanings and use sophisticated syntactic and semantic structures to relate sound to meaning. What are the cognitive mechanisms that speakers and listeners need to create and sustain such a remarkable system? What is the collective evolutionary dynamics that allows a language to self-organize, become more complex and adapt to changing challenges in expressive power? This paper focuses on grammar. It presents a basic cycle observed in the historical language record, whereby meanings move from lexical to syntactic and then to a morphological mode of expression before returning to a lexical mode, and discusses how we can discover and validate mechanisms that can cause these shifts using agent-based models.This article is part of the themed issue 'The major synthetic evolutionary transitions'.

This paper reports recent progress on modeling the grounded co-acquisition of syntax and semantics of locative spatial language in developmental robots. We show how a learner robot can learn to produce and interpret spatial utterances in guided-learning interactions with a tutor robot (equipped with a system for producing English spatial phrases). The tutor guides the learning process by simplifying the challenges and complexity of utterances, gives feedback, and gradually increases the complexity of the language to be learnt. Our experiments show promising results towards long-term, incremental acquisition of natural language in a process of codevelopment of syntax and semantics.

This paper introduces the Syntax Game, a language game for exploring the origins of syntactic structure, specifically phrase structure. We define the game and propose a particular strategy for playing it. We show that this strategy leads to the emergence of a phrase structure grammar through the collective invention, adoption, and alignment of culturally established conventions.

Fluid Construction Grammar (FCG) is an open-source computational grammar formalism that is becoming increasingly popular for studying the history and evolution of language. This demonstration shows how FCG can be used to operationalise the cultural processes and cognitive mechanisms that underly language evolution and change.

Grammatical agreement means that features associated with one linguistic unit (for example number or gender) become associated with another unit and then possibly overtly expressed, typically with morphological markers. It is one of the key mechanisms used in many languages to show that certain linguistic units within an utterance grammatically depend on each other. Agreement systems are puzzling because they can be highly complex in terms of what features they use and how they are expressed. Moreover, agreement systems have undergone considerable change in the historical evolution of languages. This article presents language game models with populations of agents in order to find out for what reasons and by what cultural processes and cognitive strategies agreement systems arise. It demonstrates that agreement systems are motivated by the need to minimize combinatorial search and semantic ambiguity, and it shows, for the first time, that once a population of agents adopts a strategy to invent, acquire and coordinate meaningful markers through social learning, linguistic self-organization leads to the spontaneous emergence and cultural transmission of an agreement system. The article also demonstrates how attested grammaticalization phenomena, such as phonetic reduction and conventionalized use of agreement markers, happens as a side effect of additional economizing principles, in particular minimization of articulatory effort and reduction of the marker inventory. More generally, the article illustrates a novel approach for studying how key features of human languages might emerge.

This is a reply to commentaries on a target article in this volume reviewing models for the cultural evolution of language. Many commentaries amplify positions taken in this article but they also cover novel issues in social evolution and biological evolution, which are briefly ...

The question how a shared vocabulary can arise in a multi-agent population despite the fact that each agent autonomously invents and acquires words has been solved. The solution is based on alignment: Agents score all associations between words and meanings in their lexicons and update these preference scores based on communicative success. A positive feedback loop between success and use thus arises which causes the spontaneous self-organization of a shared lexicon. The same approach has been proposed for explaining how a population can arrive at a shared grammar, in which we get the same problem of variation because each agent invents and acquires their own grammatical constructions. However, a problem arises if constructions reuse parts that can also exist on their own. This happens particularly when frequent usage patterns, which are based on compositional rules, are stored as such. The problem is how to maintain systematicity. This paper identifies this problem and proposes a solution in the form of multilevel alignment. Multilevel alignment means that the updating of preference scores is not restricted to the constructions that were used in the utterance but also downward and upward in the subsumption hierarchy.

The paper surveys recent research on language evolution, focusing in particular on models of cultural evolution and how they are being developed and tested using agent-based computational simulations and robotic experiments. The key challenges for evolutionary theories of language are outlined and some example results are discussed, highlighting models explaining how linguistic conventions get shared, how conceptual frameworks get coordinated through language, and how hierarchical structure could emerge. The main conclusion of the paper is that cultural evolution is a much more powerful process that usually assumed, implying that less innate structures or biases are required and consequently that human language evolution has to rely less on genetic evolution.

Human language is the key evolutionary innovation that makes humans different from other species. And yet, the fabric of language is tangled and all levels of description (from semantics to syntax) involve multiple layers of complexity. Recent work indicates that the global traits displayed by such levels can be analyzed in terms of networks of connected words. Here, we review the state of the art on language webs and their potential relevance to cognitive science. The emergence of syntax through language acquisition is used as a case study to illustrate how the approach can shed light into relevant questions concerning language organization and its evolution.

This chapter introduces the cultural approach towards the question how a symbolic communication system could form in a population of agents. This approach emphasises the role of communication, high level cognition, and social interaction. The chapter introduces briefly the main challenges for working out this approach and which methods could be used to address these challenges.

This chapter gives an overview of different experiments that have been performed to demonstrate how a symbolic communication system, including its underlying ontology, can arise in situated embodied interactions between autonomous agents. It gives some details of the Grounded Naming Game, which focuses on the formation of a system of proper names, the Spatial Language Game, which focuses on the formation of a lexicon for expressing spatial relations as well as perspective reversal, and an Event Description Game, which concerns the expression of the role of participants in events through an emergent case grammar. For each experiment, details are provided how the symbolic system emerges, how the interaction is grounded in the world through the embodiment of the agent and its sensori-motor processing, and how concepts are formed in tight interaction with the emerging language.

Computational and robotic research into symbolic communication systems requires sophisticated tools. This chapter introduces Babel, a tool framework that has been developed to engage in extensive repeatable multi-agent experiments including experiments with embodied robots. A brief example is presented of how experiments are configured in this framework.

Cognitive scientists tend to focus on the behavior of single individuals thinking and perceiving on their own. This is natural because our own introspection provides us with unique insight into this level. However, interacting groups of people also create emergent structures that are not intentionally produced by any individual. People participate in collective behavior patterns that they may not even be able to perceive, let alone understand. Social phenomena such as rumors, linguistic conventions, the emergence of a standard currency, transportation systems, the World Wide Web, resource harvesting, crowding, and scientific establishments arise because of individualsa beliefs and goals, but the eventual form that these phenomena take is rarely the goal of any individual.

This paper is part of an ongoing research program to understand the cognitive and functional bases for the origins and evolution of spatial language. Following a cognitive-functional approach, we first investigate the cross-linguistic variety in spatial language, with special attention for spatial perspective. Based on this language-typological data, we hypothesize which cognitive mechanisms are needed to explain this variety and argue for an interdisciplinary approach to test these hypotheses. We then explain how experiments in artificial language evolution can contribute to that and give a concrete example.

In the 1980s, a lot of ink was spent on the question of symbol grounding, largely triggered by Searle's Chinese room theory (Searle 1980).Searle's article had the advantage ofstirring up discussion about when and how symbols could be about things in the world,whether intelligence involves representations or not,what embodiment means, and under what conditions cognition is embodied.But almost 25 years ofphilosophical discussion have shed little light on the issue, partly because the discussion has been mixed up with emotional arguments whether artificial intelligence (AI) is possible or not.However,today I believe that sufficient progress has been made in cognitive science and AI so that we can say that the symbol grounding problem has been solved. This chapter briefly discusses the issues of symbols,meanings,and embodiment (the main themes ofthe workshop),why I claim the symbol grounding problem has been solved, and what we should do next.

We examine the social prerequisites for symbolic communication by studying a language game embedded within a signaling game, in which cooperation is possible but unenforced. Despite incentives to cheat, and even with persistent cheating, the lateral inhibition dynamics commonly used in language game models remain resilient, as long as sufficient mechanisms are in place to detect deceit. However, unfairly antagonistic strategies can undermine lexical convergence. Symbolic communication, and hence human language, requires a delicate balance between restrained deception and revocable trust, but unconditional cooperation is unnecessary.

Learning the meanings of words requires coping with referential uncertainty - a learner hearing a novel word cannot be sure which aspects or properties of the referred object or event comprise the meaning of the word. Data from developmental psychology suggest that human learners grasp the important aspects of many novel words after just a few exposures, a phenomenon known as fast mapping. Traditionally, word learning is viewed as a mapping task, in which the learner has to map a set of forms onto a set of pre-existing concepts. We criticise this approach and argue instead for a flexible nature of the coupling between form and meanings as a solution to the problem of referential uncertainty. We implemented and tested the model in populations of humanoid robots that play situated language games about objects in their shared environment. Results show that the model can handle an exponential increase in uncertainty and allows scaling towards very large meaning spaces, while retaining the ability to grasp an operational meaning almost instantly for a great number of words. In addition, the model captures some aspects of the flexibility of form-meaning associations found in human languages. Meanings of words can shift between being very specific (names) and general (e.g. 'small'). We show that this specificity is biased not by the model itself but by the distribution of object properties in the world.

It is well known that perspective alignment plays a major role in the planning and interpretation of spatial language. In order to understand the role of perspective alignment and the cognitive processes involved, we have made precise complete cognitive models of situated embodied agents that self-organise a communication system for dialoging about the position and movement of real world objects in their immediate surroundings. We show in a series of robotic experiments which cognitive mechanisms are necessary and sufficient to achieve successful spatial language and why and how perspective alignment can take place, either implicitly or based on explicit marking.

Language can be viewed as a complex adaptive system which is continuously shaped and reshaped by the actions of its users as they try to solve communicative problems. To maintain coherence in the overall system, different language elements (sounds, words, grammatical constructions) compete with each other for global acceptance. This paper examines what happens when a language system uses systematic structure, in the sense that certain meaning-form conventions are themselves parts of larger units. We argue that in this case multi-level selection occurs: at the level of elements (e.g. tense affixes) and at the level of larger units in which these elements are used (e.g. phrases). Achieving and maintaining linguistic coherence in the population under these conditions is non-trivial. This paper shows that it is nevertheless possible when agents take multiple levels into account both for processing meaning-form associations and for consolidating the language inventory after each interaction.

In this paper, we investigate the combination of collaborative tagging and emergent semantics for improved data navigation and search. We propose to use visual features in addition to tags provided by users in order to discover new relationships between data. We show that our method is able to overcome some of the problems involved in navigating databases using tags only, such as synonymy or different languages, spelling mistakes, homonymy, or missing tags. On the other hand, image search based on visual features can be simplified substantially by the use of tags. We present technical details of our prototype system and show some preliminary results.

What processes can explain how very large populations are able to converge on the use of a particular word or grammatical construction without global coordination? Answering this question helps to understand why new language constructs usually propagate along an S-shaped curve with a rather sudden transition towards global agreement. It also helps to analyze and design new technologies that support or orchestrate self-organizing communication systems, such as recent social tagging systems for the web. The article introduces and studies a microscopic model of communicating autonomous agents performing language games without any central control. We show that the system undergoes a disorder/order transition, going trough a sharp symmetry breaking process to reach a shared set of conventions. Before the transition, the system builds up non-trivial scale-invariant correlations, for instance in the distribution of competing synonyms, which display a Zipf-like law. These correlations make the system ready for the transition towards shared conventions, which, observed on the time-scale of collective behaviors, becomes sharper and sharper with system size. This surprising result not only explains why human language can scale up to very large populations but also suggests ways to optimize artificial semiotic dynamics.

We study the exchange of information in collective informa- tion systems mediated by information agents, focusing specifically on the problem of semantic interoperability. We advocate the use of mecha- nisms inspired from natural language, that enable each agent to develop a repertoire of grounded categories and labels for these categories and negotiate their use with other agents. The communication system as well as its semantics is hence emergent and adaptive instead of predefined. It is the result of a self-organised semiotic dynamics where relations be- tween data, labels for the data, and the categories associated with the labels undergo constant evolution.

According to the functional approach to language evolution (inspired by cognitive linguistics and construction grammar), grammar arises to deal with issues in communication among autonomous agents, particularly maximisation of communicative success and expressive power and minimisation of cognitive effort. Experiments in the emergence of grammar should hence start from a simulation of communicative exchanges between embodied agents, and then show how a particular issue that arises can be solved or partially solved by introducing more grammar. This paper shows a case study of this approach, focusing on the issue of search during parsing. Multiple hypotheses arise in parsing when the same syntactic pattern can be used for multiple purposes or when one syntactic pattern partly overlaps with another one. It is well known that syntactic ambiguity rapidly leads to combinatorial explosions and hence an increase in memory use and processing power, possibly to a point where the sentence can no longer be handled. Additional grammar, such as syntactic or semantic subcategorisation or word order and agreement constraints can help to dampen search because it provides information to the hearer which hypotheses are the most likely. The paper shows an operational experiment where avoiding search is used as the driver for the introduction and negotiation of syntax. The experiment is also a demonstration of how Fluid Construction Grammar is well suited for experiments in language evolution.

Children learn language from their parents and then use the acquired system throughout the rest of their life with little change. At least that is commonly assumed. But a recent paper by Galantucci adds to the growing evidence that adults (and children) are able to create and negotiate complex communication systems from scratch and relatively quickly, without a prior model. This raises questions of what cognitive mechanisms are implied in this joint construction of communication systems, and what the implications are for the origins of human language.

Fluid Construction Grammar (FCG) is a new linguistic formalism designed to explore in how far a construction grammar approach can be used for handling open-ended grounded dialogue, i.e. dialogue between or with autonomous embodied agents about the world as experienced through their sensory-motor apparatus. We seek scalable, open-ended language systems by giving agents both the ability to use existing conventions or ontologies, and to invent or learn new ones as the needs arise. This paper contains a brief introduction to the key ideas behind FCG and its current status.

Semiotic dynamics involves the processes whereby groups of people or artificial agents collectively invent and negotiate shared semiotic systems, which they use for communication or information organization. Tagging systems (such as Flickr, CiteULike, del.icio.us, or connotea) offer examples of human semiotic dynamics at work, aided by technologies such as the Internet but also by a new sense of collective action in an increasingly connected world. Semiotic dynamics builds on many earlier AI developments: the insights into and technologies of semantic networks and knowledge representation from the seventies, the ideas on embodiment and grounding from the late eighties, and the perspective of multiagent systems from the nineties. But all these aspects join together into a new vision on intelligence, with the social, collective dynamics of representation-making at the center. These new AI developments don't stand in isolation; they resonate with recent developments in linguistics, psychology, and the mathematical study of networks. This article briefly illustrates the current study of semiotic dynamics, the resulting technologies, and the field's impact on current and future intelligent systems applications. This article is part of a special issue on the Future of AI.

The paper discusses recent developments in web technologies based on collaborative tagging. This approach is seen as a tremendously powerful way to coordinate the ontologies and views of a large number of individuals, thus constituting the most successful tool for distributed cognition so far.

Research into the evolution of grammar requires that we employ formalisms and processing mechanisms that are powerful enough to handle features found in human natural languages. But the formalism needs to have some additional properties compared to those used in other linguistics research that are specifically relevant for handling the emergence and progressive co-ordination of grammars in a population of agents. This document introduces Fluid Construction Grammar, a formalism with associated parsing, production, and learning processes designed for language evolution research. The present paper focuses on a formal definition of the unification and merging algorithms used in Fluid Construction Grammar. The complexity and soundness of the algorithms and their relation to unification in logic programming and other unification-based grammar formalisms are discussed.

This paper reports further progress into a computational implementation of a new formalism for construction grammar, known as Fluid Construction Grammar (FCG). We focus in particular on how hierarchy can be implemented. The paper analyses the requirements for a proper treatment of hierarchy in emergent grammar and then proposes a particular solution based on a new operator, called the J-operator. The J-operator constructs a new unit as a side effect of the matching process.

Several important recent advances in various sciences (particularly biology and physics) are based on complex network analysis, which provides tools for characterizing statistical properties of networks and explaining how they may arise. This article examines the relevance of this trend for the study of human languages. We review some early efforts to build up language networks, characterize their properties, and show in which direction models are being developed to explain them. These insights are relevant, both for studying fundamental unsolved puzzles in cognitive science, in particular the origins and evolution of language, but also for recent data-driven statistical approaches to natural language.

In this paper, efforts to understand the self-organization and evolution of language from a cognitive modelling point of view are discussed. In particular, the paper focuses on efforts that use connectionist components to synthesize some of the major stages in the emergence of language and possible transitions between stages. New technical results are not introduced, but some dimensions for mapping out the research landscape are discussed.

One of the key problems in any language processing system is to establish an adequate syntax/semantics interface, and one of the major requirements of such an interface is that partial meanings contributed by individual words are properly linked with each other based on grammatical constructions. This paper reports how we deal with this problem within the context of Fluid Construction Grammars ({\sc fcg}). {\sc Fcg} is a general unification-based inference engine which has been designed to support experiments in the self-organisation of language in a population of interacting situated embodied agents. The paper focuses on technical details pertaining to the linking problem.

This article proposes a number of models to examine through which mechanisms a population of autonomous agents could arrive at a repertoire of perceptually grounded categories that is sufficiently shared to allow successful communication. The models are inspired by the main approaches to human categorisation being discussed in the literature: nativism, empiricism, and culturalism. Colour is taken as a case study. Although we take no stance on which position is to be accepted as final truth with respect to human categorisation and naming, we do point to theoretical constraints that make each position more or less likely and we make clear suggestions on what the best engineering solution would be. Specifically, we argue that the collective choice of a shared repertoire must integrate multiple constraints, including constraints coming from communication.

Form: The repertoire of speech sounds used in human language is extraordinarily complex. It relies on an articulatory apparatus which needs to be controlled very fast and at a very fine-grained level. It requires the real-time processing of structured sounds despite noise and ...

We study the question of how a local learning algorithm, executed by multiple distributed agents, can lead to a global system of communication. First, the notion of a perfect communication system is defined. Next, two measures of communication system quality are specified. It is shown that maximization of these measures leads to perfect communication production. Based on this principle, local adaptation rules for communication development are constructed. The resulting stochastic algorithm is validated in computational experiments. Empirical analysis indicates that a mild degree of stochasticity is instrumental in reaching states that correspond to accurate communication.

The paper surveys some of the mechanisms that have been demonstrated to be relevant for evolving communication systems in software simulations or robotic experiments. In each case, precursors or parallels with work in the study of artificial life and adaptive behaviour are discussed.

Behaviour-based robotics has always been inspired by earlier cybernetics work such as that of W. Grey Walter. It emphasizes that intelligence can be achieved without the kinds of representations common in symbolic AI systems. The paper argues that such representations might indeed not be needed for many aspects of sensory-motor intelligence but become a crucial issue when bootstrapping to higher levels of cognition. It proposes a scenario in the form of evolutionary language games by which embodied agents develop situated grounded representations adapted to their needs and the conventions emerging in the population.

The paper describes a system for open-ended communication by autonomous robots about event descriptions anchored in reality through the robot's sensori-motor apparatus. The events are dynamic and agents must continually track changing situations at multiple levels of detail through their vision system. We are specifically concerned with the question how grounding can become shared through the use of external (symbolic) representations, such as natural language expressions.

The computational and robotic synthesis of language evolution is emerging as a new exciting field of research. The objective is to come up with precise operational models of how communities of agents, equipped with a cognitive apparatus, a sensori-motor system, and a body, can arrive at shared grounded communication systems. Such systems may have similar characteristics to animal communication or human language. Apart from its technological interest in building novel applications in the domain of human?robot or robot?robot interaction, this research is of interest to the many disciplines concerned with the origins and evolution of language and communication.

We have been conducting large-scale public experiments with artificial robotic agents to explore what the necessary and sufficient prerequisites are for word-meaning pairs to evolve autonomously in a population of agents through a self-organized process. We focus not so much on the question of why language has evolved but rather on how. Our hypothesis is that when agents engage in particular interactive behaviors which in turn require specific cognitive structures, they automatically arrive at a language system. We study this topic by performing experiments based on artificial systems. One such experiment, known as the Talking Heads Experiment, employs a set of visually grounded autonomous robots into which agents can install themselves to play language games with each other.

Integration and grounding are key AI challenges for human-robot dialogue. The author and his team are tackling these issues using language games and have experimented with them on progressively more complex platforms. The results of their work show that language games are a useful way to both understand and design human-robot interaction.

The paper surveys recent work on modeling the origins of communication systems in groups of autonomous distributed agents. It is shown that five principles gleaned from biology are crucial: reinforcement learning, self-organisation, selectionism, co-evolution through structural coupling, and level formation.

Over the past five years, the topic of the origins of language is gaining prominence as one of the big unresolved questions of cognitive science. Artificial Intelligence can make a major contribution to this problem by working out precise, testable models using grounded robotic agents which interact with a real world environment and communicate among themselves or with humans about this environment. A potential side effect op this basic research are new technologies for man-machine interaction based on the negotiation of shared conventions.

Linguistics must again concentrate on the evolutionary nature of language, so that language models are more realistic with respect to human natural languages and have a greater explanatory force. Multi-agent systems are proposed as a possible route to develop such evolutionary models and an example is given of a concrete experiment in the origins and evolution of word-meaning based on a multi-agent approach.

The paper investigates the dynamical properties of spatially distributed naming games. Naming games are interactions between two agents, a speaker and a hearer, in which the speaker identifies an object using a name. Adaptive naming games imply that speaker and hearer update their lexicons to become better in future games. By engaging in adaptive naming games, a coherent shared vocabulary arises through self-organisation in a population of distributed agents. When the agents are spatially distributed, diversity can be shown to arise, and changes, in population contact lead to language changes.

The paper reports on experiments in which robotic agents and software agents are set up to originate language and meaning. The experiments test the hypothesis that mechanisms for generating complexity commonly found in biosystems, in particular self-organisation, co-evolution, and level formation, also may explain the spontaneous formation, adaptation, and growth in complexity of language.

The paper proposes a complex adaptive systems approach to the formation of an ontology and a shared lexicon in a group of distributed agents with only local interactions and no central control authority. The underlying mechanisms are explained in some detail and results of some experiments with robotic agents are briefly reported.

The paper proposes a set of principles and a general architecture that may explain how language and meaning may originate and complexify in a group of physically grounded distributed agents. An experimental setup is introduced for concretising and validating specific mechanisms based on these principles. The setup consists of two robotic heads that watch static or dynamic scenes and engage in language games, in which one robot describes to the other what they see. The first results from experiments showing the emergence of distinctions, of a lexicon, and of primitive syntactic structures are reported.

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.

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.