Combining symbolic and corpus-based approaches for the generation of successful referring expressions

Konstantina Garoufi, Alexander KollerENLG 2011 · OpenReview

Abstract

Traditional Referring Expression Generation (REG) systems prioritize "human-likeness" or logical uniqueness. However, human speech is often suboptimal for task completion. This paper presents mSCRISP, a hybrid system that combines symbolic planning with a statistical model of referential success. By optimizing for the speed and accuracy of the listener's response in complex 3D environments, mSCRISP generates expressions that outperform both purely symbolic and purely statistical baselines.

Introduction

In Natural Language Generation (NLG), the task of Referring Expression Generation (REG) involves describing a target object such that a listener can uniquely identify it. Historically, the field has focused on two primary metrics: uniqueness (the description applies only to the target) and human-likeness (the description mimics human speech patterns).

Recent research suggests a disconnect between these metrics and actual communicative utility. Human-generated descriptions are frequently vague or omit critical landmarks, leading to confusion in complex environments. The authors of this study propose a shift in focus toward referential success: generating expressions that minimize the time and effort required for a listener to resolve the reference.

Methodology: The mSCRISP System

The mSCRISP system is a hybrid architecture that integrates symbolic AI with machine learning to optimize for utility.

Symbolic Planning with CRISP

The foundation of the system is CRISP, a planning-based approach to NLG. It utilizes Tree-Adjoining Grammars (TAG) to construct sentences. This symbolic component ensures that the generated phrases are grammatically correct and logically unique within the given context.

Statistical Success Model

To guide the selection of attributes (e.g., color, location, or landmarks), the authors trained a Maximum Entropy (MaxEnt) classifier. This model analyzes features of the current scene—such as the distance to the referent, the number of distractors, and the presence of landmarks—to predict which attributes will lead to the fastest resolution by a human user.

Metric Planning

The "glue" of the system is a metric planner (MetricFF). The probabilities generated by the MaxEnt success model are converted into "costs." The planner then searches for the "cheapest" path to a unique description. For instance, if the model predicts that mentioning a specific landmark is highly effective in a certain room, the cost of including that landmark decreases, making the system more likely to produce a redundant but helpful description.

Experimental Setup and Datasets

The system was developed and tested using the GIVE-2 Corpus, derived from the "Generating Instructions in Virtual Environments" challenges.

A typical virtual environment from the GIVE-2 challenge, featuring various rooms, buttons, and landmarks.

The training data consisted of 714 annotated referring expressions from human-to-human interactions. "Successfulness" was quantitatively defined as the ratio of distance traveled to time elapsed ($\Delta S / \Delta T$), representing the speed of resolution. The final evaluation took place during the GIVE-2.5 Challenge, involving real-time interactions with human users in virtual tasks.

Key Results

The mSCRISP system was compared against a purely statistical baseline (MaxEnt) and a purely symbolic baseline (EqualCosts).

Comparison of referring expressions generated by humans and different system configurations.
  • Referential Success: mSCRISP achieved a 95% resolution success rate in task-based evaluations, significantly outperforming the symbolic baseline's 86%.
  • Resolution Speed: For instructions resolved on the first attempt, mSCRISP’s expressions led to faster identification than those of the baselines.
  • Strategic Redundancy: Unlike traditional systems that strive for brevity, mSCRISP learned that "redundant" information (e.g., "the red button on the left" when only one red button exists) can significantly reduce a listener's cognitive load and improve performance.

Conclusion

The success of mSCRISP demonstrates that AI systems should not merely aim to mimic average human behavior. Instead, by combining the logical rigor of symbolic planning with statistical models of communicative success, NLG systems can become "super-human" communicators—prioritizing clarity and utility to help users navigate complex tasks more efficiently. Future work will look to extend this success-based approach to longer navigation discourses and more diverse environmental layouts.

Summary updated

BibTeX
@inproceedings{garoufi2011combining,
  author = {Konstantina Garoufi and Alexander Koller},
  title = {{Combining symbolic and corpus-based approaches for the generation of successful referring expressions}},
  booktitle = {ENLG},
  year = {2011},
  url = {https://openreview.net/forum?id=xaWEH6YrT8},
}
Figure