Language Evolution and Computation Bibliography

This paper investigates the evolution of communication among autonomous robots in the real world. A simple model has been constructed as a first step, in which a population of artificial organisms inhabits a lattice plane. Each organism communicates information with neighbors by uttering words. A common language typically evolves. We have analyzed evolutionary dynamics in this system, and have begun to implement it with a population of small mobile robots.

The cognitive revolution of the 1950's spawned development of the Turing Machine model of Mind (TMM) entailing both the formalism and practice of casting human cognition in the image of a digital computer. With the TMM, the mechanism of knowing (processing over internal knowledge states) could be integrated with the content of what is known (the mental products of histories of social living). This integration promoted the division of labor among psychologists and anthropologists which persists in many modern studies of mind and culture. This paper presents an alternative model of mind -- the Distributed Cognition model of Mind (DCM) -- based upon a reconstruction of the natures of, and relationships between, culture and cognition. The DCM is founded upon the notions that (1) cognition is built out of interactions among structures, (2) these interactions (instances of processes which employ and create structures) are not limited to events internal to individuals, but distribute across diverse media, social space, and time, and (3) culture is itself such a process, generating many of the structures and processes constituting cognition and human intelligence. The model is supported by data collected during ethnographic fieldwork among fishermen of an island community off the west coast of Sweden. Data analysis demonstrates the negotiated, distributed, and experientially grounded nature of language employed to communicate about sonar images of herring which mediate fishermen's understandings and practice.

This paper discusses the significance of communication between individual agents that are embedded into learning Multi-Agent Systems. For several learning tasks occurring within a Multi-Agent System, communication activities are investigated and the need for a mutual understanding of agents participating in the learning process is made explicit. Thus, the need for a common ontology to exchange learning-related information is shown. Building this ontology is an additional learning task that is not only extremely important, but also extremely difficult. We propose a solution that is motivated by the human ability to understand each other even in the absence of a common language by using alternative communication channels, such as gestures.

In this paper we present a new methodology for determining the evolutionary history of related languages. Our methodology uses linguistic information encoded as qualitative characters, and provides much greater precision than previous methods. Our analysis of Indo- European (IE) languages resolves questions that have troubled scholars for over a century.

Animal communication and human language have fundamental differences in their structures and functions. Furthermore, there is no living species demonstrating an intermediate stage of language evolution. Thus, we have difficulty in finding characteristics attributable to a communication system which can already be considered as a starting point for linguistic evolution. However, some findings coming from neurolinguistic research give us the opportunity to suppose that varying and arranging linguistic elements can be detached from other grammatical functions. Further information in this direction comes from apes' language-teaching experiments; namely bonobos (Panpaniscus) are able to understand and produce differences in meaning by varying word arrangements. Based on these results one can suppose that an acoustic signal system, which possesses discrete units for variable use, might be very ancient and might exist independent and prior to a more advanced language state. In the natural setting, acoustic territorial marking behaviour is exposed to selection pressure to elaborate sign systems built up from discrete, variable units. In addition to the well-known territorial bird songs, some monkey species and all species of lesser apes have territorial songs fitting these criteria. The analyses of the so-called long calls in chimpanzees and bonobos make it likely that the group-living great apes preserved the ability to create syntactically different calls, which would be developed by requirements of social life. A call repertoire emerged in these species, which contained a large number of call variants at group level available for each group member via social learning. This type of animal call is different from ordinary animal communication; its how some features of human language. It can represent an intermediate stage between animal communication and language, and communication system similar to this one can be considered as a starting point or first stage of language evolution.

Monogenesis of language is widely accepted, but the conventional argument seems to be mistaken; a simple probabilistic model shows that polygenesis is likely. Other prehistoric inventions are discussed, as are problems in tracing linguistic lineages. Language is a system of representations; within such a system, words can evoke complex and systematic responses. Along with its social functions, language is important to humans as a mental instrument. Indeed, the invention of language,that is the accumulation of symbols to represent emotions, objects, and acts may be the most important event in human evolution, because so many developments follow from it. For example, Edward Sapir speculated that some embryonic form of language must have been available to early man to help him fashion tools from stone (Sapir,1921). Sophisticated biface stone tools date to early Homo erectus some 1.5 million years ago, suggesting a similar age for language. This paper considers whether the invention of language occurred at only one pre-historic site or at several sites. In other words, did language emerge by monogenesis or polygenesis? Early thinkers believed in monogenesis, against a background of divine creation. Perhaps the best known account is the biblical story of Adam giving names to plants and animals in the Garden of Eden. Similar legends are found among many peoples. Modern linguists too assume monogenesis, but on probabilistic grounds (see, for instance, Southworth and Daswani, 1974, p.314). The argument seems to be that the invention of language is an extremely unlikely event, because symbolization involves abstraction and requires synchronized insight by several individuals; therefore, the probability of occurrence at more than one site must be vanishingly small. We have found no explicit quantitative treatment of this question in the literature, but the underlying logic has to be the multiplication of probabilities. If p is small at one site,then p.p for two sites is smaller still, and so on. This reasoning is false, as we show here. The fallacy lies in the focus on two particular sites rather than consideration of all pairs of sites.

Evolution of symbolic language and grammar is studied in a network model. Language is expressed by words, i.e. strings of symbols, which are generated by agents with their own symbolic grammar system. Agents communicate with each other by deriving and accepting words via rewriting rule set. They are ranked according to their communicative effectiveness: an agent which can derive less frequent and less acceptable words and accept words in less computational time will have higher scores. They can evolve by mutational processes, which change rewriting rules in their symbolic grammars. Complexity and diversity of words increase in the course of time. The emergence of modules and loop structure enhances the evolution. On the other hand, ensemble structure lead to a net-grammar, restricting individual grammars and their evolution.

A Saussurean communication system exists when an entire communicating population uses a single ``language'' that maps states unambiguously onto symbols and then back into the original states. This paper describes a number of simulations performed with a genetic algorithm to investigate the conditions necessary for such communication systems to evolve. The first simulation shows that Saussurean communication evolves in the simple case where direct selective pressure is placed on individuals to be both good transmitters and good receivers. The second simulation demonstrates that, in the more realistic case where selective pressure is only placed on doing well as a receiver, Saussurean communication fails to evolve. Two methods, inspired by research on the Prisoner's Dilemma, are used to attempt to solve this problem. The third simulation shows that, even in the absence of selective pressure on transmission, Saussurean communication can evolve if individuals interact multiple times with the same communication partner and are given the ability to respond differentially based on past interaction. In the fourth simulation, spatially organized populations are used, and it is shown that this allows Saussurean communication to evolve through kin selection.

Statistical analyses of a published phylogenetic classification of languages show some properties attributable to taxonomic methods and others that reflect the nature of linguistic evolution. The inferred phylogenetic tree is less well resolved and more asymmetric at the highest taxonomic ranks, where the tree is constructed mainly by phenetic methods. At lower ranks, where cladistic methods are more prevalent, the asymmetry of well resolved parts of the tree is consistent with a stochastic birth and death process in which languages originate and become extinct at constant rates, although poorly resolved parts of the tree are still more asymmetric than predicted. Other tests applied to a sample of historically recorded languages reveal substantial fluctuations in the rates of origination and extinction, with both rates temporarily reduced when languages enter the historical record. For languages in general, the average origination rate is estimated to be only slightly higher than the average extinction rate, which in turn corresponds to an average lifetime of about 500 years or less.

Analysis of a linguistic atlas reveals an ecological gradient in the diversity of languages in West Africa. As one moves south from arid into lusher ecoclimatic zones, the average size of ethnolinguistic groups decreases. Various factors are considered which may have contributed to this distribution. I argue that the ethnolinguistic map is primarily a reflection of the systems of generalized exchange and mutual dependence into which people enter. It is hypothesized that such social networks function to reduce subsistence risk due to variations in the food supply. If this hypothesis is correct, the average size of ethnolinguistic groups should be inversely proportional to the degree of ecological variability they face. This prediction is tested and found to hold strongly for a large part of West Africa. There is also limited evidence of a correlation between linguistic diversity and topography. It is concluded that ecological risk has been a key historical force in West Africa and that the ethnolinguistic mosaic can be used as a valuable 'fossil record' of people's adaptive social and economic strategies.

This paper shows how to formally characterize language learning in a finite parameter space, for instance, in the principles-and-parameters approach to language, as a Markov structure. New language learning results follow directly; we can explicitly calculate how many positive examples on average (``sample complexity'') it will take for a learner to correctly identify a target language with high probability. We show how sample complexity varies with input distributions and learning regimes. In particular we find that the average time to converge under reasonable language input distributions for a simple three-parameter system first described by Gibson and Wexler (1994) is psychologically plausible, in the range of 100-150 positive examples. We further find that a simple random step algorithm - that is, simply jumping from one language hypothesis to another rather than changing one parameter at a time - works faster and always converges to the right target language, in contrast to the single-step, local parameter setting method advocated in some recent work.

This paper presents a computational study of part of the lexical-acquisition task faced by children, namely the acquisition of word-to-meaning mappings. It first approximates this task as a formal mathematical problem. It then presents an implemented algorithm for solving this problem, illustrating its operation on a small example. This algorithm offers one precise interpretation of the intuitive notions of cross-situational learning and the principle of contrast applied between words in an utterance. It robustly learns a homonymous lexicon despite noisy multi-word input, in the presence of referential uncertainty, with no prior knowledge that is specific to the language being learned. Computational simulations demonstrate the robustness of this algorithm and illustrate how algorithms based on cross-situational learning and the principle of contrast might be able to solve lexical-acquisition problems of the size faced by children, under weak, worst-case assumptions about the type and quantity of data available.

A central topic for linguistic theory is the degree to which the communicative function of language influences its form. In particular many so-called functional explanations argue that cross-linguistic constraints can be explained with reference to pressures imposed by processing. In apparent opposition to this is the innatist stance which claims that universals are properties imposed by an autonomous language module. This thesis approaches the issues raised by this conflict by examining the nature of the link between processing and universals. The starting point for the work, then, is not the discovery of new universals nor new explanations, but the question ``exactly how do processing theories that have been proposed give rise to the universals that they claim to explain?'' Careful investigation of this problem proves to be fruitful in highlighting the roles of innateness and function in explaining universals.

The methodology chosen involves computational simulations of language as a complex adaptive system, in which language universals appear as emergent properties of the dynamics of the system and the influence of processing on use. This influence is characterised as a differential selection of competing variant forms. The simulation approach is first used to demonstrate the plausibility of a recent parsing explanation for word order universals. An extension of the model to deal with hierarchical universals relating to relative clauses leads to the conclusion that current explanations of hierarchies in general are incomplete. Instead, it is argued that implicational hierarchies are the result of competing processing pressures, in particular between morphological and parsing complexity.

Further examination of relative clause processing and universals leads to an apparent flaw in the approach put forward. It is noted that not all processing pressures appear to show up as universals, challenging the explanatory adequacy of the functional explanations. Instead, it is shown that a complete characterisation of language as an adaptive system requires there to be an innate, autonomous syntactic component to language. This leads to the conclusion that universals arise from the interaction of processing constraints and constraints imposed on the adaptive process by an innate language acquisition device. Moreover, the possibility of processing directly influencing this innate faculty without violating its autonomy is investigated with reference to recent work on the biological evolution of language.

This thesis therefore espouses a perspective on the explanation of language universals in which processing complexity and autonomous syntactic constraints have crucial and complementary roles.