TL;DR
This paper introduces a new, computationally efficient algorithm for generating referring expressions (like "the small black dog") that aims to be more aligned with human language use than previous methods. By prioritizing human perception and reducing unnecessary complexity, the algorithm produces more practical and natural-sounding descriptions for natural language generation systems.
What Problem Does This Paper Address?
Generating natural-sounding descriptions for objects in a given context is a fundamental task in natural language generation (NLG). Previous algorithms for creating referring expressions, while aiming for accuracy, often focused too heavily on minimizing the length of the expression (efficiency) and sometimes produced descriptions that humans wouldn't naturally use. This could lead to misunderstandings or convey unintended implications. The authors observed that human speakers, in contrast, prioritize making sure their descriptions are easily understood by the listener (sensitivity), even if it means using slightly longer or more redundant phrases. This paper addresses the gap between computationally optimal but unnatural descriptions and human-like, perceptually-driven descriptions.
Methods
The core of the paper is a new algorithm for generating referring expressions. It's designed to be:
- Fast: Its runtime is linear with respect to the number of "distractors" (other objects in the context that the description needs to differentiate from) and independent of the total number of possible descriptive attributes.
- Sensitive to Human Preferences: It prioritizes attributes and values that humans find easy to perceive, such as basic-level categories (e.g., "dog" over "animal") and common attributes like size, shape, and color.
- Domain-Independent: The algorithm itself is general, relying on a knowledge base and user model that can be adapted to different domains.
The algorithm works by iterating through a pre-defined list of "preferred attributes" (e.g., type, color, size). For each attribute, it checks if using a specific value for that attribute can rule out at least one distractor. If it can, the attribute-value pair is added to the referring expression. This process continues until all distractors are ruled out. Crucially, the algorithm does not backtrack; once an attribute-value pair is added, it's not removed, even if later additions make it redundant. A "type" attribute (like "dog") is always included.
The algorithm relies on several assumptions about the knowledge base: entities are described by attribute-value pairs, there's a taxonomy of attribute values, and a way to determine "basic-level" values for users. It also requires specific interface functions to query attribute values, navigate taxonomies, and check user knowledge.
Datasets
Not discussed in the paper. The authors mention using a transcript of a dialogue between two humans performing an assembly task to inform their analysis of human preferences, but this is not presented as a formal dataset for training or evaluation.
Key Insights and Ideas
- Sensitivity over Efficiency: The paper strongly advocates for prioritizing how easily a listener can understand a description (sensitivity) over minimizing its length (efficiency). This is a significant departure from some prior work.
- The Role of "Preferred Attributes": The concept of a domain-specific, ordered list of attributes that humans naturally prefer is central. This list guides the generation process and makes it more human-like.
- Incremental Generation without Backtracking: The algorithm's design to add attribute-value pairs incrementally without backtracking simplifies the process and contributes to its speed. While this might lead to some redundancy, the authors argue it's a reasonable trade-off for efficiency and psychological plausibility.
- Basic-Level Categories are Key: The emphasis on using basic-level attribute values (e.g., "dog" instead of "mammal") aligns with psychological findings about human categorization and perception.
- Distinguishing Navigation from Discrimination: The authors highlight that referring expressions can serve two purposes: navigating the listener's attention to the object and discriminating it from others. This paper focuses on the latter but acknowledges the importance of the former for future work.
Key Results
The paper presents a new algorithm that is:
- Computationally Efficient: The algorithm runs in linear time with respect to the number of distractors, which is a significant improvement over previous algorithms that had more complex optimization requirements.
- Practical for NLG Systems: The algorithm has been implemented in the IDAS natural-language generation system and is performing satisfactorily. It generates referring expressions that are typically short (head noun plus zero to two modifiers).
- Aligned with Human Preferences: Through the use of preferred attributes and basic-level values, the generated expressions are more likely to be easily processed by human hearers.
Limitations and Future Work
- Navigation: The current algorithm assumes the intended referent is already in the listener's focus of attention. Future work will address how to generate expressions that also help the listener locate or attend to the object (navigational information).
- Relative vs. Absolute Attribute Values: The paper notes that human speakers often prefer relative attribute values (e.g., "small") over absolute ones (e.g., "one-inch"). While the knowledge base might store absolute values, the generation algorithm needs to intelligently convert them to relative ones based on the context. This is an area for further research.
- Robustness for Complex Cases: While the algorithm is good at generating simple, common referring expressions, the authors acknowledge that optimal handling of more complex cases is less critical but still desirable.
- User Model Sophistication: The
user-knowsfunction is currently simplified. More sophisticated models of user knowledge and perception could further improve the generated expressions.
Summary updated