An Algorithm for Generating Referential Descriptions with Flexible Interfaces

Helmut HoracekACL 1997 · DOI

Abstract

Generating referential descriptions such as "the large red cup" requires balancing logical distinguishability with linguistic naturalness. Traditional algorithms often treat property selection and linguistic realization as separate processes, leading to expressions that are mathematically correct but linguistically awkward. This paper introduces a goal-driven, iterative algorithm that interleaves property selection with linguistic constraints. By incorporating lexical and scoping checks directly into the selection process, the algorithm ensures that generated descriptions are both identifying and naturally expressible.

Introduction: The Generation Gap

In Natural Language Generation (NLG), a "referential description" is a phrase used to identify a specific object among distractors. For decades, the gold standard was the "Incremental Algorithm" (Dale & Reiter), which selects properties (color, size, type) until only the target object remains. However, Helmut Horacek identifies a major "generation gap" in this approach. Existing algorithms typically made two problematic assumptions: that all possible attributes of every object are instantly available to the system, and that any set of logical predicates can be easily converted into a clear, grammatical sentence.

In reality, a vision system might find it computationally expensive to compute all attributes upfront. Furthermore, some combinations of attributes lead to linguistic "nightmares"—such as infinite recursion or scoping ambiguities (e.g., "the bottle on the table on which there is a cup...").

The Proposed Algorithm

The paper proposes a three-stage iterative algorithm designed to be both goal-driven and incremental. Unlike previous models, this approach checks for linguistic "slots" during the selection process to avoid picking properties that are logically sound but linguistically impossible to express clearly.

The three-stage iterative algorithm for generating referential descriptions, featuring success checks, property selection with linguistic "vetos," and description extension.

The algorithm follows these core steps:

  1. Check Success: Determines if the current description uniquely identifies the target or if a user-defined "complexity limit" has been reached.
  2. Choose Property: Proposes properties based on salience and proximity. It includes critical "veto" steps: a Lexical Check to ensure the property maps to a word, and a Scoping Check (Check-Scope) to prevent ambiguous nested structures.
  3. Extend Description: Updates linguistic resources and the constraint network ($N$), which tracks which objects are ruled out by the current description. It prefers descriptors that fill "empty slots" in the emerging sentence structure.

Evaluation and Qualitative Results

The algorithm was evaluated using a qualitative "toy" environment consisting of a row of four tables populated with various cups, glasses, and books. This setup allowed the author to demonstrate how the algorithm handles specific edge cases that typically cause previous models to fail or produce unnatural language.

The qualitative "toy" environment used to evaluate the algorithm, featuring tables ($t_1$ to $t_4$) with various arrangements of cups ($c$), glasses ($g$), and books ($b$).

Key findings from this evaluation include:

  • Naturalness: The algorithm produces "flat" expressions (e.g., "the table with a glass and a cup") rather than the deeply nested, awkward structures produced by earlier approaches.
  • Inference Awareness: The system rejects redundant descriptors. If an object's properties are already inferable from the description generated so far, the algorithm avoids explicit repetition.
  • Ambiguity Avoidance: Through the Check-Scope function, the algorithm identifies and rejects descriptions that would lead to "unintended scope relations," where a listener might misattribute a relative clause.

Conclusion and Future Work

Horacek’s work demonstrates that property selection cannot be separated from linguistic realization. By introducing complexity limits, the algorithm also mimics human behavior—stopping when a description becomes too cumbersome even if the object isn't perfectly identified. While the current version relies on the quality of external perception and lexicalization modules, it provides a robust framework for more natural NLG. Future research will focus on extending the algorithm to handle pluralities ("the two red cups") and negative descriptions.

Summary updated

BibTeX
@inproceedings{horacek1997algorithm,
  author = {Helmut Horacek},
  title = {{An Algorithm for Generating Referential Descriptions with Flexible Interfaces}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1997},
  doi = {10.3115/976909.979644},
}
Figure