The Pattern Language Models Use

The four rules on the pages before this one disagree about almost everything, and agree about one thing without ever saying so. Splitting on spaces asks where the gaps are, the boundary rules ask which pairs of characters a word may break between, the annotation rules ask which units a grammar talks about, and the translation rules ask what a phrase table should have a row for. Every one of them answers with the writing and throws the spacing away.

That is invisible until something has to go the other way. A model that reads text and produces text has to hand a person a sentence at the end, and if the pieces it was trained on do not carry the spacing then something else has to put the spacing back by guessing. We carry the same sentence the other pages carry, since it breaks in the places that matter.

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

Fifty-one characters, of which six are spaces. Every one of the four rules gives back some arrangement of the other forty-five, and none of them gives back a single one of the six.

Here is the whole method applied once. Fourteen pieces, each shown with the half-open span of the sentence it stands for, and a raised dot standing where a space is, since a space at the front of a piece is the entire point and is otherwise impossible to see.

Dr           [0, 2)      ·the         [25, 29)
.            [2, 3)      ·low         [29, 33)
·Alvarez     [3, 11)     -            [33, 34)
·didn        [11, 16)    cost         [34, 38)
't           [16, 18)    ·re          [38, 41)
·expect      [18, 25)    -            [41, 42)
                         analysis     [42, 50)
                         .            [50, 51)

Notice what that does to a word that turns up twice. cost at position 34 follows a hyphen, so it carries no space, while expect at position 18 follows a space and carries one. Those are two different pieces even where they would be the same word, and section 16 counts what that costs.

The test is worth stating before the numbers. Take the pieces, throw the spans away, write them one after another with nothing at all between them, and ask whether what comes out is the sentence. Not the sentence less its spacing, which is the most any of the four earlier rules can manage, but the sentence.

…

The pattern passes, on all six sentences of the notebook. The crudest rule fails and is rescued by putting one space between every pair, which happens to reproduce all six because the notebook is written with single spaces and no punctuation standing alone. The other three fail both tests, since a full stop with a space in front of it is not English, so anything reading their pieces needs a second set of conventions about the language before it can produce a sentence at all.

The sharpest way to see what discarding the spacing costs is to write two texts that differ in nothing else. Put one two beside one  two, with two spaces in the second, and ask each rule what it makes of them.

All four earlier rules answer with the identical two pieces both times, and the panel above puts three more pairs to them, a doubled space inside a sentence, a tab standing where a space stood and a line break standing where a space stood. In all sixteen of those readings the two texts of a pair came back as one answer. Under the pattern all four pairs come back as two answers, because the spacing is inside the pieces rather than between them.

That looks at first like a small matter of tidiness, and what it actually bounds is what a model can be asked for. A model trained on pieces that cannot tell a line break from a space has no way to produce a line break, and a list, a table or a program is laid out in precisely the characters those rules threw away.

The four earlier rules are lists of clauses, and one of them needs a data file besides. This one is a single regular expression, and the expression is the whole of the method. Every non-empty match is a piece, the matches are taken left to right without overlapping, and there is nothing else.

's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+

Read the vertical bars as the word “or” and the expression is a list of twelve things, tried in the order they are written. At each position the engine tries the first, then the second, and takes the first one that succeeds; that match becomes a piece, and the search starts again from the character after it. So the order carries weight of its own, since it is what settles every position where two branches could both have matched.

A regular expression is a description of a set of strings, written in a small notation of its own, and an engine is the program that reads the description and finds the stretches of a text that fit it. The notation is large, and this expression uses very little of it. The ten marks below are all of them, and each of the next four sections is one or two of them at work.

Read with those, the eighth branch says an optional space followed by one or more letters, and the eleventh says one or more characters of spacing with nothing but spacing, or nothing at all, coming next.

Three of the twelve read the writing, two read the spacing, and the seven at the front are a list of English contractions which Part 3 is about. The next three sections take the middle five one at a time.

The middle three branches are the ones doing nearly all the work. They say that a run of letters is one thing, a run of digits is one thing, and a run of anything else that is not spacing is one thing, and they are tried in that order.

 ?\p{L}+        a run of letters
 ?\p{N}+        a run of numbers
 ?[^\s\p{L}\p{N}]+   a run of everything else that is not spacing

Between them those three classes account for every character that is not spacing, with no character in two of them, which is why nothing is ever dropped and why every position starts a match. That is also exactly the repair the pattern was written for. A run of letters stops at a full stop whether or not a linguist would call the stop part of the word, so dog and dog. are never two rows in anything learned afterwards, and the rule needed no list of abbreviations and no knowledge of English to say so.

What it costs is the reverse case. On our sentence low-cost comes apart into three pieces and re-analysis into three more, because a hyphen is not a letter, and 3.14 would come apart into three as well. The rule knows nothing about compounds and nothing about numbers, and that is the same fact as its knowing nothing about abbreviations.

Each of those three branches begins with  ?, a space followed by a question mark, which in this notation means one space if there is one and nothing if there is not. So a run of letters reaches backwards by one character and takes the space in front of it along.

the drift    ->    "the"  " drift"
thedrift     ->    "thedrift"

Everything the space attachment buys follows from that one optional character. The spacing ends up inside the pieces, so the pieces join back to the writing. A word that begins a line and the same word in the middle of a sentence become two different pieces, which is information a model can use, since in English they are genuinely different situations. And a vocabulary learned over these pieces afterwards will hold  the with its space rather than the without it, which is why the pieces such a model works in so often look like words with a space stuck to the front.

It also buys length, which was the stated reason. Deleting those three characters from the pattern and changing nothing else turns our sentence from fourteen pieces into twenty, since each of the six spaces then stands alone, and turns the six sentences of the notebook from 85 pieces into 142.

142 − 85   =  57 pieces saved
57 / 142   ≈  40 per cent

That is 57 pieces saved on six sentences, or a text forty per cent shorter for everything downstream to read. The 57 is also the number of spaces in the six sentences, since the only thing the change does is decide whether a space is a piece of its own or the front of the piece after it.

The eleventh branch is the one that looks fussy on first reading and turns out to be protecting the previous three. It is \s+(?!\S), which reads as a run of spacing that is not followed by anything other than spacing.

Consider two spaces in a row. The word branches cannot start there, since each takes at most one space and then needs a letter. The greedy reading would take both spaces as one piece and leave the following word bare. This branch refuses to do that. It takes as much spacing as it can while stopping short of the next piece of writing, so it hands the final space back for the following word to claim.

Dr.  Alvarez  didn't expect

with it        Dr  .  ·  ·Alvarez  ·  ·didn  't  ·expect
without it     Dr  .  ··  Alvarez  ··  didn  't  ·expect

Attaching the space to the following word is only worth doing if a word reliably has its space, and irregular spacing is exactly the case where it would not, which is what the branch is for. Six sentences of ordinary prose never reach this branch at all, because a single space is claimed by the word after it and the branch is never tried.

The last branch is a bare run of spacing, which catches whatever is left, and that is the twelve. It is worth seeing which of them actually do anything, since a rule with twelve clauses and a rule with four are different objects however the first is written.

…

Over the six sentences, four of the twelve claimed a piece. The letters branch took 68 of the 85, which is four pieces in five; the marks branch took 15; the digits branch took one, which is the year in the third sentence; and one of the seven contractions took one, which is the ’t of didn’t. The other eight branches, six contractions and both spacing branches, never fired. The spacing branches are unreached because single spaces are claimed by the words after them, which is the previous section’s point arriving as a count.

One more thing about the notation, which is a small point and a real one. An expression that is not well formed is refused before it reads any text at all, since a bracket that never closes names no set of matches and therefore no rule. Three plausible mistypings of a single branch are in the panel above and all three are refused. That is the one kind of error this method can report; every other failure it has is silent, which is Part 6.

The seven branches at the head of the expression are seven literal spellings, and they are the only place in the whole pattern where a particular language appears.

's   't   're   've   'm   'll   'd

Being first is what makes them do anything. An apostrophe is not a letter, so without these seven the marks branch would claim it, and didn’t would come out as three pieces rather than two. Deleting them from the pattern and changing nothing else takes our sentence from fourteen pieces to fifteen, with ’ and t standing separately where ’t stood.

Notice also that these seven carry no optional space, unlike the three branches beneath them. That is not an oversight. A contraction ending never has a space in front of it, since it is glued to the word it belongs to, so an optional space would match nothing it was not going to match anyway.

What they catch is a verb ending that English writes as part of the previous word. Six of the seven are verb forms, and one, the first, is the possessive that is spelt the same way as the contraction of is.

The cut falls at the apostrophe every time, which is the translation rules’ choice rather than the annotation rules’. On didn’t the annotation rules produce did and n’t, because the negation is a morpheme spelt with the n; here the pieces are ·didn and ’t, so the second is not a morpheme of anything and the first is not a word. What makes that acceptable is that nothing downstream is expected to read a piece as a word.

A list of seven literal spellings misses everything that is not one of those seven spellings, and the interesting part is how ordinary the misses are. I put twelve texts to the branch, chosen to be things a person actually types, and six of them matched nothing.

…

Two of the misses are the same word written slightly differently. A sentence in capitals misses, because the seven are written in small letters and the notation is case sensitive, so IT’S comes out as three pieces where it’s comes out as two. A word processor’s curved apostrophe misses, because the seven name the straight one, and didn’t typed that way comes out as three pieces where the same word typed with the straight mark comes out as two. Both of those are the same sentence to a reader and two different sequences to whatever reads the pieces.

One miss is no contraction at all. The apostrophe of the students’ notes has no letter after it, so none of the seven spellings can begin there, and it stands alone as a mark between ·students and ·notes.

The other three are words the list simply does not hold. y’all and o’clock come apart into three pieces each, and a French l’analyse comes apart into three as well, with the article and the noun in separate pieces and the mark alone between them. The annotation rules keep all three whole, which is one of the two places on this page where a rule from an earlier page is straightforwardly ahead of this one, and section 17 is the other.

The misses are one half of what a list of spellings does, and this is the other. The branch matching ’t was written for the end of didn’t, and it fires on any apostrophe followed by a t, wherever that pair stands.

didn't cold    ->    didn    't    ·cold
'twas cold     ->    't      was   ·cold

In the second the pattern has cut a word at its own beginning and produced a piece that stands for the elided it of an archaic it was, using a branch whose only reason for existing is the negation. Nothing is wrong with the pieces, in the sense that they join back to the word, and the piece is nonetheless the wrong piece, since it will share a row in everything downstream with every negated verb in the corpus.

These are not academic complaints, and the evidence is that the tokenizers released for the models after this one repair two of them and leave the rest. The panel above shows both changes on the texts that exhibit them.

's|'t|'re|'ve|'m|'ll|'d     becomes    (?i:'s|'t|'re|'ve|'m|'ll|'d)
 ?\p{N}+                    becomes     ?\p{N}{1,3}

The first makes the seven spellings insensitive to case, so a sentence shouted in capitals is cut the same way as the same sentence written normally, and the seven-piece reading of THE DRIFT DIDN’T GO AWAY becomes a six-piece one. The second caps a run of digits at three characters, so 1000000 becomes three pieces rather than one, and a long figure the model has never seen before becomes groups of digits it has seen many times. That one costs length, since the same sentence goes from seven pieces to nine.

What did not change is the case that has no cheap repair. Nothing in either pattern catches the curved apostrophe, nothing holds y’all, and the cut on didn’t still falls at the mark rather than in front of the negation. Those are the ones that would need a list per language rather than a change to a branch.

The bill is length. Everything reading the text afterwards pays per piece, and a model that compares every position with every other position pays roughly with the square of the count, so a rule that separates a hyphen is spending on every pass over the corpus for the rest of the pipeline’s life.

…

Over the six sentences the pattern gives 85 pieces where splitting on spaces gives 63, the boundary rules give 69 and both rule lists give 72.

85 − 63   =  22 more pieces
22 / 63   ≈  35 per cent

That is 35 per cent more than the crudest rule from identical writing, and it is the largest count of the five. It also keeps all 375 characters where the three rules that keep the writing keep 318 and the boundary rules keep 303, so part of the extra length is the spacing itself now being carried.

The row worth reading twice is the last one, which is the pattern with its optional space deleted. That gives 142 pieces for the same six sentences, and it is the honest comparison, since it is the only other arrangement that also gives every sentence back. Against a rule that keeps the spacing at all, 85 is the short answer rather than the long one.

The cost that is not length is the one the space attachment causes directly. A word carries its leading space, so the same word with and without one are two different pieces, and anything counting pieces afterwards keeps two rows where a rule that discarded the spacing would keep one.

Over the six sentences the pattern produces 53 different pieces, where splitting on spaces produces 47, the boundary rules 47, the annotation rules 48 and the translation rules 49. Forty-one of the 53 begin with a space. Two words are spelt both ways in the same six sentences, and the panel above names them. Alvarez begins the third sentence and stands mid-sentence in the first, and analysis stands after a space twice and after the hyphen of re-analysis twice.

There is a kind of writing on which this method does nothing whatever, and it is not an exotic one. Handed a sentence in a script that puts no spaces between its words, the pattern finds a single run of letters and answers with one piece.

低コストの再分析

        the pattern        one piece, the whole sentence
        the boundary rules 低  コスト  の  再  分  析

The boundary rules of the second sibling page give six pieces there, because the standard has rules about which scripts break between characters and this pattern has a class called “letter” and nothing else. The pattern is not wrong in any sense it would recognise, since its pieces do join back to the sentence; it has simply found nothing. Whatever runs afterwards has to do the entire job, and the pages on maximum matching and the word lattice are about doing it.

That is the honest description of what the pattern is for. It is a cheap first cut that stops a later stage from joining characters that should not be joined, and where the writing has no spaces there is almost nothing for it to stop.

It is worth being exact about where this method stops, because the pieces on this page are not what a model reads. They are the units a vocabulary is then learned inside, and ·Alvarez will very likely be cut again into two or three smaller pieces by the method on the byte pair encoding page.

What the pattern does is forbid certain joins. A later stage that counts adjacent pairs and merges the commonest will never be offered the pair that would make dog. one unit, because the g and the . are in different pieces and it never sees across a boundary. That is why the pattern had to come first and why it can be as crude as it is; the refinement happens afterwards and this stage only has to stop the refinement from going somewhere it should not.

Everything above has been read off the published expression, and running it requires an engine, and this is where a pattern turns out not to be quite a rule. Two of the classes in it are named by Unicode general category. A letter is anything the standard files under the letter categories, written \p{L}, and a number is anything filed under the number categories, written \p{N}.

Python’s own regular expression engine has no such notation, and the published pattern was written for a third-party one that does. So running it here means writing the two classes another way, and the two nearest things available are not the same two classes.

Start with the third class, because its failure is the loudest and the easiest to check. The published version says everything that is not spacing, a letter or a number, and the underscore is none of those three, so it is caught. The obvious short form here says everything that is not spacing and not a word character, and to this engine the underscore is a word character.

So the underscore falls into no class at all. It is not a letter under the first branch, which excludes it explicitly, it is not a digit, it is not caught by the short form of the third, and it is not spacing. No branch matches at that position, the engine advances one character, and the character is simply gone.

re-analysis_2019.csv

written out    re  -  analysis  _  2019  .  csv     joins back to the name
short form     re  -  analysis     2019  .  csv     one character is in no piece

The letters and the numbers are the pair that cannot be repaired, and the reason is a disagreement about what counts as a digit. To measure it, I built the published classes out of Unicode’s own general categories, one codepoint at a time over all 1,114,112 of them, so both readings run through the same machinery and the classes are the only thing between them.

…

Unicode files 1,831 characters under a number category. Of those, 680 are decimal digits and are numbers under both readings. The remaining 1,151, which is where Roman numerals, vulgar fractions, superscripts and subscripts live, are numbers to the published classes and letters here, because the test for a letter used here is a word character that is not a decimal digit and those characters pass it. In the other direction there is no disagreement at all. All 136,104 characters Unicode files as letters are letters under both readings.

Three of the seven texts in the panel split differently, and they are the ones to quote. 1½ is one piece as published and two here, since the published reading joins the figure and the fraction into one run of numbers while here the figure is a digit and the fraction is a letter. aⅫ is two pieces as published and one here, for the mirror-image reason. And a² and x₂ are each cut in two as published and each kept whole here.

Before treating that as a serious defect it is worth asking when it shows, because a character being in the wrong class is not the same as a text being cut differently. The classes only decide where one run stops and the next begins, so a character with spacing on both sides is a run of one whichever class it is in.

I put each of the 1,151 into four arrangements and asked whether the two readings gave different pieces. Standing alone between two spaces, 0 of the 1,151 split differently. Directly after a letter, all 1,151 did. Directly after a digit, all 1,151 did. Directly before a letter, all 1,151 did. The condition is exactly adjacency, with no exceptions in either direction, and chapter Ⅻ of the agreement is read identically by both while 1½ is not.

On ordinary English writing it therefore never shows. All six sentences of the notebook are cut identically by both readings, as are the Cyrillic and Arabic-digit texts in the panel, and no alphabetic script can produce a difference at all, since every one of the 136,104 characters Unicode calls a letter is a letter under both readings. The difference is confined to writing that puts one of a particular 1,151 characters directly against a letter or a digit, which is a real kind of writing and a narrow one.

Five of the twelve branches read character kinds and apply to any writing at all. The other seven are a list of English verb endings, and they sit at the head of the expression where they are tried before everything else, so the part of the method that is specific to one language is also the part that runs first.

What that costs on another language is not that the pattern does the wrong thing there, since it has nothing to say about the case at all. A French text meets a rule that cuts after ’t and has no clause at all for l’, so l’analyse is three pieces and c’était would be three, while an English contraction beside them is two. There is no setting to change and nothing to load, because the list is written into the expression.

What is genuinely open is which way that should be resolved, and it is a real decision rather than an oversight. Dropping the seven makes the pattern language-neutral and costs one more piece per contraction in English, which on our sentence is fifteen pieces instead of fourteen. Adding a list per language makes the rule a rule plus a data file, which is the shape the Moses rules page describes at length, with the correctness of the method then located in a document somebody maintains. The published pattern took neither and hard-coded one language, which is a choice defensible only when the corpus is mostly that language.

The deeper thing this method leaves undefined is the one it never claimed. Nothing in the expression refers to a word. There is no vocabulary, no dictionary, no frequency and no notion of a morpheme, and the whole rule is a partition of the characters into kinds together with a statement about where a run of one kind stops.

That is why it will cut a word it has never seen in a place no reader would. re-analysis is a word to anybody reading it and three pieces here, because a hyphen is not a letter. A decimal number is cut at its point, and an address at the character that makes it an address. None of that is a failure of the rule; a run of letters really does stop at the hyphen, and the rule promised exactly that and nothing more.

What follows is that a piece from this method carries no claim at all about meaning, and treating one as a word is the reader importing something the method did not supply. That matters most where the pieces look most like words, which is ordinary English prose, and least where they obviously do not, which is a script with no spaces in it.

The last thing the method leaves open is a property of writing a rule as a pattern at all, rather than anything about this pattern. An expression is a piece of notation, and a piece of notation means whatever the thing reading it takes it to mean.

Part 5 measured one instance of that and it is worth stating in general. The classes an expression names are defined by the engine, so two engines can agree about every operator and part company over what a letter is; and they can also part company over what the operators do, since the greedy and the lazy readings of a repetition, the meaning of a lookahead at the end of a text, and whether a match may be empty are all conventions rather than consequences.

The same expression is then two different rules, and both are being applied faithfully.

The practical consequence is about reporting rather than about quality. Publishing the expression is not the same as publishing the method, so two people who ran that expression over one corpus with different engines have not necessarily measured the same thing, and nothing in either output would say so. On the corpus counted here it would have made no difference, which is the ordinary case and is exactly why the exceptions are hard to notice.

The cases below are gathered from the whole page. The right column says what the method does not determine and why, and it quotes a number where the number is a fact about the method rather than about any particular text.