Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation (2020)

Abstract: This paper introduces Dynamic Programming Encoding (DPE), a new segmentation algorithm 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 transformer 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 transformer as a means of pre-processing parallel data to segment output sentences using dynamic programming. Empirical results on machine translation suggest that DPE is effective for segmenting output sentences and can be combined with BPE dropout for stochastic segmentation of source sentences. DPE achieves an average improvement of 0.9 BLEU over BPE (Sennrich et al., 2016) and an average improvement of 0.55 BLEU over BPE dropout (Provilkov et al., 2019) on several WMT datasets including English <=> (German, Romanian, Estonian, Finnish, Hungarian).

## introduction the segmentation of rare words into subword units @xcite has become a critical component of neural machine translation @xcite and natural language understanding @xcite . subword units enable open vocabulary text processing with a negligible pre-processing cost and help maintain a desirable balance between the vocabulary size and decoding speed. since subword vocabularies are built in an unsupervised manner @xcite , 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 suitable segmentations for the word "unconscious". this paper studies the impact of subword segmentation on neural machine translation, given a fixed subword vocabulary, and presents a new algorithm called dynamic programming encoding @xcite . we identify three families of subword segmentation algorithms in neural machine translation: 1. greedy algorithms: @xcite segment words by recursively selecting the longest subword prefix. @xcite recursively combine adjacent word fragments that co-occur most frequently, starting from characters. 2. stochastic algorithms @xcite draw multiple segmentations for source and target sequences resorting to randomization to improve robustness and generalization 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 variable that should be marginalized out to obtain the probability of the output sentence given the input. on the other hand, the segmentation of source sentences can be thought of as input features and can be randomized as a form of data augmentation to improve translation robustness and generalization. unlike previous work, we recommend using two distinct segmentation algorithms for tokenizing source and target sentences: stochastic segmentation for source and dynamic programming for target sentences. we present a new family of mixed charactersubword transformers, for which simple dynamic programming algorithms exist for exact marginalization and map inference of subword segmenta-tions. the time complexity of the dynamic programming algorithms is o(t v ), where t is the length of the target sentence in characters, and v is the size of the subword vocabulary. by comparison, even computing the conditional probabilities of subword units in an autoregressive model requires o(t v ) to estimate the normalizing constant of the categorical distributions. thus, our dynamic programming algorithm does not incur additional asymptotic costs. we use a lightweight mixed character-subword transformer as a means to pre-process translation datasets to segment output sentences using dpe for map inference. the performance of a standard subword transformer @xcite trained on wmt datasets tokenized using dpe is compared against byte pair encoding (bpe) @xcite and bpe dropout @xcite . empirical results on english ↔ (german, romanian, estonian, finnish, hungarian) suggest that stochastic subword segmentation is effective for tokenizing source sentences, whereas deterministic dpe is superior for segmenting target sentences. dpe achieves an average improvement of 0.9 bleu over greedy bpe @xcite and an average improvement of 0.55 bleu over stochastic bpe dropout @xcite foot_0 . ## related work neural networks have revolutionized machine translation @xcite @xcite . early neural machine translation (nmt) systems used words as the atomic element of sentences. they used vocabularies with tens of thousands words, resulting in prohibitive training and inference complexity. while learning can be sped up using sampling techniques @xcite , word based nmt models have a difficult time handling rare words, especially in morphologically rich languages such as romanian, estonian, and finnish. the size of the word vocabulary should increase dramatically to capture the compositionality of morphemes in such languages. more recently, many nmt models have been developed based on characters and a combination of characters and words @xcite @xcite @xcite . fully character based models @xcite demonstrate a significant improvement over word based models on morphologically rich languages. nevertheless, owing to the lack of morphological information, deeper models are often required to obtain a good translation quality. moreover, elongated sequences brought by a character representation drastically increases the inference latency. in order to maintain a good balance between the vocabulary size and decoding speed, subword units are introduced in nmt @xcite . these segmentation approaches are data-driven and unsupervised. therefore, with a negligible pre-processing overhead, subword models can be applied to any nlp task @xcite . meanwhile, since subword vocabularies are generated based on word frequencies, only the rare words are split into subword units and common words remain intact. previous work @xcite ) has explored the idea of using stochastic subword segmentation with multiple subword candidates to approximate the log marginal likelihood. @xcite observed marginal gains in translation quality at the cost of introducing additional hyperparameters and complex sampling procedures. we utilize bpe dropout @xcite , a simple stochastic segmentation algorithm for tokenizing source sentences. dynamic programming has been used to marginalize out latent segmentations for speech recognition @xcite , showing a consistent improvement over greedy segmentation methods. in addition, dynamic programming has been successfully applied to learning sequence models by optimizing edit distance @xcite and aligning source and target sequences @xcite . we show the effectiveness of dynamic programming for segmenting output sentences in nmt using a mixed character-transformer in a pre-processing step. ## latent subword segmentation let x denote a source sentence and @xmath0, . . . , y t ) denote a target sentence comprising t characters. the goal of machine translation is to learn a conditional distribution p(y | x) from a large corpus of source-target sentences. state-ofthe-art neural machine translation systems make use of a dictionary of subword units to tokenize the target sentences in a more succinct way as a sequence of @xmath1. given a subword vocabulary, there are multiple ways to segment a rare word into a sequence of subwords (see figure 1 ). the common practice in neural machine translation considers subword segmentation as a pre-process and uses greedy algorithms to segment each word across a translation corpus in a consistent way. this paper aims to find optimal subword segmentations for the task of machine translation. let @xmath2, .., z m +1 ) denote a sequence of character indices 0 = z 1 < z 2 < . . . < z @xmath3, defining the boundary of m subword segments {y z i ,z i+1 } m @xmath4. let y a,b ≡ [y a+1 , . . . , y b ] denote a subword that spans the segment between (a + 1) th and b th characters, including the boundary characters. for example, given a subword dictionary {'c', 'a', 't', 'at', 'ca'}, the word 'cat' may be segmented using @xmath5, 1, 3) as ('c', 'at'), or using @xmath6, 2, 3) as ('ca', 't'), or using @xmath7, 1, 2, 3) as ('c', 'a', 't'). the segmentation @xmath8, 3) is not valid since 'cat' does not appear in the subword vocabulary. autoregressive language models create a categorical distribution over the subword vocabulary at every subword position and represent the logprobability of a subword sequence using chain rule, we consider a subword segmentation z as a latent variable and let each value of @xmath9, in the set of segmentations compatible with y, contribute its share to p(y) according to p(y) = z p(y, z), ## a mixed character-subword transformer we propose a mixed character-subword transformer architecture, which enables one to marginalize out latent subword segmentations exactly using dynamic programming (see figure 2 ). our key insight is to let the transformer architecture process the inputs and the conditioning context based on characters to remain oblivious to the specific choice of subword segmentation in the conditioning context and enable exact marginalization. that said, the output of the transformer is based on subword units and at every position it creates a categorical distribution over the subword vocabulary. more precisely, when generating a subword y z i ,z i+1 , the model processes the conditioning context (y z 1 , . . . , y z i ) based solely on characters using, given a fixed subword vocabulary denoted v , at every character position t within y, the mixed character-subword model induces a distribution over the next subword @xmath10, ## conclusion this paper introduces dynamic programming encoding in order to incorporate the information of the source language into subword segmentation of the target language. our approach utilizes dynamic programming for marginalizing the latent segmentations when training, and inferring the highest probability segmentation when tokenizing. our comprehensive experiments show impressive improvements compared to state-of-the-art segmentation methods in nmt, i.e., bpe and its stochastic variant bpe dropout.