Abstract
Michel Galley and Kathleen McKeown (2007) present a novel approach to sentence compression using lexicalized head-driven Markovization. By decomposing Synchronous Context-Free Grammar (SCFG) rules into smaller dependencies and utilizing a robust tree-alignment method to unlock 15x more training data, their system produces compressions that are significantly more grammatical and accurate than previous state-of-the-art models.
The Challenge of Context and Data Sparsity
Sentence compression—shortening a sentence while preserving its core meaning—is a critical component for summarization and mobile content delivery. Early models based on Synchronous Context-Free Grammars (SCFG) faced two primary hurdles: data sparsity and a lack of contextual awareness.
Standard SCFG rules are often too "flat" and specific. If a model encounters a word sequence not seen exactly in training, it fails to generalize. Furthermore, these models struggled to distinguish between complements (essential components, e.g., "fell from the chair") and adjuncts (optional modifiers, e.g., "fell because of the rain"). Without identifying the "head" of a phrase, models frequently deleted vital information, leading to ungrammatical outputs.
Methodology: Lexicalized Head-Driven Markovization
To address these issues, the authors introduced Lexicalized Head-Driven Markovization. Instead of treating a grammar production (like $VP \rightarrow VBD\ NP\ PP\ PP$) as an atomic unit, they decompose it by identifying the phrase's "head." Modifiers are then generated independently to the left and right of this head.
- Markovization: This allows the model to estimate probabilities based on smaller, more frequent horizontal (sister nodes) and vertical (parent nodes) contexts. The authors found that "sister annotation" of order 1 ($s=1$) was critical for avoiding dangling punctuation.
- Lexicalization: Grammar nodes are annotated with their actual head words and parts of speech (POS). For example, knowing a prepositional phrase is headed by "from" versus "because" provides the necessary context for the model to decide if the phrase is safe to delete.
Expanding Training Data through Robust Alignment
A significant bottleneck in training compression models is the availability of parallel data. Previous research relied on pairs where the compression was a perfect substring of the original. Galley and McKeown implemented a robust tree alignment algorithm based on minimum edit distance. This allowed them to align trees even when human-written abstracts contained slight rewordings. This innovation expanded their usable training set from the Ziff-Davis corpus by 15-fold (from 1.75% to 25% of the corpus).
Evaluation and Results
The Markovized model was evaluated against the "Noisy Channel" baseline (Knight and Marcu, 2000) using the Ziff-Davis corpus. The results demonstrated substantial improvements across all metrics.
As shown in Figure 4, the Markovized model achieved a word-level classification accuracy of 67.9%, compared to 61.3% for the baseline. Human judges also rated the Markovized output significantly higher for both grammaticality (4.68 vs. 4.37) and content importance (4.22 vs. 3.87), nearing the human gold standard in grammatical quality.
Conclusion
By moving away from rigid, flat grammar rules toward a lexicalized, Markovized framework, Galley and McKeown successfully mitigated the issues of data sparsity and context-insensitivity in sentence compression. Their work highlights the importance of sister-node annotation and bilexicalization in maintaining the syntactic and semantic integrity of compressed text. Future improvements may involve moving to discriminative frameworks to further optimize quality directly.
Summary updated