Context-Dependent Alignment Models for Statistical Machine Translation

Jamie Brunning, Adrià de Gispert, William J. ByrneNAACL 2009 · OpenReview

Abstract: Jamie Brunning, Adrià de Gispert, William Byrne. Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics. 2009.

Introduction

In Statistical Machine Translation (SMT), the "alignment" process is critical: it identifies which words in a source sentence correspond to which words in a target sentence. Traditionally, foundational models like IBM Model 1 and Hidden Markov Models (HMMs) have been context-independent. They operate under the simplifying assumption that the probability of a word $f$ translating to word $e$ remains constant, regardless of the surrounding linguistic environment.

Linguistically, this assumption is flawed. A word like "bank" carries vastly different translation probabilities depending on whether its neighbors are "river" and "water" or "investment" and "shares." However, incorporating context into these models traditionally leads to a "combinatorial explosion" of parameters. Attempting to track every possible combination of surrounding words results in severe "data sparsity," where the model lacks sufficient training examples for specific, rare contexts.

Methodology: Decision Tree Clustering

To address the data sparsity problem while capturing contextual nuances, the researchers developed an extension to Model 1 and HMMs that incorporates arbitrary context information, such as Part-of-Speech (POS) tags. They borrowed a technique from Automatic Speech Recognition (ASR)—decision tree clustering—to manage model complexity.

Figure 1: Example of word alignment with Part-of-Speech (POS) tags, illustrating the contextual information used by the model.

The implementation follows a structured optimization process:

  1. Contextual Questions: The model evaluates binary questions about a source word's environment (e.g., "Is the preceding word a preposition?" or "Is the following word a noun?").
  2. EM Optimization: The tree grows by selecting splits that maximize the Expectation-Maximization (EM) auxiliary function, ensuring that splits directly improve the likelihood of the training data.
  3. Clustering: Contexts resulting in similar translation distributions are grouped into "classes." This allows the model to share data across similar linguistic environments, providing reliable estimates even for rare contexts.
  4. Thresholding: Two controls, $T_{imp}$ (minimum likelihood improvement) and $T_{occ}$ (minimum occurrences), prevent the tree from over-splitting and overfitting the training data.

Experimental Setup

The models were evaluated on two major language pairs:

  • Arabic-English: Trained on ~300k parallel sentence pairs from NIST 08 data, using the MADA toolkit for morphological decomposition.
  • Chinese-English: Trained on 600k random parallel sentences from the LDC collection.

Alignment quality was measured using Alignment Error Rate (AER) against a manually-aligned gold standard, while end-to-end translation quality was assessed via BLEU scores.

Key Results and Insights

The researchers found that context-dependent (CD) models consistently outperformed their context-independent (CI) counterparts. Analysis of the decision trees revealed a surprising insight: the POS tags of the previous and next words were often more predictive of a translation than the POS tag of the word itself.

Figure 5: Alignment Error Rate (AER) for HMM models across iterations. Context-dependent models (Thresholds 10, 20, 60) consistently achieve lower error rates than the context-independent (CI) baseline.

As shown in the performance metrics, the CD approach achieved significant gains:

  • Alignment Accuracy: CD models reached lower AER across both Model 1 and HMM architectures. However, as seen in Figure 5, if the improvement threshold is too low, the model can begin to overfit, causing AER to rise in later iterations.
  • Translation Quality: These alignment improvements translated to significant BLEU score increases: +0.3 to +0.6 for Arabic-English and +0.5 to +0.8 for Chinese-English.
  • Efficiency: The clustering approach allowed for a modest increase in parameters while remaining computationally tractable for large-scale datasets.

Conclusion and Future Work

By applying ASR-inspired decision tree clustering to SMT, the authors successfully mitigated the data sparsity issues inherent in context-dependent modeling. While the study focused on immediate neighbors and POS tags, future work could explore longer-range dependencies or the inclusion of actual word identities. Furthermore, extending these techniques to more complex models like IBM Models 4 or 5 remains a promising avenue for further improving statistical translation systems.

Summary updated

BibTeX
@inproceedings{brunning2009context,
  author = {Jamie Brunning and Adrià de Gispert and William J. Byrne},
  title = {{Context-Dependent Alignment Models for Statistical Machine Translation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  url = {https://openreview.net/forum?id=MlomcQNID2k},
}
Figure