Tokenization and the Noiseless Channel

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 5184–5207 July 9-14, 2023 ©2023 Association for Computational Linguistics Tokenization and the Noiseless Channel Vilém ZouharE Clara MeisterE Juan Luis GastaldiE Li DuJ Mrinmaya SachanE Ryan CotterellE ETH ZürichE Johns Hopkins UniversityJ {vzouhar,cmeister,gjuan,msachan,rcotterell}@ethz.ch leodu@cs.jhu.edu Abstract Subword tokenization is a key part of many NLP pipelines. However, little is known about why some tokenizer and hyperparameter combinations lead to better downstream model performance than others. We propose that good tokenizers lead to efficient channel usage, where the channel is the means by which some input is conveyed to the model and efficiency can be quantified in information-theoretic terms as the ratio of the Shannon entropy to the maximum possible entropy of the token distri- bution. Yet, an optimal encoding according to Shannon entropy assigns extremely long codes to low-frequency tokens and very short codes to high-frequency tokens. Defining efficiency in terms of Rényi entropy, on the other hand, penalizes distributions with either very high or very low-frequency tokens. In machine transla- tion, we find that across multiple tokenizers, the Rényi entropy with α = 2.5 has a very strong correlation with BLEU: 0.78 in comparison to just −0.32 for compressed length. 1 Introduction Tokenization, the practice of breaking up text into words or subword pieces, or more generally, tokens,1 is often the first step in an NLP pipeline. A wide variety of tokenization functions have been proposed in the NLP literature (Mermer, 2010; Sennrich et al., 2016; Kudo, 2018). And, indeed, research on developing a good tokenization function continues because how one tokenizes may have a large impact on model performance in the downstream task. For instance, Gowda and May (2020) note BLEU ranges from 28 to 37 just by changing the size of the vocabulary in their machine translation (MT) pipeline. A direct extrinsic evaluation of a tokenization function, We release the tokenization-scorer package (App. B). 1To avoid ambiguity, we eschew the common expressions word and subword and, instead, adopt the term token to mean an element of the vocabulary after tokenization. We formally define token in §2. however, is computationally intensive: One first has to retokenize the corpora (generally quick), but then retrain the NLP model (often computationally intensive) to evaluate the effect. For this reason, characterizing the intrinsic properties of a good tokenization function has practical benefits (Gallé, 2019; Gowda and May, 2020). Our paper takes an information-theoretic ap- proach to characterizing a good tokenization func- tion. Following Gallé (2019), we contend that tok- enization may be fruitfully viewed as determining a good dictionary code for a language. Fortunately, dictionary codes are equipped with a natural intrin- sic metric of utility (expected code length) whereas there are many ways to extrinsically measure the tokenization quality. For simplicity and in line with previous research, we choose a specific down- stream task metric: BLEU (Papineni et al., 2002) in the domain of MT.2 We hypothesize that, ceteris paribus, down- stream task metrics should …

Content truncated to 500 words