Language Evolution and Computation Bibliography

Some recent Artificial Life models have attempted to explain the origin of linguistic diversity with varying conclusions and explanations. We posit, contrary to some existing Artificial Life work, that linguistic diversity should naturally emerge in spatially organised populations of ...

The naming game is a formal mechanism that describes the development of a lexicon in a society of culturally interacting agents. We will here use a cellular automaton version of this game to study the influence of an extra-linguistic structure over the evolution of the lexicon ...

What permits some systems to evolve and adapt more effectively than others? Gell-Mann [3] has stressed the importance of ``com- pression'' for adaptive complex systems. Information about the environ- ment is not simply recorded as a look-up table, but is rather compressed in a theory or schema. Several conjectures are proposed: (I) compression aids in generalization; (II) compression occurs more easily in a ``smooth'', as opposed to a ``rugged'', string space; and (III) constraints from com- pression make it likely that natural languages evolve towards smooth string spaces. We have been examining the role of such compression for learning and evolution of formal languages by artificial agents. Our sys- tem does seem to conform generally to these expectations, but the trade- oobetween compression and the errors that sometimes accompany it need careful consideration.

This paper presents a system that simulates the emergence of realistic vowel systems in a population of agents that try to imitate each other as well as possible. Although none of the agents has a global view of the language, and none of the agents does an explicit optimization, a coherent system of vowels emerges that happens to be optimized for acoustic distinctiveness. The results presented here fit in and confirm the theory of Luc Steels [Steels 1995, 1997, 1998] that views languages as a complex dynamic system and the origins of language as the result of self-organization and cultural evolution.

This paper argues that developmental patterns in child language be taken seriously in computational models of language acquisition, and proposes a formal theory that meets this criterion. We first present developmental facts that are problematic for statistical learning approaches which assume no prior knowledge of grammar, and for traditional learnability models which assume the learner moves from one UG-defined grammar to another. In contrast, we view language acquisition as a population of grammars associated with 'weights', that compete in a Darwinian selectionist process. Selection is made possible by the variational properties of individual grammars; specifically, their differential compatibility with the primary linguistic data in the environment. In addition to a convergence proof, we present empirical evidence in child language development, that a learner is best modeled as multiple grammars in co-existence and competition.

The Americas harbor a very great diversity of indigenous language stocks, many more than are found in any other continent. J. Nichols [(1990) Language 66, 475-521] has argued that this diversity indicates a great time depth of in situ evolution. She thus infers that the colonization of the Americas must have begun around 35,000 years ago. This estimate is much earlier than the date for which there is strong archaeological support, which does not much exceed 12,000 years. Nichols' assumption is that the diversity of linguistic stocks increases linearly with time. This paper compares the major continents of the world to show that this assumption is not correct. In fact, stock diversity is highest in the Americas, which are by consensus the youngest continents, intermediate in Australia and New Guinea, and lowest in Africa and Eurasia where the time depth is greatest. If anything, then, after an initial radiation, stock diversity decreases with time. A simple model is outlined that predicts these dynamics. It assumes that early in the peopling of continents, there are many unfilled niches for communities to live in, and so fissioning into new lineages is frequent. As the habitat is filled up, the rate of fissioning declines and lineage extinction becomes the dominant evolutionary force.

The emergence of language was a defining moment in the evolution of modern humans. It was an innovation that changed radically the character of human society. Here, we provide an approach to language evolution based on evolutionary game theory. We explore the ways in which protolanguages can evolve in a nonlinguistic society and how specific signals can become associated with specific objects. We assume that early in the evolution of language, errors in signaling and perception would be common. We model the probability of misunderstanding a signal and show that this limits the number of objects that can be described by a protolanguage. This 'error limit' is not overcome by employing more sounds but by combining a small set of more easily distinguishable sounds into words. The process of 'word formation' enables a language to encode an essentially unlimited number of objects. Next, we analyze how words can be combined into sentences and specify the conditions for the evolution of very simple grammatical rules. We argue that grammar originated as a simplified rule system that evolved by natural selection to reduce mistakes in communication. Our theory provides a systematic approach for thinking about the origin and evolution of human language.

Much current discussion of the evolution of language has concerned the emergence of a stage in which single vocal or gestural signals were used symbolically. Assuming the existence of such a stage, the present review decomposes the emergence of modern language into nine partially ordered steps, each of which contributes to precision and variety of expression. Bickerton's proposed `protolanguage' falls somewhere in the middle of this succession. In addition to the by-now accepted evidence from language learning, language disorders, and ape language experiments, modern languages provide evidence of these stages of evolution through the presence of detectable `fossils' in vocabulary and grammar.

We explore how evolutionary game dynamics have to be modified to accomodate a mathematical framework for the evolution of language. In particular, we are interested in the evolution of vocabulary, that is associations between signals and objects. We assume that successful communication contributes to biological fitness: individuals who communicate well leave more offspring. Children inherit from their parents a strategy for language learning (a language acquisition device). We consider three mechanisms whereby language is passed from one generation to the next: (i) parental learning: children learn the language of their parents; (ii) role model learning: children learn the language of individuals with a high payoff; and (iii) random learning: children learn the language of randomly chosen individuals. We show that parental and role model learning outperform random learning. Then we introduce mistakes in language learning and study how this process changes language over time. Mistakes increase the overall efficacy of parental and role model learning: in a world with errors evolutionary adaptation is more efficient. Our model also provides a simple explanation why homonomy is common while synonymy is rare.

The computer simulation of language change in a finite, structured population which was presented in an earlier paper ('Using Social Impact Theory to simulate language change', Lingua 108, 95-117, 1999), is here extended to speech communities of different sizes. On the basis of the results it is proposed (a) that language change may be faster in small communities; (b) that linguistic borrowing is one sense more likely in small communities; and (c) that the evolution of linguistically marked structures is more likely in small communities. It is argued that these three generalisations could be used to make sense of the different patterns of linguistic diversity observed in the Old and New Worlds, and the distribution of marked word orders in the world's languages.

This paper presents a framework for simulating language change in social networks derived from Social Impact Theory. In this framework, the language learner samples the speech of individuals from right across his speech community, though he may weight their input differentially according to their social position. This conceptualisation is argued to be more realistic than that provided by other models. Computer simulations are used to investigate the effects on language change of different social structures and biases in language acquisition. From the results of these simulations, it is argued that the fundamental engine driving language change is the combination of inherent variation in language acquisition and differences between individuals in local social influence. Functional biases attaching to different linguistic variants influence the direction of language change.

Abstract Social behaviour and in particular social learning are key mechanisms for the cohesion and evolu tion of primate societies. Similarly, social skills might be desirable for artificial agents who are expected to interact with other natural or artificial agents. We view ...

Human language is a unique ability. It sits apart from other systems of communication in two striking ways: it is syntactic, and it is learned. While most approaches to the evolution of language have focused on the evolution of syntax, this paper explores the computational issues that arise in shifting from a simple innate communication system to an equally simple one that is learned. Associative network learning within an observational learning paradigm is used to explore the computational difficulties involved in establishing and maintaining a simple learned communication system. Because Hebbian learning is found to be sufficient for this task, it is proposed that the basic computational demands of learning are unlikely to account for the rarity of even simple learned communication systems. Instead, it is the problem of *observing* that is likely to be central -- in particular the problem of determining what meaning a signal is intended to convey.

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 paper describes computer simulations that investigate the role of self-organisation in explaining the universals of human vowel systems. It has been observed that human vowel systems show remarkable regularities, and that these regularities optimise acoustic distinctiveness and are therefore adaptive for good communication. Traditionally, universals have been explained as the result of innate properties of the human language faculty, and therefore need an evolutionary explanation. In this paper it is argued that the regularities emerge as the result of self-organisation in a population and therefore need not be the result of biological evolution. \\ The hypothesis is investigated with two different computer simulations that are based on a population of agents that try to imitate each other as well as possible. Each agent can produce and perceive vowels in a human-like way and stores vowels as articulatory and acoustic prototypes. The aim of the agents is to imitate each other as well as possible. \\ It will be shown that successful repertoires of vowels emerge that show the same regularities as human vowel systems.

The origin of phonological systems is examined from the paradigm of self-organization. We claim that phonological systems could have emerged as the product of self-organizing processes. Self-organization may have facilitated the evolution of structures within the sounds that humans were able to produce. One of the main points of the paper concerns the identification of the processes which could account for the self-organized behavior of sound systems used in languages spoken by humans. In this paradigm, phonological systems or sound patterns of human languages are emergent properties of these systems rather than properties imposed by some external influence. Regulations are defined as the constraints that adjust the rate of production of the elements of a system to the state of the system and of relevant environmental variables. The main operators of these adjustments are feedback loops. Two types of processes can be distinguished in regulatory networks, homeostatic and epigenetic. Since the origin of sound patterns, of human languages, is in the vocal tract constraints, we make the hypothesis that sound change does not reflect any adaptive character but rather is the phonetic modality of differentiation understood as epigenetic regulation.

The basic internal structure of a word consists of an alternation between consonants and vowels. Words tend to begin with a consonant and end with a vowel. The fundamental evolutionary status of the consonant-vowel alternation is indicated by its presence in rhythmically organized pre-linguistic vocalizations of 7 month-old babbling infants. We have argued that the basic alternation results from a mandibular cyclicity (``The Frame'') originally evolving for ingestive purposes. Here, we consider beginnings and endings of words. We conclude that preferences for consonantal beginnings and vocalic endings may be basic biomechanical consequences of the act of producing vocal episodes between resting states of the production system. Both the characteristic beginning-end asymmetry and some details of the choice of individual sounds in the non-preferred modes (vocalic beginnings and consonantal endings) are mirrored in babbling and early words. The presence of many of these properties in modern words, even though they are delivered in running speech, as well as in a proto-language corpus, indicates retention, for message purposes, of properties originally associated with the single word stage of language evolution.

Naturally occurring speech contains only a limited amount of complex recursive structure, and this is reflected in the empirically documented difficulties that people experience when processing such structures. We present a connectionist model of human performance in processing recursive language structures. The model is trained on simple artificial languages. We find that the qualitative performance profile of the model matches human behavior, both on the relative difficulty of center-embedding and cross-dependency, and between the processing of these complex recursive structures and right-branching recursive constructions. We analyze how these differences in performance are reflected in the internal representations of the model by performing discriminant analyses on these representations both before and after training. Furthermore, we show how a network trained to process recursive structures can also generate such structures in a probabilistic fashion. This work suggests a novel explanation of people's limited recursive performance, without assuming the existence of a mentally represented competence grammar allowing unbounded recursion.

Animal behavior is often altruistic. In the frame of the theory of natural selection, altruism can only exist under specific conditions like kin selection or reciprocal cooperation. We show that reciprocal cooperation, which is generally invoked to explain non-kin altruism, requires very restrictive conditions to be evolutionary stable. Some of these conditions are not met in many cases of altruism observed in nature. In the search of another explanation of non-kin altruism, we consider Zahavis's theory of prestige. We extend it to propose a 'political' model of altruism. We give evidence showing that non-kin altruism can evolve in the context of inter-subgroup competition. Under such circumstances, altruistic behavior can be used by individuals to advertise their quality as efficient coalition members. In this model, only abilities which positively correlate with the subgroup success can evolve into altruistic behaviors.

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 distribution of living languages is investigated and scaling relations are found for the diversity of languages as a function of the country area and population. These results are compared with data from Ecology and from computer simulations of fragmentation dynamics where similar scalings appear. The language size distribution is also studied and shown to display two scaling regions: (i) one for the largest (in population) languages and (ii) another one for intermediate-size languages. It is then argued that these two classes of languages may have distinct growth dynamics, being distributed on the sets of different fractal dimensions.

On the evolutionary trajectory that led to human language there must have been a transition from a fairly limited to an essentially unlimited communication system. The structure of modern human languages reveals at least two steps that are required for such a transition: in all languages (i) a small number of phonemes are used to generate a large number of words; and (ii) a large number of words are used to a produce an unlimited number of sentences. The first (and simpler) step is the topic of the current paper. We study the evolution of communication in the presence of errors and show that this limits the number of objects (or concepts) that can be described by a simple communication system. The evolutionary optimum is achieved by using only a small number of signals to describe a few valuable concepts. Adding more signals does not increase the fitness of a language. This represents an error limit for the evolution of communication. We show that this error limit can be overcome by combining signals (phonemes) into words. The transition from an analogue to a digital system was a necessary step toward the evolution of human language.

[This is the text of a talk that I gave one day last fall, in the tenth month of the year. I have fixed a few bugs here and there and changed a phrase or two to make my thoughts more clear. The talk as I first gave it can be had on tape [12].] I think you know what a man is. A ...

“… By “grammar of the language L” I will mean a device of some sort (that is, a set of rules) that provides, at least, a complete specification of an infinite set of grammatical sentences of L and their structural description. In addition to making precise the notion “structural ...

Function, Selection, and Innateness is a powerful demonstration of the value of looking at language as an adaptive system, which reaches the heart of debates in linguistics and cognitive science on the evolution and nature of language. Why are all languages alike in some ways, different in others? Why do languages change? How did they originate and evolve? Kirby argues these questions must be studied together. He combines functional and formal theories in order to develop a way of treating language as an adaptive system in which its communicative and formal roles have crucial and complimentary roles. He then uses computational models to show what universals emerge given a particular theory of language use or acquisition.

TABLE OF CONTENTS
1 A Puzzle of Fit
2 The Impact of Processing on Word Order
3 Hierarchies and Competing Motivations
4 The Limits of Functional Adaptation
5 Innateness and Function in Linguistics
6 Conclusion

To answer these questions, David Lightfoot looks closely at young children. A child develops a grammar on exposure to some triggering experience. A small perturbation in the trigger may entail a different grammar in the next population of speakers, with dramatic effects. This "" ...

TABLE OF CONTENTS
1. A Puzzle and a Hypothesis
2. Biological and Cultural Inheritance
3. Joint Attention and Cultural Learning
4. Linguistic Communication and Symbolic Representation
5. Linguistic Constructions and Event Cognition
6. Discourse and Representational Redescription
7. Cultural Cognition

The research described in this thesis tries to explain the origins and the struc- ture of human sound systems (and more specifically human vowel systems) as the result of self-organisation in a population under functional con- straints. These constraints are: acoustic distinctiveness, articulatory ease and ease of learning. The process is modelled with computer simulations, following the meth- odology of artificial life and artificial intelligence. The research is part of a larger re- search effort into understanding the origins and the nature of language and intelli- gence.

The emergence of sound systems is studied in a setting called the imitation game. In an imitation game, agents from a population interact in order to imitate each other as well as possible. Imitation is a binary process: it is either successful or a failure. Agents are able to produce and perceive speech sounds in a human-like way, and to adapt and extend their repertoires of speech sounds in reaction to the outcome of the imitation games. The agents' vowel repertoires are initially empty and are bootstrapped by random insertion of a speech sound when an agent with an empty repertoire wants to produce a sound. When the agents' repertoires are not empty anymore, random insertion does not happen anymore, except with very low probability. This low-probability random insertion is done in order to keep a pres- sure on the agents to extend their number of vowels. .

As the agents' repertoires are initially empty and their production and percep- tion are not biased towards any language in particular, the systems of speech sounds that emerge are language-independent and can be considered predictions of the kinds of systems of speech sounds that can be found in human languages.

The main focus of the thesis is on the emergence of vowel systems. It is shown that coherent, successful and realistic vowel systems emerge for a wide range of pa- rameter settings in the simulation. When the vowel systems are compared with the types of vowel systems that are found in human languages, remarkable similarities are found. Not only are the most frequently found human vowel systems predicted, (this could already be done with direct optimisation of acoustic distinctiveness) but also less frequently occurring vowel systems are predicted in approximately the right proportions.

Variations on the basic imitation game show that it is remarkably robust. Not only do coherent, successful and realistic vowel systems emerge for a large number of parameter settings, but they also emerge when either the imitation game or the agents are changed qualitatively. Coherent and realistic systems still emerge when the perception and production of the agents are changed. Even if the rules of the imitation game are slightly changed, coherent and realistic systems still emerge. Of course, there are circumstances under which no systems emerge, indicating that the process is non-trivial.

It is also shown that the vowel systems can emerge and be preserved in chang- ing populations. When old agents are removed from the population, and new, empty agents are added, coherent and realistic vowel systems can still emerge, provided that the replacement rate is not too high. It is also shown in the thesis that vowel systems can be preserved in a population, even though all original agents in it have been replaced. Furthermore, it is shown that under certain circumstances it can be advantegeous to have an age-structure in the population, so that older agents learn less quickly than young ones.

Finally, some experiments with more complex utterances are presented in the thesis. An experiment with artificial CV-syllables is presented and it is shown that, although phonemically coded (as opposed to holistically coded) systems can emerge, this simulation is much harder and much more sensitive to parameter changes than the vowel simulation. This probably has to do with the fact that in the case of CV- syllables multiple independent and partly contradictory constraints have to be satis- fied simultaneously, whereas in the vowel simulations, only one constraint (acoustic distinctiveness) is really important. Also, the first attempts at building a system that can produce complex and dynamic utterances without any constraints on their structure are presented, and it is argued that the main obstacle to getting such a system to work is the mapping from acoustic signals back to articulatory com- mands.

The conclusion of the thesis is that universal tendencies of human vowel sys- tems, and probably of human sound systems in general can be explained as the re- sult of self-organisation in a population of agents that try to communicate as well as possible under articulatory and acoustic constraints. The articulatory and acoustic constraints cause the emerging sound systems to tend towards articulatory and acoustic optimality. However, the fact that the agents communicate in a population forces them to conform to the sound system in the population and causes sub- optimal systems to emerge as well.

An exploration is presented of the interplay between the situated activity of embodied autonomous organisms and the social dynamics they constitute in interaction, with special emphasis on evolutionary, ecological and behavioral aspects. The thesis offers a series of theoretical and methodological criticisms of recent investigations on the biology of social behavior and animal communication. An alternative theoretical framework, based on a systemic theory of biological autonomy, is provided to meet these criticisms and the elaboration of the corresponding theoretical arguments is supported by the construction and analysis of mathematical and computational models.

A game of action coordination is studied by a series of game-theoretic, ecological and computational models which, by means of systematic comparisons, permit the identification of the evolutionary relevance of different factors like finite populations, ecological and genetic constraints, spatial patterns, discreteness and stochasticity. Only in an individual-based model is it found that cooperative action coordination is evolutionarily stable. This is due to the emergence of spatial clusters in the spatial distribution of players which break many of the in-built symmetries of the game and act as invariants of the dynamics constraining the path of viable evolution.

An extension to this model explores other structuring effects by adding the possibility of parental influences on phenotypic development. The result is a further stabilization of cooperative coordination which is explained by the presence of self-promoting networks of developmental relationships which enslave the evolutionary dynamics.

The behavioral aspects involved in the attainment of a coordinated state between autonomous systems are studied in a simulated model of embodied agents coupled through an acoustic medium. Agents must locate and approach each other only by means of continuous acoustic signals. The results show the emergence of synchronized rhythmic signalling patterns that resemble turn-taking which is accompanied by coherent patterns of movement. It is demonstrated that coordination results from the achievement of structural congruence between the agents during interaction.