Design and Performance of Pre-Grammatical Language Games - PDF

Please download to get full document.

View again

of 54
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Speeches

Published:

Views: 0 | Pages: 54

Extension: PDF | Download: 0

Share
Related documents
Description
Design and Performance of Pre-Grammatical Language Games JORIS VAN LOOVEREN Artificial Intelligence Laboratory Vrije Universiteit Brussel Proefschrift voorgelegd voor het behalen van de academische graad
Transcript
Design and Performance of Pre-Grammatical Language Games JORIS VAN LOOVEREN Artificial Intelligence Laboratory Vrije Universiteit Brussel Proefschrift voorgelegd voor het behalen van de academische graad van doctor in de wetenschappen. Acknowledgements DOCTORAL THESISES have, by definition, one single author on their cover. After all, only one person can earn their degree with the same work. Everybody knows however that the work carried out by the applicant never stands on its own. On the one hand, the scientific work is always framed within a larger body of work, in which there is a need or a desire for that specific work to be carried out, for example to solve a smaller problem within the framework, so the framework can be carried further, or because it seems to be a promising line of research to pursue. On the other hand, the researcher is not isolated from the world. He functions in the world; interacts with colleagues, family and friends, and is influenced by them. Some of these influences, such as the interactions with his colleagues, will have a large impact on the research, while interactions with family and friends have not so much a direct impact on the scientific work, but nevertheless are crucial to make the researcher feel good and allow him to do his scientific work as well as possible. Of course, I am no exception to this rule. In total, I spent about ten years at the VUB and in Brussels, four years as a student, and six years as a researcher at prof. Steels Artificial Intelligence lab. During that time, I have seen many people come and go, both at the university, and elsewhere in my pursuit of other activities. First of all, I want to thank my supervisor, prof. Luc Steels, for the opportunities he has given me. I have worked at both of his laboratories, the AI-lab at the VUB in Brussels and the Sony Computer Science Laboratory in Paris. I have been able to go to many places and meet many interesting people, through conferences and through the Talking Heads project. I have had the honor to work together with many people that, thanks to their different backgrounds, each have had different, interesting points of view on many issues: Tony Belpaeme, Joachim De Beule, Bart De Vylder, Bart Jansen, and Dominique Osier. Apart from these current colleagues, over the years we also had a steady supply of Dutchmen: Bart de Boer, Edwin de Jong, Paul Vogt, Jelle Zuidema, and Tom ten Thij, and an extended German presence in the form of Andreas Birk, Holger Kenn and Thomas Walle. At CSL, Frédéric Kaplan and Angus McIntyre have been essential to get our scientific projects going. At the personal level, there are a great many people who helped, by being who they are, get me to where I am now: my running mates from the Brussels i ii Athletics Club, my teachers and co-students at the photography course, etc., and not in the least, the old, but stable values in my circle of friends: Peter and Bénédicte and their wonderful kids, Bart and Sofie, and Zeger. And finally, without my parents, who supported my studying at the university, and my two sisters, all of this would simply not have been possible. Of course, not only relationships between people make for a good PhD thesis. It may be a sobering thought, but without monetary support which ensures that one can concentrate on the research, such an undertaking would be next to impossible. The work reported in this thesis has been financially supported by several institutions. I started doing research in Paris, at Luc Steels Sony Computer Science Laboratory. After my four-month stint at Sony CSL, I came back to the VUB to work first as a researcher, then as a teaching assistant. Finally, on January 1st, 2001, I became a full-time researcher again on a four-year scholarship of the IWT (Instituut voor Innovatie door Wetenschap en Technologie, Vlaanderen). Brussels, March 24th, 2005 Joris Van Looveren Abstract Past efforts in the study of language and its evolution have tended to focus on an individual s language capacity, and tried to understand in detail how this speaker/hearer s language capacity (LC) works. This was done e.g. by presenting people with sentences containing special cases and exceptions of specific rules, and judging their reaction to them. While this is a valid approach, it ignores many aspects of language that may be relevant to a global picture of how it works. Additionally, when the daunting complexity of the LC became apparent, it has been proposed that it must have evolved genetically, in analogy to the complexity of what evolution has accomplished in nature. This view has become widespread throughout the linguistic community. Recent research, especially on the evolution of the human LC, has taken more of a bottom-up approach, by attempting to identify core features of language, and thinking about the order in which these features must have become available for language. Initially, the linguist Bickerton proposed two stages, a simple protolanguage and modern language, with a genetic transition between the two. More recently his colleague Jackendoff proposed a much more detailed schema with many milestones that must have been reached at some point during the evolution of language. Techniques developed in other areas of science are also being applied more and more to language. Of specific interest here are game theory (from economy) and dynamic systems (physics), because they are specifically geared towards systems with many small components, and the interactions between them. Language can be viewed as a prime example of such a system, with many individuals that interact, and create a language in this way. Computer science offers a method that permits us to actually test theories based on this view of language in a very elegant way: multi-agent simulations. Individual language users are modeled as agents, which each have the ability to produce or interpret an utterance. The agents are then allowed to interact repeatedly according to a fixed protocol (a language game), describing objects and events that occur in their environment. During such a series of interactions, the agents develop utterances to express their meanings, and ultimately develop fully usable communication systems that cover the environment. This thesis describes three multi-agent models of three different linguistic communication systems, which correspond roughly to several of the milestones in Jackendoff s proposed schema. The agents have different cognitive capabilities iii iv in each model: in the first model, the agents are capable only of expressing simple meanings using utterances the contain only one word. The second model extends this with compositional meanings and the capability to use several words in one utterance to allow the agents to produce more complex utterances. The agents in the third model are able to express meanings that contain references to several objects and/or events (and the relations between them) through utterances that contain syntactic structure. Each model is evaluated against a number of criteria to see how it performs: basic communicative success, but also more qualitative measures such as lexicon size, lexical coherence, and degrees of homonymy and synonymy. It is shown that the same type of dynamics that work in the simplest model to create and maintain a stable and adaptive lexical inventory, scale up to more complex environments and agent LCs; in the second model to multi-word utterances, and also to syntactic rules in the third model. Even though the models become more complex at every step, their performance in terms of communicative success remains high. Communication becomes more efficient, in the sense that while the linguistic mechanisms become more complex, the agents are able to express more using smaller lexicons. The fact that all models perform well and that they become more efficient according to criteria relevant to communication and cognitive capacities lends support to the hypothesis that language evolved in small steps rather than in one leap, as proposed earlier in linguistics. In the three models, efficiency is measured using global measures. In a fourth model, we show that they can also serve as internal pressures in the agents that could guide the evolution process between stages. This model is a hybrid version of the two first models, in which the agents can choose between two strategies to use when they create an utterance. Both strategies are subject to pressure based on the agents cognitive limitations and performance in communication. Experiments with the hybrid model show how agent-internal pressure on the strategies can lead to global coherent behaviour, where all agents agree on the communication strategy to use. Several efficiency criteria are looked at. We have at this point found two selection criteria that work reliably; however they depend on strategy selection being done probabilistically instead of deterministically like the mechanism used for lexicon lookup does. So while it seems that the same mechanism that is used for the evaluation of words and other linguistic constructions, can also be used to evaluate whole communication strategies, we have not yet identified the ultimate selection pressure. This result shows how the transition from simple to more complex communication system can have taken place, without needing recourse to genetic evolution. Samenvatting 1 In het verleden waren taal- en taalevolutiestudies dikwijls gericht op de individuele taalcapaciteit van taalgebruikers, om te proberen om in detail te begrijpen hoe deze taalcapaciteit werkt. Dit werd onder meer gedaan door mensen allerlei uitzonderingsgevallen voor te leggen, en hun reactie hierop te bestuderen. Dit is een goede benadering, maar ze gaat voorbij aan allerlei aspecten die relevant kunnen zijn om een globaal beeld van taal en zijn werking te krijgen. Bovendien werd er, toen de ingewikkeldheid van de taalcapaciteit duidelijk werd, geponeerd dat die genetisch moest geëvolueerd zijn, naar analogie met de complexiteit van de flora en fauna die in de natuur ontstaan zijn door evolutie. Dit standpunt is vervolgens wijd verspreid geraakt in de linguistische gemeenschap. In recent onderzoek heeft men, specifiek met betrekking tot de evolutie van de menselijke taalcapaciteit, een andere benadering gekozen. Daarbij wordt geprobeerd om de belangrijkste kenmerken van taal te identificeren, en na te denken over de volgorde waarin deze kenmerken in de taalcapaciteit moeten verschenen zijn. In eerste instantie stelde de linguïst Bickerton twee stadia voor: een eenvoudige prototaal en moderne taal, met een genetische overgang tussen de twee. Recenter heeft zijn collega Jackendoff een veel gedetailleerder schema voorgesteld, waarin verschillende mijlpalen voorkomen die taal (en de taalcapaciteit) tijdens zijn evolutie heeft moeten bereiken. Technieken die ontwikkeld werden in andere domeinen van de wetenschap worden ook steeds meer toegepast op taal. Van specifiek belang in deze context zijn speltheorie (uit de economie) en dynamische systemen (uit de fysica), omdat deze speciaal gericht zijn op systemen met veel componenten en de interacties tussen deze componenten. Taal kan gezien worden als een mooi voorbeeld van zo n systeem, met veel individuen die interageren, en door deze interacties een taal creëren. Binnen de informatica bestaat een paradigma dat toelaat om theorieën gebaseerd op deze benadering van taal op een elegante manier te testen: multi-agent simulaties. Individuele taalgebruikers worden gemodelleerd als agents, die elk talige expressies kunnen produceren en interpreteren. Deze agents interageren dan herhaaldelijk volgens een vast protocol, waarbij ze objecten en gebeurte- 1 Zie ook (Vogt, de Boer en Van Looveren, 2000), (Steels, 2000) en (Belpaeme en Van Looveren, te verschijnen) voor uitgebreidere beschrijvingen van dit (en aanverwant) werk in het Nederlands. v vi nissen uit hun omgeving beschrijven. In de loop van zo n reeks interacties ontwikkelen ze expressies om de betekenissen uit te drukken die ze vinden, tot ze uiteindelijk een volwaardig, bruikbaar communicatiesysteem hebben dat hun wereld dekt. In deze thesis worden drie multi-agent modellen beschreven van drie verschillende linguistische communicatiesystemen, die ruwweg overeen komen met een aantal van de mijlpalen in Jackendoffs schema. In elk model hebben de agents specifieke cognitieve capaciteiten: in het eerste model kunnen ze enkel eenvoudige betekenissen uiten met expressies die uit één enkel woord bestaan. Het tweede model breidt dit uit met complexere, samengestelde betekenissen en de mogelijkheid om expressies bestaande uit meerdere woorden te gebruiken. De agents in het derde model kunnen betekenissen uitdrukken die referenties bevatten naar meerdere objecten en/of gebeurtenissen (en de relaties ertussen) in expressies die syntactisch gestructureerd zijn. Elk model wordt volgens een aantal criteria geëvalueerd om na te kunnen gaan hoe het presteert: eenvoudig communicatief succes, maar ook meer kwalitatieve maten zoals de grootte van het lexicon, de coherentie van het lexicon, en de mate van homonymie en synonymie. We tonen aan dat hetzelfde soort dynamiek dat in het eenvoudigste model werkt om het lexicon te organiseren, ook werkt op grotere schaal: in het tweede model voor samengestelde expressies, en in het derde model ook voor syntactische regels. Ondanks het feit dat de modellen complexer worden in elke stap, blijft hun performantie in termen van communicatief succes hoog. De communicatie wordt efficiënter, in de zin dat hoewel de linguïstische mechanismen complexer worden, de agents toch meer kunnen uitdrukken met kleinere lexicons. Het feit dat alle modellen goed blijven werken en efficiënter zijn met betrekking tot een aantal communicatief en cognitief relevante criteria steunt de hypothese dat taal in kleine stappen geëvolueerd is, eerder dan in één grote stap, zoals in de linguistiek voorgesteld geweest is. In de drie bovenstaande modellen wordt de efficiëntie gemeten aan de hand van globale maten. Dit wil zeggen dat de meetinstrumenten inzage hebben in de interne toestanden van alle agents. In een vierde model tonen we aan dat ze ook kunnen werken als interne selectiecriteria die het evolutieproces tussen de stadia kunnen sturen. Dit model is een hybride versie van de eerste twee modellen, waarin de agents kunnen kiezen uit twee strategieën om expressies te produceren. Beide strategieën zijn onderworpen aan de selectiedruk opgelegd door de cognitieve beperkingen van de agents en hun performantie in communicatie. De experimenten met het hybride model tonen hoe agent-interne druk op de strategieën kan leiden tot globaal coherent gedrag, waarbij alle agents dezelfde communicatiestrategie gebruiken. Verschillende efficiëntiecriteria worden onder de loupe genomen. We hebben op dit moment twee selectiecriteria gevonden die betrouwbaar lijken te werken. Ze steunen echter op het feit dat de communicatiestrategieën probabilistisch gekozen wordt, i.p.v. deterministisch zoals het opzoekmechanisme van het lexicon doet. Desalniettemin lijkt het er toch op dat hetzelfde mechanisme dat instaat voor de evaluatie van woorden en andere linguistische constructies ook gebruikt kan worden om hele communicatiestrategieën te evalueren. Dit resultaat toont hoe de transitie van eenvoudige naar complexere communicatiesystemen plaatsgevonden kan hebben, zonder genetische evolutie nodig te hebben voor de verklaring. vii viii Contents 1 Introduction The Problem Methodology Multi-Agent Systems Successive Stages Self-organisation Language Games Agents History Evaluation of the Models Communicative Success Lexical Coherence Lexicon Size Synonymy and Homonymy Outline of the Thesis Simple Naming Game Related Research Simplest Experiment Semantics First Experiment Discrimination Game Algorithm Discussion Form Variants Stochasticity Talking Heads Summary Simple Naming Game: Experiments Meanings Are Referents Naming Game Algorithm Details Communicative Success Coherence ix x CONTENTS 3.2 Discrimination Game Discrimination Algorithm Details Naming Game Algorithm Details Success Coherence Coherence Revisited Vocabulary Coherence Other Types of Coherence Ontology Coherence Talking Heads Communicative Success Coherence Summary Multi-Word Naming Game Related Research Semantics Discrimination Game Predicate calculus Form Explicit Subform Boundaries No Explicit Subform Boundaries Evolutionary Transition Game Result Lexicon Size Lexicon Expansion Summary Multi-Word Naming Game: Experiments Basic Experiments Discrimination Game Algorithm Details Predicate Semantics Algorithm Details Multi Word Naming Game Algorithm Details Communicative Success Coherence Lexicon Size Efficiency Competition between Words Synonyms and Homonyms No Explicit Subform Boundaries Evolutionary Transition Dual Strategy Algorithm Details Results Discussion Summary CONTENTS xi 6 Simple Syntactic Naming Game Related Research Decreasing Ambiguity: Illustration Meaning of an Utterance Composite Meanings Context Syntax Semantics Specialists Combining specialist data Processes Form Rules & Constructions Example Implementation Discussion Categories Syntactic Devices Summary Simple Syntactic Naming Game: Experiments Basic Experiments Predicate Semantics Algorithm Details Simple Syntactic Naming Game Algorithm Details Communicative Success Coherence Lexicon Size Grammar Use Word Competition Synonyms and Homonyms Summary Conclusion Models Results Individual Models Global Interpretation Future Research A Measures 145 A.1 Communicative Success A.2 Coherence A.2.1 Lexical Coherence A.2.2 Grammatical Coherence B Selection Pressure: Experiments 153 xii CONTENTS List of Figures 1.1 Succession of the models described in this thesis Different layers in agents and the population as language transfers from generation to generation Jackendoff s proposal for incremental steps in the evolution of language (Jackendoff, 2002) General structure of a cognitive module Semiotics in the basic experiment Example of two discrimination trees Pseudo-code for the discrimination algorithm Semiotic triangle in experiments with semantics Pipeline of the single-word utterance system Discrimination trees as developed by the agents in the Talking Heads experiment Talking Heads installation layout; schematically (i) and actual (ii) An example of the distortion faced by the Talking Heads software; the whiteboard is parallel to the camera plane Success and coherence in a 10-agent, 10-object experiment (5,000 games; averaged over 10 runs) Success and coherence in a 20-agent, 10-object experiment (15,000 games; averaged over 10 runs) Success and coherence in a 20-agent, 20-object experiment (30,000 games; averaged over 10 runs) Success and vocabulary coherence in a 10-resp. 20-agent experiment, with 7 objects in the context (50,000 resp. 100,000 games; averaged over 10 runs). The fact that the success curve is severely jagged in both graphs even after being averaged over 10 experiments, is due to the short intervals over which communicative success has been measured Competition between words for meaning WIDTH in a population of 2 agents Competition between words for meaning HEIGHT in a population of 5 agents xiii xiv LIST OF FIGURES 3.7 Competition between words for meaning GRAY-LEVEL in a population of 10 agents Competition between meanings for word bee in a population of 2 agents Competition between meanings for word gedale in a population of 2 agents Competition between meanings for word soopeeki in a population of 10 agents Percentual occurrence of meanings (most frequent meanings on the left) in a 10-agent, 7-segment experiment (50,000 games) Success and ontology coherence in a 10- resp. 20-agent, 7-segment experiment (50,000 resp. 100,000 games; averaged over 10 runs) Communicative Success in the Talking Heads experiment Rate of appearance of
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks