A System for Generating Descriptions of Sets of Objects in a Rich variety

A System for Generating Descriptions of Sets of Objects in a Rich Variety Helmut Horacek Universität des Saarlandes F.R. 6.2 Informatik Postfach 151150 D-66041 Saarbrücken, Germany email: horacek@cs.uni-sb.de Abstract Even ambitious algorithms for the gener- ation of referring expressions that iden- tify sets of objects are restricted in terms of efficiency or in their expressive reper- toire. In this paper, we report on a system that applies a best-first searching proce- dure, enhancing both its effectiveness and the variety of expressions it can generate. 1 Introduction Generating referring expressions has recently been extended from the identification of single to sets of objects. However, existing algorithms suffer in terms of efficiency and expressiveness. In this paper, we report on a system that applies a best-first searching procedure, with an enhanced effectiveness and a larger variety of expressions it can generate. The system's repertoire includes compositions of partially identifying expressions and descriptions of objects to be excluded, there- by taking into account impacts on surface forms. Throughout this paper, we refer to a scenario with a set of 12 vehicles as defined in Figure 1. All vehicles are identifiable individually, to make the identification task meaningful. Only minor differences hold between some of these vehicles, which makes the identification task challenging. This paper is organized as follows. First, we motivate our goals. Then we describe techniques for enhancing efficiency. We follow by illus- trating improvements of expressiveness. Finally, 2we evaluate several efficiency-related techniques. Motivation Identifying sets of objects originally followed the incremental algorithm (Dale and Reiter 1995), as in (Bateman 1999), (Stone 2000) and (Krahmer et al. 2003), with limited coverage, since only few attributes typically apply to all intended referents and to none of the potential distractors. There- fore, van Deemter (2002) has extended the set of descriptors to boolean combinations of attributes, including negations. Unfortunately, when apply- ing the incremental strategy, this may lead to the inclusion of too many redundant descriptors in the final specification. This deficit disappeared using an exhaustive search (Gardent 2002), but run-time then increases considerably. Mediating between these two extreme search paradigms, we have developed a best-first searching algorithm that avoids the major deficit of the incremental approach (Horacek 2003). Since its intermediate results can also be used as partial descriptions, we build on the flexibility of this new algorithm to extend its expressive capabilities. In addition, we further enhance its efficiency-seeking measures. These extensions attack the deficits previous •algorithms share, according to (Horacek 2004): Expressions produced may become lengthy: for identifying sets of vehicles in the scenario in Figure 1, we have obtained non-redundant specifications with up to 8 descriptors. • Specifications may contain some disjunctions, frequently causing the production of structur- ally ambiguous expressions (Gardent 2002) – “trucks and sportscars which are white or in the center” referring to x1, x5, x11 (Figure 1). We avoid these deficits by not restricting boolean expressions to a form with conjunctions as top level operators, as others always do. This allows us to incorporate descriptions of …

Content truncated to 500 words