Concept Generation in Language Evolution

1 Introduction

Humans are skilled at making sense of novel combinations of concepts, so to create artifical languages for implementation in AI systems, we must model this ability. Standard approaches to combining concepts, e.g. fuzzy set theory, have been shown to be inadequate [Osherson and Smith, 1981]. Composite labels frequently have 'emergent attributes' [Hampton, 1987] which cannot be explicated by decomposing the label into its constituent parts. We argue that in this case a new concept is generated. This project aims to determine conditions for such concept generation, using multi-agent models of language evolution.

1.1 Thesis Outline

The project divides into three parts. Firstly, we have developed a model of concept combination within the label semantics framework as given in [Lawry and Tang, 2009]. The model is inspired by and reflects results in [Hampton, 1987], in which membership in a composite concept can be rendered as the weighted sum of memberships in individual concepts.

Secondly, we must show that compositionality can evolve within a population of interacting agents. Preliminary work in this area examines the ability of a population of agents to converge to a shared set of dimension weights.

Thirdly, we will investigate the generation of new unitary concepts from existing composite concepts, building further upon the multi-agent model.

2 Background

This work is based on the label semantics framework [Lawry, 2004; Lawry and Tang, 2009], together with prototype theory [Rosch, 1975], where membership in a concept is based on proximity to a prototype, and conceptual spaces [G¨ardenfors, 2004]. The latter views concepts as regions of a space made up of quality dimensions and equipped with a distance metric, for example the RGB colour space.

∗Support from EPSRC Grant No. EP/E501214/1 acknowledged

Label semantics proposes that agents use a set of labels LA = {L1, ...,Ln} to describe a conceptual space Ω with distance metric d(x, y). Labels Li are associated with prototypes Pi ⊆ Ω and uncertain thresholds εi, drawn from probability distributions δεi . The threshold εi captures the notion that an element x ∈ Ω is sufficiently close to Pi to be labelled Li. The appropriateness of a label Li to describe x is quantified by µLi (x), given by

Labels can then be described as Li =<Pi, d(x, y), δεi>.

3 ANewModel of Concept Composition

Experiments in [Hampton, 1987] propose that human concept combination can (roughly) be modelled as a weighted sum of attributes such as 'has feathers', 'talks' (for the concept 'Bird'). These attributes differ from quality dimensions in conceptual spaces: they tend to be binary, complex, and multidimensional. We therefore view each attribute as a label in a conceptual space Ωi and combine these labels in a binary space {0, 1}n illustrated in figure 1, where a conjunction of such labels ˜α = ∧ni=1 ±Li maps to a binary vector ⃗xα taking value 1 for positive labels Li and 0 for negated labels ¬Li. We treat membership in ˜α in the binary space within the label semantics framework. So ˜α is described in the binary space by ˜α =<⃗xα, d(⃗x, ⃗x′ ), δ> as before.

We define a distance metric in the binary space {0, 1}n as:

Definition 1 Weighted Hamming Distance

For ⃗λ ∈ (R+)n , ∀⃗x, ⃗x′ ∈ {0, 1}n , where (·) is the scalar product,

Theorem 2 Let α = ∧ni=1 ±Li and λT = ∑ni=1 λi. Let ε ∼ U(0, λT ), d = H⃗λ . Then:

Compound concepts ˜ θ, ˜ ϕ may be combined in a higher level binary space. Then ˜ θ · ˜ ϕ can be expressed in the continuous space as a weighted sum of ˜ θ and ˜ ϕ.

We have therefore shown that combining labels in a weighted binary space leads naturally to the creation of composite and compound concepts as weighted sums of individual labels, reflecting results in [Hampton, 1987]. We have further characterised notions of necessary and impossible attributes using ideas from possibility theory.

4 Convergence of DimensionWeights Across a Population

We investigate how a population of agents in a multi-agent simulation playing a series of language games might converge to a shared set of dimension weights. Agents with equal labels L1 = L2 =<1, d, U[0, 1]>∈ Ω1 = Ω2 = [0, 1] (d is Euclidean distance), and randomly initiated weights λ ∈ [0, 1] engage in a series of dialogues about elements in the conceptual space, adjusting their weights after each dialogue is completed. At each timestep, speaker agents make assertions αi = ±L1 ∧ ±L2 about elements ⃗x ∈ Ω1 × Ω2 which maximise µαi (⃗x) = λµL1 (x1) + (1 - λ)µL2 (x2).

The listener agent assesses αi against its own label set. If µαi (x) ≤ w, the reliability of the speaker agent, the listener agent updates its label set.

The update consists in incrementing the dimension weight λ towards a value A, so that λt+1 = λt + h(A - λt) where h = 10-3 and

This is the quantity that satisfies µαi (x) = w. If A < 0 (or A > 1) we set A = 0 (or A = 1).

The convergence across the population is measured by the standard deviation (SD) of the λ across the population.

Figure 2 shows the results of two sets of simulations across varying values of w. The two sets of simulations have distinct distributions of elements encountered within the space. When w is 0.5 or below, the agents do not converge to shared dimension weights (not shown). When w > 0.5, agents do converge to shared dimension weights: SD is low. The weights converged to depend both on the reliability, w, of each agent, and the distribution of elements in the conceptual space.

0.5 for all values of w

(b) x1 ∼ U[0.25, 0.75], x2 ∼ U[0, 0.5]. λ converges to varying values.

Figure 2: Mean SD and λ at time t = 2000 for different values of w. Each point averages 25 simulations run with 10 agents.

When w = 1 we can predict the value to which λ will converge. Consider the quantity A - λt which determines whether the update is positive or negative at each step.

Definition 4 A positive region R+ ⊂ Ω is a set of points R+ = {⃗x ∈ Ω : A - λt ≥ 0}

Theorem 5 Let p+ denote the probability of a point ⃗x ∈ Ω falling in a positive region and let w = 1 across the population. Then the expected value of λ converges to p+.

5 FurtherWork

We are currently working on analytical results to predict the value of λ to which agents converge. Under certain circumstances, such as the case where w = 1, or with an altered updating model, analytic results are possible. We will extend this work to look at the utility of using conjunctive assertions within these simulations.

Work in the third year will focus on examining how new concepts might be generated from the combination of existing ones. We will build on the language evolution model currently in development.