Accelerated DP based search for statistical translation

By Christoph Tillmann, Stephan Vogel, Hermann Ney, Arkaitz Zubiaga, H. Sawaf. 1997

In this paper, we describe a fast search algorithm for statistical translation based on dynamic programming (DP) and present experimental results. The approach is based on the assumption that the word alignment is monotone with respect to the word order in both languages. To reduce the search e(cid:11)ort for this approach, we introduce two methods: an acceleration technique to e(cid:14)ciently compute the dynamic programming recursion equation and a beam search strategy as used in speech recognition. The experimental tests carried out on the Verbmobil corpus showed that the search space, measured by the number of translation hypotheses, is reduced by a factor of about 230 without a(cid:11)ecting the translation performance.

Subfields: Natural Language Processing, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

In Optimization & Training

Citations in the corpus

Findings of the 2014 Workshop on Statistical Machine Translation (2014, methodology): “MT quality in the Medical Translation Task is evaluated using automatic evaluation metrics: BLEU (Papineni et al., 2002), TER (Snover et al., 2006), PER (Tillmann et al., 1997), and CDER (Leusch et al., 2006).”
BERTScore: Evaluating Text Generation with BERT (2019, background): “PER (Tillmann et al., 1997), WER (Klakow and Peters, 2002), CDER (Leusch et al., 2006), TER (Snover et al., 2006), and TER P (Snover et al., 2009) are metrics based on edit distance.”
Minimum Error Rate Training in Statistical Machine Translation (2003, methodology): “Examples of such methods are word error rate, position-independent word error rate (Tillmann et al., 1997), generation string accuracy (Bangalore et al., 2000), multi-reference word error rate (Nießen et al., 2000), BLEU score (Pap-ineni et al., 2001), NIST score (Doddington, 2002).”
Evaluation of Text Generation: A Survey (2020, neutral): “PER (Tillmann et al., 1997) computes position independent error rate.”
Multilingual Test Sets for Machine Translation of Search Queries for Cross-Lingual Information Retrieval in the Medical Domain (2014, methodology): “BLEU score and positionindependent word error rate (PER) (Tillmann et al., 1997) were used for evaluation.”
Asiya: An Open Toolkit for Automatic Machine Translation (Meta-)Evaluation (2010, methodology): “PER (Position-independent Word Error Rate) (Tillmann et al., 1997) We use −PER.”
A Survey of Evaluation Metrics Used for NLG Systems (2020, background): “ion of TER. In addition to the basic edit operations in TER (insertion, deletion, substitution and shift), ITER also allows stem matching and uses optimizable edit costs and better normalization. PER [158] computes ‘Position-independent Edit Rate’ by identifying the alignments/matching words in both”
BERT: A Review of Applications in Natural Language Processing and Understanding (2021, methodology): “This can also include methods like PER [77] and CDER [37], taking into account the permutation of text blocks.”
Improving Statistical Machine Translation Using Word Sense Disambiguation (2007, methodology): “In addition to the widely used BLEU (Papineni et al., 2002) and NIST (Doddington, 2002) scores, we also evaluate translation quality with the recently proposed Meteor (Banerjee and Lavie, 2005) and four edit-distance style metrics, Word Error Rate (WER), Positionindependent word Error Rate (PER) (Ti”
CDER: Efficient MT Evaluation Using Block Movements (2006, background): “In this, the new measure differs significantly from the position independent error rate (PER) by (Tillmann et al., 1997).”
FBK-UEdin Participation to the WMT13 Quality Estimation Shared Task (2013, methodology): “Using the predictions of the English-Spanish systems as pseudo-references and likewise the original source as reference for the back-translation system we computed a number of automatic metrics including BLEU (Papineni et al., 2002), GTM (Turian et al., 2003), PER (Tillmann et al., 1997), TER (Snove”
Adaptation of machine translation for multilingual information retrieval in the medical domain (2014, background): “BLEU [5] and PER (position-independent word error rate) [6].”
A Re-examination of Machine Learning Approaches for Sentence-Level MT Evaluation (2007, background): “In addition to the well-known word error rate (WER), more sophisticated modifications have been proposed (Tillmann et al., 1997; Snover et al., 2006; Leusch et al., 2006).”
An Evaluation Tool for Machine Translation: Fast Evaluation for MT Research (2000, methodology): “In machine translation this criterion is used e.g. in (Vidal, 1997), and (Tillmann et al., 1997).”
Investigating Data Variance in Evaluations of Automatic Machine Translation Metrics (2022, methodology): “These metrics are summarized as follows: BLEU (Papineni et al., 2002), WER (Morris et al., 2004), PER (Tillmann et al., 1997), TER (Snover et al., 2006), chrF (Popović, 2015), chrF+ (Popović, 2017), BEER (Stanojević and Sima’an, 2014), CharacTER (Wang et al., 2016), BERTScore (Zhang et al.,…”
Using Machine Translation Evaluation Techniques to Determine Sentence-level Semantic Equivalence (2005, background): “However, when the features from PER and POS-are combined there is an improvement in performance (to 72.71”