Empirical Analysis of Beam Search Curse and Search Errors with Model Errors in Neural Machine Translation

Empirical Analysis of Beam Search Curse and Search Errors with Model Errors in Neural Machine Translation Jianfei He1, Shichao Sun2, Xiaohua Jia1, Wenjie Li2 1 City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong 2 The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong jianfeihe-2c@my.cityu.edu.hk, bruce.sun@connect.polyu.hk csjia@cityu.edu.hk, wenjie.li@polyu.edu.hk Abstract Beam search is the most popular decoding method for Neural Machine Translation (NMT) and is still a strong baseline com- pared with the newly proposed sampling- based methods. To better understand the beam search, we investigate its two well- recognized issues, beam search curse and search error, not only on the test data as a whole but also at the sentence level. We find that only less than 30% of sentences in the WMT17 En–De and De–En test set ex- perience these issues. Meanwhile, there is a related phenomenon. For the majority of sentences, their gold references get lower probabilities than the predictions from the beam search. We also test with differ- ent levels of model errors including a spe- cial test using training samples and mod- els without regularization. In this test, the model has an accuracy of 95% in predict- ing the tokens on the training data. We find that these phenomena still exist even for such a model with very high accuracy. These findings show that it is not promis- ing to improve the beam search by seeking higher probabilities and further reducing the search errors in decoding. The relation- ship between the quality and the probabil- ity at the sentence level in our results pro- vides useful information to find new ways to improve NMT. © 2023 The authors. This article is licensed under a Creative Commons 4.0 licence, no derivative works, attribution, CC- BY-ND. 1 Introduction Beam search has been the most popular decoding (inference) method for Neural Machine Transla- tion (NMT) (Bahdanau et al., 2014). Fernandes et al. (2022)1 and our experimental results (in Ap- pendix A) show that the beam search is still a very strong baseline compared with the recently pro- posed sampling-based methods, including Top-k sampling, Nucleus (Top-p) sampling (Holtzman et al., 2019) and Minimum Bayes Risk (MBR) de- coding (Eikema and Aziz, 2021; Freitag et al., 2022). This is verified with different evaluation methods: BLEU, Meteor, and Comet (Rei et al., 2020). Meanwhile, there are still open issues deserving further exploration for the beam search. One widely recognized issue is a phenomenon called beam search curse (Koehn and Knowles, 2017; Yang et al., 2018; Meister et al., 2020). Beam search tends to get worse performance when the beam size increases. This issue is counter- intuitive. Usually, it is expected that using a larger beam size finds a sequence with higher probability in the search space and gets better quality. Another issue is search error (Stahlberg and Byrne, 2019; Shi et al., 2020), which means that the beam search as a heuristic method is not guaranteed to find the sequence with the largest probability in the search space. Stahlberg …

Content truncated to 500 words