A Probability Model to Improve Word Alignment

Colin Cherry, Dekang LinACL 2003 · OpenReview

Abstract

Word alignment is a critical component of statistical machine translation (SMT), serving as a primary source for translation knowledge. We propose a statistical model that computes the probability of an alignment $A$ given a sentence pair $(E, F)$. Unlike traditional generative models, our approach allows for the seamless integration of context-specific linguistic features, such as dependency structures and word adjacency. Our experiments demonstrate that this model significantly improves upon existing alignments, outperforming the industry-standard IBM Model 4.

Introduction

In the early 2000s, SMT systems relied heavily on word alignment to map source words to target words. The dominant approach utilized the IBM Models, which were generative and modeled the probability of a source sentence generating a target sentence. However, these models suffered from inherent directionality—requiring post-hoc heuristics to achieve symmetry—and were difficult to augment with external linguistic knowledge.

Cherry and Lin address these limitations by introducing a discriminative refinement model. Instead of generating a sentence from scratch, the model evaluates the probability of a proposed alignment, making it naturally symmetric and flexible enough to incorporate complex grammatical constraints.

The Statistical Framework

The core of the proposed method is the calculation of $P(A|E, F)$. To make this calculation tractable, the authors decompose the alignment into individual links. They employ a Naive Bayes-style approximation where the probability of a link is adjusted by a ratio of feature probabilities. This modular design allows researchers to plug in arbitrary features without altering the underlying mathematical framework.

The model acts as a refiner: it starts with a "noisy" initial alignment—often based on simple co-occurrence statistics like $\phi^2$—and uses its feature set to clean it up. To find the optimal alignment in a vast search space, the system uses a best-first search algorithm combined with a greedy completion heuristic.

Integrating Linguistic Constraints

The model's strength lies in its ability to enforce "common sense" linguistic rules through specific features:

  • One-to-One Constraint: Each word is restricted to a single link, preventing the model from over-aligning to common words.
  • Adjacency Features: This captures the tendency for neighboring source words to remain neighbors in the target language.
  • Dependency Features: By utilizing the Minipar English dependency parser, the model identifies grammatical relationships like subject-verb or determiner-noun. It favors alignments that preserve these relationships in the target language.
  • Cohesion Constraint: This ensures that the projected dependency structure does not result in "crossing dependencies," maintaining structural integrity across the translation.
Dependency tree projection between English and French sentences.
Alignment of complex noun phrases using dependency information.

Experimental Evaluation

The model was evaluated using the Hansard Corpus, a collection of Canadian parliamentary proceedings. The training set consisted of 50,000 sentence pairs, while a manually aligned test set of 500 pairs was used for evaluation.

The primary metric was the Alignment Error Rate (AER), where lower scores indicate higher accuracy. The results showed that the proposed model achieved an AER of 8.7, outperforming the intersected IBM Model 4 (9.0) and significantly improving upon the refined IBM Model 4 (11.7). This represents a 44% relative error reduction over the standard single-direction IBM-4.

Conclusion and Future Work

The success of this model highlights the value of linguistic structure in statistical tasks. By treating alignment as a refinement problem rather than a generative one, the authors created a tool that is both more accurate and more extensible.

However, limitations remain. The current implementation is strictly one-to-one, and the model requires a decent initial alignment to begin its refinement process. Future work could involve extending the search space to handle many-to-many alignments and exploring unsupervised learning techniques to remove the dependency on pre-existing alignments.

Summary updated

Abstract

Word alignment plays a crucial role in statistical machine translation. Word-aligned corpora have been found to be an excellent source of translation-related knowledge. We present a statistical model for computing the probability of an alignment given a sentence pair. This model allows easy integration of context-specific features. Our experiments show that this model can be an effective tool for improving an existing word alignment.
BibTeX
@inproceedings{cherry2003probability,
  author = {Colin Cherry and Dekang Lin},
  title = {{A Probability Model to Improve Word Alignment}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2003},
  url = {https://openreview.net/forum?id=HyEKTje_bS},
}
Figure