Language Evolution and Computation Bibliography

In a distributed model of intelligence, peer components need to communicate with one another. I present a system which enables two agents connected by a thick twisted bundle of wires to bootstrap a simple communication system from observations of a shared environment. The agents learn a large vocabulary of symbols, as well as inflections on those symbols which allow thematic role-frames to be transmitted. Language acquisition time is rapid and linear in the number of symbols and inflections. The final communication system is robust and performance degrades gradually in the face of problems.

Human colour perception is continuous, but humans categorise the colour continuum and often label the resulting colour categories. The debate on whether colour categorisation is an individual process, or whether it is embedded in genetic constraints has not been settled yet. Further- more, as colour categories have colour names, it is claimed that language could have an influence on the categorisation. This paper reports on agent-based simulations that test the validity of dirent theories, and uncovers the weak and strong points of each. We conclude, from experi- ments using AI techniques, that colour categorisation is most likely to be cultural process.

We examined the role of fitness, commonly assumed without proof to be conferred by the mastery of language, in shaping the dynamics of language evolution. To that end, we introduced island migration (a concept borrowed from population genetics) into the shared lexicon model of communication (Nowak et al., 1999). The effect of fitness linear in language coherence was compared to a control condition of neutral drift. We found that in the neutral condition (no coherence-dependent fitness) even a small migration rate - less than 1% - suffices for one language to become dominant, albeit after a long time. In comparison, when fitness-based selection is introduced, the subpopulations stabilize quite rapidly to form several distinct languages. Our findings support the notion that language confers increased fitness. The possibility that a shared language evolved as a result of neutral drift appears less likely, unless migration rates over evolutionary times were extremely small.

Human, syntactic language is one of the most intriguing behaviors and receives increasing attention from researchers in numerous fields. Here we present a model that goes an important step further than previous work because it explicitly connects low-level perception and categorization, hierarchical meaning construction and syntactic language. The model thus shows a solution to the `symbol grounding problem' (Harnad, 1990): the meaning of the symbolic system - logical symbols and syntactic rules - is grounded in its relation with a simplified but realistic world. We discuss the different components of this collaborative effort: (i) a realistic simulation of Newtonian dynamics of objects in a 2D plane; (ii) schemabased event-perception and categorization; (iii) a semantics based on predicate logic; and (iv) a categorial grammar for the production and interpretation of language. The integration of the different components poses on the one hand novel and important constraints; on the other hand, it allows for experiments that help to identify the relations between the different levels. We note some important similarities and differences with SHRDLU (Winograd, 1976) and the Talking Heads experiment (Steels et al., 2002), and give an agenda for future experiments.

To create multi-agent systems that are both adaptive and open, agents must collectively learn to generate their own concepts, interpretations, and even languages actively in an online fashion. The issue is that there is no pre- existing global concept to be learned; instead, agents are in effect collectively designing a concept that is evolving as they exchange information. This paper presents a framework of {\it mutual online concept learning} (MOCL) in a shared world. MOCL extends the classical online concept learning from single-agent to multi-agent setting. Based on the Perceptron algorithm, we design a specific MOCL algorithm, called the {\it mutual perceptron convergence algorithm}, which can converge within a finite number of mistakes under some conditions. Analysis of the convergence conditions shows that the possibility of convergence depends on the number of participating agents and the quality of the instances they produce. Finally, we point out applications of MOCL and the convergence algorithm to the formation of linguistic knowledge in the form of dynamically generated shared vocabulary and grammar structure for multiple agents.

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

It is very costly to build up lexical resources and domain ontologies. Especially when confronted with a new application domain lexical gaps and a poor coverage of domain concepts are a problem for the successful exploitation of natural language document analysis systems that need and exploit such knowledge sources. In this paper we report about ongoing experiments with `bootstrapping techniques' for lexicon and ontology creation.

One of the most salient properties of phonological systems are their very consistency. This paper describes work suggesting that such categorical behavior in phonological systems can be modeled as an emergent property resulting from self-organization (Nicolas and Prigogine 1977) within an iterating, richly-specified lexicon.

Language is a uniquely human trait likely to have been a prerequisite for the development of human culture. The ability to develop articulate speech relies on capabilities, such as fine control of the larynx and mouth, that are absent in chimpanzees and other great apes. FOXP2 is the first gene relevant to the human ability to develop language. A point mutation in FOXP2 co-segregates with a disorder in a family in which half of the members have severe articulation difficulties accompanied by linguistic and grammatical impairment. This gene is disrupted by translocation in an unrelated individual who has a similar disorder. Thus, two functional copies of FOXP2 seem to be required for acquisition of normal spoken language. We sequenced the complementary DNAs that encode the FOXP2 protein in the chimpanzee, gorilla, orang-utan, rhesus macaque and mouse, and compared them with the human cDNA. We also investigated intraspecific variation of the human FOXP2 gene. Here we show that human FOXP2 contains changes in amino-acid coding and a pattern of nucleotide polymorphism, which strongly suggest that this gene has been the target of selection during recent human evolution.

Language is our legacy. It is the main evolutionary contribution of humans, and perhaps the most interesting trait that has emerged in the past 500 million years. Understanding how darwinian evolution gives rise to human language requires the integration of formal language theory, learning theory and evolutionary dynamics. Formal language theory provides a mathematical description of language and grammar. Learning theory formalizes the task of language acquisition--it can be shown that no procedure can learn an unrestricted set of languages. Universal grammar specifies the restricted set of languages learnable by the human brain. Evolutionary dynamics can be formulated to describe the cultural evolution of language and the biological evolution of universal grammar.

Linguistic metaphors have been woven into the fabric of molecular biology since its inception. The determination of the human genome sequence has brought these metaphors to the forefront of the popular imagination, with the natural extension of the notion of DNA as language to that of the genome as the 'book of life'. But do these analogies go deeper and, if so, can the methods developed for analysing languages be applied to molecular biology? In fact, many techniques used in bioinformatics, even if developed independently, may be seen to be grounded in linguistics. Further interweaving of these fields will be instrumental in extending our understanding of the language of life.

We argue that an understanding of the faculty of language requires substantial interdisciplinary cooperation. We suggest how current developments in linguistics can be pro.tably wedded to work in evolutionary biology, anthropology, psychology, and neuroscience. We submit that a distinction should be made between the faculty of language in the broad sense (FLB)and in the narrow sense (FLN). FLB includes a sensory-motor system, a conceptual-intentional system, and the computational mechanisms for recursion, providing the capacity to generate an in.nite range of expressions from a finite set of elements. We hypothesize that FLN only includes recursion and is the only uniquely human component of the faculty of language. We further argue that FLN may have evolved for reasons other than language, hence comparative studies might look for evidence of such computations outside of the domain of communication (for example, number, navigation, and social relations).

The lexicon consists of a set of word meanings and their semantic relationships. A systematic representation of the English lexicon based in psycholinguistic considerations has been put together in the database Wordnet in a long-term collaborative effort. We present here a quantitative study of the graph structure of Wordnet to understand the global organization of the lexicon. Semantic links follow power-law, scale-invariant behaviors typical of self-organizing networks. Polysemy (the ambiguity of an individual word) is one of the links in the semantic network, relating the different meanings of a common word. Polysemous links have a profound impact in the organization of the semantic graph, conforming it as a small world network, with clusters of high traffic (hubs) representing abstract concepts such as line, head, or circle. Our results show that: (i) Wordnet has global properties common to many self-organized systems, and (ii) polysemy organizes the semantic graph in a compact and categorical representation, in a way that may explain the ubiquity of polysemy across languages.

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

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

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

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

We work with a large spatialized array of individuals in an environment of drifting food sources and predators. The behavior of each individual is generated by its simple neural net; individuals arecapable of making one of two sounds and are capable of responding to sounds from their immediate neighbors by opening their mouths or hiding. An individual whose mouth is open in the presence of food is 'fed' and gains points; an individual who fails to hide when a predator is present is 'hurt' by losing points. Opening mouths, hiding, and making sounds each exact an energy cost. There is no direct evolutionary gain for acts of cooperation or 'successful communication' per se.

In such an environment we start with a spatialized array of neural nets with randomized weights. Using standard learning algorithms, our individuals 'train up' on the behavior of successful neighbors at regular intervals. Given that simple setup, will a community of neural nets evolve a simple language for signaling the presence of food and predators? With important qualifications, the answer is yes.'In a simple spatial environment, pursuing individualistic gains and using partial training on successful neighbors, randomized neural nets can learn to communicate.

It has been postulated that aspects of human language are both genetically and culturally transmitted. How might these processes interact to determine the structure of language? An agent-based model designed to study gene-culture interactions in the evolution of communication is introduced. This model shows that cultural selection resulting from learner biases can be crucial in determining the structure of communication systems transmitted through both genetic and cultural processes. Furthermore, the learning bias which leads to the emergence of optimal communication in the model resembles the learning bias brought to the task of communication by human infants. This suggests that the iterated application of such human learning biases may explain much of the structure of human language.

Human language is learned, symbolic and exhibits syntactic structure, a set of properties which make it unique among naturally-occurring communication systems. How did human language come to be as it is? Language is culturally transmitted and cultural processes may have played a role in shaping language. However, it has been suggested that the cultural transmission of language is constrained by some language-specific innate endowment. The primary objective of the research outlined in this paper is to investigate how such an endowment would influence the acquisition of language and the dynamics of the repeated cultural transmission of language. To this end, a new connectionist model of the cultural evolution of communication is presented. In this model an individual's innate endowment is considered to be a learning rule with an associated learning bias. The model allows manipulations to be made to this learning apparatus and the impact of such manipulations on the processes of language acquisition and language evolution to be explored. These investigations reveal that an innate endowment consisting of an ability to read the communicative intentions of others and a bias towards acquiring one-to-one mappings between meanings and signals results in the emergence, through purely cultural processes, of optimal communication. It has previously been suggested that humans possess just such an innate endowment. Properties of human language may therefore best be explained in terms of cultural evolution on an innate substrate.

The application of information theory to biology can be broadly split into three areas: (i) At the level of the genome; considering the storage of information using the genetic code. (ii) At the level of the individual animal; communication between animals passes information from one animal to another (usually, but not always, for mutual benefit). (iii) At the level of the population; the diversity of a population can be measured using population entropy. This paper is concerned with the second area. We consider the evolution of an individual's ability to obtain and process information using the ideas of evolutionary game theory. An important part of game theory is the definition of the information available to the participants. Such games tend to treat information as a static quantity whilst behaviour is strategic. We consider game theoretic modelling where use of information is strategic and can thus evolve. A simple model is developed which shows how the information acquiring ability of animals can evolve through time. The model predicts that it is likely that there is an optimal level of information for any particular contest, rather than more information being inherently better. The total information required for optimal performance corresponded to approximately the same entropy, regardless of the value of the individual pieces of information concerned.

Certain word types of natural languages - conjunctions, articles, prepositions and some verbs - have a very low or very grammatically marked semantic contribution. They are usually named functional categories or relational items. Recently, the possibility of considering prepositions as simple parametrical variations of semantic features instead of categorial features or as the irrelevance of such categorial features has been pointed out. The discussion about such particles has been and still is widespread and controversial. Nonetheless, there is no quantitative evidence of such semantic weakness and no satisfactory evidence against the coexistence of categorial requirements and the fragility of the semantic aspects. This study aims to quantify the semantic contribution of particles and presents some corpora-based results for English that suggest that such weakness and its relational uncertainty come from the categorial irrelevance mentioned before.

Linguistics and evolutionary biology have substantially diverged until recently. The chief reason for this divergence was the dominance of essentialist thinking in linguistics during the twentieth century. Croft (2000) describes a thoroughgoing application of Hull's (1988) generalized theory of selection to language change. In this model, tokens of linguistic structure in utterances (`linguemes') are replicators and speakers are interactors. Current debates in the philosophy of evolutionary biology (e.g. Sterelny and Griffiths, 1999) are then applied to language change. Hull's generalized theory is post-synthesis: it recognizes a distinction between replicator and interactor and is independent of levels of biological organization. Biological issues such as mechanisms of inheritance (e.g. Lamarckism) and of selection (e.g. intentional behavior) are simply irrelevant to the generalized theory of selection outside biology. However, there are many striking parallels between biological evolution and language change that are likely to be consequences of the generalized theory of selection, including flexibility of adaptation to the environment, emergent structure, evolutionary conservatism, vestigial traits, exaptation, and the absence of ``progress''. The evolutionary theory of language change is not evolutionary psychology, but it is mimetics; this approach is defended against Sterelny and Griffith's criticisms.

The evolution of species and languages are compared with respect to the distinction between homologies and homoplasies (or analogies), the prevalence of hybridism, the contrast between scenarios, trees and cladograms, the metaphysical nature of species and languages, and the sense in which the evolution of languages is or is not Lamarckian.

The primary thesis of this paper is that selection plays a role in language evolution. Underlying this position is the assumption that a language is a Lamarckian species, a construct extrapolated from idiolects spoken by individuals who acknowledge using the same verbal code to communicate with each other. There is no perfect replication in any case of language ``acquisition'', which is actually a recreation process in which the learner makes a system out of features selected from utterances of different individuals with whom he/she has interacted. In a way similar to gene recombination in biology, each learner gradually and selectively reintegrates into new system features which are often modified in the process. At the population level, the congruence of some divergent idiolectal selections is often strong enough for a language to evolve into a new communal system. A fundamental question for my hypothesis is: What principles regulate selection I also assume hybridism in language ``transmission'', which is polyploidic, as features of every idiolect originate not only in various competing idiolects, but possibly also in different dialects or languages in contact. The question about feature selection remains the same.

On various modern accounts, human language or some of its features evolved like the vertebrate eye by natural selection. The present article offers a critical appraisal of the way in which this idea is articulated in Pinker and Bloom's (1990) selectionist account of language evolution--the most sophisticated account of its kind. It is argued that this account is less than insightful since it fails to draw some of the conceptual distinctions that are central to a certain requirement for such selectionist accounts. The requirement states that language can be accorded the evolutionary status of an adaptation by natural selection if it exhibits complex adaptive design for some evolutionary significant function.

Random-text models have been proposed as an explanation for the power law relationship between word frequency and rank, the so-called Zipf's law. They are generally regarded as null hypotheses rather than models in the strict sense. In this context, recent theories of language emergence and evolution assume this law as a priori information with no need of explanation. Here, random texts and real texts are compared through (a) the so-called lexical spectrum and (b) the distribution of words having the same length. It is shown that real texts fill the lexical spectrum much more efficiently and regardless of the word length, suggesting that the meaningfulness of Zipf's law is high.

Human language may have started from a consistent set of mappings between meanings and signals. These mappings, referred to as the early vocabulary, are considered to be the results of conventions established among the agents of a population. In this study, we report simulation models for investigating how such conventions can be reached. We propose that convention is essentially the product of self-organization of the population through interactions among the agents; and that cultural selection is another mechanism that speeds up the establishment of convention. Whereas earlier studies emphasized either one or the other of these two mechanisms, our focus is to integrate them into one hybrid model. The combination of these two complementary mechanisms, i.e. self-organization and cultural selection, provides a plausible explanation for cultural evolution which progresses with high transmission rate. Furthermore, we observe that as the vocabulary tends to convergence there is a uniform tendency to exhibit a sharp phase transition.

In this paper we present some multiagent simulations in which the individuals try to reach a uniform vocabulary to name spatial movements. Each agent has initially a random vocabulary that can be modified by means of interactions with the other agents. As the objective is to name movements, the topic of conversation is chosen by moving. Each agent can remember a finite number of words per movement, with certain strength. We show the importance of the forgetting process and memory size in these simulations, discuss the effect of the number of agents on the time to agree and present a few experiments where the evolution of vocabularies takes place in a divided range.

This is an overview of recent computational work done in the simulated evolution of language. It is prefaced by an overview of the broader issues in linguistics that computational models may help to clarify. Is language innate - genetically specified in the human organism in some way, a product of natural selection? Or can the properties of language be accounted for by general cognitive capabilities that did not develop as a consequence of language-specific selective pressures? After a consideration of the intellectual background surrounding these issues, we will examine how recent computational work sheds light on them.

The traditional theory equating the brain bases of language with Broca's and Wernicke's neocortical areas is wrong. Neural circuits linking activity in anatomically segregated populations of neurons in subcortical structures and the neocortex throughout the human brain regulate complex behaviors such as walking, talking, and comprehending the meaning of sentences. When we hear or read a word, neural structures involved in the perception or real-world associations of the word are activated as well as posterior cortical regions adjacent to Wernicke's area. Many areas of the neocortex and subcortical structures support the cortical-striatal-cortical circuits that confer complex syntactic ability, speech production, and a large vocabulary. However, many of these structures also form part of the neural circuits regulating other aspects of behavior. For example, the basal ganglia, which regulate motor control, are also crucial elements in the circuits that confer human linguistic ability and abstract reasoning. The cerebellum, traditionally associated with motor control, is active in motor learning. The basal ganglia are also key elements in reward-based learning. Data from studies of Broca's aphasia, Parkinson's disease, hypoxia, focal brain damage, and a genetically transmitted brain anomaly (the putative ``language gene,'' family KE), and from comparative studies of the brains and behavior of other species, demonstrate that the basal ganglia sequence the discrete elements that constitute a complete motor act, syntactic process, or thought process. Imaging studies of intact human subjects and electrophysiologic and tracer studies of the brains and behavior of other species confirm these findings. As Dobzansky put it, ``Nothing in biology makes sense except in the light of evolution'' (cited in Mayr, 1982). That applies with as much force to the human brain and the neural bases of language as it does to the human foot or jaw. The converse follows: the mark of evolution on the brains of human beings and other species provides insight into the evolution of the brain bases of human language. The neural substrate that regulated motor control in the common ancestor of apes and humans most likely was modified to enhance cognitive and linguistic ability. Speech communication played a central role in this process. However, the process that ultimately resulted in the human brain may have started when our earliest hominid ancestors began to walk.

Communication plays a vital role in the organization and operation of biological, computational, economic, and social systems. Agents often base their behavior on the signals they receive from others and also recognize the importance of the signals they send. Here we develop a framework for analyzing the emergence of communication in an adaptive system. The framework enables the study of a system composed of agents who evolve the ability to strategically send and receive communication. While the modeling framework is quite general, we focus here on a specific application, namely the analysis of cooperation in a single shot Prisoner?s Dilemma. We find that contrary to initial expectations, communication allows the emergence of cooperation in such a system. Moreover, we find a systematic relationship between the processing and language complexity inherent in the communication system and the observed behavior. The approach developed here should open up a variety of phenomena to the systematic exploration of endogenous, strategic communication.

How do social values come about and gain legitimacy? Starting from the premise that discourses of social analysis affect the ways in which social norms develop and proliferate, this article models the evolution of professional codes and dialects using Wittgenstein's idea of a language game. A language game is formalized as a repeated game of tacit coordination played among participants with informational asymmetries. The informational asymmetries model the different meanings that people assign to the same word used in a conversation. A language is formalized as a code that emerges as a result of repeated interactions in a language game. The paper argues that certain codes--such as those based on the real number system--lead to more reliable strategies in language games. The result is used to argue that professional dialects based on axiomatizable codes--such as physics, mathematics and economics--are less likely to experience fragmentation into intra-disciplinary 'sects,' camps and incommensurable paradigms than are professional dialects that are not based on an axiomatizable code--such as sociology, psychology, organization studies, and strategic management studies. The idea of a language game is extended to explore ways in which certain disciplines can establish cognitive jurisdiction over particular phenomena, starting from a particular set of codes, and thereby claim 'cognitive monopolies.' A rudimentary theory of the market for ideas is advanced.

We define two words in a language to be connected if they express similar concepts. The network of connections among the many thousands of words that make up a language is important not only for the study of the structure and evolution of languages, but also for cognitive science. We study this issue quantitatively, by mapping out the conceptual network of the English language, with the connections being defined by the entries in a Thesaurus dictionary. We find that this network presents a small-world structure, with an amazingly small average shortest path, and appears to exhibit an asymptotic scale-free feature with algebraic connectivity distribution.

The perspective of this paper is to compare mathematical models for the evolutionary dynamics of genomes and languages. The quasispecies equation describes the evolution of genetic sequences under the influence of mutation and selection. A central result is an error threshold which specifies the minimum replication accuracy required for maintaining genetic information of a certain length. The language equation describes the evolution of communication, including the cultural evolution of grammar and the biological evolution of universal grammar. A central result is a coherence threshold which specifies certain conditions that universal grammar has to fulfill in order to induce coherent communication in a population.

We investigate common design decisions for constructing a computational genetic language in an autoadaptive system. Such languages must support self-replication and are typically Turing-complete so as not to limit the types of computations they can perform. We examine the importance of using templates to denote locations in the genome, the methods by which those templates are located (direct-matching versus complementmatching), methods used in the calculation of genome length and the size and complexity of the language. For each test, we examine the effects on the rate of evolution of the populations and isolate those factors that contribute to it, most notably the organisms' ability to withstand mutations.

This article presents a formal framework and outlines a method that autonomous agents can use to negotiate the semantics of their communication language at run-time. Such an ability is needed in open multi-agent systems so that agents can ensure they understand the implications of the utterances that are being made and so that they can tailor the meaning of the primitives to best fit their prevailing circumstances. To this end, the semantic space framework provides a systematic means of classifying the primitives along multiple relevant dimensions. This classification can then be used by the agents to structure their negotiation (or semantic fixing) process so that they converge to the mutually agreeable semantics that are necessary for coherent social interactions.

This paper reports the results of an attempt to recover the first-order subgrouping of the Indo-European family using a new computational method devised by the authors and based on a 'perfect phylogeny' algorithm. The methodology is also briefly described, and points of theory and methodology are addressed in connection with the experiment whose results are here reported.

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

How does a group of individuals who lack a shared communication system evolve to achieve a consensus, so that every member of the group uses each signal in a manner consistent with others in the group? There are many factors that affect the difficulty of this task, including the number of signals available, the number of meanings or situations to convey, the population size, and whether or not any learning occurs. Each of these factors is explored in simulations which use a genetic algorithm that selects for agents who communicate meanings effectively with other agents. The difficulty of gaining consensus among a population of signalers increases as the number of meanings (and signals) increases, but decreases if more signals than meanings are allowed. Surprisingly, difficulty decreases as population size increases. An analysis is made of the exponentially increasing difficulty of achieving consensus as the number of meanings and signals grows. The implications for the evolution of communication are discussed.

Scholars studying the origins and evolution of language are also interested in the general issue of the evolution of cognition. Language is not an isolated capability of the individual, but has intrinsic relationships with many other behavioral, cognitive, and social abilities. ...

As language users humans possess a culturally transmitted system of unparalleled complexity in the natural world. Linguistics has revealed over the past 40 years the degree to which the syntactic structure of language in particular is strikingly complex. Furthermore, as Pinker and Bloom point out in their agenda-setting paper Natural Language and Natural Selection ``grammar is a complex mechanism tailored to the transmission of propositional structures through a serial interface'' (Pinker and Bloom, 1990, 707). These sorts of observations, along with influential arguments from linguistics and psychology about the innateness of language (see, e.g. Chomsky, 1986; Pinker, 1994), have led many authors to the conclusion that an explanation for the origin of syntax must invoke neo-Darwinian natural selection.

``Evolutionary theory offers clear criteria for when a trait should be attributed to natural selection: complex design for some function, and the absence of alternative processes capable of explaining such complexity. Human language meets these criteria.'' (Pinker and Bloom, 1990, 707)

Since Pinker and Bloom made these arguments there have been many attempts to put forward a coherent evolutionary story that would allow us to derive known features of syntax from communicative selection pressures (e.g. Nowak, Plotkin, and Jansen, 2000; Newmeyer, 1991 and discussion in Kirby, 1999a). One problem with this approach to evolutionary lin- guistics is that it often fails to take into account that biological natural selection is only one of the complex adaptive systems at work.

Language emerges at the intersection of three complex adaptive systems:

• Learning: During ontogeny children adapt their knowledge of language in response to the environment in such a way that they optimise their ability to comprehend others and to produce comprehensible utterances.
• Cultural evolution: On a historical (or glossogenetic) timescale, languages change. Words enter and leave the language, meanings shift, and phonological and syntactic rules ad- just.
• Biological evolution: The learning (and processing) mechanisms with which our species has been equipped for language, adapt in response to selection pressures from the environ- ment, for survival and reproduction.

There are two problems with this multiplicity of dynamical systems involved in linguistic evolution. Firstly, we understand very little about how learning, culture, and evolution inter- act (though, see Belew, 1990; Kirby and Hurford, 1997; Boyd and Richerson, 1985), partly because language is arguably the only sophisticated example of such a phenomenon. There clearly are interactions: for example, biological evolution provides the platform on which learning takes place, what can be learnt influences the languages that can persist through cultural evolution, and the structure of the language of a community will influence the selec- tion pressures on the evolving language users (see figure 1).

Secondly, it is not clear what methodology we should use to study this problem. Mathe- matical techniques for looking at the interaction of dynamical systems and linguistic behaviour are in their infancy (though, Nowak, Komarova, and Niyogi, 2001, take a potentially valuable approach). We feel that computational modelling is currently the most appropriate method- ology, but although simulations of language learning have a long history, and there are many methods from the A-life field that can be used for modelling evolution, models of the cultural transmission of learned behaviour are relatively sparse (see Steels, 1997 for a review). This is unfortunate, since we will argue in this chapter that it is through this particular mechanism that the most basic features of human language syntactic structure can be explained.

To remedy this situation, we introduce here the Iterated Learning Model (ILM), a gen- eral approach to exploring the transmission over a glossogenetic timescale of observationally learned behaviour. We will illustrate the ILM with a few examples of simulations that lead to two conclusions:

• There is a non-trivial mapping between the set of learnable languages (i.e. the lan- guages allowed by our innate language faculty), and the set of stable languages (i.e., the languages we can actually expect to see in the world).
• Under certain circumstances, cultural evolution leads inevitably to recursively compo- sitional (i.e., syntactic) languages.

Х вн г и ди жз в и з гг к дджг йб в а в й л и в н иг из йв ей ийж зИ зй з ж йжз к знви мИ гж а ж а жв а м гвК Я джгдгз иг и л ж к лИ з в йб в а в й з гв бгв б вн в б а гббйв и гв знзи бзИ в г йз в гв и з а и к дж ззйж з Ћ иЙ в и гж в в б ви в в г зй знзи бзК Ь дгзз а ин и и йб в а в й ...

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references. ... Harler P. Evans C, Hauser M (1992) Animal signals: Motivational, referential, or both? In: ...

This chapter argues that the ability to imitate is a key innovation in the evolutionary path leading to language in the human and relates this hypothesis to specific data on brain mechanisms. In this context, imitation involves more than simply observing someone else's movement and responding with movement that in its entirety is already in one's own repertoire, imitation involves 'parsing' a complex movement. What marks humans as distinct from their common ancestors with chimpanzees is that whereas the chimpanzee can imitate short novel sequences through repeated exposure, humans can acquire (longer) novel sequences in a single trial if the sequences are not too long and the components are relatively familiar. This chapter will take us through seven hypothesized stages of evolution: (1) grasping; (2) a mirror system for grasping; (3) a simple imitation system for grasping; (4) a complex imitation system for grasping; (5) a manual-based communication system; (6) speech, which I here characterize as being the open-ended production and perception of sequences of vocal gestures, without implying that these sequences constitute a language; and (7) language.

Of the known animal communication systems, human languages appear to be unique in their use of recursively characterizable structural relations among sequences of sounds or gestures and the meanings those sequences can be used to express.

The patterns of structural relations that recursion makes possible can serve a range of communicative functions, tremendously extending the expressive resources of the system. Certain structural relations may be used to express specific meanings, or to modify, or extend, or restrict the meanings conveyed by words and other simple constituents.

Despite the unbounded complexity it makes possible, a recursive communicative system can be learned relatively easily because the constituents of a complex construction may themselves be simpler instances of that same kind of construction, and the properties of complex constructions are often predictable from simpler counterparts.

The research described in this paper is an investigation of how recursive communication systems can come to be. In particular, the investigation explores the possibility that such a system could emerge among the members of a population as the result of a process I characterize as ``negotiation,'' because each individual both contributes to, and conforms with, the system as it develops. The members of the population are assumed to possess general cognitive capacities sufficient for communicative behavior, and for learning to modify their behavior based on observations of others. However they are given no external guidance about how their communication system is to work, and their internal cognitive mechanisms impose few specific constraints.

A specific model of the ...

(In Linguistic Evolution through Language Acquisition: Formal and Computational Models, edited by Ted Briscoe, Cambridge University Press. pp.301-344. Note: This HTML version may differ slightly from the printed version; the printed version is the `authorized' version. See a ...

Human language is a unique natural communication system for two rea- sons. Firstly, the mapping from meanings to signals in language has structural properties that are not found in any other animal's communi- cation systems. In particular, syntax gives us the ability to produce an in nite range of expressions through the dual tools of compositionality and recursion. Compositionality is defined here as the property whereby an expression's meaning is a function of the meanings of parts of that expression and the way they are put together. Recursion is a property of languages with finite lexica and rule-sets in which some constituent of an expression can contain a constituent of the same category. Together with recursion, compositionality is the reason that this in finite set of expressions can be used to express different meanings.

Secondly, at least some of the content of this mapping is learned by children through observation of others' use of language. This seems not to be true of most, maybe all, of animal communication (see review in Oliphant, this volume). In this chapter I formally investigate the interaction of these two unique properties of human language: the way it is learned and its syntactic structure.

While most work on the evolution of language has been centered on the evolution of syntax, my focus in this paper is instead on more basic features that separate human communication from the systems of communication used by other animals. In particular, I argue that human language is the only existing system of learned arbitrary reference. While innate communication systems are, by definition, directly transmitted genetically, the transmission of a learned systems must be indirect. Learners must acquire the system by being exposed its the use in the community. Although it is reasonable that a learner has access to the utterances that are produced, it is less clear how accessible the meaning is that the utterance is intended to convey. This particularly problematic if the system of communication is symbolic -- where form and meaning are linked in a purely conventional way. Given this, I propose that the ability to transmit a learned symbolic system of communication from one generation to the next represents a key milestone in the evolution of language.

Introduction

The acquisition and processing of language is governed by a number of universal constraints, many of which undoubtedly derive from innate properties of the human brain. These constraints lead to certain universal tendencies in how languages are structured and used. More generally, the constraints help explain why the languages of the world take up only a small part of the considerably larger space de. ned by the logically possible linguistic subpatterns. Although there is broad consensus about the existence of innate constraints on the way language is acquired and processed, there is much disagreement over whether these constraints are linguistic or cognitive in nature. Determining the nature of these constraints is important not only for theories of language acquisition and processing, but also for theories of language evolution. Indeed, these issues are theoretically intertwined because the constraints on language define the endpoints for evolutionary explanations: theories about how the constraints evolved in the hominid lineage are thus strongly determined by what the nature of these constraints is taken to be.

The Chomskyan approach to language suggests that the constraints on the acquisition and processing of language are linguistic, rather than cognitive, in nature. Th e constraints are represented in the form of a Universal Grammar (UG)--a large biological endowment of linguistic knowledge (e.g. Chomsky 1986). It is assumed that this knowledge-base is highly abstract, comprising a complex set of linguistic rules and principles that could not be acquired from exposure to language during development. Opinions differ about how UG emerged as the endpoint of language evolution. Some researchers have suggested that it evolved through a gradual process of natural selection (e.g., Newmeyer 1991; Pinker 1994; Pinker and Bloom 1990), whereas others have argued for a sudden emergence through non-adaptationist evolutionary processes (e.g., Bickerton 1995; Piattelli-Palmarini 1989). An important point of agreement is the emphasis in their explanations of language evolution on the need for very substantial biological changes to accommodate linguistic structure.

More recently an alternative perspective is gaining ground, advocating a refocus in thinking about language evolution. Rather than concentrating on biological changes to accommodate language, this approach stresses the adaptation of linguistic structures to the biological substrate of the human brain (e.g., Batali 1998; Christiansen 1994; Christiansen and Devlin 1997; Deacon 1997; Kirby 1998, 2000, 2001). Languages are viewed as dynamic systems of communication, subject to selection pressures arising from limitations on human learning and processing. Some approaches within this framework have built in a certain amount of linguistic machinery, such as context-free grammars (Kirby 2000). In this chapter we argue that many of the constraints on linguistic adaptation derive from non-linguistic limitations on the learning and processing of hierarchically organized sequential structure. Th ese mechanisms existed prior to the appearance of language, but presumably also underwent changes aft er the emergence of language. However, the selection pressures are likely to have come not only from language but also from other kinds of complex hierarchical processing, such as the need for increasingly complex manual combinations following tool sophistication. Consequently, many language universals may re. ect nonlinguistic, cognitive constraints on learning and processing of sequential structure rather than an innate UG.

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

Using computational modeling techniques, this paper explores the range of conditions under which structured, language-like communication systems can emerge. In particular, we reconsider Simon Kirby's learning bottleneck model of linguistic adaptation using a different learning mechanism and different semantic domain. We demonstrate how parameters such as population size and training corpus size affect the likelihood of a population reaching consensus on a structure communication system.

Many special problems crop up when evolutionary theory turns, quite naturally, to the question of the adaptive value and causal role of consciousness in human and nonhuman organisms. One problem is that -- unless we are to be dualists, treating it as an independent nonphysical force -- consciousness could not have had an independent adaptive function of its own, over and above whatever behavioral and physiological functions it ``supervenes'' on, because evolution is completely blind to the difference between a conscious organism and a functionally equivalent (Turing Indistinguishable) nonconscious ``Zombie'' organism: In other words, the Blind Watchmaker, a functionalist if ever there was one, is no more a mind reader than we are. Hence Turing-Indistinguishability = Darwin-Indistinguishability. It by no means follows from this, however, that human behavior is therefore to be explained only by the push-pull dynamics of Zombie determinism, as dictated by calculations of ``inclusive fitness'' and ``evolutionarily stable strategies.'' We are conscious, and, more important, that consciousness is piggy-backing somehow on the vast complex of unobservable internal activity -- call it ``cognition'' -- that is really responsible for generating all of our behavioral capacities. Hence, except in the palpable presence of the irrational (e.g., our sexual urges) where distal Darwinian factors still have some proximal sway, it is as sensible to seek a Darwinian rather than a cognitive explanation for most of our current behavior as it is to seek a cosmological rather than an engineering explanation of an automobile's behavior. Let evolutionary theory explain what shaped our cognitive capacity (Steklis and Harnad 1976; Harnad 1996, but let cognitive theory explain our resulting behavior.

Already hailed as a masterpiece, Foundations of Language offers a brilliant overhaul of the last thirty-five years of research in generative linguistics and related fields." Few books really deserve the cliche'this should be read by every researcher in the field,'" writes Steven ...

Linguists, biological anthropologists, and cognitive scientists come together in this book to explore the origins and early evolution of phonology, syntax, and semantics. They consider the nature of pre-and proto-linguistic communication, the internal and external triggers that ...

Humans perceive a continuous colour spectrum, but divide the spectrum into colour categories in order to reason and communicate about colour. There is an ongoing debate on whether these colour categories necessary for language communication are universal or culture-specific, whether these categories are genetically determined or learned, and whether there is a causal influence of language on colour category acquisition or not. The dissertation presents a number of models, each examining one of these outstanding issues. The models draw on techniques from multi-agent systems, machine learning and evolutionary programming. After considering the behaviour of each model, we conclude in favour of a cultural specificity of language categories and argue that learning under the influence of language is the most plausible explanation for their acquisition.

The PhD thesis titled ``An Agent-Based Evolutionary Computing Approach to Memory-Based Syntactic Parsing of Natural Language'' introduces the grael system (grammar evolution) as one of the first research efforts that investigates an agent-based evolutionary computing approach as a possible machine learning method for data-driven grammar optimization and induction. Using the same architecture, but different information sources, grael can be shown to handle a diverse range of grammar engineering tasks, which can help resolve common issues in corpus-based parsing systems, such as insufficient grammar coverage and the suboptimal distribution of probability mass.

Since the PhD thesis covers a considerable array of research issues, which may not be relevant to all researchers alike, this web page is further subdivided into thematic units. If you want to read the entire thesis, please go to the full download page...