S ub M erge: Merging Equivalent Subword Tokenizations for Subword Regularized Models in Neural Machine Translation (2024)

Abstract: Subword regularized models leverage multiple subword tokenizations of one target sentence during training. However, selecting one tokenization during inference leads to the underutilization of knowledge learned about multiple tokenizations.We propose the SubMerge algorithm to rescue the ignored Subword tokenizations through merging equivalent ones during inference.SubMerge is a nested search algorithm where the outer beam search treats the word as the minimal unit, and the inner beam search provides a list of word candidates and their probabilities, merging equivalent subword tokenizations. SubMerge estimates the probability of the next word more precisely, providing better guidance during inference.Experimental results on six low-resource to high-resource machine translation datasets show that SubMerge utilizes a greater proportion of a model’s probability weight during decoding (lower word perplexities for hypotheses). It also improves BLEU and chrF++ scores for many translation directions, most reliably for low-resource scenarios. We investigate the effect of different beam sizes, training set sizes, dropout rates, and whether it is effective on non-regularized models.

## introduction despite the end-to-end nature that makes neural machine translation (nmt) @xcite @xcite the most prevalent and convenient approach for machine translation (mt), subword tokenization @xcite the authors. this article is licensed under a creative commons 4.0 licence, no derivative works, attribution, cc-by-nd. figure 1 : subword regularized models suffer from discrepancies between training and inference, where they are trained on multiple target tokenizations and generate one. we propose to merge equivalent subword tokenizations that compose the same word with different conditional probabilities during the inference. @xcite @xcite remains an indispensable preprocessing step for most nmt systems. subword vocabularies address the out-of-vocabulary problem of word-based nmt systems @xcite @xcite by reducing new words to known subwords, while avoiding the high computational cost of character-based nmt systems @xcite @xcite @xcite by enabling much shorter input and output sequences. deterministic segmenters like byte-pair encoding (bpe) @xcite and sentence-piece @xcite are widely used due to their simplicity and effectiveness. they are determinisitic in the sense that they consistently generate the same tokenization for a given sentence. nmt models trained on consistent subword tokenizations typically allocate the majority of a sentence's true probability (considering all potential tokenizations by marginalizing over them) to its specific tokenization @xcite , except for out-of-domain data @xcite . therefore, the probability of the sentence approximately equals the probability of that tokenization. on the other hand, stochastic segmenters such as subword regularization methods @xcite produce multiple tokenizations of a given sentence during training, as illustrated in figure 1 . as a data augmentation method, models trained on regularized data usually outperform those trained on non-regularized data, especially in low-resource scenarios. however, this causes a discrepancy between training and inference. during training, the model learns to generate multiple target tokenizations for each source sentence and learns to distribute the probability of a target sentence across all the tokenizations. during inference, greedy or beam search approximates the single highest probability tokenization. this causes a discrepancy -the probability of a target tokenization diverges drastically from the probability of a target sentence. the inaccurate probability estimation of the next word during inference in turn leads to a degradation in translation quality. the way to overcome this is to incorporate the marginal likelihood of the next words during decoding for the subword regularized models. to this end, we propose submerge, a decoding algorithm that aggregates probabilities from exponentially many tokenizations for a sentence by merging subword tokenizations that form the same word. the property of bpe-dropout @xcite ) that each word is individually segmented makes aggregating probabilities from exponentially many tokenizations theoretically possible. as for the implementation, submerge is a nested beam search approach. in the outer beam search, we hide the detail of possible subword tokenizations of the word, treating words as minimal units. this ensures that the outer beam is unaware of and unaffected by the subword tokenizer. in the inner beam search, we limit the search space within the word boundary. the inner beam search finds the n-best tokenizations, merges equivalent ones, and returns a list of words and the corresponding probabilities. previous attempts to estimate marginal likelihood over tokenizations include summing over nbest tokenizations @xcite and using importance sampling @xcite . however, these algorithms focus on perplexity estimation, assuming the output is already in hand. in our approach, we perform marginal likelihood estimation for the next words along with the inference process, aiming to improve not only the estimation precision but also the translation quality. in a nutshell, our contributions are as follows: ## preliminaries this section formulates the objective of the inference process of nmt models, highlights the distinction introduced by subword regularized models, and introduces how we address it. inference objective an nmt model with parameters θ during inference is to obtain arg max non-regularized models for nmt models using deterministic tokenizers such as bpe @xcite , tokenization function τ (•) is a bijective function, and we can approximate the objective using one tokenization with a small gap (less than 0.5%) @xcite : with greedy or beam search in inference. this allows us to identify the next tokens with high conditional probabilities without concern for the discrepancy between the probability of raw text y and of the particular tokenization y. subword regularized models for nmt models using stochastic tokenizers @xcite , the tokenization function τ yields multiple tokenizations for one sentence. that is τ s (x) = @xmath0. similar for y . in this case, the number of possible segmentation v s (x ) increases exponentially according to the length of x, which deviates p θ (y|x) drastically from p θ (y |x), thus it requires marginalization over all possible tokenizations: this study focuses on better estimating the marginal likelihood of the target side, so we simplify eq. ( 3 ) by using the most probable source tokenization arg max @xmath1, resulting in: inference for subword regularized models we propose submerge to approximates eq. (4) by introducing an intermediate variable, word tokenizations @xmath2, ..., w n ), generated by a word to-kenizer τ w (•) which is a bijective function. foot_0 the problem is simplified as: p θ (y |x) = p θ (w|x) = n @xmath3, x). (5) we estimate p θ (w i |@xmath4, x) by summing over probabilities of subword tokenizations for one word w i where the search space is much smaller compared to the search space of tokenizations of a whole sentence in eq. (4): in practice, since the decoder only takes subword as input, we feed the best subword tokenization of the next word w i , which is arg max in this way, the probability of the target sentence is accurately calculated through a deterministic word tokenization as shown in eq. ( 5 ), where the probability estimation of each word is precisely estimated through marginal likelihood estimation shown in eq. ( 6 ). we implement eq. ( 5 ) with the outer beam search as introduced in section 3.2 and eq. ( 6 ) with our inner beam search as introduced in section 3.3. ## experimental setup we introduce the mt datasets and pre-processing settings section 4.1. in section 4.2, we provide details around the model hyper-parameters, training and inference settings. in section 4.3, we present our evaluation metrics. ## translation quality results the results for subword regularized models are shown in ## efficiency we show the theoretical analysis of time complexity as well as running time results of submerge comparing with beam search. time complexity let k denote beam size and t word denote the number of words in the sentence. in the outer beam search algorithm 1, the loop in line 3 contains at most t steps, and line 5 contains at most k steps. therefore, the time complexity of the submerge is o(t word * k * o(innerbeamsearch()). in the inner beam search algorithm 2, line 3 contains at most t subword steps, which is the number of subwords within the word boundary. line 5 contains at most k steps, and line 9 contains at most k steps because each beam yields maximum k candidates by selecting top-k probable tokens. therefore, the time complexity of algorithm 2 is o(t subword * k * k). ## analysis we investigate the effect of different beam sizes on the algorithm in section 7.1. section 7.2 explores using a sampling algorithm as the inner search algorithm. section 7.3 and section 7.4 respectively analyze the impact of the training set size and the dropout rate. section 7.5 show conditions in which submerge is effective. 1 2 4 6 8 10 beam size 5.0 7.5 10.0 12.5 15.0 17.5 20.0 22.5 word ppl wmt'15 en->fi bpe w/ beam search bpe w/ submerge bpe-dropout w/ beam search bpe-dropout w/ submerge figure 3: word perplexity results using different beam sizes on the wmt'15 @xmath5. ## related work submerge is designed for decoding with text generation models for which likely tokenization probabilities diverge drastically from sentence probabilities. in other words, there are multiple tokenizations for one target sentence, and the probability distribution is splintered among them. our objective is to enhance the inference algorithm on the target side. on the source side, merging probabilities of multiple tokenizations for a single source sentence has been shown to improve translation performance in low-resource scenar-ios @xcite . although we only experimented on models trained on data segmented by bpe-dropout @xcite , it also works for sentencepiece regularization @xcite , maxmatch-dropout @xcite and nmt models with multiple subword segmenters @xcite . on the other hand, nmt models trained on sentences segmented by deterministic segmenter only benefit from marginal likelihood estimation in out-of-domain data or long words @xcite . deterministic subword segmentation includes not only subword-level methods such as wordpiece @xcite , bpe @xcite , sentence-piece @xcite , dynamic programming encoding @xcite , bert-seg @xcite , but also byte-level (shaham and levy, 2021), character-level @xcite , word-level @xcite , and hybrid word-character methods @xcite . marginal likelihood estimation can be implemented in two ways: sampling and dynamic programming. sampling methods include summing over n-best tokenizations @xcite or important tokenizations @xcite . sampling can be easily applied to any generation model. however, a manageable number of tokenizations cannot precisely estimate the probability of sentences with an exponentially large number of tokenizations, which is the case during the inference of the subword regularized models. on the other hand, dynamic programming can handle an exponentially large number of tokenizations by merging the same historical states, as introduced in sequence modeling via segmentations @xcite and applied in the mixedcharacter-subword models @xcite . however, they merge the historical states by approximating the previous output by character-level data. that is, after the decoder generates one subword, it is split into characters and fed to the decoder. this is not applicable to pure subword models. based on the property that each word is individually segmented in bpedropout @xcite , we obtain n-best tokenizations within a small search space and treat the best tokenization of each word the historical state, taking advantage of both marginal likelihood estimation methods. ## conclusion and future work we propose submerge to estimate the marginal likelihood of the next word by merging equivalent subword tokenizations during the inference of subword regularized models. results demonstrate a significant improvement in word perplexity estimation and translation quality improvement in terms of bleu and chrf++ scores, especially in low-resource scenarios. current inference algorithms are mostly based on conditional probability, which is a short-term value function. for future work of inference, we suggest aligning the value function towards evaluation metrics and human preference through reinforcement learning, where models are more aware of longer-term rewards.