The Unigram Language Model

Every page in this section carries the same sentence, and this one carries two corpora beside it. The large one is eighteen short sentences of ordinary English about reports and costs and analyses, holding 72 distinct words across 133 occurrences and spelled in 51 symbols. The small one is four words with their counts, low five times, lower twice, newest six times and widest three, which is the example the original subword paper worked through and is small enough that every number on this page can be checked by hand.

Neither corpus contains the sentence.

Dr. Alvarez didn't expect the low-cost re-analysis.

What is being chosen, in both cases, is a set of pieces. Any set that contains every symbol the corpus uses can spell any text written in those symbols, so the question is never whether a vocabulary works but which of the enormous number of workable ones to take. Written out in characters the large corpus is 648 pieces long and the sentence is 45; the smallest vocabulary that can exist on it is 52 rows, one per symbol plus one for anything unspellable.

Byte pair encoding grows the vocabulary. It starts at single characters and repeatedly joins the commonest adjacent pair, so a piece exists because at some step it was the best available join. Nothing later revisits that decision. Once a piece has been added, every later count is taken on a corpus already respelled to use it, which means the whole rest of the run is conditioned on a choice made when very little was known.

Look at what that does on the four words. Merging them to a vocabulary of 22 rows makes newest and low into single pieces, but lower occurs only twice and never gets one; it comes out as lo, then w, then e, then r with its end-of-word mark, four pieces for a word the corpus definitely contains. The pieces are all frequent and the cut is defensible at every step, and yet the finished vocabulary spends four rows on a word it holds and cannot say that spelling it whole would have been better.

The deeper trouble is that the merge list gives one answer and offers no way to ask how good it is. Replay the merges on a word and you get a cut; there is no second cut to compare it with and no number attached to either. That is fine when the cut is the only thing wanted, and it is exactly what fails when a model would learn more from meeting several cuts of the same word.

Kudo’s change is easier to state than it looks. Instead of starting small and adding, start with a vocabulary far larger than anything wanted, give every piece in it a probability, and then remove pieces, a fraction at a time, choosing at each step the ones whose loss would cost the corpus least. A piece survives not because of a step it won long ago but because, right now, with the whole rest of the vocabulary present, the corpus would be measurably harder to spell without it.

That is a statement about the whole vocabulary rather than about one greedy join, and it is only possible because there is now a number to compare. The number is the corpus’s likelihood under the model, which is what the next two parts build.

The model is a table. On the left, every piece; on the right, a probability, and the probabilities over the whole table add to one. Nothing else. To start it off, take every substring the corpus contains, count how often each occurs, and give each one its share of the total count, so a substring seen twice as often begins twice as likely.

On the four words that gives 49 candidates, since those four words have 49 distinct substrings between them once the end-of-word mark is counted as part of the letter it rides on. The commonest is e, which occurs 17 times and gets probability 0.068. The pieces es, est with its mark, s, st with its mark and t with its mark all occur 9 times and all get 0.036.

candidate count = 6 + 3 = 9
coverage score = 9 × 3 = 27

Now the consequence that makes this a different method rather than a different heuristic. If a word is pieces drawn one after another from that table, and the draws do not depend on each other, then the probability of a particular spelling is the product of its pieces’ probabilities. Every way of cutting the word into pieces the table holds is a spelling, so a word does not have a cut; it has a whole set of them, each with a number.

P(spelling)  =  p(piece 1) × p(piece 2) × … × p(piece k)

Products of many numbers below one fall very fast, so everything from here on is done in logarithms, where the product becomes a sum and the numbers stay comparable. A log probability is always at most zero, and less negative means more likely.

log P(spelling)  =  log p(piece 1) + log p(piece 2) + … + log p(piece k)

Take lowest, which the four words never contain, and ask the starting table for every spelling of it. There are 28. The likeliest is lo followed by west with the mark, which takes 46.81% of everything the model gives that word. Next come low with est, and lowe with st, at 20.06% each, and those two are tied exactly rather than nearly, because the frequencies behind them happen to multiply to the same number.

…

The row worth looking at is the fourth. Merging the same four words to a vocabulary of 22 rows cuts lowest as lo, then w, then est with its mark, and that cut is here, ranked fourth, holding 3.10% of the word. It is not wrong; it is one of the 28 and it is a perfectly ordinary member of the list. What merging cannot do is see the other 27, so it cannot notice that three of them are more probable and that one of them is fifteen times as probable.

Switch the widget to lower and the gap is wider. The starting table gives lower spelled whole 92.90% of the word, and the merged vocabulary’s four-piece cut ranks twelfth of sixteen. Switch to newest, which merging does learn whole, and the two agree at 85.45%, which is worth seeing as well, since the point is not that merging is usually wrong.

There are now two different questions about a word and they have two different answers. The first is which spelling is likeliest, which is a maximum over the list. The second is how probable the word is at all, which is the total over the list, since the model could have produced the word by any of those routes and they are alternatives rather than requirements.

P(word)  =  Σ over spellings s of the word   P(s)

The total is never below the maximum, and the two are equal exactly when the word has one spelling only. Dividing one spelling’s probability by the word’s total gives that spelling’s share, which is what the widget above prints, and the shares over a word’s spellings add to one. Those shares are the thing Kudo wanted in the first place, since drawing a spelling in proportion to its share is exactly how a model gets to see several cuts of one word.

Twenty-eight spellings for a six-symbol word is already too many to list at any real scale, and the count grows roughly like two to the power of the word length. Nothing is enumerated in practice, and the reason nothing has to be is a change of view. Stop thinking about which pieces a word is made of and think instead about the positions between its symbols. A word of six symbols has seven positions, numbered 0 to 6, and a piece is a step from one position to a later one.

…

A spelling of the word is then a walk from position 0 to position 6 taking any steps available, and the count of walks is the count of spellings. Seventeen pieces of the starting table span a pair of these positions, and those seventeen steps admit exactly 28 walks. The picture is worth the paragraph because it converts a question about sets of pieces into a question about paths through a small graph, and paths through a graph are something we know how to search without listing them.

Here is the observation the whole search rests on. Suppose we already know, for every position, the best score achievable over the rest of the word from that position onward. Then the best score from a position is found by trying each piece that starts there, adding its log probability to the already-known best score of wherever that piece ends, and taking the largest. The best score for the whole word is the answer at position 0.

best(i)  =  max over pieces p starting at i   [ log P(p) + best(end of p) ]

The score at the last position is zero, since spelling nothing costs nothing, so the table is filled from the end of the word backwards and each entry only ever reads entries to its right. Recording, alongside each best score, how long the winning first piece was is enough to read the spelling itself back off the table afterwards, walking forward from position 0.

Replacing the maximum with a sum answers the other question at the same cost. Where the first recurrence keeps the best route into each position, the second keeps the total over all routes into it, and its last entry is the probability of the word. Both are one pass over the same arcs.

total(j)  =  Σ over pieces p ending at j   total(start of p) × P(p)

Two spellings can reach exactly the same score, as low with est and lowe with st do above, and then the recurrence has to be told what to prefer. The first rule is fewer pieces, which is the one worth having, since a model reading the answer pays per piece. The second, for a tie that survives the first, is the longer piece at the earliest position where two spellings differ.

A third rule sounds necessary and is not, and the argument is short enough to give. If two spellings agree up to some position and their pieces starting at that position have the same length, then those pieces span the same symbols, so they are the same piece, so the spellings have not yet differed after all. Two rules therefore settle every case, and the reason the recurrence runs from the end of the word rather than the start is that this reading falls directly out of it.

The work is worth stating plainly, since it is charged once per word every time anything is encoded. For a word of n symbols there are about n squared over two spans to consider, and looking each one up means joining the symbols it covers, which is itself work proportional to its length. Done in the most direct way, that is proportional to n cubed for one word.

Words are short, so this is not the reason anything on this page is slow. The usual repair, where it matters, is to hold the pieces in a structure that lets the spans starting at a position be enumerated in one walk, which takes the cost to n times the length of the longest piece. That is an optimisation of this search rather than a different search.

Everything so far assumed the table. The frequencies it was seeded from are a reasonable start and they are not the answer, because they count every occurrence of every substring including the ones that overlap, and a word was in truth produced by one spelling rather than by all of them at once. What we would like is the probability of each piece given how the corpus was actually spelled, and how the corpus was actually spelled is precisely what nobody observed.

That shape of problem has a standard treatment. Guess the probabilities, work out what the hidden thing probably was given the guess, then re-estimate the probabilities as though that were what happened, and repeat. Each round raises the corpus’s likelihood or leaves it alone, so the walk climbs and settles, though it settles at a local maximum rather than the best one that exists.

The first step asks how often each piece was probably used. For a piece spanning two positions of a word, the chance that the word’s spelling went through that arc is the total over routes reaching its start, times the piece’s own probability, times the total over routes finishing from its end, divided by the total over all routes through the word.

The second recurrence of section 9 supplies the first of those and its mirror running the other way supplies the third. Multiply by how often the word occurs, add up over the corpus, and every piece has an expected count.

expected count of p  =  Σ over words w   count(w) × P(the spelling of w goes through p)

The second step is a division. Give each piece its share of the expected counts, which are no longer whole numbers but are otherwise exactly what counting would have produced had the spellings been visible.

…

The panel above works the smallest corpus that has a choice in it. One word ab, seen once, with the three pieces a, b and ab all at a third. The word can be spelled whole at a third or in two pieces at a ninth, so the word’s own probability is four ninths and the one-piece spelling holds three quarters of it.

The expected counts are therefore 0.75 for ab and 0.25 each for a and b, adding to 1.25, and the division gives 0.6, 0.2 and 0.2. A second round takes the whole spelling to 0.882.

The second panel is where I found something I had not expected. Run the same two steps on the four words and the model does not merely improve, it becomes certain. Low spelled whole goes from 0.020 to 0.265 to 0.312 and then stops, at exactly five sixteenths, which is the share of the corpus that word occupies.

Meanwhile lo, which no occurrence needs, goes from 0.028 to 0.011 to 0.000134 and keeps falling. The likeliest spelling of lowest never changes, and its score falls from −7.30 to −9.45 to −18.39 to −36.75 to −73.50, roughly doubling every round.

Now the question the whole method turns on. Take one piece out of the table and ask how much worse the corpus gets. For every word whose likeliest spelling uses that piece, spell it again with the piece gone, and add up the fall in score, weighted by how often the word occurs. A word whose likeliest spelling did not use the piece contributes nothing at all, because its best route is untouched.

loss(p)  =  Σ over words w whose best spelling uses p   count(w) × [ best score with p  −  best score without p ]

That last observation is what makes the step affordable. There is no need to re-spell the whole corpus once per candidate piece, only the words that were actually using it, and on any real corpus most pieces sit in the likeliest spelling of very few words.

…

On the four words the answer is stark. Four pieces carry the entire corpus. Dropping newest costs 91.26 nats of likelihood, low costs 85.04, widest 45.63 and lower 34.02, and those four are the four words themselves. On the eighteen sentences the ranking is the frequency ranking of the corpus’s own words, with the at 339.32, capitalised The at 229.02, was at 187.94, expected at 88.02 and analysis at 85.65.

The measurement that surprised me is in the readouts above rather than in the bars. On the four words, 34 of the 38 pieces the pruning is allowed to touch cost exactly zero. On the eighteen sentences it is 745 of 815, which is 91% of them. These are not small numbers rounded down; they are zero to the last bit, which means the objective has no preference at all about whether those pieces stay.

There are two ways a piece gets there and both are ordinary. It may lie on no word’s likeliest spelling, in which case removing it changes nothing by construction. Or it may lie on one, and the spelling that replaces it may be exactly as probable, which happens whenever two arcs cover the same symbols at the same total score. Either way the objective is indifferent about whether that piece stays.

So the ranking that decides which pieces survive separates a handful of pieces from each other and leaves the great majority tied at the bottom, and among those the order has to come from somewhere else. Here it comes from alphabetical order, which is arbitrary and at least repeatable. Ask the four words for 22 tokens and the six pieces kept above the four words themselves are de, des, dest, er, es and est, which are the first six in alphabetical order among 34 candidates the objective could not tell apart.

The starting vocabulary is every substring the corpus contains, up to a length bound, and on these two corpora the bound never bites, so the number is a fact about the corpus. The four words supply 49 candidates. The eighteen sentences supply 866, which is worth pausing on, since the vocabulary they end at is 137 and the alphabet alone is 51.

A large seed is not a cost to be minimised. Everything the method can ever choose has to be in it, so a seed that is too small removes options before any evidence has been consulted, which is the very failure the whole design was arranged to avoid. At a real scale the seed is capped, typically at a few times the target size, and that cap is the one place where a piece is discarded on frequency alone.

The pieces are not removed one at a time, and the reason is that the losses were all measured against the same table. Remove one piece and every other piece’s loss is in principle different, since a word that had been leaning on the removed piece now leans somewhere else. Recomputing after every removal would be correct and would cost a full pass per piece, so instead a fixed share is dropped at once and everything is re-estimated before the next round.

…

Each round keeps three quarters of what is there, or the size asked for if that is larger, so the fall is geometric until the last round lands on the target exactly. The four words go 49, 36, 27, 20, 15 in four rounds. The eighteen sentences go 866, 649, 486, 364, 273, 204, 153, 136 in seven. Two rounds of re-estimation run before every size check, so the probabilities reported at the end were estimated on the pieces reported at the end.

Two things stop the shrinking. The obvious one is reaching the size asked for. The other is that a single symbol is never a candidate for removal, whatever it costs, because a vocabulary that cannot spell every symbol the corpus uses assigns some word a probability of zero and the whole corpus a likelihood of zero, at which point nothing can be compared with anything. Asking for fewer rows than the alphabet has is therefore refused rather than approximated.

Here is the result I did not predict, and it is the most informative thing on the page. Take the eighteen sentences, ask for 100 tokens, and look at what the 48 pieces above the alphabet actually are. Every single one of them is a whole word of the corpus with its end-of-word mark, and there is not a stem or a suffix or a frequent letter pair among them.

At 80 the same thing holds for all 28, and only at 137, once the corpus has run short of words to buy, do 15 pieces appear that are something else, among them Augus and the apostrophe followed by t.

A merge-grown vocabulary of the same size is nothing like it. At 100 tokens it holds 8 whole words among its 48 learned pieces and the rest are fragments, and at 137 it holds 18 of 85. Given the same corpus and the same budget, one method spends 48 rows of 48 on words and the other spends 8.

The honest comparison is at matched sizes, since the two methods reach different vocabularies at the same budget and neither can be given the other’s. Fit both on the eighteen sentences at fourteen sizes and count two things at each, what the corpus costs in pieces and what the one held-out sentence costs.

…

On the corpus the shrunk vocabulary wins everywhere and wins by a lot. At 80 tokens it reads the corpus in 324 pieces against merging’s 414; at 137 it reads it in 133 against 263, which is a little over half. And 133 is the floor, since the corpus holds 133 word occurrences and one piece per word is the fewest pieces any vocabulary can achieve. It reaches that floor at 130 tokens and merging never comes near it.

On the held-out sentence it loses everywhere, and this is the place on the page where the method is worse than the thing it is usually offered against. At 80 tokens the shrunk vocabulary reads the sentence in 40 pieces where merging reads it in 28. At 137 the gap narrows to 28 against 25 and it never closes.

The same property is behind both columns. A vocabulary of whole words is unbeatable on the words it holds and has almost nothing to offer a word it does not, so the sentence’s expect, which the corpus never wrote without its ending, comes back at 137 as six single letters.

It is worth seeing the pieces themselves rather than the counts, since the two kinds of mistake look completely different.

…

At the smallest vocabulary neither method has learned anything and both hand back 45 single symbols. At 80 the shrunk vocabulary has picked up the and cost, which are corpus words that happen to appear in the sentence, and everything else is still letters. Merging at the same size has exp, ec, lo, re and analysi, none of which is a word, and reads the sentence in 28.

At 137 the shrunk vocabulary manages Dr. and the and analysis with its full stop, three whole words of the corpus, and the hyphenated -cost, which is the tail of high-cost. It still spells expect letter by letter, because the corpus only ever wrote expected. That is what a vocabulary made of whole words does when it meets a word it has not got, and it is why the three-piece gap in the counts above sits where it does.

Gluing pieces back is mechanical. Concatenate them, then turn every end-of-word mark into a space. The marks are inside the pieces, so no separate record of where the spaces were is needed, and the round trip is exact on any text spelled entirely in symbols the corpus taught. The control sentence, which is written in exactly those symbols, reads as 9 pieces at a vocabulary of 137 and comes back exactly.

The running sentence does not come back, at any size, and the reason is precise. The corpus contains the letter z, in the word size, but no word in it ends in z, and a word-final letter is a different symbol from the same letter inside a word. Alvarez ends in the symbol the corpus never wrote. The encoder hands back its stand-in row, the stand-in carries no end-of-word mark, and gluing the pieces therefore loses the space that was attached to it.

Alvarez didn't   →   Alvare[UNK]didn't

The name says the assumption out loud, which is unusual and is worth crediting. A unigram model over pieces is a model in which each piece is drawn without reference to the pieces around it, so the probability of a spelling is a product with no conditioning in it anywhere. That is false about language in the most obvious way available. The probability that the next piece is ing depends enormously on whether the piece before it was play or the.

Two consequences follow and they are different in kind. The first is that the model’s probability for a word is not a serious estimate of anything, and nothing on this page or in the method treats it as one; it is a score used to compare spellings of the same word and to compare vocabularies, both of which are relative judgements the independence assumption affects far less.

The second is that the assumption is what makes the arithmetic a dynamic programme at all. A model in which a piece depends on the one before it would need a state per piece at every position and the lattice would grow by that factor.

So the assumption is not a shortcut that could be dropped for more accuracy at more cost. It is what buys the search, and any richer model is a different method rather than this one tuned up.

Part 1 said that merging is greedy and never revisits a piece it added. It is worth being exact about what shrinking fixes and what it does not, because the improvement is real and smaller than it first looks. Each removal here is chosen with the whole current vocabulary in view, which is genuinely better than choosing a join with almost nothing in view. But a piece once removed is gone, and its loss was computed while every other piece was still present.

The case that shows the gap is a pair of pieces that stand in for each other. Suppose two pieces cover the same ground, so that with both present each is nearly free and both are ranked near the bottom. Drop one, and the other has become valuable; drop them in the same round, as a round dropping a quarter of the table well might, and the corpus loses something neither loss predicted.

Nothing in the procedure reconsiders the second in the light of the first having gone, and nothing brings a dropped piece back if it turns out to have been needed.

The measured shadow of this is section 15. When 91% of the removable pieces on a corpus price at exactly zero, a great many of them are zero because something else is there, and the ranking cannot distinguish those from the ones that are zero outright. Making the rounds smaller reduces the exposure and makes the fit proportionately slower, and there is no setting at which the effect is absent.

The objective is the corpus’s probability, and the thing anybody actually wants is a vocabulary that reads new text well. Those are different quantities and the page has already measured them coming apart, in section 19, where the vocabulary that halves the corpus reads the held-out sentence three pieces longer than its rival at the same size.

A sharper version of the same gap is available inside one vocabulary, and the lattice of Part 3 is what makes it easy to ask about. Leave the arcs exactly where they are and give every one of them a cost of one instead of a log probability, and the same recurrence answers a different question, which is the fewest pieces this vocabulary can spell the word in.

Sequence length is what everything downstream pays in, so that is a reasonable thing to want, and there is no reason the two answers have to agree, since two common pieces can outscore one rare one.

I expected them to disagree often and measured it rather than asserting it. Over 88 words at a vocabulary of 200, comprising every word of the corpus and sixteen held-out ones, exactly one comes out longer than it needed to be.

One word in 88 is not a crisis, and the small number is the honest finding here rather than a disappointing one. What it shows is that on this corpus likelihood and length agree almost always without being the same thing. Making the count the objective on both sides, so that the vocabulary is chosen to keep the corpus short and the cut is the shortest one that vocabulary allows, is a separate method with its own answers, and the arithmetic it needs is the arithmetic already on this page with the arc costs changed.

The other half of the gap has no measurement here and I will not pretend otherwise. Whether these pieces make a better input for a model to learn from is a question about the model, not about the tokenizer, and nothing on this page trains one.

Gathered in one place, these are the inputs on which the method does not become approximate but stops being defined, together with what has to be decided in each case and what turns on the decision. Several of them are genuine open choices with defensible answers on both sides, and those are the ones worth a reader’s attention, since they are the decisions anybody implementing this has to make and nothing in the mathematics makes them.