Abstract
Sentence compression aims to shorten sentences while maintaining grammatical correctness and core meaning. Traditional methods using Context-Free Grammar (CFG) parse tree trimming often suffer from context blindness and structural alignment issues. This paper proposes a Maximum Entropy (MaxEnt) model combined with a novel bottom-up tree-matching technique. By incorporating lexical features and a robust alignment method, the proposed system significantly outperforms baseline models in both automated metrics and human evaluations of grammaticality and importance.
Introduction
Sentence compression is the task of shortening a sentence while ensuring it remains grammatically correct and retains its core meaning. It is a vital component for document summarization, headline generation, and displaying text on small mobile screens.
Historically, the dominant approach (e.g., Knight and Marcu’s noisy-channel model) worked by "trimming" CFG parse trees. However, these models faced two major challenges:
- Context Blindness: Probabilities were often calculated based only on node labels. This led to the deletion of critical words like "not" or "never," which completely flip a sentence's meaning.
- Structural Mismatch: Models struggled to learn from training data when the parse tree of a human-compressed sentence did not align perfectly as a sub-sequence of the original sentence's tree.
Methodology
The researchers introduced two primary innovations to the standard CFG-trimming pipeline to overcome these hurdles.
Maximum Entropy (MaxEnt) Model
Instead of relying on simple rule frequencies, the authors utilized a MaxEnt framework. This allows the model to incorporate a wide array of "features" when deciding whether to trim a node, including node depth, specific lexical content (to catch negative adverbs), and the identity of sibling nodes. This semantic awareness ensures that the logic of the sentence is respected during compression.
Bottom-Up Matching Method
To solve the alignment problem, the authors developed a bottom-up matching technique. Rather than parsing the compressed sentence independently, they take the original sentence's parse tree and "mark" the words that appear in the human-compressed version. They then recursively mark all parent nodes of those words. This creates a "skeleton" tree that represents the compressed sentence within the original structure, allowing the model to learn even from complex, non-linear mappings.
Experimental Results
The study utilized the Ziff-Davis corpus, a standard benchmark containing pairs of long sentences and their human-compressed counterparts.
The proposed method significantly outperformed baseline models across multiple metrics:
- Automated Metrics: It achieved higher F-measures (word-level accuracy) and BLEU scores across all compression ratios.
- Human Evaluation: In blind tests, humans rated the MaxEnt + Bottom-Up method significantly higher for both Grammaticality (4.22 vs. 3.81) and Importance (4.06 vs. 3.38) on a 5-point scale.
- Semantic Integrity: The model was far more successful at retaining the word "not," correctly preserving it in cases where baseline models would have deleted it.
Conclusion
By moving beyond simple syntax and incorporating machine learning with structural awareness, this research demonstrates that sentence compression can be made both more accurate and more meaningful. While the model's independence assumption for trimming decisions can occasionally impact grammaticality in very deep trees, the use of lexical features and the bottom-up matching method provides a robust foundation for future work in automated summarization.
Summary updated