What changes when you randomly choose BPE merge operations? Not much. (2023)

Abstract: We introduce two simple randomized variants of byte pair encoding (BPE) and explore whether randomizing the selection of merge operations substantially affects a downstream machine translation task. We focus on translation into morphologically rich languages, hypothesizing that this task may show sensitivity to the method of choosing subwords. Analysis using a Bayesian linear model indicates that one variant performs nearly indistinguishably compared to standard BPE while the other degrades performance less than we anticipated. We conclude that although standard BPE is widely used, there exists an interesting universe of potential variations on it worth investigating. Our code is available at: https://github.com/bltlab/random-bpe.

## introduction and related work most neural machine translation (nmt) models assume their inputs to be sequences of units drawn from a fixed vocabulary. while these units were tokens in the early years of nmt @xcite , there has since been a transition to subword-level models that learn a vocabulary of "word pieces" which serve as an intermediate representation between words and characters @xcite . such representations are attractive because they solve the closed-vocabulary problem of early, word-level nmt @xcite while also yielding more semantically meaningful units than individual characters. well-known subword segmentation algorithms include byte pair encoding (bpe) @xcite , sentencepiece unigram lm @xcite and the wordpiece algorithm @xcite . all of them include a hyperparameter that controls the size of the subword vocabulary: sentencepiece and wordpiece do this explicitly with a vocabulary size parameter, whereas bpe specifies the number of merge operations which implicitly define the subword vocabulary. prior work has addressed the problem of optimally selecting the vocabulary size. @xcite and @xcite find that using too large a subword vocabulary can result in low-frequency tokens being represented as atomic units, which makes it difficult to learn proper representations for them. @xcite suggest a heuristic: use as many subwords as possible provided that at least 95% of the subwords have 100 or more examples in the training set. @xcite find that around 350 merge operations are enough to generate similar subword distributions across languages. subword segmentation algorithms usually build their subword vocabularies by optimizing an objective function that is independent of the downstream task. for instance, sentencepiece employs the probabilities under its unigram language model, while bpe aims to maximize the degree of sequence compression by greedily selecting and merging the symbol pairs that occur most frequently. others have re-framed this process as finding an "optimal" set of units that maximize more sophisticated probabilistic criteria. @xcite introduce an extension of bpe that learns a subword vocabulary by maximizing a likelihood objective over potential subwords. @xcite introduce a method that treats the segmentation as a latent variable to be marginalized out and seek to find segmentations that maximize the downstream task probability directly. in this paper, we build upon the concept of stochastic segmentation and conduct neural machine translation experiments on four languages (german, finnish, estonian and uzbek) of varying morphological complexity, using variants of bpe that randomly sample merge operations instead of deterministically choosing the most frequent one. our negative result challenges our initial beliefs that standard bpe would produce the most effective subword representations for translation and that the success of bpe was due to the greedy selection process for learning merge operations. we find that even when merge operations are randomly sampled uniformly, the performance degradation is less than we anticipated. we conclude by discussing how this finding relates to the overall role of subwords in nmt. ## byte pair encoding and randomization we briefly review the bpe training algorithm and introduce our randomized variants. the pseudocode for the algorithm we use can be seen in algorithm 1. our presentation is adapted from the bpe algorithm in @xcite . algorithm 1: bpe training algorithm. input: d: training corpus. m : number of merge operations to learn. output: r: list of learned merges. 1 def trainbpe(d, m , method): ## experimental setup task and data we experiment with translation from english to several morphologically rich languages: finnish, estonian, german, and uzbek. statistics for each dataset can be found in the appendix. for all languages except uzbek, we use the wmt shared task data from @xcite . for uzbek, we use the turkic interlingua corpus @xcite . model and training our model is a standard transformer-based encoder-decoder model, as implemented in the fairseq library. our architecture is similar to transformer-base, with 512-dimensional embeddings on both the encoder and decoder side, 2048-dimensional feedforward layers, and 6 stacked transformer layers with 8 attention heads each in both the encoder and decoder. we train all our models for 10,000 updates using a learning rate of 0.005 and the largest feasible batch size (36k tokens per batch for finnish and estonian, 30k tokens per batch for german, and 12k tokens per batch for uzbek). each translation experiment is run on a single nvidia v100 gpu (24gb). we simulate training on multiple gpus by accumulating gradients for 16 backward passes before each parameter update. to estimate the variability of our results across random seeds, we perform 10 replications of each experiment. evaluation we evaluate all of our models with the sacrebleu library (post, 2018) using bleu 1 1 version string: nrefs:1|case:mixed|eff:no| tok:13a|smooth:exp|version:2.3.1 @xcite as well as chrf foot_0 @xcite as it is a tokenization-free metric. both metrics are computed using the default parameters. we use the sacremoses foot_1 detokenizer to create the detokenized versions of our corpora. ## results our main experimental results are displayed in initially, we would have expected that standard bpe would perform the best out of all methods and that different bpe variants would produce noticeable performance differences for all languages. somewhat contrary to our hypothesis, we find that using randomized bpe variants seems to have quite a small average effect with significant variation in the effect size from language to language. uniform segmentation tends to consistently perform worse than standard bpe and softmax-based sampling, which can be explained by the roughly 3x longer sequences the model produces. looking across merge operations, the bleu/chrf differences between the best and worst bpe variants seem to be less than 1.0 and 1.5 points for estonian and finnish, respectively. however, german and uzbek show a different picture, with bleu/chrf differences of around 2-2.5 points for german and 4-9 points for uzbek. the impact of varying the number of merge operations varies and again bifurcates the set of languages. finnish and estonian seem to suffer slightly as the merge operations are increased (approx. -2 to -2.5 points in bleu/chrf), whereas german and uzbek seem to benefit from more merge operations (approx. +1 to +2 points in bleu/chrf). we find this perplexing, as the german and uzbek datasets are the largest and smallest used in our experiments. to analyze these results, we fit a hierarchical, bayesian linear model with language-specific effects for the bpe variant and number of merge operations: the effects for the number of merges are largely similar, with small average effects and betweenlanguage variation in effects on both sides of zero. while effect sizes tend to be very small for 2,000 and 5,000 merge operations, the effect varies with 32k merges. german and uzbek seem to benefit from using 32k merge operations (posterior means 0.59 and 2.30, respectively). in contrast, finnish and estonian have significantly negative effect sizes (-1.83 and -1.31, respectively) with the entire 94% hdi for finnish below zero as well.