Source-linked AI summary
Sentence Compression as Tree Transduction
Trevor Anthony Cohn, Mirella Lapata
TL;DR
Sentence compression requires models that can represent structural rewrites beyond simple deletion. The paper uses synchronous tree-substitution grammar with discriminative large-margin learning and specialized decoding, achieving superior results to a state-of-the-art system in most tested cases.
Problem
Word-deletion compression remains challenging because producing the target requires sequences of structured rewrite operations.
Method
The paper uses a synchronous tree-substitution grammar with weighted rules, discriminative large-margin training, and a specialized algorithm for training and decoding.
Results
Across the CLspoken, CLwritten, and Ziff-Davis corpora, the model outperforms the state-of-the-art system in most cases.
Takeaways & Limitations
The framework can capture reordering, non-terminal changes, and lexical substitution, and can be ported to other rewriting tasks.
Takeaways & Limitations
Decoding has asymptotic time complexity O(SR|T_T|^(2(n−1)V)), making complexity grow with the target lexicon size and number of variables.
Abstract
from arXiv · showhide
This paper presents a tree-to-tree transduction method for sentence compression. 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.
1. Introduction
Sentence compression remains difficult despite restricting the task to word deletion, because systems must perform structured rewrite operations to produce grammatical shorter sentences. The paper proposes a synchronous tree-substitution grammar with discriminative large-margin learning and specialized training and decoding algorithms.
- 1. Introduction: Word-deletion compression remains challenging because systems must apply sequences of rewrite rules to obtain grammatical target sentences.The examples require deleting terminals or subtrees and merging remaining structures.
- 1. Introduction: The model formulates compression as tree-to-tree rewriting with synchronous tree-substitution grammar, which represents non-isomorphic source and target structures.The formalism is presented as suitable for structural mismatches in rewriting.
- 1. Introduction: The framework learns a weighted transducer discriminatively using a large-margin algorithm and supports both parameter learning and decoding.The paper develops an algorithm for finding the most plausible compression under the learned model.
- 1. Introduction: The approach is designed to extend beyond sentence compression to other tasks involving structural rewriting.The authors state that the framework may be relevant to additional rewriting tasks.
2. Related Work
Prior compression systems use generative or discriminative models, but restricted synchronous context-free grammars cannot represent some structurally complicated compressions. This work uses STSG to model deeper, non-isomorphic tree transformations while retaining discriminative training and adaptable loss functions.
- 2. Related Work: Earlier generative systems estimate rewrite-rule probabilities from parsed parallel corpora and search over possible compressions.These approaches model the joint or channel-based probability of source and target sentences.
- 2. Related Work: SCFG-based compression is limited because its rules cannot represent some structurally complicated transformations, including the deeper tree pairs illustrated in the paper.The cited work identifies depth-one restrictions as the source of this limitation.
- 2. Related Work: STSG permits arbitrary-depth, non-isomorphic tree pairs and therefore represents local syntactic modifications such as dropping phrases or changing passive verbs to active form.Its tree rules are more general than the SCFG rules discussed in the related work.
- 2. Related Work: The proposed discriminative framework supports configurable loss functions, allowing adaptation to rewriting tasks beyond sentence compression.The loss can describe how a predicted target tree differs from a reference tree.
- 2. Related Work: Discriminative alternatives model compression through subtree deletion or features over compression bigrams, parse trees, dependencies, and parts of speech.These models do not explicitly use a synchronous grammar in the cited bigram-based approach.
3. Problem Formulation
The paper formulates sentence compression as tree-to-tree rewriting with a weighted STSG and discriminative large-margin training. It defines grammar induction, chart-based decoding, derivation scoring, and loss functions for selecting compressed target trees.
- 3.1 Synchronous Grammar: STSG transduces a given source tree into target trees by recursively rewriting aligned source and target nodes with synchronous productions.The formalism supports elementary trees of arbitrary depth, unlike SCFG, and uses aligned frontier variables for recursion.
- 3.1 Synchronous Grammar: The transductive algorithm initializes source and target roots, applies matching productions, and recursively processes aligned child-node pairs until both trees are complete.The procedure maintains a frontier stack of aligned nodes and expands each pair using a rule whose source side matches the source tree.
- 3.2 Grammar: The induced grammar may fail to cover unseen trees, so additional rules are needed when unseen fragments or child sequences cannot be matched.This is an explicit coverage limitation of grammar induction on unseen source structures.
- 3.3 Linear Model: Because one target tree can have multiple derivations, the model scores derivations rather than aggregating all derivations, preserving polynomial-time inference.The scoring function combines rule features with target-yield ngram features, allowing local coherence to influence decisions.
- 3.4 Decoding: Chart decoding stores the best partial target tree for each source node and target root category while retaining boundary context for ngram-feature evaluation.Back-pointers recover the maximizing rule and child chart entries.
- 3.4 Decoding: Exact decoding has complexity O(SR|TT|2(n−1)V), making it infeasible when the target lexicon, ngram order, or number of variables is large.The bound arises from enumerating combinations of child chart entries with different ngram contexts.
- 3.5 Training: Large-margin training uses slack variables to trade off margin maximization against training errors, while loss functions can target tokens, ngrams, or CFG productions.The paper also selects a maximum-rule gold derivation to address spurious ambiguity during training; edit-distance losses have exponentially sized argument spaces.
4. Features
The model uses rule-level and target-output features to score synchronous grammar derivations, including structural identity, length, yield, and rule-source information. Coverage rules address unseen source structures, but using the same training set for extraction and estimation biases the model against them.
- Feature design: Features combine grammar-rule properties with target n-gram information, including a trigram language-model feature.Rule features are defined over source trees and target derivations; the language model was trained on the BNC using modified Kneser-Ney smoothing.
- Rule features: Rule-source features distinguish extracted, copy, and delete rules so the model can learn preferences among grammar-rule types.The Type feature records whether a rule came from training extraction or was created as a copy or delete rule.
- Structural and length features: Root, rule-count, word-count, yield, and length features capture tree categories, derivation size, output and source terminal counts, terminal correspondence, and frontier-length differences.Word counts can derive the number of deleted terminals, while yield features compare source and target terminal and frontier non-terminal sequences.
- Rule features: Identity features represent source and target elementary trees, complete rules, and whether the source and target trees are identical.The templates also support features shared by rules or by rules with the same elementary tree.
- Coverage rules and limitation: Coverage rules are dispreferred because grammar extraction and parameter estimation reuse the same training set, although separate-corpus extraction could make them useful for training and testing.Separate extraction may make some training target trees unreachable, so the bias and its remedies remain an open research problem.
5. Experimental Set-up
The experiments evaluate the tree-based compression model across three corpora, against a discriminative string-based baseline, using human judgments and grammatical-relation F1. The corpora differ in domain, genre, compression requirements, and sentence quality, creating varied evaluation challenges.
- 5.1 Corpora: The system was evaluated on three publicly available corpora: Ziff-Davis, CLwritten, and CLspoken.Ziff-Davis was automatically constructed from news articles and abstracts, while CLwritten and CLspoken were manually created from written and broadcast news, respectively.
- 5.1 Corpora: The corpora vary in domain, genre, compression requirements, and sentence characteristics, including disfluencies and incomplete utterances in CLspoken.Ziff-Davis is more aggressively compressed, CLspoken may contain sentences that should remain uncompressed, and CLwritten has longer sentences that may be harder to parse.
- 5.1 Corpora: The model can represent reordering and substitution, but deletion-only training data means the learned rules encode deletion, insertion, and tree restructuring rather than those additional edits.The authors note that broader rewriting requires an appropriate training set and cite adaptation to abstractive compression as evidence of this capability.
- 5.2 Comparison with State-of-the-Art: McDonald’s discriminative model provides the comparison baseline, differing mainly because it performs compression on strings while treating syntax trees only as feature sources.The paper’s model instead makes the syntax tree integral to compression.
- 5.3 Evaluation: Evaluation combines human ratings of information preservation and grammaticality with F1 over directed, labeled grammatical relations.Thirty self-reported native English speakers supplied the human ratings through Internet-based experiments.
6. Results
The results examine model selection, grammar design, feature groups, derivation choice, and tree quality. They show that the full feature set performs best overall, while direct tree evaluation improves relation F1 over reparsed string output and source-tree errors can sometimes be recovered from.
- 6.1 Model Selection: The model sometimes recovered from source-tree errors by deleting or preserving erroneous structures, and less commonly by correcting them with tree transformation rules.Most recoveries yielded acceptable strings even when the resulting output trees remained poor.
- 6.1 Model Selection: Hamming loss over tokens achieved the best mean human rating, 3.38, among the tested loss functions.Edit distance followed closely with a mean rating of 3.30, while differences were small and standard deviations were high.
- 6.2 Grammar and Derivation Analysis: Grammar size grows exponentially with specification depth, so only small recursion depths are practical.The experiments compared specialized rules with recursion limits of one and two against maximally general rules.
- 6.2 Grammar and Derivation Analysis: Twelve percent of maximally general rules had deeper structure not licensed by an SCFG, while another 13% changed syntactic category.These patterns reflect structural divergences between source and target syntax trees.
- 6.1 Model Selection: The full feature set outperformed both ablation sets on all reported criteria and achieved a better compression rate.Token-only features tended to compress less and generalized poorly to unseen data because they were highly lexicalized.
- 6.1 Model Selection: Directly extracting dependency relations from predicted trees increased relation F1 by 2.50% to 4.15% absolute across all tasks compared with reparsing string output.This indicates that the predicted tree output encodes syntactic dependencies more accurately than the parse obtained after converting the output to a string.
7. Model Comparison
The tree transducer outperforms prior systems on several corpora and remains competitive when compression rates are matched. Human judgments likewise favor it on CLspoken and CLwritten, while differences disappear on Ziff-Davis.
- Automatic evaluation: The model outperforms McDonald’s original and improved ILP-based systems on CLspoken, CLwritten, and Ziff Davis.Table 6 reports compression rates and relations-based F1 for all systems.
- Human evaluation: On CLspoken and CLwritten, participants rate the Transducer significantly better than McDonald for both grammaticality and importance.The comparison uses post-hoc Tukey tests after an ANOVA over system type.
- Human evaluation: On Ziff-Davis, Transducer and McDonald receive similar grammaticality and importance ratings, with no significant difference.The paper characterizes Ziff-Davis as less challenging and less likely to highlight system differences.
- Model behavior: The supervised model fits the training corpus’s compression rate but cannot easily adapt to a user-specified rate.The paper notes that loss functions and length-stratified decoding can indirectly control compression rate.
8. Conclusions
The paper formulates compression as tree-to-tree rewriting with a weighted synchronous tree substitution grammar and discriminative large-margin learning. Experiments show mostly superior results to state-of-the-art systems, while future work targets broader rewriting tasks and richer loss functions.
- Conclusions: Sentence compression is formulated as a tree-to-tree rewriting task rather than a deletion-only process.The framework licenses structural rewrite operations through synchronous grammar rules.
- Conclusions: A tree substitution grammar licenses possible rewrites, while rule weights are learned discriminatively in a large-margin model.A specialized algorithm learns the weights and finds the highest-scoring compression.
- Conclusions: The synchronous grammar captures reordering, non-terminal changes, and lexical substitution, enabling adaptation beyond sentence compression.The paper describes the framework as portable to other rewriting tasks without new decoding or training algorithms.
- Conclusions: Across CLspoken, CLwritten, and Ziff-Davis, the model yields results superior to state-of-the-art in most cases.The experiments also examine grammar complexity, loss functions, features, and generated tree quality.
- Future directions: The experiments use grammars acquired from training corpora, while future work considers other grammar sources, richer features, and linguistically informed loss functions.Proposed extensions include document summarization, machine translation, parse-tree losses, and semantic-similarity losses.