# The evolution of grounded spatial language

Michael Spranger

Computational Models of Language Evolution 5

### Computational Models of Language Evolution

Editors: Luc Steels, Remi van Trijp

In this series:

# The evolution of grounded spatial language

Michael Spranger

Michael Spranger. 2016. *The evolution of grounded spatial language* (Computational Models of Language Evolution 5). Berlin: Language Science Press.

This title can be downloaded at: http://langsci-press.org/catalog/book/53 © 2016, Michael Spranger Published under the Creative Commons Attribution 4.0 Licence (CC BY 4.0): http://creativecommons.org/licenses/by/4.0/ ISBN: 978-3-946234-14-2 (Digital) 978-3-946234-15-9 (Hardcover) 978-3-944675-46-6 (Softcover) 978-1-523743-49-0 (Softcover US) ISSN: 2364-7809 DOI:10.17169/langsci.b53.183

Cover and concept of design: Ulrike Harbort Fonts: Linux Libertine, Arimo, DejaVu Sans Mono Typesetting software: XƎLATEX

Language Science Press Habelschwerdter Allee 45 14195 Berlin, Germany langsci-press.org

Storage and cataloguing done by FU Berlin

Language Science Press has no responsibility for the persistence or accuracy of URLs for external or third-party Internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

### **Preface ix**

## **Preface**

This book contributes to our understanding of the origins of spatial language by carrying out language game experiments with artificial agents instantiated as humanoid robots. It tests the theory of language evolution by linguistic selection, which states that language emerges through a cultural process based on the recruitment of various cognitive capacities in the service of language. Agents generate possible paradigmatic choices in their language systems and explore different language strategies. Which ones survive and dominate depends on linguistic selection criteria, such as expressive adequacy with respect to the ecological challenges and conditions in the environment, minimization of cognitive effort, and communicative success.

To anchor this case study in empirical phenomena, the book reconstructs the syntax and semantics of German spatial language, in particular German locative phrases. Syntactic processing is organized using Fluid Construction Grammar (FCG), a computational formalism for representing linguistic knowledge. For the semantics the book focusses in particular on proximal, projective and absolute spatial categories as well as perspective, perspective reversal and frame of reference. The semantic investigations use the perspective of Embodied Cognitive Semantics. The spatial semantics is grounded in the sensory-motor experiences of the robot and made compositional by using the Incremental Recruitment Language (IRL) developed for this purpose. The complete reconstructed system allows humanoid robots to communicate successfully and efficiently using the German locative system and provides a performance base line. The reconstruction shows that the computational formalisms, i.e. FCG and IRL, are sufficient for tackling complex natural language phenomena. Moreover, the reconstruction efforts reveal the tight interaction of syntax and semantics in German locative phrases.

The second part of the book concentrates on the evolution of spatial language. First the focus is on the formation and acquisition of spatial language by proposing strategies in the form of invention, adoption, and alignment operators. The book shows the adequacy of these strategies in acquisition experiments in which some agents act as learners and others as tutors. It shows next in language for-

### Preface

mation experiments that these strategies are sufficient to allow a population to self-organize a spatial language system from scratch. The book continues by studying the origins and competition of language strategies. Different conceptual strategies are considered and studied systematically, particularly in relation to the properties of the environment, for example, whether a global landmark is available. Different linguistic strategies are studied as well, for instance, the problem of choosing a particular reference object on the scene can be solved by the invention of markers, which allows many different reference objects, or by converging to a standard single reference object, such as a global landmark.

The book demonstrates that the theory of language evolution by linguistic selection leads to operational experiments in which artificial agents self-organize semantically rich and syntactically complex language. Moreover, many issues in cognitive science, ranging from perception and conceptualization to language processing, had to be dealt with to instantiate this theory, so that this book contributes not only to the study of language evolution but to the investigation of the cognitive bases of spatial language as well.

This book would not have been possible without the hard work of the people at Sony Computer Science Laboratory Paris and the A.I. Lab at the Vrije Universiteit Brussels. Many of them have left traces in software and ideas that provide the background against which a book like this one becomes possible. Most notably I would like to thank the current and past members of the AI lab in Brussels and Sony CSL Paris who I have met and who have made contributions to the various software systems that underly the experiments described in this book: Katrien Beuls, Joris Bleys, Joachim De Beule, Wouter van den Broeck, Remi van Trijp and Pieter Wellens.

Martin Loetzsch and Simon Pauw had big impact on many issues discussed in this book. I am indebted to all of them for long discussions that have tremendously shaped my way of thinking and for their collaboration on different aspects of spatial language, conceptualization and embodiment.

Last but not least, I would like to thank Luc Steels who has had tremendous impact on the intellectual ideas put forth in this book, provided the necessary environment to conduct this research, and who continues to be an inspirational and visionary figure for future work.

## **1 Introduction**

Spatial language is a vast topic. This book focusses on locative phrases, which are phrases that single out objects in the physical environment with the communicative intention to draw attention to these objects. The following shows an example of a locative phrase from German.

(1) der the.nom Block block.nom rechts right.prep der the.gen Kiste box.gen von from.prep dir your.dat aus perspective

'The block to the right of the box from your perspective'

Phrases like this can be seen as highly complex tools that help dialog partners to establish spatial reference. The utterance conveys to the hearer a number of instructions such as (1) apply the spatial relation right, (2) use a particular landmark and (3) take the perspective of the interlocutor. These instructions, when applied properly, allow an interlocutor to identify the object in question. The syntactic structure, i.e. the words and the grammatical relations of the utterance, encode which concepts and categories should be used and how the instructions work together. For instance, the fact that the hearer's perspective on the scene should be taken is conveyed by the phrase *von … aus* ('from … your perspective').

Languages vary widely in how they solve the problem of spatial reference – including both how they conceptualize space and how they talk about it (Levinson & Wilkins 2006; Levinson 2003). Spatial position of objects can be expressed using a variety of syntactic means including case, adpositions, particles, and verbs. But, maybe more importantly, there is a breathtaking variety in how people conceptualize space, which spatial relations they know, what counts as a landmark, how perspective is used, etc. Just to give a few simple examples, Spanish has three basic proximal distinctions, while German has two. In Barcelona people make active use of the topology of the surrounding landscape, referring regularly to the seaside and mountainside when giving navigation instructions. In other languages 'uphill' and 'downhill' are used to refer to proximal objects (Levinson 2003).

### 1 Introduction

These examples show that spatial language is a highly developed tool for establishing reference in a spatial environment. How did spatial language become this way? There is an emerging view now that the most plausible answer to this question is that spatial language is a complex adaptive system (see Steels 2000a for the general idea of language as a complex adaptive system), that is constructed and changed by its users for the same purpose it is used for today, namely to describe spatial scenes, establish reference to objects in the environment, give instructions for navigation, etc. This process is, of course, not the same process of construction that a group of engineers use when they are building a bridge. In such classic engineering problems, a team of people with a more or less complete view of the problem designs a top-down solution. By contrast, nobody has a global view on the state of a language. Rather, language lives in the individuals of the language community. Every individual has its own views on the state of the language, i.e. what words and grammatical relations are available.

When we combine the evidence from the complexity of particular spatial languages, such as German locative phrases, and the variation that can be seen across languages, it seems reasonable to consider results from a science that routinely deals with complexity and variation – biology. Biological species are highly complex solutions to particular environmental and social challenges. The solutions found by each species exhibit a high degree of variation. This simple observation has forced biology to come up with precise models and predictions to explain the origins of species. It comes as no surprise, then, that theories of language, particularly language evolution and language change, have adopted concepts from biology related to variation, complexity and the emergence of order in biological systems.

This book defends the selectionist theory of language evolution, which exploits biological concepts to explain how language is shaped by the communicative needs and environmental conditions that a community or population faces. The theory hypothesizes that agents create variation within their language and select working solutions based on how successful they are in communication (communicative success), how complex they are in processing (cognitive effort) and other factors.

Studying language change from the perspective of communicative intentions requires a great deal of insight into how humans or artificial systems can realize their specific communicative intentions in social interactions in the physical world. Such holistic explanations necessitate a whole systems approach (Steels 2001), in which great care is taken to ensure that perception, conceptualization and linguistic processing systems are integrated to an extent that interaction be-

### 1.1 Locative spatial language

tween agents is possible. Only when all of this machinery is in place can one attempt to examine questions of language change.

In particular, a whole systems approach requires an operational theory of language. How are utterances processed? How is space conceptualized? How is linguistic knowledge represented? How does language interact with the perception of the physical reality? A whole systems approach requires concrete answers to each of these important questions. The resulting burden placed on operational models is of course far greater than for high-level explanations or logical reasoning about these processes. But concrete, mechanistic accounts allow much greater insights into the phenomena studied. In the best case, a successful model of language evolution in a whole systems approach validates many aspects of the theory of language and language change at the same time.

This book contributes to the understanding of spatial language in two ways. First, it provides a detailed operational reconstruction of German locative phrases using a whole systems approach. Second, it explores the evolution of spatial language within the same computational framework. The two parts together argue for (1) the validity of the approach to language, and (2) the validity and explanatory power of the selectionist theory of language evolution.

### **1.1 Locative spatial language**

If one wants to make an interesting claim about how language evolves, one needs a solid idea what language actually is, how linguistic knowledge is represented, and how to organize linguistic processing. These questions are best answered by reconstructing a complex natural language phenomenon such as German locative phrases. Such phrases are used for establishing reference to static objects and identifying them by denoting their spatial position (Miller & Johnson-Laird 1976). They can be distinguished from other parts of spatial language that are dealing with motion or navigation (Eschenbach 2004).

German locative phrases can be analyzed in terms of components or systems which together form a locative phrase. (1) consists of three parts: a spatial relation, which is combined with a landmark and a perspective.

**Spatial Relations** The defining quality of locative spatial phrases are that they contain locative spatial relations such as*rechts* ('right'), *vorne* ('front'), *nah* ('near'), *nördlich* ('north on' and so forth). These relations are called locative because they encode static spatial relationships and do not refer to change of position in time. In (1), *rechts* ('right') is the locative spatial rela-

### 1 Introduction

tion. In this book we study three classes of spatial relations. *Proximal* relations are based on distance estimations. Examples of proximal relations in German are *nah* ('near') and *fern* ('far'). The second class is called *projective* relations and includes direction-based spatial relations such as *links* ('left') and *vor* ('front'). The last class considered are *absolute* relations such as *nördlich* ('north') and *östlich* ('east'). These are also direction-based, but the direction is related to a geocentric reference system such as the magnetic poles of the earth.

### **1.2 A theory of language evolution**

Theories of language evolution have to explain the evolution of language by defining the role and contribution of four different factors on language: biology, cognition, social cognition, and culture (Steels 2009; 2011c).

### 1.2 A theory of language evolution

are the basic cognitive processing mechanisms underlying production and parsing of language, interpretation, conceptualization, but also categorization, perception etc.? Language depends on a number of capabilities that may or may not be prior to language, such as temporal clustering of events, spatial navigation, perception-action systems (Rizzolatti & Arbib 1998; Arbib 2002; Steels & Spranger 2012; 2008), memory and so on and so forth. For instance, some have linked the evolution of language to an increase in capacity for storing cognitive categories and their interrelations (Schoenemann 1999). Another strand of cognitive influences on language evolution are general cognitive operators such as analogy and learning operators, for instance sequential learning (Christiansen et al. 2001).

### 1 Introduction

Brighton 2003). The question from the perspective of cultural evolution is what are the mechanisms that bring about change in language and what are the principles with which agents conventionalize language up to the point that interlocutors have a chance of understanding each other.

I emphasize the cultural point of view in this book. That is, my primary concern is with change in language on the cultural level independent of changes in the human biology. Language change occurs on a smaller time scale than, for instance, the adaptation of a new biological organ, let alone a new species. There is absolutely no doubt that languages evolve fast. One just has to look through a text by Shakespeare or Goethe to see that a few hundred years can have impact on vocabulary and grammatical structure. It took Vulgar Latin a mere 1500 years to evolve into about a dozen different languages such as French, Italian, Portuguese or Catalan (e.g., see Pope 1952 for French). If we observe languages today, we can easily see that new words are invented all the time. In academic and technological contexts, for instance, new concepts arise all the time. Roughly 30 years ago vocabulary such as *email* or *website* did not even exist. What drives change in language, in what circumstances does it take place and what are necessary requirements for language change to occur? These are questions that cultural evolution theories of language have to address.

### **1.2.1 Language systems and language strategies**

Cultural theories of language evolution have to take a close look at individual trajectories of language change (Steels 2011c). For instance, how did the Russian aspectual system emerge or why does English have a system of determiners and Russian not? How do spatial language systems develop over time? In other words, cultural theories of language evolution must provide models for the emergence and evolution of concrete language systems (Steels 2011c). Language systems package a particular semantic system (e.g. a set of spatial categories) and a particular way of expressing these distinctions (e.g. a corresponding set of lexical items).   They can be compositionally combined with landmarks to build complex spatial phrases. Interestingly, the German locative systems effectively consist of different conceptualization strategies that have distinct but converging evolutionary trajectories. For instance, the absolute system is connected to the invention of the compass, whereas projective systems often

1.2 A theory of language evolution

at least in part can be traced back to body parts (Traugott & Heine 1991). Nevertheless, many locative spatial relations are used in the same syntactic context.

Spatial language systems such as the proximal or projective system are characterized by a degree of cohesion and systematicity that points to an underlying principle that organizes acquisition, emergence and coordination. We call the mechanisms organizing a particular language system the language strategy (Steels 2011c). Language strategies have a *linguistic* and a *conceptual* part. For example, on the conceptual side absolute spatial categories share that they are part of the same conceptualization strategy which uses absolute directions to the magnetic poles of the earth. Syntactically all spatial relations share that they are expressed in a similar way namely lexically and that they can be expressed as adjective, adverb and preposition.

### **1.2.2 Selectionist theory of language evolution**

In this book I follow the *selectionist* theory of language evolution (Steels 2011c), which applies the dominant theoretical construct in biology natural selection and uses it to explain language change on the level of language systems and language strategies. Additionally, the concepts of self-organization, recruitment and co-evolution of syntax and semantics are used as theoretical pillars.

### 1 Introduction

particular language system, is communicative success. A communicative interaction between two interlocutors is successful if the communicative intention of the speaker is reached. For instance, if the speaker wanted to draw attention to some object, the communication is successful if the hearer pays attention to that object. Communicative success drives selection on the levels of the language system, but also on the level of language strategies (see Figure 1.1).

Variation occurs in the systems for two reasons. First, agents are actively trying to solve problems in communication (Steels 2000a). Agents introduce new categories, new words and grammar when they detect problems that they cannot solve using the current language they know. Second, language is an inferential communication system (Sperber & Wilson 1986) which means that the information provided in an utterance is often incomplete and ambiguous. Interpreting phrases is an active process in which the hearer is fusing information from the context, from the dialogue and his knowledge about the language to arrive at the best possible interpretation. In this process of course hearers might interpret the utterance differently then intended. This is the second source of variation.

**Self-organization** Steels (2011c) assumes that selection is not enough to explain language change and proposes another driving force in the evolution of language: self-organization – a concept used to account for complex phenomena in physical and biological systems. In short, self-organization is a way to explain how global structure arises out of local interaction of subunits (Camazine et al. 2003). An example from biology for self-organization is swarm behavior in a school of fish. Each individual fish locally controls its behavior based on the estimation of the position and direction of its immediate neighbors. On the global level this leads to consistent swarm behavior. Self-organization is typically seen as a complementary mechanism to selection, although there is some discussion on how to reconcile the two mechanisms. Kauffman (1993), for instance, proposes the following idea. Local components and the interaction rules are determined by selection, whereas the global emergent behavior is explained using self-organization. Applied to the swarm behavior this means that the anatomy of fish as well as the perceptual feedback loop are a product of natural selection. The global emergent swarm behavior is the product of self-organization.

Similar to swarm behavior, agents in a population evolving a language have to achieve global coherence in the language they use. Each agent

### 1.2 A theory of language evolution

has its own private representations of the language that they speak and they can adjust their own representations based on local interactions with peers. How, from local interactions, agents can agree on a globally shared communication system is the problem of alignment. Psychologists have found that interlocutors align on all levels of linguistic processing even over the course of a few interactions, i.e., dialogue (Garrod & Doherty 1994; Pickering & Garrod 2004). Similar mechanisms applied over a long time span are required for driving populations to self-organize a sufficiently shared communication system (Steels & Kaplan 2002).

### **1.2.3 Evolutionary explanations**

In every science one has to define what counts as an explanation. This book is guided by what counts as an evolutionary explanation in biology, ethology and psychology (Tinbergen 1963; Dunbar 1998). In order to explain a complex trait from the evolutionary perspective one has to provide explanations on four different levels: function, mechanism, ontogeny and phylogeny.

**Function** An explanation for a particular behavior has to show what the behavior is good for, i.e. what is its purpose. For Darwinian biology, the function of

### 1 Introduction

a behavior has to be explained in terms of its impact on survival or, more precisely, on the production of offspring. For evolutionary linguistics this turns into the question of how a particular language system or a particular strategy helps an agent to be more successful in communication. For example, one can explain particular spatial language systems with respect to their ability to help agents solve communicative problems in spatial navigation and spatial reference.

### **1.3 Main hypothesis**

This book provides experimental evidence for the theory of linguistic evolution. The hypothesis is that *spatial language syntax and spatial semantics co-evolve through a cultural process based on selection, self-organization and recruitment*.

1.4 Contributions

This book explores the hypothesis for the different components of spatial language: spatial relations, landmarks and perspective. Computational experiments show the emergence of spatial relations, the negotiation of the use of landmarks and perspective. I also explore different strategies for expressing spatial conceptualizations: lexical and grammatical strategies.

### **1.4 Contributions**

This book provides detailed accounts of the function, mechanisms, ontogeny and phylogeny of spatial language.

This book follows a whole systems approach which allows us to define external criteria for the progress in each of the objectives. The defining moment for the underlying conception of language is communication. A communication system is successful if it allows robotic agents to achieve their communicative goals such as drawing the attention to an object in the environment.

### **1.4.1 Evolutionary stages**

One way of understanding evolutionary processes is to try to identify evolutionary stages. Over the years, different steps in the evolution of language have been identified involving varying degrees of specificity (Bickerton 1999; Jackendoff 1999; Steels 2005). All of these proposals, while differing in detail and the exact number of stages, agree that language evolution starts at some pre-grammatical stage and increases in complexity to the form of language, in particular, grammar that we see today. Obviously any evolutionary account of language has to show how the current state of complexity of language can be traced back to earlier simple stages.

### 1 Introduction

This book orients itself alongside Steels (2005), who proposes a number of stages of complexity which are relevant for this book: single-word utterances, multi-word utterances, and grammatical utterances (see Figure 1.2).

Figure 1.2: Co-evolution of syntactic and semantic complexity.

This syntactic underdetermination has consequences for the semantic interpretation. If the phrase is interpreted as an adjective noun phrase as in *linke Kiste* ('left box'), the spatial category acts as a modifier on the set of boxes. If the spatial relation is interpreted as an adverb, then box might be a landmark and the whole phrase denotes a region next to the landmark as in *links der Kiste* ('to the left of the box'). Grammar signals the difference in these two semantic interpretations and disambiguates the conceptualization strategies. Consequently, agents equipped with grammatical strategies can disambiguate even more strategies and consequently, they can be more expressive.

The goal of this book is to identify, implement and test the mechanisms that drive the evolution of language on *each* of these stages. The mechanisms we are interested in are not descriptions of the phenomena but mechanistic explanations which identify the computational and cognitive components that enable robotic agents to self-organize communication systems. The procedure to find and validate mechanistic explanations is to

Invention, adoption and alignment operators are the backbone of the evolutionary models of this book. For instantiating the theory of linguistic selection one has to identify agent-level mechanisms that orchestrate the global behavior of the population. The mechanisms can be classified into the following three classes.

### 1 Introduction

carried out by hearers in interactions when they observe new items that they are unable to process. Adoption is another source of novelty and variation. An agent that picks up a new word might have a different idea of what that word means than the speaker actually intended.

**Alignment operators** Invention is local to an interaction. When two agents communicate and one of them invents a new word, this word might be acquired by the interlocutor, but the knowledge about this word is still local. Alignment operators orchestrate the self-organization of the system and the global alignment of language.

### **1.4.2 Co-evolution of syntactic and semantic complexity**

In each stage, syntactic complexity co-evolves with semantic complexity (see Figure 1.2). Syntactic complexity rises because the number of words per utterance increases (from the single-word stage to the multi-word stage) and because syntactic categorizations such as word order, morphology, agreement become important (from multi-word to grammar).

The notion of semantic complexity is harder to define. Obviously German spatial language is complex. But why does this seem obvious? What are the properties that make it a complex semantic system? For this book, complex semantics is defined with respect to spatial language as: the language supports a large number of conceptualizations of a spatial scene. There are two factors influencing the complexity of the space of possible conceptualizations of a spatial scene.

1.5 Structure of the book

### **1.5 Structure of the book**

This book is structured into three main parts besides this introduction and the conclusion. Part I explains the interaction model and the technical systems needed for studying spatial language. Part II deals with objective number one and details the reconstruction efforts for the German locative system. In Part III, I detail how spatial language evolves based on the model of evolutionary stages.

### **1.5.1 Part I: Spatial language games and technical background**

### **<IP_ADDRESS> Spatial language games**

Spatial language occurs mainly in interactions of individuals in spatial scenes. To research spatial language in such a communication-based approach to language a number of things need to be in place. We need a model of interactions in spatial scenes. This is the topic of Chapter 2 which introduces spatial language games which are routinized interactions consisting of defined roles for interlocutors – speaker and hearer. The chapter explains the basic interaction scheme and the linguistic and non-linguistic behaviors that define a spatial language game.

### **<IP_ADDRESS> Embodied cognitive semantics with IRL**

In order to achieve the objectives of this book, we need computational formalisms that support the reconstruction and evolution investigations. One of such formalisms in part developed for this book is the Incremental Recruitment Language (IRL). IRL is (a) a formalism for representing semantics, (b) a set of planning algorithms for automatic conceptualization and interpretation, and (c) a set of tools that make semantics an open-ended adaptive system. Chapter 3 introduces the formalism and the technology behind it.

### **<IP_ADDRESS> Construction grammar with FCG**

Another important backbone of the investigations is Fluid Construction Grammar (FCG). FCG is a formalism for representing and processing linguistic knowledge. Chapter 4 details how mappings from semantics to syntax are implemented using FCG and gives an example of processing a simple phrase.

### **1.5.2 Part II: Reconstructing German locative phrases**

To ground the modeling efforts in sufficient knowledge of a real spatial language system, I decided to reconstruct a part of German spatial language – German

### 1 Introduction

locative phrases. The second part of this book reconstructs the syntax and semantics of German locative phrases. The part starts out with an in-depth look at German locative spatial language as a natural language phenomenon. Chapter 5 gives more examples of the syntactic variety and the connection to the space of conceptualization strategies supported in German locative phrases. This sets the scope for the reconstruction effort, but also identifies a number of processing issues that the reconstruction has to deal with in order to be successful.

### **<IP_ADDRESS> Spatial semantics**

The following chapter details the operationalization of spatial semantics. Chapter 6 the basic semantic building blocks of German locative phrases and discusses how they work together to make up the complex semantics of spatial scenes.

### **<IP_ADDRESS> Syntactic processing**

A close look at German locative phrases reveals a number of interesting phenomena. Most importantly it uncovers the tight relationship between spatial syntax and spatial semantics. Chapter 7 explains how FCG can be used to model the tight connection between the words and grammatical relations observed in German locative phrases and the world of spatial semantics. These mappings are interesting because they pose particular challenges to the organization of linguistic processing. The re-use of the same spatial categories in different strategies for conceptualizing reality and their syntactic expression requires sophisticated mechanisms for dealing with many-to-many mappings in language. Another important issue is how to deal with the case system of German. All of these aspects of linguistic processing are discussed in Chapter 7.

### **<IP_ADDRESS> Conceptualization of spatial scenes**

Spatial scenes do not come a priori labeled, categorized and construed. Agents have to autonomously conceptualize reality given the particular communicative goal they have. Chapter 8 deals with the problem of conceptualization which is the problem of how to construct semantic structure that is helpful in reaching communicative intentions. The chapter gives an overview of different factors influencing the conceptualization of spatial scenes and compares different implementations of spatial conceptualization.

1.5 Structure of the book

### **<IP_ADDRESS> Integrating syntactic and semantic processing**

The last chapter of this part reports on the integration of syntax, semantics and conceptualization. One of the issues that can be studied in an approach like mine issemantic ambiguity which refers to the fact that natural language is often ambiguous with respect to the precise interpretation of a phrase. But humans are very strong in communicating even though language only encodes hints at how to conceptualize reality. The key is that humans integrate the sparse information communicated in utterances with knowledge about the current context of the interaction. Chapter 9 explains how one can operationalize this process of disambiguation through the context using the conglomerate of systems for linguistic and semantic processing as well as perception.

### **1.5.3 Part III: Spatial language evolution**

Finally the book turns to evolution in the third part. The organization of this part orients itself along the stages of complexity introduced earlier. There are two parts on single-word utterance systems, followed by a chapter on multi-word utterance systems. The part closes with a chapter on the evolution of grammatical structure.

### **<IP_ADDRESS> Acquisition and formation of basic spatial category systems**

The first chapter in this part explains how the basic building blocks of spatial language – spatial relationships and corresponding words – become shared in populations of agents. This corresponds to complexity stage one – single words. The goal of the chapter is to define the language strategies necessary for forming single-word spatial language systems.

Single-word spatial language systems are built by a particular strategy of conceptualizing reality which includes a priori commitments to certain reference objects, frames of reference and perspectives on the scene. The chapter shows how a language strategy which is a combination of a particular strategy for conceptualizing reality plus the necessary invention operators for basic spatial categories build the language systems that allow agents to communicate successfully. Language strategies are tested in two scenarios – acqisition and formation. In acquisition a learner agent has to pick up the spatial language system spoken by a tutor. In formation all agents start from scratch and progressively develop categories and lexical items.

The most important influence on what kind of language system emerges is

### 1 Introduction

the language strategy. The chapter details different language strategies necessary for building proximal, projective and absolute systems which encompass dedicated invention, adoption and alignment operators as well as the different conceptualization strategies. The success of the learning operators and the conceptualization strategy is tested in experiments where populations are fitted with a particular strategy. The resulting languages spoken by individual agents are analyzed with respect to communicative success and how similar they are to each other.

Another important factor influencing the emerging language system are environmental conditions. The chapter studies the impact of environmental conditions systematically by manipulating environmental features such as global landmarks or the statistical distribution of objects.

Obviously, natural languages support many conceptualization strategies at the same time. German, for instance, simultaneously has a proximal, a projective and an absolute system. So one can ask what happens when agents are simultaneously operating different strategies. I hypothesize that agents need additional cognitive mechanisms for choosing between different strategies and that choosing a strategy can be realized using the discriminative power of each strategy in a particular context. When an agent has to invent a new category they use the strategy that is most discriminating using a new category. Experiments show that this principle allows agents to build multiple language systems at the same time. Lastly, the chapter also studies the impact of different environmental layouts on formation of language systems for interacting strategies.

### **<IP_ADDRESS> Origins and alignment of spatial conceptualization strategies**

Chapter 11 deals with the emergence and alignment of conceptualization strategies. When one compares different languages of the world it becomes clear that many languages differ in the kinds of conceptualization strategies they support. Some languages solely use an absolute system, others can use intrinsic and relative systems and so on and so forth. Consequently, the evolution of spatial language is intricately connected to the origins and evolution of spatial conceptualization strategies. The chapter shows that conceptualization strategies are organized in a process of recruitment, selection and self-organization.

To explain conceptualization strategies from the viewpoint of the theory of linguistic selection is to explain (a) how different conceptualization strategies are created and (b) how they are selected for in communication. Competition is an important aspect of selection. Obviously environmental conditions and communicative success are main influences on which strategies are selected for

### 1.5 Structure of the book

because they are more successful. The chapter proposes alignment operations that update and track the score of conceptualization strategies so that agents can locally align in their interactions. I show that these operators lead to global convergence of the population on using single conceptualization strategies. The chapter studies competition of different strategies for landmarks and frames of reference and shows that with the right alignment strategy agents can agree on using a particular conceptualization strategy while co-evolving a lexicon and ontology of spatial relations at the same time.

Besides selection the theory has to explain how conceptualization strategies are created. This is were the idea of recruitment comes into play. Conceptualization strategies are assemblies of cognitive operations. For instance, an absolute strategy consists of a particular way of applying spatial categories plus the computation of a global landmark. Recruitment is the process of drawing from the pool of cognitive operations and assembling and packaging them so that the complete structure for conceptualization can be scored and the score updated and tracked. In a second set of experiments creation and competition of strategies are studied together.

### **<IP_ADDRESS> Multi-word lexical systems for expressing landmarks**

Single-word utterance systems are limited in how much information can be conveyed in them.  Which landmark is used? Which perspective did the speaker have in mind? These are questions that cannot be decided by just looking at a single word, unless of course the word is known and always refers to the same landmark and the same conceptualization strategy. When we look at human language we see a lot of re-use of spatial relations. Absolute, projective and proximal relations in German can be used with different landmark objects. Chapter 12 examines what mechanisms are needed for agents to mark landmark objects using lexical items while at the same time co-evolving a lexicon and ontology of spatial relations. Once these mechanisms are in place success of such extended lexical systems can be studied and compared to systems which only support a single conceptualization strategy.

### **<IP_ADDRESS> Grammar as a tool for disambiguating spatial phrases**

The part on language evolution of this book is concluded by Chapter 13 that examines the role and evolution of grammatical language.

### 1 Introduction

Lexical systems which are all systems studied up to this point in the book, have considerable shortcomings. One can study the effect grammar has by removing grammatical knowledge from the German locative grammar implemented for this book. The results presented in Chapter 13 show that agents operating a German locative system without grammar have significantly lower communicative success. I show that environmental conditions and diverging perspective on the scene can increase the drop in communicative success. The lack of grammar increases semantic ambiguity of phrases which means that the number of possible interpretations of a phrase escalates. As a consequence, the number of wrongly interpreted topics enlarges as well.

Given such a clear communicative advantage for having grammar, one can study the necessary operators that enable agents to develop a grammar for disambiguating spatial phrases. This is the topic of the second part of Chapter 13 which reports on the precise implementation of these operators. I test the operators in multi-agent experiments which prove that the hypothesized invention, learning and alignment operators allow agents to become increasingly more successful in communication because they develop an effective grammatical communication system.

## **Part I**

## **Spatial language games and technical background**

## **2 Grounded spatial language games**

Language does not occur in a vacuum. Spoken language occurs in physical, situated interactions when two interlocutors meet with specific communicative intentions. This chapter explains the basic social interactions at the center of the approach to language. Physical robots meet in communicative encounters and try to reach communicative goals within real world settings. Taking such a radical approach to the study of language is grounded in a number of social and perceptual mechanisms. Here I look at the prerequisites for the computational models discussed later in this book.

Figure 2.1 shows such an encounter of two humanoid robots in which one of the robots, the speaker, has the goal of drawing the attention of the hearer to some object in the environment using language. Such interactions are called language games (Steels 2001). Language games are routinized interactions between two members of a population. The game combines a particular script for the interaction, the linguistic information transfer and extra-linguistic feedback about the success of the interaction. Here is an example of a language game called the spatial language game:

### 2 Grounded spatial language games

Figure 2.1: Example scene. Two robots autonomously perceive and act in an office environment that contains different types of objects. Both robots autonomously create world models reflecting the state of the environment (see bottom left and right schematics), that include objects with spatial and color properties, the carton boxes as well as the robots.

To study language in a real world setting requires to fully spell out all components involved in the interaction. Besides social mechanisms agents need operational systems for perceiving the world, as well as the construction and interpretation of utterances. Figure 2 shows a schematic view of the systems involved in production and parsing, conceptualization and interpretation. Both agents independently process sensorimotor data stemming from the onboard cameras and proprioceptive sensors in order to construct world models of the environment (Spranger 2008; Spranger, Loetzsch & Steels 2012). Based on the particular communicative goal and the current state of the world represented in the world model, the speaker conceptualizes a meaning which is then rendered into an utterance by the language system. The hearer parses the utterance to determine its meaning and interprets it with respect to his current model of the world in order

### 2.1 Perception

Figure 2.2: The semiotic cycle is a model of situated communicative interactions between two interacting agents.

to infer the speaker's communicative goal and, for instance, perform a desired action. The system used for conceptualization and interpretation are explained in detail in Chapter 3. The system for producing and parsing utterances is treated in Chapter 4. The following sections focus on the necessary prerequisites for language production, parsing and evolution in terms of social mechanisms and perceptual processing.

### **2.1 Perception**

The environment that robots interact in is equipped with four kinds of objects that were carefully chosen to pick out special features relevant for spatial language: blocks, boxes, wall markers and the robots themselves (see Figure 2.1).

### 2 Grounded spatial language games

Before a language game starts the robots perceive their environment. The robots are endowed with perceptual systems for recognizing and tracking the objects in their environment. These systems continuously build up world models of the environment consisting of sets of objects. The objects are characterized by continuous real-valued features such as color, position and orientation but also width, height and length. The perceptual system also provides a basic grouping of objects into classes such as robots, blocks and boxes and wall markers. The following is the world model built by the agent to the left in Figure 2.1. It includes the other robot (robot-2), the landmark (box-1) and the colored blocks (obj-265, obj-266 and obj-268):

```
((robot-1 :type robot :x 0.0 :y 0.0 :orientation 0.5)
 (robot-2 :type robot :x 1461.65 :y -351.24 :orientation 0.9)
 (box-1 :type box :x 513.0 :y 891.67 :orientation 0.36
        :width 320.0 :height 450.0 :length 310.0)
 (obj-265 :x 1454.74 :y 248.72 :z 0.0 :width 59.75
          :height 235.99
          :average-y 128.0 :stdev-y 26.49 :min-y 51.0
          :max-y 199.0 :average-u ...)
 (obj-266 :x 285.0 :y 549.02 :z 0.0 ...)
 (obj-268 ...)
 (box-wall :orientation 0.36))
```
Each robot constructs perceptual representations of the objects in its immediate surroundings from the raw sensations streaming from the robot's sensor. Each type of object in the environment is tracked by a dedicated perceptual system. In general, processing of the different object classes is a three step process. First, low-level vision routines process raw camera images to yield basic percepts – these are connected regions that differ from the background of the environment or are related to the patterns distributed on the boxes and wall markers. Second, these regions are tracked in subsequent camera images. In order to do so, the vision system needs to establish a correspondence between an internal model and the image regions that refer to the same physical object, a process known in robotics as anchoring (Coradeschi & Saffiotti 2003). I use state es-

### 2.2 Social mechanisms

timation techniques from robotics, e.g. Kalman filters (Kálmán 1960), for maintaining such persistent models. Third, the vision system fuses information from the proprioceptive sensors of the robot the visual information to encode a set of visual properties about each object. In this particular setup these properties are the position and orientation of objects, an estimated width and height and color information. In the experiments discussed in this book only position and orientation are relevant. Most importantly, the perceptual systems only track objects on the ground. The position and orientation of objects is encoded in a two dimensional *egocentric* coordinate system which has its origin between the two feet of the robot facing to the front of the robot. Spranger (2008) gives more detail on the perceptual systems.

The experiments reported on in later sections require that agents play many language games. In order to speed up the process of a game and in order to do repeatable, manipulatable experiments, data from spatial scenes such as the one in Figure 2.1 are recorded and stored. The output of the perception system of more than 800 spatial scenes with different spatial configurations has been collected and can be accessed by artificial software agents without the agents required to run on physical robots. A spatial language game can be enacted on such stored scenes as if robots were perceiving the scene at the very moment they are playing a particular language game.

Figure 2.3 shows different spatial scenes. Each spatial scene consists of a world model for each of the two robots recorded from the position of each robot. Scenes are grouped into data sets with similar characteristics with respect to perspective on the scene, the number of objects and the availability of boxes and wall markers. For instance, in some data sets the perspective of interlocutors is similar (see Figure 2.3 for examples from one data set), i.e., robots are looking at the scene from the same position and there are few objects. Figure 2.4 shows examples from different data sets.

### **2.2 Social mechanisms**

Language games require a number of social mechanisms to be in place. Joint attention, turn-taking behavior, pointing and other non-linguistic feedback are mechanisms at the heart of the social interaction. Crucial social mechanisms required for these interaction are considered prerequisites for studying the evolution of language. They constitute the background against which communication and evolution of communication take place.

In joint attentional scenes (Tomasello 1995), interlocutors are jointly attending

### 2 Grounded spatial language games

Figure 2.3: Example world models from a spatial data set called space-game-2. Left the world model of robot *a* is shown. To the right the world model of robot *b* is shown. All scenes share similar properties. In this data set robots share a similar perspective on the scene. The actual position of the robots varies across different scenes, but is always similar. Similarly, every scene has a box landmark and two yellow blocks in it. However, the actual position of the box and its orientation, as well as the position of the objects change in every scene.

Figure 2.4: Example scenes from different spatial data sets. Each row shows scenes from a particular data set (the world model of robot *a* is always shown). The first row shows a data set which features a global landmark (space-game-9). The middle row shows scenes of a data set without global landmark and without box (space-game-17). Lastly, a data set which features many objects is shown (space-game-18).

### 2 Grounded spatial language games

to some object for some reasonable amount of time. Establishing joint attention in robotic experiments means that two robots taking part in a language game must (1) share a physical environment, (2) attend to a set of objects in their surrounding, (3) track whether the respective other robot is able to attend to the same set of objects and (4) be able to manipulate attention by pointing to distal objects and perceiving these pointing gestures. Joint attention is monitored by an external computer program, that has access to the world models of both interacting robots. This system initiates the interaction between two agents as soon as both agents observe the same set of objects. Spatial scenes are manipulated by a human experimenter to find spatial setups in which joint attention is possible, the program monitors whether robots are seeing the same set of objects and informs the experimenter whether the robots jointly attend to the same set of objects.

Social interactions have to be structured, so that agents can interpret the signals they exchange. For instance, if the hearer points before he has received the utterance, the speaker will have a hard time understanding the gesture. However, if the hearer points after receiving the utterance, the speaker can assume that this is the response to his speech act. Language games are coordinated by behavioral scripts. Every agent in the population knows the language game script and individually reacts to changes in the environment and actions of the other robot. For example the speaker triggers the action of pointing to the intended topic when the hearer signals that he did not understand the utterance. The scripts are implemented in the form of finite-state machines: actions are performed depending on the current state in the game flow, the perception of the environment and the history of the interaction.

In order to be able to learn and form spatial language systems, robots need non-linguistic means of conveying information, such as pointing to an object or conveying notions of success, failure and agreement in communication. For demonstration purposes robots are equipped with pointing gestures but in the communicative interactions underlying the results presented in this book, robots use a different mechanism in order to avoid further difficulties stemming from uncertainties in pointing (see Steels & Kaplan 1998 for a discussion of the impact of such uncertainties on the performance in language games). When a robot wants to point to an object in the environment, he directly transmits the coordinates of the intended object to the interlocutor. Since robots model object positions in their own (egocentric) coordinate systems, additional steps have to be taken to interpret these coordinates. Most importantly the robot has to know the position and orientation of the robot that is pointing. With this information

robots transform the coordinates into their own coordinate system and interpret the pointing by choosing the closest object to the pointing coordinates in their world model. Similarly, robots directly exchange other non-linguistic feedback, for instance agreement and disagreement in communication by exchanging signals whose meaning is shared. Moreover, linguistic utterances are directly passed between interlocutors.

## **3 Embodied cognitive semantics with IRL**

Artificial agents trying to achieve communicative goals in situated interactions in the real-world need powerful computational systems for conceptualizing their environment. In order to provide embodied artificial systems with rich semantics reminiscent of human language complexity, agents need mechanisms for both conceptualizing complex compositional semantic structure, but also for actively reconstructing semantic structure in interpretation of ambiguous utterances. Furthermore, the system must be open-ended and allow agents to adjust their semantic inventories in order to reach their goals. This chapter presents the computational system called Incremental Recruitment Language (IRL) that allows agents to represent and process complex conceptualizations of spatial scenes. The work presented here is based on substantial previous work. Key ideas of the IRL system have been laid out by Steels (2000b), with progress reported by Steels & Bleys (2005), Van den Broeck (2008), and recently by Spranger, Loetzsch & Pauw (2010) and Spranger et al. (2012).

### **3.1 Procedural semantics**

In order for a hearer to interpret an utterance, he has to apply the meaning conveyed in the linguistic structure to his perception of the context. Consequently, a speaker who uses language to achieve a certain communicative goal wants the hearer to execute a program (Johnson-Laird 1977), i.e. a set of operations that allow the hearer to, for example, discriminate an object in the environment or perform an action. Thus we model semantics, i.e. what it is a speaker wants the hearer to execute, as a program linking operations and data. Let us start with an example. Suppose a speaker utters the phrase *der rote Block* ('the red block') with the intention of making the hearer point to an object. In this case, the phrase encodes a program, i.e., set of operations, that are supposed to lead the hearer to identify the object in question. Presumably the hearer of this utterance has to filter the context for blocks first, followed by the application of the color cate-

### 3 Embodied cognitive semantics with IRL

gory red, in order to arrive at the set of red blocks, which is used to compute the topic consisting of a single entity. A possible program, also called irl-network, is shown in Figure 3.1. This network explicitly represents the chain of the four operations get-context, apply-class, apply-color and apply-selector by linking their arguments through variables (starting with ?). The network also includes the color category red, the object class block and the selector unique which are introduced via so called bind statements, as in (bind color-category ?color red). We collectively refer to concepts, categories etc. as semantic entities.

### 3.2 Evaluation

category ?color red) encodes the access to the color category red which is a prototype represented using values for different color channels.

Figure 3.2: Progressive evaluation of the network in Figure 3.1 on the context shown in Figure 2.1. From left to right, each node represents a step in the evaluation process. From top to bottom, the evaluated operation, the node status, and the current list of bindings of each node are shown. A consistent solution with bindings for all variables is found in the last node, and the value obj-252 is indeed a unique red block (compare Figure 2.1).

### **3.2 Evaluation**

A program such as the one in Figure 3.1 is *evaluated* by a speaker to test the semantic structure with respect to the particular communicative goal, or by a hearer in order to interpret an utterance. Evaluation is a process which cycles over the network and progressively computes values for variables, a process called binding. When the network in Figure 3.1 is evaluated the following happens. First get-context gets the current world model from the perceptual processes that are monitoring the environment for events and objects and binds it to the variable ?ctx-2. This is followed by the evaluation of the apply-class operation which computes a similarity score for every object in the context with respect to the object class block. This yields the set of objects from the context with each object scored using the computed similarity. The set is bound to the variable ?set-12. Because this variable is linked to the operation apply-color, the set bound to the variable ?set-12 is further processed using the color category red. apply-color first computes a similarity score for every object in the input set to the color category red which is multiplied with the similarity score the object already has from the application of the class block. This yields a new set of objects with multiplied similarity scores. The set is bound to the variable ?set-31. Lastly, apply-selector checks the objects in ?set-31, finds the object with the highest similarity score

### 3 Embodied cognitive semantics with IRL

and binds it to the variable ?topic which is the referent<sup>1</sup> of the phrase *der rote Block* ('the red block'). Figure 3.2 gives an idea how variables get progressively bound when the IRL-network is evaluated.

This is only one example how such a network can be evaluated. As Steels (2000b) has argued, language requires that semantic structure does not encode control flow, but rather data flows in all directions and is computed wherever possible. For this, operations need to be able to function in different directions with varying input-output parameters. For instance, the operation apply-class, which has three arguments, applies a class such as block to an input set, when the class is explicitly represented in the network. But in case this class is not introduced via a bind statement in the network, the operation can also provide this information, effectively turning this argument into an output argument. This multidirectionality of operations proves important for dealing with missing items, for instance due to partial parsing of an utterance, but it is also needed when constructing semantic structure.

### **3.3 Conceptualization and interpretation**

There are two scenarios in which agents autonomously compose semantic structure like the one just described in Figure 3.1. First, speakers have a particular communicative goal and need to construct semantic structure, for instance, for singling out the particular topic they want to draw attention to. This process is called conceptualization. In the second scenario, hearers use information parsed from the observed utterance and their knowledge about the current context of the interaction to actively reconstruct meanings from the potentially partial structures parsed by the language system. We call this process interpretation. Both cases are equally important and they both conceive the process of building semantic structure as a heuristically guided search process, that explores the space of possible IRL-networks driven by the agent's particular communicative goal and the information available to him.

In conceptualization, in other words while "planning what to say" (Steels & Bleys 2005), a speaker searches for an IRL-network that, when executed by the hearer, will reach a particular given communicative goal in a particular context. IRL-networks are constructed by assembling basic building blocks, in particular, cognitive operations packaged into chunks into more and more complex semantic structures. Each assembled structure is immediately tested by evaluating it

<sup>1</sup> Note that the word "object" here refers to an agent's private representation of things he has perceived in the world and only indirectly refers to the physical object which is the referent.

### 3.3 Conceptualization and interpretation

Figure 3.3: The search tree for finding the semantic structure seen in Figure 3.1. From left to right, nodes represent progressively growing programs combined from several chunks, which are each tried out and in some cases lead to solutions (green nodes).

which assesses its compatibility with the current communicative goal and the perceived context. Figure 3.3 shows an example of such a search process that has produced the program in Figure 3.1 for discriminating the red block in Figure 2.1. The search process for "good" semantic structure is guided by many different heuristics, one being that the structure can be expressed using the language system available to an agent. Others are more focused on the particular character of the communicative goal. If the goal is to discriminate an object in the environment, then it is beneficial to use more discriminative categories, i.e. categories that enlarge the distance between the similarity of the topic and the similarity of all other objects in the context.

Search is also applied when an agent perceiving an utterance tries to interpret it. The semantic structure an agent parsed from an utterance is often incomplete and semantic entities, cognitive operations and links can be missing in the network. Interpretation is a flexible, active process by which agents use search to add missing items to the network. Networks are immediately evaluated to see if they find a referent for the parsed utterance. The search process is constrained by the partial meaning parsed from the utterance and the kinds of semantic structures that are appropriate in the current context. The same scoring mechanisms as for conceptualization ensures that only a structure that is discriminating for a particular object (implicitly assuming that the speaker constructs structure based on

### 3 Embodied cognitive semantics with IRL

these principles) will be considered and the best of all possible results is chosen as the interpretation of an utterance.

### **3.4 Chunking**

Search spaces quickly become intractable because the number of possibilities for composing semantic structures increases exponentially with the number of cognitive operations. A look at language is helpful here. Grammar can be analyzed as a sophisticated tool that highly structures human language in order to manage not only the search space of possible syntactic structure (Steels & Wellens 2006) but perhaps more importantly the vast space of possible conceptual structures. Parts of meaning that are covered by a particular part of language can be stored as a chunk and then used as an basic atomic unit in composition. Ready-made semantic structure dramatically reduces the search space. If a structure like the final structure in Figure 3.1 is constructed from scratch using simple operations, the search tree would have a search depth of three (essentially one step in depth per operation). However, every time an operation is added to a program, it can be linked to the current structure in multiple ways, which leads to an explosion of nodes on every layer of depth. Hence, the system soon has to deal with a wide search tree, where every node will be executed and tested against the context. Consequently, using chunking dramatically increases the performance of the system, even in simple examples.

Chunks have an important role in the study of language because they package strategies for conceptualizing reality. Chunks allow to research how cognitive operations form strategies for conceptualizing reality, how these strategies can be adapted by agents and how strategies become conventionalized. For studying conventionalization, chunks have scores. This allows to track the success of each strategy with respect to the communicative goals, e.g. discriminative power of a strategy, but also with respect to communicative success. Strategies for conceptualizing reality are tightly linked to language. For instance, one can image that the chunk in Figure 3.4 which is extracted from the network in Figure 3.1 could be the semantics expressed by a determined adjective noun phrase construction. One important claim is that the structure in language – in particular in grammar – is tightly connected to the conceptualization of reality underlying every utterance. So the exemplary facts that in English, noun phrases have determiners, or that in Russian, all verbs are marked for aspects, suggests that these languages require speakers to conceptualize reality in a certain way and mark these conceptualizations in language.

```
target var ?topic (sensory-entity)
open vars ?class (object-class), ?c (color-category), ?sel-1 (selector)
irl program ((apply-selector ?topic ?set-31 ?sel-1)
            (apply-color-category ?set-31 ?set-12 ?c)
            (apply-class ?set-12 ?ctx-2 ?class) (get-context ?ctx-2))
            (apply-selector ?topic ?set-31 ?sel-1)
               (apply-color-category ?set-31 ?set-12 ?color)
                                (apply-class ?set-12 ?ctx-2 ?class)
                                         (get-context ?ctx-2)
score 0.50
det-color-adj-np (0.50)
```
Figure 3.4: Chunk representing the meaning of a determined color-adjective noun phrase. Chunks consist of an IRL-network, plus additional information used for processing: a target variable and open variables. These variables are typed (see brackets for type information) and they are used in conceptualization and interpretation for combining chunks to larger structures. The target variable of a chunk can be linked to the open variable of another chunk. Which selector is used, which object class and which color category are, is mostly determined by evaluating the network which yields bindings for the variables. Since the corresponding variables are open variables the information can also be provided by other chunks or in interpretation by the actual lexical items observed in the utterance. Chunks also have a score which can reflect the degree to which they are conventional ways of conceptualizing reality.

### 3 Embodied cognitive semantics with IRL

### **3.5 Grounding**

Another important issue is grounding. There are now many proposals of how agents can ground lexicons and categorical systems in sensorimotor interaction with the environment (Billard & Dautenhahn 1998; Vogt 2002; Steels 2008) and IRL is designed to allow such insights to be applied straightforwardly. For instance, the implementation of the operation for apply-color is in part based on findings about how basic color categories can be grounded in the sensor data streams of digital cameras (Steels & Belpaeme 2005; Bleys et al. 2009). Similarly, other grounding mechanisms such as for events (Siskind 2001; Steels & Baillie 2003) are easily instantiated in IRL operations.

One of the main claims in this book is that agents co-evolve syntax and semantics. Chunks are one way in which agents can shape strategies for conceptualizing reality. Another is related to the semantic entities themselves and the fact that the number of prototypes and categories and their particular representation is not fixed. For instance, there is now abundant research in the formation of basic color categories (Steels & Belpaeme 2005; Belpaeme & Bleys 2007) and how agents can invent, adopt and shape their inventory of color categories based on the environment they are facing. These insights into adaptive categories, but also names and individuals can be incorporated into IRL, which provides mechanisms for the creation and adaptation of categories in semantic structure.

### **3.6 Discussion**

IRL is a powerful system that for the first time allows to study complex semantic phenomena that go beyond purely lexical studies. IRL is a general system for representing the procedural semantics of utterances. It establishes a link between perception and language by providing a mechanism for representing the meaning of utterances, finding and interpreting the meaning of utterances. Moreover, IRL is designed to allow language processing to be a flexible, adaptive process which can be extended by new cognitive operations, new chunks, and new categories at any moment. Moreover, IRL provides mechanisms for tracking the success of semantic material such as chunks and categories.

The oldest and in some sense most similar system to what I have presented here is Winograd's shrdlu (Haddock 1989; Winograd 1971), However, shrdlu misses the key aspects of grounding, active interpretation and conceptualization as a search process. Other work such as those by Bailey, Feldman & Narayanan (1997) and Siskind (2001) focus mostly on lexical meaning. Some approaches have

3.6 Discussion

taken more general approaches e.g. to event structure (Narayanan 1999) but stay mostly tied with that particular domain. One of the few approaches talking about objects and events in the same framework is Roy's (2005), which is comparable to ours, but so far has been a theoretical proposal only.

## **4 Construction Grammar with FCG**

Construction Grammar posits that linguistic knowledge is organized in the form of "constructions" (Goldberg 1995; Croft 2001) which are mappings of semantics and pragmatics to syntax, i.e. words and grammar, but also phonology, prosody or intonation. Typically, Construction grammarians take a functional view on language and analyze every piece of language as a tool for communication and in terms of the syntactic and semantic function it performs. The theoretical framework of Construction Grammar is important for this book, because it integrates semantics with syntax and opens up ways for understanding the acquisition and evolution of language as a tool for solving communicative problems in which all elements of processing from semantics to syntax can be used as a tool for solving these problems.

Every part of an utterance has meaning and a semantic function. The meaning of a lexical item is the reference to the category, prototype or concept that it refers to. Its function is how it is used both in the semantic structure underlying the phrase and in the syntactic structure of the phrase. The following two examples include the word *rot* ('red') but they use the word in completely different syntactic and semantic structures.

In (1) *rot* ('red') is used to modify the set of objects denoted by the word *Block* ('block') whereas in (2) the statement is about the color itself. We can precisely capture these differences in semantic function using cognitive operations and IRL (an structure for (1) can be found in Section 3). The semantic function is coupled to a particular expression in syntax. In (1) the color is expressed as an adjective which signals its use as a modifier. In (2) the color is expressed as a noun and signals that the subsequent verb phrase is a fact about the color itself. In production, the speaker can therefore choose to express the category as an

### 4 Construction Grammar with FCG

adjective if the category is linked to the corresponding cognitive operation (e.g. apply-color). In parsing, when he observes a color adjective this allows him to infer that he is supposed to modify a set of objects using that operation. Which set of objects the color adjective modifies is determined by the larger syntactic and semantic context. For instance, in (1) the adjective is part of an adjective noun phrase that indicates which set is modified by the color category namely the set of blocks. From the viewpoint of the adjective noun phrase the adjective has the semantic function of providing a modifier and in particular of modifying the set of objects denoted by the noun. Of course, other adjectives, such as spatial adjectives can have the same function within an adjective noun phrase. The modified set is then input to another operation namely the operation applyselector which is marked by the determiner. So what we can see already in these simple examples are mappings from semantics to syntax and back, where every aspect of syntax, i.e. words and grammatical relations have a specific effect on the semantic interpretation of the phrase. Vice versa, the speaker can use all the potential of syntax to communicate precise semantic distinctions that he wants to convey. The key item for analysis is the function of items both in syntax and semantics. These dependencies between syntax and semantics can be easily operationalized using FCG (De Beule & Steels 2005; Steels, De Beule & Neubauer 2005).

Throughout this book language processing is implemented in FCG, a computational implementation of Construction Grammar. FCG is (1) a formalism that provides a notation for specifying constructions, (2) a an engine that processes linguistic structure by applying constructions, in order, to produce utterances or parse meanings, and (3) a set of design principles for organizing the grammar and linking grammar to representations of semantics, in particular, to semantic structure formalized using IRL.

### **4.1 Linguistic processing**

Linguistic processing encompasses both production and parsing of utterances. In production, FCG starts from a conceptualized meaning and tries to translate as much as possible of the semantic structure conceptualized by IRL into syntactic structure, i.e. words and grammatical relations using constructions in the linguistic inventory. In parsing this process is reversed and the construction inventory is used to recover as much semantic structure from an utterance as possible. Processing is organized around the transient structure which acts as a blackboard representing the current state of processing. Constructions work

4.1 Linguistic processing

like rules – if a construction is applicable, i.e. if conditions for its application are met, the construction can change the transient structure. Over time the transient structure accumulates information provided by the different constructions that have applied until some end state is reached, for instance, no construction can apply anymore.

meaning top ((apply-selector -?topic -?set-31 -?sel-1) (bind selector -?sel-1 unique) (apply-color-category -?set-31 -?set-12 -?color) (bind color-category -?color red) (apply-class -?set-12 -?ctx-2 -?class) (bind object-class -?class block)) top sem syn

Figure 4.1: Initial transient structure which contains only the meaning to be expressed in the top-unit of the semantic pole (left). There is no hierarchy yet and the syntactic pole (right) is empty.

### **4.1.1 Transient structure**

The transient structure has two poles: a semantic and a syntactic pole. Information regarding meaning is accumulated on the semantic side, information about words and grammatical relations are gathered on the syntactic side. Information is organized into units identified by a unit-name. Units consist of attribute-value pairs. In order to represent constituent structure, units can form hierarchies in which some units are hierarchically linked to other units effectively building tree like structures. In the beginning of processing the transient structure is filled with information either from the conceptualization processes, e.g. in production, or from the utterance observed, e.g. in parsing. Subsequently, constructions change the transient structure by adding new units, introducing hierarchy, changing the value of attributes or by introducing new attributes. Figures 4.1 and 4.2 show the transition from an initial transient structure which only contains a single unit, called "top-unit" on each side to a final transient structure with hierarchical organization of units and many more features. The initial structure only contains a meaning on the semantic side. The final structure contains, among other things, strings and syntactic word order constraints which can be used to build an utterance, a process called rendering. Figures 4.1 and 4.2 show graphical representations of the list representation (s-expression) used in processing. The following restates the initial transient structure as s-expression.

Figure 4.2: Final transient structure after many constructions of a simplified German grammar have been applied. The structure consists of units which are hierarchically organized starting from the top-unit. The meaning to be expressed is distributed over various units on the semantic side. Units feature semantic and syntactic categorization (sem-cat and syn-cat) which was build up in processing to organize constituent structure and allow for high-level constructions to abstract from individual items. On the syntactic side units have form features consisting of strings providing words and, so called "meets constraints" which introduce word order.

### 4 Construction Grammar with FCG

4.1 Linguistic processing

```
((top
  (meaning ((apply-selector -?topic -?set-31 -?sel-1)
            (bind selector -?sel-1 unique)
            (apply-color-category -?set-31 -?set-12 -?color)
            (bind color-category -?color red)
            (apply-class -?set-12 -?ctx-2 -?class)
            (bind object-class -?class block)))))
<-->
((top))
```
The top shows the semantic pole. The bottom, after the <-->, shows the syntactic pole. Both poles have one unit (the top-unit). On the semantic side the top-unit has one attribute, the meaning attribute which has an IRL-network in list form as its value. The following shows the final structure in the same representational format.

```
(...
 (color-adjective-unit-44
  (meaning ((apply-color-category -?set-31 -?set-12 -?color)))
  (sem-subunits (red-unit-40))
  (sem-cat ((sem-fn (modifier))))
  (args ((ref -?set-31) (src -?set-12))))
 (red-unit-40
  (meaning ((bind color-category -?color red)))
  (sem-cat ((type (color-category))))
  (args ((ref -?color))))
  ...
 (top (sem-subunits (determined-noun-phrase-77))))
<-->
(...
 (color-adjective-unit-44
  (syn-subunits (red-unit-40))
  (syn-cat ((syn-fn (adjectival)))))
 (red-unit-40
  (form ((string ?str-284 "rote")))
  (syn-cat ((lex-cat (color-adjective)))))
  ...
 (top (syn-subunits (determined-noun-phrase-77))))
```
Only parts of the complete final structure are shown, in particular, three units on each pole are shown the red-unit-40, color-adjective-unit-44 and top. In contrast to the initial transient structure, meaning is distributed across different units. Notice that which unit is subunit of another is coded by a special attribute called syn-subunits on the syntactic pole and sem-subunits on the semantic pole. Compare this with Figure 4.5 which shows the hierarchy in the final structure. For example red-unit-40 is a subunit of color-adjective-unit-44.

### 4 Construction Grammar with FCG

Figure 4.3: This figure shows a schematic view on construction application (Figure adapted from Steels 2011b). Starting from the initial transient structure (left) all constructions in the set of constructions are tested whether they match with the structure. Two constructions match with the initial transient structure. If a construction matches it can merge new information. Construction 72 adds unit C. After the structure has been changed, the process continues and all constructions are checked whether they merge with the transient structure modified by construction 72. Because construction 72 has applied, the transient structure is in a state such that construction 2 can now apply. This was previously not the case. Construction 2 is depending on information provided by construction 72. Subsequently, construction 2 further changes the transient structure and so on and so forth. Often multiple constructions from the set of constructions can apply. For example, construction 3 could also change the initial transient structure. This poses a general problem in processing which is solved by using a search algorithm described later in this section.

4.1 Linguistic processing

### **4.1.2 Constructions**

Constructions are organized in the same way as transient structures. They consist of two poles and the data in each pole are organized in terms of units, attributes and values. FCG supports bi-directional constructions which means that the same construction is used in production and parsing. The difference between production and parsing is how the syntactic and semantic pole of a construction is used in each case. In production the semantic pole is used to check the applicability of the construction. In parsing the syntactic pole is used. Applicability of a construction is checked using a mechanism called matching. Matching is based on the well studied concept of unification which is a computational process for equating two terms in this case the semantic or syntactic pole of the construction with the corresponding pole of the transient structure. If matching succeeds, the construction can change both poles of the transient structure, a process called merge, because it fuses information. The precise inner workings of these two fundamental operations are described in Steels & De Beule (2006). The most important fact is that matching in FCG mainly relies on variables, which in FCG (and in IRL) start with ?. In computational terms constructions specify (1) under which conditions they apply and (2) if they apply how the structure should be changed.

Figure 4.4: Schematic representation of a construction. The two poles of the construction are shown. The top shows the tagged and matching parts of the construction. The bottom shows the hierarchy building part of the construction.

Figure 4.4 shows an example of a lexical construction that maps the color category red onto the string *rote* ('red') (Figure 4.5 shows what happens when this construction is applied to the initial transient structure). The following shows the low-level list representation of the construction schematically depicted in Figure 4.4

4 Construction Grammar with FCG

```
(3)
     ((?top-6143
       (tag ?meaning-2381
        (meaning (== (bind color-category ?red-57 red)))))
      ((j ?red-unit-158 ?top-6143)
       ?meaning-2381
       (sem-cat ((type (color-category))))
       (args ((ref ?red-57)))))
     <-->
     ((?top-6143
       (tag ?string-251 (form (== (string ?str-251 "rote")))))
      ((j ?red-unit-158 ?top-6143)
       ?string-251
       (syn-cat ((lex-cat (color-adjective))))))
```
The top displays the semantic pole followed by the syntactic pole after the <-->. In production the construction requires the meaning (bind color-category ?red red) to be present. If this is the case, the construction merges the information on the syntactic side, in particular the stem, into the transient structure. Additionally, this construction builds hierarchy. It introduces a new unit which is a subunit of the top-unit and which is used to collect information for this particular lexical item. Already this simple construction uses the four basic ways in which constructions interact with the transient structure:

4.1 Linguistic processing

(4)

((J ?new-unit ?parent (?child-1 .. ?child-n)) (new-attribute new-attribute-value))

In the example construction the J-operator is used on the semantic and on the syntactic side. It introduces new units on both sides and adds information to this unit (in Figure 4.4 the parts pertaining to the J-operator are shown below the dotted line). Notice that the name of the new units is equal.

**Movement** Constructions can *tag* attributes and their values in order to move them around. In this example construction, the tag-operator moves the bind statement pertaining to the color category from the top-unit to the newly created unit. The tag operator takes the following form:

(?unit (tag ?tag-variable (attribute attribute-value))

The operator binds whatever follows the variable ?tag-variable to the variable. If the variable is used in a J-unit, i.e. a unit with a J-operator, in another part of the construction, this denotes the place where (attribute attribute-value) will be moved. The example construction has tag operators on the semantic side for moving the bind statement to the new semantic unit. Similarly, on the syntactic side the operator is used to move the string *rote* to the new syntactic unit.

### **4.1.3 Search**

Constructions are organized in a pool of constructions. In principle, constructions compete for access to the transient structure in processing. More than one construction can typically apply to the transient structure and the question is how to organize the process if there are multiple constructions that want to change the transient structure. In the absence of a priori rules to prefer one construction over another, each construction that can apply to the transient structure, is tried in a different branch of a heuristically guided search process. In other words, instead of having competing constructions change the same transient structure, the structure is copied and each potentially applying construction is applied to a copy without necessarily influencing the other. Naturally, this leads to different branches in processing, in which each branch computes a particular parsing or production result. Search is represented using a search tree

### 4 Construction Grammar with FCG

Figure 4.5: Transient structure after the lexical construction applied. The construction has introduced two new units using the J-operator. One on the semantic side and one on the syntactic side. Both units have the same name red-unit-42. The construction introduced the string *rote* on the syntactic side and the bind statements used for triggering the construction has been moved moved using the tag-operator from the top-unit to the new semantic subunit. The construction also added new semantic and syntactic categories (sem-cat and syn-cat) that can be used by subsequent constructions.

in which each node contains a transient structure. The initial node contains the initial transient structure. Leaf nodes contain final structures. The search process itself can be manipulated. For instance, it is possible to remove and refrain from processing duplicate nodes which contain the same transient structure and the order of following a particular branch can be influenced by how successful one predicts the branch to be. Figure 4.6 shows an example search tree for production of the utterance *der rote Block*.

Figure 4.6: FCG search tree which produces *der rote Block* given the IRL-network shown in Figure 3.1.

initial unique-lex block-lex red-lex color-adjective-cat determiner-cat *noun-cat adjective-noun-phrase* **determined-noun-phrase**

### **4.1.4 Design layer**

In order to design grammars it has proven beneficial to abstract from the low level processing layer of FCG and add a representational layer that connects high level linguistic analysis with the processing engine of FCG. The idea is to allow re-occurring problems in grammar design to be solved using templates – without having to resort and copy the code needed for describing a construction in the basic list notation. Templates are a general mechanism for expressing design patterns, i.e. solutions that can be re-used to deal with the same problem

4.2 Open-ended language evolution with FCG

occurring in different situations. For instance, all grammars implement phrasal constructions. One of the main semantic functions of phrasal constructions is to introduce variable equalities for linking constituents. A template encapsulates the solution to the problem of linking constituents in a way that the solution can be re-used in other phrasal constructions of the same grammar, but ideally also for phrasal constructions in other grammars. Templates are defined similar to functions. They have a name and a set of arguments which are specific to the template.

```
(template-name construction-name
:argument-1 value-1
:argument-2 value-2
...
```
:argument-n value-n)

Let us consider an example. I redefine the lexical construction introduced earlier, using a template called def-lex-skeleton.

```
(6)
```
(5)

```
(def-lex-skeleton red-cxn
 :meaning (== (bind color-category ?cat red))
 :args ((ref ?cat))
 :string "rote")
```
If this template is executed it translates into the low-level list representation in (3).

### **4.2 Open-ended language evolution with FCG**

Besides the obvious requirement of computational formalism for linguistic processing for computational experiments, FCG has a number of features that make it an optimal choice for studies in language evolution. FCG is not fixed to a certain set of constructions, a particular grammar layout, a particular set of meanings, or even a particular set of semantic and syntactic categories. FCG solely provides dedicated mechanisms for processing language but makes no actual claims about how a particular phenomenon should be processed in language. This allows different solutions to be explored by grammar designers. But, most importantly, it allows artificial agents to invent different constructions for solving a particular problem in communication, track their success and adapt them until the agents have conventionalized a solution to their particular problem. Language is not a

### 4 Construction Grammar with FCG

fixed system, but rather a system negotiated by its users to reach communicative goals in a decentralized manner. The fact that there are different solutions to solving the same problem therefore requires formalisms that are designed to be open to change syntactic and semantic categorization, and evolve meaning structure and new constructions. FCG is such a formalism.

From a computational perspective, FCG provides an easily manipulatable data representation, which makes inventing new constructions, changing and adapting semantic and syntactic categories, and introducing hierarchy or movement of data relatively easy. As in Construction Grammar the *unified* nature of representation is important. There is absolutely no difference in terms of representation and processing between lexical, functional or phrasal constructions. Hence, FCG supports research into how constructions can change from lexical to grammatical constructions, which is of interest for the study of the influence of the grammaticalization processes on language evolution (Traugott & Heine 1991).

Another important argument for the use of FCG is its robust behavior in parsing and production. The search process for construction application and the bi-directional nature of constructions allow agents to produce as much of the meaning as they can when they are speaker. In parsing, the same process allows agents to recover as much of the semantics of a phrase as they possibly can. This is a prerequisite for any kind of grounded language learning let alone language evolution. Agents have to get as much information as possible from the different systems, such as perception and conceptualization, but also language processing. If agents would have to deal with a grammar engine that essentially gives up on processing as soon as an agent encounters a phrase that he thinks is unconventional, learning the new unconventional phrase can never occur or is significantly hindered. Whereas if the grammar engine provides as much information as possible, agents have a much better shot at guessing underlying meaning and making sense of what was conveyed to them. Subsequently, they can better represent the new parts of an utterance versus parts they already know. Modeling this whole process as a search process is an immense advantage of FCG. Agents can track what changes when they apply other constructions and explore different possible parse and produce results, in order to identify problems in language processing.

The last point with respect to the advantage of keeping information from the search process that governs linguistic processing is important, in particular for the main problem studied in this book: conventionalization. In order for agents to realize that constructions are competing for the same string, the same grammatical structure or the same meaning, it is vital to fully explore the search process.

### 4.3 Discussion

If there are multiple ways of producing an utterance for a meaning, for instance because there are multiple words to express the same category, then the search can recover all of them. Together with a mechanism for tracking success of constructions, the search can choose the best one of them. After the interaction the agent can then update the constructions used and those that he could have used, for instance, by rewarding successfully used constructions and punishing unsuccessful or unused constructions. Constructions are equipped with a score that allows agents to update their inventories by scoring constructions according to their success in communication. If scores get too low agents can remove the affected constructions.

### **4.3 Discussion**

There is no question that this is a short, in many ways too short, introduction to FCG. FCG has been under continuous development since 1998 and it has developed into a mature system which allows to research complex language phenomena such as Russian aspect (Gerasymova & Spranger 2010; 2012). The complexity of natural language has without doubt left its mark on the system and many design choices in the system are not immediately obvious, unless one takes the scope of the research program into account. Recently several book projects (Steels 2011b; 2012) attempted to communicate the full scope of FCG research performed in the last decade. The interested reader is referred to these efforts to get a broader introduction.

## **Part II**

## **Reconstructing German locative phrases**

## **5 German locative phrases – an introduction**

To appreciate the complexity of spatial language one just needs to consider a particular human language such as German. The following chapters detail an elaborate reconstruction effort which targets locative German phrases (parts of this reconstruction effort have been published in Spranger & Loetzsch 2011). I specifically focus on the processing of German locative phrases in a whole systems approach encompassing the perception, conceptualization, as well as production and parsing of spatial phrases. Before we jump to the implementation and the specific challenges in modeling such a complex phenomenon, this introduction overviews German spatial relations and highlights the syntax and semantics of German locative phrases, as well as the close interaction of syntax and semantics. The claim is that important aspects of the syntactic structure of an utterance, i.e. the lexical items and the grammatical relations between them, work together to convey semantic structure, i.e. meaning. Vice versa, the varied syntactic devices in German spatial language allow to express subtle differences in the conceptualization of spatial scenes. The German spatial language system serves as a beautiful example of how syntax connects to the extraordinarily rich world of spatial semantics.

The literature distinguishes several classes of spatial relations available in German. Among them are projective, proximal and absolute relations (see Figure 5).

### 5 German locative phrases – an introduction

Weiss 1996). For this book proximal relationships such as *nah* ('near') and *fern* ('far') are important.

**Absolute relations** refer to cardinal directions, for instance *nördlich* ('north'), *westlich* ('west'), *östlich* ('east') and *südlich* ('south').

Spatial relations take different syntactic forms in German. All of the projective terms, for instance, can be expressed in different lexical classes, most prominently as adjectives, adverbs and prepositions. For example, the projective term *vor* can appear as adjective as in (1), as adverb as in (2) and as preposition as in (3).

The different lexical classes carry with them different syntactic functions, e.g. adjectives can function as modifiers in determined adjective noun phrases, prepositions are followed by noun phrases and in German govern case. But each lexical class is also connected to a different semantic interpretation. In particular, there is a tight connection between the lexical class and specific spatial construal operations that govern how precisely the spatial relation is to be applied. The meaning of a projective category when used as an adjective is to filter objects (Tenbrink 2007), whereas when used as preposition the meaning is to construct a region (Klabunde 1999). For instance, the following phrase (4) uses the projective category front to construct a region to which one is asked to put a chair. Unlike in the adjective case, the region is not used to modify or filter, rather the region is necessarily empty in order for the chair to be put there.

Figure 5.1: Taxonomy of spatial relations discussed in this book. The rectangular items refer to the spatial terms used for denoting the relations. Since in German spatial relations can be expressed in different lexical classes and word forms, English equivalents are used as placeholder.

### 5 German locative phrases – an introduction

Another important difference between spatial adjectives and spatial adverbs and prepositions is the potential for reference objects or landmarks. Example (3) relates a located object, also called "figure" (Talmy 2000) and "trajector" (Vandeloise 1991) to a reference object, also called "landmark" (Vandeloise 1991), "relatum" (Tenbrink 2007) or "ground" (Talmy 2000). If a spatial term is used prepositionally as in (3), both the spatial relation, in this case *vor*, and the landmark *Kiste* ('box'), are expressed in the prepositional phrase itself.

A third possible lexical class, in which spatial relations partake, are adverbs. Spatial adverbs can be accompanied by a prepositional phrase, as in (5)–(6):

The prepositional phrases*in der Kiste* and *von der Kiste* both introduce a landmark which, via the spatial term, relates to the figure, in this case *der Block*. The two different prepositions *in* and *von* denote whether the relation referred to by the spatial term is internal to the landmark or external. In the case of *von*, the spatial region denoted by the projective adverb, e.g. *links* ('left'), is external to the landmark, whereas in the case of *in* the region lies within the landmark. The projective adverbs*links* ('left') and *rechts* ('right') can be followed both by *von* and *in* prepositional phrases, hence they can have an internal and external reading. The projective adverbs *vorne* ('front') and *hinten* ('back') can only be extended by *in* prepositional phrases. The vertical projective adverbs *oben* ('above') and *unten* ('below') elicit internal readings. Again differences in semantic processing are syntactically marked, in the case of adverbs by prepositional phrases that complement the adverb.

The last important component of spatial language considered in this book is perspective marking. The following two example feature perspective markers. In (7) an adverb is perspective marked, in (8) a prepositional phrase is perspective marked.

(7) der the.nom Block block.nom vorne front.adv von from.prep dir the.dat aus box.dat 'The block in front from your perspective'

(8) der the.nom Block block.nom links left.prep der the.gen Kiste box.gen von from.prep dir your.dat aus perspective 'The block to the left of the box from your perspective'

Perspective on a scene is important for particular interpretations of spatial phrases, because it influences how the spatial scene and in particular the landmark is conceptualized.

These few examples from German locative phrases show that we can analyze the syntax of spatial language fruitfully in terms of its spatial semantics. This resonates with theories of syntax which put the direct mapping of syntax to semantics at the core of language processing, such as Construction Grammar. The tight relationship between syntax and semantics is an important claim in this book which underlies the reconstruction efforts, and also the evolution experiments.

The first question I am focusing on is how to organize language processing. That is, how semantics is encoded in words and grammar – and vice versa. However, this is not the full story. One needs to ground language in perception. Speakers need to be able to plan what they are going to say based on their communicative intention. Hearers must have machinery for interpreting the utterance based on the spatial context. This widens the question from how to organize the syntax and semantics interface to how to organize processing in a large array of systems comprising perception, conceptualization, interpretation and also processing of syntax. In particular, one has to identify the cognitive operations underlying the semantics of German locative phrases and how these operations are used in conceptualization of spatial scenes, as well as how conceptualization interacts with the perception of spatial scenes. The following section examine three main questions. First, what is the meaning of phrases such as *der Block links von der Box von dir aus* ('the block left of the box from your perspective', see (8)) and how can we formalize the semantic structure of these utterances? What are the cognitive primitives that are necessary for modeling the semantics of spatial phrases in particular? Second, how does semantic structure get translated into words and grammatical relations and back? And thirdly how can agents autonomously conceptualize spatial scenes given communicative goals and how can agents interpret semantic structure recovered in parsing so that success in communication can be achieved?

## **6 Spatial semantics**

So what is then the meaning of a phrase such as *der Block links von der Kiste von dir aus* ('the block left of the box from your perspective')? Figure 6.1 shows an IRL-network that agents autonomously construct to conceptualize a particular spatial scene. The structure consists of a set of cognitive operations that involve, for example, the construction of regions, the identification of landmarks, the application of perspective transformations and so on. But of course the network also contains references to spatial categories, selectors, and other semantic entities that are processed by cognitive operations. The following sections identify and describe the cognitive operations and the semantic entities underlying locative utterances.

### **6.1 Representing spatial relations**

The semantics of spatial relations is the subject of ongoing debate. The key question is whether there is something like a semantic core of spatial relations, i.e. a core meaning that abstracts from discourse situations as far as possible (Tenbrink 2007), and what that semantic core should be. For many scholars, the semantic core of spatial relations is related to geometric properties (Herskovits 1986; Eschenbach 1999; Tenbrink 2007) in particular prototypical axis (directions) and distances defined using tools like lines, points, vectors, half-planes, etc. (Levinson 1996). Particularly, projective relations, e.g. *vor* ('front') have been studied in this respect and certainly the class of absolute relations, e.g. *nördlich* ('north'), can be conceived in these terms. For instance, Herskovits (1986) describes the meaning of the spatial relation *in front of* as graded concept with the frontal axis as the focal region. This conception links to another important property of spatial language namely its inherent vagueness (Hall & Jones 2008). Many of these proposals are rooted in a strand of psycholinguistic research that is concerned with prototypes and prototypicality effects (Roach 1978). Here, prototypes or prototypical points in the sensorimotor space are used as representations for spatial categories (for a similar approach to color, see Bleys 2010). For instance, the projective term *links* ('left') can be interpreted for objects which relate to the ref-

### 6 Spatial semantics

Figure 6.1: An IRL-network representing the meaning of the phrase *der Block links von der Kiste von dir aus* ('the block left of the box from your perspective')

erence object by an angle of 90*◦* (prototypical left angle). The more the angle between the target object and the reference system deviates, the less acceptable the spatial relation becomes (Tenbrink 2005a; Herskovits 1986; Gapp 1995).

In this section I focus on the geometric properties of spatial relations and combine them with the prototype approach to spatial categorization. There are two features of the sensorimotor space which are of particular importance for spatial categorization: distance and angle. Two objects always have a certain distance from each other, and if there is a coordinate system available which supports rotation also angles between objects can be measured. Consequently, from a computational point of view, there are two important category types for representing the geometric properties of the German spatial relations discussed in this book angular-category, which represent prototypical angles and proximal-category, which represent prototypical distances (see Figure 6.2 for an overview).

### 6.1 Representing spatial relations

Figure 6.2: Category type hierarchy used in semantic processing

### **6.1.1 Angular relations**

The core semantics of spatial relations is represented using functions that map a particular input location to the applicability degree of a particular category. For prototype based spatial categories degree of applicability amounts to similarity in some spatial dimension, e.g. in the angular dimension for angular relations. Projective and absolute relations are examples of angular categories, with a focal region around the denoted axis. For instance, frontal categories have a high degree of applicability along the frontal axis. Whereas lateral categories have a high degree of applicability along the left and right axis. Similarly, absolute categories have high values of applicability in their respective direction (see Figure 6.1.2 for an overview). In other words, for angular categories, similarity of some location to the category depends on the distance of angles. In order to get a similarity function sim*<sup>a</sup> ∈* [0*,*1] the angle distance is wrapped in an exponential decay envelope and weighted by a *σ* which steers the steepness of the exponential decay. High values for *σ* correspond to a slow decay in similarity the bigger the angular distance, whereas low values for *σ* correspond to a sharper decline in similarity. Consequently, the following equations defines the degree of applicability given a location *l* and an angular category *c*, as the angular distance between *c* and *l*, weighted by *σ* and run through an exponential decay.

$$\text{sim}\_a(l, \mathfrak{c}) \quad := \quad e^{-\frac{1}{2\sigma\_\xi}d\_\mathfrak{a}(l, \mathfrak{c})} \tag{6.1}$$

$$d\_a(l, \mathbf{c}) \quad := \quad |a\_l - a\_\mathbf{c}| \tag{6.2}$$

### 6 Spatial semantics

In this definition *a<sup>l</sup>* denotes the angle of the position of location *l* to the coordinate center and *a<sup>c</sup>* denotes the prototypical angle of the category *c*. Given this definition, one can go ahead and define angular categories, in particular I need to define the prototypical angle for each angular category and the *σ*. Examples of definitions of angular spatial relations are depicted in Figure 6.1.2.

### **6.1.2 Proximal relations**

Proximal relations relate to some prototypical distance. Two relations are modeled: near and far. The only difference to the definition of angular categories is that proximal relations rely on the distance channel.

$$\text{sim}\_d(l, \mathbf{c}) \quad := \quad \mathbf{e}^{-\frac{1}{2\sigma\_\mathbf{c}}d\_d(l, \mathbf{c})} \tag{6.3}$$

$$d\_d(l, \mathfrak{c}) \quad := \quad |d\_l - d\_\mathfrak{c}| \tag{6.4}$$

In this definition *d<sup>l</sup>* denotes the distance of the location *l* to the coordinate center and *d<sup>c</sup>* denotes the prototypical distance of the category *c*.

Figure 6.3: Degrees of acceptability shown for prototypical representation of frontal and lateral projective categories. From left to right front, back, left, right, near and far are shown. The opacity of each color denotes acceptability for a particular location in space (*x*-axes and *y*axes each run from *−*2000*.*0 to 2000*.*0). Front, for instance, shows a strong acceptability along the *x*-axes. Definitions of categories are *a*front = 0*.*0, *a*back = *π*, *a*left = *π* 2 and *a*left = *− π* 2 and *σ*front = *σ* back = *σ*left = *σ*right = 1*.*0. For absolute categories the same definitions exist with north being defined like front and so forth. The two proximal categories near and far are defined with *d*near = 0*.*0, *a*far = 2000*.*0 and *σ*near=700*.*<sup>0</sup> and *σ*far = 1200*.*0.

6.2 Applying spatial relations

### **6.2 Applying spatial relations**

Prepositionally and adverbially expressed spatial relations denote spatial regions which are always related to some reference object. For instance, in the phrase *der block links der Kiste* ('the block to the left of the box') an object *der Block* ('the block') is related to the landmark *die Kiste* ('the box') via the spatial category *links* ('left'). The information about which category is used and which landmark is referred to is packaged in a spatial region. In order to represent the difference between the construction of a region as for instance denoted by the prepositional phrase *vor der Kiste* ('in front of the box') and the application of that region to filter objects, as in the phrase *der Block vor der Kiste* ('the block in front of the region'), in other words in order to represent spatial relations, spatial processing is split into two distinct semantic operations. One operation constructs the region and packages the particular landmark and the particular spatial category, the other applies the region as a spatial relation to the objects available in the context.

### **6.2.1 Spatial regions and spatial relations**

Proximal regions are computed based on the distance prototype of the corresponding category and the landmark. The semantic operation construct-regionproximal therefore constructs a specific region based on a spatial category and a landmark. The right image in Figure 6.4 shows an example of a proximal region.

*Semantic operation* construct-region-proximal

The other operation needed for applying a region is called apply-spatial-region. This operation computes the similarity of every object in the context, given a region constructed, for instance by the operation construct-proximal-region. For the case of a proximal region, this involves (1) transforming the context so that the landmark is at the center of origin of the coordinate system and (2) applying the similarity function defined in Equation 6.3. This operation in many ways acts as a classifier such as the semantic operations for color and object-class described in Chapter 3. For each object in the source set the similarity of this object to the spatial region is computed, based on the constituents of the region, e.g. which

### 6 Spatial semantics

category and which landmark was used to define the region. This similarity is combined with the other computed similarities for the object (see Chapter 3 for description). The operation apply-region-filter is general enough to be applicable to all regions, including projective and absolute regions whose description is to follow.<sup>1</sup>

*Semantic operation* apply-spatial-region

An example of the interplay of the operations construct-region-proximal and apply-region-filter for a spatial scene can be seen in Figure 6.4. The following table summarizes the similarities computed when applying the region to the context (Figure 6.4 left).

### **6.3 Frames of reference**

Projective and absolute relations are defined in terms of focal directions. Consequently, for these kinds of relations the rotation of the landmark is an important issue determining the precise applicability of these relationships. For example, what is considered the front direction of a landmark has a direct effect on what is considered a frontal region. It turns out that there is considerable amount of choice when it comes to how to define the rotation of the landmark. The combination of a coordinate system, in particular its rotation, with a landmark is called reference system. Reference systems have been dealt with in great

<sup>1</sup> This operation can be very general because its implementation defers different methods of computing similarity for different category types using the method dispatching facility of lisp.

### 6.3 Frames of reference

Figure 6.4: When a region is applied, first, the context (left figure) is transformed so that the landmark is at the origin of the coordinate system (middle figure) which is followed by the application of the spatial relation (right figure). Here, these steps are depicted for the category near and the landmark box-1.

detail in cognitive semantics and psycholinguistics under the term frame of reference. Levinson (1996; 2003) identifies three possible frames of reference: intrinsic, relative and absolute, all of which denote a particular way of construing a landmark for spatial relationships involving direction. In German all three frames of reference are possible.

### 6 Spatial semantics

determined front, and it is the position of the observer together with the position of the tree that designates the precise region denoted as front.

**Absolute frame of reference** Absolute frames of reference construe the landmark using an external rotation. Neither intrinsic properties nor the perspective on the landmark determine the layout of the coordinate system, but rather geocentric features of the environment, for instance cardinal directions as in *nördlich* ('north') or the direction of gravity as in *über* ('above') govern what the precise layout of the reference system is.

Figure 6.5: Frames of reference have a profound effect on spatial relations. In all three pictures spatial relations are shown with box-1 as reference object. The left figure shows the landmark construed with an intrinsic frame of reference which orients the coordinate system such that the front of the landmark (little blue line in the landmark) corresponds to the frontal spatial relation with left, right and back projective relations aligned accordingly. The middle figure shows the same landmark, but with a relative frame of reference constructed from the perspective of robot robot-1 which entails that frontness corresponds to a region between the perspective and the landmark. Left and right in relative frames of reference are aligned not with respect to front, but rather are parallel to the left and right side of the perspective robot-1. The right figure shows an absolute frame of reference applied to the landmark box-1. Cardinal directions are aligned based on a geocentric direction induced on the scene by a marker.

The differences in processing frames of reference are captured using distinct semantic operations. In other words, absolute relationships, such as *nördlich* 6.3 Frames of reference

('north') or *über* ('above') demand other semantic operations as relative and intrinsic ones. For instance, processing of phrases involving absolute regions, e.g. *nördlich* ('north'), is represented using the construct-region-absolute operation, which takes a landmark and transforms the context with respect to the landmark, subsequently applying a rotation that follows from a geocentric direction. Some of the spatial scenes recorded by the robots feature a geocentric marker on the wall. The direction towards this marker defines the direction to the north. Figure 6.5 gives an example.

*Semantic operation* construct-region-absolute

Frontal prepositions, e.g., *vor* ('front') and *hinter* ('back'), can have both intrinsic and relative readings. Both readings are incorporated into a single operation, which construes the landmark both in relative and intrinsic way signified by an additional parameter of type f-o-r (frame of reference) to the operation. For the relative reading the perspective on the scene additionally influences the layout of the region. The viewpoint on the scene constrains front regions in such a way that only those locations which are between the perspective and the landmark have a high degree of applicability.

*Semantic operation* construct-region-frontal

Vertical relations can be construed with an absolute, relative or intrinsic frame of reference. In the case of absolute frames of reference the orientation is derived from gravity. For the purpose of this book only absolute frames of reference readings are implemented in the operation construct-region-vertical.

### **6.4 Internal and external regions**

Another line of processing distinctions can be made between internal and external relations. *North* and *south*, but also prepositional use of *front*, e.g. *vor*, are referring to external regions, that is the region lies outside of the landmark. Internal regions on the other hand lie inside the reference object. Adverbs such as *vorne* ('front') denote such regions inside the landmark. Consequently, they require separate treatment and there is a specific operation for handling the internal processing of frontal relations construct-region-frontal-internal.

*Semantic operation* construct-region-frontal-internal

Internal lateral regions are not clearly marked in syntax. While lateral prepositions clearly denote an external region, lateral adverbs can be used more varied which becomes apparent since they can be complemented both by *von* headed prepositonal phrases, as well as *in* headed prepositional phrases. In other words, the interpretation of an adverb depends on the complement. If there is no complement both readings internal and external are possible.

### 6.5 Group-based reference

Figure 6.6: Group-based reference requires computing a landmark based on a group of objects. The centroid of the group of objects, in this case all blocks in the context, is construed using a relative frame of reference. Consequently, object obj-182 could be described in German as *der vordere Block* ('the front block').

### **6.5 Group-based reference**

The semantics of German spatial adjectives is best understood in terms of groupbased reference.<sup>2</sup> In order for a group of objects to function as a reference object, the group needs to be construed as a landmark object, and in particular its position needs to be established. One way of computing a position for a group of objects, is to use the spatial centroid (center of mass) of the group as the position of the reference object. Additionally, a frame of reference, in other words a rotation, needs to be chosen. This choice depends on the spatial relation. For absolute relations the frame of reference is determined by an absolute frame of reference. In the absence of intrinsic features of the group of objects, a relative frame of reference seems to be the natural choice, as a spatial group of objects has no intrinsic front without including further constraints. Together, the centroid and the respective frame of reference sufficiently describe the reference system in order for spatial relations to be applied.

*Semantic operation* apply-spatial-category-group-based

description Applies the spatial category based on a group-based landmark.

<sup>2</sup> Recent evidence (Moratz & Tenbrink 2006) points to more variety in interpretation. For the purpose of this book, however, I choose to model group-based semantics only.

### 6 Spatial semantics

```
arguments ?target-set (of type entity-set)
              ?source-set (of type entity-set)
              ?category (of type spatial-category)
```
Group-based reference offers a technical challenge of how to compute the group used for reference in the first place. Given that all objects in the context are scored by successive operations, how can a group of objects be established, in order to compute the spatial centroid? For instance, in phrases like *der linke block* ('the left block'), the spatial adjective is part of a noun phrase, which primarily denotes the type of objects that constitute a set, namely the set of all block which relates to the group that the reference should be based on. The implementation of the semantic operation apply-spatial-category-group-based relies on a well-known clustering algorithm called *k*-means) (Lloyd 1982) in order to find the group of objects in the input set. The scores of all objects in the input set are used to divide the input set into two groups and all elements in the group with the higher score centroid are used to compute the spatial landmark.

### **6.6 Perspective marking**

Figure 6.7: The two figures show the influence perspective has on relative frames of reference. The left figure shows the landmark box-1 when construed with a relative frame of reference from the perspective of robot-1. In this configuration object obj-266 is in front and object obj-265 is to the right. Whereas when the same landmark box-1 is construed with a relative frame of reference from the perspective of robot-2 it is object obj-265 which is in front, whereas object obj-266 is to the left.

### 6.7 Discussion

The perspective of relative frames of reference is sometimes explicitly marked by speakers. In the example *der Block links von der Kiste von dir aus* ('the block left of the box from your perspective'), the speaker choose to provide a perspective *von dir aus* ('from your perspective'). Only relative interpretations of a spatial phrase can be perspective marked. The perspective itself marks the position of the viewpoint, and therefore also the view direction, i.e. rotation.

Intrinsic frames of reference computationally behave very similar to perspective-marked relative frames. Some argue therefore, that an intrinsic reference system is in essence a conflated relative reference system that coincides with the perspective on the scene (Levinson 1996). Hence, intrinsic reference systems are never perspective marked, since they already include position and orientation. However, perspective marking is only compatible with relative frames of reference and excludes intrinsic the usage of intrinsic or absolute frames of reference. On the other hand, relative reference systems always explicitly or implicitly mark perspective, since they cannot be conceived without since by definition relative reference systems always construe the world from a perspective (see Figure 6.7).

Perspective on a scene is changed by an operation that transforms a complete spatial context as if it had been perceived from a particular viewpoint.

### *Semantic operation* geometric-transform

### **6.7 Discussion**

### **6.7.1 Functional constraints**

Purely geometric accounts of spatial semantics have been criticized on the basis of psycholinguistic studies that reveal for many spatial relations, that additional functional constraints influence their applicability. Studies in particular for topological relations, including *in* and *on*, but also for projective relations such as *over* and *under* (Coventry, Prat-Sala & Richards 2001) as well as *in front* and *behind* (Carlson-Radvansky & Radvansky 1996) have led to new proposals (Coventry et al. 2005) as to how to include functional considerations into the semantics

### 6 Spatial semantics