The classes held-out pairs cannot rule out

The grain a corpus chooses for itself fitted six substitution costs to corpora drawn from a generator that uses two. Transitions — a purine for a purine, a pyrimidine for a pyrimidine — cost 1.64 bits there, and transversions 4.64. The fit estimates each of the six pairs of letters separately, so it returns six numbers, and noise makes them differ. Rounding them to a lattice, which the lattice that decides the ties and the ties a rounded matrix makes had priced, turned out to resolve noise rather than remove it, so the page pooled them after the fit instead. Any two costs within two bootstrap standard errors of each other were merged, and that recovered the generator’s two classes on seven resamples of eight. The resulting matrix chose an alignment the generator agreed with for every one of 200 test pairs.

Its closing section called that a repair made from outside and proposed the principled version. A partition of the six pairs into classes is a model with one cost a class. There are 203 such partitions, from all six pairs in one class to each pair on its own. Fit each, score it by how well it predicts aligned pairs it was not fitted to, and keep the best. The prediction was that on the two-class generator this would agree with the pooling. On a generator with a third class half a bit from its neighbour, it should detect that class at 400 pairs and miss it at 40, and the size where it switches would say what a half-bit difference is worth in evidence.

The measurement follows the proposal exactly and the first prediction fails. What fails, and why, turns out to be the useful part.

Held-out pairs choose the generator’s classes a third of the time #

A corpus is a set of aligned sequence pairs, each 60 letters long before indels, drawn with uniform letters. A letter survives with probability 0.9 and otherwise becomes one of its three partners with probability proportional to a weight a pair: eight for the two transitions, one for each of the four transversions. For each partition of the six pairs, one probability is fitted a class, shared equally among its pairs, from the counts of aligned letter pairs. The score is the log-likelihood of held-out columns under those probabilities. The corpus’s sequence pairs are split into five folds, and each fold is scored under a fit to the other four. A sequence pair is the unit held out, because the columns inside one pair are not independent draws.

Held-out scoring chooses the generator’s two classes on between 2 and 8 of 16 corpora, and it does no better at 3,200 pairs than at 50. At 3,200 pairs a corpus holds 188,106 aligned columns and the six fitted costs are each known to within a few hundredths of a bit. The score still prefers a partition with three or four classes on most seeds. It never merges the two classes the generator keeps apart. It splits classes the generator keeps together.

Two other criteria are drawn on the same plate, and neither uses held-out data. Each takes the fit’s own log-likelihood on the whole corpus and subtracts a penalty a class. The fixed penalty is 1/ln 2 = 1.44 bits a class, the Akaike criterion written in bits. The growing penalty is half the base-2 logarithm of the number of columns, which is the Bayesian information criterion; it runs from 5.3 bits at 25 pairs to 8.8 at 3,200. The fixed penalty finds the two classes about half the time and also does not improve. The growing penalty finds them on 127 of the 128 corpora.

The fixed penalty and held-out scoring behave alike, and that is not a coincidence. Held-out likelihood charges each extra parameter, in expectation, about the same fixed amount the Akaike penalty charges, which is a standard result about the two. That is the whole of the argument below, and it is visible in one number.

A spurious split gains the same at every size #

The question a criterion faces is this. Given the generator’s two classes, one of the eight partitions that split a class in two fits the corpus a little better, because a split lets two counts that differ by noise have two probabilities. By how much?

The best spurious split gains about a bit and a half of fit, at every corpus size. That is what noise does. A corpus of any size has some difference between the counts of ac and gt substitutions. Given two parameters instead of one, the fit spends them on that difference and gains an amount that depends on how large the difference is relative to its own noise. That ratio does not depend on the size of the corpus. With eight splits to choose from, the best one gains a little more. The median across all eight sizes lies between 0.9 and 2.3 bits and shows no trend.

A fixed penalty of 1.44 bits sits in the middle of that distribution, so it rejects the best split on about half the corpora and accepts it on the rest, at every size. Held-out scoring does the same with more variance, because each fold’s score is itself a noisy estimate, and so it accepts the split more often. A penalty that grows with the corpus clears the whole distribution from the start and keeps clearing it by more: 5.3 bits at 25 pairs and 8.8 at 3,200, against a gain that never moves. Of the 128 corpora on the plate, the best split’s gain exceeded the growing penalty on one.

This is the arithmetic behind the plate above, and it explains why more data does not help the first two criteria. More data shrinks every fitted cost’s error. It does not shrink the likelihood gained by fitting that error, because the gain is measured in the same units as the evidence. A criterion whose price for a parameter is fixed can never refuse a spurious one with more than a fixed probability.

A result the size of its own noise met the same shape in a coding experiment. A measured win that never exceeded its own spread across streams was a property of the streams, not of the method. Here the win is a split, and its size is a property of noise that does not shrink with the corpus.

What a spurious split looks like #

The partitions held-out scoring prefers are not far from the generator’s. They split the four transversions and leave the transitions alone, and the costs they give are close together.

On this corpus the held-out score chose four classes. It pooled ac and at, which were 0.04 bits apart, and kept cg and gt separate, 0.29 bits below them and 0.19 above. Those are fair readings of the counts. Taken as costs, they say a c↔g substitution is 22% more likely than an a↔c one, which the generator does not do. The growing penalty returned one transversion cost of 4.72, eight hundredths from the generator’s value, the offset being the fit’s estimate of how often any transversion happens at all.

The split is a claim about the process that drew the corpus. The matrix a corpus wrote built fitted matrices on the principle that a cost is only as good as the counts it came from. Held-out scoring does not violate that principle. It asks a different question, which grouping predicts best, and a grouping that separates two nearly equal counts can predict slightly better on the fold in hand. The growing penalty asks which grouping is most probably the process’s own, and that question can be answered with certainty as the corpus grows. The two questions have different answers, and the proposal on the earlier page named the first while meaning the second.

A class that is there #

The second half of the proposal plants a class and asks when it can be seen. The three-class generator gives two of the four transversions, at and cg, a weight of $1/\sqrt{2}$ instead of one. That makes their cost exactly half a bit higher: 5.10 bits against 4.60 for ac and gt, with the transitions at 1.60. Every letter keeps one partner of each kind, so the letters stay uniform.

The growing penalty finds the half-bit class on none of 16 corpora at 100 pairs, on half at 400, and on every one from 1,600. Its switch is between 200 and 800 pairs, and 400 pairs — about 24,000 aligned columns, of which about 240 are ac or gt substitutions and 165 are at or cg — is where the difference becomes as likely to be seen as not. Below that it says two classes, and it is wrong in the safe direction. It merges the half-bit class into its neighbour, which is what the evidence can support, and it never invents a class.

Held-out scoring’s curve looks better at the small sizes, and it is not. At 100 pairs it chose three classes on ten of the sixteen corpora and the right three on five. The rest split something else, because it splits whatever the noise offers and here the noise and the signal are the same size. From 200 pairs up it holds between 8 and 10 of 16, and it falls back to 8 at 3,200, because past the true partition it keeps splitting. At 3,200 pairs it chose four or five classes on eight corpora, all of them refinements of the generator’s three.

So the prediction’s second half is right about the size and wrong about the criterion. A half-bit class does become visible at about 400 pairs. The criterion that reports it reliably from there is the one that also refuses to report classes that are absent, and held-out scoring cannot refuse.

What the choice does to alignments #

The earlier page scored every matrix by the alignments it chooses, against the generator: an alignment is right if it is optimal under the generator’s own costs. The same scoring separates the partitions here, and it separates them less than the plates above.

At 400 pairs from the two-class generator, a spurious split costs nothing: held-out scoring’s three and four classes get all 200 alignments right on all eight corpora. Its costs differ by a few tenths of a bit within a class the generator treats as one, and that rarely changes which alignment is cheapest. At 100 pairs the extra classes cost more, 191.6 against 198.5, because the split costs are further apart when counts are small and the splits change alignments that trade one transversion for another.

At 1,600 pairs from the three-class generator, the half-bit class matters. A matrix that merges it gets 193.4 alignments right; any matrix that keeps it gets 199.6 or more. Six or seven of 200 test alignments turn on whether at costs half a bit more than ac.

The three-class case at 400 pairs is dominated by something else. On one corpus of the eight the fitted transition and the cheaper transversion add to 6.00 bits, which is exactly the price of two gaps. Every matrix that keeps those two fitted costs, including the generator’s own partition, trades substitutions for gaps on dozens of test pairs and gets 143 right. That is the boundary effect the parameter plane has few answers mapped: an alignment is fixed within a region of cost space and changes at its boundary, and a fitted cost can land on one by chance. The six-cost matrix gets 164 on that corpus, because its separate costs put some of those pairs back on the right side of the boundary.

So the alignment count is the right final score and a poor instrument for choosing among partitions. It turns on a handful of boundaries. The likelihood of held-out columns is the right instrument, and it needs a price for parameters that grows.

Why the growing penalty is the one to use here #

The growing penalty was not proposed on the earlier page, and its success is not an accident of this substitution process. It is built to identify the process that produced the data. Among nested models, it chooses the true one with probability tending to one as the data grow, because a spurious class’s gain stays fixed while the price rises with the logarithm of the columns. Held-out scoring and the fixed penalty are built to choose the model that predicts best, which they do. On a finite corpus the model that predicts best can be one with a spurious class, since the class costs almost nothing in prediction.

Which one a matrix should use depends on what the matrix is for. If the costs are only there to score alignments of more sequences from the same process, the difference is small: the right-alignments plate shows a split within a class costing nothing at 400 pairs. If the costs are read as a statement about the process — that a c↔g change is 22% likelier than an a↔c one — then held-out scoring makes false statements about a third to two thirds of the time at every corpus size, and more data will not fix it.

Fitting a class to measurements grants a growth class only when a fit with that class holds and a fit with one fewer parameter does not. The growing penalty is the same standard applied to substitution costs, and it is the standard the pooling on the earlier page approximated. Two standard errors is a fixed threshold — a constant of the kind the threshold somebody chose went looking for — and the pooling found two classes on seven of eight corpora at 400 pairs. On the three-class generator it found the half-bit class on four of eight at 400 and eight of eight at 1,600, almost exactly the growing penalty’s record. The earlier page’s repair was closer to right than the principled version it proposed.

What was measured and what was not #

A generator whose classes are exact. Every cost here belongs to a class with exactly one value. A real substitution process — twenty amino acids, graded by chemistry — may have no exact classes at all, and then every criterion is choosing how much of a continuum to resolve. The growing penalty would keep splitting as the data grew, correctly, and the question would become which resolution is useful rather than which is true.

Letters that are uniform. The fit here uses one probability a class and a uniform background, which is exact for these generators. A real alphabet’s letter frequencies differ, and a class of pairs would then need its costs fitted as log-odds against each pair’s background rather than as one shared probability.

Five folds and one shuffle. Held-out scoring was run with one assignment of sequence pairs to five folds. A different number of folds changes its variance and slightly changes its effective penalty. Leaving out one pair at a time makes it behave still more like the fixed penalty, which is the direction the measured criterion was already failing in.

All 203 partitions, including absurd ones. The search considered partitions that pool a transition with a transversion. None was ever chosen, by any criterion, on any corpus. A search limited to partitions of the transitions and transversions separately would give the same answers here, and on a larger alphabet the full space of partitions (the Bell numbers grow faster than exponentially) could not be searched at all.

Still open: a class whose cost is not its members’ mean #

Every partition here gives each class one cost, fitted from the pooled counts of its members. A cost that is not one began this line of argument with a different kind of matrix: costs computed from a rule about the letters, such as purine against pyrimidine or keyboard distance, with a few parameters shared across all pairs. A partition is one such rule — a list of which pairs are the same — and there are others. A matrix could have a transition cost and a transversion cost plus a single extra term for pairs that also differ in some second property of the letters, fitted as one parameter across all the pairs it touches.

The measurement that follows draws a corpus from a generator whose costs are a sum of two such terms, one for class and one for a second property that crosses the classes, so that no partition of the pairs is exactly right. It compares the growing penalty’s best partition with a two-term additive model. The additive model has fewer parameters than the partition that would fit the same costs exactly. The prediction is that on such a generator the best partition needs four or five classes where the additive model needs two terms. It would reach the generator’s alignments with less data, because a shared term pools evidence across pairs no partition would group. That would make partitions the wrong space to search whenever costs come from more than one property of the letters, which is the ordinary case for proteins.