Non-Projective Parsing for Statistical Machine Translation

Xavier Carreras, Michael CollinsEMNLP 2009 · OpenReview

Abstract

We describe a novel approach for syntax-based statistical MT, which builds on a variant of tree adjoining grammar (TAG). Inspired by work in discriminative dependency parsing, the key idea in our approach is to allow highly flexible reordering operations during parsing, in combination with a discriminative model that can condition on rich features of the source-language string. Experiments on translation from German to English show improvements over phrase-based systems, both in terms of BLEU scores and in human evaluations.

Introduction

Machine translation (MT) systems traditionally divide into phrase-based and syntax-based approaches. Phrase-based systems excel at local reordering through high flexibility but often lack global structural coherence, leading to ungrammatical outputs. Conversely, syntax-based systems, typically utilizing Synchronous Context-Free Grammars (SCFG), provide necessary structural constraints but are often too rigid to handle "non-projective" reorderings. These are cases where words from different parts of a sentence interleave or "cross" each other, a common occurrence in language pairs like German and English where verbs may migrate to clause-final positions or arguments may be scrambled.

This paper addresses these limitations by proposing a model that combines the flexibility of phrase-based systems with the structural integrity of syntax-based ones, treating translation as a non-projective parsing problem.

Methodology

The proposed approach is built upon a variant of Tree Adjoining Grammar (TAG), introducing several key technical innovations:

S-Phrases (Syntactic Phrases)

Instead of simple string-to-string mappings, the model utilizes "s-phrases." These pair source-language strings with "treelets"—small fragments of a target-language parse tree, often referred to as spines. This allows the model to associate lexical items directly with their syntactic roles in the target language.

Mapping German phrases to English treelets (s-phrases).

Flexible Adjunction and Reordering

Standard TAG operations are extended to include "sister-adjunction" and "r-adjunction," enabling arbitrary reordering of tree fragments. This flexibility allows the model to "skip" source words and fill them in later, effectively modeling non-projective dependencies that are difficult for standard SCFGs.

Discriminative Dependency Model

To manage the vast search space created by flexible reordering, a discriminative model ($score_R$) is employed. This model calculates the probability of target-language dependencies (e.g., a verb-object relationship) by conditioning on rich features of the source string, including POS tags, word identities, and relative distances.

Structural Constraints

To maintain computational tractability and output quality, the authors introduce the $\pi$-constituent constraint. While intermediate translation steps can be non-contiguous, once a treelet has integrated all its modifiers, the resulting constituent must correspond to a contiguous block of words in the source language. Decoding is performed using a beam search algorithm that tracks source-word coverage via bit-strings.

Experimental Setup

The model was evaluated on the Europarl corpus for German-to-English translation. The training set consisted of 751,088 sentence pairs. Due to the computational complexity of non-projective parsing, the evaluation was restricted to sentences of 30 words or fewer. The system was compared against Pharoah, a standard phrase-based SMT baseline.

Results and Discussion

The syntax-based system outperformed the phrase-based baseline across both automated and human metrics.

  • BLEU Scores: The proposed system achieved a BLEU score of 25.04, representing a 0.46 point improvement over Pharoah (24.58).
  • Human Evaluation: In blind tests, human annotators significantly preferred the syntax-based output (e.g., 73 vs. 42 preferences for one annotator).
A complete target-language parse tree generated by the model.

Ablation Analysis

Ablation studies highlighted the critical components of the system:

  1. Source-Language Context: Removing the discriminative dependency model led to a 1.5 BLEU point drop, confirming that conditioning target syntax on source features is vital.
  2. Structural Constraints: Removing the $\pi$-constituent constraint resulted in a 0.8 BLEU point drop, demonstrating its role in pruning structurally unsound translations.

Conclusion

This research demonstrates that target-language syntax can serve as an effective mechanism for reordering in MT. By allowing treelets to adjoin flexibly while remaining grounded in source-language features, the model achieves superior translation quality. Future work will focus on improving computational efficiency to handle longer sentences and incorporating more complex source-language features, such as grammatical roles and clause boundaries, to further enhance performance.

Summary updated

Abstract

We describe a novel approach for syntax-based statistical MT, which builds on a variant of tree adjoining grammar (TAG). Inspired by work in discriminative dependency parsing, the key idea in our approach is to allow highly flexible reordering operations during parsing, in combination with a discriminative model that can condition on rich features of the source-language string. Experiments on translation from German to English show improvements over phrase-based systems, both in terms of BLEU scores and in human evaluations.
BibTeX
@inproceedings{carreras2009non,
  author = {Xavier Carreras and Michael Collins},
  title = {{Non-Projective Parsing for Statistical Machine Translation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=Bk-myzM_-r},
}
Figure