A line with a prior toward the classes

A line the corpus finds fitted substitution costs for a four-letter alphabet without being told what makes two letters similar. Each letter got a position on a line, and a mismatch between two letters cost a transversion term plus the distance between their positions, so the fit had to find both the letters’ order and their spacing from a corpus of aligned pairs. On a generator whose letters really do sit on a graded property — a, c, g and t at 0, 1, 3 and 7, each step a fifth of a bit — the fitted line found the generator’s order from about a hundred pairs and its spacing much more slowly. On a generator with no property at all, the plain two-class matrix of transitions and transversions, it invented a line, with a median length of 0.40 bits at 200 pairs, and predicted fresh data worse than the partition a growing penalty chose.

Its closing section read both failures as one fact: the gaps between the letters are free, and nothing pulls them toward any value before the data does. It proposed a prior. Put a cost in bits on the line’s length, the sum of its gaps, and fit the positions under it, with the cost growing with the corpus as the partitions’ penalty does; a large cost collapses the line to the two-class matrix, a cost of nought is the free line. It predicted that on the generator with no property the charged line collapses to nearly nothing from 50 pairs and matches the chosen partition, and that on the generator with a property it costs a little at small sizes and nothing from 400 pairs, aligning as well as the free line everywhere and better than the partition from 200. It named the failure: a cost strong enough to collapse a line of noise would also collapse the fifth of a bit between a and c, and then the model would have the order wrong exactly where the free line had it right.

Two ways to charge a line #

The corpora, the generators and the scoring are the earlier pages’: sixteen seeds at each of eight corpus sizes from 25 to 3,200 aligned pairs, every fitted model scored by its excess bits a pair over the generator’s own costs on a fresh corpus. The free line is fitted as before, order by order, the likelihood concave in the gaps once the order is fixed.

The proposal’s charge is a cost on the line’s length: $\tfrac12 c \log_2 n$ bits of log-likelihood for every bit the line spans, with $n$ the corpus’s aligned columns — about fifty-eight to a pair — at two strengths, $c = 0.5$ and $c = 1$. The growth with $\log_2 n$ is the partitions’ own: the chosen partition is the one whose likelihood exceeds its rivals’ by more than $\tfrac12 \log_2 n$ bits for each extra class. A linear charge on the gaps keeps every order’s fit concave, so it is still exact, and a gap the data do not pull hard enough is held at nought.

A second charge was added when the first had been measured, for reasons the plates make plain. It charges the line for the number of gaps it keeps, not their length: every order and every subset of its three gaps held at nought is fitted, and the fit kept is the one whose likelihood less $\tfrac12 \log_2 n$ bits a free parameter is greatest. That is exactly the rule the partitions are chosen under, applied to the line. A line with no gap kept is the two-class matrix; a line with all three is the free line.

Where there is no line #

On the generator with no property, counting the line’s gaps finds that there is no line at every size: the gap-counted line keeps no gap on any of sixteen seeds from 25 pairs to 3,200, and is then the chosen partition to the bit, 0.041 excess bits a pair at 800 against the free line’s 0.090. At 25 pairs it is better than the partition, 0.902 against 1.244, most likely because there the partition’s choice among many ways to group six pairs is noisy and the line’s choice — none of three gaps — is not.

The charge on length does less than predicted. It helps the free line, by a quarter at 50 pairs and nearly two fifths at 100, but it never matches the partition, and at the largest corpora it is worse than the free line: 0.022 excess bits a pair at 3,200 against 0.017. The prediction that it would collapse the line from 50 pairs is the one this plate refuses most plainly, and the next one shows why.

Charging a line for its length shortens it and never removes it: the line charged at the partitions’ full rate still has a median length of 0.07 bits at 800 pairs and 0.12 at 3,200. The free line shrinks too as the corpus grows, from 1.41 bits at 25 pairs to 0.16 at 3,200, because noise opens smaller gaps in a larger corpus; the charged line follows it down and then levels off at about the same length.

The arithmetic suggests why, though it was not run as a measurement. A gap that noise opens is worth, in log-likelihood, roughly what the noise in the six pair frequencies is worth, and that grows with the square root of the corpus. The charge grows with its logarithm. At 25 pairs the corpus has 1,463 aligned columns, whose square root is 38 and logarithm 10.5; at 3,200 pairs it has 188,061, whose square root is 434 and logarithm 17.5. A linear charge on a length is weak where it is needed most, at large corpora where nothing else will tell a noise gap from a real one, and a charge strong enough to close noise gaps at 3,200 pairs would have to grow as fast as the noise does. Counting gaps sidesteps the scale: a gap kept costs the same however short it is, and a noise gap buys too little likelihood to pay for itself at any length.

Where there is a line #

Where a line is there, counting its gaps holds it back: at 200 pairs the gap-counted line is 0.566 excess bits a pair against the free line’s 0.290, and it catches up only at 3,200 pairs, 0.011 against 0.011. Charging the length is worse still at small sizes, 0.638 at 200 and 4.673 at 25 where the free line is at 2.007. Both priors beat the chosen partition at most sizes, because a line with one gap is already a better shape for these costs than any partition of the six pairs, but neither comes near the free line until the corpus is large.

The prediction for the generator with a property was that the charge would cost a little at small sizes and nothing from 400 pairs. At 400 pairs the length charge costs 0.340 excess bits a pair against the free line’s 0.178, nearly twice as much, and gap-counting 0.488, nearly three times. Both priors work as priors: they pull the fit toward the two-class matrix, and on this generator the two-class matrix is wrong by a graded property, so they pull toward the wrong answer until the data outweigh them.

A charge on the line’s length takes the order away exactly where the free line had found it: at 100 pairs the free line has the generator’s order on all sixteen seeds, and the line charged at half the partitions’ rate has it on none. This is the failure the proposal named, and it is complete rather than partial. The gap between a and c is a fifth of a bit; the charge at 100 pairs, 5,867 aligned columns, is 3.1 bits for every bit of length at half rate, and closing a fifth-of-a-bit gap saves six tenths of a bit of charge for very little likelihood. The charged line closes it, a and c land on one point, and an order with them swapped fits as well as the right one. At the full rate the order comes back only at 800 pairs.

Gap-counting does the same thing for a different reason. Keeping a gap costs half $\log_2 n$ bits whatever its length, and the a–c gap and the c–g gap, two-fifths of a bit, do not buy that much likelihood until the corpus is large.

The line, one gap at a time #

The gap-counted line keeps one gap from 50 pairs to 400, two or three only at 800, and all three on twelve seeds of sixteen at 1,600 pairs and all sixteen at 3,200. A line with one gap is a partition of the four letters into two groups placed some distance apart, which is a two-class model with a fitted distance; with two gaps it is three groups; with three it is the full line. The gap-counted fit climbs that ladder of models in order as the corpus grows, adding a gap when its likelihood pays half $\log_2 n$ bits for it, which is how the classes held-out pairs cannot rule out found the partitions themselves growing.

That makes the gap-counted line’s result on the generator with a property less a failure than a statement about what the corpus can establish. At 400 pairs the data do not say, at the partitions’ level of confidence, that there are three distinct gaps; they say there is one. The free line answers a question the corpus cannot answer at that size — what are the three gaps — and happens to answer it nearly right, because the generator does have three gaps. On the generator without a property it answers the same question just as confidently and is wrong.

Why the order goes first #

The two charges take away different things, and the difference says what the free line had learned at a hundred pairs. Its order was right on every seed and its spacing was not yet: a line the corpus finds found the order learned quickly and the spacing slowly. The order is a statement about which pairs of letters are closer than which, and the six pair frequencies say that early, because the three pairs that span the long g–t gap, four fifths of a bit, cost noticeably more than the rest. The spacing is a statement about how much closer, and that needs every gap estimated well.

A length charge acts on the spacing and destroys the order as a side effect. Pulling all three gaps toward nought by the same charge a bit pulls the shortest one, a–c, to nought first; with a and c on one point, the fit cannot say which comes first, and any order that swaps them fits as well. Gap-counting acts on the number of distinct positions, which is exactly the statement the corpus makes last, and it removes a–c first for the same reason. Both priors are priors toward fewer distinctions, and the letters’ order is the distinction a short gap carries.

The grain a corpus chooses for itself met the same short gap from the other side: a rounding lattice for fitted costs was set by whichever two costs happened to sit closest, and on resamples of one corpus that grain ranged over a factor of six. A gap of a fifth of a bit is where every estimate of this alphabet’s costs is least certain, and every rule that simplifies the costs simplifies it first.

What one rule can tell #

The proposal ended on the question whether one rule can tell a short line that is there from a short line that is not, or whether that is the question the corpus cannot answer at any size worth having. These plates answer it in two parts. A rule that charges for the line’s length cannot tell them apart at any size: it shortens both and removes neither, and it takes the real line’s order away while leaving a noise line in place. A rule that charges for the number of gaps can tell them apart at every size, and the price is that it believes the real line only once the corpus would convince the partitions’ rule of three distinct gaps — 1,600 pairs here, where the free line had the order from 100.

There is no rule in between that has both. The free line’s advantage on the generator with a property is precisely its willingness to fit gaps the data do not yet justify, and that willingness is what invents a line on the generator without one. The matrix a corpus wrote and the pages after it found that a substitution matrix is a statement about a corpus rather than about an alphabet; here the statement has a confidence attached, and the two models make the same statement with different confidence. Which to want depends on what is known before the corpus arrives. Told there is a graded property, a cost built from two properties needed fifty pairs. Not told, the honest model is the one that waits.

What these generators do not settle #

Two generators. One generator has a graded property with gaps of a fifth, two fifths and four fifths of a bit; the other has none. A property with larger gaps would be believed sooner by gap-counting and lose its order to the length charge later; one with smaller gaps the other way.

Two kinds of charge. The length charge was run at two strengths, both growing as $\log_2 n$. A charge growing as the square root of the corpus, which the arithmetic suggests would be needed to close noise gaps, was not run, and would take the real line’s order away even more surely at small sizes.

Excess bits, not alignments. Every model is scored by excess bits a pair on a fresh corpus, and by whether it finds the order — not by the optimal alignments its costs choose, which the parameter plane has few answers found can stay the same across wide changes in the costs. How many test alignments each model gets right, which the earlier pages also scored, was not measured; the ties a rounded matrix makes is the reminder that the two scores can disagree when costs are close.

Still open: a line that keeps its gaps and doubts their lengths #

The two charges fail in opposite ways because each acts on only one of the line’s two properties: the length charge on how far apart the letters are, the gap count on how many distinct positions there are. A third rule could keep every gap the free line keeps — so the order the data find early is never taken away — and shrink each gap’s length toward the average of the gaps, rather than toward nought, by an amount that falls as the corpus grows.

The measurement that follows fits that line, with the shrinkage set by the gaps’ own spread across bootstrap resamples of the corpus, on both generators at every size. The prediction is that on the generator with a property it keeps the free line’s order from 100 pairs and its excess bits within a tenth of the free line’s, and that on the generator with no property its gaps, all noise and all shrunk toward a common small value, cost no more than the free line’s do now — which is still far worse than the gap-counted line. It could fail on that second generator alone, and if it does the conclusion is that no rule that keeps the order early can also refuse a line that is not there. The question is whether the order of the letters and the existence of a line are separable statements a corpus can support at different sizes, or one statement it supports all at once.