Referring expression generation

Referring expression generation is a subtask of Natural language generation (NLG), which involves creating referring expressions (noun phrases) that identify specific entities to the reader. A variety of algorithms have been developed in the NLG community to generate different types of referring expressions.

History

REG goes back to the early days of NLG. One of the first approaches was done by Winograd 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 BERTRAND 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 lead by Dale and Reiter who stressed the identification of the referent as the central goal. 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.

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
• Relational Descriptions
• Context Dependency
• Vagueness
• Gradability
• Salience
• Generation of Pronouns

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.

Problem Definition

Dale and Reiter (1995) think about referring expressions as distinguishing descriptions.

They define:

• The referent as the entity that should be described
• The context set as set of salient entities
• The contrast set or potential distractors as all elements of the context set except the referent
• A property as a reference to a single attribute-value pair

Each entity in the domain can be characterised as a set of attribute-value pairs.

The problem then is defined as follows:

Let $r$ be the intended referent, and $C$ be the contrast set. Then, a set $L$ of attribute–value pairs will represent a distinguishing description if the following two conditions hold:

1. Every attribute–value pair in $L$ applies to $r$: that is, every element of $L$ specifies an attribute–value that $r$ possesses.
2. For every member $c$ of $C$, there is at least one element $l$ of $L$ that does not apply to $c$: that is, there is an $l$ in $L$ that specifies an attribute–value that $c$ does not possess. $l$ is said to rule out $c$.

In other words to generate a referring expression one is looking for a set of properties that apply to the referent but not to the distractors.

The problem could be easily solved by conjoining all the properties of the referent which often leads to long descriptions violating the second Gricean Maxim of Quantity. Another approach would be to find the shortest distinguishing description like the Full Brevity algorithm does. Yet in practice it is most common to instead include the condition that referring expressions produced by an algorithm should be as similar to human-produced ones as possible although this is often not explicitly mentioned.

Basic Algorithms

Full Brevity

The Full Brevity algorithm always finds a minimal distinguishing description meaning there is no shorter distinguishing description in regard to properties used.

Therfore it iterates over $n=1,2,3,4,...$ and checks every description of a length of $n$ properties until a distinguishing description is found.

Two problems arise from this way of creating referring expressions. Firstly the algorithm has a high complexity meaning it is NP-hard which makes it impractical to use. Secondly human speakers produce descriptions that are not minimal in many situations.

Example

For example, the following text has several referring expressions

He told the tourist that rain was expected tonight in Southern Scotland.

• He is a pronoun which refers to a person who was previously mentioned in the conversation.
• the tourist is a definite noun phrase which identifies another person
• tonight is a temporal referent which identifies a particular time period
• Southern Scotland is a spatial reference which identifies a particular spatial region

Criteria for good referents

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.

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, 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. 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 [5] 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. 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

Other Kinds of Referring Expressions

Of course there are many other kinds of referring expressions, such as one-anaphora and event references, in addition to the ones described above. Unfortunately little research has been done on how to best generate such kinds of referring expressions.