A Statistical Extension of Byte-Pair Encoding (2021)

Abstract: Sub-word segmentation is currently a standard tool for training neural machine translation (MT) systems and other NLP tasks. The goal is to split words (both in the source and target languages) into smaller units which then constitute the input and output vocabularies of the MT system. The aim of reducing the size of the input and output vocabularies is to increase the generalization capabilities of the translation model, enabling the system to translate and generate infrequent and new (unseen) words at inference time by combining previously seen sub-word units. Ideally, we would expect the created units to have some linguistic meaning, so that words are created in a compositional way. However, the most popular word-splitting method, Byte-Pair Encoding (BPE), which originates from the data compression literature, does not include explicit criteria to favor linguistic splittings nor to find the optimal sub-word granularity for the given training data. In this paper, we propose a statistically motivated extension of the BPE algorithm and an effective convergence criterion that avoids the costly experimentation cycle needed to select the best sub-word vocabulary size. Experimental results with morphologically rich languages show that our model achieves nearly-optimal BLEU scores and produces morphologically better word segmentations, which allows to outperform BPE’s generalization in the translation of sentences containing new words, as shown via human evaluation.

## introduction sub-word segmentation is currently a standard tool for machine translation systems (see e.g. the systems submitted to wmt and iwslt evaluations @xcite , as well as systems for a wide variety of nlp tasks (see e.g. @xcite and derived works). the goal * now at google. is to split words (both in the source and target language) into smaller units which then constitute the input and output of the machine translation system. the goal is twofold: on the one hand, sub-word splitting reduces the size of the input and output vocabularies. this is specially important when using neural models, as the size of the input layer is fixed and thus the vocabulary size cannot be dynamically adjusted. on the other hand, it tries to increase the generalization capabilities of the translation model, enabling the system to accept and/or generate new words at translation time by combining previously seen units. the most widespread method used for sub-word splitting in neural machine translation is byte pair encoding (bpe), introduced by @xcite . since then, bpe has become a default preprocessing step for many nlp tasks. the bpe extraction algorithm is an adaptation of the algorithm introduced by @xcite for data compression. the main idea of this algorithm is to replace the most frequent pair of bytes found in the input data with a new, unseen byte. the process is repeated until no more byte pairs are repeated or until no free bytes are available. @xcite took this algorithm as a starting point, considering characters instead of bytes, and joining them using the same criterion to produce sub-word units (more details can be found in section 3). one potential problem with this approach is that the objective of the original bpe algorithm differs from the goals for which it is being used for translation, as detailed above. while it is certainly effective for the first objective (reducing the vocabulary size), it is arguable whether it is appropriate for the goal of generating new words @xcite @xcite . intuitively, in order to generate new words, we would expect the sub-word units to have some linguistic meaning, so that a new word can be created beklagen ↓ bek@@ lagen bewertungsinstrumente ↓ bewer@@ t@@ ungsin@@ stru@@ mente in a compositional way. being purely frequency driven, bpe does not take this intuition into consideration, as illustrated in the two german word examples in the bpe algorithm also introduces an additional practical problem. the original formulation does not specify a criterion for stopping the creation of new symbols. if the algorithm runs for an unlimited time, it will merge all sub-words into the original input vocabulary, which is clearly undesired. in practice, one specifies a fixed number of merges to be carried out, or a threshold frequency and when the considered symbols fall below this value the algorithm is stopped. it is however not clear how to set these hyperparameters, although they can have a drastic effect on translation quality depending on the translation direction, task and amount of data @xcite . furthermore, these hyperparameters are rarely optimized, as evaluating them constitutes a full training-evaluation cycle, which is notoriously costly. in this paper we introduce a new criterion for defining sub-word units that tries to address these shortcomings. we introduce a probability distribution over the units which in turn induces a likelihood function over the corpus which we can optimize. we will show how this statistical approach can guide the extraction process towards more linguistically satisfying units, while still remaining a purely data driven approach. having a well founded optimization criterion also allows us to define a data driven stopping criterion. our proposed criterion allows to select a nearly optimal number of units using only an intrinsic measure on the training corpus, thus dramatically reducing experimentation costs. ## related work as stated in the introduction, our starting point is the bpe algorithm introduced in @xcite . in this work, the authors adapt the data compression algorithm by @xcite to the task of sub-word unit generation. some authors have tried to expand the extraction of sub-word units by leveraging linguistic information. sánchez-cartagena and toral (2016) use morphological segmentation for finnish and compare the effectiveness of these sub-word units for the wmt evaluation. the system using this segmentation approach together with other extensions performed best in human evaluation. @xcite follow a similar approach with the addition of compound splitting for translation into german, achieving improvements of around 0.5 bleu points on wmt data. @xcite propose to replace bpe with unsupervised morphological segmentation which also takes morphological coherence into consideration during prediction of the sub-words. experiments run under smalldata conditions on ted talks in five directions, all from/to english, show systematic improvements on arabic, turkish, czech, but not on italian and german. @xcite also use unsupervised morphological units generated by morfessor @xcite as input for a neural machine translation system and report improvements for low-resource conditions. @xcite follow a similar approach for translation into czech on wmt data, but were not able to obtains improvements over the standard bpe approach. an alternative model to bpe which is also widely used was presented by @xcite , which can be considered as an extension of @xcite . they show that using a purely statistical approach, they are able to achieve subword units that are better linguistically motivated. similar to our approach, a probability distribution over the sub-word units is defined with the goal of improving the likelihood over the training data. the strategy for defining the sub-word units differ in his approach and ours. while we start with single characters and expand the units, @xcite starts with a large set of sub-word units and prunes iteratively until reducing the number to a desired quantity. segmentation probabilities are modeled with a multinomial distribution trained via expectation maximization. in order to improve generalization of the segmentation model (i.e. performance on new words), different regularization approaches have been proposed. @xcite applies different segmentations at training time. for each parameter update, segmentations for each word are sampled from a smoothed posterior distribution computed from the multinomial distribution. along the same line, @xcite , proposed to generate alternative segmentations directly with bpe, by randomly dropping out merging rules. these approaches, as noted by @xcite , can be seen as variants of the ensemble training principle, where many different models are trained (and finally combined) on different subsets of the training data. our work differs with respect to @xcite in that we train an observable model in a stepwise fashion, like bpe, by maximizing the likelihood of the training data. thus, we expect our approach to be more efficient than @xcite . differently from @xcite and @xcite , we do not apply regularization, however nothing prevents from applying the drop out method also to our merging rules, although we expect that our model has already learned more general segmentation rules than bpe. to the best of our knowledge, there has been little previous work on automatically determining the number of sub-word units to produce by segmentation algorithms. @xcite integrate segmentation into the nmt system and find that the system favors character-based translation over sub-word segmentation. @xcite pointed out that determining vocabulary sizes for nlp tasks is one of the few aspects that is still done manually, and suggests it as one possible direction for future improvement of nlp models. ## the byte pair encoding (bpe) algorithm the bpe training algorithm as presented in @xcite is shown in algorithm 1. it closely follows the original bpe for data compression algorithm by @xcite . the algorithm re-ceives as input a text as a sequence of words, which in turn are represented as sequences of characters. the single characters constitute the initial set of symbols. at each iteration the pair of symbols (occurring inside words) with highest frequency is selected and substituted with a new symbol. this substitution is recorded as a new rule. this merging operation is repeated for a fixed number of steps. the algorithm returns the sorted list of merging rules. algorithm 1: bpe training algorithm. ## the statistical bpe (s-bpe) algorithm we can generalize the criterion for bpe unit selection by adjusting line 3 of algorithm 1. specifically, we define a probability distribution over the bpe units and define a maximum likelihood optimization criterion. let s be a corpus of words w from a vocabulary v , and let each word be decomposed as a sequence of symbols (initially characters) s from an alphabet σ. the log-likelihood of s can be written as: algorithm 1 initializes σ with single characters (σ 0 ). then, at each step n of training, it selects the pair of symbols with the highest frequency or, equivalently, joint probability: from a statistical modeling perspective, however, we would be more interested in rules for which the training data likelihood increases, i.e.: it can be shown (see the appendix for a derivation) that for any pair of symbols x, @xmath0, the following inequality holds, which provides a lower bound for the increase in likelihood: the above inequality thus suggests the new update rule: note an important difference between equations (3) and ( 7 ): in (3) we use a bigram probability p n-1 (x, y) computed on σ n-1 ×σ n-1 , while in (7) we use a unigram probability p n (xy) computed on σ n . the two probabilities are expected to be close but not the same. note that in practice, in the course of the algorithm the count for a unit may drop to 0 (due to all the occurrences being combined with another unit to form a new pair), thus producing a probability of 0. in order to avoid computation of log 0 in equation ( 7 ) we use laplace smoothing for the computation of all probabilities. ## experimental results we conducted experiments for machine translation in a variety of languages, focusing on morphologically rich ones, using the data available from the latest wmt evaluation campaign where the language pair was used. we include results for finish (fi), german (de) @xcite , estonian (et), turkish (tr) [wmt'18], latvian [wmt'17] and romanian (ro) [wmt'16], all paired with english (en) and for both translation directions. we used all available corpora for translation model training, except paracrawl. corpora statistics can be found in for bpe training, the corpora were subsampled to 1m sentences for bpe training foot_2 , and a common bpe model was trained for the source and target languages (which also share the same em-bedding matrix). experiments were carried out using sockeye @xcite using mostly the default settings, except for a transformer architecture consisting of 20 encoder layers and 2 decoder layers @xcite . the corpora were tokenized using the moses tokenizer. ## conclusions and future work we introduced a statistical extension of bpe extraction. it introduces a well-founded objective for unit selection, which also allows the definition of a statistically motivated stopping criterion. using this approach we achieve nearly optimal machine translation performance as measured with bleu, while at the same time producing more linguistically motivated units. this leads to better translations of single words, which increases the translation quality as perceived by human judges, especially in the case of sentences containing unseen words. using the stopping criterion we approximate the optimal selection of number of units, without the need to perform the costly optimization required by bpe, involving a full training-evaluation cycle for each tested number of operations. regarding future work, we observe that the probability distributions defined for our approach are closely related to those used for n-gram language models. thus, smoothing methods can be applied, which can enhance the robustness of the method for unseen events, which opens a wide variety of possible extensions of this work. the code is available from https: //github.com/amazon-research/ statistical-byte-pair-encoding. and similarly for y. using ( 6 ) and ( 8 ) in (4) we obtain ∆l n (s) > @xmath1,y} c s,σn (s) log p n (s) -c s,σ n-1 (s) log p n (s) + c s,σn (xy) log p n (xy)