Structuring Knowledge for Reference Generation: A Clustering Algorithm

Structuring Knowledge for Reference Generation: A Clustering Algorithm Albert Gatt Department of Computing Science University of Aberdeen Scotland, United Kingdom agatt@csd.abdn.ac.uk Abstract This paper discusses two problems that arise in the Generation of Referring Expressions: (a) numeric-valued attributes, such as size or location; (b) perspective-taking in reference. Both problems, it is argued, can be resolved if some structure is imposed on the available knowledge prior to content determination. We describe a clustering algorithm which is suffi- ciently general to be applied to these diverse problems, discuss its application, and evaluate its performance. 1 Introduction The problem of Generating Referring Expressions (GRE) can be summed up as a search for the prop- erties in a knowledge base (KB) whose combination uniquely distinguishes a set of referents from their dis- tractors. The content determination strategy adopted in such algorithms is usually based on the assump- tion (made explicit in Reiter (1990)) that the space of possible descriptions is partially ordered with respect to some principle(s) which determine their adequacy. Traditionally, these principles have been defined via an interpretation of the Gricean maxims (Dale, 1989; Reiter, 1990; Dale and Reiter, 1995; van Deemter, 2002)1. However, little attention has been paid to con- textual or intentional influences on attribute selection (but cf. Jordan and Walker (2000); Krahmer and The- une (2002)). Furthermore, it is often assumed that all relevant knowledge about domain objects is repre- sented in the database in a format (e.g. attribute-value pairs) that requires no further processing. This paper is concerned with two scenarios which raise problems for such an approach to GRE: 1. Real-valued attributes, e.g. size or spatial coor- dinates, which represent continuous dimensions. The utility of such attributes depends on whether a set of referents have values that are ‘sufficiently 1For example, the Gricean Brevity maxim (Grice, 1975) has been interpreted as a directive to find the shortest possible description for a given referent close’ on the given dimension, and ‘sufficiently distant’ from those of their distractors. We dis- cuss this problem in §2. 2. Perspective-taking The contextual appropriate- ness of a description depends on the perspective being taken in context. For instance, if it is known of a referent that it is a teacher, and a sportsman, it is better to talk of the teacher in a context where another referent has been introduced as the stu- dent. This is discussed further in §3. Our aim is to motivate an approach to GRE where these problems are solved by pre-processing the infor- mation in the knowledge base, prior to content deter- mination. To this end, §4 describes a clustering algo- rithm and shows how it can be applied to these different problems to structure the KB prior to GRE. 2 Numeric values: The case of location Several types of information about domain entities, such as gradable properties (van Deemter, 2000) and physical location, are best captured by real-valued at- tributes. Here, we focus on the example of location as an attribute taking a tuple of values which …

Content truncated to 500 words