Referring expression generation (REG) is the subtask of natural language generation (NLG) that received most scholarly attention. While NLG is concerned with the conversion of non-linguistic information into natural language, REG focuses only on the creation of referring expressions (noun phrases) that identify specific entities called targets.
This task can be split into two sections. The content selection part determines which set of properties distinguish the intended target and the linguistic realization part defines how these properties are translated into natural language. A variety of algorithms have been developed in the NLG community to generate different types of referring expressions.
Types of referring expressions A referring expression (RE), in linguistics, is any noun phrase, or surrogate for a noun phrase, whose function in discourse is to identify some individual object (thing, being, event...) The technical terminology for identify differs a great deal from one school of linguistics to another. The most widespread term is probably refer, and a thing identified is a referent, as for example in the work of John Lyons. In linguistics, the study of reference relations belongs to pragmatics, the study of language use, though it is also a matter of great interest to philosophers, especially those wishing to understand the nature of knowledge, perception and cognition more generally.
Various devices can be used for reference: determiners, pronouns, proper names... Reference relations can be of different kinds; referents can be in a "real" or imaginary world, in discourse itself, and they may be singular, plural, or collective.
Pronouns The simplest type of referring expressions are pronoun such as he and it. The linguistics and natural language processing communities have developed various models for predicting anaphor referents, such as centering theory,M Poesio, R Stevenson, B di Eugenio, J Hitzeman (2004). Centering: A Parametric Theory and Its Instantiations. Computational Linguistics 30:309-363 and ideally referring-expression generation would be based on such models. However most NLG systems use much simpler algorithms, for example using a pronoun if the referent was mentioned in the previous sentence (or sentential clause), and no other entity of the same gender was mentioned in this sentence.
Definite noun phrases There has been a considerable amount of research on generating definite noun phrases, such as the big red book. Much of this builds on the model proposed by Dale and Reiter. This has been extended in various ways, for example Krahmer et al.E Krahmer, S van Erk, A Verleg (2003). Graph-Based Generation of Referring Expressions. Computational Linguistics 23:53-72 present a graph-theoretic model of definite NP generation with many nice properties. In recent years a shared-task event has compared different algorithms for definite NP generation, using the TUNA corpus.
Spatial and temporal reference Recently there has been more research on generating referring expressions for time and space. Such references tend to be imprecise (what is the exact meaning of tonight?), and also to be interpreted in different ways by different people.E Reiter, S Sripada, J Hunter, J Yu, and I Davy (2005). Choosing Words in Computer-Generated Weather Forecasts. Artificial Intelligence 167:137-169. Hence it may be necessary to explicitly reason about false positive vs false negative tradeoffs, and even calculate the utility of different possible referring expressions in a particular task context.R Turner, Y Sripada, E Reiter (2009) Generating Approximate Geographic Descriptions. Proceedings of the 12th European Workshop on Natural Language Generation (ENLG), pages 42–49, Athens.
Criteria for good expressions Ideally, a good referring expression should satisfy a number of criteria: Referential success: It should unambiguously identify the referent to the reader. Ease of comprehension: The reader should be able to quickly read and understand it. Computational complexity: The generation algorithm should be fast No false inferences: The expression should not confuse or mislead the reader by suggesting false implicatures or other pragmatic inferences. For example, a reader may be confused if he is told Sit by the brown wooden table in a context where there is only one table.R Dale, E Reiter (1995). Computational interpretations of the Gricean maxims in the generation of referring expressions. Cognitive Science, 18:233–263.
History
Pre-2000 era REG goes back to the early days of NLG. One of the first approaches was done by WinogradT Winograd (1972). Understanding Natural Language. Academic Press, New York. Section 8.3.3, Naming Objects and Events in 1972 who developed an "incremental" REG algorithm for his SHRDLU program. Afterwards researchers started to model the human abilities to create referring expressions in the 1980s. This new approach to the topic was influenced by the researchers Appelt and Kronfeld who created the programs KAMP and BERTRANDD Appelt (1985). Planning English referring expressions. Artificial Intelligence, 26:1–33.D Appelt, A Kronfeld (1987). A computational model of referring. In Proceedings of the 10th International Joint Conference on Artificial Intelligence (IJCAI), pages 640–647, Milan.A Kronfeld (1990). Reference and Computation: An Essay in Applied Philosophy of Language. Cambridge University Press, Cambridge. and considered referring expressions as parts of bigger speech acts.
Some of their most interesting findings were the fact that referring expressions can be used to add information beyond the identification of the referent as well as the influence of communicative context and the Gricean maxims on referring expressions. Furthermore, its skepticism concerning the naturalness of minimal descriptions made Appelt and Kronfeld's research a foundation of later work on REG.
The search for simple, well-defined problems changed the direction of research in the early 1990s. This new approach was led by Dale and Reiter who stressed the identification of the referent as the central goal.R Dale (1989). Cooking up referring expressions. In Proceedings of the 27th Annual Meeting of the Association for Computational Linguistics (ACL), pages 68–75.R Dale (1992). Generating Referring Expressions: Constructing Descriptions in a Domain of Objects and Processes. TheMIT Press, Cambridge, MA.E Reiter (1990). The computational complexity of avoiding conversational implicatures. In Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics (ACL), pages 97–104, Pittsburgh, PA.E Reiter, R Dale (1992). A fast algorithm for the generation of referring expressions. In Proceedings of the 14th International Conference on Computational Linguistics (COLING), pages 232–238, Nantes. Like Appelt they discuss the connection between the Gricean maxims and referring expressions in their culminant paper in which they also propose a formal problem definition. Furthermore, Reiter and Dale discuss the Full Brevity and Greedy Heuristics algorithms as well as their Incremental Algorithm(IA) which became one of the most important algorithms in REG. This section is an excerpt of the following paper. For more details see: E Krahmer, K van Deemter (2012). Computational Generation of Referring Expressions: A Survey. Computational Linguistics 38:173-218
Later developments After 2000 the research began to lift some of the simplifying assumptions, that had been made in early REG research in order to create more simple algorithms. Different research groups concentrated on different limitations creating several expanded algorithms. Often these extend the IA in a single perspective for example in relation to:
Reference to Sets like "the t-shirt wearers" or "the green apples and the banana on the left"H Horacek (2004). On referring to sets of objects naturally. Proceedings of the 3rd International Conference on Natural Language Generation (INLG), pages 70–79, Brockenhurst.A Gatt, K van Deemter (2007). Lexical choice and conceptual perspective in the generation of plural referring expressions. Journal of Logic, Language and Information, 16:423–443.I H Khan, K van Deemter, G Ritchie (2008). Generation of referring expressions: Managing structural ambiguities. Proceedings of the 22nd International Conference on Computational Linguistics (COLING), pages 433–440, Manchester.M Stone (2000). On identifying sets. Proceedings of the 1st International Conference on Natural Language Generation (INLG), pages 116–123, Mitzpe Ramon. Relational Descriptions like "the cup on the table" or "the woman who has three children"R Dale, N Haddock (1991). Generating referring expressions involving relations. Proceedings of the 5th Conference of the European Chapter of the Association of Computational Linguists (EACL), pages 161–166, Berlin.E Krahmer, M Theune (2002). Efficient context-sensitive generation of descriptions in context. In K van Deemter, R Kibble, editors, Information Sharing: Givenness and Newness in Language Processing. CSLI Publications, Stanford, CA, pages 223–264.J Viethen, R Dale (2008). The use of spatial relations in referring expressions. Proceedings of the 5th International Natural Language Generation Conference (INLG), pages 59–67, Salt Fork, OH.Y Ren, K van Deemter, J Pan (2010). Charting the potential of Description Logic for the generation of referring expressions. Proceedings of the 6th International Natural Language Generation Conference (INLG), pages 115–124, Dublin.E Krahmer, M Goudbeek, M Theune (2014). Referring Expression Generation in Interaction: A Graph-based perspective. A Stent, S Bangalore (eds.), Natural Language Generation in Interactive Systems. Cambridge University Press. Context Dependency, Vagueness and Gradeability include statements like "the older man" or "the car on the left" which are often unclear without a contextK van Deemter (2006). Generating referring expressions that involve gradable properties. Computational Linguistics, 32(2):195–222.H Horacek (2005). Generating referential descriptions under conditions of uncertainty. Proceedings of the 10th European Workshop on Natural Language Generation (ENLG), pages 58–67, Aberdeen. Salience and Generation of Pronouns are highly discourse dependent making for example "she" a reference to "the (most salient) female person"R Passonneau (1996). Using centering to relax Gricean informational constraints on discourse anaphoric noun phrases. Language and Speech, 39:229–264.P W Jordan (2000). Intentional Influences on Object Redescriptions in Dialogue: Evidence from an Empirical Study. Ph.D. thesis, University of Pittsburgh.E Hajičová (1993). Issues of Sentence Structure and Discourse Patterns—Theoretical and Computational Linguistics, Vol. 2. Charles University, Prague.B J Grosz, A K Joshi, S Weinstein (1995). Centering: A framework for modeling the local coherence of discourse. Computational Linguistics, 21:203–225.D DeVault, C Rich, C L Sidner (2004). Natural language generation and discourse context: Computing distractor sets from the focus stack. Proceedings of the 17th International Meeting of the Florida Artificial Intelligence Research Society (FLAIRS), Miami Beach, FL.A Siddharthan, A Copestake (2004). Generating referring expressions in open domains. Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL), pages 407–414, Barcelona.I Paraboni, K van Deemter, J Masthoff (2007). Generating referring expressions: Making referents easy to identity. Computational Linguistics, 33:229–254.
Many simplifying assumptions are still in place or have just begun to be worked on. Also a combination of the different extensions has yet to be done and is called a "non-trivial enterprise" by Krahmer and van Deemter.E Krahmer, K van Deemter (2012). Computational Generation of Referring Expressions: A Survey. Computational Linguistics 38:173-218