When the algorithm is a table

A shrink that keeps the length

Substitution costs fitted as letters' positions on a free line find the order of the letters early and invent a line where there is none; charging the line's length never collapsed the invented one, and counting its gaps took the real order away from small corpora. A third rule was proposed: keep every gap the free line keeps, and shrink each gap's length toward the average of the gaps by a weight read from bootstrap resamples, predicted to cost within a tenth of the free line where there is a property and no more than the free line where there is none. The second half holds and the first fails: at 100 pairs the shrunk line's excess is 0.79 bits a thousand columns against the free line's 0.34. Both results have one cause. A shrink toward the gaps' mean keeps their mean, and so the line's whole length, exactly where it was: with no property the line is still 0.57 bits long at 100 pairs when it should have none, and with one the shrink flattens the differences between the gaps, which are what the property put there.

An alignment of two sequences charges every mismatch a cost, and the costs are learned from aligned pairs: the matrix a corpus wrote fitted a full table of them, the grain a corpus chooses for itself let the corpus choose how finely they are rounded, and a cost built from two properties built them from named properties of the letters. A line the corpus finds learned them without being told what makes two letters similar: each of the four letters a, c, g and t gets a position on a line, and a mismatch costs a transversion term plus the distance between the two letters’ positions. The fit has to find both the order of the letters along the line and the gaps between them. On a generator whose letters really sit on a graded property, at 0, 1, 3 and 7 times a fifth of a bit, the free line found the order from about a hundred pairs and the gaps much more slowly. On the plain two-class generator, with no property at all, it invented a line anyway.

A line with a prior toward the classes tried two ways of making the line justify itself. Charging the line for its length, at a rate growing with the corpus, never collapsed the invented line: its median length was still 0.12 bits at 3,200 pairs. Charging it for the number of gaps it keeps, the rule the classes held-out pairs cannot rule out and the partitions are chosen under, collapsed the invented line on every seed — and then took the real line’s order away from every corpus under 1,600 pairs, because a gap of a fifth of a bit does not pay its parameter’s charge until the data are large.

Its closing section read the two failures as acting on one property each: the length charge on how far apart the letters are, the gap count on how many distinct positions there are. It proposed a third rule. 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. It predicted that with a property the rule keeps the free line’s order from 100 pairs with excess bits within a tenth of the free line’s, and that with none its gaps, all noise and all shrunk toward a common small value, cost no more than the free line’s do. The named risk was that second generator: if the rule failed there, no rule that keeps the order early could also refuse a line that is not there.

A weight from the corpus’s own noise

The corpora, generators and scoring are the earlier essays’: sixteen seeds at each of eight sizes from 25 to 3,200 aligned pairs, about 58 aligned columns a pair, every fitted model scored by its excess bits a thousand columns over the generator’s own costs on a fresh corpus. The free line is fitted order by order, exactly, as before.

The shrink needs to know how much each gap is noise. It resamples the corpus’s pairs with replacement 24 times and refits the line on each resample with the order held at the free line’s, which gives each gap a variance across resamples; the average of the three is the noise in one gap. The gaps’ own spread about their mean, less that noise, is the spread the data actually support. Each gap is then moved toward the mean by the empirical-Bayes weight, the supported spread over the supported spread plus the noise: a weight of one leaves the free line’s gaps, a weight of nought sets all three to their mean. The transversion term and the identity share are the free line’s.

The rule is the textbook shrinkage estimator of James and Stein, applied here to three numbers, and it falls as the corpus grows because the bootstrap noise does. It keeps every gap, so the order is the free line’s by construction.

The weight, aimed correctly

The weight does what it was built to: with a property it rises from nought at 25 pairs to 0.98 at 3,200 as the gaps' differences outgrow their noise, and with none it stays under 0.11 to 800 pairs — the shrink is aimed correctly and still cannot helpMean bootstrap weight w over sixteen seeds, where w = 1 leaves the free line's gaps and w = 0 sets every gap to their mean, and the number of seeds at w = 0. With a property: 25: 0.18 (9 at nought), 50: 0.32 (3 at nought), 100: 0.56 (0 at nought), 200: 0.76 (0 at nought), 400: 0.87 (0 at nought), 800: 0.94 (0 at nought), 1,600: 0.97 (0 at nought), 3,200: 0.98 (0 at nought). With none: 25: 0.11 (13), 50: 0.10 (13), 100: 0.11 (12), 200: 0.04 (13), 400: 0.03 (13), 800: 0.09 (13), 1,600: 0.29 (8), 3,200: 0.44 (7).00.2500.5000.7501aligned pairs in the corpusweight left on the gaps' differences25501002004008001,6003,200with a propertywith nonemean over sixteen seedsbootstrap weight
Fig. 1 Mean bootstrap weight over sixteen seeds, one leaving the free line’s gaps and nought setting every gap to their mean. With a property: 0.18 at 25 pairs (nine seeds at nought), 0.32 at 50, 0.56 at 100, 0.76 at 200, 0.87 at 400, 0.94 at 800, 0.97 at 1,600, 0.98 at 3,200. With none: 0.11, 0.10, 0.11, 0.04, 0.03, 0.09, 0.29 and 0.44, with seven to thirteen seeds at nought at every size.

The weight does what it was built to: with a property it rises from nought at 25 pairs to 0.98 at 3,200 as the gaps’ differences outgrow their noise, and with none it stays under 0.11 to 800 pairs — the shrink is aimed correctly and still cannot help. On the generator with a property the bootstrap sees the three gaps differ by more than their noise once the corpus reaches a hundred pairs, and lets them differ. On the generator with none it sees, correctly, that the gaps differ by no more than noise, and sets most of them equal.

The weight with no property creeps up at the largest sizes, to 0.44 at 3,200 pairs. The invented line there is short, a sixth of a bit, and its three gaps are small enough that the bootstrap noise in them is smaller still, so small differences between them look real. That is a weakness of a weight that compares differences with noise, but it is not where the rule fails.

If the weight is right on both generators, the shrink is doing exactly what was asked. The plates that follow show what was asked was the wrong thing.

Where there is a line, a cost

With a property to find, shrinking the gaps toward their mean costs more than leaving them free on every corpus under 400 pairs — 0.79 excess bits a thousand columns at 100 pairs against the free line's 0.34, more than twice, where within a tenth was predicted — and gains a hundredth or two from 400 pairs onThe generator with a graded property, sixteen seeds a size: excess bits a thousand columns on a fresh corpus for the free line, the line with its gaps shrunk toward their mean by the bootstrap weight, the line that counts its gaps, and the line charged for its length. 25 pairs: free line 2.01, gaps shrunk to their mean 3.25, gaps counted 2.94, length charged 4.67; 50 pairs: free line 0.93, gaps shrunk to their mean 1.80, gaps counted 1.18, length charged 1.67; 100 pairs: free line 0.34, gaps shrunk to their mean 0.79, gaps counted 0.60, length charged 0.71; 200 pairs: free line 0.29, gaps shrunk to their mean 0.33, gaps counted 0.57, length charged 0.64; 400 pairs: free line 0.18, gaps shrunk to their mean 0.17, gaps counted 0.49, length charged 0.34; 800 pairs: free line 0.09, gaps shrunk to their mean 0.07, gaps counted 0.19, length charged 0.15; 1,600 pairs: free line 0.03, gaps shrunk to their mean 0.02, gaps counted 0.06, length charged 0.04; 3,200 pairs: free line 0.01, gaps shrunk to their mean 0.00, gaps counted 0.01, length charged 0.02.aligned pairs in the corpusexcess bits a thousand columns (log)25501002004008001,6003,2000.00390.0160.0630.2514gaps countedlength chargedfree linegaps shrunk to their meansixteen seeds a sizeexcess bits, log scale
Fig. 2 The generator with a graded property, sixteen seeds a size: excess bits a thousand columns on a fresh corpus. Free line: 2.01, 0.93, 0.34, 0.29, 0.18, 0.09, 0.03 and 0.01 from 25 to 3,200 pairs. Shrunk toward the mean: 3.25, 1.80, 0.79, 0.33, 0.17, 0.07, 0.02, 0.00. Gaps counted: 2.94, 1.18, 0.60, 0.57, 0.49, 0.19, 0.06, 0.01. Length charged: 4.67, 1.67, 0.71, 0.64, 0.34, 0.15, 0.04, 0.02.

With a property to find, shrinking the gaps toward their mean costs more than leaving them free on every corpus under 400 pairs — 0.79 excess bits a thousand columns at 100 pairs against the free line’s 0.34, more than twice, where within a tenth was predicted — and gains a hundredth or two from 400 pairs on. At 25 pairs the shrunk line is the second worst of the four rules and at 50 the worst; at 100 it is worse than counting gaps and charging length, the two rules it was meant to improve on.

From 400 pairs it is the best of the four by a few hundredths of a bit. That is real, and it is the expected behaviour of a shrinkage estimator: once the gaps are well measured, pulling each slightly toward the others trades a little bias for a little less variance, and the trade is favourable. But a few hundredths of a bit at 400 pairs, where every rule is under half a bit, is not what the rule was for. It was for the small corpora, and there it is the free line’s worst competitor.

The proposal’s prediction kept the free line’s order from 100 pairs, and that half held exactly, as the orders plate shows. The excess is lost with the order intact, which points at the gaps.

The shape the shrink erases

The shrink erases the shape the property gives the line: the generator's gaps are 0.20, 0.40, 0.80, and at 100 pairs the shrunk line's median gaps on the seeds with the right order are 0.28, 0.42, 0.61 against the free line's 0.18, 0.39, 0.73With a property, on the seeds whose free line has the generator's order: the median of each of the three gaps, in bits, for the free line (upper bar) and the shrunk line (lower bar), at four sizes, and the generator's own gaps. 50 pairs (10 seeds): free 0.36, 0.68, 0.94; shrunk 0.61, 0.63, 0.71; 100 pairs (16 seeds): free 0.18, 0.39, 0.73; shrunk 0.28, 0.42, 0.61; 400 pairs (15 seeds): free 0.22, 0.41, 0.84; shrunk 0.25, 0.43, 0.79; 3,200 pairs (16 seeds): free 0.21, 0.42, 0.81; shrunk 0.21, 0.42, 0.81.a to cc to gg to tgenerator50 pairsfreeshrunk100 pairsfreeshrunk400 pairsfreeshrunk3,200 pairsfreeshrunkseeds with the right ordergaps in bits
Fig. 3 With a property, on the seeds whose free line has the generator’s order: the median of each of the three gaps, in bits, for the free line (upper bar) and the shrunk line (lower bar), and the generator’s gaps, 0.20, 0.40 and 0.80. At 100 pairs the free line’s are 0.18, 0.39 and 0.73, the shrunk line’s 0.28, 0.42 and 0.61.

The shrink erases the shape the property gives the line: the generator’s gaps are 0.20, 0.40, 0.80, and at 100 pairs the shrunk line’s median gaps on the seeds with the right order are 0.28, 0.42, 0.61 against the free line’s 0.18, 0.39, 0.73. The free line’s gaps are close to the truth at 100 pairs. The shrunk line’s are pulled toward their common mean, so the small gap is too large and the large gap too small, and the error in each is larger than the free line’s.

That is the cost of the target. Shrinkage toward the mean assumes the quantities being shrunk are alike unless shown otherwise, and on a line with a graded property they are not alike: the gaps double from one to the next. A weight of about a half at 100 pairs, which is what the bootstrap gives, is a statement that the differences between the gaps are about as large as their noise. They are; and halving them halves the property’s signature while the noise it removes is smaller than the bias it adds.

The prediction’s figure, within a tenth of the free line, would need the gaps’ differences to be small compared with their noise. They are the property. A rule that doubts them doubts the thing the data were collected to find.

A shrink that keeps the line’s length

A shrink toward the gaps' mean cannot shorten the line, since the mean is a third of its length: with no property the free line — and so the shrunk one — is still 0.57 bits long at 100 pairs and 0.16 at 3,200, where the true line has no length at allMedian line length, the sum of the three gaps, over sixteen seeds, the free line's and the shrunk line's being equal by construction. With a property (true length 1.40): 25: 1.59, 50: 1.28, 100: 1.27, 200: 1.50, 400: 1.45, 800: 1.45, 1,600: 1.45, 3,200: 1.42. With none (true length 0): 25: 1.41, 50: 0.84, 100: 0.57, 200: 0.40, 400: 0.27, 800: 0.21, 1,600: 0.17, 3,200: 0.16.00.4000.8001.201.60aligned pairs in the corpusline length, bits25501002004008001,6003,200true, with a property: 1.40with a propertywith nonetrue, with none: 0median of sixteen seedsfree and shrunk alike
Fig. 4 Median line length, the sum of the three gaps, over sixteen seeds; the free line’s and the shrunk line’s are equal by construction. With a property (true length 1.40): 1.59, 1.28, 1.27, 1.50, 1.45, 1.45, 1.45 and 1.42 from 25 to 3,200 pairs. With none (true length nought): 1.41, 0.84, 0.57, 0.40, 0.27, 0.21, 0.17 and 0.16.

A shrink toward the gaps’ mean cannot shorten the line, since the mean is a third of its length: with no property the free line — and so the shrunk one — is still 0.57 bits long at 100 pairs and 0.16 at 3,200, where the true line has no length at all. This is the plate that answers the proposal’s question, and it does so by arithmetic. Moving three numbers toward their mean leaves their sum unchanged. The line’s length is the sum of its gaps, so the shrunk line is exactly as long as the free line on every corpus.

On the generator with no property, length is the whole of the error. There is no line; the true gaps are all nought; and the free line’s invented length is what makes it predict fresh data badly. The shrink equalises the invented gaps, which removes a fake shape from a fake line, and leaves the fake line its full length. That is why it costs no more than the free line there, as predicted, and also why it cannot cost much less.

The proposal anticipated the second generator as the risk and asked for no more than the free line’s cost there. It got that. What it did not anticipate is that the rule would be no better than the free line for a reason that does not depend on the data: the rule shrinks the one quantity that is not wrong and preserves the one that is.

Where there is no line

With no property, the shrunk line costs no more than the free line at any size — 2.29 against 2.81 at 25 pairs, the same from 100 on — as predicted, and stays two to four times the gap-counted line's up to 1,600 pairs, 0.20 at 100 pairs against 0.48The two-class generator with no property, sixteen seeds a size: excess bits a thousand columns on a fresh corpus for the free line, the line with its gaps shrunk toward their mean by the bootstrap weight, the line that counts its gaps, and the line charged for its length. 25 pairs: free line 2.81, gaps shrunk to their mean 2.29, gaps counted 0.90, length charged 2.22; 50 pairs: free line 1.09, gaps shrunk to their mean 0.94, gaps counted 0.47, length charged 0.82; 100 pairs: free line 0.48, gaps shrunk to their mean 0.48, gaps counted 0.20, length charged 0.30; 200 pairs: free line 0.31, gaps shrunk to their mean 0.28, gaps counted 0.14, length charged 0.25; 400 pairs: free line 0.19, gaps shrunk to their mean 0.19, gaps counted 0.11, length charged 0.15; 800 pairs: free line 0.09, gaps shrunk to their mean 0.08, gaps counted 0.04, length charged 0.08; 1,600 pairs: free line 0.05, gaps shrunk to their mean 0.04, gaps counted 0.01, length charged 0.05; 3,200 pairs: free line 0.02, gaps shrunk to their mean 0.02, gaps counted 0.00, length charged 0.02.aligned pairs in the corpusexcess bits a thousand columns (log)25501002004008001,6003,2000.000240.000980.00390.0160.0630.2514length chargedfree linegaps shrunk to their meangaps countedsixteen seeds a sizeexcess bits, log scale
Fig. 5 The plain two-class generator, sixteen seeds a size: excess bits a thousand columns. Free line: 2.81, 1.09, 0.48, 0.31, 0.19, 0.09, 0.05, 0.02 from 25 to 3,200 pairs. Shrunk: 2.29, 0.94, 0.48, 0.28, 0.19, 0.08, 0.04, 0.02. Gaps counted: 0.90, 0.47, 0.20, 0.14, 0.11, 0.04, 0.01, 0.00. Length charged: 2.22, 0.82, 0.30, 0.25, 0.15, 0.08, 0.05, 0.02.

With no property, the shrunk line costs no more than the free line at any size — 2.29 against 2.81 at 25 pairs, the same from 100 on — as predicted, and stays two to four times the gap-counted line’s up to 1,600 pairs, 0.20 at 100 pairs against 0.48. The shrink’s small gain at 25 and 50 pairs is the fake shape removed. From 100 pairs, where the invented line is shorter and its shape already nearly flat, there is nothing left for it to remove.

The gap-counted line stays far ahead, because it alone can set a gap to nought and so remove length. The length-charged line sits between them. Of the three rules measured across the two essays, only counting gaps solves the second generator, and only leaving the line free does well on the first at small sizes.

So the proposal’s conclusion arrives by the route it named: no rule here that keeps the order early can also refuse a line that is not there. The shrink was the most direct attempt, and it shows why. Refusing a line means shortening it; keeping the order means keeping the gaps that set it; and a rule that keeps every gap and moves them only toward each other has no way to shorten anything.

Orders, kept and given away

The shrunk line keeps the order wherever the free line finds it — 16 of 16 seeds at 100 pairs — where the gap-counted line has the full line on none until 800 pairs; keeping the order was the half of the proposal that held, and it was the free line's to keepWith a property, seeds of sixteen on which the line has the generator's order (free and shrunk alike) and on which the gap-counted line keeps all three gaps in that order: 25: 10 and 0; 50: 10 and 0; 100: 16 and 0; 200: 16 and 0; 400: 15 and 0; 800: 16 and 5; 1,600: 16 and 12; 3,200: 16 and 16.free and shrunkgaps counted2510 · 05010 · 010016 · 020016 · 040015 · 080016 · 51,60016 · 123,20016 · 16of sixteen seedsright order
Fig. 6 With a property, seeds of sixteen on which the line has the generator’s order — free and shrunk alike — and on which the gap-counted line keeps all three gaps in that order. 25 pairs: 10 and 0. 50: 10 and 0. 100: 16 and 0. 200: 16 and 0. 400: 15 and 0. 800: 16 and 5. 1,600: 16 and 12. 3,200: 16 and 16.

The shrunk line keeps the order wherever the free line finds it — 16 of 16 seeds at 100 pairs — where the gap-counted line has the full line on none until 800 pairs; keeping the order was the half of the proposal that held, and it was the free line’s to keep. The shrink inherits the free line’s order by construction, so this plate is a reminder of what was at stake rather than a result about the shrink.

It is also the measure of how much the gap-counted line gives up. From 100 to 400 pairs the data have found the order on every seed, and the rule that solves the second generator throws it away on every one. Any rule that wanted both would need to keep this column’s left bar and the excess plate’s gap-counted line on the second generator at once.

Two statements, not one

The earlier essay asked 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. The shrink sharpens the answer. The order is a statement about the gaps’ signs — which letter is next to which — and the free line makes it early. The existence of a line is a statement about the gaps’ sizes, chiefly their sum. The shape, how the gaps differ from each other, is a third statement, and it is the one the shrink acted on.

A corpus of a hundred pairs supports the first statement on every seed and the third on most of them, since the free line’s gaps at 100 pairs are already near the truth. It does not support the second on the generator with no property: the free line invents a length of half a bit, and nothing about the order or the shape says whether that length is real. A rule that is to tell the generators apart early must act on the length, and must do so without touching the gaps’ signs, which is what neither a gap count nor a shrink toward the mean can do.

That points at a shrink with a different target: the line’s length toward nought, the gaps scaled together so that their ratios and their order are kept and only the line’s overall size is doubted.

Where James and Stein help

The shrinkage estimator has a famous result behind it: for three or more means measured with equal noise, pulling each toward their common average lowers the total squared error whatever the true means are. That theorem holds here too, in its own terms. What it promises is a smaller total squared error in the three gaps, and it says nothing about which errors matter to the model’s predictions. Excess bits penalise errors in the gaps through the probabilities they imply, and those probabilities depend on sums of consecutive gaps — the distance from a to t is all three — so an error that spreads evenly across the gaps, as shrinkage does, is magnified in the long distances that carry the property.

The theorem also assumes the means are exchangeable before the data arrive, that nothing distinguishes one from another. On the generator with a property the gaps are not exchangeable: they are differences between values that grow geometrically, so the largest gap is expected to be the largest. A target that respected that, shrinking toward a fitted progression rather than a flat mean, would be a model of the property, which is what the free line was introduced to avoid needing.

What the replays do not settle

One shrinkage rule. The weight is the James–Stein form for three numbers with a common noise. A weight for each gap separately, or a different target such as the gaps’ median, was not tried; neither changes the sum’s invariance unless the target itself is shorter.

Bootstraps on the fixed order. The noise is measured with the order held at the free line’s, which understates it on small corpora where the order itself is uncertain.

Gap costs held fixed. Opening and extending a gap cost the same throughout; the parameter plane has few answers found the optimal alignment takes only a few values across hundreds of gap settings, so they were not refitted.

Two generators. The graded property’s gaps double from one to the next. A property with three equal gaps would be one a shrink toward the mean could only help.

Excess bits. Every comparison is the model’s predictive cost on a fresh corpus, the stricter measure; the ties a rounded matrix makes showed that a refitted table moves mainly the alignments that sit on a tie, so alignments follow a table’s errors only loosely. Alignments were not scored, since the earlier essay found them to follow excess bits.

Still open: the line’s length doubted by itself

The shrink failed because it moved the gaps toward each other and never toward nought, and the length is the sum it preserved. The other shrink keeps the gaps’ ratios and doubts the sum: scale every gap by one factor, read from the bootstrap spread of the line’s total length against its size, so that a line whose length is no larger than its noise collapses toward the two-class matrix while its order, carried in the ratios, is kept for whenever the length returns.

The measurement that follows fits that scaled line on both generators at every size, with the factor set as the same empirical-Bayes weight applied to the length alone, beside the free and gap-counted lines. The prediction is that with no property it reaches within a tenth of a bit of the gap-counted line from 100 pairs, because the invented length, half a bit at 100 pairs, is about its own noise, and that with a property it costs no more than the free line from 100 pairs, because a length of 1.4 bits measured from a hundred pairs is far larger than its noise. It could fail at the smallest corpora with a property, where the length’s noise is as large as the length and the factor would shrink a real line toward the two-class matrix. The question is whether a line’s existence can be doubted without doubting its shape, and whether one number, its length, is enough to carry the doubt.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

EstimatorFittingModel selectionOverfittingPredictionSubstitution matrix