learn.ifs.name

Words and Tokens

Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2

18 cards in “2.4 Subword tokenization: byte-pair encoding” · whole deck

2.4 Subword tokenization: byte-pair encoding

  1. What are the pros and cons of words, morphemes and characters as tokens?
    Words and morphemes are at roughly the right level (consistent meanings) but hard to define formally. Characters are easy to define but too small a unit.
  2. Why tokenize text into a fixed set of units at all?
    So systems can agree on basic questions (How long is this text? Is New York one token or two?), which is essential for replicability; metrics like perplexity assume a fixed tokenization. Subword tokens also eliminate unknown words.
  3. What is the unknown word problem, and how do subwords solve it?
    A system trained on low, new, newer but not lower wouldn’t know what to do with lower at test time. With subword tokens, every unseen word can be built from known pieces (low + er), in the worst case from single characters.
  4. What two subword tokenization algorithms are widely used in modern LMs?
    Byte-pair encoding (BPE; Sennrich et al., 2016) and the unigram language model (ULM; Kudo, 2018). The SentencePiece library implements both.
  5. What are the two phases of a tokenization scheme like BPE?
    A training phase, which induces a vocabulary of tokens from a raw training corpus, and an encoding phase, which segments new text into tokens from that vocabulary.
  6. Describe the BPE training algorithm.
    Start with a vocabulary of all single characters (or bytes). Repeatedly find the most frequent pair of adjacent tokens in the corpus, add their concatenation as a new token, and replace every occurrence of the pair with it. Stop after \(k\) merges; the vocabulary is the characters plus \(k\) new tokens.
  7. Run two BPE merges on the corpus A B D C A B E C A B.
    Most frequent pair: A B → new token AB: AB D C AB E C AB. Next most frequent: C AB → CAB: AB D CAB E CAB. Vocabulary is now {A, B, C, D, E, AB, CAB}.
  8. Why does BPE usually not merge across word boundaries?
    The corpus is first pre-split at whitespace and punctuation (with regexes) into words with counts; merges are allowed only inside these strings, which keeps tokens word-like.
  9. In BPE training on new, renew, reset, set, which prefix does the algorithm “discover”, and how?
    re-: after merging n e and ne w, frequent pairs like (space, r) and then (r, e) merge into a word-initial token “␣re”, since it appears in renew and reset.
    mergecorpus afterwards
    n e → ner e ne w, r e s e t
    ne w → newr e new, r e s e t
    ␣ r → ␣r␣r e new, ␣r e s e t
    ␣r e → ␣re␣re new, ␣re s e t
  10. How does the BPE encoder tokenize a test sentence?
    It splits each word into characters, then applies the learned merges greedily in the order they were learned (most frequent in training first). Test-data frequencies play no role.
  11. Besides recreating training words, what useful units does BPE learn?
    Morpheme-like pieces, e.g. the prefix re- (for unseen revisit, rearrange) or word-internal new without a leading space (for anew).
  12. What vocabulary sizes do real BPE tokenizers use, and what is the effect?
    Tens of thousands of merges, giving 50,000–200,000 tokens, so most (English) words are single tokens and only rare or unknown words are split.
  13. On what units is BPE usually run for Unicode text, and why?
    On the individual bytes of the UTF-8 encoding. Only 256 byte values exist, so there are no unknown tokens; BPE first rediscovers common multi-byte UTF-8 sequences. Rare illegal byte sequences can be filtered.
  14. What regularities show up in an industrial BPE tokenizer’s output for English?
    Most words are single tokens, usually including their leading space; clitics like ’s split off rare names but not frequent words like she’s; numbers are chunked into groups of 3 digits; capitalization and position change segmentation (Any+how vs ␣anyhow).
  15. What is pretokenization?
    A stage before BPE that segments the input with regular expressions: breaking at spaces and punctuation, splitting off clitics, and chunking numbers.
  16. What do SuperBPE and BoundlessBPE do differently?
    After learning ordinary subword tokens with pretokenization, they run a second BPE stage that allows merges across spaces and punctuation, producing larger multi-word tokens that encode text more efficiently.
  17. Why do multilingual BPE tokenizers oversegment languages other than English?
    Training data is dominated by English, so most tokens are spent on English; other languages get split into shorter pieces (Spanish hondo → h + ondo), and lower-resource languages sometimes down to single characters.
  18. What problems does oversegmentation into tiny tokens cause?
    Poorer representations of meaning, the need for longer contexts, and higher costs to train (and use) models for those languages.

Source