Generation of Referring Expressions: Assessing the Incremental Algorithm
- 31 October 2011
- journal article
- Published by Wiley in Cognitive Science
- Vol. 36 (5) , 799-836
Abstract
A substantial amount of recent work in natural language generation has focused on the generation of ‘‘one‐shot’’ referring expressions whose only aim is to identify a target referent. Dale and Reiter's Incremental Algorithm (IA) is often thought to be the best algorithm for maximizing the similarity to referring expressions produced by people. We test this hypothesis by eliciting referring expressions from human subjects and computing the similarity between the expressions elicited and the ones generated by algorithms. It turns out that the success of the IA depends substantially on the ‘‘preference order’’ (PO) employed by the IA, particularly in complex domains. While some POs cause the IA to produce referring expressions that are very similar to expressions produced by human subjects, others cause the IA to perform worse than its main competitors; moreover, it turns out to be difficult to predict the success of a PO on the basis of existing psycholinguistic findings or frequencies in corpora. We also examine the computational complexity of the algorithms in question and argue that there are no compelling reasons for preferring the IA over some of its main competitors on these grounds. We conclude that future research on the generation of referring expressions should explore alternatives to the IA, focusing on algorithms, inspired by the Greedy Algorithm, which do not work with a fixed PO.Keywords
This publication has 34 references indexed in Scilit:
- Inter-Coder Agreement for Computational LinguisticsComputational Linguistics, 2008
- Reference production: Production-internal and addressee-oriented processesLanguage and Cognitive Processes, 2008
- Generating Referring Expressions that Involve Gradable PropertiesComputational Linguistics, 2006
- Tracking the time course of multidimensional stimulus discrimination: Analyses of viewing patterns and processing times during “same”-“different“ decisionsThe European Journal of Cognitive Psychology, 2002
- Generating Referring Expressions: Boolean Extensions of the Incremental AlgorithmComputational Linguistics, 2002
- Risk-taking and recovery in task-oriented dialogueJournal of Pragmatics, 1996
- Computational Interpretations of the Gricean Maxims in the Generation of Referring ExpressionsCognitive Science, 1995
- The Hcrc Map Task CorpusLanguage and Speech, 1991
- Referring as a collaborative processCognition, 1986
- Planning english referring expressionsArtificial Intelligence, 1985