An extractive supervised two-stage method for sentence compression

Dimitrios Galanis, Ion AndroutsopoulosNAACL 2010

TL;DR

This paper introduces a novel two-stage supervised method for sentence compression that automatically learns to shorten sentences by removing words. It achieves state-of-the-art performance by first generating candidate compressions using a Maximum Entropy classifier on dependency trees and then selecting the best one with a Support Vector Machine Regression model, all without requiring manually crafted rules.

What Problem Does This Paper Address?

Sentence compression is the task of creating a shorter, grammatical version of a sentence that retains its most important information. This is crucial for applications like displaying text on small screens, generating subtitles, and text summarization. While many methods exist, the paper focuses on extractive compression, which only removes words, as opposed to abstractive methods that can rephrase or add words. The challenge is to improve the performance of extractive methods, particularly by avoiding the need for hand-engineered rules, which are time-consuming to create and maintain. Existing state-of-the-art methods often rely on such rules or complex parsing machinery.

Methods

The proposed method is a two-stage, supervised approach:

  1. Candidate Generation (Maximum Entropy Classifier):
    • The core idea is to model sentence compression as a decision process on the dependency tree of the source sentence.
  2. For each dependency edge in the tree, a Maximum Entropy (ME) classifier decides whether to retain the edge, delete it along with its head, or delete it along with its modifier.
  3. This stage uses a rich set of features capturing the local context of the edge, including edge labels, POS tags of head and modifier, entire head-label-modifier triples, father's POS tags, surrounding word POS tags, and "signature terms" (words important to the document).
  4. The ME model is trained on parallel corpora of source sentences and their human-authored compressed versions (gold compressions).
  5. This stage generates multiple candidate compressions by exploring different combinations of edge decisions. A pruning threshold is used to limit the number of candidates.
  6. Candidate Ranking (Support Vector Machine Regression):
    • A Support Vector Machine Regression (SVR) model is used to score and rank the candidate compressions generated in the first stage.
  7. The SVR model is trained to predict a score indicating how good a candidate compression is.
  8. It uses a large feature set (98 features) that includes:
  9. Grammaticality scores (based on an n-gram language model).
  10. Importance rate scores (measuring retained information from the original sentence).
  11. Features related to deleted words and their depth in the dependency tree.
  12. Features counting POS tags in the source sentence and how many were deleted.
  13. Two specific SVR configurations are explored: one using an F1-score of dependencies against the gold standard, and another combining token accuracy, grammaticality, and a compression rate penalty.

Datasets

  • Edinburgh's "written" sentence compression corpus: Used for training and evaluation. This corpus consists of source-gold pairs where gold compressions are created by deleting words.
  • The corpus was split into training (1024 pairs), development (324 pairs), and testing (291 pairs) sets.
  • For language modeling and IDF calculations, the paper utilized the TIPSTER corpus (approx. 4.5 million sentences for LM, 19.5 million verbs/nouns for IDF).

Key Insights and Ideas

  • Two-stage "over-generate and select" is effective: The paper demonstrates that generating a diverse set of candidate compressions and then using a sophisticated ranking model is a powerful strategy.
  • Dependency trees as the structural basis: Leveraging dependency trees provides a rich structural representation that allows for more nuanced decisions about what parts of a sentence to remove.
  • ME for pruning, SVR for fine-grained ranking: The complementary strengths of ME (efficiently pruning unlikely decisions) and SVR (learning complex scoring functions from features) are effectively combined.
  • Eliminating hand-crafted rules: A significant contribution is achieving state-of-the-art results without relying on manually written rules, which is a major advantage for scalability and maintainability.
  • Feature engineering is key: The success of both the ME classifier and the SVR ranker hinges on the carefully designed feature sets that capture syntactic, semantic, and statistical properties of the sentences and their compressions.

Key Results

  • The proposed method, particularly the SVR-TOKACC-LM configuration, outperforms the state-of-the-art extractive system T3 (Cohn and Lapata, 2007; 2009) in terms of F1 scores on the test set (53.75% vs. 47.52%).
  • Human evaluations also showed the proposed system performing favorably against T3 across grammaticality, meaning preservation, and overall quality.
  • The SVR-based configurations (SVR-F1 and SVR-TOKACC-LM) significantly outperformed the simpler LM-IMP configuration on the development set.
  • The compression rates achieved by the proposed system were comparable to T3, indicating a good balance between compression and quality.

Limitations and Future Work

  • Limited to extractive compression: The method currently only removes words and does not support more complex transformations like paraphrasing or reordering.
  • Performance with more training data: The authors suggest that using more training examples for the SVR models could further improve performance.
  • Exploring more complex transformations: Future work could involve supporting abstractive transformations.
  • Experimenting with different training data sizes: The impact of varying training data size on performance is an open area.

Summary updated

BibTeX
@inproceedings{galanis2010extractive,
  author = {Dimitrios Galanis and Ion Androutsopoulos},
  title = {{An extractive supervised two-stage method for sentence compression}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure