A DP based Search Algorithm for Statistical Machine Translation

S. Nießen, S. Vogel, H. Ney, C. TillmannACL 1998

TL;DR

This paper introduces a novel dynamic programming (DP) based search algorithm for statistical machine translation (SMT). It efficiently combines translation and language models by expanding hypotheses along target string positions, ensuring all source words are considered, and presents experimental results on the Verbmobil task.

What Problem Does This Paper Address?

Statistical Machine Translation (SMT) aims to find the most probable target language representation for a given source language string. This involves maximizing a joint probability distribution that combines a translation model (how likely a target word is given a source word) and a language model (how likely a sequence of target words is). The core challenge lies in efficiently searching through the vast space of possible translations to find the optimal one. Traditional approaches often rely on approximations or constraints, such as monotonicity, which can limit translation quality. This paper tackles the problem of finding an efficient search algorithm that can effectively integrate these statistical knowledge sources without overly restrictive constraints.

Methods

The paper proposes a dynamic programming (DP) based search algorithm that operates by expanding hypotheses along the positions of the target string. This "inverted alignment model" allows for a more natural integration of the bigram language model.

Key aspects of their method include:

  • Dynamic Programming: Leverages DP to store and reuse solutions to subproblems, which is fundamental for efficiency in search algorithms.
  • Inverted Alignment Model: Instead of aligning source words to target words, each target word position is assigned a source word position. This allows for a more flexible handling of word reordering.
  • Maximum Approximation: To manage the complexity, the algorithm uses a "maximum approximation" where, at each step, only the most probable alignment is considered for a given source word.
  • Position Coverage Constraint: A crucial aspect is ensuring that all words in the source string are eventually covered by the translation. They introduce a recursive DP formulation with a control function to enforce this.
  • Acceleration Techniques: Several techniques are employed to speed up the search:
  • Minimal/Maximal Coverage: Restricting the range of source string coverage considered at each target string position.
  • Rescoring: Approximating the target string length and then re-evaluating hypotheses with the true score.
  • Thresholds: Using thresholds (θL and θT) to prune unlikely candidate words and alignments, reducing the search space.
  • Heuristic Sorting: Sorting arcs leading to DP states to potentially stop computation earlier.

Datasets

  • Verbmobil Corpus: Used for both training and evaluation. This corpus consists of spontaneously spoken German dialogs in the domain of appointment scheduling, translated into English.
  • Training Data: 16,296 sentence pairs.
  • Test Data: 150 sentences.
  • The vocabularies include category labels for dates, proper names, numbers, times, places, and spellings, which were replaced by appropriate labels during preprocessing.

Key Insights and Ideas

  • DP along Target String: The core innovation is framing the search problem by progressing through the target string positions, which naturally accommodates bigram language models without requiring monotonicity constraints.
  • Inverted Alignment Flexibility: The "inverted alignment" perspective allows for more flexible handling of word reordering and non-monotonic alignments, which are common in real-world translation.
  • Balancing Optimality and Efficiency: The paper acknowledges that DP, when applied to this problem, is inherently suboptimal due to the need for local decisions (like the maximum approximation). However, they demonstrate that with careful design and acceleration techniques, it can achieve good results.
  • Importance of Position Coverage: Explicitly addressing the "position coverage" problem is critical for ensuring that the entire source sentence is translated, not just parts of it.
  • Model Improvement Impact: The experimental results suggest that improvements in the underlying translation and language models, as well as more training data, will significantly impact translation quality.

Key Results

  • The proposed DP-based search algorithm was tested on the Verbmobil task.
  • Word Error Rate (WER): The algorithm achieved a WER of 39.6% after rule-based translation of labels (AL), which is reported to be better than a previous result of 51.8% on similar data by Tillmann et al. (1997a).
  • Subjective Evaluation: A subjective evaluation by experts classified translations into Correct, Acceptable, and Incorrect. For the 150 test sentences, 61 were Correct, 45 Acceptable, and 44 Incorrect. The Subjective Sentence Error Rate (SSER) was 44.3%.
  • Score Comparison: In cases where the output was not correct ("acceptable" or "incorrect"), the algorithm's produced translations often had higher scores than the sample translations, suggesting that the models themselves might be preferring these outputs, even if they are not ideal.
  • Acceleration: The paper details several acceleration techniques that significantly reduce the time complexity, with some achieving speed-ups of up to 3.5 times.

Limitations and Future Work

  • Suboptimality of DP: The authors acknowledge that the DP approach, due to the need for local decisions and approximations (like the maximum approximation), might miss the global optimum in some cases.
  • Search Errors: The possibility of "search errors" (missing a hypothesis with a higher score) is a known limitation, especially when outputs are classified as "acceptable" or "incorrect."
  • Heuristic for Pruning: Future work includes implementing more sophisticated pruning methods (e.g., similar to A*-search heuristics) to better compare different hypotheses, especially when they cover different sets of source words.
  • HMM-based Alignment: The paper notes that if HMM-based alignment models (which do not depend on target string length) are used, the alignment probabilities would need to be re-calculated as inverted alignments.
  • Data Sparseness: The limited size of the training corpus (16,296 sentence pairs) leads to data sparseness issues, particularly for lexicon probabilities, necessitating interpolation with manually created probabilities.

Summary updated

BibTeX
@inproceedings{nieen1998dp,
  author = {S. Nießen and S. Vogel and H. Ney and C. Tillmann},
  title = {{A DP based Search Algorithm for Statistical Machine Translation}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1998},
}
Figure