📄 Alignment by Agreement

Summary

The paper addresses unsupervised word alignment for statistical machine translation. The standard pipeline trains two directional aligners separately, often GIZA++ IBM model 4, and intersects their outputs afterwards. Liang, Taskar and Klein instead train two simple, mirror-image sequence-based models (E→F and F→E HMMs) together. The training objective adds the log-probability that both models choose the same alignment to the usual sum of their data log-likelihoods. This yields an EM-like procedure. Its M-step splits into ordinary per-model updates, but its E-step combines both models' posteriors. Exact computation of that combined E-step is #P-complete, so the authors use a heuristic approximation. On the English-French Hansards task, the jointly trained HMMs reach 4.9% AER. The authors report this as the best published unsupervised result at the time, comparable to supervised aligners. The method is no harder to implement or slower to train than two standard HMMs. The work matters because cheap, simple models trained to agree can beat a complex fertility-based system, and the same coupling idea applies to other pairs of tractable latent-variable models.

Key points

• Joint training cuts AER by 32% compared with intersecting two independently trained models. A jointly trained HMM pair cuts AER by 29% compared with symmetrized GIZA++ IBM model 4.
• On the English-French Hansards task, the method reaches 4.9% AER. For independently trained HMMs, intersection alone lowers AER from about 11% to 7%.
• In a Figure 1 example with models trained on 1.1 million sentences, the intersected AER drops from 7.6 to 5.7. The rare word "cojo" stops acting as a garbage collector.
• Implementation details of the HMM aligner:
  • The null probability is set to 1/(I+1), depending on English sentence length.
  • Distortion uses 11 offset buckets, from ≤−5 to ≥5.
  • There are three separate distortion sets: one governs transitions into the first state, another governs transitions out of the final state, and a third covers every remaining transition.
• In a downstream test, 100K Europarl sentences were aligned and used with Pharaoh, then evaluated on 3000 test sentences of length 5–15. BLEU rose only slightly, from 0.3035 with GIZA++ model 4 to 0.3051.

Interesting ideas

• I1. Move agreement into training. If combining two models at test time helps, add a term that rewards their agreement to the training objective itself. This could be useful for any pair of complementary unsupervised models, such as two directions or two views of the data.
• I2. Agreement as a shared-output probability. Measuring agreement as the probability that both models pick the same output keeps the M-step decoupled. Each model keeps its usual update and only the E-step changes, so existing EM code can be reused almost unchanged.
• I3. A common output space for asymmetric models. Rewriting directional alignments as sets of binary edge indicators lets two structurally different models share one output space. This is a general recipe for comparing or coupling models whose native outputs differ.
• I4. Approximate an intractable coupling heuristically. When the exact joint E-step is intractable, a heuristic approximation can still work well in practice. The lesson is to test a pragmatic approximation before investing in heavy sampling or variational inference.
• I5. Error analysis that informs model design. The authors identify specific failure types: rare words acting as garbage collectors, a monotonicity bias from context-free distortion, and "stepping stone" alignments. Naming failures this concretely points directly to the next modelling improvements.