Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3042–3051 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 3042 Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation Xuanli He Monash University Gholamreza Haffari Monash University {xuanli.he1,gholamreza.haffari}@monash.edu mnorouzi@google.com Mohammad Norouzi Google Research Abstract This paper introduces Dynamic Programming Encoding (DPE), a new segmentation algo- rithm for tokenizing sentences into subword units. We view the subword segmentation of output sentences as a latent variable that should be marginalized out for learning and inference. A mixed character-subword trans- former is proposed, which enables exact log marginal likelihood estimation and exact MAP inference to find target segmentations with maximum posterior probability. DPE uses a lightweight mixed character-subword trans- former as a means of pre-processing parallel data to segment output sentences using dy- namic programming. Empirical results on ma- chine translation suggest that DPE is effective for segmenting output sentences and can be combined with BPE dropout for stochastic seg- mentation of source sentences. DPE achieves an average improvement of 0.9 BLEU over BPE (Sennrich et al., 2016) and an aver- age improvement of 0.55 BLEU over BPE dropout (Provilkov et al., 2019) on several WMT datasets including English ↔ (German, Romanian, Estonian, Finnish, Hungarian). 1 Introduction The segmentation of rare words into subword units (Sennrich et al., 2016; Wu et al., 2016) has be- come a critical component of neural machine trans- lation (Vaswani et al., 2017) and natural language understanding (Devlin et al., 2019). Subword units enable open vocabulary text processing with a neg- ligible pre-processing cost and help maintain a de- sirable balance between the vocabulary size and decoding speed. Since subword vocabularies are built in an unsupervised manner (Sennrich et al., 2016; Wu et al., 2016), they are easily applicable to any language. Given a fixed vocabulary of subword units, rare words can be segmented into a sequence of subword units in different ways. For instance, “un+conscious” and “uncon+scious” are both suit- able segmentations for the word “unconscious”. This paper studies the impact of subword segmen- tation on neural machine translation, given a fixed subword vocabulary, and presents a new algorithm called Dynamic Programming Encoding (DPE). We identify three families of subword segmenta- tion algorithms in neural machine translation: 1. Greedy algorithms: Wu et al. (2016) segment words by recursively selecting the longest sub- word prefix. Sennrich et al. (2016) recursively combine adjacent word fragments that co-occur most frequently, starting from characters. 2. Stochastic algorithms (Kudo, 2018; Provilkov et al., 2019) draw multiple segmentations for source and target sequences resorting to ran- domization to improve robustness and general- ization of translation models. 3. Dynamic programming algorithms, studied here, enable exact marginalization of subword segmentations for certain sequence models. We view the subword segmentation of output sentences in machine translation as a latent vari- able that should be marginalized out to obtain the probability of the output sentence given the input. On the other hand, the segmentation of source sen- tences can be thought …

Content truncated to 500 words