tailieunhanh - Báo cáo khoa học: "A Best-First Search Algorithm for Generating Referring Expressions"

Existing algorithms for generating referential descriptions to sets of objects have serious deficits: while incremental approaches 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 preferences and several techniques to cut down the search space. Preliminary results show the effectiveness of the new algorithm. . | A Best-First Search Algorithm for Generating Referring Expressions Helmut Horacek Universităt des Saarlandes FR Informatik Postfach 151150 D-66041 Saarbrucken Germany email horacek@ Abstract Existing algorithms for generating referential descriptions to sets of objects have serious deficits while incremental approaches 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 preferences 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 generated 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 identifying sets of objects by incorporating linguistically 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