Abstract
This paper presents a tree-to-tree transduction method for text rewriting. Our model is based on synchronous tree substitution grammar, a formalism that allows local distortion of the tree topology and can thus naturally capture structural mismatches. We describe an algorithm for decoding in this framework and show how the model can be trained discriminatively within a large margin framework. Experimental results on sentence compression bring significant improvements over a state-of-the-art model.
Introduction: Beyond Word Deletion
Sentence compression is the task of shortening a sentence while retaining its core meaning and remaining grammatical. Historically, many models treated this as a simple "word deletion" problem. However, human-written compressions often involve more complex operations: reordering words, substituting phrases, or changing the syntactic structure entirely.
Existing models often struggled with two primary issues:
- Non-isomorphism: The assumption that the "tree" structure of the short sentence must perfectly match a subset of the long sentence’s tree.
- Grammaticality: Models that delete words without considering the underlying syntax often produce "word salad" that is difficult for humans to read.
The authors aim to build a text-to-text rewriting system that isn't application-specific and can learn complex, non-isomorphic transformations from a parallel corpus of examples.
Methodology: STSG and Large Margin Training
The proposed framework consists of three main components:
Synchronous Tree Substitution Grammar (STSG): Unlike standard context-free grammars that generate one string, synchronous grammars generate two strings (source and target) simultaneously. STSG is particularly powerful because it uses "elementary trees" (fragments of syntax) rather than just single rules, allowing it to capture local context and structural mismatches more naturally.
Large Margin Training (Structured SVM): The model is trained using a discriminative framework. Instead of just trying to "predict the next word," the model learns to maximize the "margin" (the gap) between the correct compression and all other possible (incorrect) compressions. This allows the authors to incorporate a wide variety of features—syntactic, lexical, and task-specific.
Custom Loss Functions: To prevent the model from becoming "too short" or "too long," they introduced brevity penalties (inspired by the BLEU metric used in translation). They found that a "two-sided" brevity penalty (BP2) was most effective at balancing information retention with compression.
The model was evaluated on two distinct datasets: the Ziff-Davis Corpus (computer-related news) and the Broadcast News Corpus (manually compressed broadcast news stories). The latter is particularly challenging due to speech artifacts and incomplete sentences.
Key Insights: The Importance of Structure and Tuning
- Trees over Strings: By operating on tree structures rather than flat strings of words, the model is much better at preserving the "grammaticality" of the output. Transforming a tree into another valid tree ensures the resulting sentence is far more likely to make sense.
- The Power of STSG: The authors demonstrate that STSG is superior for rewriting tasks because it doesn't require the source and target to be structural mirrors of each other. It can handle "structural divergences" where a concept is expressed differently in the compressed version.
- Brevity Matters: A key finding is how different loss functions affect the compression rate. Without a specific penalty for being too short, discriminative models tend to over-compress, losing vital information.
Key Results
The STSG model significantly outperformed the previous state-of-the-art discriminative model (McDonald, 2006):
- Automated Metrics: On the Broadcast News corpus, the STSG model achieved a RelF1 score of 53.4, compared to 47.6 for the baseline.
- Human Evaluation: Volunteers rated the outputs on a 5-point scale for both "information retained" and "grammaticality." On Ziff-Davis, STSG scored 3.20 (vs. 2.82 for the baseline), and on Broadcast News, it scored 2.63 (vs. 2.16).
- Qualitative Success: The model proved capable of leaving sentences uncompressed if they were already short, a feat many previous models struggled with.
Conclusion and Future Work
While the STSG framework shows great promise, there are areas for improvement. Current limitations include a reliance on relatively simple feature engineering and a fixed compression rate learned from training data. Future work could explore incorporating more complex dependency features or allowing users to specify a desired compression rate on-the-fly. Additionally, exploring unsupervised grammar induction could reduce the dependency on high-quality parallel corpora. Ultimately, this framework serves as a general-purpose "rewriting engine" applicable to machine translation or paraphrase generation.
Summary updated