Alignment by Agreement

Percy Liang, Benjamin Taskar, Dan KleinNAACL 2006 · OpenReview

Abstract

We present an unsupervised approach to symmetric word alignment in which two simple asymmetric models are trained jointly to maximize a combination of data likelihood and agreement between the models. Compared to the standard practice of intersecting predictions of independently-trained models, joint training provides a 32% reduction in AER. Moreover, a simple and efficient pair of HMM aligners provides a 29% reduction in AER over symmetrized IBM model 4 predictions.

Introduction

Word alignment is a critical component in statistical machine translation, identifying correspondences between words in source and target sentences. Traditionally, this task has relied on asymmetric models like the IBM models or HMM-based aligners, which assume each target word originates from exactly one source word. This paper introduces a novel unsupervised method that trains two directional models (e.g., English-to-French and French-to-English) to agree with each other during the learning process, rather than reconciling them post-hoc. By maximizing a joint objective of data likelihood and model agreement, the authors achieved a state-of-the-art 4.9% Alignment Error Rate (AER) on the Hansards corpus.

The Word Alignment Problem

The standard approach to obtaining symmetric alignments involves training two separate directional models ($E \to F$ and $F \to E$) and intersecting their predictions. However, independent training often results in "garbage collection" errors. In these cases, rare words in one language are incorrectly aligned to many words in the other simply because the model lacks a better explanation for the observed data.

Independent training of directional models often leads to 'garbage collection' errors, where rare words are incorrectly aligned to multiple tokens.

As seen in Figure 2, the $E \to F$ model incorrectly aligns the word "cojo" to multiple English tokens, a typical symptom of the garbage collector effect. The authors argue that encouraging agreement during training prevents these errors from becoming entrenched in the model parameters.

Methodology: Training by Agreement

The proposed framework couples two simple sequence-based models, such as HMMs, through a joint objective function:

  1. Objective Function: The model maximizes both the likelihood of the training data and the probability that both directional models produce the same alignment for any given sentence pair.
  2. Optimization via EM: A joint Expectation-Maximization (EM) algorithm is employed. While calculating the exact joint posterior is computationally intractable (#P-complete), the authors utilize a "product of marginals" approximation to maintain efficiency.
  3. Posterior Decoding: Instead of standard Viterbi decoding, the system uses posterior decoding. Alignment edges are retained if the product of the marginal probabilities from both models exceeds a specific threshold, allowing for a flexible trade-off between precision and recall.

Experimental Results

The jointly trained HMM model significantly outperformed existing baselines:

  • State-of-the-Art AER: The system achieved an AER of 4.9%, surpassing the standard independent HMM intersection (7.2%) and the more complex GIZA++ IBM Model 4 (6.9%).
  • Error Reduction: Joint training resulted in a 32% relative reduction in AER compared to intersecting independently trained models.
  • Translation Performance: The improved alignments led to a measurable gain in BLEU score, increasing from 0.3035 to 0.3051.
A directional alignment produced by the proposed method, demonstrating significantly improved AER compared to the baseline.

Figure 6 illustrates a directional alignment with a 7.3% AER, a substantial improvement over the 11.5% to 13.0% AER seen in baseline directional models.

Discussion and Insights

A key finding is that agreement acts as a powerful regularizer. By constraining the search space, joint training prevents models from falling into local optima characterized by spurious asymmetric alignments. Furthermore, this approach demonstrates that simplicity can win: a jointly trained HMM outperforms the much more complex, fertility-based IBM Model 4, which requires intricate search heuristics and is significantly slower to train.

The method also proved robust to initialization. While standard HMM aligners are sensitive to starting conditions, the joint training approach converged to high-quality solutions even from uniform initializations that caused independent models to fail.

Limitations and Future Work

Despite its success, the method has limitations. The "product of marginals" is a heuristic and does not strictly guarantee an increase in the joint objective at every EM step. Additionally, the underlying HMMs favor monotonic alignments, which may be less effective for language pairs with divergent word orders, such as English and Japanese. Future research could explore models designed for symmetry from the outset, rather than coupling two asymmetric ones.

Summary updated

Abstract

We present an unsupervised approach to symmetric word alignment in which two simple asymmetric models are trained jointly to maximize a combination of data likelihood and agreement between the models. Compared to the standard practice of intersecting predictions of independently-trained models, joint training provides a 32% reduction in AER. Moreover, a simple and efficient pair of HMM aligners provides a 29% reduction in AER over symmetrized IBM model 4 predictions.
BibTeX
@inproceedings{liang2006alignment,
  author = {Percy Liang and Benjamin Taskar and Dan Klein},
  title = {{Alignment by Agreement}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
  url = {https://openreview.net/forum?id=HJEIvQ-OWB},
}
Figure