Deep Syntax Language Models and Statistical Machine Translation

Yvette Graham, Josef van GenabithSSST @ COLING 2010 · OpenReview

Introduction

Traditional Statistical Machine Translation (SMT) relies heavily on string-based language models (LMs) that predict the next word based on a local window of preceding words (n-grams). However, hierarchical SMT systems often generate "discontiguous" phrases—sequences of words with gaps filled later in the decoding process. This creates a significant context gap, as string-based LMs struggle to provide accurate fluency scores when words are separated by non-terminal placeholders.

This paper proposes a Deep Syntax Language Model (DSLM) that estimates word probability based on dependency relations (e.g., a noun conditioned on its head verb) rather than immediate string neighbors. By leveraging Lexical Functional Grammar (LFG), the authors demonstrate that deep syntax provides more meaningful context for lexical choice and naturally handles the discontiguities common in modern translation systems.

Methodology: From F-Structures to Dependency Paths

The authors utilize LFG "f-structures"—attribute-value matrices representing grammatical relations like subject, object, and adjunct—to build their model. These structures are simplified into directed acyclic unlabeled graphs, which are then processed to extract dependency paths.

Figure 1: (a) An LFG f-structure and (b) its corresponding dependency tree for the sentence "Today congress passed Obama’s health care bill."

To train the model, a depth-first traversal of these graphs constructs paths of predicates from the root to the leaves. These paths are treated similarly to strings for n-gram modeling. For instance, a trigram in this model represents a word conditioned on its "head" and its "head's head." The authors implemented this using the standard SRILM toolkit, feeding it extracted dependency paths instead of raw text.

Key Insights: Meaningful Context and Robustness

The primary advantage of the DSLM is its ability to capture long-distance dependencies that are invisible to local n-gram models. In a sentence like "Today congress passed Obama’s health care bill," a traditional LM predicts "congress" based on "Today," whereas the DSLM links "congress" directly to the verb "passed."

Figure 5: Comparison of probability estimation between (a) the Deep Syntax LM and (b) a Traditional string-based LM.

Furthermore, the DSLM is robust to word order variations. Sentential adverbs (like "today" or "quickly") can move within a sentence without altering the underlying dependency structure. The DSLM counts these as the same bigram regardless of position, effectively reducing data sparseness. Because hierarchical MT models build translations via nested non-terminals, this dependency-based approach is naturally aligned with the translation process.

Experimental Results

The authors compared the Deep Syntax (DS) model against a standard String-Based (SB) model using approximately 7 million English sentences from the WMT09 monolingual corpus. Due to vocabulary differences (lemmas vs. surface forms), they used n-gram coverage as the primary metric:

  • Bigram Coverage: The DS model (with end-of-sentence markers) achieved 94.71% coverage, outperforming the best string-based configuration at 93.09%.
  • Trigram Coverage: The DS model maintained its lead with 64.71% coverage compared to 58.75% for the string-based model.

Qualitative analysis further suggested that the DS model provides more distinct probabilities for competing translations, such as choosing "congress" over "convention" based on the head verb "pass," indicating superior potential for ranking translation hypotheses.

Limitations and Future Work

While promising, the DSLM faces challenges regarding parser dependency; the model requires a high-quality parser, and sentences that cannot be parsed remain unscored. Additionally, since the DSLM operates on lemmas/predicates while MT systems output surface forms, a mapping layer is required for full integration. Future work will focus on integrating the DSLM directly into an SMT decoder to evaluate its impact on BLEU scores in a production environment.

Summary updated

BibTeX
@inproceedings{graham2010deep,
  author = {Yvette Graham and Josef van Genabith},
  title = {{Deep Syntax Language Models and Statistical Machine Translation}},
  booktitle = {SSST @ COLING},
  year = {2010},
  url = {https://openreview.net/forum?id=7Yd5HpjXvs},
}
Figure