Extending Phrase-Based Translation with Dependencies by Using Graphs

Liangyou Li, Andy Way, Qun Liu

Introduction

Traditional Phrase-Based Machine Translation (PBMT) systems generally operate on the assumption that translation units are continuous sequences of words. However, natural language frequently employs discontinuous constructions—where words that function as a single semantic unit are separated by intervening text. Examples include phrasal verbs in English ("set the table up") or negation in French (ne... pas).

While previous attempts to address this have utilized tree-based structures, trees often struggle to capture "non-syntactic" phrases that do not align with formal linguistic branches. This research introduces a novel Graph-Based Machine Translation (GBMT) framework that moves beyond 1D sequences and 2D trees, utilizing a flexible graph representation to capture both linear order and structural dependencies simultaneously.

The Graph-Based Framework

The core innovation of this approach lies in representing source sentences as graphs rather than simple strings.

Graph Construction

For every source sentence, a graph is constructed where nodes represent words. Two distinct types of edges are established:

  1. Bigram relations: These connect adjacent words to preserve the linear sequence of the sentence.
  2. Dependency relations: These connect words based on their grammatical relationships, regardless of their distance in the sentence.
Figure 1: Illustration of a source sentence graph combining linear bigram relations (dotted blue) and syntactic dependency relations (dashed red).

Segmentation and Decoding

Instead of slicing sentences into linear chunks, the GBMT model segments the graph into connected subgraphs. Because these subgraphs can follow dependency edges, they naturally capture discontinuous phrases that are "close" in the graph structure even if they are distant in the linear string. A beam search decoder then translates these subgraphs into target strings from left to right.

To optimize this process, the researchers introduced the Graph Segmentation Model (GSM). This model utilizes sparse features—such as word classes and connectivity direction—to help the system determine the most effective way to partition the graph during translation.

Experimental Evaluation

The framework was evaluated on two major translation tasks using the Moses open-source toolkit:

  • Chinese–English (ZH–EN): Trained on 1.5M+ sentence pairs (LDC corpus) and evaluated on NIST04 and NIST05.
  • German–English (DE–EN): Trained on 2M+ sentence pairs (WMT 2014 corpus) and evaluated on WMT12 and WMT13.

Results and Discussion

The graph-based models (GBMT and GSM) consistently outperformed both standard PBMT and the state-of-the-art discontinuous model (DTU).

Figure 3: Performance comparison (BLEU scores) across Chinese-English and German-English translation tasks, showing significant gains for the GSM model.

Key Findings

  • Improved Accuracy: As shown in the results table, the GSM model achieved a 32.0 BLEU score on the Chinese-English NIST05 task, a notable improvement over the 31.4 achieved by standard PBMT. These gains were statistically significant ($p \leq 0.01$) across nearly all test sets.
  • Structural Efficiency: By requiring subgraphs to be connected via linguistic dependencies, the model effectively filters out "noisy" or accidental word groupings. In the German-English task, GBMT achieved superior results to the DTU model while using only 153 million rules, compared to DTU's 352 million—a reduction of over 50%.
  • The Power of Explicit Segmentation: The performance of the GSM variant highlights that explicitly modeling the segmentation process is crucial for maximizing the utility of graph-based structures.

Conclusion and Future Work

By unifying local context and long-distance dependencies into a single mathematical structure, this graph-based approach provides a more robust solution for translating complex, discontinuous languages. While the model demonstrates clear gains in accuracy and rule efficiency, future research is needed to address the computational complexity of graph segmentation during real-time decoding and to explore the impact of dependency parser reliability on overall translation quality.

Summary updated

Abstract

In this paper, we propose a graph-based translation model which takes advantage of discontinuous phrases. The model segments a graph which combines bigram and dependency relations into subgraphs and produces translations by combining translations of these subgraphs. Experiments on Chinese‐English and German‐English tasks show that our system is significantly better than the phrase-based model. By explicitly modeling the graph segmentation, our system gains further improvement.
BibTeX
@inproceedings{li2016extending,
  author = {Liangyou Li and Andy Way and Qun Liu},
  title = {{Extending Phrase-Based Translation with Dependencies by Using Graphs}},
  booktitle = {SedMT @ NAACL},
  year = {2016},
  doi = {10.18653/v1/w16-0602},
}
Figure