Language Evolution and Computation Bibliography

In this paper, a computational model of a successful negotiated com- munication system is presented, in which language agents develop their own meanings in response to their environment and attempt to infer the meanings of others' utterances. The inherent uncertainty in the process of meaning inference in the system leads to variation in the agents' internal semantic representations, which then itself drives language change in the form of semantic generalisation.

Rhythm is common in courtship signals of many species. Here we explore whether regularly repeating rhythmic patterns can serve as indicators of underlying mate quality. We find through simulation that rhythmic signals allow the greatest discrimination between high- and low-quality males when low quality is associated with timing errors in artificial songs. However, rhythmic signals are difficult to evolve in our framework, leading to the conclusion that other pressures may have been involved in their appearance.

The main contribution of this paper is twofold. Firstly, it presents a new system for empirical investigations of evolving agent societies in SugarScapelike environments, which improves existing Sugarscape testbeds. Secondly, we introduce a framework for modelling communication and cooperation in an animal society. In this framework the environmental pressure to communicate and cooperate is controllable by a single parameter. We perform several experiments with different values for this parameter and observe some surprising outcomes.

Pure synonymy is rare. By contrast, homonymy is common in languages. Human avoidance of synonymy is plausibly innate, as theorists of differing persuasions have claimed. Innate dispositions to synonymy and homonymy are modelled here, in relation to alternative roles of speaking and hearing in determining fitness.

In the computer model, linguistic signs are acquired via different genetically determined strategies, variously (in)tolerant to synonymy or homonymy. The model defines communicative success as the probability of a speaker getting a message across to a hearer; interpretive success is the probability of a hearer correctly interpreting a speaker's signal. Communicative and interpretive success are compared as bases for reproductive fitness. When communicative success is the basis for fitness, a genotype evolves which is averse to synonymy, while tolerating homonymy. Conversely, when interpretive success is the basis for fitness, a genotype evolves which is averse to homonymy, while tolerating synonymy.

This paper looks at the way signaling behaviour can arise within a population of evolving agents involved in complex task domains where problem-solving behaviours need to be developed and integrated with appropriate signaling strategies. A method is proposed to overcome the difficulties of evolving separate yet compatible parts required by transmitters and receivers that serve no function but communication. The validity of this method is supported by a series of experiments. These not only succeed in evolving agents capable of controlling and enhancing complex behaviours through signaling but also demonstrate how bigger search spaces with more signal channels than might be needed can lead to faster adaptation.

This paper presents an adaptation of Luc Steels's model of Category Formation and Language Sharing. The simple competitive learning algorithm is proposed as a more general means of creating categories from real-world perception. The model is shown to achieve high levels of coherence and to be very robust when two distinct populations are mixed together, with both populations learning each other's words.

The mating song of the male Bengalese finch can be described by a finite-state grammar and has the feature that more complex songs are preferred by females [1]-[3]. These facts suggest that complex song grammars may have evolved via sexual selection. How, then, do the female birds gauge a song's complexity? Assuming that they can measure the complexity of a song while communicating with a male, but without making a model of the song, we studied the evolution of song grammars. In our simulation, it was demonstrated that song grammars became more complex through communication between coevolving males and females. Furthermore, when singing and listening were subject to fluctuations, peculiar features were observed in communication and evolution.

This paper proposes a layered systemic architecture for audio signal processing. The described systems consists of several building blocks connected in different ways and thus enabling different behaviour. Three different systems are proposed constructed with almost the same building blocks fulfilling three different tasks of audio processing: learning to hear, learning to reproduce and learning to associate. The systemic architecture facilitates the connection of all three proposed subsystems to get one big system fulfilling all three proposed tasks of audio signal processing.

Structural hallmarks of language can be explained in terms of adaptation, by language, to pressures arising during its cultural transmission. Here I present a model which explains the compositional structure of language as an adaptation in response to pressures arising from the poverty of the stimulus available to language learners and the biases of language learners themselves.

Models of the cultural evolution of language typically assume a very simplified population dynamic. In the most common modelling framework (the Iterated Learning Model) populations are modelled as consisting of a series of non-overlapping generations, with each generation consisting of a single agent. However, the literature on language birth and language change suggests that population dynamics play an important role in real-world linguistic evolution. We aim to develop computational models to investigate this interaction between population factors and language evolution. Here we present results of extending a well-known Iterated Learning Model to a population model which involves multiple individuals. This extension reveals problems with the model of grammar induction, but also shows that the fundamental results of Iterated Learning experiments still hold when we consider an extended population model.

This paper describes a framework for studies of the adaptive acquisition and evolution of language, with the following components: language learning begins by associating words with cognitively salient representations (``grounding''); the sentences of each language are determined by properties of lexical items, and so only these need to be transmitted by learning; the learnable languages allow multiple agreements, multiple crossing agreements, and reduplication, as mildly context sensitive and human languages do; infinitely many different languages are learnable; many of the learnable languages include infinitely many sentences; in each language, inferential processes can be defined over succinct representations of the derivations themselves; the languages can be extended by innovative responses to communicative demands. Preliminary analytic results and a robotic implementation are described.

Language is a complex phenomenon. Utterances arise from complex interactions between semantics and grammar. Usually, semantics and grammar are studied separately from each other. This paper introduces a model that makes it possible to study the interaction between these two parts of language. The model comprises a population of agents that feature a relatively complex semantic module, and a lexicalisation module that can produce utterances from semantic representations. The language the agents use to communicate is developed through their interactions, without central control. The concrete focus of the model is on determination: whether or not the referents of an utterance are definite.

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.

Compositionality is one of the fundamental properties of natural language. Explaining its evolution remains a challenging problem because most existing explanations require a structured language to be already present in the population before compositionality can successfully spread in a population. In this paper, I study whether a communication system can evolve that shows the preservation of topology between meaning-space and signal-space, without assuming that individuals have any prior processing mechanism for compositionality. I present a formalism to describe a communication system where there is noise in signaling and variation in the values of meanings. In contrast to previous models, both the noise and values depend on the topology of the signal- and meaning spaces. I study a model of a population of agents that each try to optimize their communicative success under these circumstances. The results show that the preservation of topology between follows naturally from the assumptions on noise, values and individual-based optimization.

We advance and discuss a framework suitable to study theoretical implications and practical impact of language evolution and lexicon sharing in an open distributed multi-agent system. In our approach, the assumption of autonomy plays a key role to preserve the opportunity for the agents of local encoding of meanings. We consider the application scenario of Web services, where we conceive the problem of advertisement as a matter of sharing a denotational language. We provide a precise formulation of the agentsrsquo behavior within a game-theoretical setting. As an important consequence of our ``advertising games,'' we interpret the problem of knowledge interoperability and management in the light of evolutionary dynamics and learning in games. Our methodology is inspired by work in natural language semantics and ``language games.''

It is commonly agreed upon that misperception is detrimental. However, misperception might have a beneficial effect from a collective viewpoint when individuals mispercept incoming information that promotes a specific kind of behavior, which leads to an increase in diversity. First, this paper proposes our hypothesis regarding adaptive property of misperception based on the argument of the relationship between misperception and behavioral diversity, and the effects of communication on diversity. Then, a simple computational model is constructed for a resource-searching problem by using the multi-agent modeling method. We investigate both direct misperception, that are caused when obtaining information directly from surrounding environment, and indirect misperception, that are caused when obtaining information indirectly through communication by conducting simulation experiments. The experimental results have shown that misperception could increase diversity in behavior of agents, thus could be adaptive, while accurate communication could decrease a diversity of agent behavior, which might decrease fitness. This paper also discusses a correlative relationship between direct misperception and indirect misperception. We believe that the study on adaptive property of misperception based on an innovative frame of reference and a powerful methodology in the field of complex system or artificial life would shed light on fundamental issues in cognitive science, memetics and engineering.

Language change has recently come to be seen as a complex dynamical system, along the lines of evolutionary biology and economics, as opposed to previous conceptions as a linear or cyclical system. We model the change of a particular phenomenon, vowel harmony, and look at the conditions under which the trajectory of change matches theoretical and empirical predictions. Our experimental work shows that there are certain conditions under which the desired trajectories do not occur, implying that absence of these conditions is necessary for accurate modeling of language change.

Advertising plays a key role in service oriented recommendation over a peer-to-peer network. The advertising problem can be considered as the problem of finding a common language to denote the peers' capabilities and needs. Up to now the current approaches to the problem of advertising revealed that the proposed solutions either affect the autonomy assumption or do not scale up the size of the network. We explain how an approach based on language games can be effective in dealing with the typical issue of advertising: do not require ex-ante agreement and to be responsive to the evolution of the network as an open system. In the paper we introduce the notion of advertising game, a specific language game designed to deal with the issue of supporting the emergence of a common denotation language over a network of peers. We provide the related computational model and an experimental evaluation. A positive empirical evidence is achieved by sketching a peer-to-peer recommendation service for bookmark exchanging using real data.

Steels in [4] claims that both flux of agents (changing of agents in an experiment) and stochasticity in communication of agents are necessary for a spontaneous change in language. This paper argues that flux of agents alone could be responsible for a spontaneous change in language. This hypothesis is demonstrated by modeling language use through language games played in a population of evolving agents.

This paper investigates factors influencing the establishment of a common spatial lexicon in a community of agents moving in a simulated environment. The model avoids some traditionally criticized features of other models of the emergence of a common lexicon such as the use of only cued representations, pre-defined fixed meanings shared by all agents, explicit meaning transmission and nonverbal feedback about the outcome of a game. While each agent forms its own concepts for distances and directions, coherent lexicon emerges enabling agents to localize objects in the environment based on their spatial description. Factors necessary for language change are then investigated in an experiment where agents join/leave the community and the results are compared to those of the related model of Steels.

Creole is one of the main topics in various fields concerning the language origin and the language change, such as sociolinguistics, the developmental psychology of language, paleoanthropology and so on. Our purpose in this paper is to develop an evolutionary theory of language to study the emergence of creole. We discuss how the emergence of creole is dealt with in the perspective of population dynamics. The proposal of evolutionary equations is a modification of the language dynamics equations by Komarova et al. We show experimental results, in which we could observe the emergence of creole. Furthermore, we analyze the condition of creolization in terms of similarity among languages. We conclude that a creole becomes dominant when pre-existing languages are not similar to each other and rather similar to the newly appeared language (would-be-creole); however the new language must not be too similar, in which case pre-existing languages remain and coexist.

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.

An expression-induction model was used to simulate the evolution of basic color terms in order to test Berlin and Kay's (1969) hypothesis that the typological patterns observed in basic color term systems are produced by a process of cultural evolution under the influence of universal aspects of human neurophysiology. Ten agents were simulated, each of which could learn color term denotations by generalizing from examples using Bayesian inference. Conversations between these agents, in which agents would learn from one-another, were simulated over several generations, and the languages emerging at the end of each simulation were investigated. The proportion of color terms of each type correlated closely with the equivalent frequencies found in the world color survey, and most of the emergent languages could be placed on one of the evolutionary trajectories proposed by Kay and Maffi (1999). The simulation therefore demonstrates how typological patterns can emerge as a result of learning biases acting over a period of time.

The evolutionary history of languages can be modeled as a tree, called a phylogeny, where the leaves represent the extant lan- guages, the internal vertices represent the ancestral languages, and the edges represent the genetic relations between the languages. Languages not only inherit characteristics from their ancestors but also sometimes borrow them from other languages. Such borrowings can be represented by additional non-tree edges. This paper addresses the problem of com- puting a small number of additional edges that turn a phylogeny into a 'perfect phylogenetic network'. To solve this problem, we use answer set programming, which represents a given computational problem as a logic program whose answer sets correspond to solutions. Using the answer set solver smodels, with some heuristics and optimization tech- niques, we have generated a few conjectures regarding the evolution of Indo-European languages.

In this paper we present our work on developing a shared repertoire of action categories through imitation. A population of robotic agents invents and shares a repertoire of actions by engaging in imitative interactions. We present an experimental set-up which enables us to investigate what properties agents should have in order to achieve this. Among these properties are: being able to determine the other's actions from visual observation and doing incremental unsupervised categorisation of actions.

Children will develop their parental languages correctly, since language learners come to obtain the one which they contact most in the community. At the same time, children would be affected by other languages, the influence of which is proportional to the population of those languages. In this paper, we revise the foregoing evolutionary theory of language, that is differential equations of the population dynamics. We propose that the transition rate in languages is sensitive to the distribution of population of each generation. In addition, we introduce the exposure probability that is the measure of influence from other languages. We show experimental results, in which we could observe the emergence of creole. Furthermore, we analysed which language would be dominant, dependent on the initial distribution of population, together with the exposure probability.

How and where are the universal features of language specified? We consider language users as situated agents acting as conduits for the cultural transmission of language. Using multi-agent computational models we show that certain hallmarks of language are adaptive in the context of cultural transmission. This observation requires us to reconsider the role of innateness in explaining the characteristic structure of language. The relationship between innate bias and the universal features of language becomes opaque when we consider that significant linguistic evolution can occur as a result of cultural transmission.

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.

Abstract Language acquisition is a special kind of learning problem because the outcome of learning of one generation is the input for the next. That makes it possible for languages to adapt to the particularities of the learner. In this paper, I show that this type of language ...

Thousands of the world's languages are vanishing at an alarming rate, with 90% of them being expected to disappear with the current generation1. Here we develop a simple model of language competition that explains historical data on the decline of Welsh, Scottish Gaelic, Quechua (the most common surviving indigenous language in the Americas) and other endangered languages. A linguistic parameter that quantifies the threat of language extinction can be derived from the model and may be useful in the design and evaluation of language-preservation programmes.

Languages, like genes, provide vital clues about human history. The origin of the Indo-European language family is ``the most intensively studied, yet still most recalcitrant, problem of historical linguistics''. Numerous genetic studies of Indo-European origins have also produced inconclusive results. Here we analyse linguistic data using computational methods derived from evolutionary biology. We test two theories of Indo-European origin: the 'Kurgan expansion' and the 'Anatolian farming' hypotheses. The Kurgan theory centres on possible archaeological evidence for an expansion into Europe and the Near East by Kurgan horsemen beginning in the sixth millennium BP. In contrast, the Anatolian theory claims that Indo-European languages expanded with the spread of agriculture from Anatolia around 8,000-9,500 years BP. In striking agreement with the Anatolian hypothesis, our analysis of a matrix of 87 languages with 2,449 lexical items produced an estimated age range for the initial Indo-European divergence of between 7,800 and 9,800 years BP. These results were robust to changes in coding procedures, calibration points, rooting of the trees and priors in the bayesian analysis.

There are global threats to biodiversity with current extinction rates well above background levels1. Although less well publicized, numerous human languages have also become extinct, and others are threatened with extinction. However, estimates of the number of threatened languages vary considerably owing to the wide range of criteria used. For example, languages have been classified as threatened if the number of speakers is less than 100, 500, 1,000, 10,000, 20,000 or 100,000 (ref. 3). Here I show, by applying internationally agreed criteria for classifying species extinction risk4, that languages are more threatened than birds or mammals. Rare languages are more likely to show evidence of decline than commoner ones. Areas with high language diversity also have high bird and mammal diversity and all three show similar relationships to area, latitude, area of forest and, for languages and birds, maximum altitude. The time of human settlement has little effect on current language diversity. Although similar factors explain the diversity of languages and biodiversity, the factors explaining extinction risk for birds and mammals (high altitude, high human densities and insularity) do not explain the numbers of endangered languages.

The emergence of a complex language is one of the fundamental events of human evolution, and several remarkable features suggest the presence of fundamental principles of organization. These principles seem to be common to all languages. The best known is the so-called Zipf's law, which states that the frequency of a word decays as a (universal) power law of its rank. The possible origins of this law have been controversial, and its meaningfulness is still an open question. In this article, the early hypothesis of Zipf of a principle of least effort for explaining the law is shown to be sound. Simultaneous minimization in the effort of both hearer and speaker is formalized with a simple optimization process operating on a binary matrix of signal-object associations. Zipf's law is found in the transition between referentially useless systems and indexical reference systems. Our finding strongly suggests that Zipf's law is a hallmark of symbolic reference and not a meaningless feature. The implications for the evolution of language are discussed. We explain how language evolution can take advantage of a communicative phase transition.

Indo-European is the largest and best-documented language family in the world, yet the reconstruction of the Indo-European tree, first proposed in 1863, has remained controversial. Complications may include ascertainment bias when choosing the linguistic data, and disregard for the wave model of 1872 when attempting to reconstruct the tree. Essentially analogous problems were solved in evolutionary genetics by DNA sequencing and phylogenetic network methods, respectively. We now adapt these tools to linguistics, and analyze Indo-European language data, focusing on Celtic and in particular on the ancient Celtic language of Gaul (modern France), by using bilingual Gaulish-Latin inscriptions. Our phylogenetic network reveals an early split of Celtic within Indo-European. Interestingly, the next branching event separates Gaulish (Continental Celtic) from the British (Insular Celtic) languages, with Insular Celtic subsequently splitting into Brythonic (Welsh, Breton) and Goidelic (Irish and Scottish Gaelic). Taken together, the network thus suggests that the Celtic language arrived in the British Isles as a single wave (and then differentiated locally), rather than in the traditional two-wave scenario ('P-Celtic' to Britain and 'Q-Celtic' to Ireland). The phylogenetic network furthermore permits the estimation of time in analogy to genetics, and we obtain tentative dates for Indo-European at 8100 BC ± 1,900 years, and for the arrival of Celtic in Britain at 3200 BC ± 1,500 years. The phylogenetic method is easily executed by hand and promises to be an informative approach for many problems in historical linguistics.

A small number of discrete choices (`parameters') embedded within a system of otherwise universal principles create the extensive superficial differences between unrelated languages like English, Japanese, and Mohawk. Most current thinking about the evolution of language ignores or denies the existence of these parameters because it can see no rationale for them. That the human language faculty is organized in this way makes more sense if language is compared to a cipher or code. As such, it would have a purpose of concealing information from some at the same time as it communicates information to others.

Why is language the way it is? How did language come to be this way? And why is our species alone in having complex language? These are old unsolved questions that have seen a renaissance in the dramatic recent growth in research being published on the origins and evolution of human language. This review provides a broad overview of some of the important current work in this area. We highlight new methodologies (such as computational modeling), emerging points of consensus (such as the importance of pre-adaptation), and the major remaining controversies (such as gestural origins of language). We also discuss why language evolution is such a difficult problem, and suggest probable directions research may take in the near future.

A new theoretical approach to language has emerged in the past 10-15 years that allows linguistic observations about form-meaning pairings, known as 'constructions', to be stated directly. Constructionist approaches aim to account for the full range of facts about language, without assuming that a particular subset of the data is part of a privileged 'core'. Researchers in this field argue that unusual constructions shed light on more general issues, and can illuminate what is required for a complete account of language.

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 propose a theoretical framework for exploring the evolution of the music faculty from a comparative perspective. This framework addresses questions of phylogeny, adaptive function, innate biases and perceptual mechanisms. We argue that comparative studies can make two unique contributions to investigations of the origins of music. First, musical exposure can be controlled and manipulated to an extent not possible in humans. Second, any features of music perception found in nonhuman animals must not be part of an adaptation for music, and must rather be side effects of more general features of perception or cognition. We review studies that use animal research to target specific aspects of music perception (such as octave generalization), as well as studies that investigate more general and shared systems of the mind/brain that may be relevant to music (such as rhythm perception and emotional encoding). Finally, we suggest several directions for future work, following the lead of comparative studies on the language faculty.

Any mechanism of language acquisition can only learn a restricted set of grammars. The human brain contains a mechanism for language acquisition which can learn a restricted set of grammars. The theory of this restricted set is universal grammar (UG). UG has to be sufficiently specific to induce linguistic coherence in a population. This phenomenon is known as ``coherence threshold''. Previously, we have calculated the coherence threshold for deterministic dynamics and infinitely large populations. Here, we extend the framework to stochastic processes and finite populations. If there is selection for communicative function (selective language dynamics), then the analytic results for infinite populations are excellent approximations for finite populations; as expected, finite populations need a slightly higher accuracy of language acquisition to maintain coherence. If there is no selection for communicative function (neutral language dynamics), then linguistic coherence is only possible for finite populations.

The fact that all languages known are digital poses the question of their origin. The answer developed here treats language as the interface of information theory and molecular development by showing previously unrecognized isomorphisms between the analog and digital features of language and life at the molecular level. Human language is a special case of signal transduction and hence is subject to the coding aspects of Shannon's theorems and the analog aspects of pattern recognition, each represented by genotype and phenotype. Digital language acquisition is late in evolution and postnatal development and requires a neural reorganization by a mechanism of somatic network programming in response to the environment. Such a mechanism would solve the Chomsky conundrum of how children can learn any language without knowing rules of grammar too numerous to be encoded genotypically. BioEssays

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.

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.

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.

This article reviews recent progress made by computational studies investigating the emergence, via learning or evolutionary mechanisms, of communication among a collection of agents. This work spans issues related to animal communication and the origins and evolution of language. The studies reviewed show how population size, spatial constraints on agent interactions, and the tasks involved can all influence the nature of the communication systems and the ease with which they are learned and/or evolved. Although progress in this area has been substantial, we are able to identify some important areas for future research in the evolution of language, including the need for further computational investigation of key aspects of language such as open vocabulary and the more complex aspects of syntax.

In this study, optimization models using Genetic Algorithms are proposed to study the conguration of vowels and tone systems. Similar to previous explanatory models that have been used to study vowel systems, certain criteria, which are assumed to be the principles governing the structure of sound systems, are used to predict optimal vowels and tone systems. In most of the earlier studies only one criterion has been considered. When two criteria are considered, they are often combined into one scalar function. The GA model proposed for the study of tone systems uses a Pareto-ranking method which is highly applicable for dealing with optimization problems having multiple criteria. For optimization of tone systems, perceptual contrast and markedness complexity are considered simultaneously. Although the consistency between the predicted systems and the observed systems is not as significant as those obtained for vowel systems, further investigation along this line is promising.

This paper contributes to neurolinguistics by grounding an evolutionary account of the readiness of the human brain for language in the search for homologies between different cortical areas in macaque and human. We consider two hypotheses for this grounding, that of Aboitiz and Garci[Brain Res. Rev. 25 (1997) 381] and the Mirror System Hypothesis of Rizzolatti and Arbib [Trends Neurosci. 21 (1998) 188] and note the promise of computational modeling of neural circuitry of the macaque and its linkage to analysis of human brain imaging data. In addition to the functional differences between the two hypotheses, problems arise because they are grounded in different cortical maps of the macaque brain. In order to address these divergences, we have developed several neuroinformatics tools included in an on-line knowledge management system, the NeuroHomology Database, which is equipped with inference engines both to relate and translate information across equivalent cortical maps and to evaluate degrees of homology for brain regions of interest in different species.

Walter's Machina speculatrix inspired the name Rana computatrix for a family of models of visuomotor coordination in the frog, which contributed to the development of computational neuroethology. We offer here an 'evolutionary' perspective on models in the same tradition for rat, monkey and human. For rat, we show how the frog-like taxon affordance model provides a basis for the spatial navigation mechanisms that involve the hippocampus and other brain regions. For monkey, we recall two models of neural mechanisms for visuomotor coordination. The first, for saccades, shows how interactions between the parietal and frontal cortex augment superior colliculus seen as the homologue of frog tectum. The second, for grasping, continues the theme of parieto-frontal interactions, linking parietal affordances to motor schemas in premotor cortex. It further emphasizes the mirror system for grasping, in which neurons are active both when the monkey executes a specific grasp and when it observes a similar grasp executed by others. The model of humanbrain mechanisms is based on the mirror-system hypothesis of the evolution of the language-ready brain, which sees the human Broca's area as an evolved extension of the mirror system for grasping.

Evolutionary robotics is a biologically inspired approach to robotics that is advantageous to studying the evolution of communication. A new model for the emergence of communication is developed and tested through various simulation experiments. In the first simulation, the emergence of simple signalling behaviour is studied. This is used to investigate the inter-relationships between communication abilities, namely linguistic production and comprehension, and other behavioural skills. The model supports the hypothesis that the ability to form categories from direct interaction with an environment constitutes the grounds for subsequent evolution of communication and language. In the second simulation, evolutionary robots are used to study the emergence of simple syntactic categories, e.g. action names (verbs). Comparisons between the two simulations indicate that the signalling lexicon emerged in the first simulation follows the evolutionary pattern of nouns, as observed in related models on the evolution of syntactic categories. Results also support the language-origin hypothesis on the fact that nouns precede verbs in both phylogenesis and ontogenesis. Further extensions of this new evolutionary robotic model for testing hypotheses on language origins are also 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.

We investigate how the evolution of communication strategies affects signal credibility when there is common interest as well as a conflict between communicating individuals. Taking alarm calls as an example, we show that if the temptation to cheat is low, a single signal is used in the population. If the temptation increases cheaters will erode the credibility of a signal, and an honest mutant using a different signal ('a private code') will be very successful until this, in turn, is cracked by cheaters. In such a system, signal use fluctuates in time and space and hence the meaning of a given signal is not constant. When the temptation to cheat is too large, no honest communication can maintain itself in a Tower of Babel of many signals. We discuss our analysis in the light of the Green Beard mechanism for the evolution of altruism.

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.

Computational models were constructed to investigate how the meanings of basic colour terms were learned, and to determine why these words have prototype properties, and why they partition the colour space. A Bayesian model of acquisition was able to learn colo ur term systems with these properties, but could equally well learn colour term systems which did not partition the colour space or have prototype properties, and so it failed to explain the empirical data concerning these words. Computational evolutionary simulations were then conducted by creating a community of artificial people using multiple copies of the Bayesian model. These artificial people then learned colour words from one-another, and colour term systems were allowed to evolve over a number of generations. The emergent colour terms always partitioned the colour space and had prototype properties. These results demonstrate that the Bayesian model is able to account for the properties of colour term systems only when it is placed in a social contex t and so they provide evidence of the importance of understanding language as a product of both psychology and social interaction.

This paper presents a numeric and information theoretic model for the measuring of language change, without specifying the particular type of change. It is shown that this measurement is intuitively plausible and that meaningful measurements can be made from as few as 1000 characters. This measurement technique is extended to the task of determining the ``rate'' of language change based on an examination of brief excerpts from the National Geographic Magazine and determining both their linguistic distance from one another as well as the number of years of temporal separation. A statistical analysis of these results shows, first, that language change can be measured, and second, that the rate of language change has not been uniform, and that in particular, the period 1939-1948 had particularly slow change, while 1949-1958 and 1959-1968 had particularly rapid changes.

In several communication systems that rely on social learning, such as bird song, and possibly human language, the range of signals that can be learned is limited by perceptual biases - predispositions - that are presumably based on genes. In this paper, we examine the coevolution of such genes with the culturally transmitted communication traits themselves, using deterministic population genetic models. We argue that examining how restrictive genetic predispositions are is a useful way of examining the evolutionary origin and maintenance of learning. Under neutral cultural evolution, where no cultural trait has any inherent advantage over another, there is selection in favour of less restrictive genes (genes that allow a wider range of signals to recognized). In contrast, cultural conformity (where the most common cultural trait is favoured) leads to selection in favour of more restrictive genes.

Evolutionary computing is a powerful tool for studying the origins and evolution of music. In this case, music is studied as an adaptive complex dynamic system and its origins and evolution are studied in the context of the cultural conventions that may emerge under a number of constraints (e.g. psychological, physiological and ecological). This paper introduces three case studies of evolutionary modelling of music. It begins with a model for studying the role of mating-selective pressure in the evolution of musical taste. Here the agents evolve ``courting tunes'' in a society of ``male'' composers and ``female'' critics. Next, a mimetic model is introduced to study the evolution of musical expectation in a community of autonomous agents furnished with a vocal synthesizer, a hearing system and memory. Finally, an iterated learning model is proposed for studying the evolution of compositional grammars. In this case, the agents evolve grammars for composing music to express a set of emotions.

Universal grammar (UG) is a list of innate constraints that specify the set of grammars that can be learned by the child during primary language acquisition. UG of the human brain has been shaped by evolution. Evolution requires variation. Hence, we have to postulate and study variation of UG. We investigate evolutionary dynamics and language acquisition in the context of multiple UGs. We provide examples for competitive exclusion and stable coexistence of different UGs. More specific UGs admit fewer candidate grammars, and less specific UGs admit more candidate grammars. We will analyze conditions for more specific UGs to outcompete less specific UGs and vice versa. An interesting finding is that less specific UGs can resist invasion by more specific UGs if learning is more accurate. In other words, accurate learning stabilizes UGs that admit large numbers of candidate grammars.

This paper presents algorithms that allow a robot to express its emotions by modulating the intonation of its voice. They are very simple and efficiently provide life-like speech thanks to the use of concatenative speech synthesis. We describe a technique which allows to continuously control both the age of a synthetic voice and the quantity of emotions that are expressed. Also, we present the first large-scale data mining experiment about the automatic recognition of basic emotions in informal everyday short utterances. We focus on the speaker-dependent problem. We compare a large set of machine learning algorithms, ranging from neural networks, Support Vector Machines or decision trees, together with 200 features, using a large database of several thousands examples. We show that the difference of performance among learning schemes can be substantial, and that some features which were previously unexplored are of crucial importance. An optimal feature set is derived through the use of a genetic algorithm. Finally, we explain how this study can be applied to real world situations in which very few examples are available. Furthermore, we describe a game to play with a personal robot which facilitates teaching of examples of emotional utterances in a natural and rather unconstrained manner.

The recent emergence of a new sign language among deaf children and adolescents in Nicaragua provides an opportunity to study how grammatical features of a language arise and spread, and how new language environments are constructed. The grammatical regularities that underlie language use reside largely outside the domain of explicit awareness. Nevertheless, knowledge of these regularities must be transmitted from one generation to the next to survive as part of the language. During this transmission, language form and use is shaped by both the characteristics of ontogenetic development within individual users and by historical changes in patterns of interaction between users. To capture this process, the present study follows the emergence of spatial modulations in Nicaraguan Sign Language (NSL). A comprehension task examining interpretations of spatially modulated verbs reveals that new form-function mappings arise among children who functionally differentiate previously equivalent forms. The new mappings are then acquired by their age peers (who are also children), and by subsequent generations of children who learn the language, but not by adult contemporaries. As a result, language emergence is characterized by a convergence on form within each age cohort, and a mismatch in form from one age cohort to the cohort that follows. In this way, each age cohort, in sequence, transforms the language environment for the next, enabling each new cohort of learners to develop further than its predecessors.

Language arises from the interaction of three complex adaptive systems -- biological evolution, learning, and culture. We focus here on cultural evolution, and present an Iterated Learning Model of the emergence of compositionality, a fundamental structural property of language. Our main result is to show that the poverty of the stimulus available to language learners leads to a pressure for linguistic structure. When there is a bottleneck on cultural transmission, only a language which is generalizable from sparse input data is stable. Language itself evolves on a cultural time-scale, and compositionality is language's adaptation to stimulus poverty.

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.

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 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.

From a biologist's perspective, language has its own particular design features. It is present in virtually all humans, appears to be mediated by dedicated neural circuitry, exhibits a characteristic pattern of development, and is grounded in a suite of constraints that can be ...

The human capacity for language and the structures of individual languages can best be understood from an evolutionary perspective. Both the biological capacity and languages owe their shape to events far back in the past. Biological steps toward language-readiness involved preadaptations for modern phonetics, syntax, semantics and pragmatics. Once humans were language-ready, ever more complex language systems could grow, relatively fast, by cultural transmission, generation after generation. This latter process is profitably studied by grammaticalization theory and computer modelling.

There are an enormous number of communication systems in the natural world (Hauser, 1996). When a male Tungara frog produces `whines' and `chucks' to attract a female, when a mantis shrimp strikes the ground to warn o a competitor for territory, even when a bee is attracted to a particular flower, communication is taking place. Humans as prodigious communicators are not unusual in this respect. What makes human language stand out as unique (or at least very rare indeed, Oliphant, 2002) is the degree to which it is learned.

The frog's response to mating calls is determined by its genes, which have been tuned by natural selection. There is an inevitability to the use of this signal. Barring some kind of disaster in the development of the frog, we can predict its response from birth. If we had some machine for reading and translating its DNA, we could read-off its communication system from the frog genome. We cannot say the same of a human infant. The language, or languages, that an adult human will come to speak are not predestined in the same way. The particular sounds that a child will use to form words, the words themselves, the ways in which words will be modi ed and strung together to form utterances - none of this is written in the human genome.

Whereas frogs store their communication system in their genome, much of the details of human communication are stored in the environment. The information telling us the set of vowels we should use, the inventory of verb stems, the way to form the past tense, how to construct a relative-clause, and all the other facts that make up a human language must be acquired by observing the way in which others around us communicate. Of course this does not mean that human genes have no role to play in determining the structure of human communication. If we could read the genome of a human like we did with the frog, we would find that, rather than storing details of a communication system, our genes provide us with mechanisms to retrieve these details from the behaviour of others.

From a design point of view, it is easy to see the advantages of providing instructions for building mechanisms for language acquisition rather than the language itself. Human language cannot be completely innate because it would not t in the genome. Worden (1995) has derived a speed-limit on evolution that allows us to estimate the maximum amount of information in the human genome that codes for the cognitive di erences between us and chimpanzees. He gives a paltry gure of approximately 5 kilobytes. This is equivalent to the text of just the introduction to this chapter.

The implications of this aspect of human uniqueness are the subject of this chapter. In the next section we will look at the way in which language learning leads naturally to language variation, and what the constraints on this variation tell us about language acquisition. In section three, we introduce a computational model of sequential learning and show that the natural biases of this model mirror many of the human learner's biases, and help to explain the universal properties of all human languages.

If learning biases such as those arising from sequential learning are to explain the structure of language, we need to explore the mechanism that links properties of learning to properties of what is being learned. In section four we look in more detail at this issue, and see how learning biases can lead to language universals by introducing a model of linguistic transmission called the Iterated Learning Model. We go on to show how this model can be used to understand some of the fundamental properties of human language syntax.

Finally, we look at the implications of our work for linguistic and evolutionary theory. Ultimately, we argue that linguistic structure arises from the interactions between learning, culture and evolution. If we are to understand the origins of human language, we must understand what happens when these three complex adaptive systems are brought together.

This chapter outlines the theory (first explicitly defended by Pinker and Bloom 1990), that the human language faculty is a complex biological adaptation that evolved by natural selection for communication in a knowledgeusing, socially interdependent lifestyle. This claim might ...

It is a simple observation that children make mistakes when they learn a language. Yet, to the trained eye, these mistakes are far from random; in fact, they closely resemble perfectly grammatical utterances by adults--who speak other languages. This type of error analysis suggests a novel view of language learning: children are born with a fixed set of hypotheses about language--Chomsky's Universal Grammar--and these hypotheses compete to match the child's ambient language in a Darwinian fashion. The book presents evidence for this perspective from the study of children's words and grammar, and how language changes over time.

In this thesis, I address the problem of how successful communication systems can emerge between agents who do not have innate or explicitly transferable meanings, cannot read the minds of their interlocutors, and are not provided with any feedback about the communication process. I develop a solution by focusing on the role of meanings within the framework of language evolution, and on communication through the repeated inference of meaning.

Much recent work on the evolution of language has concentrated on the emergence of compositional syntax as the crucial event which marked the genesis of language; all the experimental models which purport to demonstrate the emergence of syntax, however, rely on models of communication in which the signals are redundant and which contain pre-defined, structured meaning systems which provide an explicit blueprint against which the syntactic structure is built. Moreover, the vast majority of such meaning systems are truly semantic in name only, lacking even the basic semantic characteristics of sense and reference, and the agents must rely on mind-reading or feedback (or both) in order to learn how to communicate.

By contrast, at the heart of this thesis is a solution to the signal redundancy paradox based on the inference of meaning and the disambiguation of potential referents through exposure in multiple contexts. I describe computational models of meaning creation in which agents independently develop individual conceptual structures based on their own experiences of the environment, and show through experimental simulations that the agents can use their own individual meanings to communicate with each other about items in their environment. I demonstrate that the development of successful communication depends to a large extent on the synchronisation of the agents' conceptual structures, and that such synchronisation is significantly more likely to occur when the agents use an intelligent meaning creation strategy which can exploit the structure in the information in the environment.

Motivated by research into the acquisition of language by children, I go on to explore how the introduction of specific cognitive and lexical biases affects the level of communicative success. I show that if the agents are guided by an assumption of mutual exclusivity in word meanings, they do not need to have such high levels of meaning similarity, and can instead communicate successfully despite having very divergent conceptual structures.

How did language come to have its characteristic structure? Many argue that by understanding those parts of our biological machinery relevant to language, we can explain why language is the way it is. If the hallmarks of language are simply properties of our biological machinery, elicited through the process of language acquisition, then such an explanatory route is adequate.

As soon as we admit the possibility that knowledge of language is learned, in the sense that language acquisition is a process involving inductive generalisations, then an explanatory inadequacy arises. Any thorough explanation of the characteristic structure of language must now explain why the input to the language acquisition process has certain properties and not others. This thesis builds on recent work that proposes that the linguistic stimulus has certain structural properties that arise as a result of linguistic evolution. Here, languages themselves adapt to fit the task of learning: they reflect an accumulated structural residue laid down by previous generations of language users.

Using computational models of linguistic evolution I explore the relationship be- tween language induction and generalisation based on a simplicity principle, and the linguistic evolution of compositional structures. The two main contributions of this thesis are as follows. Firstly, using a model of induction based on the minimum description length principle, I address the question of linguistic evolution resulting from a bias towards compression. Secondly, I carry out a thorough examination of the parameter space affecting the cultural transmission of language, and note that the conditions for linguistic evolution towards compositional structure correspond to (1) specific levels of semantic complexity, and (2), induction based on sparse language exposure.

Ultimately, the story of the evolution of language in humans must depend on an account of the genetic evolution of the biological machinery underlying language. Rather than explicitly encoding the observed constraints on language, I argue that any explanation based on biological evolution should instead aim to explain how the conditions for linguistic evolution, outlined above, came about.

The emergence and evolution of human language has been the focus of increasing amounts of research activity in recent years. This increasing interest has been coincident with the increased use of computer simulation, particularly using one or more of the methods and techniques of `Artificial Life', to investigate a wide range of evolutionary problems and questions. There is now a significant body of work that uses such computer simulations to investigate the evolution of language.

In this thesis a broad review of work on the evolution of language is presented, showing that language evolution occurs as two distinct evolutionary processes. The ability to use language is clearly the result of biological evolution. But the changes that occur over time to all spoken languages can also be viewed as being part of a process of cultural evolution. In this thesis, work using artificial life models to investigate each of these processes is reviewed. A review of the methods and techniques used in artificial life is also presented early in the work.

A novel model is developed which is used to explore the conditions necessary for the evolution of language. Interesting results from initial tests of the model highlight the role of redundancy in language. From these initial tests, the model is further developed to explore the biological evolution of the human capacity for language. One significant outcome of this work is to highlight the limitations of the model for developing, and especially for `proving', particular theories on how or why Homo sapiens alone evolved language. This is tied to a brief review showing that this weakness is not one specific to this particular model, but may be one that is possessed by all artificial life models that try to explain the origins of language.

With further minor modifications to the model, the focus is shifted to the evolution of languages and language diversity. In comparison with some of the earlier conclusions, this work emphasises the positive contribution to ongoing scientific debate that is possible using computer simulations. In this case, experiments using the model focus on whether social and/or linguistic benefits are required in explanations of language change. A review and debate is then presented on work that contradicts our findings. Further corroboration of our conclusions is then gained by conducting a similar experiment using a different computer model.

The key contributions of this interdisciplinary work are: first, in detailing some of the unique problems and issues inherent in using computer models specifically for modelling the evolution of language; second, in emphasising the importance of redundancy in language evolution; and finally, in adding to the current debate on whether the evolution of languages can be viewed as a form of adaptively neutral evolution.

Human language is a remarkable communication system, apparently unique among an- imals. All humans have a built-in learning mechanism known as universal grammar or UG. Languages change in regular yet unpredictable ways due to many factors, including properties of UG and contact with other languages. This dissertation extends the standard replicator equation used in evolutionary biology to include a learning process. The resulting language dynamical equation models language change at the population level. In a further extension, members of the population may have di#erent UGs. It models evolution of the language faculty itself.

We begin by examining the language dynamical equation in the case where the param- eters are fully symmetric. When learning is very error prone, the population always settles at an equilibrium where all grammars are present. For more accurate learning, coherent equilibria appear, where one grammar dominates the population. We identify all bifurca- tions that take place as learning accuracy increases. This alternation between incoherence and coherence provides a mechanism for understanding how language contact can trigger change.

We then relax the symmetry assumptions, and demonstrate that the language dynami- cal equation can exhibit oscillations and chaos. Such behavior is consistent with the regular, spontaneous, and unpredictable changes observed in actual languages, and with the sensi- tivity exhibited by changes triggered by language contact. From there, we move to the extended model with multiple UGs. The first stage of analysis focuses on UGs that admit only a single grammar. These are stable, immune to invasion by other UGs with imperfect learning. They can invade a population that uses a similar grammar with a multi-grammar UG. This analysis suggests that in the distant past, human UG may have admitted more languages than it currently does, and that over time variants with more built-in information have taken over. Finally, we address a low-dimensional case of competition between two UGs, and find conditions where they are stable against one another, and where they can coexist. These results imply that evolution of UG must have been incremental, and that similar variants may coexist.

This research was conducted under the supervision of Dr. Martin A. Nowak (Program in Theoretical Biology at the Institute for Advanced Study, and Program in Applied and Computational Mathematics at Princeton University).

Theories of language evolution typically attribute its unique structure to pressures acting on the genetic transmission of a language faculty and on the cultural transmission of language itself. In strongly biological accounts, natural selection acting on the genetic transmission of the language faculty is seen as the key determinant of linguistic structure, with culture relegated to a relatively minor role. Strongly cultural accounts place greater emphasis on the role of learning in shaping language, with little or no biological adaptation.

Formal modelling of the transmission of language, using mathematical or computational techniques, allows rigorous study of the impact of these two modes of transmission on the structure of language. In this thesis, computational models are used to investigate the evolution of symbolic vocabulary and compositional structure. To what extent can these aspects of language be explained in terms of purely biological or cultural evolution? Should we expect to see a fruitful interaction between these two adaptive processes in a dual transmission model?

As a first step towards addressing these questions, models which focus on the cultural transmission of language are developed. These models suggest that the conventionalised symbolic vocabulary and compositional structure of language can emerge through the adaptation of language itself in response to pressure to be learnable. This pressure arises during cultural transmission as a result of 1) the inductive bias of learners and 2) the poverty of the stimulus available to learners. Language-like systems emerge only when learners acquire their linguistic competence on the basis of sparse input and do so using learning procedures which are biased in favour of one-to-one mappings between meanings and signals. Children acquire language under precisely such circumstances.

As the second stage of inquiry, dual transmission models are developed to ascertain whether this cultural evolution of language interacts with the biological evolution of the language faculty. In these models an individual's learning bias is assumed to be genetically determined. Surprisingly, natural selection during the genetic transmission of this innate endowment does not reliably result in the development of learning biases which lead, through cultural processes, to language-like communication -- there is no synergistic interaction between biological and cultural evolution. The evolution of language may therefore best be explained in terms of cultural evolution on a domain-general or exapted innate substrate.