Abstract
Sentence compression aims to reduce the length of a sentence while preserving its core meaning and grammatical integrity. Traditional models often rely on local, word-by-word decisions, which can lead to ungrammatical outputs. This paper introduces a global optimization approach using Integer Linear Programming (ILP). By incorporating linguistic constraints into the optimization objective, the proposed framework ensures that compressed sentences maintain structural coherence, significantly outperforming previous state-of-the-art models.
Introduction
Most early sentence compression models relied on local information, such as trigram language models, to decide which words to delete. However, sentence structure is hierarchical, and local decisions often fail to capture long-range dependencies. For instance, deleting a head noun while retaining its modifier results in gibberish. To address this, Clarke and Lapata (2008) propose a global inference method that treats sentence compression as an optimization problem over the entire sentence structure.
The ILP Framework
The core innovation is the use of Integer Linear Programming (ILP). Unlike standard Linear Programming (LP), which allows for continuous solutions within a feasible region, ILP restricts variables to integer values—typically 0 or 1 in this context, representing whether a word is kept or deleted.
The authors recast three modeling paradigms into this framework:
- Unsupervised (Language Model): A trigram model prioritizing common sequences.
- Semi-supervised (Significance Model): Combines the language model with a "significance score" based on word frequency and syntactic depth.
- Supervised (Discriminative Model): A feature-rich model trained on parallel corpora.
Linguistic Constraints
The ILP approach allows for the direct encoding of linguistic knowledge as linear inequalities. These "hard" constraints prevent the model from making common grammatical errors by defining the boundaries of the feasible solution space.
Key constraints include:
- Modifier Constraints: If a modifier (adjective/determiner) is kept, its head noun must also be kept.
- Argument Structure: If a verb is retained, its subject and object should ideally be retained as well.
- Sentential Constraints: Function words like prepositions must be kept if their associated phrases are kept.
- Discourse/Personal Pronouns: Personal pronouns are always retained to ensure coherence.
Experimental Results
The models were evaluated on both written (British National Corpus) and spoken (HUB-4 Broadcast News) datasets. The impact of the constraints was significant across the board. On the written corpus, the semi-supervised model's F-score for grammatical relations jumped from 23.3 to 40.5 just by adding constraints. Human evaluations also saw a significant boost, with grammaticality scores rising from 2.25 to 3.47 on a 5-point scale.
One of the most surprising findings was that adding constraints to a simple, semi-supervised model made it perform nearly as well as a complex, fully supervised model. This suggests that encoding linguistic knowledge directly can be more efficient than trying to learn it from massive amounts of data.
Conclusion
By moving from local to global inference via ILP, Clarke and Lapata demonstrated that structural linguistic knowledge can be effectively integrated into statistical models. While the current approach treats sentences in isolation and relies on the accuracy of external parsers, it provides a robust foundation for future work in document-level compression and discourse-aware NLP.
Summary updated