A Fast Algorithm for the Generation of Referring Expressions

A Fast Algorithm for the Generation of Referring Expressions Abstract We simplify previous work in the development of algorithms for the generation of referring expre~ sions while at the same time taking account of psy- cholinguistic findings and transcript data. The result is a straightforward algorithm that is computation- ally tractable, sensitive to the preferences of human users, and reasonably domain-independent. We pro- vide a specification of the resources a host system must provide in order to make use of the algorithm, and describe an implementation used in the IDAS sys- tem. Introduction In previous work [Da189,DH91,Rei90a,Rei90b] we have proposed algorithms for determining the con- tent of referring expressions. Scrutiny of the psy- cholinguistics literature and transcripts of human di- alogues shows that in a number of respects the be- haviour of these algorithms does not correspond to what people do. In particular, as compared to these algorithms, human speakers pay far less attention to reducing the length of a referring expression, and far more attention to making sure they use attributes and values that human hearers can easily process; in the terms introduced in [Da188,Da189], hearers are more concerned with the principle of sensitivity than with the principle of efficiency. We have designed a new referring expression generation algorithm that is based on the~ observations, and believe that the new algorithm is more practical for real-world natu- ral language generation systems than the algorithms we have previously proposed. In particular, the al- gorithm is: • fast: its run-time is linear in the number of distrac- tors, and independent of the number of possible modifiers; • sensitive to human preferences: it attempts to use easily perceivable attributes and basic-level [Ros78] attribute values; and • Supported by SERC grant GR/F/36750. E-mail ad- dress is E.Reiter@ed. ac.uk. tAiso of the Centre for Cognitive Science at the Univer- sity of Edinburgh. E-mail address is R. DaleQed. ac .uk. Ehud Reiter*and Robert Dalef Department of Artificial Intelligence University of Edinburgh Edinburgh EH1 1tlN Scotland • domain-independent: the core algorithm should work in any domain, once an appropriate knowl- edge base and user model has been set up. A version of the algorithm has been implemented within the IDAS natural-language generation system [RML92], and it is performing satisfactorily. The algorithm presented in this paper only gener- ates definite noun phrases that identify an object that is in the current focus of attention. Algorithms and models that can be used to generate pronominal and one-anaphoric referring expressions have been presented elsewhere, e.g., [Sid81,GJW83,Da189]. We have recently begun to look at the problem of gen- erating referring expressions for objects that are not in the current focus of attention; this is discussed in the section on Future Work. Background Distinguishing Descriptions The term 'referring expression' has been used by dif- ferent people to mean different things. In this paper, we define a referring expression in intentional terms: a noun phrase is considered to be a referring expres- sion if and only if its only communicative purpose is …

Content truncated to 500 words