From characters to words: the turning point of BPE merges (2021)

Abstract: The distributions of orthographic word types are very different across languages due to typological characteristics, different writing traditions and potentially other factors. The wide range of cross-linguistic diversity is still a major challenge for NLP and the study of language. We use BPE and information-theoretic measures to investigate if distributions become similar under specific levels of subword tokenization. We perform a cross-linguistic comparison, following incremental merges of BPE (we go from characters to words) for 47 diverse languages. We show that text entropy values (a feature of probability distributions) tend to converge at specific subword levels: relatively few BPE merges (around 350) lead to the most similar distributions across languages. Additionally, we analyze the interaction between subword and word-level distributions and show that our findings can be interpreted in light of the ongoing discussion regarding different types of morphological complexity.

## introduction in nlp, one of the predominant methods for obtaining subword units is byte-pair encoding (bpe). these subwords have proven to be useful for improving several nlp tasks, most likely because they capture morphological patterns to some extent (and also phonological and orthographic ones). bpe is based on a compression algorithm which finds frequently ocurring patterns in a text by means of incrementally merging adjacent symbols into longer strings @xcite . the granularity of the subword units is controlled by the number of merge operations applied to the text (few merges lead to a text tokenization closer to the character level, while more merges lead to a tokenization closer to the word level). 1 data and code available at https://github.com/ ximenina/theturningpoint usually the number of bpe merges is chosen arbitrarily depending on the application. it is rarely analyzed how the distribution of these subwords changes across different merge operations. our goal is to investigate if languages get 'closer' in terms of their subword distributions under specific levels of tokenization. we quantify this cross-linguistic variation using informationtheoretic measures. information theory provides a useful tool for exploring variation, and for quantifying the predictability/organization of patterns, e.g., in morphological systems @xcite . we measure shannon entropy and redundancy over varied subword tokenizatons of texts obtained with bpe. at each incremental merge, we compare the values across 47 typologically diverse languages. cross-linguistic corpora are widely used as a means of quantifying linguistic diversity. for instance, the range of entropy values measured over word-level types varies greatly across languages. this is a reflection of the diversity of morphological systems. however, we show that this crosslinguistic variation is not so pronounced at the subword level. namely, a convergence of entropy values across languages is achieved at a relatively low number of merge operations. the entropy of subword distributions grows quickly before this turning point, while the growth is considerably slower after it. furthermore, in this turning point, the subword distributions start to correlate with the ones observed at the word-level. we interpret this change of trend in light of previous findings regarding the difference between subword and word-level complexity: a language that is complex at the word level (rich inflectional morphology), is not necessarily complex at a more atomic subword level (predictable subword patterns). ## data and methods our general proposal comprises calculating several measures over varied subword tokenizatons of texts obtained with bpe. in each consecutive tokenization, we hence regard a different set of strings of characters as symbols of our "alphabet". in merge 0, a text is a sequence of single utf-8 characters; in the last merges, a text is a sequence closer to orthographic word types (i.e. original tokenization given by white spaces and punctuation). at each incremental step, we compare the values across parallel corpora in 47 typologically diverse languages. ## god c-r-e-a-t-ed the h-e-a-v-e-n a-n-d god d-i-v-i-d-ed the l-i-g-h-t where the probability of a type p(t) is estimated using the so-called maximum likelihood method (i.e. its relative frequency in the text). higher values of entropy indicate higher complexity (less predictability). we take this as our main measure of text-based morphological complexity through merges. we also use redundancy, a measure that is related to entropy. the entropy of a source of data is maximum when the symbols comprising a message can be chosen freely and they are equiprobable (maximum uncertainty). the redundancy, as defined here, quantifies how close the empirically estimated entropy h(t ) is to the maximum value it can take, assuming that we utilize the same alphabet (or types in our case). it can be defined as follows @xcite : where h(t ) is the entropy of a text, calculated as in (1). the maximum entropy can be calculated as max{h(t )} = log 2 |v |, i.e, the entropy when the probability distribution of types is uniform p(t i ) = 1 ## discussion the "turning point" we discussed here reflects several phenomena. firstly, languages become more similar in terms of their subword entropies around this point. secondly, the trends of entropy and redundancy start to change (redundancy starts to grow, while entropy growth slows down). thirdly, there is a shift in several cross-linguistic correlations around the same region of merges. it seems that two different subword distributions emerge, one before the turning point, and one afterward. the entropy measured over word-level types reflect one dimension of diversity, i.e., some languages have rich inflectional morphology while others do not mark grammatical information wordinternally. however, in another dimension, at the subword level, this variation is reduced. if we rank languages by their entropy, the first merges' rankings are not correlated to the ones closer to the word level. in some of the languages, we see a clear trade-off across merges. for instance, some languages with high word entropy (low predictability, long words with the potential of com-bining many different morphological distinctions), have highly predictable subword distributions. languages where this trade-off is observed include: basque (eus), imbabura highland quichua (qvi), finnish (fin), yagua (yad), kalaallisut (kal). there are also examples of languages that start with high complexity on the first merges but they are not the most complex ones at the word level: vietnamese (vie), thai (tha), hindi (hin), yoruba (yor), nama (naq). english (eng) is also an example of a language that has comparatively low entropy at the word level, probably due to a relative lack of productive inflections, but is not one of the least complex at the subword level (first merges). however, this trade-off was not general, as we did not find a significant negative correlation between the entropies at first merges with the entropies at last merges. taking a linguistic perspective, several accounts have focused on the structure of the morphological paradigm and the predictability between the inflected forms @xcite @xcite . for instance, @xcite distinguish between two types of complexity: a) enumerative complexity (e-complexity), reflecting the diversity of morphological distinctions, word forms, paradigm size; and b) integrative complexity (i-complexity), related to systematic paradigmatic organization underlying the morphological surface patterns. the entropy values of i-complexity tend to be lower and less disperse than the ones exhibited by e-complexity @xcite . according to these observations, a morphological paradigm could grow (many different word forms, many morphosyntactic distinctions) as long as it maintains its predictive structure. this is argued to be the reason why languages vary more widely in the dimension of e-complexity, while being more constrained in the i-dimension. even though our work is not based on paradigms, and it did not require the use of linguistically annotated data, our findings seem to point in a similar direction, at least in the sense that the internal predictability of words is more similar across languages than than their word-level predictability. however, note that there is some evidence from language learning experiments -with neural networks and human participants -which suggests that both are more sensitive to e-complexity than i-complexity @xcite . it is an open question how our word-internal predictability measures relate to language learning. on a practical note, the fact that certain numbers of bpe merges lead to more similar entropies across languages could be beneficial for nlp multilingual tasks. to our knowledge, the entropy and redundancy of tokenized texts have not been used as a criterion for choosing an appropriate number of bpe merge operations. there is recent work that investigates how the number of merges can lead to more balanced distributions of subwords, improving tasks like nmt @xcite . another important question is to what extent our findings can be generalized to other corpora. the corpus size, type of register, etc., are likely to influence the turning point. as a general trend we expect this convergence to arise in a relatively low number of bpe operations. ## conclusions in this paper, we went from single characters to orthographic words through incremental merges of bpe. we observed that text entropy values across 47 typologically diverse languages are less dispersed at the subword level than at the wordlevel. our findings revealed a curious turning point, around the merge 200, where the values are least dispersed. around this point, subword token distributions gradually start to look like word-level distributions (subword-and word-level entropy rankings are correlated only after this point). additionally, this is approximately the point where text redundancy starts to grow after an initial drop and also where entropy growth slows down considerably after initial fast growth. at the early merges, the entropy of texts is strongly correlated with an independent measure based on modeling character trigrams sequences. this provides new evidence that contributes to the ongoing discussion regarding different types of linguistic complexity. finally, our analysis could provide a useful insight for nlp processing. choosing the number of merges that result in more similar distributions across languages could lead to more suitable subword representations for multilingual settings.