Learning Boundaries From Examples

The previous page gave every character of a text one of four places in its word, and chose the whole run of places at once by adding up a score along it and taking the largest total. That is a real advantage and it is worth naming before we give it up. A word cannot be left half open, a boundary in one spot can be paid for by what it forces two characters later, and the answer that comes back is the best reading of the sentence under one account of what sentences look like.

Now ask a narrow question of such an answer. The sentence we carry through this section is Dr. Alvarez didn’t expect the low-cost re-analysis, and with its spaces taken out it is forty-five characters with forty-four gaps between them. Point at the gap between the full stop of Dr. and the A of Alvarez and ask what decided it.

There is no answer, and the reason is structural rather than a shortcoming of any implementation. The score being maximised is a sum over the whole run, so the boundary at that gap was settled by a comparison between two complete readings of forty-five characters, one of which cut there and one of which did not, and the difference between those two totals includes terms drawn from every character in the sentence.

Changing the answer at that gap alone is not something the method can be asked to do.

The same holds for correcting it. If a reader sees one gap answered wrongly there is no weight to reach for, because the quantity that decided it was assembled out of counts about places and steps that every other gap in the sentence also leaned on. And the annotation has the same shape from the other direction, which is the third section.

Between any two neighbouring characters of a text there either is a word boundary or there is not. That is a question with two answers, it has one at every gap of every text, and nothing in it mentions any other gap. So take it as the whole method. Ask it forty-four times of our sentence, cut wherever the answer is yes, and read off the pieces.

a text of n characters   →   n − 1 questions, each answered on its own

Here is that done, on eight short sentences somebody has marked up by hand. Each bar is one gap, drawn upward when the answer was to cut and downward when it was to keep going, and the height is how strongly. Nothing joins the bars, because nothing in the calculation joins them.

…

Forty-one of the forty-four gaps agree with the reading a person gives, and the three that do not are the three drawn in red, all of them inside the surname. What matters for now is not the score but the shape of the answer, since every one of those bars was arrived at without consulting any other bar, and the three wrong ones can be pointed at individually in a way the previous method offers no vocabulary for.

This is the argument the method was invented for, and it is about who has to do the work rather than about accuracy. Imagine somebody going through text marking boundaries and stopping wherever they are unsure. Whether a compound noun is one word or two is genuinely arguable, so a careful annotator leaves such gaps alone and marks the ones they are certain of.

To a gap-at-a-time learner that corpus is simply fewer examples, since a marked gap is one instance and needs no neighbour. To a method that works in places inside a word it is much worse than that, because the place a character occupies is known only when the gaps on both sides of it have been settled, so an unmarked gap spoils the two characters it sits between. Two hundred sentences of a generated language, with a share of the gaps marked at random, say how much worse.

…

With two fifths of the gaps marked, the gap learner keeps 39.49% of its training material and the sequence learner keeps 19.61% of its own, a little over half as much, which is what you would expect from needing two independent events rather than one. At a fifth marked it is 20.41% against 7.79%, so the gap between them widens as the annotation gets sparser.

a gap, usable                         0.4
a character inside a sentence         0.4 × 0.4  =  0.16
a character at the end of a sentence  0.4

(1,461 × 0.16 + 400 × 0.4) / 1,861  ≈  0.21

A gap has to be answered from something, and the only thing available is the text around it. Number the characters so that the one immediately before the gap is at offset minus one and the one immediately after is at offset zero, and then decide how far to look in each direction. That distance is the one number the whole design turns on, and we will call it the reach.

… c[−3] c[−2] c[−1] | c[0] c[1] c[2] …   with the gap at the bar

Within the reach, each single character is one thing the gap is asked about, and each neighbouring pair of them is another. The pairs matter because a boundary is often a fact about a juxtaposition rather than about either character alone. In our sentence a punctuation mark sits immediately to the left of four gaps, one of which is a boundary and three of which are not, so a question about punctuation on its own is being asked to answer two different things at once, where a question about which characters sit either side of the gap is not.

Asking which character sits at an offset is exact and it is useless the first time an unfamiliar character turns up. So each offset is asked a second, coarser question, which is what kind of character that is. Seven kinds are enough for this purpose, namely a Han character, a hiragana, a katakana, any other letter, a digit, a punctuation mark, and everything else.

What that buys is a rule learned once instead of once per pair. A boundary between a run of one script and a run of another is a single thing to learn, rather than something that must be learned separately for every one of the thousands of character pairs that could sit astride it. And it never goes silent.

Counted over every gap of two hundred held-out sentences of a generated language, 31,566 questions in all, the ones naming particular characters carry a weight 79.33% of the time and the ones naming kinds carry one every time.

Our own sentence needs both halves, and it is worth being exact about which does what. The full stop that ends Dr. is followed by a boundary; the apostrophe inside didn’t and the hyphen inside low-cost are not. All three are a letter next to a punctuation mark, so the kinds alone cannot separate them, and which character it is has to settle it. Meanwhile in a name nobody has written down, the kinds are all there is.

…

Those two texts are read by a fit that has met eight sentences in which a foreign name keeps its own script. Ortiz is a name those sentences never held and the three characters after it never appeared in them at all, and the answer is still right, while the whole-sequence method taught the identical eight sentences answers Ortiz漢 and 字文 and gets neither of them.

Count them, since the number is exact and it is the only cost a wider reach carries. A reach of w covers 2w offsets, minus w to w minus one, and each of those contributes a question about the character and a question about its kind. The neighbouring pairs inside that stretch number 2w minus one, and each contributes the same two. One more for the fact of being a gap at all.

questions at a gap  =  1 + 2 × 2w + 2 × (2w − 1)  =  8w − 1

Three is the reach used everywhere on this page, so a gap in the middle of a run answers twenty-three questions. That is small, it does not grow with the length of the text, and it does not grow with the amount of marked-up text the answers were learned from, which is what makes the cost of reading a text the dull half of this method.

Each of the questions at a gap gets a number, and the answer at that gap is the sum of the numbers of the questions it asked. Positive means cut and anything else means keep going. That is the whole scoring rule, and its plainness is the property the eleventh section trades on, since a sum can be listed term by term where a maximum over readings cannot.

score at a gap  =  Σ over the questions this gap asks of  weight(question)

A question the marked-up sentences never raised has a weight of zero and therefore contributes nothing, which is the right behaviour and not a special case. There is no threshold to choose either, because the constant question every gap asks can absorb any base rate on its own.

Walk through the marked gaps one at a time. Score the gap with the weights as they currently stand. If the sign agrees with what the annotator marked, change nothing at all and move on. If it does not, add one to every weight the gap asked about when the annotator said cut, and subtract one when they said keep going. That is the whole learning rule, and it is worth noticing that it never looks at a gap it is already right about.

on a mistake:  weight(question)  ←  weight(question) + label,  with label = +1 to cut and −1 to join

A score of exactly zero counts as a mistake while learning, since zero is right for neither answer, and at reading time it is not a cut, because leaving text whole is the more conservative of the two errors. Our eight marked-up sentences hold 189 gaps between them, 34 of which carry a boundary, and here is what the corrections do over twenty passes.

…

Forty-five corrections on the first pass, then ten, five, nine, seven, three, and from the seventh pass onwards none at all, which means every one of the 189 gaps is now answered the way the annotator marked it. That is a stopping condition rather than a convergence in any deeper sense, and the ninth and tenth sections are about the two things it does not settle.

There is a repair worth making before the weights are used, and it costs almost nothing. The walk of the previous section passes through one set of weights after every correction, and the last of those has no special claim on being the best. It is simply the one that happened to be current when the passes ran out, and it carries the full imprint of whatever gap was corrected most recently.

So answer with the mean of every set of weights the walk passed through, counting each one once for every step it survived. That is the averaged form Freund and Schapire analysed, and it generalises considerably better than the final set on data the walk has not seen.

averaged weight  =  ( Σ over steps of the weight at that step ) / number of steps

The rule repairs the gap it is currently looking at, so which gap it looks at first changes which weights move first, which changes what it is wrong about next. Two runs over the same marked-up sentences in two different orders therefore end up with different weights, and the widget in the eighth section shows what that is worth on our own sentence.

Eight orders over the same eight sentences give five different readings of the same forty-five characters, and none of the eight reproduces the reading a person gives. Every one of them runs out of corrections within seven passes, so all eight are equally right about the 189 gaps they were shown and disagree only about the gaps they were not. The disagreement is concentrated in the surname, which is the one stretch of the sentence made of characters those sentences never carried.

Now the whole thing on our own sentence, with the marked-up sentences chosen so that the exercise is not rigged. Eight sentences carry the shapes the sentence needs, which are an abbreviation whose full stop ends it, a contraction, a hyphenated compound and a prefix. Four of the seven words a reader answers with are absent from those eight sentences altogether, namely Alvarez, expect, low-cost and re-analysis with its full stop.

…

Three of the forty-four gaps come out against the reading a person gives, and all three are inside the surname. The method cuts after the v and after the a, leaving a single letter standing as a word of its own, and then fails to cut between the z and the d that begins didn’t, so what comes back is Alv, then a, then rezdidn’t. Everywhere else it is right, and three of the four words the sentences never held come back exactly, which is the thing to take from the widget.

Set against it is the whole-sequence method taught the identical eight sentences. It recovers Alvarez whole, which is precisely where this method fails, and it loses didn’t and expect, which is precisely where this method succeeds. The sixteenth section comes back to the surname, where the difference between the two is a consequence of how each answer is put together rather than an accident.

A score that is a sum can be listed. Pick a gap, write down every question it asked and the weight that question carries, and the list adds to the number that decided it. Nothing is approximated and nothing is attributed, since the sum is what the calculation actually did.

…

The first of those is the gap between the full stop of Dr. and the A of Alvarez, and it comes to +7.1283. Every question about the characters after the gap carries a weight of zero, so the whole of the positive case is made from behind it, and two of those questions could never have carried a weight at all, since those eight sentences contain no capital A and no v anywhere.

The single largest contribution is +3.6304, for the full stop sitting immediately to the left, and the questions about kinds contribute −0.3188 between them, which is to say almost nothing.

Now the second and third, which are a letter followed by a punctuation mark inside didn’t and inside low-cost. Both are kept together, at −17.5093 and −19.7016, and in both the questions about kinds contribute −12.0563, the same figure to the last digit, since those two gaps ask exactly the same questions about kinds. That is the generalisation working, and it is also why the offsets have to be kept apart, since the full stop of Dr. carries its punctuation on the other side of the gap, asks a different set of questions about kinds, and gets −0.3188 out of them rather than −12.0563.

The fourth gap is the opposite case, a change of script where only one of the eleven questions about which characters these are carries any weight, and the cut is made at +0.0367.

A text handed to a segmenter is not always one unbroken run. Chinese quoting an English name, Japanese with line breaks in it, two sentences with a space between them, all contain whitespace, and whitespace is already a boundary. A gap that spans a space is therefore never asked about at all, and the runs on either side of it are answered separately.

…

Eight characters here with a space in the middle, so there are two runs of four and six gaps rather than seven. The boundary at the space is free, in the sense that it costs no question and cannot be got wrong, and the six that remain are all answered correctly. The other thing being kept is that the pieces coming back report where they sit in the original text rather than in their own run, so the third word starts at position five rather than at zero.

There is a mild consequence for the reach. A gap near the start of a run has fewer characters behind it than the reach asks for, and the questions about those offsets simply do not arise rather than being answered with anything. So the first gap of a run answers fewer questions than a gap in the middle, which is why the sixth section’s count is stated for a gap in the middle.

The comparison has to be made on the same evidence or it says nothing, so both methods are handed the identical marked-up sentences at every size, and both are scored on the same two hundred held-out sentences, with a word counting as recovered only when both of its ends land where the sentence put them. Two generated languages are used, one of seventy words spelled out of forty characters and one of ordinary English words with the spaces taken out.

…

On the character language the whole-sequence method is ahead for a long time. At thirty sentences it scores 0.8659 against 0.7974, and the lead does not turn over until somewhere between eighty and a hundred and sixty sentences, after which it turns over decisively, 0.9650 against 0.9178 at a hundred and sixty and 0.9799 against 0.9223 at three hundred and twenty.

On the English words the picture is not the same picture shifted along, it is a different picture. The gap method passes the other one by twenty sentences and then keeps climbing, reaching 0.9057 at 1,280 sentences, while the whole-sequence method peaks at 0.6087 and then falls back to 0.5186 as more text is added.

The previous page measured why that happens to it, which is that a single letter of an alphabet says very little about where in its word it sits and says less as the vocabulary widens. A gap method never asks a character where it sits; it asks a window of six characters and five pairs whether a boundary is between the middle two, and that question keeps its answer.

Two places, and both are worth stating without softening.

The first is words the marked-up sentences never held, which is the very thing the previous page’s method was built to reach. Splitting the same recall by whether the word had been seen, on the character language at thirty sentences, the gap method recovers 0.2640 of the unfamiliar words and the whole-sequence method recovers 0.6560 of them, two and a half times as many. The table under the widget above carries that split at every size, and the gap method is behind on unfamiliar words at every size up to forty sentences. At eighty only nineteen unfamiliar words are left among the held-out sentences, and the gap method recovers six of them to the other method’s five, which is too few to rank the two on.

The second is small corpora of a script whose characters are strongly positional. Four sentences whose every word is exactly two characters long are enough to teach the whole-sequence method that words come in twos, since that fact lives directly in its table of steps from one place to the next. The gap method has nowhere to put it.

…

Handed 生命起源, which is two of the three words those sentences contain, the gap method answers one four-character piece and the whole-sequence method answers the two words. On the surname text underneath it, the ranking reverses again, with five pieces against seven where a reader answers four, so neither of these is a general result about either method.

Here is the cost of independence stated exactly. The whole-sequence method returns the reading with the largest total score, so its answer is the best reading under one account of the sentence, and changing any single boundary in it lowers that total. An answer assembled out of independent decisions has no such property, because there is no quantity anywhere in the method that mentions the whole run.

That is checkable rather than merely arguable. Take the reading the gap method gives our sentence and score it with the whole-sequence method’s own tables, learned from the same eight sentences.

Read the bottom row before the top one. The reading a person gives scores lower than the reading the whole-sequence method chose, so being the maximum of that score is not the same as being right, and the consistency the method buys is consistency with its own account of sentences rather than with the language. The top row then says what independence costs in those terms, a gap of 4.7503 between an answer that maximises that score and one that maximises nothing.

the best whole sequence, less one answer per gap   −151.0253 − (−155.7756)  =  4.7503
the best whole sequence, less what a reader answers  −151.0253 − (−153.9847)  =  2.9594

Both differences are in the units of that score, which are logarithms of probabilities, so a larger difference marks a reading the tables find less likely. The reader’s reading sits between the other two, nearer the maximum than the gap method’s answer is and still short of it.

What that looks like in the answer is the single letter a standing as a word inside a surname. Cutting after the v is defensible on its own and cutting after the a is defensible on its own, and nothing in the method ever puts the two decisions in the same sentence. It is tempting to say the whole-sequence method could not have produced such a thing, and that is not true, which is the subject of the twentieth section.

Two costs, and the honest one is not the time. Reading a text is 8w minus 1 additions per gap at a reach of w, so twenty-three per gap at the reach used here, against the whole-sequence method’s eight comparisons per character. Both are linear in the length of the text and neither grows with the amount of marked-up text behind them, so on a sentence of forty-five characters the difference is a few hundred additions and is not a consideration.

The cost that matters is marked gaps. Our eight sentences hold 189 of them and produce 631 weights, so there are more weights than examples, which is the ordinary situation for this kind of model and is the reason the tenth section’s eight orders disagree. On the generated character language, the gap method needs a hundred and sixty sentences, 1,361 marked gaps, before it passes a whole-sequence method that was already ahead at thirty sentences and 265 gaps.

Set that beside the third section and the trade is visible from both ends. This method needs more marked gaps than the other one to reach the same score, and it can be handed marked gaps that the other one cannot use at all. Which of those dominates is a question about how the annotation was produced rather than about either method.

A gap reads offsets minus w to w minus one and nothing else, so a character further away than that is not part of the question being asked. This is not a matter of the evidence being weak or the corpus being small. The quantity simply has no place in the question, and more text cannot supply one.

That can be measured rather than asserted, by building a language in which the boundary between two characters is decided by a character a known distance away and nothing else. Every run is either p followed by some padding and then ab and cd as two words, or q followed by the same padding and then abcd as one word. Everything between the deciding character and the gap is identical in the two cases, so the gap can only be settled by reading that far back.

…

So the reach is not a tuning parameter in the usual sense of trading accuracy against cost. It is a statement about which dependencies can be written down at all, made before any text is read, and a dependency outside it is invisible rather than poorly estimated. Widening the reach is not free either, since each step raises eight more questions per gap and every one of them needs marked gaps to answer.

Every question a gap is asked was chosen by a person. Somebody decided that single characters and neighbouring pairs are asked about and that triples are not, that seven kinds of character are told apart and not seventy, and that the offsets are treated separately rather than as a bag. Those choices fix what the method can express, and the learning then only settles how much each of the chosen questions counts.

What follows is a ceiling that no amount of text raises. A boundary whose evidence is a triple of characters, or a distinction the seven kinds do not draw, has no question to attach itself to, so the weights cannot represent it however many marked gaps arrive. It is the same shape of limit as the window and it is easier to miss, because widening the questions is a change to the design where widening the reach is a change to a number.

Two things follow that are worth separating. Adding questions widens what can be represented and at the same time thins the evidence behind each one, since every new question needs marked gaps to settle it and our eight sentences already raise 631 of them on 189 gaps. And a ceiling set by hand is one that can be raised by hand, which is exactly what the neural descendants of this idea do, replacing the chosen questions with a function that learns what to read.

The assumption underneath every answer on this page is that the boundary at one gap can be settled without knowing the boundary at any other. That assumption is false, and it is worth saying as a fact rather than as a caveat. The gaps of a text are the boundaries of the same words, so the answer at one gap and the answer at the next describe two ends of one object.

What is tempting here is to conclude that the answers can therefore contradict each other in ways a whole-sequence method could not produce, and that turns out to be wrong. Any set of cuts is a segmentation, so there is no arrangement of independent answers that the other method is incapable of returning. I checked it on the case where the argument should be strongest, four marked-up sentences whose every word is exactly two characters long, over all 1,296 four-character texts spellable from their alphabet.

So the difference is not that one method forbids incoherent answers. Both produce them, and here the one with a model of the sentence produces them more often, since it has never seen a one-character word either and what decides those cases for it is the amount added to every count it never saw. The real difference is the one the sixteenth section measured, which is that only one of the two answers is the maximum of anything, and the practical consequence, which the fifteenth section already showed, is that a fact about word shapes has nowhere to be recorded here.

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 each of them changes what comes back.