Definition
Unigram tokenization is the subword method of Taku Kudo, "Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates" (ACL 2018). A vocabulary of pieces carries probabilities that sum to 1. A segmentation of a string has probability , with the pieces treated as independent. Encoding takes the most probable segmentation by Viterbi. Training alternates EM re-estimation of with pruning the pieces whose removal loses the least likelihood, starting from a large seed vocabulary. Because the model is probabilistic, segmentations can also be sampled. Training a translation model on sampled segmentations is what Kudo called subword regularization.
Byte-pair encoding (BPE) and WordPiece are deterministic: a word always gets the same pieces. Kudo's starting point was that the same text admits many segmentations. Hello world could be Hell·o world or H·ello world, and a model that only ever sees one of them learns nothing about the others. Showing the network several segmentations of each sentence works like data augmentation. It makes the model more robust to segmentation noise, which matters most in low-resource and out-of-domain translation, where the paper reported its largest gains. BPE has no probabilities to sample from, so Kudo needed a tokenizer that is a proper probability model over segmentations. The unigram language model is the simplest one.
The direction of construction is also reversed. BPE and WordPiece build bottom-up, starting from characters and adding merges. The unigram method works top-down. It starts with far too many candidate pieces and deletes the least useful until the target size is reached. The SentencePiece library, which Kudo released with Richardson the same year, uses the unigram model by default.
The model and its decoder
- all segmentations of into vocabulary pieces; exponentially many, up to for characters
- probability of piece x, independent of its neighbours (a unigram language model)
- the Viterbi segmentation, used when encoding at inference time
The pieces of form a lattice. Nodes are the character boundaries , and every vocabulary piece is an edge from to with weight . A segmentation is a path from to , and its log-probability is the sum of its edge weights. The best path is a one-line dynamic program:
- log-probability of the best segmentation of the prefix ; a back-pointer to the argmax recovers the path
- cost, with the longest piece (SentencePiece caps pieces at 16 characters by default)
Replace max by log-sum-exp and the same recursion becomes the forward algorithm. It gives , the marginal likelihood of the string. A matching backward pass gives the posterior probability of every edge. Training and sampling both need these.
Training: EM, then prune
For a fixed vocabulary, the segmentations are hidden variables, and the corpus log-likelihood sums over them:
- the training corpus, in practice word types weighted by their counts
- E-step: expected number of times piece is used, summed over all segmentations weighted by their posterior (forward–backward)
- M-step: normalise the expected counts. Each EM round cannot decrease the likelihood
EM fits the probabilities but cannot choose the vocabulary. Kudo handles that greedily. For each piece , define as how much drops when is removed and its probability mass is redistributed. Sort by loss, keep the top (80% in the paper), and run EM again.
The vocabulary loop (Kudo 2018, as implemented in SentencePiece)
- 1Seed. Build a large initial vocabulary from all characters and the most frequent substrings, found with an enhanced suffix array. SentencePiece's default seed size is 1,000,000 pieces.
- 2EM. Fix the vocabulary and re-estimate with a few EM iterations over the lattices of the corpus.
- 3Score. Compute for every piece. SentencePiece approximates it by re-segmenting each occurrence of with the remaining pieces.
- 4Prune. Keep the top of pieces by loss, 80% in the paper and
shrinking_factor=0.75in SentencePiece. Single characters are always kept, so every string remains encodable. - 5Repeat steps 2–4 until reaches the target, for example 32,000, then run a final EM.
Subword regularization: sampling segmentations
- smoothing: is uniform over segmentations, is the model posterior, and always returns Viterbi
- the -best segmentations, or all of when
- exact sampling over the whole lattice by forward-filtering backward-sampling: run the forward pass with weights , then walk back from , choosing each incoming edge with probability
In training, every sentence is re-segmented each time it is drawn into a mini-batch. The encoder and decoder see relat·ing once and re·lating the next time, and occasionally re·l·at·ing. At test time, decoding uses Viterbi again, or the paper's -best variant, which translates several top segmentations and keeps the best-scoring output. With SentencePiece this is two arguments: enable_sampling=True, alpha=0.1, nbest_size=-1, where means . The BPE counterpart came later as BPE-dropout (Provilkov, Emelianenko and Voita, ACL 2020), which randomly skips merges.
Settings and where it is used
- Paper
- Kudo, "Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates", ACL 2018
- Pruning
- keep the top by loss per round (paper);
shrinking_factor=0.75in SentencePiece - Seed
- all characters plus frequent substrings from a suffix array; SentencePiece
seed_sentencepiece_size=1000000 - Piece length
- SentencePiece
max_sentencepiece_length=16by default - Sampling
nbest_size= ( for the full lattice),alpha=- Models
- T5 (32,000 pieces), ALBERT (30,000), XLNet (32,000): SentencePiece unigram vocabularies
- Evidence
- Bostrom & Durrett, "Byte Pair Encoding is Suboptimal for Language Model Pretraining" (Findings of EMNLP 2020): unigram segmentations align better with morphology, and models pretrained on them matched or beat BPE on downstream tasks
Worked example: Viterbi, EM and pruning by hand
Use the figure's vocabulary: , , , , , and . Run Viterbi on related:
| j | prefix | best last piece | best[j] |
|---|---|---|---|
| 1 | r | r | −3.943 |
| 2 | re | re | −2.200 |
| 3 | rel | rel | −4.097 |
| 4 | rela | a (after rel) | −4.097 − 3.809 = −7.907 |
| 5 | relat | relat | −4.790 |
| 6 | relate | relate | −4.279 |
| 7 | related | related | −4.097 |
From one word to the training loop
- 1Decode. At the candidates are
related,relat+ed,relate+d,rel+atedandr+elated. Viterbi keeps the single piece. - 2Posterior. The forward algorithm over all 35 segmentations gives , so , and
relat·edgets . - 3E-step on the corpus
unrelated×4,related×6,relating×3, whose log-likelihood is . The expected count ofrelatedis 9.106 out of 21.501 piece uses: almost fromrelatedplus fromun·related, plus a little fromu·n·related. - 4M-step. goes from to . The 16 pieces that appear in none of these three words drop to zero, and one EM step raises to .
- 5Prune (table below). Remove each piece in turn, renormalise the rest, and recompute . A negative loss means the corpus is more likely without the piece, because its probability mass was wasted on these words.
| piece | loss = L(V) − L(V∖{x}) | η = 80% of 20 multi-character pieces: keep 16 |
|---|---|---|
| related | 23.605 | keep (rank 1) |
| un | 22.771 | keep (rank 2) |
| relat | 2.132 | keep (rank 3) |
| lating | 1.456 | keep (rank 4) |
| ing | 0.774 | keep (rank 5) |
| lat | 0.043 | keep (rank 6) |
| rel | −0.028 | keep (rank 7) |
| re | −0.446 | keep (rank 15) |
| late | −0.463 | keep (rank 16, the last kept) |
| ate | −0.846 | drop (rank 17) |
| at | −0.982 | drop (rank 18) |
| in | −1.535 | drop (rank 19) |
| ed | −1.551 | drop (rank 20) |
Notice that ed is pruned even though it has the second-largest prior count (35). On this corpus Viterbi never uses it, because related covers that ending. Pruning judges a piece by what the corpus loses without it, not by how frequent it looks.
1import math, random2from collections import defaultdict34def lattice(word, logp, max_len=16):5 """All (start, end, piece) arcs whose piece is in the vocabulary."""6 return [(i, j, word[i:j]) for i in range(len(word))7 for j in range(i + 1, min(len(word), i + max_len) + 1) if word[i:j] in logp]89def viterbi(word, logp):10 best, back = [0.0] + [-math.inf] * len(word), [0] * (len(word) + 1)11 for i, j, p in sorted(lattice(word, logp), key=lambda a: a[1]):12 if best[i] + logp[p] > best[j]:13 best[j], back[j] = best[i] + logp[p], i14 pieces, j = [], len(word)15 while j > 0:16 pieces.append(word[back[j]:j]); j = back[j]17 return pieces[::-1], best[-1]1819def logaddexp(a, b):20 if a == -math.inf: return b21 m = max(a, b); return m + math.log(math.exp(a - m) + math.exp(b - m))2223def forward_backward(word, logp, alpha=1.0):24 arcs, n = lattice(word, logp), len(word)25 fwd, bwd = [0.0] + [-math.inf] * n, [-math.inf] * n + [0.0]26 for i, j, p in sorted(arcs, key=lambda a: a[1]):27 fwd[j] = logaddexp(fwd[j], fwd[i] + alpha * logp[p])28 for i, j, p in sorted(arcs, key=lambda a: -a[0]):29 bwd[i] = logaddexp(bwd[i], alpha * logp[p] + bwd[j])30 return arcs, fwd, bwd3132def em_step(corpus, logp):33 """E: expected piece counts over all segmentations. M: renormalise."""34 counts, loglik = defaultdict(float), 0.035 for word, freq in corpus.items():36 arcs, fwd, bwd = forward_backward(word, logp)37 logZ = fwd[-1]; loglik += freq * logZ38 for i, j, p in arcs:39 counts[p] += freq * math.exp(fwd[i] + logp[p] + bwd[j] - logZ)40 total = sum(counts.values())41 return {p: math.log(c / total) for p, c in counts.items() if c > 0}, loglik4243def sample(word, logp, alpha, rng):44 """Forward-filtering backward-sampling: an exact draw from P(x|X)^alpha / Z."""45 arcs, fwd, _ = forward_backward(word, logp, alpha)46 pieces, j = [], len(word)47 while j > 0:48 cand = [(i, p) for i, jj, p in arcs if jj == j]49 w = [math.exp(fwd[i] + alpha * logp[p] - fwd[j]) for i, p in cand]50 i, p = rng.choices(cand, weights=w)[0]51 pieces.append(p); j = i52 return pieces[::-1]5354counts = {c: 2 for c in "abcdefghijklmnopqrstuvwxyz"}55counts.update(e=12, a=8, t=9, n=7, r=7, i=7, l=5, d=5, u=3, g=3, s=6, o=6,56 un=30, re=40, rel=6, relat=3, relate=5, related=6, late=8, lat=4, ate=14, at=20,57 ated=4, ed=35, el=5, ing=30, ng=4, ti=6, ting=5, lating=2, elated=3)58counts["in"] = 2559T = sum(counts.values())60logp = {p: math.log(c / T) for p, c in counts.items()} # 46 pieces, T = 3616162print(viterbi("relating", logp)) # (['relat', 'ing'], -7.2779...)63print(viterbi("unrelated", logp)) # (['un', 'related'], -6.5848...)64rng = random.Random(0)65print([" ".join(sample("relating", logp, 0.2, rng)) for _ in range(4)])66# ['re lat i n g', 'rel at ing', 're l at ing', 'r el at ing']6768corpus = {"unrelated": 4, "related": 6, "relating": 3}69new_logp, ll = em_step(corpus, logp)70print(round(ll, 3), len(new_logp)) # -69.464 30 (16 unused pieces drop out)71print(round(math.exp(new_logp["related"]), 4)) # 0.423572print(round(em_step(corpus, new_logp)[1], 3)) # -28.7827374# The library version (not run here):75# import sentencepiece as spm76# spm.SentencePieceTrainer.train(input="corpus.txt", model_prefix="uni", vocab_size=32000,77# model_type="unigram")78# sp = spm.SentencePieceProcessor(model_file="uni.model")79# sp.encode("relating", out_type=str) # Viterbi80# sp.encode("relating", out_type=str, enable_sampling=True, alpha=0.1, nbest_size=-1)Use when
- +Principled: vocabulary and probabilities chosen by corpus likelihood
- +Multiple segmentations with probabilities: n-best, marginals, sampling
- +Subword regularization improves robustness, especially for low-resource and out-of-domain data
- +Linear-time Viterbi and FFBS on the lattice; default model in SentencePiece
Avoid when
- −Training is heavier than BPE: a large seed vocabulary and repeated EM over lattices
- −Pruning is greedy and its loss is approximated in practice
- −Sampling lengthens sequences and adds a hyperparameter (α, ℓ) to tune
- −Context-free piece probabilities; segmentations can look odd for rare words
Check yourself
In subword regularization with α → 0, what happens to the sampled segmentations?
Check yourself
Why does unigram training always keep single-character pieces when pruning?
Remember
- ✓Unigram tokenization (Kudo, ACL 2018): over pieces. Encoding takes the Viterbi path through the lattice of every vocabulary piece in the string, in .
- ✓Training is top-down: a large seed vocabulary, EM with forward–backward expected counts, then keep the top 80% (SentencePiece: 75%) of pieces by likelihood loss. Single characters always survive.
- ✓Subword regularization samples every time a sentence is seen, exactly over the whole lattice by forward-filtering backward-sampling.
- ✓α interpolates between a uniform distribution (α → 0), the posterior (α = 1) and Viterbi (α → ∞). Use sampling only in training.
- ✓It is the default model in SentencePiece and is used by T5, ALBERT and XLNet.