WordPiece and SentencePiece: Exercises — AI-ML deep dive

Before we begin, three symbols we will lean on constantly — defined in plain words so nothing is assumed:

We will also reuse PMI, the pointwise mutual information of a pair:

Level 4 leans on two words from Expectation Maximization. We define them here so this page stands alone:

Definition E-step and M-step, in plain words

A word like dogs can be split many ways. We do not know which split is "right", and we also do not yet know good token probabilities — a chicken-and-egg loop. Expectation Maximization breaks it by alternating two moves:

E-step (Expectation): hold the current token probabilities fixed and ask "how much does each possible split of each word deserve to be believed?" Score every split, normalize the scores into weights that sum to $1$ , and spread a fractional (soft) count to every token according to those weights.
M-step (Maximization): hold those soft counts fixed and recompute each $P (x)$ = (soft count of $x$ ) / (total soft counts). This is the split that maximizes the likelihood given the counts. Repeat E → M → E → M until the numbers stop moving. Exercises 4.1 and 4.2 walk one E-step and its M-step by hand.

Level 1 — Recognition

Exercise 1.1

Which algorithm uses the marker ▁ (U+2581) for whitespace, and which uses the ## prefix for non-initial pieces? State each.

Recall Solution

▁ is used by SentencePiece. It treats raw text as a stream, so it must encode spaces as a visible symbol to stay reversible.
## is used by WordPiece. It marks a piece that is not at the start of a word (e.g. play + ##ing), because WordPiece is fed already-space-split words and never crosses word boundaries. Answer: SentencePiece → ▁; WordPiece → ##.

Exercise 1.2

True or false: WordPiece merges the pair with the highest raw frequency. If false, state the true rule in one sentence.

Recall Solution

False. That is Byte-Pair Encoding (BPE)'s rule. WordPiece merges the pair with the largest likelihood gain $Δ L = count (ab) \cdot lo g \frac{P ( ab )}{P ( a ) P ( b )}$ — i.e. frequency weighted by PMI, which rewards pairs that co-occur more than chance.

Level 2 — Application

Exercise 2.1

Vocabulary: ["un", "##happ", "##i", "##ness", "happiness"]. Tokenize "unhappiness" with WordPiece greedy longest-match. Give the token list and its length.

Recall Solution

Greedy longest-match starts at position 0 and shrinks the candidate until it hits the vocabulary. WordPiece looks up a word-initial piece bare (no prefix) and a non-initial piece with a ## prefix.

"unhappiness"…"unh" — none in vocab. "un" — found (word-initial). Consume it.
Remaining string is "happiness", but we are now non-initial, so lookups carry ##: "##happiness" — not in vocab. Shrink: "##happ" — found. Consume it.
Remaining "iness": "##iness"…"##ines"…"##ine"…"##in" — none. "##i" — found. Consume it.
Remaining "ness": "##ness" — found. Consume it. Output: ["un", "##happ", "##i", "##ness"], length 4. Note there is no bare happiness reachable here: once we cross the first piece, every later lookup must carry ##, and ##happiness is not in the vocabulary — so greedy longest-match assembles the word from the ##-prefixed pieces instead.

Exercise 2.2

SentencePiece vocab: ["▁", "▁H", "ello", "▁w", "orld"]. Tokenize "Hello world" and then detokenize your output back to a string.

Recall Solution

Tokenize: replace each space with ▁ → "▁Hello▁world". Segment left-to-right: ▁H | ello | ▁w | orld → ["▁H", "ello", "▁w", "orld"]. Detokenize: concatenate → "▁Hello▁world" → replace ▁ with a space → "Hello world". The round trip is exact — that reversibility is the whole point of the ▁ marker.

Exercise 2.3

Compute the PMI-weighted likelihood gain of merging the pair (un, happy) given $count (u nha pp y) = 100$ , $P (u n) = 0.02$ , $P (ha pp y) = 0.01$ , $P (u nha pp y) = 0.004$ .

Recall Solution

$Δ L = count (u nha pp y) \cdot lo g \frac{P ( u nha pp y )}{P ( u n ) P ( ha pp y )} = 100 \cdot lo g \frac{0.004}{0.02 \times 0.01} .$ Inside: $0.02 \times 0.01 = 0.0002$ , so the ratio is $0.004/0.0002 = 20$ . $ln 20 \approx 2.9957$ . Thus $Δ L \approx 100 \times 2.9957 = 299.57$ (using natural log). Positive and large → this pair clings together far above chance (ratio $20 ≫ 1$ ) → a strong merge candidate.

Level 3 — Analysis

Exercise 3.1

A pair (the, cat) is very frequent ( $count = 5000$ ) but $P (t h e) = 0.05$ , $P (c a t) = 0.004$ , $P (t h e c a t) = 0.0004$ . Compute $Δ L$ and explain whether WordPiece merges it before the rarer pair from Ex 2.3.

Recall Solution

$P (t h e) P (c a t) = 0.05 \times 0.004 = 0.0002$ . Ratio $= 0.0004/0.0002 = 2$ . $ln 2 \approx 0.6931$ . $Δ L = 5000 \times 0.6931 \approx 3465.7$ . Numerically this beats Ex 2.3's $299.6$ , so on gain alone WordPiece would merge the cat first. The teaching point: the per-occurrence PMI ( $ln 2 = 0.69$ ) is far weaker than un+happy's ( $ln 20 = 3.0$ ) — the cat only wins because it is enormously frequent. This is exactly why WordPiece is not pure frequency and not pure PMI: it is count × PMI. Contrast with raw-frequency Byte-Pair Encoding (BPE), which would merge the cat even if its PMI were near zero.

Exercise 3.2

Explain, in terms of the Out-of-Vocabulary Problem, why word-level tokenization fails on "antidisestablishmentarianism" while subword succeeds. Reference Morphology and Compositionality.

Recall Solution

A word-level vocabulary is a fixed finite list. Any unseen word maps to a single [UNK] token, destroying all information — that is the OOV problem. Subword tokenization keeps a vocabulary of reusable pieces (anti, dis, establish, ment, arian, ism). Because English morphology is compositional — meaning is built by stacking morphemes — the model reconstructs a rare word from familiar parts and never emits [UNK] for spellable text. Coverage becomes effectively unbounded with a bounded vocabulary.

Level 4 — Synthesis

Exercise 4.1 (SentencePiece Unigram E-step)

Corpus: the single word "dogs", count 1. Vocabulary probabilities: $P (d o g) = 0.40, P (s) = 0.20, P (d o) = 0.10, P (g s) = 0.05, P (g) = 0.10, P (d) = 0.05, P (o) = 0.05, P (d o g s) = 0.05$ . Score every segmentation, normalize, and give the posterior weight of [dog, s] and [dogs].

Recall Solution

Step 0 — enumerate every segmentation systematically. A segmentation is a choice of "cut points" between the 4 letters d o g s. There are 3 possible internal cuts (after d, after o, after g), so at most $2^{3} = 8$ raw splits. We keep only those whose every piece is in the vocabulary. Walk them by number of pieces:

1 piece: [dogs] — in vocab ✓
2 pieces: [d,ogs] ✗(ogs absent), [do,gs] ✓, [dog,s] ✓
3 pieces: [d,o,gs] ✓, [d,og,s] ✗(og absent), [do,g,s] ✓
4 pieces: [d,o,g,s] ✓

Six segmentations survive: [dogs], [do,gs], [dog,s], [d,o,gs], [do,g,s], [d,o,g,s].

E-step scoring — hold the current $P (x)$ fixed; each segmentation's score is the product of its token probabilities (unigram assumption):

[dog, s] $= 0.40 \times 0.20 = 0.0800$
[dogs] $= 0.05$
[do, gs] $= 0.10 \times 0.05 = 0.0050$
[do, g, s] $= 0.10 \times 0.10 \times 0.20 = 0.0020$
[d, o, gs] $= 0.05 \times 0.05 \times 0.05 = 0.000125$
[d, o, g, s] $= 0.05 \times 0.05 \times 0.10 \times 0.20 = 0.00005$

Normalizer $Z = 0.0800 + 0.05 + 0.0050 + 0.0020 + 0.000125 + 0.00005 = 0.137175$ .

Posterior of [dog, s] $= 0.0800/0.137175 \approx 0.5832$
Posterior of [dogs] $= 0.05/0.137175 \approx 0.3645$

The bar chart shows where the posterior mass lands: the two "sensible" splits [dog, s] and [dogs] between them hold about $95%$ of the belief, while the letter-by-letter splits are nearly ignored — exactly the behaviour that lets the M-step drown out useless tokens. The horizontal bars are ordered by posterior weight, with each bar's numeric weight printed at its tip and a coral arrow flagging the two dominant, linguistically sensible segmentations.

Figure: posterior weight $P (seg) / Z$ for each of the six valid segmentations of "dogs"; [dog, s] and [dogs] dominate.

Exercise 4.2 (M-step follow-through)

Using the posteriors from Ex 4.1, compute the expected soft count of token s and of token dog. (The word count is 1, so soft counts are just summed posterior weights of segmentations containing the token.)

Recall Solution

Token dog appears only in segmentation [dog, s]: $E [d o g] = 0.0800/ Z \approx 0.5832.$ Token s appears in [dog, s], [do, g, s], and [d, o, g, s]: $E [s] = \frac{0.0800}{Z} + \frac{0.0020}{Z} + \frac{0.00005}{Z} = \frac{0.08205}{Z} .$ With $Z = 0.137175$ : $E [s] \approx 0.08205/0.137175 = 0.5982$ . The M-step would then renormalize all soft counts into new $P (x)$ . Tokens like do, gs collect almost no mass → they are prime pruning candidates in the next round.

Level 5 — Mastery

Exercise 5.1 (Derive the merge formula)

From the unigram log-likelihood $L = \sum_{i} lo g P (w_{i})$ , derive that merging pair $(a, b) \to ab$ changes the likelihood by $Δ L = count (ab) \cdot lo g \frac{P ( ab )}{P ( a ) P ( b )}$ . Show every case (including where the pair does not occur).

Recall Solution

Assumption (state it up front). During this single-merge analysis we treat $P (a)$ , $P (b)$ , and $P (ab)$ as fixed constants — the probabilities that already hold before we decide to merge. We are only asking "what does this one merge do to $L$ , everything else held still?" (In a full run these probabilities are re-estimated after each merge, but that is a separate step and does not affect this local comparison.) Setup. Only occurrences of the adjacent pair $(a, b)$ change. Each such occurrence currently contributes two independent terms $lo g P (a) + lo g P (b)$ . Before merge — summed over all $count (ab)$ occurrences: $L_{before} = count (ab) [lo g P (a) + lo g P (b)] .$ After merge — each becomes one token $ab$ : $L_{after} = count (ab) lo g P (ab) .$ Difference: $Δ L = L_{after} - L_{before} = count (ab) [lo g P (ab) - lo g P (a) - lo g P (b)] = count (ab) lo g \frac{P ( ab )}{P ( a ) P ( b )} .$ Degenerate cases:

If $count (ab) = 0$ (pair never adjacent): $Δ L = 0$ — nothing to merge, correctly ignored.
If $a, b$ are independent ( $P (ab) = P (a) P (b)$ ): ratio $= 1$ , $lo g 1 = 0$ , gain $= 0$ — merging a chance co-occurrence buys nothing.
If $P (ab) < P (a) P (b)$ (anti-correlated): gain negative — WordPiece would never pick it. $■$

Exercise 5.2 (Design decision)

You must tokenize a corpus mixing English and Chinese (no spaces in Chinese). Choose between WordPiece and SentencePiece-Unigram and justify with two concrete technical reasons.

Recall Solution

Choose SentencePiece-Unigram. Reasons:

No pre-tokenization needed. WordPiece requires whitespace-split input; Chinese has no word delimiters, so a whitespace pre-tokenizer would treat entire sentences as one "word" and fail. SentencePiece consumes the raw byte/character stream directly and is language-agnostic.
Reversibility via ▁. Because spaces are encoded as ▁, detokenization is exact for the English half (leading/trailing spaces preserved), while Chinese — having no spaces — reconstructs perfectly too. This is the exact design used by T5 and mT5. WordPiece (used in BERT Architecture) drops precise spacing and assumes space-delimited words.

Recall Quick self-check (clozes)

The WordPiece merge criterion is count times ::: PMI (log P(ab)/(P(a)P(b))) SentencePiece encodes whitespace with the symbol ::: ▁ (U+2581) The SentencePiece Unigram E-step assigns counts that are ::: soft / probabilistic across all segmentations The gain of merging an independent pair is ::: zero (log 1 = 0)