Byte Pair Encoding is Suboptimal for Language Model Pretraining (2020)

Abstract: The success of pretrained transformer language models (LMs) in natural language processing has led to a wide range of pretraining setups. In particular, these models employ a variety of subword tokenization methods, most notably byte-pair encoding (BPE) (Sennrich et al., 2016; Gage, 1994), the WordPiece method (Schuster and Nakajima, 2012), and unigram language modeling (Kudo, 2018), to segment text. However, to the best of our knowledge, the literature does not contain a direct evaluation of the impact of tokenization on language model pretraining. We analyze differences between BPE and unigram LM tokenization, finding that the latter method recovers subword units that align more closely with morphology and avoids problems stemming from BPE’s greedy construction procedure. We then compare the fine-tuned task performance of identical transformer masked language models pretrained with these tokenizations. Across downstream tasks and two languages (English and Japanese), we find that the unigram LM tokenization method matches or outperforms BPE. We hope that developers of future pretrained LMs will consider adopting the unigram LM method over the more prevalent BPE.

## introduction large transformers @xcite pretrained with variants of a language modeling objective, such as bert @xcite , have proven their effectiveness at flexibly transferring to a variety of domains and tasks. one design decision that makes them particularly adaptable is their graceful handling of the open vocabulary problem through subword tokenization. subword tokenization, popularized in the neural machine translation literature @xcite @xcite , produces tokens at multiple levels of granularity, from individual characters to full words. as a result, rare words are broken down into a collection of subword units, bottoming out in characters in the worst case. critically, a pretrained language model's subword vocabulary cannot be altered: any downstream application of these models must tokenize input or generate output using the original subword vocabulary, making the choice of tokenization a particularly significant decision. a variety of subword tokenization methods have seen use in pretrained language models. bert uses the wordpiece method @xcite , a language-modeling based variant of bpe; t5 @xcite uses character-level bpe; gpt2 @xcite and roberta @xcite use bpe over raw bytes instead of unicode characters; xlnet @xcite and albert @xcite use the sentence-piece library @xcite ) which implements both bpe and unigram language model tokenization, but in both cases fail to clarify which of these methods they chose. the effects of tokenization are not examined in a reported experiment in any of the above works except @xcite , who note that wordpiece gave a small advantage over bpe in their preliminary investigation. in the machine translation literature, @xcite introduced the unigram language model tokenization method in the context of machine translation and found it comparable in performance to bpe. @xcite performed further experiments to investigate the effects of tokenization on neural machine translation, but used a shared bpe vocabulary across all experiments. @xcite examined algorithms in the bpe family, but did not compare to unigram language modeling. in this work, we characterize the space of proposed subword tokenization algorithms and analyze the differences between the two methods with publicly available implementations: bpe (merging tokens based on bigram frequency) and unigram language modeling (pruning tokens based on unigram lm perplexity). while the vocabularies resulting from these schemes are heavily overlapping, we compare each method to reference morphological segmentations and find that the unigram lm method produces tokens better aligned with morphology. to understand whether this more natural tokenization leads to improved performance, we pretrain separate language models using the roberta objective @xcite with each tokenization for both english and japanese, two typologically distant languages. on downstream tasks, we find a performance gap across tasks and languages, with the unigram lm method providing an improvement over bpe of up to 10% in our japanese qa experiments, indicating the benefits of adopting this technique in the context of language model pretraining. ## algorithms subword tokenization algorithms consist of two components: a vocabulary construction procedure, which takes a corpus of text and returns a vocabulary with the desired size, and a tokenization procedure, which takes the built vocabulary and applies it to new text, returning a sequence of tokens. in theory, these two steps can be independent, although for the algorithms we examine the tokenization procedure is tightly coupled to the vocabulary construction procedure. a bpe vocabulary is constructed as follows: algorithm 1 byte-pair encoding @xcite 1: input: set of strings d, target vocab size k 2: procedure bpe(d, k) v ← all unique characters in d 4: the wordpiece algorithm @xcite , used to construct bert's vocabulary, closely resembles bpe. however, instead of merging the most frequent token bigram, each potential merge is scored based on the likelihood of an n-gram language model trained on a version of the corpus incorporating that merge. @xcite note that the process of estimating language model parameters for every potential merge is prohibitive, so they employ aggressive heuristics to reduce the number of potential merges considered. as their implementation is not public, foot_0 we are unable to make a comparison to this method. the unigram lm method @xcite , in contrast to the bottom-up construction process of bpe and wordpiece, begins with a superset of the final vocabulary, pruning it to the desired size: algorithm 2 unigram lm @xcite 1: input: set of strings d, target vocab size k 2: procedure unigramlm(d, k) original: furiously bpe: fur iously uni. lm: fur ious ly original: tricycles bpe: t ric y cles uni. lm: tri cycle s original: nanotechnology bpe: n an ote chn ology uni. lm: nano technology original: completely preposterous suggestions bpe: comple t ely prep ost erous suggest ions unigram lm: complete ly pre post er ous suggestion s original: corrupted bpe: cor rupted unigram lm: corrupt ed original: 1848 and 1852, bpe: 184 8 and 185 2, unigram lm: 1848 and 1852 , original 磁性は様々に分類がなされている。 bpe 磁 性は 様々 に分類 がなされている 。 unigram lm 磁 性 は 様々 に 分類 がなされている 。 gloss magnetism (top.) various ways in classification is done . translation magnetism is classified in various ways. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 token length 0 1000 2000 3000 4000 number of tokens bpe unigram lm (a) token length distributions within each vocabulary 1 20000 token frequency rank 10 2 10 3 10 4 10 5 10 6 10 7 token frequency bpe unigram lm (b) token frequency profiles over the corpus figure 2: english subword vocabulary and corpus profiles. the unigram lm method produces longer tokens on average (a) and uses its vocabulary space more effectively (b), with more tokens of moderate frequency. in the course of our experiments we did not observe a major difference in speed between the two algorithms. both require similar amounts of time to construct a vocabulary, and both have a negligible impact on overall model inference latency. ## downstream task experiments in order to make a fair experimental comparison between these two methods on downstream tasks, we do not use an existing pretrained language model like bert, but instead train our own language models from scratch, controlling for the data, training objective, and optimization procedure. we pretrain four transformer masked language models using the architecture and training objective of roberta-base @xcite using the reference fairseq implementation @xcite . two are pretrained on the text of english wikipedia, comprising ∼3b tokens under either tokenization. the other two are pretrained on the text of japanese wikipedia, comprising ∼0.6b tokens. in each pair, one model is pretrained on the bpe tokenization of the corpus, and the other on the unigram lm tokenization, each with a vocabulary of 20,000 tokens. hyperparameters are listed in appendix a. we subsequently fine-tune each of the pretrained english models on the squad question-answering task @xcite , the mnli textual entailment task @xcite , and the english portion of the conll 2003 named-entity recognition shared task @xcite . we fine-tune the japanese models on the japanese minimal-answer subset of the tydi question-answering task @xcite . we base our fine-tuning implementations on those of the transformers toolkit @xcite . the results of our fine-tuning experiments are presented in ## conclusion in this work we show that the choice of input encoding makes a difference in how well pretrained language models are able to perform end tasks. this indicates that tokenization encodes a surprising amount of inductive bias, and we suggest that unigram lm tokenization may be the better choice for development of future pretrained models.