A Discriminative Framework for Bilingual Word Alignment

Robert C. MooreEMNLP 2005

TL;DR

This paper introduces a discriminative approach to bilingual word alignment, moving away from traditional generative models. By framing alignment as a feature-weighted scoring problem and training with a modified perceptron algorithm, they achieve comparable accuracy to complex generative models while offering greater flexibility in adding new features and faster optimization.

What Problem Does This Paper Address?

Statistical Machine Translation (SMT) heavily relies on accurate bilingual word alignment as a foundational step. Existing state-of-the-art systems predominantly use generative models, often based on the IBM Models or HMMs. While these models can achieve high accuracy, they suffer from two main drawbacks:

  1. Parameter Tuning: Many parameters within these generative models require optimization using annotated data. However, the complex interplay of probabilities makes it difficult to jointly optimize these parameters effectively, often leading to time-consuming manual tuning.
  2. Feature Extensibility: Adding new features to generative models is challenging because it requires inventing new "generative stories" to explain how these features contribute to the data generation process. This can be cumbersome and limit the exploration of richer feature sets.

This paper aims to address these limitations by proposing a discriminative framework that simplifies parameter optimization and facilitates the easy incorporation of new features.

Methods

The core of the paper is the proposal of a discriminative framework for word alignment. Instead of modeling how data is generated, they model the decision of what constitutes a good alignment directly.

  • Feature-Based Scoring: For a given parallel sentence pair, each possible word alignment is assigned a score. This score is a weighted linear combination of various features that capture different aspects of the alignment. The alignment with the highest score is chosen. The general formula is: $score(\alpha) = \sum_{i=1}^{n} w_i f_i(\alpha, e, f)$ where $f_i$ are features and $w_i$ are learned weights.

  • Discriminative Training: The model weights ($w_i$) are optimized using a modified version of the averaged perceptron learning algorithm. This approach is "online," meaning it can converge quickly, and it avoids the need to invent generative stories.

The paper introduces two specific discriminative models:

  1. Log-Likelihood-Ratio (LLR)-Based Model: This model uses the LLR statistic to measure word association, a common technique for building translation lexicons. It also incorporates features for:
  2. Nonmonotonicity: Capturing how word order deviates from strict monotonicity.
  3. One-to-Many Links: Penalizing alignments where one word in one language aligns to multiple words in the other.
  4. Unlinked Words: Counting words that are not aligned to anything.
  5. Conditional-Link-Probability (CLP)-Based Model: This model replaces the LLR word association with the logarithm of estimated conditional probabilities of word pairs being linked. These probabilities are derived from alignments produced by a simpler model. It also includes nonmonotonicity and unlinked word features but omits the explicit one-to-many feature, as it's assumed to be implicitly handled by the conditional link probabilities.
  6. Alignment Search: Finding the optimal alignment is done using a beam-search procedure. This involves generating a list of potential association types, sorting them by score, and iteratively building up alignments by adding links. Pruning strategies are employed to manage the combinatorial explosion of possible alignments.

Datasets

  • Canadian Hansards Bilingual Corpus: A subset of 500,000 English-French sentence pairs was used.
  • Manually Word-Aligned Test Data: 447 English-French sentence pairs from the Hansards corpus, annotated with "sure" and "possible" links, were used for evaluation.
  • Development Set: The test data was split into two virtually equal subsets. One subset was used as a development set for parameter optimization.

Key Insights and Ideas

  • Discriminative models are competitive: The paper demonstrates that discriminative models, despite being simpler in concept and training, can achieve accuracy comparable to or even better than complex generative models like IBM Model 4.
  • Feature extensibility is a major advantage: The discriminative framework allows for easy addition of new features without requiring complex re-engineering of the model's underlying generative story. This opens up avenues for incorporating diverse linguistic knowledge.
  • Perceptron training is efficient: The averaged perceptron algorithm provides a fast and effective way to optimize model weights, especially when dealing with a manageable number of features.
  • LLR vs. CLP: The CLP-based model, particularly when using probabilities from a heuristic alignment model (CLP2), outperformed the LLR-based model. The authors attribute this to the CLP2 model having access to a larger number of potential links due to the richer source of conditional probabilities.

Key Results

  • Accuracy: The discriminative CLP-based models achieved significantly lower Alignment Error Rates (AER) than the LLR-based model and compared favorably to IBM Model 4. Specifically, CLP2 achieved an AER of 0.075, while IBM Model 4's refined combination achieved 0.079.
  • Training Time: While the alignment search implementation was slow (over a day for the LLR-based model on a large corpus), the parameter optimization itself was fast, requiring only a few passes over the development set. Total training time for each model was around an hour, even with multiple runs for parameter tuning.

Limitations and Future Work

  • Alignment Search Efficiency: The current Perl implementation of the alignment search is slow. The authors suggest that a more optimized implementation could significantly improve training speed.
  • CLP Source: The performance of the CLP-based model is dependent on the quality and quantity of links provided by the initial "simpler" model. The CLP2 model's success was partly attributed to a richer set of conditional link probabilities derived from a heuristic alignment model.
  • Future Work: The paper suggests that the ease of adding features makes it possible to experiment with a wide variety of knowledge sources to further improve word-alignment accuracy. The authors also mention that their work is a step towards exploring discriminative approaches for other tasks in statistical machine translation.

Summary updated

BibTeX
@inproceedings{moore2005discriminative,
  author = {Robert C. Moore},
  title = {{A Discriminative Framework for Bilingual Word Alignment}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
}
Figure