Graph-Based Generation of Referring Expressions
Authors:
- 1 March 2003
- journal article
- Published by MIT Press in Computational Linguistics
- Vol. 29 (1) , 53-72
Abstract
This article describes a new approach to the generation of referring expressions. We propose to formalize a scene (consisting of a set of objects with various properties and relations) as a labeled directed graph and describe content selection (which properties to include in a referring expression) as a subgraph construction problem. Cost functions are used to guide the search process and to give preference to some solutions over others. The current approach has four main advantages: (1) Graph structures have been studied extensively, and by moving to a graph perspective we get direct access to the many theories and algorithms for dealing with graphs; (2) many existing generation algorithms can be reformulated in terms of graphs, and this enhances comparison and integration of the various approaches; (3) the graph perspective allows us to solve a number of problems that have plagued earlier algorithms for the generation of referring expressions; and (4) the combined use of graphs and cost functions paves the way for an integration of rule-based generation techniques with more recent stochastic approaches.Keywords
This publication has 12 references indexed in Scilit:
- Planarizing Graphs - A Survey and Annotated BibliographyJournal of Graph Algorithms and Applications, 2001
- Representation, reasoning, and relational structures: a hybrid logic manifestoLogic Journal of the IGPL, 2000
- Subgraph Isomorphism in Planar Graphs and Related ProblemsJournal of Graph Algorithms and Applications, 1999
- A new algorithm for error-tolerant subgraph isomorphism detectionIEEE Transactions on Pattern Analysis and Machine Intelligence, 1998
- Enabling technology for multilingual natural language generation: the KPML development environmentNatural Language Engineering, 1997
- Computational interpretations of the Gricean maxims in the generation of referring expressionsCognitive Science, 1995
- Incremental speech production and referential overspecificationLinguistics, 1989
- Planning english referring expressionsArtificial Intelligence, 1985
- The graph isomorphism diseaseJournal of Graph Theory, 1977
- Efficient Planarity TestingJournal of the ACM, 1974