Abstract: Jun Sun, Min Zhang, Chew Lim Tan. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP.
2009.
Introduction
Statistical Machine Translation (SMT) has long navigated a trade-off between phrase-based and syntax-based models. While phrase-based models excel at capturing local word groupings, they often struggle with global reordering and discontinuous phrases—such as the English "call him up" or the Chinese equivalent of "at some time." Conversely, syntax-based models utilize grammatical structures to manage reordering but are frequently constrained by "contiguous translational equivalence." This rigid requirement forces models to learn rules only from perfectly adjacent tree fragments, leading to data sparseness and a failure to generalize when irrelevant words appear within a syntactic structure.
This paper introduces a novel translation model that utilizes non-contiguous tree sequences. By allowing syntactic sub-trees to be separated by "gaps," the model can capture essential structural relationships while ignoring intervening, non-essential context.
Methodology: SncTSSG and Pisces
The authors propose the Synchronous non-contiguous Tree Sequence Substitution Grammar (SncTSSG). Unlike standard models that operate on single trees or contiguous sequences, SncTSSG allows for sequences of sub-trees separated by gaps (denoted as <***>). This flexibility enables the model to bridge the gap between rigid syntax and the fluid nature of natural language reordering.
Rule Extraction
To manage the potential explosion of noisy rules, the authors implement a "one-side-only" constraint. Translation rules are extracted only if at most one side (either source or target) is non-contiguous. This constraint maintains semantic cohesion while providing the necessary structural flexibility to handle complex reorderings.
The Pisces Decoder
Standard CYK parsing algorithms cannot natively handle these gaps. To address this, the authors developed the Pisces decoder, which operates in three phases:
- Phase 1: Processing standard contiguous rules.
- Phase 2 (Source Gap Insertion): Handling rules where the source side contains a gap.
- Phase 3 (Target Tree Sequence Reordering): Managing rules with target-side gaps, allowing for flexible reordering of translated components.
Experimental Evaluation
The model was evaluated on a Chinese-to-English translation task using the FBIS corpus for training (approx. 7.2M Chinese words) and the NIST MT-2005 set for evaluation. Syntactic analysis was performed using the Stanford parser, with word alignments generated via GIZA++.
The SncTSSG model demonstrated statistically significant improvements over both phrase-based and contiguous syntax-based baselines:
| Model | BLEU Score |
|---|---|
| Moses (Phrase-based) | 23.86 |
| STSSG (Contiguous Syntax-based) | 25.92 |
| SncTSSG (Proposed Model) | 26.53 |
Key Insights
- Contextual Flexibility: The primary advantage of non-contiguous rules is their ability to ignore irrelevant context within gaps. This allows the model to capture the core syntactic relationship between parts that match, which is often lost in contiguous models due to "richer context" (extra words) appearing in the middle of a phrase.
- Asymmetric Gaps: Research indicated that gaps are more effective on the Chinese side for Chinese-to-English translation. This suggests that Chinese syntax often embeds "filler" information within structures that translate to more compact English phrases.
- Cohesion via Constraints: By limiting gaps to one side of a rule, the authors successfully mitigated the rule redundancy issues that hindered previous non-contiguous modeling attempts.
Conclusion and Future Work
While SncTSSG significantly improves translation quality, it remains sensitive to initial word alignment errors and increases computational complexity during decoding. Furthermore, despite constraints, the model still generates a large volume of rules. Future research will focus on optimizing rule pruning and refining the decoding algorithm to better handle increasingly complex linguistic phenomena.
Summary updated