Language Evolution and Computation Bibliography

This paper proposes a language acquisition framework that includes both intra-generational transmission among children and inter-generational transmission between adults and children. A multi-agent computational model that adopts this framework is designed to evaluate the relative roles of these forms of cultural transmission in language evolution. It is shown that intra-generational transmission helps accelerate the convergence of linguistic knowledge and introduce changes in the communal language, while inter-generational transmission helps preserve an initial language to a certain extent. Due to conventionalisation during transmission, both forms of transmission collectively achieve a dynamic equilibrium of language evolution: On short time-scales, good understandability is maintained among individuals across generations; in the long run, language change is inevitable.

We examine the evolution of major grammatical forms and constructions as linguistic manifestations of human cognitive ability, based on historical data from English. We show that the complex linguistic system has arisen as more and more grammaticalized forms have accumulated. Word order and case go back to the earliest language. Tense, aspect, modality, gender, questions, negations, parataxis can be traced back to Proto-Indo-European, and they may go back further. Most crucial is the rise of embedding recursion and its product, the VO word order in Old English. This brought about the transition from the syntactic organization of the clause interwoven with discourse organization to the more strictly syntactic organization of the clause. With this transition, the periphrastic constructions of progressive, perfect and pluperfect, modal auxiliaries, periphrastic do and definite article arose due to speakers' desire to be more specific than was possible with the older forms. We also show the role of high-frequency words in the evolution of the grammatical forms.

Previous research on categorical perception of pitch contours has mainly considered the contrast between tone language and non-tone language listeners. This study investigates not only the influence of tone language vs. non-tone language experience (German vs. Chinese), but also the influence of different tone inventories (Mandarin tones vs. Cantonese tones), on the categorical perception of pitch contours. The results show that the positions of the identification boundaries do not differ significantly across the 3 groups of listeners, i.e., Mandarin, Cantonese, and German, but that the boundary widths do differ significantly between tone language (Mandarin and Cantonese) listeners and non-tone language (German) listeners, with broader boundary widths for non-tone language listeners. In the discrimination tasks, the German listeners exhibit only psychophysical boundaries, whereas Chinese listeners exhibit linguistic boundaries, and these linguistic boundaries are further shaped by the different tone inventories.

We conduct an evolutionary simulation to explore the coevolution of language and a language-related ability, intentionality sharing. Our simulation shows that during the evolution of a simple informative language, communicative success helps optimize the level of intentionality sharing in the population. This study illustrates a selective role of language communications on language-related abilities, and assists the discussion of the uniqueness of language-related abilities based on comparative studies.

The majority of the extant languages have one of three dominant basic word orders: SVO, SOV or VSO. Various hypotheses have been proposed to explain this word order bias, including the existence of a universal grammar, the learnability imposed by cognitive constraints, the descent of modern languages from an ancestral protolanguage, and the constraints from functional principles. We run simulations using a multi-agent computational model to study this bias. Following a local order approach, the model simulates individual language processing mechanisms in production and comprehension. The simulation results demonstrate that the semantic structures that a language encodes can constrain the global syntax, and that local syntax can help trigger bias towards the global order SOV/SVO (or VOS/OVS).

This paper presents a simulation study exploring the role of cultural transmission in intention sharing (the ability to establish shared intentions in communications). This ability has been argued to be human-unique, and a low level of it has deprived animals of the possibility of developing human language. Our simulation results show that the adequate level of this ability to trigger a communal language is not very high, and that cultural transmission can indirectly optimize the average level of this ability in the population. This work extends the current discussion on the human-uniqueness of some language-related abilities, and provides better understanding on the role of cultural transmission in language evolution.

This paper presents a simulation study to explore the role of naming game in social structure, which is nearly neglected by contemporary studies from statistical physics that mainly discuss the dynamics of naming game in predefined mean-field or complex networks. Our foci include the dynamics of naming game under some simpler, distance restrictions, and the origin and evolution of primitive social clusters as well as their languages under these restrictions. This study extends the current work on the role of social structure in language games, and provides better understanding on the self-organizing process of lexical conventionalization during cultural transmission.

The language game approach is widely adopted to study conventionalization of linguistic knowledge. Most of contemporary models concentrate on the dynamics of language games in random or predefined social structures, but neglect the role of communicative constraints. This paper adopts one form of language games, the category game, to discuss whether some simple distance-related communicative constraint may affect the conventionalization of linguistic categories. By comparing the simulation results with those based on another form of language games, the naming game, we point out some essential differences between these two games which cause their distinct performances under the same communicative constraint. This study fills the gap between the dynamics of language games in random structures and that in complex networks, and suggests that internal properties of language games may reversely influence communicative constraints and social structures.

The language game approach has recently been adopted to explore the conventionalization of linguistic knowledge in a social environment. Most contemporary studies focus on the dynamics of language games in random or predefined social networks, but neglect the reverse roles of communicative constraints in language evolution and social structures. This article, based on two forms of language games (the naming game and the category game), examines whether a simple, distance-based communicative constraint can affect the conventionalization of linguistic knowledge. The study bridges the gap between random networks and complex social structures, and illustrates that the internal properties of language games can influence the effects of communicative constraints and social structures.

A compositionality-regularity coevolution model is adopted to explore the effect of social structure on language emergence and maintenance. Based on this model, we explore language evolution in three experiments, and discuss the role of a popular agent in language evolution, the relationship between mutual understanding and social hierarchy, and the effect of inter-community communications and that of simple linguistic features on convergence of communal languages in two communities. This work embodies several important interactions during social learning, and introduces a new approach that manipulates individuals' probabilities to participate in social interactions to study the effect of social structure. We hope it will stimulate further theoretical and empirical explorations on language evolution in a social environment.

Social networks play an important role in determining the dynamics and outcome of language change. Early empirical studies only examine small-scale local social networks, and focus on the relationship between the individual speakers' linguistic behaviors and their characteristics in the network. In contrast, computer models can provide an efficient tool to consider large-scale networks with different structures and discuss the long-term effect of individuals' learning and interaction on language change. This paper presents an agent-based computer model which simulates language change as a process of innovation diffusion, to address the threshold problem of language change. In the model, the population is implemented as a network of agents with age differences and different learning abilities, and the population is changing, with new agents born periodically to replace old ones. Four typical types of networks and their effect on the diffusion dynamics are examined. When the functional bias is sufficiently high, innovations always diffuse to the whole population in a linear manner in regular and small-world networks, but diffuse quickly in a sharp S-curve in random and scale-free networks. The success rate of diffusion is higher in regular and small-world networks than in random and scale-free networks. In addition, the model shows that as long as the population contains a small number of statistical learners who can learn and use both linguistic variants statistically according to the impact of these variants in the input, there is a very high probability for linguistic innovations with only small functional advantage to overcome the threshold of diffusion.

The mathematical model for language competition developed by Abrams and Strogatz allows the evolution of the numbers of monolingual speakers of two competing languages to be estimated. In this paper, we extend the model to examine the role of bilingualism and social structure, neither of which are addressed in the previous model. We consider the impact of two strategies for language maintenance: (1) adjusting the status of the endangered language; and (2) adjusting the availability of monolingual and bilingual educational resources. The model allows us to predict for which scenarios of intervention language maintenance is more likely to be achieved. Qualitative analysis of the model indicates a set of intervention strategies by which the likelihood of successful maintenance is expected to increase.

We demonstrate that polysemous links have a profound impact on the organization of the semantic graph, conforming it as a small-world network, based on the data from WordNet and A Thesaurus of Old English. We then show that the words with higher frequency and therefore with higher number of meanings construct the higher level of the hypernymy tree and this architecture is robust through the times. We suggest that our quantitative analysis of structural connection patterns in semantic networks provides insights into the functioning of neural architectures in the human brain. Furthermore, we discuss that vast quantities of variable and random utterances are converted into a small-world of fixed forms with fixed meanings by the cooperation between humans in the emergence of lexicon.

We propose an asymmetric negotiation strategy to investigate the influence of high-degree agents on the agreement dynamics in a structured language game, the naming game. We introduce a model parameter, which governs the frequency of high-degree agents acting as speakers in communication. It is found that there exists an optimal value of the parameter that induces the fastest convergence to a global consensus on naming an object for both scale-free and small-world naming games. This phenomenon indicates that, although a strong influence of high-degree agents favors consensus achievement, very strong influences inhibit the convergence process, making it even slower than in the absence of influence of high-degree agents. Investigation of the total memory used by agents implies that there is some trade-off between the convergence speed and the required total memory. Other quantities, including the evolution of the number of different names and the relationship between agents' memories and their degrees, are also studied. The results are helpful for better understanding of the dynamics of the naming game with asymmetric negotiation strategy.

A multi-agent computational model is proposed to simulate language evolution in an acquisition framework. This framework involves many major forms of cultural transmission, and the simulation results of the model systematically examine the role of cultural transmission in language emergence and maintenance. In addition, this study discusses the effects of conventionalization during horizontal transmission on diffusing linguistic innovations, maintaining high levels of linguistic understandability, and triggering inevitable changes in the communal languages across generations. All these reflect that conventionalization could be a self-organizing property of the human communication system that drives language evolution.

We present a modified naming game by introducing weights of words in the evolution process. We assign the weight of a word spoken by an agent according to its connectivity, which is a natural reflection of the agent's influence in population. A tunable parameter is introduced, governing the word weight based on the connectivity of agents. We consider the scale-free topology and concentrate on the efficiency of reaching the final consensus, which is of high importance in the self-organized system. Interestingly, it is found that there exists an optimal parameter value, leading to the fastest convergence. This indicates appropriate hub's effects favor the achievement of consensus. The evolution of distinct words helps to give a qualitative explanation of this phenomena. Similar nontrivial phenomena are observed in the total memory of agents with a peak in the middle range of parameter values. Other relevant characters are provided as well, including the time evolution of total memory and success rate for different parameter values as well as the average degree of the network, which are helpful for understanding the dynamics of the modified naming game in detail.

We propose a Finite-Memory Naming Game (FMNG) model with respect to the bounded rationality of agents or finite resources for information storage in communication systems. We study its dynamics on several kinds of complex networks, including random networks, small-world networks and scale-free networks. We focus on the dynamics of the FMNG affected by the memory restriction as well as the topological properties of the networks. Interestingly, we found that the most important quantity, the convergence time of reaching the consensus, shows some non-monotonic behaviors by varying the average degrees of the networks with the existence of the fastest convergence at some specific average degrees. We also investigate other main quantities, such as the success rate in negotiation, the total number of words in the system and the correlations between agents of full memory and the total number of words, which clearly explain the nontrivial behaviors of the convergence. We provide some analytical results which help better understand the dynamics of the FMNG. We finally report a robust scaling property of the convergence time, which is regardless of the network structure and the memory restriction.

Compositionality and regularity are universals in human languages; in most languages, complex expressions are determined by their structures and their components' meanings. Based on a multi-agent computational model, the coevolution of compositionality and one type of regularity, word order, is traced during the emergence of compositional language out of holistic signals. The model modifies some questionable aspects in the Iterated Learning Model and Fluid Construction Grammar by considering the conventionalization in horizontal transmission and the gradual formation of syntactic categories which mirror the semantic categories. The model also implements a bottom-up syntactic developmental process, i.e., the global orders for regulating multiple arguments are gradually formed from simple local orders between two categories.

The emergence of a compositional language with a simple grammar and the effects of individuals popularity on the phylogeny of language are studied based on a multi-agent computational model. In this model, a bottom-up syntactic development is traced, in which the global syntax in sentences is gradually formed from local sequential information. Assuming that the popularity of individuals follows a power-law distribution, we demonstrate that a common language can emerge efficiently only for certain power-law distributions and that these distributions could also be formed as a result of the language phylogeny.

The majority of extant languages have one of three basic word orders: SVO, SOV or VSO. Various hypotheses have been put forward to explain aspects of this bias, including the existence of a universal grammar, learnability imposed by non-linguistic-specific cognitive constraints, and the descent of the extant languages from a common ancestral proto-language. Here, we adopt a multi-agent model for language emergence that simulates the coevolution of a lexicon and syntax from a holistic signaling system. The syntax evolves through a process of categorization; local syntactic rules are constructed that assign a relative order (e.g., S before V) to the elements of the two categories to which each rule applies. We demonstrate that local syntax encoding the relative position of S and O are the most stable, allowing the coexistence of the global word order pairs SOV/SVO and VOS/OVS. The structure of the semantic space that the language encodes further constrains the global syntax that is stable.

Whether simple syntax (in the form of simple word order) can emerge during the emergence of lexicon is studied from a simulation perspective; a multiagent computational model is adopted to trace a lexicon-syntax coevolution through iterative communications. Several factors that may affect this self-organizing process are discussed. An indirect meaning transference is simulated to study the effect of nonlinguistic information in listener's comprehension. Besides the theoretical and empirical argumentations, this computational model, following the Emergentism, demonstrates an adaptation of syntax from some domain-general abilities, which provides an argumentation against the Innatism.

In this paper, after a brief review of current computational models on language emergence, a multi-agent model is introduced to simulate the emergence of a compositional language from a holistic signaling system, through iterative interactions among heterogeneous agents. A coevolution of lexicon and syntax (in the form of simple word order) is tracked during communications with indirect meaning transference, in which the listener's comprehension is based on interactions of linguistic and nonlinguistic information, and the feedback is not a direct meaning check. In this model, homonymous and synonymous rules emerge inevitably, and a sufficiently developed communication system is available only when a homonym-avoidance mechanism is adopted. In addition, certain degrees of heterogeneity regarding agent's natural characteristics and linguistic behaviors do not significantly affect language emergence. Finally, based on theories of complex networks, a preliminary study of social structure's influence on language emergence is given, and a coevolution of the emergence of language and that of simple social structure is implemented.

Evolutionary computation is used to explore the emergence of language, focusing particularly on the intrinsic relationship between the lexicon and syntax, and the exogenous relationship between language use and cultural development. A multi-agent model traces a coevolution of the lexicon and syntax, and demonstrates that linguistic and some distance constraint on communications can trigger and maintain cultural heterogeneity. This model also traces an optimization process using evolutionary mechanisms based on local information. Certain mechanisms in this model, such as recurrent pattern extraction, strength-based competition and indirect feedback, can be generalized to study robot learning, optimization and other evolutionary phenomena.

1. Introduction Part 1 -- Language Emergence
2. Speech and language - a human trait defined by molecular genetics -- King Chow
3. Conceptual complexity and the brain: understanding language origins -- P. Thomas Schoenemann
4. The emergence of grammar from perspective -- Brian MacWhinney
5. Polygenesis of linguistic strategies: a scenario for the emergence of languages -- Christophe Coupe Jand ean-Marie Hombert

Part 2 -- Language Acquisition
6. Multiple-cue integration in language acquisition: a connectionist model of speech segmentation and rule-like behavior -- Morten Christiansen, Christopher M. Conway and Suzanne Curtin
7. Unsupervised lexical learning as inductive inference via compression -- Chunyu Kit
8. The origin of linguistic irregularity -- Charles Yang

Part 3 -- Language Change
9. The language organism: the Leiden theory of language evolution -- George van Driem
10. Taxonomy, typology, and historical linguistics -- Merritt Ruhlen
11. Modeling language evolution -- Felipe Cucker, Steve Smale and Ding-Xuan Zhou

Part 4 -- Language and Complexity
12. Language and complexity -- Murray Gell-Mann
13. Language acquisition as a complex adaptive system -- John H. Holland
14. How many meanings does a word have? Meaning estimation in Chinese and English -- Charles Lin and Kathleen Ahrens
15. Typology and complexity -- Randy LaPolla
16. Creoles and complexity -- Bernard Comrie

Research into the emergence and evolution of human language has received unprecedented attention during the past 15 years. Efforts to better understand the processes of language emergence and evolution have proceeded in two main directions: from the top-down (linguists) and from the bottom-up (cognitive scientists). Language can be viewed as an invading process that has had profound impact on the human phenotype at all levels, from the structure of the brain to modes of cultural interaction. In our view, the most effective way to form a connection between the two efforts (essential if theories for language evolution are to reflect the constraints imposed on language by the brain) lies in computational modelling, an approach that enables numerous hypotheses to be explored and tested against objective criteria and which suggest productive paths for empirical researchers to then follow. Here, with the aim of promoting the cross-fertilization of ideas across disciplines, we review some of the recent research that has made use of computational methods in three principal areas of research into language evolution: language emergence, language change, and language death.

It has been observed that borrowing within a group of genetically related languages often causes the lexical similarities among them to be skewed. Consequently, it has been proposed that borrowing can sometimes be inferred from such skewing. However, heterogeneity in the rate of lexical replacement, as well as borrowing from other languages, can also give rise to skewed lexical similarities. It is important, therefore, to determine to what degree skewing is a statistically significant indicator of borrowing. Here, we describe a statistical hypothesis test for detecting language contact based on skewing of linguistic characters of arbitrary type. Significant probabilities of correct detection of contact are maintained for various contact scenarios, with low false alarm probability. Our experiments show that the test is fairly robust to substantial heterogeneity in the retention rate, both across characters and across lineages, suggesting that the method can provide an objective criterion against which claims of significant skewing due to contact can be tested, pointing the way for more detailed analysis.

In this paper, a multi-agent computational model is proposed to simulate the coevolution of social structure and compositional protolanguage from a holistic signaling system through iterative interactions within a heterogeneous population. We implement an indirect meaning transference based on both linguistic and nonlinguistic information in communications, together with a feedback without direct meaning check. The emergent social structure, triggered by two locally selective strategies, friendship and popularity, has small-world characteristics. The influence of these selective strategies on the emergent language and the emergent social structure are discussed.

In this paper, the basic words introduced by Swadesh(1952,1955) are used to uncover information about language evolution. In section 2, based on Chen (1996), Swadesh's 200-word list can be split into two sub-groups; the first 100 words, called high rank, are more stable and loan-resistant than the second 100, called low rank. More retentions tend to be present among the high rank words while borrowed elements tend to occur more frequently among the low rank words. This feature can be used to distinguish retentions and borrowings when the evolution of a language has been blurred by language contact, such as the transmission of Middle Chinese entering tones into Pekinese. In section 3, we argue that Swadesh (1955)'s 100 basic words (high rank) are better for sub-grouping Chinese dialects, compared with Dolgopolsky (1964)'s 15-word list and Yakhontov' 35-word list.

The study of language evolution has revitalized recently due to converging interests from many disciplines. Computational modeling is one such fruitful area. Various aspects of language evolution have been studied using mathematical modeling and simulation. In this paper we discuss several computational studies in language change and language emergence.

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

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.

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.