A Dependency-Based Neural Reordering Model for Statistical Machine Translation

Christian Hadiwinoto, Hwee Tou Ng

Abstract

In machine translation (MT) that involves translating between two languages with significant differences in word order, determining the correct word order of translated words is a major challenge. The dependency parse tree of a source sentence can help to determine the correct word order of the translated words. In this paper, we present a novel reordering approach utilizing a neural network and dependency-based embeddings to predict whether the translations of two source words linked by a dependency relation should remain in the same order or should be swapped in the translated sentence. Experiments on Chinese-to-English translation show that our approach yields a statistically significant improvement of 0.57 BLEU point on benchmark NIST test sets, compared to our prior state-of-the-art statistical MT system that uses sparse dependency-based reordering features.

Introduction

Determining the correct word order is a fundamental challenge in Machine Translation (MT), particularly when translating between languages with divergent syntactic structures, such as Chinese and English. Traditional phrase-based Statistical Machine Translation (SMT) systems typically address this through distance-based penalties or phrase-based lexicalized reordering models.

While source-side dependency parse trees provide valuable structural guidance, previous attempts to integrate them relied heavily on sparse features—manually engineered templates that memorize specific combinations of words, Part-of-Speech (POS) tags, and dependency labels. These models often suffer from data sparsity, failing to generalize when encountering words in novel syntactic contexts. This research proposes a neural network-based reordering model that leverages continuous vector representations (embeddings) to predict reordering decisions, effectively overcoming the limitations of sparse feature sets.

Methodology

The core of the proposed approach consists of two feed-forward neural classifiers designed to predict the relative order of translated words based on their source-side dependency relations:

  1. Head-Child Classifier: Predicts whether a source word and its syntactic head should maintain their relative order or be swapped in the target translation.
  2. Sibling Classifier: Predicts the translation order of two source words that share the same syntactic head.
The neural reordering model architecture and its application to a source dependency tree.

Input Features and Embeddings

The classifiers utilize a variety of features, including the words themselves, their POS tags, dependency labels, the signed distance between words in the source sentence, and indicators for intervening punctuation. Instead of treating these as discrete symbols, the model maps them to continuous embeddings.

A critical innovation is the use of dependency-driven word embeddings. Unlike standard skip-gram models (like Word2Vec) that predict linearly adjacent words, this model is trained to predict a word's syntactic context (its head and children). This ensures that the vector space captures the functional syntactic roles necessary for accurate reordering.

Integration into SMT

The neural classifiers output probabilities for "swap" or "in-order" transitions. These probabilities are integrated directly into the SMT beam search decoder as feature functions within a log-linear model. To enhance robustness, the system employs an ensemble of ten classifiers initialized with different random seeds.

Experimental Evaluation

The model was evaluated on Chinese-to-English translation tasks using approximately 8.8 million sentence pairs from various LDC corpora. The development set comprised MTC v1 and v3, while evaluation was conducted on standard NIST MT sets from 2002 to 2006, and 2008.

Qualitative comparison of translation outputs using different model configurations alongside the source dependency tree.

Results and Insights

The experimental results demonstrate the efficacy of the dependency-based neural approach:

  • Significant BLEU Gains: The 10-classifier ensemble achieved a statistically significant improvement of +0.57 BLEU over a highly optimized baseline that already utilized conventional phrase-based reordering and sparse dependency features. Even a single neural model provided a +0.32 BLEU boost.
  • Superiority over Traditional Models: When traditional phrase-based reordering models (PBRM) were removed, the neural classifier outperformed them by +1.05 BLEU points, suggesting it captures reordering dynamics more effectively than legacy lexicalized models.
  • The Importance of Initialization: A key finding was that initializing the network with random or standard linear embeddings yielded no improvement. The performance gains were entirely dependent on the use of dependency-driven embeddings, highlighting the necessity of capturing syntactic structure in the vector space.
  • SMT vs. Early NMT: At the time of the study (2017), this enhanced SMT system outperformed an in-house end-to-end Neural MT (NMT) system by 0.58 BLEU on NIST benchmarks, while requiring significantly less training time (3 days vs. 18 days).

Conclusion

This work demonstrates that neural networks can effectively bridge the gap between structural dependency parsing and statistical machine translation. By replacing sparse, hand-crafted features with continuous dependency-driven embeddings, the model achieves superior generalization and translation quality. While the field has since shifted toward end-to-end NMT architectures like the Transformer, this research provides lasting insights into the value of injecting explicit syntactic priors into neural NLP systems.

Summary updated

Abstract

In machine translation (MT) that involves translating between two languages with significant differences in word order, determining the correct word order of translated words is a major challenge. The dependency parse tree of a source sentence can help to determine the correct word order of the translated words. In this paper, we present a novel reordering approach utilizing a neural network and dependency-based embeddings to predict whether the translations of two source words linked by a dependency relation should remain in the same order or should be swapped in the translated sentence. Experiments on Chinese-to-English translation show that our approach yields a statistically significant improvement of 0.57 BLEU point on benchmark NIST test sets, compared to our prior state-of-the-art statistical MT system that uses sparse dependency-based reordering features.
BibTeX
@inproceedings{hadiwinoto2017dependency,
  author = {Christian Hadiwinoto and Hwee Tou Ng},
  title = {{A Dependency-Based Neural Reordering Model for Statistical Machine Translation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10499},
}
Figure