Segmenting With a Hidden Model

Both dictionary methods are limited by their entries. Even a better path score cannot select a word the candidate list never included. Could we learn where words begin and end from examples instead? We will use sentences with labelled boundaries to learn a model over character positions.

Here is the failure with everything else held still. Three sentences are handed to all three methods, six words between them, three of them distinct. A word list is counted from those sentences and the greedy scan and the best path are run against it, and the model this page is about is fitted on exactly the same three sentences. Then all three are asked to read six characters that spell out three words none of the sentences contained.

…

Both word-list methods answer six single characters, which is the only thing they can do when nothing in the text matches anything they hold. The third answers three two-character words, and it is right, and every one of the three is a word it had never been shown. The characters were not new; a, c and e had only ever begun a word in those sentences and b, d and f had only ever ended one, so what those three sentences taught about a and about d is still true inside ad, where what they taught about the words ab and cd reaches nothing in this text at all.

The dictionary methods ask, of a stretch of characters, which word it is. That question has no answer for a stretch nobody has written down. Ask instead, of one character, where in its word it happens to sit, and the question has an answer for every character in every text, because a character sits somewhere whatever word it is in.

Our own sentence carries the case that made this worth inventing. Dr. Alvarez didn’t expect the low-cost re-analysis, and Alvarez is a Spanish surname in an English sentence, which is precisely the sort of word no list holds. In Chinese a foreign name is written out in characters chosen for their sound, so Alvarez becomes five characters that are each ordinary and that together mean nothing. The previous page showed those five costing five separate pieces and the loss being unrecoverable by any arrangement of the counts.

There is a second thing this buys, and it will matter later. To build a word list somebody has to have decided where the words were; to count what this method counts somebody has to have decided exactly the same thing. So the two methods need the same evidence and differ only in what they take from it, which is why every measurement on this page can hand both of them the identical sentences.

Consider where a character sits within its word. In a multi-character word it can begin the word, lie in the middle, or end it. A one-character word needs its own label because the character both begins and ends that word. These give us four states with which to describe a segmentation.

a word of one character      →   S

a word of k characters, k ≥ 2   →   B  M … M  E,  with k − 2 middles

The letters are the usual shorthand and they stand for begins, middle, ends and single. Read a whole sentence this way and you get one letter per character. The six characters that mean either research into the origin of life or a graduate student’s fate and origin are B E B E B E under the first reading, since it is three two-character words, and B M E S B E under the second, since it is a three-character word, then a one-character word, then a two-character word.

That correspondence deserves to be checked rather than believed, because everything after it depends on the letters being able to say whatever a cut can say. Between any two neighbouring characters there either is a boundary or there is not, so a run of n characters admits two to the power of n minus one cuts. Count the runs of letters instead, allowing only those that describe some cutting, and the count comes out the same.

runs of places over n characters  =  2^(n − 1)  =  ways to cut n characters

The state representation can express boundary patterns beyond a fixed dictionary. On the twenty-eight-character example, the word lattice allowed 2,592 of the 134,217,728 possible patterns. The character-role representation can describe all 134,217,728 before their scores are considered, including many segmentations we would reject linguistically. Representation coverage alone does not choose a good reading.

That is the same fact as section 1 seen from the other side, since a word nobody listed sits on some cut of the characters that spell it, and every cut is reachable here.

Look at what may follow what. After a character that begins a word, or one inside a word, the word is still open, so the next character is either another middle or the end. After a character that ends a word, or one that was a word by itself, a word has just closed, so the next character either begins a new word or is a new word by itself. That rules out eight of the sixteen pairs before any text has been looked at.

These eight steps are not learned and they are not smoothed away. They are refused, and the refusal is the reason the counting in the next Part comes out as small as it does, since a place has two possible successors rather than four. It is also what stops the search answering something like B B, which is a run of letters that cannot be cut into words at all and would be a wrong answer of a kind no inspection of the words would explain.

Take sentences somebody has already cut into words. Write the four letters under every character, which the third section showed is a rule with no choices in it. Now three things can be counted, and the model is those three things and nothing else. How often a sentence started in each place, how often each place followed each other place, and how often each place produced each character.

Two sentences over three characters are small enough to read every number of. The first is the two-character word ab followed by the one-character word c, so its letters are B E S. The second is the single three-character word abc, so its letters are B M E.

…

Read the middle table across. Both sentences started with a character that begins a word, so of the two starts, two were B and none was S. After a B there was one M and one E. After the only M there was one E and no further M. After the only E there was one S and no B.

And after S there was nothing at all, since the one S in the corpus was the last character of its sentence. That last row is the interesting one, and the next section is about it.

A path score multiplies emission and transition probabilities. One zero makes the entire product zero, excluding every path that uses it. With a small corpus, a permitted event may have zero count simply because it was never observed. We therefore add a smoothing amount to allowed outcomes before normalizing the counts. Transitions forbidden by the state design remain forbidden.

P(next place | this place)  =  (count of the pair + a) / (count of this place + 2a)

The two in the denominator is the number of places that may follow, which the fifth section fixed at two for each of the four. The eight refused steps get no helping, because a helping is for an outcome that could have occurred and did not, and those eight could not have occurred.

P(start B) = (2 + 1) / (2 + 2) = 3/4
P(start S) = (0 + 1) / (2 + 2) = 1/4

P(M | B) = P(E | B) = (1 + 1) / (2 + 2) = 1/2
P(M | M) = (0 + 1) / (1 + 2) = 1/3
P(E | M) = (1 + 1) / (1 + 2) = 2/3

The characters need the same treatment and one thing more. A place that never produced a given character can be handled the way the steps were, by adding a helping to every character of the alphabet. That still leaves a character the corpus never contained anywhere with no entry in any row, and such a character is exactly what turns up in a name. So the shares are spread over the alphabet plus one extra slot standing for everything else.

P(character | place)  =  (count of that pair + a) / (count of the place + a × (alphabet + 1))

The observed alphabet contains a, b and c. Add an unknown-character slot, giving four possible emissions. State B emitted a twice and no other character.

P(a | B) = (2 + 1) / (2 + 4) = 1/2
P(b | B) = P(c | B) = P(unknown | B) = (0 + 1) / (2 + 4) = 1/6

State S emitted c once. Apply the same rule with its own counts.

P(c | S) = (1 + 1) / (1 + 4) = 2/5
P(a | S) = P(b | S) = P(unknown | S) = (0 + 1) / (1 + 4) = 1/5

Notice what that last sentence quietly concedes. A character the corpus contains but that this place never produced gets exactly the same share as a character the corpus has never seen. The extra slot exists so that the second case has a number rather than to tell the two cases apart, and the nineteenth section is about what follows from their being indistinguishable.

How much to add is a free number, and on a small corpus it is not a small decision. Here are four sentences in which the first two of three characters are a word twice and all three are a word once, so the corpus contradicts itself about that stretch and something has to choose. Walk the amount added down from two to a hundredth and watch the answer turn over.

…

At the usual value of one, and at a half, and at a quarter, the model answers the majority reading and therefore fails to reproduce a sentence it was itself trained on. Below about 0.238 it answers the minority reading and the training sentence comes back as written. The middle figure in the widget is what moves.

The share of the place inside a word producing the second character rises from 0.1429 at a helping of two to 0.9182 at a hundredth, because that place produced that character every one of the very few times it produced anything, and a large helping drowns a small count while a small one lets it through.

A run of letters over a text is worth the chance of it having happened, and by the three tables that chance is a product. The chance that the first character sat where it did, times the chance it produced the character it produced, times for every character after it the chance of the step that reached it and the chance of the character it produced.

Taking logarithms turns that product into a sum for the same reason it did on the previous page, which is that a product of many numbers below one falls below what a computer can tell from zero.

score  =  log P(t₁) + log P(c₁ | t₁) + Σ over i ≥ 2 of [ log P(tᵢ | tᵢ₋₁) + log P(cᵢ | tᵢ) ]

Two properties of that sum decide everything that follows. It has one term per character and one per step, so it is a sum along a path, which is the shape the search of the next section needs. And each term looks at one character and at most one step, so nothing in it can read two characters at once, which is the shape of the failure the eighteenth section measures.

There are two to the power of n minus one runs of letters over n characters, so scoring them all is not a method. The word lattice page derived the way round it, and the argument is reused here rather than rebuilt. If the best run of letters over a whole text passes through a particular place at a particular character, then the part of it up to there is the best way of reaching that place at that character.

Otherwise a better head could be swapped in, leaving the tail untouched and raising the total, which contradicts the run having been best.

best(i, t)  =  log P(cᵢ | t)  +  max over places s that may precede t of [ best(i − 1, s) + log P(t | s) ]

So carry four numbers rather than one, since a tail depends on which place the head finished in, and there are four places it could have finished in. At every character work out, for each of the four, the best way of arriving there and which place it came from; at the end take the better of the two places a text may finish in and walk the record backwards. The grid below is that calculation with nothing hidden.

…

Read the first column. Only two of its four cells carry a number, because a text cannot start in the middle or at the end of a word, and the cells that carry no number carry no number for a reason fixed in the fifth section rather than for want of evidence. Every cell after that is a maximum over the two places that could have led to it.

The filled cells are the winners at each character and the line joining them is the answer, which for those six characters is B E B E B E and therefore three two-character words.

Each character offers four places, each place is reached from at most two, and the fifth section fixed those numbers before any data arrived. So the work is eight comparisons per character plus two to start, whatever the text says and whatever the corpus was.

comparisons  =  8 × (n − 1) + 2

Set that beside the previous page, where the work was the length of the text times the length of the longest entry, and grew when a longer word joined the list. Here there is no list to grow. What replaces the dictionary lookup entirely is a table of four numbers per character, which is why nothing in this method needs to be optimised and why the interesting costs are all in the next Part, where they are paid in tagged text rather than in time.

Back to the six characters of the first section, now with the search visible. The three sentences the model was fitted on contain three words and none of them appears in the text at all, so a word list has nothing to match and every candidate on the previous page’s lattice is a single character.

…

What decides is the character table. In those three sentences a, c and e only ever produced under the place that begins a word, and b, d and f only under the place that ends one, so at the first character the cell for begins carries a much larger number than the cell for alone, and at the second the cell for ends carries a much larger number than the cell for begins.

The run that wins alternates, and reading it off gives three words that were never in the corpus and are the right three.

Our surname example shows the remaining difficulty. The corpus has never seen its five characters. Dictionary matching returns eight pieces, including five single characters. The hidden-state method returns seven after joining the first two surname characters, but still differs from the four-word reference. Its representation permits that reference in principle; the learned scores and unknown-character treatment do not select it here.

The nineteenth section is about why that particular wrong answer, and it turns out to have nothing to do with the name.

Two- to five-sentence examples let us inspect the mechanism, but they are too small to assess performance broadly. We will also use a seeded synthetic language with seventy words drawn from forty characters. Its frequency distribution gives a few words many occurrences and leaves a longer tail of less frequent words, providing a larger controlled comparison.

Both methods are fitted on the first two sentences of one corpus, then the first five, and so on, and both are scored on the same two hundred held-out sentences, a word counting as found only when both its ends land where the sentence put them.

…

The curves cross between thirty and forty sentences, and they cross the other way from the way I expected. Below the crossing the places win, at thirty sentences by 0.8659 against 0.8501; at and above it the word list wins, at forty by 0.9019 against 0.8792, and by a hundred and sixty sentences the list has seen every word of a seventy-word language and scores exactly 1.0000 while the places have flattened out at 0.9178.

The split recall says why. Against words the training sentences contained, the list is at 0.9983 and better at every size; against words they did not, the list is at 0.0000 from ten sentences on and the places are between 0.42 and 0.66. So the crossing is not really about sentence counts at all. It sits where the share of held-out words that are new falls below about a tenth, and it is a crossing at all only because a language of seventy words runs out of new words.

A real vocabulary does not, which is the honest caveat on this measurement and the reason the method is used on real text at corpus sizes far past forty sentences.

There is a cost here and the split recall has already shown it. This method does not memorise. A word list holds a word and recovers it whenever it appears; a table of four places holds a habit and can be talked out of it by the characters on either side. Across every size measured, on both languages, the places are worse than the list on exactly the words the corpus contained.

Reading the last column of the first two rows together with the first is the whole trade in one place. Under a tenth of the familiar words are given up, in exchange for about half of the unfamiliar ones being recovered where a list recovers none. Which of those matters more is a question about the text being read rather than about either method, and the seventeenth section is about not having to choose.

This method was invented for Chinese, and it is fair to ask what is special about that. The answer is measurable and it is not about the language. It is about how much a single character tells you about where it sits. Take the same measurement on a generated language built from the eight hundred and ten ordinary English words of the first page of this section, with the spaces taken out, and everything changes.

…

Before you read a character, which of the four places it is in is worth 1.5590 bits of uncertainty on the English words and 1.7518 on the character language. Reading the character removes 0.4869 of those bits on the English and 0.9207 on the characters, which is roughly twice as much. That is the whole difference, and it shows up as a ceiling.

The places top out at 0.6087 on the English words and then fall back to 0.5186 as the corpus grows, because a wider vocabulary uses every letter in every position, while on the character language they climb past 0.92.

Our own sentence is where this lands. Handed the sentence with its spaces taken out, a model fitted on 1,280 English sentences answers thirteen pieces where a reader answers seven, and it gets Dr. and nothing else; the word list at the same size answers twenty-four pieces and gets expect and the. Neither is usable, and the reason the first one is unusable is the 0.4869 bits above rather than anything about the sentence.

The two methods are wrong in different places, and the previous page ended by pointing at the arrangement that follows from that. Find the best path through the word list, look for the stretches of consecutive single characters no entry covered, and hand each of those stretches to the places. The list keeps its near-perfect recall on familiar words and the places are asked only about the characters the list gave up on.

…

The green curve is that arrangement, and on both languages and at every size measured it is at least as good as either method alone. On the character language at thirty sentences it reaches 0.9262 where the better of the two singles reaches 0.8659; on the English words at eighty sentences it reaches 0.7781 against 0.6065. This is what the segmenter most people use in Python actually does, and it is the reason a page on this method belongs after a page on the word lattice rather than instead of it.

The combined method leaves this surname result unchanged. No dictionary entry covers its five characters, so that whole span goes to the hidden-state fallback. The fallback returns the same four pieces as it did alone. Combining the methods cannot improve a span where it simply delegates to the same unchanged procedure.

The score of the tenth section has one term per character and one per step. No term anywhere reads two characters together, so a boundary whose evidence is a pair of characters has nowhere in the model to be recorded. That is not a shortage of data and more text does not fix it, since the quantity is not in the model’s vocabulary.

Here is what that costs, arranged so it can be checked rather than argued. Two languages over the same four characters, one making its words by joining the first character to the second and the other by crossing them over. Every count either language leaves behind is the same count, so the two fits are the same fit.

…

Thirty-six numbers compared and thirty-six equal, so no quantity of text in either language could separate them. And the consequence is not abstract. A fit shown only the first language reads four characters of the second into two words of the second, words that its own language does not contain and never could, with exactly the confidence it reads its own. The mechanism of the thirteenth section, which recovers a genuine word nobody wrote down, is the same mechanism inventing one that does not exist.

The eighth section put every unfamiliar character on the same share as every other. Follow that through. If a stretch of a text is made entirely of characters the corpus never contained, then every one of them contributes the same number under every place, those numbers cancel out of every comparison, and the score of a run of letters over that stretch depends only on the steps. So the method answers, and what it answers is a fact about the corpus rather than about the stretch.

The widget above lists what that looks like for each length. A run of five characters no corpus of those five Chinese sentences ever held comes back as B E S S S, four pieces, and it comes back as that for a transliterated surname, for five Latin capitals and for five pictograms alike. That is the wrong answer the thirteenth section left hanging, and it was never an answer about the surname.

Unknown-character handling is a policy we must choose. Here each role has its reserved unknown probability. We could estimate different behaviour for character categories, or reject an unknown span and leave it for another method. Those choices change path scores, so the implementation needs to document which one it uses.

Taking the first, as here, gives a confident answer that on the surname is wrong; taking the second means estimating four numbers from the one thing the corpus cannot show; taking the third gives no answer and marks the stretch for whatever comes next. Nothing in the mathematics prefers any of the three.

Two decisions sit in front of every number on this page and neither is settled by anything in the method. The first is that somebody had to cut the training sentences into words. That is the input, it is expensive, and it is an opinion, since whether a Chinese compound is one word or two is unsettled in the language itself, and the annotated corpora built for this problem disagree with one another about the same strings.

So a model fitted on one of them is right by that corpus’s standard and can be measured wrong by another with nothing having gone amiss.

The second is the helping added to the counts, and the ninth section makes that concrete rather than theoretical. On the same four sentences and the same five characters the answer is the majority reading at 1.0, at 0.5 and at 0.25, and the minority reading at 0.23 and below, turning at 0.238. That is not a rounding difference; it is two different words. There is no quantity inside the method that prefers a value, and the effect shrinks only as the counts grow, which on four sentences leaves it deciding outright.

The hidden-state model can only score legal paths built from its defined states and observations. Unknown characters, impossible transitions and competing boundary conventions need to be considered separately.