The Word Lattice

The previous page took the longest entry of a word list that fitted where the scan was standing, cut there, and went again. Two things went wrong with that and they are worth having in front of us as numbers, because everything on this page is aimed at the first of them and nothing on this page touches the second.

The English case is the one to look at closely, since anybody can check it. Standing after under, the longest entry in a list of 810 ordinary English words that begins there is theta, the Greek letter, which the list holds like any other word. Taking it leaves b, l and e behind, three characters no entry covers, and the answer comes back in seven pieces where five would have done.

The scan had no way of knowing that theta was going to cost three pieces later, because at the moment it chose, later did not exist.

The second failure is not repaired here and it would be dishonest to imply it is. A word the list does not hold cannot be produced by anything on this page either, and the surname Alvarez will still come back as its separate characters at the end. What changes is only the first failure, which is the one about committing early.

Instead of standing at a position and choosing, stand at every position and write down every entry of the list that begins there, keeping all of them. Add, at each position, the single character standing there, whether the list holds it or not, so that nothing in the text is left with no way past it. That collection of candidates is the word lattice, and it is the whole of what the method builds.

Here it is for the six characters that mean either research into the origin of life or a graduate student’s fate and origin. Five words are in the list, and the sentence is exactly the case where a word list alone has nothing to say, since both readings use three real words.

…

Ten candidates in all, which are the five entries at the positions where they fit and the five single characters that no entry covers. Each one knows where it starts and where it ends, so the arc for the first entry runs from position 0 to position 2 and the arc for the three-character entry runs from 0 to 3.

An arrangement like this one is what the method is named after, and this sense of the word, a set of positions with arcs between them, has nothing to do with the lattice of order theory that the same word names in algebra.

Reading the sentence means choosing candidates that fit together, which means each one starts exactly where the last one ended, the first starts at the beginning and the last ends at the end. Follow the arcs above from the left edge to the right edge without a gap and without an overlap, and what you have walked is one reading of the sentence.

This is the move the whole page rests on. The previous page’s rule scored a position, since the longest entry beginning here is a fact about here. A path is a whole reading, so anything said about a path is said about the sentence, and a candidate taken early can now be made to answer for what it leaves behind.

Between any two neighbouring characters there is either a boundary or there is not, so a text of n characters admits two to the power of n minus one cuts. Almost none of those are paths, because a cut whose pieces are not entries has no arcs to walk along, and that is the first thing the word list buys.

Ten of thirty-two on six characters, and 240 of seventeen and a half trillion on forty-five, so the filter tightens as the text lengthens without ever bringing the count down to something small. The number to watch is the last column, which is how many candidates there are, and which the fifteenth section will show is also how many steps the search takes. Twenty-eight characters of ordinary English permit 2,592 readings and the search touches 45 things.

Every entry of the list carries a count of how often it was seen. Treat that count divided by the total of all the counts as the chance of meeting that word, treat the words of a reading as independent of one another, and the chance of the whole reading is the product of the chances of its words. That is the entire model, and both of its assumptions are wrong in ways worth stating.

P(reading)  =  product over its words w of  count(w) / total

Words are not independent, since research is far likelier before origin than after it, and the counts come from whatever text somebody happened to count. Neither is fatal here. The independence is what makes the search in Part 4 possible at all, and the counts are the only evidence about the language the method has.

Multiplying shares together is the right arithmetic and the wrong thing to compute. Every share is below one, so a reading of forty words is a product of forty numbers below one, and on a real dictionary where a common word has a share near one in a thousand that product falls below the smallest number a computer can tell from zero long before the sentence ends. Taking logarithms turns the product into a sum and the problem goes away.

score(reading)  =  sum over its words w of  log( count(w) / total )

Nothing about which reading wins changes, because the logarithm is increasing, so whichever product was larger has the larger logarithm. Every score is negative, since every share is below one, and a score nearer zero is a likelier reading. Two scores can be compared by subtracting them, and the difference is the logarithm of how many times likelier one reading is than the other, which is a more useful thing to hold than a ratio of two very small numbers.

Now the six characters from the second section can be answered. Both readings use three words of the list, so counting pieces says nothing about them, and the greedy rule of the previous page gave one answer from the left and the other from the right with no way to choose. Score both whole and the counts choose.

…

research reading = ln(10/33) + ln(8/33) + ln(5/33) ≈ −4.4981
graduate-student reading = ln(6/33) + ln(4/33) + ln(5/33) ≈ −5.7020
log-score difference ≈ 1.2040

probability ratio = (10 × 8 × 5) / (6 × 4 × 5)
                  = 400 / 120 = 10/3
log ratio = ln(10/3) ≈ 1.2040
losing probability / winning probability = 120/400 = 0.30

It is worth being exact about what has been settled here. The method has not discovered that the sentence is about research. It has reported that under one particular set of counts the research reading is the likelier of the two, and the twentieth section is about how much weight that will carry.

Move two counts and nothing else. Let the graduate student entry be counted 20 times rather than 6 and the single character be counted 12 rather than 4, which takes the total from 33 to 55. The lattice is character for character the same, the same ten candidates at the same ten spans, and the answer reverses.

…

After the count changes, the graduate-student reading wins. Compare the two path products again.

probability ratio = (20 × 12 × 5) / (10 × 8 × 5)
                  = 1,200 / 400 = 3
log-score difference = ln 3 ≈ 1.0986

The log-score difference is about 1.0986; the probability ratio is three. Greedy longest matching is unchanged because it does not consult these counts.

Back to the English text the greedy scan broke. Standing after under, taking theta was free as far as the greedy rule could see, because the rule was comparing five characters against three at one position. Scoring the whole path, the same choice is no longer free, since a path through theta has to get from the end of theta to the end of the text and there are only single characters left to do it with.

…

Every entry in this list is counted once, so every word is worth the same and the score of a reading is simply how many words it used, times the score of one word. The reading a person gives uses five and scores −33.4852. The reading the greedy scan gives uses seven and scores −46.8792, which puts it fourth on the list above and makes it one part in 656,100 as likely, that being 810 twice over for the two extra words it had to spend.

Suppose there are no counts, only a list of words, which is ordinarily what somebody has. Then every entry has been counted once and every word is worth the same, so the score of a reading is that one value added up once per word, and maximising the score means using as few words as possible. The method is still doing something, and what it is doing is the shortest reading rather than the likeliest one.

every count 1  ⇒  score(reading)  =  (number of words) × log( 1 / total )

…

On the wildlife park sentence with nine words all counted once, every candidate scores −2.1972, and the best paths use five words for −10.9861 where the greedy scan from the left used six for −13.1833. So the piece count is repaired. What is not repaired is the reading, because two different paths use five words and they score identically to the last bit, and the one that comes back is the wrong one. The right one is second on the list above and the greedy scan from the right had found it.

Give those nine words counts and the tie disappears. I have to be honest about where these particular counts came from, since nothing on this site counts Chinese text and I wrote them by hand, putting the preposition and the pronoun high, the two compounds the sentence uses in the middle, and the two compounds it does not use low. They are a plausible ordering rather than a measurement, and the point they make is about what counts do, not about these counts.

…

With them the reading a person gives scores −10.9001 and the other five-word reading scores −16.6684, a gap of 5.7683, so the loser is now worth about a three-hundred-and-twentieth of the winner rather than exactly as much. The two arcs that led the greedy scan astray, the one meaning out of office and the one meaning vivid, are still in the lattice and are still perfectly legal readings; they are simply rare, which is something a count records and a number of pieces cannot.

Here is the consequence that surprised me, and it follows from the division rather than from anything about words. Every score is a count divided by the total of all counts, so adding an entry raises that total and lowers every score by the same amount. A reading with four words has four of those lowered scores and a reading with three has three, so the longer reading loses more, and the ordering between two readings of different lengths can turn over without a single one of their own counts moving.

one word wins over two  ⇔  count(whole) × total  >  count(first) × count(second)

Take six words in which the compound meaning life is counted 3 times while each of its two characters, both ordinary words on their own, is counted 10, and let the whole list have been counted 32 times. Then reading the compound as two words is worth more than reading it whole, and the sentence comes back in four pieces. Now count one more word, one that occurs nowhere in the sentence at all.

…

The compound’s count is three and its two separate words each have count ten. The preference changes when the corpus total crosses the following threshold.

tie condition: 3 × total = 10 × 10
tie total = 100/3 ≈ 33.3333

At total thirty-two, splitting wins by about 0.0408 in log score. Adding two occurrences of an unrelated word raises the total to thirty-four, making the compound win by about 0.0198. The sentence and its candidate counts did not change.

My first reading of this was that it made the answer depend on how much text had been counted, and the control at the bottom of the widget says otherwise. Multiply all six counts by a hundred, so that the total runs from 32 to 3,200, and the winning score stays at −6.7729 to the last bit, because every share is a count over a total and multiplying both leaves it alone.

Counting the same text over again moves nothing. What moved the answer above was one count belonging to a word this sentence never uses.

Twenty-eight characters of ordinary English permit 2,592 readings and a longer text permits very many more, so scoring every reading and taking the best is not a method. What is done instead is to ask, at each position, one question whose answer is a single number, and to ask it from the right-hand end of the text backwards.

best(i)  =  max over candidates w starting at i of  log( count(w)/total ) + best(i + length of w)

The number best(i) is the score of the best reading of everything from position i to the end. At the very end there is nothing left to read, so best(n) is zero. Working leftwards, every position has already had the positions to its right answered, so each candidate at position i costs its own score plus a number already sitting in the table. Remembering which candidate won at each position is enough to walk the answer back out from position zero.

Ten additions, one per candidate, settled a choice among ten readings, and the arithmetic never mentioned a reading. Notice that −5.7020 and −10.2972 turn up in that table as losing branches at position zero and turn up on the ranked list in the seventh section as whole readings, which they are.

The recurrence is only correct if a fact holds that is easy to assume and worth checking. It is that if the best reading of the whole text passes through position i, then the part of it from i onwards is the best reading of everything from i onwards. Without that, keeping one number per position throws away a tail that some other head would have wanted.

This is the argument Bellman called the principle of optimality and the recurrence is the one Viterbi published for decoding a channel, with the words of a sentence standing where the states of a code stood. The character-level tagger of the next page in this section runs the identical recurrence one level down, over positions in a word rather than words in a sentence.

Each position offers at most as many candidates as the longest entry is long, so a run of n characters against a list whose longest entry is L characters costs at most n multiplied by L questions, exactly the bound the greedy scan had. The difference is that the greedy scan stops asking at a position as soon as one candidate hits, and this one asks about all of them, because a candidate that loses at a position may still be on the best path.

questions  ≤  n × L

…

There is one cost that is not a count of questions and it matters more in practice. The greedy scan can hand back its first word after reading a few characters; this one cannot say anything until it has reached the end of the run and come back, because best(0) is the last number the table fills in.

On a sentence that is nothing, and on a stream of text that has to be cut into runs first, it is the reason whitespace ending a run matters as much here as it did on the previous page.

A path has to exist for every text, including a text made entirely of characters nobody wrote down, so every position carries a single-character candidate whether or not the list holds it. That candidate needs a score, and there is no evidence anywhere from which to estimate one. What is used is the smallest score a real entry could have had, which is the score of a word counted exactly once.

score of a character no entry covers  =  log( 1 / total )

Against a list counted 33 times that is −3.4965, which is worse than the rarest of the five entries at −2.1102 and much worse than the commonest at −1.1939. It is a convention rather than a measurement and it is worth saying so plainly, because it is doing real work. Set it lower and a stretch of unknown characters becomes so expensive that the path will contort to avoid it; set it higher and single characters start winning against real words.

…

Here is our own sentence contributing to the Chinese half of the page again, with Alvarez written the way Chinese writes a foreign name and put in front of the six characters from before. The five characters of the surname have no arcs above them at all, only the flat single-character candidates along the baseline, which is what a stretch the list never saw looks like.

That choice has a consequence worth checking, which is that a stretch of unknown characters can never outscore a single entry covering the same stretch, however the entries are counted. So the fallback never eats a word, and no arrangement of the counts lets it.

It also says something about the shape of the failure. The method will not chop a word it knows into characters, and it will always chop a word it does not know into characters, so every error of this kind falls on the same side. Five unknown characters cost five times −3.4965, which is −17.4826, and there is no arrangement of the list that would have got any of it back.

Score the whole thing and the arithmetic separates cleanly, which is itself informative. The surname contributes its five fallback scores and the rest of the sentence contributes exactly what it contributed before the surname was in front of it.

…

The best path scores −21.9806, which is −17.4826 for the surname plus the −4.4981 the six characters scored on their own, and the gap to the next reading is 1.2040, exactly the gap it was without the surname. Eleven characters that a person reads as four words come back as eight pieces, five of which carry almost nothing about the sentence. The greedy scan answered eight pieces here as well, so on this text the two methods cost the same and are wrong in the same place.

The method asks for the reading with the highest score, and a highest score can be reached by more than one reading. When it is, the question the method poses has several correct answers and the method contains nothing whatever that prefers one of them. Something outside the score has to finish the job, and whatever that something is, it is a convention of the same kind the previous page was made of.

…

Seventeen characters of ordinary English against 810 words counted once each. Two readings use four words, they score −26.7881 apiece and the two numbers are equal in every bit, so the gap is zero and neither is likelier. One of them is the sentence and the other is four real English words nobody would write, and what decides is a rule about which candidate to keep when a comparison comes out level.

Prefer the longer candidate, which is the usual choice, and the five-letter Greek letter is taken and the wrong reading comes back. The greedy scan run from the right end had answered correctly.

Ties are not an accident of a small example either. With every count equal the score is a count of words times a constant, so every reading of a given length scores identically and ties are the normal case rather than the exception; the wildlife park sentence in the tenth section ties for the same reason. Counts make ties rare without making them impossible, since two readings can multiply out to the same product.

The score of a reading is built entirely out of counts, and a count is a fact about whatever somebody counted rather than about the language. So when this method reports that one reading is three and a third times likelier than another, it is reporting a property of a corpus, and it will report a different number for a different corpus without anything having gone wrong.

The eighth section is that statement made concrete. Two sets of counts over the same five words, one lattice, and two opposite answers with confident-looking margins on both. Neither is a mistake. If the counted text was news, the research reading is the right answer for news; if it was university administration, the graduate student reading is the right answer for that, and the method has no access to which body of text a reader has in mind.

There is a further wrinkle, which is that the counts have to come from text somebody has already segmented, since counting occurrences of a word means knowing where the words were. The method therefore consumes the answer to a version of the question it exists to answer. That is not circular in practice, because a small hand-segmented corpus can build counts good enough to segment a large one, and it does mean any claim about what these numbers measure runs back to a body of text somebody cut up by hand.

Two more places where the method is silent rather than approximate. The first is the ceiling. The readings available are exactly those spellable out of the list plus single characters, so a reading containing a word the list lacks was never a candidate, and no amount of improvement to the counts can reach it. However good the scoring becomes, the word list is the boundary of what can be said.

The second is that the scores are not probabilities of anything, and it is worth seeing why rather than taking it as a caution. Every entry’s share is its count over the total of every count, so the shares of the entries add to exactly one already. Each single character the list does not hold is then handed another share of one over the total on top of that.

The numbers being multiplied together therefore add to more than one over the things they describe, so a score ranks readings correctly and is no probability.

That is why the widgets on this page print a gap and a ratio rather than a confidence. The difference between two scores is readable, since the extra mass sits in both of them and cancels in the comparison, and a single score standing on its own cannot be read as how sure anything is.

Building a segmenter that answers with a genuine probability means reserving mass for words nobody has written down and taking it away from the ones the list holds, which is a different model rather than a correction to this one.

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 decisions are the ones worth a reader’s attention, since nothing in the method makes them and every one of them changes what comes back.