A Best-First Search Algorithm for Generating Referring Expressions

A Best-First Search Algorithm for Generating Referring Expressions Helmut Horacek Uniyersitat des Saarlandes, FR 6.2 Informatik Postfach 151150, D-66041 Saarbdicken, Germany email: horacek@cs.uni - sb.de Abstract Existing algorithms for generating referen- tial descriptions to sets of objects have serious deficits: while incremental appro- aches may produce ambiguous and redundant expressions, exhaustive searches are computationally expensive. Mediating between these extreme control regimes, we propose a best-first searching algorithm for uniquely identifying sets of objects. We incorporate linguistically motivated prefer- ences and several techniques to cut down the search space. Preliminary results show the effectiveness of the new algorithm. 1 Introduction A referential description (Donellan 1966) serves the purpose of letting the addressee identify an object or a set of objects out of the context set, the objects assumed to be in the current focus of attention. The referring expression to be gener- ated needs to be a distinguishing description, that is, a description of the intended referent(s), the target set. Its elements are to be distinguished from potential distractors (McDonald 1981), the contrast set, which entails all elements of the context set except the intended referent(s). Several algorithms have been developed for this purpose, differing in terms of computational efficiency, quality and coverage. For identifying sets of objects rather than individuals, they typi- cally suffer from complementary deficits: while incremental approaches may produce ambiguous, redundant expressions, exhaustive searches are computationally expensive. Mediating between these extreme control regimes, we propose a best-first search algorithm for uniquely identi- fying sets of objects, by incorporating lingui- stically motivated preferences and techniques to cut down the search space. Preliminary results show the effectiveness of the new algorithm. This paper is organized as follows. We review relevant work in the field and motivate our goals. Then we describe the new algorithm Finally, we illustrate its functionality by some examples. 2 Motivation and Previous Approaches Generating referring expressions has been pursued since the eigthies (Appelt 1985, Kronfeld 1986, Appelt and Kronfeld 1987). Later, Dale and Reiter have put considerably more emphasis on computational efficiency in the systems EPICURE (Dale 1988), FN (Reiter 1990), and IDAS (Reiter, Dale 1992). Their algorithms are sensitive to human preferences (e.g., preferring basic categories (Rosch 1978)), and efficient in the sense of minimality of the elements appearing in the resulting referring expression. They differ, however, in terms of the precise interpretation of the minimality criterion. In the mid-nineties, the associated debate of computational efficiency versus minimality of the elements appearing in the resulting referring 103 expression seemed to be settled in favor of the incremental approach (Dale and Reiter, 1995) — motivated by various results of psychological experiments (see Levelt 1989), certain non- minimal expressions are tolerated in favor of adopting the simple and fast strategy of incre- mentally selecting ambiguity-reducing attributes from a domain-dependent preference list. With the extension of the algorithm's scope to the identification of sets of objects rather than individuals (most recently, van Deemter 2002), the incremental strategy was in some sense put to the extreme. Since only …

Content truncated to 500 words