Emergence of communication in natural and artificial systems


Human language stands as one of the most important leaps in evolution (Bickerton, 1990; Deacon, 1997; Maynard Smith and Szathmary, 1995). It is one of its most recent inventions: it might have emerged in human evolution as recently as 50.000 years ago. Our society emerges, to a large extent, from the cultural evolution allowed by our simbolic minds. Words constitute the substrate of our communication system and the combinatorial nature of language (with a virtually infinite universe of sentences) allows to describe and eventually manipulate our world. By means of a fully developed communication system, human societies have been able to store astronomic amounts of information beyond the limits imposed by purely biological constraints. As individuals sharing our knowledge and the cumulative experience of past generations, we are able to predict the future and adapt in ways that only cultural evolution can permit.

The faculty of language makes us different from any other species (Hauser et al., 2002). The differences between animal communication and human language are fundamental, both in their structure and function. Although evolutionary precursors exist, it is remarkable to see that there seems to be no intermediate stage between them (Ujhelyi, 1996).

One possible approach to these questions is to analyse the patterns of communication emerging from interacting, artificial systems. Such an approximation has been proven successful within biology, and is known as Artificial Life (shortly Alife). Alife systems can be structurally far from their organic counterparts, but they often display very similar solutions to common problems. For example, evolving populations of programs competing for computer memory resources and incorporating mistakes when replicating can develop parasitism, sex or cooperation (Ray, 1991; Adami 1998). Such type of behaviors are easily recognized as essential traits of living systems. The observation of common traits strongly suggests convergent evolution at its fundamental level. In other words, if virtual creatures eventually behave as real ones, it might be the case that the spectrum of possible solutions displayed by complex systems is actually very narrow. Simple forms of language are actually known to emerge within populations of interacting, artificial agents. Such individuals have a simple cognitive architecture but the colective is nevertheless able to develop communication (Cangelosi and Parisi, 1998; Kirby, 2001). These developments define a whole area within Alife known as evolutionary linguistics (see Steels, 2003 and references therein).

Artificial agents are not just a window into language origins and universals. The near future will host the emergence of new communication forms among humans and robots. Advances in artificial intelligence and technology have been made possible the development of embodied agents with the necessary degree of internal complexity to exhibit different types of emergent behavior. Robots can incorporate a high degree of behavioral plasticity, memory and interaction capabilities. Either under the presence of comunicating humans or other robots, they can actively respond to incoming information and develop new behavioral patterns. Communication among artificial creatures and humans is one of the fundamental issues of AI, but emergent communication among artificial beings is no less important. Our future society will experience considerable changes once robotic agents become incorporated to our daily life and start interacting with us. Perhaps new forms of language might finally emerge and start change our society in ways that we barely imagine right now. The project ECAGENTS will explore the basic laws underlying the emergence of communication in natural and artificial systems.

Our work at the Complex Systems Lab within this project will involve exploration of universal patterns in human language (using complex networks theory), development of models of emergence of language graphs (lexical matrices, word-word interaction graphs and protogrammars) as well as the relevance of these concepts within robot communication, computation and other forms of information transfer such as those relevant to nanosystems.

See our recent review: Scaling laws in language evolution, Ricard V. Solé. In: Power Laws in the Social Sciences, C. Cioffi (ed) Cambridge U. Press .

Network patterns in language


Words in human language interact within sentences in non-random ways, and allow humans to construct an astronomic variety of sentences from a limited number of discrete units. This construction process is extremely fast and robust. Words can be seen as defining a network of word-word coocurrence: words within sentences reflect language organization and appropriate link definitions allow to build a language graph which captures a considerable part of correct syntactic organization. See our paper: The Small World of Human Language, Proc. Roy. Soc. London B 268 (2001) 2261-2266, R. Ferrer Cancho and R. V. Sole and our recent work on syntax graphs, using dependency grammars as our basic theoretical framework.See our paper: Patterns in syntactic dependency networks, Physical Review E 69, 051915 (2004). These networks reveal the presence of small world organization: the average path to travel from a given word to another one (if the path is allowed) is extremely short, thus revealing a rather optimal flow in the word universe. Here each flow can be a sentence and the scale-free topology of these nets seems to favour a huge diversity of paths and thus an anormous flexibility in generating correct sentences. We are exploring the modular, hierarchical organization of some of these networks and the presence of nonlinear phenomena. We are also studying possible models able to capture the observed regularities and explain how they can emerge by simple evolutionary rules in artificial systems.

NETWORK LANGUAGE ANALYSIS: WIENER

Global organization of compositionality in complex communication systems


The complexity of signal communication within humans is truly remarkable. Human language is regarded as unique in the sense of being able to express an infinite number of meanings with a finite repertoire of words. Such a system, composed by a lexicon (or a set of words and their individual meanings) and a grammar (specifying the rules of combination of the words), truly has a non-trivial structure. Although many questions arise as to what is the origin of such a structure, we want to focus on the constraints that such a system imposes on their users just to be useful. To model compositionality, we are exploring models of the meaning-utterance map, with explicit treatment of how a given signal (or meaning) to be transmitted is encoded into a sequence of utterances, and also the reverse process of recovering the signal from these utterances.

Optimal information transfer in lexical networks


One possible theoretical approach to the emergence and evolution of communication in complex systems involves the use of word-object mappings. Such type of mapping defines a bipartite graph in which words and objects of reference are linked provided that a word (or utterance) is used to label a given object. We have recently found that some universal regularities displayed by human languages, such as Zipf's law might result from a phase transition phenomenon that takes place once a given threshold is reached (see: Least effort and the origins of scaling in human language, R. Ferrer Cancho and R. V. Sole, Procs. Natl. Acad. Sci. USA 100 (2003) 788-791.). See the comment in NATURE science update on this work, "Language evolved in a leap" , by Phillip Ball. Additionally, we have also explored the presence of universal patterns in syntax graphs, using dependency grammars as our basic theoretical framework.See our paper: Patterns in syntactic dependency networks, Physical Review E 69, 051915 (2004). Within ECAGENTS we are extending these ideas into collectives of embodied agents. Each agent carries a given lexical matrix and interacts with other agents in such a way that there is a collective evolution towards a common lexical matrix.

Language evolutionary tinkering with neural networks


By using populations of simple artificial agents, it has been shown that simple forms of language can emerge. In such models, individuals have a simple cognitive architecture but the colective is nevertheless able to develop communication (Cangelosi and Parisi, 1998; Kirby, 2001, Steels 2003). Using neural networks with predefined architecture, interacting agents can develop some kind of consensus communication. More recently, a number of theoretical developments within network theory and genetic programming indicate that evolving (instead of fixed) networks can display emergent behaviors not captured by their fixed counterparts. We are exploring the effects of noise in network evolution and also the relevance of the size of the agent set in achieving convergence. Collectives of artificial agents with their internal network representations might display new emergent properties relating communication strategies.

Collective exploration on complex landscapes by evolving agents


Finding specific features in a given spatial landscape is a difficult task. Autonomous rovers exploring remote planets have to be able to process local information by looking at given properties but the success of such search process relies on an appropriate spatial exploration together with an internal complexity able to store and process ongoing information. An alternative approach is to consider distributed systems of many simple, communicating agents able to gather local information and exchange it with some (or all) other agents. Theoretical models and some observations of swarm intelligence seem to indicate that there are tradeoffs between individual and global behavioral complexity. By using simple agents with low cognitive functions but having appropriate information exchange mechanisms, we might be able to most effectively explore a given landscape (either physical or abstract, such as those underlying optimization problems) in better conditions than those expected for what can be done by single, complex agents.

REFERENCES

Adami, C. 1998. Introduction to Artificial Life. New York:Springer.

Ash, Robert B. 1965. Information Theory. New York:Dover.

Bickerton, D. 1990. Language and Species. Chicago: Chicago U Press.

Cangelosi, Angelo. and Parisi, Domenico. 1998. Emergence of language in an evolving population of neural networks. Connection Science 10(2):83-97.

Deacon, T. W. 1997. The Symbolic Species: The Co-evolution of language and brain. New York: Norton and Co.

Ferrer Cancho, Ramon, and Solé, Ricard V. 2001. Two regimes in the frequency of words and th eorigins of complex lexicons: Zipf's law revisited. Journal of Quantitative Linguistics 8:165-174.

Ferrer Cancho, Ramon, and Solé, Ricard V. 2002. Zipf's law and random texts. Advances in Complex Systems 5(1):1-6.

Ferrer Cancho, Ramon, and Solé, Ricard V. 2003. Least effort and the origins of scaling in human language. Proceedings of the National Academy of Sciences USA 100: 788-791.

Ferrer Cancho, Ramon, 2004. Language: Universals, Principles and Origins. Ph D Dissertation. Universitat Politecnica de Catalunya.

Gomes, Marcelo A. F. et al. 1999. Scaling relations for diversity of languages. Physica A271: 489-495.

Hauser, Marc D., Chomsky, N., and Fitch, W. T. 2002. The faculty of language: what is it, who has it and how did it evolve? Science 298: 1569-1579.

Kirby, Simon. 2001. Spontaneous evolution of linguistic structure: an iterated learning model of the emergence of regularity and irregularity. IEEE Transactions on Evolutionary Computation 5(2): 102-110.

Li, Wentian. 1992, Random texts exhibit Zipf's-law-like word frequency distribution. IEEE Transactions on Information Theory, 38(6):1842-1845.

Maynard Smith, John and Szathmary, Eoors. 1995. The Major Transitions in Evolution. Oxford: Oxford U. Press.

Miller, George A., 1957, Some effects of intermittent silence, American Journal of Psychology, 70:311-314.

Miller, George A., 1991. The Science of Words. Scientific American Library, New York: Freeman.

Nowak, Martin A., Krakauer, D. 1999. The evolution of language. Proceedings of the National Academy of Sciences USA 96: 8028-8033.

Nowak, Martin A., Plotkin, Joshua B., Jansen V. 2000. The evolution of syntactic communication. Nature 404: 495-498

Ray, Thomas S. 1991. In : Langton, C., C. Taylor, J., Farmer, D. and Rasmussen, S. [eds], Artificial Life II, pp. 371-408. Addison-Wesley: Redwood City, CA.

Solé, Ricard V., Manrubia, Susanna C., Luque, Bartolo, Delgado, Jordi, and Bascompte, Jordi. 1996. Phase Transitions and Complex Systems. Complexity 4:13-19.

Solé, Ricard V., and Goodwin, Brian C. 2001. Signs of Life: how complexity pervades biology. New York: Basic Books.

Steels, Luc. 2003. Evolving grounded communication for robots. Trends in Cognitive Science 7(7): 308-312.

Ujhelyi, Maria. 1996. Is there any intermediate stage between animal communication and language? Journal of Theoretical Biology 180: 71-76.

Wray, Martin A., editor. 2002. The transition to language. Oxford: Oxford U. Press.