Overcoming the Lack of Parallel Data in Sentence Compression

Katja Filippova, Yasemin AltunEMNLP 2013 · OpenReview

Abstract

A major challenge in supervised sentence compression is making use of rich feature representations because of very scarce parallel data. We address this problem and present a method to automatically build a compression corpus with hundreds of thousands of instances on which deletion-based algorithms can be trained. In our corpus, the syntactic trees of the compressions are subtrees of their uncompressed counterparts, and hence supervised systems which require a structural alignment between the input and output can be successfully trained. We also extend an existing unsupervised compression method with a learning module. The new system uses structured prediction to learn from lexical, syntactic and other features. An evaluation with human raters shows that the presented data harvesting method indeed produces a parallel corpus of high quality. Also, the supervised system trained on this corpus gets high scores both from human raters and in an automatic evaluation setting, significantly outperforming a strong baseline.

Introduction

Sentence compression—the task of shortening a sentence while preserving its essential meaning—is a foundational component for text summarization and user interface design. While extractive methods, which involve deleting words, are the standard approach, the field has long been split between unsupervised models and supervised ones. Unsupervised models rely on general linguistic rules but often miss the nuances of human-like compression. Conversely, supervised models are potentially more powerful but have been severely limited by the scarcity of parallel training data.

Before this research, the largest available datasets, such as the Ziff-Davis or Edinburgh corpora, contained only about 1,000 to 1,400 pairs. This lack of scale made it impossible to train models on "sparse lexical features"—specific words that signal importance. For instance, a model needs vast examples to learn that a verb like "killed" is typically more salient in a news headline than a verb like "says."

Automated Data Harvesting

To address the data bottleneck, the authors developed a pipeline to automatically harvest 250,000 high-quality parallel sentence-compression pairs from news articles. The core insight is that news headlines often serve as natural compressions of an article's lead sentence. However, because headlines are frequently abstractive (using different wording), they cannot be used directly for extractive training.

The authors employed a subtree matching algorithm to bridge this gap. By analyzing the dependency graph of the lead sentence, they identified the smallest possible subtree that contained the same core entities and content words as the headline. If a valid subtree was found that matched the headline's meaning, it was extracted as a "gold standard" extractive compression.

The transformation and extraction process for generating parallel compression data, showing the source dependency tree (a), the transformed graph (b), the extracted headline tree (c), and the tree with transformations undone (d).

Supervised Learning via Tree Pruning

With this massive new corpus, the authors framed sentence compression as an optimization problem: finding a subset of edges in a dependency tree that maximizes a weight function while adhering to a length limit.

Instead of using hand-crafted weights, they utilized a Structured Perceptron to learn weights for thousands of features. These features moved beyond simple syntax to include:

  • Lexical features: Specific words and their contexts.
  • Structural features: Tree depth, number of children, and position.
  • Semantic features: Named Entity tags (e.g., identifying people or locations).

By enforcing the subtree constraint, the system ensures that the resulting compression remains grammatically grounded and structurally consistent with the original sentence.

Results and Evaluation

The quality of the automatically harvested corpus was validated through human qualitative analysis. Raters found the extractive headlines to be nearly as readable (4.26/5.0) and informative (3.70/5.0) as the original human-written headlines.

In performance benchmarks, the supervised model trained on the 250,000-pair dataset significantly outperformed the unsupervised baseline. Human evaluation gave the supervised model a readability score of 4.30, compared to 3.70 for the baseline. Automatic F1-score testing showed an even wider gap: 84.3 for the supervised model versus 52.3 for the baseline. Crucially, the authors demonstrated that data volume is the primary driver of success; when the training set was restricted to only 10,000 instances, performance dropped significantly.

Conclusion and Future Work

This work demonstrates that the lack of parallel data in sentence compression can be overcome by leveraging news headlines as proxies. By combining a massive, automatically harvested corpus with a supervised learning framework that utilizes rich lexical and structural features, the authors achieved state-of-the-art results.

While the model is highly effective, it tends toward aggressive compression (averaging a 0.46 rate), which may be too lossy for some applications. Additionally, the system's performance is tied to the accuracy of the underlying dependency parser. Future work could explore dynamic length constraints and more robust parsing techniques to further refine the quality of automated sentence compression.

Summary updated

Abstract

A major challenge in supervised sentence compression is making use of rich feature representations because of very scarce parallel data. We address this problem and present a method to automatically build a compression corpus with hundreds of thousands of instances on which deletion-based algorithms can be trained. In our corpus, the syntactic trees of the compressions are subtrees of their uncompressed counterparts, and hence supervised systems which require a structural alignment between the input and output can be successfully trained. We also extend an existing unsupervised compression method with a learning module. The new system uses structured prediction to learn from lexical, syntactic and other features. An evaluation with human raters shows that the presented data harvesting method indeed produces a parallel corpus of high quality. Also, the supervised system trained on this corpus gets high scores both from human raters and in an automatic evaluation setting, significantly outperforming a strong baseline.
BibTeX
@inproceedings{filippova2013overcoming,
  author = {Katja Filippova and Yasemin Altun},
  title = {{Overcoming the Lack of Parallel Data in Sentence Compression}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2013},
  url = {https://openreview.net/forum?id=SkZRJGfubr},
}
Figure