Language Evolution and Computation Bibliography

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

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

Traditional theories of child language acquisition center around the existence of a language acquisition device which is specifically tuned for learning a particular class of languages. More recent proposals suggest that language acquisition is assisted by the evolution of languages towards forms that are easily learnable. In this paper, we evolve combinatorial languages which can be learned by a simple recurrent network quickly and from relatively few examples. Additionally, we evolve languages for generalization in different ``worlds'', and for generalization from specific examples. We find that languages can be evolved to facilitate different forms of impressive generalization for a minimally biased learner. The results provide empirical support for the theory that the language itself, as well as the language environment of a learner, plays a substantial role in learning: that there is far more to language acquisition than the language acquisition device.

Animal communication is typically non-syntactic, which means that signals refer to whole situations. Human language is syntactic, and signals consist of discrete components that have their own meaning. Syntax is a prerequisite for taking advantage of combinatorics, that is, 'making infinite use of finite means'. The vast expressive power of human language would be impossible without syntax, and the transition from non-syntactic to syntactic communication was an essential step in the evolution of human language. We aim to understand the evolutionary dynamics of this transition and to analyse how natural selection can guide it. Here we present a model for the population dynamics of language evolution, define the basic reproductive ratio of words and calculate the maximum size of a lexicon. Syntax allows larger repertoires and the possibility to formulate messages that have not been learned beforehand. Nevertheless, according to our model natural selection can only favour the emergence of syntax if the number of required signals exceeds a threshold value. This result might explain why only humans evolved syntactic communication and hence complex language.

This study shows that a corpus of proto-word forms shares four sequential sound patterns with words of modern languages and the first words of infants. Three of the patterns involve intrasyllabic consonant-vowel (CV) co-occurrence: labial (lip) consonants with central vowels, coronal (tongue front) consonants with front vowels, and dorsal (tongue back) consonants with back vowels. The fourth pattern is an intersyllabic preference for initiating words with a labial consonant-vowel-coronal consonant sequence (LC). The CV effects may be primarily biomechanically motivated. The LC effect may be self-organizational, with multivariate causality. The findings support the hypothesis that these four patterns were basic to the origin of words.

Humans, but no other animal, make meaningful use of spoken language. What is unclear, however, is whether this capacity depends on a unique constellation of perceptual and neurobiological mechanisms or whether a subset of such mechanisms is shared with other organisms. To explore this problem, parallel experiments were conducted on human newborns and cotton-top tamarin monkeys to assess their ability to discriminate unfamiliar languages. A habituation-dishabituation procedure was used to show that human newborns and tamarins can discriminate sentences from Dutch and Japanese but not if the sentences are played backward. Moreover, the cues for discrimination are not present in backward speech. This suggests that the human newborns' tuning to certain properties of speech relies on general processes of the primate auditory system.

The evolution of speech can be studied independently of the evolution of language, with the advantage that most aspects of speech acoustics, physiology and neural control are shared with animals, and thus open to empirical investigation. At least two changes were necessary prerequisites for modern human speech abilities: (1) modification of vocal tract morphology, and (2) development of vocal imitative ability. Despite an extensive literature, attempts to pinpoint the timing of these changes using fossil data have proven inconclusive. However, recent comparative data from nonhuman primates have shed light on the ancestral use of formants (a crucial cue in human speech) to identify individuals and gauge body size. Second, comparative analysis of the diverse vertebrates that have evolved vocal imitation (humans, cetaceans, seals and birds) provides several distinct, testable hypotheses about the adaptive function of vocal mimicry. These developments suggest that, for understanding the evolution of speech, comparative analysis of living species provides a viable alternative to fossil data. However, the neural basis for vocal mimicry and for mimesis in general remains unknown.

Evolutionary models of communication are used to shed some light on the selective pressures involved in the evolution of simple referential signals, and the constraints hindering the emergence of signs. Error-prone communication results from errors in transmission (in which individuals learn the wrong associations) and communication (in which signs are mistaken for one another). We demonstrate how both classes of errors are required to generate diversity and subsequently impose limits on the sign repertoire within a population. We then explore the influence of geographic structuring of a population on the evolution of a shared sign system and the importance of such structure for the maintenance of sign diversity. Deceit tends to erode conventional signs systems thereby reducing signal diversity, we demonstrate that population structure can act as a hedge against deceit, thereby ensuring the persistence of sign systems.

Language is about words and rules. While there is some discussion to what extent rules are learned or innate, it is clear that words have to be learned. Here I construct a mathematical framework for the population dynamics of language evolution with particular emphasis on how words are propagated over generations. I define the basic reproductive ratio of word, R, and show that R>1 is required for words to be maintained in the lexicon of a language. Assuming that the frequency distribution of words follow Zipf's law, an upper limit is obtained for the number of words in a language that relies exclusively on oral transmission.

This paper places models of language evolution within the framework of information theory. We study how signals become associated with meaning. If there is a probability of mistaking signals for each other, then evolution leads to an error limit: increasing the number of signals does not increase the fitness of a language beyond a certain limit. This error limit can be overcome by word formation: a linear increase of the word length leads to an exponential increase of the maximum fitness. We develop a general model of word formation and demonstrate the connection between the error limit and Shannon's noisy coding theorem.

Language is the most important evolutionary invention of the last few million years. It was an adaptation that helped our species to exchange information, make plans, express new ideas and totally change the appearance of the planet. How human language evolved from animal communication is one of the most challenging questions for evolutionary biology. The aim of this paper is to outline the major principles that guided language evolution in terms of mathematical models of evolutionary dynamics and game theory. I will discuss how natural selection can lead to the emergence of arbitrary signs, the formation of words and syntactic communication.

Neural network models of categorical perception (compression of withincategory similarity and dilation of between-category differences) are applied to the symbol-grounding problem (of how to connect symbols with meanings) by connecting analogue sensorimotor projections to arbitrary symbolic representations via learned category-invariance detectors in a hybrid symbolic/non-symbolic system. Our nets are trained to categorize and name 50 2 50 pixel images (e.g. circles, ellipses, squares and rectangles) projected on to the receptive field of a 7 2 7 retina. They first learn to do prototype matching and then entry-level naming for the four kinds of stimuli, grounding their names directly in the input patterns via hidden-unit representations ('sensorimotor toil'). We show that a higher-level categorization (e.g. 'symmetric' versus 'asymmetric') can be learned in two very different ways: either (1) directly from the input, just as with the entry-level categories (i.e. by toil); or (2) indirectly, from Boolean combinations of the grounded category names in the form of propositions describing the higher-order category ('symbolic theft'). We analyse the architectures and input conditions that allow grounding (in the form of compression/ separation in internal similarity space) to be 'transferred' in this second way from directly grounded entry-level category names to higher-order category names. Such hybrid models have implications for the evolution and learning of language.

Social coordination is studied in a simulated model of autonomous embodied agents that interact acoustically. Theoretical concepts concerning social behavior are presented from a systemic perspective and their usefulness is evaluated in interpreting the results obtained. Two agents moving in an unstructured arena must locate each other, and remain within a short distance of one another for as long as possible using noisy continuous acoustic interaction. Evolved dynamical recurrent neural networks are used as the control architecture. Acoustic coupling poses nontrivial problems like discriminating `self' from `non-self' and structuring production of signals in time so as to minimize interference. Detailed observation of the most frequently evolved behavioral strategy shows that interacting agents perform rhythmic signals leading to the coordination of movement. During coordination, signals become entrained in an anti-phase mode that resembles turn-taking. Perturbation techniques show that signalling behavior not only performs an external function, but it is also integrated into the movement of the producing agent, thus showing the difficulty of separating behavior into social and non- social classes. Structural congruence between agents is shown by exploring internal dynamics as well as the response of single agents in the presence of signalling beacons that reproduce the signal patterns of the interacting agents. Lack of entrainment with the signals produced by the beacons shows the importance of transient periods of mutual dynamic perturbation wherein agents achieve congruence.

We analyze a general model of multi-agent communication in which all agents communicate simultaneously to a message board. A genetic algorithm is used to evolve multi-agent languages for the predator agents in a version of the predator-prey pursuit problem. We show that the resulting behavior of the communicating multi-agent system is equivalent to that of a Mealy finite state machine whose states are determined by the agents' usage of the evolved language. Simulations show that the evolution of a communication language improves the performance of the predators. Increasing the language size (and thus increasing the number of possible states in the Mealy machine) improves the performance even further. Furthermore, the evolved communicating predators perform significantly better than all previous work on similar prey. We introduce a method for incrementally increasing the language size, which results in an effective coarse-to-fine search that significantly reduces the evolution time required to find a solution. We present some observations on the effects of language size, experimental setup, and prey difficulty on the evolved Mealy machines. In particular, we observe that the start state is often revisited, and incrementally increasing the language size results in smaller Mealy machines. Finally, a simple rule is derived that provides a pessimistic estimate on the minimum language size that should be used for any multi-agent problem.

For many adaptive complex systems information about the environment is not simply recorded in a look-up table, but is rather encoded in a theory, schema, or model, which compresses the information. The grammar of a language can be viewed as such a schema or theory. In a prior study [Teal et al., 1999] we proposed several conjectures about the learning and evolution of language that should follow from these observations: (C1) compression aids in generalization; (C2) compression occurs more easily in a smooth, as opposed to a rugged, problem space; and (C3) constraints from compression make it likely that natural languages eveolve toward smooth string spaces. This previous work found general, if not complete support for these three conjectures. Here we build on that study to clarify the relationship between Minimum Description Length (MDL) and error in our model and examine evolution of certain languages in more detail. Our results suggest a fourth conjecture: that all else being equal, (C4) more complex languages change more rapidly during evolution.

Using communication is not the only cooperative strategy that can evolve when organisms need to solve a problem together. This article describes a model that extends MacLennan and BurghardtOs [37] synthetic ethology simulation to show that using a spatial world in a simulation allows a wider range of strategies to evolve in response to environmental demands. The model specifically explores the interaction between population density and resource abundance and their effect on the kinds of cooperative strategies that evolve. Signaling strategies evolve except when population density is high or resource abundance is low.

Our understanding of speech and language disorders may be aided by information about the constraints and predispositions contributed by neural developmental processes. As soon as we begin to look at human neuroanatomy and development from a comparative perspective, it is possible to recognize a number of ways that human brains diverge from the general pattern of other ape and monkey brains. These divergences may offer clues to language evolution. Large-scale quantitative changes in the relative proportions of brain regions (as opposed to just overall expansion) offer some of the most obvious clues. Additional information about how axons are guided in their extensions to distant developmental targets and how competitive trophic processes sculpt these connections also provides a way to understand how gross quantitative changes in cell numbers could affect circuit organization and ultimately behavior.

This paper describes a model of the emergence and the universal structural tendencies of vowel systems. Both are considered as the result of self-organisation in a population of language users. The language users try to imitate each other and to learn each other's vowel systems as well as possible under constraints of production and perception, while at the same time maximising the number of available speech sounds. It is shown through computer simulations that coherent and natural sound systems can indeed emerge in populations of artificial agents. It is also shown that the mechanism that is responsible for the emergence of sound systems can be used for learning existing sound systems as well. Finally, it is argued that the simulation of agents that can only produce isolated vowels is not enough. More complex utterances are needed for other interesting universals of sound systems and for explaining realistic sound change.

This paper presents a computer simulation of the emergence of vowel systems in a population of agents. The agents (small computer programs that operate autonomously) are equipped with a realistic articulatory synthesizer, a model of human perception and the ability to imitate and learn sounds they hear. It is shown that due to the interactions between the agents and due to self-organization, realistic vowel repertoires emerge. This happens under a large number of different parameter settings and therefore seems to be a very robust phenomenon. The emerged vowel systems show remarkable similarities with the vowel systems found in human languages. It is argued that self-organization probably plays an important role in determining the vowel inventories of human languages and that innate predispositions are probably not necessary to explain the universal tendencies of human vowel systems.

In this paper, we present several experiments of belief propagation in multi-agent communities. Each agent in the simulation has an initial random vocabulary (4 words) corresponding to each possible movement (north, south, east and west). Agents move and communicate the associated word to the surrounding agents, which can be convinced by the 'speaking agent', and change their corresponding word by 'imitation'. Vocabulary uniformity is achieved, but strong interactions and competition can occur between dominant words. Several moving and trusting strategies as well as agent roles are analyzed.

If I find that a book I am reading for review is interesting, then I count myself lucky. If it turns out to be insightful, then I am fortunate indeed. The fact that I was given three books to review, each of which is not only interesting and insightful, but downright ENJOYABLE, ...

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

We study an evolutionary language game that describes how signals become associated with meaning. In our context, a language, L, is described by two matrices: the P matrix contains the probabilities that for a speaker certain objects are associated with certain signals, while the Q matrix contains the probabilities that for a listener certain signals are associated with certain objects. We define the payoff in our evolutionary language game as the total amount of information exchanged between two individuals. We give a formal classification of all languages, L(P, Q), describing the conditions for Nash equilibria and evolutionarily stable strategies (ESS). We describe an algorithm for generating all languages that are Nash equilibria. Finally, we show that starting from any random language, there exists an evolutionary trajectory using selection and neutral drift that ends up with a strategy that is a strict Nash equilibrium (or very close to a strict Nash equilibrium).

If every productive form of linguistic expression can be described by some idealized human grammar, an individuals's variable linguistic behavior (Weinreich, Labov, & Herzog, 1968) can be modeled as a statistical distribution of multiple idealized grammars. The distribution of grammars is determined by the interaction between the biological constraints on human grammar and the properties of linguistic data in the environment during the course of language acquisition. Such interaction can be formalized precisely and quantitatively in a mathematical model of language learning. Consequently, we model language change as the change in grammar distribution over time, which can be related to the statistical properties of historical linguistic data. As an empirical test, we apply the proposed model to explain the loss of the verb-second phenomenon in Old French and Old English based on corpus studies of historical texts.

Language is the main distinctive feature of our species. Why do we feel the urge to communicate with our fellows, and why is this form of communication, characterised by relevance, unique in animal kingdom ? In this chapter, we will first stress this specificity of human communication. In a second part, using computer evolutionary simulations, we will dismiss the usual claim that human communication is a specific form of reciprocal cooperation. A Darwinian account of language requires that we find a selective advantage in the communication act. We will propose, in the third part of this chapter, that such an advantage can be found if we consider language activity in the broader frame of human social organisation. In the continuation of the 'chimpanzee politics' studied by de Waal (1982), the ability to form large coalitions must have been an essential feature of hominid societies (Dunbar 1996). We will suggest that relevant speech originated in this context, as a way for individuals to select each other to form alliances.

How can we explain the origins of our uniquely human compositional system of communication? Much of the recent work tackling this problem (e.g Bickerton 1990; Pinker & Bloom 1990; Newmeyer 1991; Hurford et al. 1998) explicitly attempts to relate models of our innate linguistic endowment with neo-Darwinian evolutionary theory. These are essentially functional stories, arguing that the central features of human language are genetically encoded and have emerged over evolutionary time in response to natural selection pressures.

In this paper I put forward a new approach to understanding the origins of some of the key ingredients in a syntactic system. I show, using a computational model, that compositional syntax is an inevitable outcome of the dynamics of observationally learned communication systems. In a simulated population of individuals, language develops from a simple idiosyncratic vocabulary with little expressive power, to a compositional system with high expressivity, nouns and verbs, and word order expressing meaning distinctions. This happens without natural selection of learners --- indeed, without any biological change at all --- or any notion of function being built into the system.

This approach does not deny the possibility that much of our linguistic ability may be explained in terms of natural selection, but it does highlight the fact that biological evolution is by no means the only powerful adaptive system at work in the origins of human language.

The theme of language as play suggests inquiries into non-cognitive uses of language such as that found in riddles, jingles, or tongue twisters—and beyond this into the poetic and ritual function of language, as well as into parallels between language and ritual, language and ...

TABLE OF CONTENTS
1 First Words
2 Fast Mapping and the Course of Word Learning
3 Word Learning and Theory of Mind
4 Object Names and Other Common Nouns
5 Pronouns and Proper Names
6 Concepts and Categories
7 Naming Representations
8 Learning Words through Linguistic Context
9 Number Words
10 Words and Concepts
11 Final Words

TABLE OF CONTENTS

PART 1 ECONOMICS OF LANGUAGE
 0 Economics and language 3
 1 Choosing the semantic properties of language 9
 2 Evolution gives meaning to language 25
 3 Strategic considerations in pragmatics 37

PART 2 LANGUAGE OF ECONOMICS
 4 Decision making and language 55
 5 On the rhetoric of game theory 71

Concluding remarks 89

PART 3 COMMENTS
 0 Johan van Benthem 93
 0 Tilman Bors 108
 0 Barton Lipman 114

A new microevolutionary theory of complex design within language is pro- posed. Experiments were carried out that support the theory that complex functional design --- adaptive complexity --- accumulates due to the evolu- tionary algorithm at the simplest levels within human natural language. A large software system was developed which identifies and tracks evolution- ary dynamics within text discourse. With this system hundreds of examples of activity suggesting evolutionary significance were distilled from a text collection of many millions of words.

Research contributions include: (1) An active replicator model of micro- evolutionary dynamics within natural language, (2) methods to distill active replicators offering evidence of evolutionary processes in action and at multiple linguistic levels (lexical, lexical co-occurrence, lexico-syntac- tic, and syntactic), (3) a demonstration that language evolution and organic evolution are both examples of a single over-arching evolutionary algo- rithm, (4) a set of tools to comparatively study language over time, and (5) methods to materially improve text retrieval.

The research in this thesis addresses the question of how autonomous agents may develop concepts about their environment and develop a system of communication that allows them to exchange information about this environment based on those concepts. An autonomous agent is a system, in software or in hardware, that receives sensor input from the environment, selects actions, and may receive evaluative feedback reflecting the appropriateness of its actions. Communication is viewed as the transfer of information, in the sense that when a sender sends a message to a receiver, the amount of uncertainty in the receiver's knowledge about its environment decreases as a result of receiving the message. When agents have incomplete knowledge about their environment, communication can be valuable as a means to reduce this uncertainty by sharing information, and can be used to coordinate the actions of agents. Communication is learned during the life time of the agents, and the research concerns the question of how agents may cooperate to arrive at a shared system of communication.

Features of the information available to an agent through its sensors can be used to construct concepts, also called meanings. Constructing concepts based on the requirements posed by the environment is a more flexible approach than fixing the concepts of agents at design time, and may be necessary when the agents are to function in unknown or changing environments.

In this thesis, a particular type of concepts is described, called situation concepts. Situation concepts consist of features in the history of interaction between the agent and its environment, which consists of sensor data, actions, and subsequent evaluative feedback. A defining criterion of a situation concept is that it predicts some aspect of the future evolution of the state of the environment, possibly conditioned on the actions the agent may take. Several existing methods, particularly from the field of reinforcement learning, can be viewed as constructing a form of situation concepts. A particular method for constructing a specific type of situation concepts, called the adaptive subspace method, is described. The method uses the current sensor values of an agent as features and develops concepts that specify an interval for each sensor. These concepts predict the value of actions the agent can take when its current sensor values are within the specified intervals. The meanings thus formed represent situations, and are especially appropriate for use in communication, since they convey information about the environment.

The development of communication is viewed as the formation of associations between words and the meanings formed by the agents in a population, in such a way that agents tend to use the same word in the same situation. When agents autonomously construct concepts, a consequence is that they may not possess identical concepts. Additional constraints that are respected, such as the commitment that agents have no direct access to the meanings formed by other agents (they can not 'look inside each other's head'), and that no single agent may decide on the system of communication, further complicate the problem of how such a system of associations may come about.

Rather than viewing communication as fixed, it is viewed as a dynamical system. A dynamical system is a mathematical model of a system that changes over time. The variables of this system are the strengths of the associations between words and the meanings of the agents in a population. An algorithm is described in detail that, when used by each individual agent to adapt its associations between words and the situation concepts it has formed, leads to a shared system of communication.

The necessity of different components of the algorithm is shown with statistical significance. Associations are linear combinations of use (the frequency with which a word is observed in a situation) and success (the degree to which the word correctly indicates that its associated situation is the current situation in the environment). Analysis of the success component of the algorithm showed that not the success information itself, but the lateral inhibition between competing associations is crucial for the development of communication. It is experimentally demonstrated how the development of communication can compensate for differences in conceptual systems.

Systematic measures have been introduced to determine the quality of conceptual systems and communication systems. The measures require knowledge of the ideal concepts, called referents; although such knowledge is not available in general, simulation experiments often do provide the opportunity for such referents to be determined.

The specificity measure for communication is based on the principle that knowledge of a word should yield information (i.e. reduce uncertainty) about the referent (the current situation in the environment), and vice versa for the consistency measure. In cases of maximal specificity, the information a word yields is complete, and thus identifies the situation, whereas in the worst case, the word does not yield any information at all. The measure quantifies these and all intermediate cases. The consistency measure is computed as the extent to which a referent identifies a word, and thus expresses whether for each a referent the agent consistently uses the same word. If both specificity and consistency are high, each agent consistently uses a unique word for each referent. A population measure called coherence is used to determine whether different agents use the same words. In combination with the specificity and consistency measures, the experimenter can determine to what degree a perfect system of communication, consistently linking each referent to a unique word, is approximated.

Interestingly, the same principle can be used to evaluate the quality of a conceptual system. Ideally, each concept an agent has formed identifies a single referent in the environment; this is expressed by the distinctiveness measure, calculated as the degree to which the meanings an agent possesses distinguish between the different referents. Conversely, parsimony expresses the degree to which a referent identifies a meaning. It thus reflects whether the agent has not generated more meanings than necessary. Together, high distinctiveness and high parsimony imply that a conceptual system is ideal in the sense that it approximates a one-to-one relation between meanings and referents.

A contribution is made to the viewpoint of communication as a dynamical system by considering the attractors in the communication system that has been described. A deterministic version of the system is proved mathematically and demonstrated experimentally to have point attractors that correspond to perfect communication. An operational definition of pseudo-attractors is used to demonstrate that the stochastic system has points that play a similar role. Stochasticity is found to be a useful ingredient in the development of communication, in that it avoids deadlocks and results in communication more consistently and under a wider variety of parameter settings. This finding is confirmed by a systematic investigation of the effect of different amounts of stochasticity, regulated by the temperature parameter that governs word production. The analysis provides evidence that a dynamical systems perspective on the development of communication is valuable.

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