Morfessor

Every page in this section carries the same sentence, and this one carries a very small corpus beside it, because the argument needs words we can already agree about. Three verbs in four forms each, walk and talk and play, with the bare stem and the three endings s, ed and ing, twelve words in all, each occurring three times. These familiar forms give us an intuitive linguistic reference: walking contains the stem walk and the ending ing. We can compare learned pieces with that reference while remembering that a compression objective is not itself a test of grammatical correctness.

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

The sentence comes back in Part 6, read by tables fitted to eighteen sentences of ordinary English. The twelve forms are where the mechanism is worked out, because they are small enough that every number below can be checked. Their familiar structure also makes it easier to see when the statistical objective prefers a different split from the linguistic one.

Grow a vocabulary on those twelve words by the usual rule, which is to start from single characters and repeatedly join whichever adjacent pair occurs most often. The twelve forms use 13 distinct characters, which comes to 15 symbols once a character that ends a word is held apart from the same character inside one, so the smallest table is 16 rows and every row after that is bought by a merge.

…

The first four rows bought are al, alk, la and pla. Every one of them cuts a stem somewhere inside it. The reason is not subtle. In walk and talk, and in every form built on either of them, the letters a and l sit next to each other, which is eight of the twelve words, and the counting finds no pair that occurs more often than that.

So a joins l, and then al joins k, and by the third row the play forms have contributed la. Nothing in the counting has any way of preferring the boundary between walk and ing to the boundary between w and alk.

That could be an artefact of twelve made-up words, so here is the same thing on eighteen sentences of ordinary English about reports and costs and analyses, 72 distinct words across 133 occurrences, grown to the point where no adjacent pair occurs twice any more, which is 135 rows. The pieces it holds are the frequent substrings of those eighteen sentences, and where they fall relative to a word’s parts is not something the fit had an opinion about.

Two of those are worth pausing on. The merge-grown table cuts lowest into lowe and st, which puts the cut one letter to the left of the joint, and costs into co and sts, which puts it two letters to the left. Both are frequent substrings of that corpus and neither is a part of anything. On the running sentence the same table reads analysis with its full stop as analysi followed by s with the stop attached, and reads the first half of low-cost as lo followed by w.

It would be easy to conclude that counting is simply the wrong rule, and that is not it. The rule is doing exactly what it promises, which is to buy the row that removes the most pieces from the corpus right now. What it lacks is any notion that a set of pieces has a price of its own.

Every row costs the same as every other row, one, so the only thing left to compare is the saving, and a piece that spans a joint saves just as readily as one that respects it.

Suppose instead that a set of pieces had a price which depended on what the pieces were. A short list of pieces that recur all over the corpus would then be cheap, and a long list of pieces each used once would be dear, and the arithmetic itself would have a reason to prefer walk and ing over w and alk, since alk turns up in eight words but leaves a stray w or t outside it in every one of them, and those strays have to be paid for too.

That is the idea the rest of this page works out, and the work is in making “price” mean something exact.

Imagine having to send somebody the twelve forms over a wire that charges by the symbol. One way is to spell each word out. That needs no list of pieces at all, and it spells walk four times over, once inside each of walk, walks, walked and walking, and spells talk and play four times each as well. The other way is to send a list of pieces first, and then send each word as a run of references into that list. Now walk is spelled once, and walking is two references.

Neither is obviously better, and which one wins depends on numbers. The list has to be paid for, and every reference has to be paid for, and a piece that is used once has cost us a place in the list to save nothing. Creutz and Lagus took that arithmetic seriously and made it the definition. The best set of pieces is the one for which the list plus the text, added together, is shortest.

The message has three parts and it is worth naming them before any formula. The first spells every piece of the list out, one character at a time, with a marker after each so a reader knows where one spelling stops. The second says how often each piece is used, since a reader who is about to decode references needs to know what they are worth.

The third is the corpus itself, written as a run of references, where a piece that is used often is cheap per use and a piece that is used once is dear every single time.

description  =  spelling the list  +  writing the counts  +  writing the text

The first two together are the price of the list, and they fall as the list gets shorter. The third is the price of the text, and it rises as the pieces get smaller, because smaller pieces mean more references. Section 8 prices both of them on the twelve forms and watches the two move against each other.

The smallest corpus with a real decision in it is two words, walk and walks, once each. Left whole the list holds two pieces and the text is two references. Split, the list holds walk and s, the text is three references, and walk is now used twice.

Look at which part paid for which. Splitting made the text dearer, by 0.5232, and made the counts dearer, by 0.6931. It made the spelling cheaper by 7.2103, because walk stopped being written down twice. On a corpus of two words the shared stem already pays for the split, and it pays out of the spelling.

With twelve words rather than two we can price the two extremes and something in between, and see the shape. Give every word a piece of its own and the text is as short as it can be, 36 references for 36 word occurrences, while the list is as long to write out as it can be, 78 symbols.

Give every character a piece of its own and the list is as cheap to spell as it gets, since each of its 13 pieces is one character, while the text has swollen to 198 references. Between them sit the three stems and the three endings.

…

Spelling the list falls all the way across the panel, from 191.7754 to 51.3662, and writing the text rises all the way, from 89.4566 to 474.8646. A quantity whose two components move monotonically in opposite directions has its smallest value somewhere in the middle, and here that is the middle bar, at 185.4634 against 301.0812 for one piece per word and 569.3002 for one piece per character.

Writing the list out means writing its characters, and the cheapest way to write a stream of symbols whose frequencies are known is to give a symbol that occurs often a short code and a symbol that occurs rarely a long one. The length that comes out of doing that as well as it can be done is fixed by the frequencies alone, and it is the expression below, where L is how many symbols the whole list contains and each n is how many times one symbol occurs in it.

spelling  =  L log L  −  Σ over symbols  n log n

The symbols counted here are the characters of the pieces plus one end marker per piece, since without the markers a reader cannot tell where one spelling stops and the next begins. The frequencies used are the frequencies inside the list, not inside the corpus, which matters because a piece appears in the list once however often the corpus uses it.

total length L = 9 + 2 = 11
Σ count × ln(count) = 4 × (2 ln 2) + 1 ln 1 + 2 ln 2
                   ≈ 6.93147
L ln L = 11 ln 11 ≈ 26.37685
spelling cost ≈ 26.37685 − 6.93147 ≈ 19.4454

A reader who has the list still cannot decode a reference without knowing what the pieces are worth, so the counts have to be sent as well. There are N references in the corpus altogether and M pieces, and every piece is used at least once, so the counts are one particular way of dealing N things into M non-empty piles. There are exactly as many such ways as the binomial coefficient below, and saying which one it is costs its logarithm.

counts  =  log C(N − 1, M − 1)

It is the smallest of the three parts on every lexicon this page prices, 15.6828 out of 185.4634 for the three stems and three endings, and it is not decoration. It is what stops a list of many rarely used pieces from looking free, since the number of ways to deal the references grows with the number of piles.

The last part is the corpus itself. Each of the N references is written under the simplest possible model, which is that the chance of a piece is how often it occurs divided by N, with no attention paid to what came before it. Writing one reference to a piece used c times then costs the logarithm of N minus the logarithm of c, and summing that over every reference gives the expression below.

text  =  N log N  −  Σ over pieces  c log c

So a piece used 12 times out of 63 costs 1.6582 every time it is used, and a piece used once out of 63 costs 4.1431 every time, which is to say once. The model behind this is the crudest one available, since it says that a piece is as likely after ing as after walk, which is plainly false about language.

It is the part of the arithmetic most obviously open to improvement and the part this family of methods leaves alone, because a model with memory makes the search inside it much harder.

With the three parts written down, the definition is complete and it is worth being precise about what has been defined. A set of pieces has been given a number. Any two sets of pieces can now be compared, including sets nobody would ever propose, and the comparison is arithmetic rather than judgement. That is a great deal more than the counting rule had, since the counting rule can only compare two candidates at the same vocabulary size.

What has not been defined is any way of finding the best set. The number of ways to cut twelve words into pieces is the product over words of two raised to the number of positions between characters, which is two to the fifty-fourth power for these twelve, and there is no known way to search it exactly. So the criterion and the search are two separate things, and everything true about one of them can be false about the other.

The search Creutz and Lagus proposed is about as simple as a search can be. Begin with every distinct word as a piece of its own, which is one of the two extremes Part 2 priced. Then take the words one at a time, in a shuffled order, and for each one ask whether the description would be shorter with that word cut somewhere. Keep going in passes until a pass barely changes the total.

The important detail is that a word is reconsidered with everything else exactly as it currently stands. Its current pieces are taken out of the books, the word is put back whole, and the question is asked against the list as the other eleven words have left it. So an early decision about walked changes what the arithmetic says about walking, and the order the words are visited in is a real input, which is why the order is drawn from a seed and the seed is part of the fit.

Asking whether one word should be cut is a small procedure with one recursive step. Price the description with the word left whole. Then, for each of the positions between its characters, price the description with the word replaced by the two halves that position makes, and keep the cheapest. If no split is strictly cheaper, the word stays whole and we are done with it. If one is, take it, and then ask the same question of each half.

Two things in that are choices rather than consequences. A split has to be strictly cheaper, so a candidate that changes nothing is refused, which keeps a fit from wandering between equal descriptions forever. And when several positions are equally cheap the earliest wins, which is arbitrary and has to be stated somewhere or two runs of the same procedure disagree.

Run that on the twelve inflected forms and it works. The description goes from 301.0812, which is every word whole, to 185.4634, and the pieces it settles on are exactly walk, talk and play, used 12 times each, with s, ed and ing used 9 times each. Every training word comes out as a bare stem or as a stem followed by an ending, and 63 references replace 36 much longer spellings.

It takes two passes, and the second one finds nothing. The first pass already reaches all six pieces, and the second is what lets the search know it has stopped moving, since the test for stopping is that a pass changed the total by very little. Every seeded visiting order tried reaches the same six.

On the eighteen sentences the walk is longer and it is worth watching, because a pass does not only add pieces. Fitted with the text half of the cost weighted at a quarter, which Part 6 explains, the search takes eight passes and the list shrinks from 67 pieces to 57 while the total falls from 1391.8737 to 976.7130.

…

The churn is the part worth seeing. The second pass gives up carries, dropped, first and greed in favour of carrie, dropp, fir and gre, which is what cutting one word does to the pieces of another, since taking a word’s spelling out of the books changes the price of every spelling that is left. The fourth pass gives up Dr, Every, Monday, Nobody and Tuesday, all of which had survived three passes, because by then the list has enough short pieces to spell them from.

A fitted list has to read words it never saw, and the rule for that is separate from the rule that learned it. Take the word, consider every way of cutting it into pieces the list holds, and take the way whose total price under the same reference cost is lowest. That is a shortest-path problem over the positions in the word and is solved exactly rather than greedily.

A character no piece covers is allowed through as a piece of its own, at a price deliberately set higher than any reading made entirely of known pieces could reach, which is the length of the word times the logarithm of the number of references, plus one. That guarantees a known reading always wins where one exists, and it is why jumping costs 121.9537 where walkings costs 5.5500. The four unknown characters are what the price is reporting.

Here is the finding that changed how I read this method. Take the same twelve inflected forms, change nothing about them, and write each one five times instead of three. More data, in the ordinary sense, of exactly the same kind. The search now leaves every single word whole and finds no pieces at all.

This is not a case of the answer getting slightly worse. At five occurrences each the fit reports twelve pieces, which are the twelve words, at a description length of 367.2274. The list of three stems and three endings, on that same corpus, has a description length of 262.9413. So the search finished 104.2861 nats away from a list it was free to report, and the criterion it is named after says that list is the better of the two.

Go back to what a split does to each of the three parts. It makes the list cheaper, because a piece stops being spelled inside several words. It makes the text dearer, because one reference becomes two. Now ask what happens to each of those when every word occurs more often.

The saving on the list does not move at all. A piece is spelled in the list once, whatever its count, so removing a duplicated spelling saves the same number of nats whether the words occurred three times or three thousand. The extra cost on the text grows with the counts, since every occurrence of the word now pays for one more reference than it did.

One side of the trade is flat in the counts and the other side is linear in them, so there is a count above which the trade stops paying.

list saving   fixed in the counts
text cost     grows with the counts

On these twelve words that crossing point sits between four occurrences each and five. At four, the best available cut is worth 0.3771 nats and the search takes it. At five it costs 1.7333 and the search refuses it, correctly, since taking it really would make the description longer.

There are exactly 54 ways of cutting one of the twelve words in two, which is the whole set of moves available from the starting position. Pricing all of them at both repeat counts shows the stall from the other side.

…

At three occurrences each, 9 of the 54 lower the description and the search has somewhere to go. At five, none of them do. The whole field has slid to the right of the line, so whichever word the shuffled order visits first, and whichever position it considers, the answer is that the word stays whole. The first pass changes nothing, the stopping rule notices that nothing changed, and the fit reports itself finished after one pass.

Three moves tie for cheapest at every repeat count, since cutting played into play and ed, playing into play and ing, and plays into play and s each leave the list holding the same characters and the text holding the same counts. Ties like that are why the recursion needs a stated rule for choosing among equally cheap positions.

The dearest move at three occurrences is worth looking at too. Cutting walks into wa and lks costs 14.2842 nats, which is far more than the cheapest move saves, and it is dear for the reason the whole method rests on. Neither wa nor lks is shared with anything, so the list gets no shorter, and the text gets a reference longer for nothing.

Since the problem is that the text half of the cost grows too fast, the repair offered by every implementation of this method is to multiply that half by something. Set the multiplier below one and the text counts for less, so splits stay worth making at higher counts. Set it above one and the fit splits less.

total  =  list  +  weight × text

…

On the five-occurrence corpus the answer changes between 0.83794 and 0.83795. Anywhere below that the search finds the three stems and the three endings; anywhere above, every word stays whole. At half, which is a setting somebody might well choose without knowing any of this, the fit lands on the six pieces and reports 169.4115.

It has to be said plainly what that number is and is not. It is not comparable with 262.9413, because a different quantity is being minimised once the multiplier is not one. The multiplier is not part of the principle at all, and turning it is admitting that the two-part code, as written, prices frequent words wrongly for this purpose.

Set at half it recovers walk, talk, play, s, ed and ing from a corpus where the plain code recovers nothing, and it does that by declaring that a reference costs half what writing it down actually costs, which is a statement nobody can defend from the coding argument that produced the criterion.

Everything downstream of a tokenizer pays in pieces, so that is the currency to compare in. On the twelve forms the six pieces and their marked twins make a table of 13 rows, and that table reads the corpus in 63 pieces. A merge-grown table needs 30 rows to reach the same 63.

That comparison flatters the shorter description, and it does so for a reason worth naming rather than hiding. The 13 rows are only the pieces the corpus needed. They do not include the alphabet, so there is no row for most single characters, and the next section is what that costs.

Here is where this method is worse than the one it is being compared with, and it is worth reporting rather than burying. Nothing in the criterion rewards keeping a piece for a character no word needs on its own. On the eighteen sentences the letter k never survives as a piece of its own, because every word that uses it can be spelled from longer pieces, and the same is true of almost every letter at the settings that give the most compact description.

…

The three readings are the whole trade in one place. The first table describes its own eighteen sentences in 167 pieces where the merge-grown table of the same 135 rows needs 267, and it can spell 4 of the corpus’s 35 characters on their own against the merge-grown table’s 34. Handed a sentence it never saw, it returns 18 stand-ins out of 28 pieces where the merge-grown table returns 1 out of 25, and gluing its pieces back does not give the sentence back.

Turning the multiplier down to a quarter fixes it, and the way it fixes it says what was wrong. At a quarter the text half counts for so little that keeping single characters becomes affordable, the list holds 34 of the 35 characters, the sentence comes out in 31 pieces with no stand-ins at all, and gluing them back gives exactly what went in. The price is that the eighteen sentences now take 338 pieces rather than 167.

Setting the two side by side on the eighteen sentences, at 135 rows each, the honest summary is that they are ahead in different places and neither dominates.

The name says minimum description length, and the search returns a local minimum of a function over a space it can only move through one cut at a time. Those are different objects, and Part 5 measured the difference on a corpus small enough to hand the better answer to, where it came to 104.2861 nats.

Nothing about that is peculiar to the corpus. The space of ways to cut a word list into pieces is astronomically large, no exact search over it is known, and the greedy walk has the property every greedy walk has, which is that it stops the moment no single move improves the total. A description that needs two cuts made together to become cheaper is unreachable, and there is no way to know from inside the walk whether such a description exists.

Which is also why the answer to “what is the shortest description of this corpus” is unknown even here. The three stems and three endings are shorter than what the search returned at five occurrences; whether anything is shorter still is a question nobody on this page has answered, and answering it means enumerating the two-to-the-fifty-fourth arrangements of those twelve words.

The three parts of Part 3 look like facts and several of them are decisions. Spelling the list character by character under the frequencies of characters within the list is one way of writing a list of strings down, and it is why a piece made of common letters is cheaper than one made of rare letters, which is a statement about spelling rather than about morphology.

Charging for the counts by the number of ways to deal references into non-empty piles is another. Writing the text under a model with no memory is a third, and it is the one that is most obviously false about language.

The criterion has no notion of meaning, of position, or of what a language is built from, and two measurements on this page show it rather than argue it. The first is that the piece s, learned from the endings of walks, talks and plays, is used in front of a stem when the fitted list reads splay as s followed by play and stalking as s, talk and ing. Both readings are cheaper than any alternative the list allows, and both are wrong about the words.

The second is sharper, because there the criterion is not being fooled, it is disagreeing. Take undo, untie, redo and retie, ten times each, where the prefixes are as clear as anything in English. Left whole, that corpus has a description length of 111.7806. Cut into un, re, do and tie, it has a description length of 148.5946. The morphological answer is 36.8140 nats worse, and the fit therefore leaves all four words whole.

So the pieces this method finds are the ones that make a particular corpus cheap to describe under a particular coding scheme, and their agreement with morphology is a happy consequence on some corpora and absent on others. Creutz and Lagus chose the word morph rather than morpheme for exactly that reason, and undo and untie are where the distinction stops being a hedge and becomes the actual answer.