BPE -knockout: Pruning Pre-existing BPE Tokenisers with Backwards-compatible Morphological Semi-supervision (2024)

Abstract: Byte-pair encoding (BPE) has become the default subword tokeniser in language models (LMs), allowing the representation of an infinite space of text with a finite set of units. Yet, BPE training is unsupervised, receiving no explicit information about a language’s morphology. This results in a subword vocabulary wherein many units are a concatenation of partial morphemes, preventing their formation as tokens. This, in turn, causes consistent intra-word patterns to be displayed inconsistently to downstream models, and bloats the vocabulary, hence requiring unnecessary embedding storage. In this paper, we address this issue by identifying blameworthy BPE merges and removing the resulting subwords from the BPE vocabulary, without impeding further use of merges that relied on them. We find that our method, BPE-knockout, is effective at making BPE’s segmentation positions adhere better to derivational and compound boundaries in English, Dutch and German, and improves token-based tasks in Dutch RoBERTa models, indicating that a tokeniser’s adherence to morphology impacts downstream models. We demonstrate the latter not only by training LMs from scratch, but also by continuing the pre-training of existing LMs. This proves promising, showing that suboptimal tokenisers can be remedied whilst salvaging training cost of downstream LMs.

## introduction subword tokenisation has become a mainstay in natural language processing (nlp) in recent years, riding on the success of translation models (tms) @xcite and language models (lms) @xcite that incorporate it as the first step to process text. rather than keeping a theoretically infinite dictionary of words in the considered language, a subword tokeniser segments each word into smaller parts (subword tokens) such that each segment is part of a known and finite set (the subword vocabulary v of subword types). an early subword tokeniser was proposed by @xcite , and in the last decade, there has been a growing set of alternatives @xcite @xcite @xcite @xcite . subword tokenisation rose to fame when @xcite proposed translating a sequence of subwords (rather than words) into a sequence of subwords (rather than words) in the attention-based machine translation architecture of @xcite . in particular, @xcite 's hierarchical compression algorithm byte-pair encoding (bpe) for building the subword vocabulary (later termed vocabularisation by @xcite ), as well as for applying the learnt vocabulary in a tokeniser. a recap of the bpe algorithm follows later. for now, it suffices to know that bpe vocabularisation builds types in the vocabulary with a bottom-up approach. this has its pathologies @xcite : e.g., some subwords are formed by adding few characters at a time, similar to the chaining effect in hierarchical clustering @xcite . many of the stepping stones are never used afterwards, either to learn other types or even as tokens during application @xcite , which means it is pointless to reserve storage for them in downstream models @xcite . furthermore, bpe vocabularisation and segmentation are both unsupervised, informed by nothing more than absolute frequencies in the training corpus. the benefit is that massive, automatically gathered corpora can be used. the downside is that no morphological constraints are imposed on the tokeniser, and indeed, bpe segmentation boundaries often deviate from morphological boundaries deduced from underlying morphemes @xcite @xcite . in particular, bpe tends to abridge morphemes. in the best case, it fuses full morphemes into one token, but the problem is often worse: @xcite show an example wherein the letters of the passivating turkish morpheme -ıl-are pulled apart into the adjacent tokens, which obscures it enough to lose the passive voice in translation. we hypothesise that recalling these boundaries in token sequences improves downstream performance of a model trained on them. not only will this avoid evaporation of morphemes by subsuming their characters into other tokens (as above), but it will also provide the most reliable intra-word patterns possible in the model's input (namely, those dictated by the language of the corpus): as @xcite point out, the most consistent surface segmentation of danced, dancing and entered are the morphologically sound danc ed, danc ing and enter ed, using the same token for the same semantics. patterns found in any other segmentation (e.g.: dance d, dancing, ente red ) are necessarily more noisy, making the language harder to model. that said, only recall of morphological boundaries is not sufficient; otherwise, character-level tokenisation would do. the advantage of subword tokenisation is that there are many more units to which a static embedding is assigned. having more embeddings means having more storage space for pooling any knowledge obtained about a subword across all the contexts it appears in. ideally, all words containing the same morpheme would contribute towards informing a single embedding for that morpheme, rather than fragmenting knowledge about it across the vocabulary. this way, when an unseen word arrives with that morpheme, the model could draw on all of its past occurrences, rather than a subset. furthermore, having only a single subword type for a morpheme could facilitate equity across languages, allowing a model to store the same amount of meanings given the same vocabulary capacity, even if its language produces many more surface word forms. 1 in summary, bpe tokenisers have a bloated vocabulary and a lack of morphology. in light of this, we present the following contributions: ## bpe-knockout as hinted at in the introduction, we want to rid the bpe vocabulary of excessive types. since types depend on each other, the impact of doing this is not immediately obvious, and hence it is best to construct an equivalent representation of a bpe tokeniser that makes this clear. once this is set up, we can define which types are "excessive" based on morphological resources. ## experiments to evaluate tokenisers resulting from blame-guided knockout (henceforth called bpe-knockout), we first check whether it indeed produces closer matches with morphological boundaries, after which we verify our hypothesis by pre-training and fine-tuning lms downstream of it. ## releases we release all code on github at https:// github.com/bauwenst/bpe-knockout . in addition, we release the final checkpoints for the 3 dutch lms on huggingface as part of a collection, bauwens/bpe-knockout. ## conclusion in this paper, we showed that a bpe tokeniser can be made significantly more adherent to morphological boundaries by disabling merges that abridge them excessively. we showed that this adherence to morphology benefits downstream lm tasks, and that it is even possible to adjust the tokeniser of lms after their pre-training in a cost-effective way. even for german, which does have inflection, our experiments do not cover false-negative merges of fusional morphemes, because celex only decomposes lemmata, which are uninflected. hence, no plural words, no conjugated verbs and (for german) no other cases than the nominative are present in celex, which means that not all merges that are morphologically harmful in a corpus of running text are counted towards blame. this likely doesn't affect the intrinsic experiments ( §4.1) since the test set also consists of only lemmata, but it does limit the improvement of our lms ( § 4.2) since those encounter more inflected forms than lemmata. no indication of lexicalisation sometimes, the meaning of a word cannot be deduced from its morphemes; the meaning is lexicalised, i.e. taken up as a new, standalone unit in a speaker's vocabulary. it would hence also be confusing to split such a word into the morphemes it originates from and then use the embeddings associated with them. an example of such non-compositionality is the dutch verb muggenziften ("to nitpick", but literally "to sift mosquitoes"), which is analysed by celex as if it were compositional: this then informs bpe-knockout that the verb should be split. in fact, merges that form lexicalised words from their constituents (like muggen and ziften) are most at risk of being blamed, because those merges are likely applied nowhere else and so b(m) increases whenever n (m) does in eq. 1.