Integrated sentence generation using charts

Alexander Koller, Nikos Engonopoulos

Abstract

Traditional Natural Language Generation (NLG) systems often separate sentence planning from surface realization, leading to inefficiencies and potential failures in generating contextually appropriate sentences. This paper describes a novel chart-based algorithm that integrates these two stages into a single, efficient process using Semantically Interpreted Grammars (SIGs). By employing structure-sharing and a heuristic pruning strategy, the proposed method generates high-quality, succinct sentences significantly faster than existing search-based approaches, reducing generation time from 50ms to 13ms in complex virtual environment scenarios.

Introduction

In classical Natural Language Generation (NLG), systems typically follow a pipeline architecture: first, a "sentence planner" decides which properties to use to describe an object (e.g., "the white rabbit"), and then a "surface realizer" turns those decisions into a grammatical string. However, this separation often results in a lack of coordination. A planner might choose a description that is grammatically impossible to realize, or it might fail to exploit "textual economy"—the ability to use sentence context to shorten descriptions. For instance, in the command "Take the rabbit from the hat," the adjective "white" is redundant if only one rabbit is currently in a hat.

While integrated solutions like SPUD and CRISP attempt to bridge this gap, they rely on search-based algorithms that can be computationally expensive or "incomplete," potentially failing to find a valid sentence even when one exists.

Methodology

The core of the proposed approach is a chart-based algorithm built upon Semantically Interpreted Grammars (SIGs). SIGs provide a formal framework for linking syntactic structures with their semantic interpretations.

Structure of Semantically Interpreted Grammars (SIGs) linking syntax and semantics.

In parsing, chart-based methods are favored for their efficiency through structure sharing—storing intermediate results to avoid redundant computations. The authors adapt this logic to generation. The algorithm constructs a chart where each entry (item) tracks three essential components: the syntactic category (nonterminal), the referent ($R$) in the world, and the semantic content ($N$) communicated by the phrase.

Example of chart items generated during the integrated realization process.

To maintain efficiency, a pruning strategy is implemented. Given that integrated generation is NP-complete, the algorithm avoids building the entire chart. Instead, it uses a heuristic to estimate the "distance" from a partial phrase to a complete, valid sentence, prioritizing the most promising paths. This "map" is created by first computing a simplified chart that ignores semantic content to calculate distances to the goal.

Experimental Setup

The algorithm was evaluated using the GIVE Challenge (Generating Instructions in Virtual Environments) dataset. This benchmark requires systems to provide real-time navigation and interaction instructions to human players in a 3D world (e.g., "Push the button to the left of the flower").

Results and Discussion

The chart-based system was compared against CRISP, a prominent search-based integrated generator. Key findings include:

  • Efficiency: In the most complex GIVE challenge scenes, the chart-based system generated sentences in 13 ms, compared to 50 ms for CRISP.
  • Robustness: Unlike greedy search methods like SPUD, this approach is more robust, ensuring that a valid realization is found if the grammar permits it.
  • Mutual Constraints: The algorithm effectively handles inter-dependencies between verbs and noun phrases. It recognizes when a verb phrase's context satisfies the requirement for a unique referent, allowing for more concise noun phrases.
  • Grammar Agnosticism: The modular design allows the algorithm to work with various grammar formalisms, including Context-Free Grammars (CFGs) and Tree-Adjoining Grammars (TAGs).

Conclusion

While the problem of integrated generation remains fundamentally NP-complete, the proposed chart-based algorithm with heuristic pruning proves highly effective in practice. Future work will focus on scaling the approach to larger, more complex grammars and exploring more sophisticated search strategies derived from AI planning to further enhance performance.

Summary updated

BibTeX
@inproceedings{koller2017integrated,
  author = {Alexander Koller and Nikos Engonopoulos},
  title = {{Integrated sentence generation using charts}},
  booktitle = {INLG},
  year = {2017},
  doi = {10.18653/v1/w17-3520},
}
Figure