Aggregation via Set Partitioning for Natural Language Generation

Regina Barzilay, Mirella LapataNAACL 2006 · OpenReview

Abstract

The role of aggregation in natural language generation is to combine two or more linguistic structures into a single sentence. This task is crucial for generating concise and readable texts. We present an efficient algorithm for automatically learning aggregation rules from a text and its related database. The algorithm treats aggregation as a set partitioning problem and uses a global inference procedure to find an optimal solution. Our experiments show that this approach yields substantial improvements over a clustering-based model which relies exclusively on local information.

Introduction

In Natural Language Generation (NLG), "aggregation" is the process of combining multiple linguistic structures into a single, fluid sentence. Without effective aggregation, generated text often feels stilted and repetitive. For example, a sports report might state "Player A ran 10 yards. Player A scored a touchdown" instead of the more natural "Player A ran 10 yards for a touchdown."

Traditionally, aggregation rules were hand-crafted by experts, which is time-consuming and difficult to scale to new domains. While some automated methods exist, they often rely on "local" information—looking only at pairs of facts in isolation. This often leads to inconsistent groupings or "run-on" sentences that are too complex for a reader to follow. This paper proposes an automated approach that ensures the final output respects global properties of the document.

Methodology

The proposed model treats semantic grouping as a supervised set partitioning task, executed in two distinct stages:

  1. Local Pairwise Classifier: First, a Maximum Entropy classifier is trained to predict the probability that any two database entries should be aggregated. It identifies shared attributes; for instance, in a football dataset, two entries are likely to be grouped if they share the same player, time, or action type.
  2. Global Inference via Integer Linear Programming (ILP): To ensure these pairwise decisions form a valid and coherent set of sentences, the authors use Integer Linear Programming (ILP). This allows the system to maximize the overall "agreement" of the groupings while enforcing critical constraints such as transitivity and global limits on sentence complexity.

This approach is novel because it allows the system to "look ahead" and ensure that local decisions do not violate broader rules of readable text.

Dataset and Evaluation

The model was evaluated using a corpus of NFL football game summaries. The dataset consists of 468 game summaries containing over 73,400 database entries. Database entries (e.g., "Passing: Cundiff, 237 yards") were automatically aligned with sentences in human-written summaries to create training data.

Example of database entries and their corresponding aggregated sentences in the NFL dataset.

As shown in the data excerpt above, a single sentence often aggregates multiple distinct database facts.

Results

The ILP-based model significantly outperformed a standard greedy clustering baseline across several metrics:

  • F-Score: The ILP model achieved a 70.3% F-score on pairwise assignments, an 11.9% absolute improvement over the clustering baseline (58.4%).
  • Precision: The model showed a massive jump in precision (82.2% vs 57.7%), meaning it made far fewer nonsensical groupings.
  • Scaling with Complexity: The ILP model's advantage becomes even more pronounced as the number of facts per sentence increases.
Accuracy of the ILP model versus the clustering baseline across different partition sizes.

As illustrated in the figure above, the ILP model is much better at correctly identifying complex, multi-fact sentences than simple clustering.

Conclusion

By framing aggregation as a set partitioning problem solved via ILP, this research demonstrates that incorporating global constraints leads to more precise and human-like text generation. Future work includes integrating the local classifier and global inference into a single learning framework and extending the system to handle sentence structuring and word choice.

Summary updated

Abstract

The role of aggregation in natural language generation is to combine two or more linguistic structures into a single sentence. The task is crucial for generating concise and readable texts. We present an efficient algorithm for automatically learning aggregation rules from a text and its related database. The algorithm treats aggregation as a set partitioning problem and uses a global inference procedure to find an optimal solution. Our experiments show that this approach yields substantial improvements over a clustering-based model which relies exclusively on local information.
BibTeX
@inproceedings{barzilay2006aggregation,
  author = {Regina Barzilay and Mirella Lapata},
  title = {{Aggregation via Set Partitioning for Natural Language Generation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
  url = {https://openreview.net/forum?id=BkWjomZdZr},
}
Figure