Abstract: We report on search errors and model errors in neural machine translation (NMT). We present an exact inference procedure for neural sequence models based on a combination of beam search and depth-first search. We use our exact search to find the global best model scores under a Transformer base model for the entire WMT15 English-German test set. Surprisingly, beam search fails to find these global best model scores in most cases, even with a very large beam size of 100. For more than 50% of the sentences, the model in fact assigns its global best score to the empty translation, revealing a massive failure of neural models in properly accounting for adequacy. We show by constraining search with a minimum translation length that at the root of the problem of empty translations lies an inherent bias towards shorter translations. We conclude that vanilla NMT in its current form requires just the right amount of beam search errors, which, from a modelling perspective, is a highly unsatisfactory conclusion indeed, as the model often prefers an empty translation.

Introduction: [0]Now at Google. Neural machine translation BIBREF0 , BIBREF1 , BIBREF2 assigns the probability INLINEFORM0 of a translation INLINEFORM1 of length INLINEFORM2 over the target language vocabulary INLINEFORM3 for a source sentence INLINEFORM4 of length INLINEFORM5 over the source language vocabulary INLINEFORM6 via a left-to-right factorization using the chain rule: DISPLAYFORM0  The task of finding the most likely translation INLINEFORM0 for a given source sentence INLINEFORM1 is known as the decoding or inference problem: DISPLAYFORM0  The NMT search space is vast as it grows exponentially with the sequence length. For example, for a common vocabulary size of INLINEFORM0 , there are already more possible translations with 20 words or less than atoms in the observable universe ( INLINEFORM1 ). Thus, complete enumeration of the search space is impossible. The size of the NMT search space is perhaps the main reason why – besides some preliminary studies BIBREF3 , BIBREF4 , BIBREF5 – analyzing search errors in NMT has received only limited attention. To the best of our knowledge, none of the previous studies were able to quantify the number of search errors in unconstrained NMT due to the lack of an exact inference scheme that – although too slow for practical MT – guarantees to find the global best model score for analysis purposes. [t!] BeamSearch INLINEFORM0 [1] INLINEFORM1 : Source sentence, INLINEFORM2 : Beam size INLINEFORM3 Initialize with empty translation prefix and zero score INLINEFORM4 INLINEFORM5 INLINEFORM6 INLINEFORM7 Hypotheses ending with INLINEFORM8 are not expanded INLINEFORM9 Add all possible continuations INLINEFORM10 Select INLINEFORM11 -best INLINEFORM12 INLINEFORM13 INLINEFORM14  [t!] DFS INLINEFORM0 [1] INLINEFORM1 : Source sentence  INLINEFORM0 : Translation prefix (default: INLINEFORM1 )  INLINEFORM0 : INLINEFORM1 (default: INLINEFORM2 )  INLINEFORM0 : Lower bound INLINEFORM1 INLINEFORM2 Trigger INLINEFORM3 update INLINEFORM4 Initialize INLINEFORM5 with dummy value INLINEFORM6 INLINEFORM7 INLINEFORM8 INLINEFORM9 INLINEFORM10 INLINEFORM11 INLINEFORM12  In this work we propose such an exact decoding algorithm for NMT that exploits the monotonicity of NMT scores: Since the conditional log-probabilities in Eq. EQREF1 are always negative, partial hypotheses can be safely discarded once their score drops below the log-probability of any complete hypothesis. Using our exact inference scheme we show that beam search does not find the global best model score for more than half of the sentences. However, these search errors, paradoxically, often prevent the decoder from suffering from a frequent but very serious model error in NMT, namely that the empty hypothesis often gets the global best model score. Our findings suggest a reassessment of the amount of model and search errors in NMT, and we hope that they will spark new efforts in improving NMT modeling capabilities, especially in terms of adequacy.

Question: what were the length constraints they set?
Answer: They set translation length longer than minimum 0.25 times the source sentence length