Dependency-Based Statistical Machine Translation

Heidi FoxACL 2005

Introduction: The Syntactic Gap in SMT

Early Statistical Machine Translation (SMT) models, such as the landmark IBM models of the 1990s, primarily treated translation as a word-to-word mapping problem. While these models were revolutionary, they largely ignored syntax, relying on linear word positions to handle reordering. This approach is particularly problematic for language pairs like Czech and English. Czech features a highly flexible word order and complex morphology (inflections), which often causes word-based or simple phrase-based models to struggle in capturing the underlying semantic relationships.

This research addresses the challenge of integrating dependency syntax into the translation process. The goal is to transition from "string-to-string" translation to "tree-to-tree" translation, leveraging the intuition that while surface word order varies, the fundamental relationships between words—such as subject-verb-object dependencies—are more likely to remain consistent across languages.

Methodology: From Strings to Tectogrammatical Trees

The proposed system builds upon previous dependency-based work but introduces a more robust model for structural changes. Central to this approach is the tectogrammatical representation, a "deep" syntactic layer. In this format, function words (e.g., "the," "is," "of") are removed, and their semantic contributions are stored as features—such as tense, negation, and number—on the remaining content words.

Table of linguistic features used in the tectogrammatical representation.

Structural Mutations

Recognizing that dependency trees do not always align perfectly between languages, the system defines specific operations to transform an English tree into a Czech-aligned structure:

  • KEEP: The structure remains identical.
  • SPLIT: A single English node generates two or more Czech nodes to account for lexical expansion.
  • BUD: Adds a "unary" level (a parent-child relationship) to accommodate extra words required in the target language.
  • ERASE: Removes a node that has no equivalent in the target language.
An illustration of a SPLIT mutation, where a single English node is expanded into multiple nodes in the Czech dependency tree.

Factored Probability Model

The translation probability $P(F|E)$ is decomposed into independent sub-problems for each node. The model generates the lemma (base word), part of speech, linguistic features, head position, and the specific mutation type. To navigate the search space, the decoder employs a best-first search guided by a Figure of Merit (FOM). This FOM normalizes probabilities based on perplexity (entropy), ensuring that features with many possible values (like lemmas) do not disproportionately affect the search compared to simpler features (like tense).

Experimental Setup

The study utilizes a high-quality parallel corpus for training and evaluation:

  • English Side: Wall Street Journal articles from 1989 (Penn Treebank).
  • Czech Side: The Prague Dependency Treebank (PDT), containing human-translated versions of the same WSJ articles with annotated dependency structures.
  • Tools: The Charniak parser provides initial syntactic analysis, which is then converted into the tectogrammatical format.

Discussion and Future Work

Dependency structures often prove more "isomorphic" (similar in shape) across languages than surface strings. By translating trees, the model handles Czech's flexible word order more naturally. Explicitly modeling structural mutations allows the system to "grow" or "shrink" the tree as needed, treating structural differences as learnable patterns rather than noise.

However, several limitations remain. The current model assumes each node is generated independently, which is linguistically unrealistic. Future work aims to introduce more conditioning factors and address data sparsity through smoothing techniques. Additionally, the system's reliance on initial parser accuracy means that errors in the Charniak parser can propagate through the translation pipeline. Future research will also explore "head switching" and improved modeling of discontinuous constituents.

Summary updated

BibTeX
@inproceedings{fox2005dependency,
  author = {Heidi Fox},
  title = {{Dependency-Based Statistical Machine Translation}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2005},
}
Figure