Abstract
Yang Liu, Qun Liu, Yajuan Lü. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies.
2011.
1. Introduction
Most syntax-based machine translation (MT) models rely on Synchronous Context-Free Grammars (SCFG) or Tree Substitution Grammars (TSG). While these are mathematically clean, they have a limited "domain of locality," struggling to model natural language features like "inside-out" stacking of clauses or long-distance dependencies. Tree Adjoining Grammar (TAG) offers a more powerful alternative by allowing "adjoining" operations—inserting one tree structure into the middle of another. However, full Synchronous TAG is computationally expensive, with bilingual parsing requiring $O(n^{12})$ time. This paper introduces a tree-to-string STAG framework that harnesses TAG's expressive power while maintaining computational tractability.
2. The STAG Framework
The authors propose a tree-to-string STAG framework where the input is a fixed source tree. This simplifies the decoding process from bilingual parsing to tree parsing, significantly reducing complexity.
2.1 Rule Categories
The grammar consists of three primary categories of rules, as illustrated in Figure 1:
- Substitution rules (e.g., $\alpha_1, \alpha_2$): Standard tree-to-string rules where a non-terminal is replaced by a tree.
- Adjoining rules: Initial trees with "adjoining sites" where other trees can be inserted.
- Auxiliary rules (e.g., $\beta_1, \beta_2$): Trees that are inserted into adjoining sites of other trees.
3. Rule Extraction and Decoding
A key technical contribution is the extension of the GHKM algorithm to extract STAG rules directly from word-aligned, parsed parallel corpora. Crucially, this is done without needing to reconstruct explicit TAG derivations first. The decoding pipeline involves three stages:
- Matching: Finding STAG rules that fit the input source tree.
- Conversion: Transforming the TAG derivation forest into a standard translation forest by composing rules on the fly.
- Intersection: Integrating a language model using cube pruning to find the optimal translation.
4. Key Insights: The Power of Discontinuity
STAG's primary advantage is its ability to handle "discontinuous" source and target phrases. An initial rule can have a "hole" (an adjoining site) where an auxiliary tree is inserted. This allows the model to handle linguistic structures that are "wrapped" around each other, a common feature in complex recursive predicates like Verb Phrases (VP). By treating the source side as a fixed tree, the authors sidestep the $O(n^{12})$ complexity of full synchronous TAG.
5. Experimental Results
The model was evaluated on a large-scale Chinese-to-English translation task using 1.5 million sentence pairs. The STAG system consistently outperformed the Synchronous Tree Substitution Grammar (STSG) baseline, achieving an average improvement of +0.7 BLEU points across NIST test sets.
Despite the increased complexity of the grammar, the STAG decoder was only 1.6 times slower than the baseline (1.763s vs 1.044s per sentence). This demonstrates that the increased expressive power does not necessitate an exponential computational hit, making STAG a viable option for real-world MT.
6. Conclusion
By moving from tree substitution to tree adjoining in a tree-to-string framework, the authors successfully capture complex syntactic dependencies that standard models miss. Future work includes extending this to tree-to-tree translation and incorporating linguistic heuristics to further refine rule extraction.
Summary of "Adjoining Tree-to-String Translation" by Yang Liu, Qun Liu, and Yajuan Lü (ACL 2011).
Summary updated