Referring Expression Generation as a Search Problem

Referring Expression Generation as a Search Problem Bernd Bohnet Bohnet@iis.uni-stuttgart.de Institute for Intelligent Systems University of Stuttgart 70569 Stuttgart Germany Robert Dale Robert.Dale@mq.edu.au Centre for Language Technology Macquarie University Sydney nsw 2109 Australia Abstract One of the most widely explored issues in natu- ral language generation is the generation of re- ferring expressions (gre): given an entity we want to refer to, how do we work out the content of a referring expression that uniquely identifies the intended referent? Over the last 15 years, a number of authors have proposed a wide range of algorithms for addressing different aspects of this problem, but the different approaches taken have made it very difficult to compare and con- trast the algorithms provided in any meaningful way. In this paper, we propose a characterisa- tion of the problem of referring expression gen- eration as a search problem; this allows us to recast existing algorithms in a way that makes their similarities and differences clear. 1 Introduction A major component task in natural language generation (nlg) is the generation of referring expressions: given an entity that we want to refer to, how do we determine the content of a referring expression that uniquely identifies that intended referent? Since at least (Dale, 1989), the standard conception of this task in the lit- erature has been as follows: 1. We assume we have a knowledge base that characterises the entities in the domain in terms of a set of attributes and the values that the entities have for these attributes; so, for example, our knowledge base might represent the fact that entity e1 has the value cup for the attribute type, and the value red for the attribute colour. 2. In a typical context where we want to re- fer to some ei, which we call the intended referent, there will be other entities from which the intended referent must be distin- guished; these are generally referred to as distractors. So, for example, we may want to distinguish a particular cup from all the other items present in the context of a din- ing table. 3. The goal of referring expression generation is therefore to find some collection of at- tributes and their values which distinguish the intended referent from all the potential distractors in the context. Over the last 15 years, a wide variety of algo- rithms have been proposed to deal with specific aspects of this problem. For example, while ear- lier algorithms focussed on the use of attributes that correspond to simple one-place predicates, later work attempts to address the use of rela- tional predicates, and other work looks at the incorporation of boolean operators such as not and and. The consequence is that we now have a considerable body of research in this area, but it is difficult to establish just how these different algorithms relate to each other. This paper represents a first step to- wards consolidating the results in this area, with the aim of developing a framework within which …

Content truncated to 500 words