Finite-State Morphology

Byte pair encoding merges the pair of symbols that occurs most often. The unigram model starts from a large set of pieces and drops whichever is least missed. The method that searches for the set of pieces describing a corpus in the fewest bits is measuring the corpus too, and so is the one that picks the pieces covering the most text.

Every one of them arrives at a vocabulary by asking a body of text a question and reading the answer off, which means every one of them inherits whatever that body of text happened to contain.

That is not a criticism, and it is the reason those methods work on languages nobody on the team speaks. It is a commitment, though, and it is worth being precise about what is being committed to. The pieces are wherever the counts fall. Nothing in any of those methods knows that re is a prefix, that ed makes a past tense, or that bake and bak are the same word spelled two ways, and if the counts put a boundary in the middle of a suffix then the middle of a suffix is where the boundary is.

I wanted a fair look at this and not a rigged one, so instead of fitting a vocabulary on a scrap of text I gave it the friendliest corpus I could construct. The grammar this page builds later accepts 1,074 different words; I put every one of those words in a corpus exactly once and fitted a vocabulary of 178 pieces on it, which is the same number of lines the grammar takes to write. Nothing was held back, nothing was rare, and the words were all inflections of one another.

On three of the six words I looked at the two answers agree. On the other three they part company in a specific way. recovers comes back from the counting as recov and ers, and bakes comes back as bak and es. Both cuts fall one character to the left of where the word is jointed, because ers and es are frequent endings of written words and the counts have no opinion about which characters belong to the stem. measured misses in the other direction, as measure and d, where the grammar says measur and ed because the stem drops its final e.

The other half of it is that the answer moves when the budget moves. At 178 pieces, measured is cut as measure and d; at 356 it is one piece and is not cut at all, and unnamed goes from three pieces to two by absorbing the prefix into the stem. A written grammar answers the same thing at every size, since nothing in it was chosen by counting.

…

The widget above is used again in section 15 for the numbers down its left-hand side. For now the column worth looking at is the right-hand one, which does not change when the button changes.

The alternative is old and it is not complicated. Somebody who knows the language writes down its stems, writes down its endings, and writes down which endings may follow which stems. A word is then read by finding a way of spelling it out of those pieces in an order the writer allowed, and what comes back is not only where the word divides but what each division is doing.

Our sentence has a word of exactly this shape.

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

A reader who knows English sees re-analysis as re in front of analysis, and would say without hesitating that the prefix means again. That reading does not depend on having seen the word before, which is the whole point, and it is the thing a person can write down and a count cannot discover. What follows is what happens when somebody does write it down.

Writing the pieces down is one thing and writing down the order they may come in is another, and the second is what turns a list into a machine. Think of reading a word as standing somewhere, taking some characters, and arriving somewhere else. Where you are standing is not a position in the word; it is a summary of what may legitimately come next, which is why there are only a handful of places to stand however long the word is.

A place to stand is a state. A step out of a state carries four things, and every step reads at least one character.

a step  =  ( state,  spelling,  label,  next state )

One state is where every word starts. One more is the end, and it is not a place with steps out of it; it is the condition that the word has finished exactly here. So reading a word means finding a run of steps that begins at the start, spells the word out with nothing left over, and stops at the end.

a reading  =  steps s₁ … sₖ  with  spelling(s₁) + … + spelling(sₖ) = the word

Here is a grammar small enough to print completely. It has three verbs in it, one of which is also a noun, and their endings. It is 16 lines and 5 states, and I am showing it whole because everything on the rest of this page is this object made larger.

…

Read one line of the table as a sentence. Standing in the start state, read the characters walk, call them the verb walk, and go to the verb ending state. Standing in the verb ending state, read ed, call it a past tense, and the word ends here. That is two steps and it is the whole of reading walked.

Two things in the table are worth noticing now because they are the subjects of sections 8 and 13. Every stem appears twice, once going to an ending and once going straight to the end. And bake appears a third time spelled bak, going to a state of its own.

Now take walked and walk it. The machine begins in the start state at the first character. It looks for a line whose spelling begins there, finds walk, takes it, and is now in the verb ending state at the fifth character. It looks again, finds ed, takes it, and that line says the word ends here, which it does.

The widget below shows that as two rows. The first is each character of the word with the state it was read in written underneath, so the machine stops being an abstraction and becomes something running along the word. The first four characters are read in the start state and the last two in the verb ending state, and the place where the label changes is the place the word divides.

…

Press bakes in the widget above and the search does something more interesting. Four lines are tried. The first takes bake into the state of endings beginning with a consonant, finds s there, and finishes. The second takes bake as a whole word and cannot, since there is an s left. The third takes bak into the state of endings beginning with a vowel, and nothing in that state spells es, so the search backs out.

That third branch is the one worth watching, because it is the machine considering a reading a reader would never entertain and rejecting it for a reason written into the grammar rather than guessed at. Backing out costs nothing here and the section on ambiguity is about the case where it costs a great deal.

In the printed grammar, walk appears once going to the verb ending state and once going straight to the end. That looks like a redundancy and it is not, and the reason is the rule that every step reads at least one character.

English marks the present tense of most verbs with nothing at all, so the natural way to write it is a step that reads no characters and calls them a present tense. Allowing steps like that means allowing a run of them, which means a machine can go round a loop forever without moving along the word, and every walk then needs a check for that. Writing the stem a second time with the end as its next state says the same thing and cannot loop.

Because every step reads a character and none of these states can be reached from itself, the set of words a grammar accepts is finite, and it can be worked out with no word in hand at all by walking every path from the start to the end. The small grammar accepts twelve words, which the widget in section 5 lists in full.

Doing the same to those twelve paths turns up something else. There are fourteen paths and twelve words, so two of the words are spelled by two different paths each. Those two are walk and walks, and they are the subject of section 20.

Every method earlier in this section answers with places. Here is a word, here is where it divides, get on with it. This method answers with places and with names, because every line of the grammar carries a label and a reading is a run of lines, so the labels come out with the pieces at no extra cost.

Set the two side by side on walked. A learned vocabulary says the word is walk followed by ed. The grammar says the word is the verb walk in the past tense, and that the past tense is spelled with the second piece. Those are different kinds of answer, and the second is the one a system doing anything grammatical downstream actually wants.

walked   →   walk+V +PAST

The notation is the one this tradition has used since the Xerox tools, a stem with a part of speech on it followed by the features the endings contributed. It is a string and not a structure because that is what analysers in this family report, and because it sorts, which section 12 needs.

Four words, read by the grammars on this page, with what every piece was identified as underneath it. The last of them, reopeners, is read by the larger grammar of Part 4 and not by the small one, because the small one has no prefixes in it.

…

The fourth is the one to look at. It has four pieces and each of them carries a different kind of claim, since a prefix meaning again, a verb, an ending that turns the verb into the person who does it and a plural on the result are four different sorts of thing to know. Nothing about that reading needed the word to have been seen, and reopeners is not a word I would expect to find in a corpus of any size.

A tokenizer downstream wants pieces and not labels, so the analyser has to be able to hand a word on as a cut. When a word has one reading that is unambiguous. When it has several, one of them has to be chosen, and nothing in the grammar chooses.

So a rule is imported from outside. The reading with the fewest pieces wins; if several tie, the one whose label string sorts first wins; if several still tie, the one whose pieces sort first wins. On walks, both readings have two pieces, and walk+N +PL sorts before walk+V +3SG because the letter N comes before V, so the plural noun is what is handed on.

bake plus ed is bakeed, and English writes baked. A grammar that lists the stem, lists the ending and lets them join has just accepted a word that does not exist and refused one that does, and that is not a small failure since it happens to every verb in the language whose stem ends in an e.

I built the smaller grammar both ways to see it. Before the repair it has 3 states and 12 lines, and it reads bakeed as the past tense of bake while returning nothing whatever for baked. After the repair it has 5 states and 16 lines and does exactly the reverse.

The repair is four lines. A second spelling of the stem, bak, labelled as the verb bake, going to a new state holding only the endings that begin with a vowel; and the full stem redirected to a state holding only the endings that begin with a consonant. What comes back is still bake+V +PAST, so the analysis is right even though the piece on the page is bak.

The small grammar is too small to say anything about cost, so I wrote a larger one. Twenty-four verbs whose stem never changes, twelve more that drop a final e, forty nouns, three prefixes, and the endings. Thirteen of the words are both a noun and a verb, which is ordinary English and not a device. That is 178 lines across 6 states.

Those 178 lines accept 1,074 different words, by 1,184 distinct readings. The ratio is the whole argument for the method, and it is not a coincidence or a property of the numbers I chose; it is what composition does. Every verb reaches every ending, every prefix reaches every stem, and the count of accepted words is therefore roughly a product where the count of lines is a sum.

178 lines,  6 states   →   1074 words,  1184 readings

It is worth saying where the 178 comes from, because the machine actually has 342 steps in it. The stems are written once and named, and a prefix has to lead somewhere, so the stem list appears in two states instead of one. In a real toolchain you write it once and the compiler makes the copy, and a step reading nothing would remove the duplication entirely; here it is a consequence of the rule from section 4.

So 178 lines is what the grammar costs. The fair question is what 178 pieces of a learned vocabulary buy on the same words, and the fairest possible setting for that comparison is the one from section 2, where the corpus is the grammar’s own language with every word in it once.

The grammar reads those 1,074 words in a mean of 2.648 pieces, and never in more than 4. A learned vocabulary of 178 pieces spells them in a mean of 2.943, and holds none of them whole. Those two numbers are close, and their closeness is the finding worth taking away, because it means the sequence length a model downstream would pay is about the same either way. What differs is that every piece in the first number has a label on it and none of the pieces in the second does.

…

The numbers to read this time are the four along the top, which describe the grammar, against the two underneath the buttons, which describe whichever learned vocabulary is selected.

Double the learned budget and the comparison turns over. At 356 pieces the mean falls to 2.071, which is shorter than the grammar’s 2.648, and 37 of the 1,074 words are held whole. Buying that from the grammar is not possible, because the grammar’s pieces are the morphemes and there are as many of them as the words have.

This is the honest place where the method is worse than the obvious alternative, and it is worth stating plainly instead of burying it. If what you want is short sequences, a learned vocabulary gets them by spending memory, and spending memory is easy. A grammar cannot be made to produce a shorter cut without making it describe the language differently, which is not a setting anybody can turn.

Hand the larger grammar busiest and it returns nothing. Not a poor cut, not a cut with a piece marked unknown, not a low score. There is no path through the grammar that spells those seven characters, so the set of readings is empty, and the word is handed on whole because there is nothing else to do with it.

…

This is a different failure from every other method on this site, and the difference is worth being sharp about. A learned vocabulary always answers, because it can always fall back on the characters, so its failures are quiet and look like successes. This one is loud. A word it has not been told about produces an empty answer, and an empty answer is trivially detectable, which means a system built on this can count exactly how often it is failing.

Whether that is better depends entirely on what happens next. If something downstream can fall back on another method, an empty answer is a gift, since it says precisely where the fallback is needed. If nothing can, an empty answer is worse than a rough guess, because a rough guess is at least a sequence a model can read.

Our sentence has seven words in it by the simplest reckoning, and the grammar reads one of them. That one is expect, and it reads it correctly, as the verb expect with nothing after it.

…

Changing how the words are found does not help. Handing the sentence to the annotation rules for English instead of to a rule about spaces gives nine pieces instead of seven, since it separates the contraction and the final stop, and the count of readable pieces is still one. That is because what is stopping the grammar is not the boundaries. It is that Alvarez is a name, Dr. is an abbreviation, the is a word with no parts, and analysis is a stem I did not write down.

Take the punctuation off, lower-case everything and treat a hyphen as a join, and the sentence becomes nine ordinary words of which the grammar reads two, since cost is in the noun list. Every one of those three operations is a decision made outside the grammar and every one of them changes the number, which is worth knowing before quoting any coverage figure at all.

One sentence is too short to measure, so I wrote a paragraph of seventy-six words of plain English about an ordinary subject, wrote it before measuring anything, and did not touch it afterwards. Of the 76 words the grammar reads 7, which is 9.2%; of the 57 different words it reads 7, which is 12.3%.

coverage  =  words the grammar reads  ÷  words in the text

That number is worse than it sounds, and the reason is instructive. The commonest words in English carry no morphology at all. There is nothing in the to analyse, nothing in and, nothing in of, and a grammar of stems and endings has no way to say anything about them except by listing them one at a time. So I listed fifty of them, which is fifty more lines and no more structure, and measured again.

…

Coverage by occurrence goes from 9.2% to 60.5%, and coverage by distinct word from 12.3% to 47.4%. Fifty lines that say nothing interesting bought more than the 178 lines that say something did, on this text, because those fifty words are the ones a text repeats. And 30 different words are still left over, among them busiest, thinned, gone and stallholder, and each of them needs a line, or a spelling rule, or both.

The other failure runs in the opposite direction. Hand the larger grammar recovers and it returns three readings. It is the verb recover with a third person ending; it is the prefix meaning again in front of the verb cover with a third person ending; it is the same prefix in front of the noun cover with a plural ending.

…

All three are real English and I can put each in a sentence. Nothing in the six characters chooses between them, so this is not a defect in the grammar and adding lines will not fix it; more lines produce more readings, not fewer. Across the whole language the larger grammar accepts, 108 of the 1,074 words are read more than one way, which is 10.1%, and that is a grammar with three prefixes and no derivational depth to speak of.

How fast it can grow is easiest to see on a grammar of four lines, a piece of one character and a piece of two, each of which may be followed by another. A word of six characters has 13 readings, of ten has 89, and of twelve has 233. The counts are the Fibonacci numbers, for the reason the widget gives.

readings(n)  =  readings(n − 1) + readings(n − 2)

Every method earlier in this section has an objective. Byte pair encoding maximises a merge count, the unigram model maximises a likelihood, the description-length method minimises a number of bits. Two people running any of those on the same corpus get the same answer, and if they do not, one of them has a bug.

This method has no objective at all. A grammar is a claim about a language, and the question of whether a claim about a language is correct is a question in linguistics rather than in arithmetic. Two competent people will write different grammars for English, and their disagreements will be real disagreements about the language and not differences of tuning. Is recover one morpheme or two? Both answers are defensible, and the grammar on this page holds both at once, which is why it reads the word three ways.

So there is nothing to optimise and nothing to converge to. What can be measured is coverage on a text, and coverage measures the grammar against a text rather than against the language, so a grammar can gain coverage by listing words while getting worse at describing how the language works.

The set of words this method can return an answer for is exactly the set its lines spell. That is a definition rather than a limitation discovered by testing, and it has a consequence that is easy to state and easy to forget. For a word outside that set, the method is not approximately right and it is not wrong. It is undefined, in the way a function is undefined outside its domain.

Every other method on this site is total. Handed anything at all, a learned vocabulary returns pieces, because character pieces are always available underneath. That totality is what lets those methods be scored, since a score needs an answer to score. Here there is nothing to score on busiest, and a system built on this has to decide what an empty answer means before it meets one.

There is a genuine decision attached and it is worth naming. Either the analyser is the whole answer, in which case an unreadable word stops the pipeline and the grammar has to grow until it does not; or the analyser is one of two methods and something else takes over where it returns nothing, in which case what reaches the model downstream is a mixture of labelled and unlabelled pieces, and whatever consumes it has to be built to cope with both.

The other end is undefined in a different way. When a word has several readings, the method is complete and correct and has nothing to say about which of them is meant, because meaning which reading is a fact about the sentence and the grammar never sees a sentence.

Two things follow, and only the second is usually noticed. The first is that a system needing one answer has to import a rule from outside, and the tie rule in section 12 is such a rule and has no argument behind it. The second is that the number of readings is not bounded by anything in the method.

It is bounded by the grammar, and a grammar with a stem that is also a prefix plus another stem multiplies rather than adds; the four-line grammar reaching 233 readings on twelve characters is the extreme case of exactly that shape.

Where the choice matters, the answer is not more lines. It is a model of what words are likely in context, which is a probability and therefore something learned from a corpus, and so the grammar and the counting turn out to be complements rather than rivals. That is what the systems in this tradition do; they produce every reading and rank them with something trained.

A grammar is written once, by a person, for one language. Three separate costs follow from that sentence, and they are the ones that decide whether anybody uses this method instead of the ones earlier in this section.

It does not transfer. The 178 lines here describe English and say nothing at all about any other language, and the work of writing them again for Finnish or Arabic or Swahili is the same work, done by somebody who knows that language. A learned method is retrained by pointing it at a different corpus, which is an afternoon.

Nor does it fill itself in. Coverage is bought a line at a time, as section 19 measured, and no amount of writing reaches a point where the rest follows. Fifty lines took coverage on one paragraph from 9.2% to 60.5%, and the 30 words still left over need 30 more decisions about English, each made by somebody able to make them.

And it goes stale where nothing has been edited. New words arrive in a language continuously, old ones acquire new senses and new parts of speech, and a grammar written five years ago returns nothing for every one of them while reporting no error and looking exactly as correct as it did the day it was written. A learned vocabulary goes stale too, but the repair is to refit it, and here the repair is to find the person again.

Gathered in one place, these are the inputs and questions on which the method stops being defined rather than becoming approximate, with what has to be decided in each case and what turns on the decision. The ones worth a reader’s attention are the decisions, since those are what anybody writing a grammar has to make and nothing in the method makes them.