A line the corpus finds

A cost built from two properties fitted substitution costs for a four-letter alphabet from a corpus of aligned pairs, where the generator’s costs were a sum of two terms: a penalty for a transversion, and a graded difference between the two letters’ values on a second property. The letters a, c, g and t carried the values 0, 1, 3 and 7, so the six mismatch pairs differed by six different amounts and no partition of them into classes was exactly right. Told which property to use, a model with the two terms and three parameters predicted a fresh corpus better than any partition at every size, and aligned 191 of 200 test pairs optimally from 50 sequence pairs, where the partition a growing penalty chose needed 3,200. Told the wrong property, the same model aligned worse than the plain two-class matrix, and nothing in its own fit said so.

That essay’s closing section proposed the model that does not need telling. Give each letter a position on a line as a free parameter, and let a mismatch cost the transversion term plus the distance between the two letters’ positions. With one position fixed at nought that is three positions, a transversion weight and the identity share: five parameters, between the sum’s three and six free classes. It asked whether the fitted positions recover the generator’s order of the letters and from how many pairs, and where the model’s alignments fall between the sum’s and six free classes’. It predicted about four times the sum’s data to find the order, and that once found the model would behave like the sum with two wasted parameters. It could fail on small corpora, where the rare letters’ pairs are poorly determined and two letters can be put in the wrong order at a small loss of likelihood.

Fitting a line through every order #

A mismatch pair’s weight is $2^{-(\alpha\,\mathrm{tv} + |x_i - x_j|)}$, with the positions $x$ in bits. The absolute value makes the likelihood non-concave in the positions, which is why the proposal suggested alternating between the terms. There is an exact way instead. For a fixed order of the four letters along the line, $|x_i - x_j|$ is the sum of the gaps between consecutive letters from $i$ to $j$, and the model becomes log-linear in $\alpha$ and three gaps that cannot be negative. That is concave, and Newton’s method solves it; a gap that wants to go below nought is held there and the rest refitted. Four letters have twelve orders along a line, an order and its reverse being the same line. Every one is fitted, and the order with the greatest likelihood is the fit.

Every matrix here is a set of costs in bits, the negative logarithm of a pair’s probability against chance, which is the sense a cost that is not one separated from a count of edits. A matrix fitted from a corpus is a statement about that corpus, as the matrix a corpus wrote found when two corpora of the same alphabet wrote different matrices. The rest is the earlier essay’s apparatus unchanged: the same source of data, transversion weight 3 bits and property weight 0.2 bits a unit, so the true positions are a at 0, c at 0.2, g at 0.6 and t at 1.4 bits; corpora of 25 to 3,200 pairs of sixty columns, sixteen seeds a size; half a count added to every pair; excess bits measured on a fresh corpus of 2,000 pairs; and alignments scored on 200 test pairs against the generator’s own costs.

The order is found early #

The fitted line puts the four letters in the generator’s order on every corpus of 100 sequence pairs or more but one, and in every miss at any size a and c are level or the wrong way round. The prediction expected about four times the told model’s data; the told model needs no data to know the order, so the comparison is better put in pairs. From 100 pairs the order is reliably there.

The failure the proposal named happens, and it happens exactly where the generator is hardest to read. The values of a and c are 0 and 1, which at a property weight of 0.2 bits is a fifth of a bit apart, against two fifths between c and g and four fifths between g and t. A corpus of fifty pairs has about three hundred mismatches, split among six pairs, and the difference between a and c changes the expected counts of the pairs involving them by about a tenth. On six seeds in sixteen that tenth is lost in the noise, and the fit puts them level, at a gap of exactly nought, or swaps them. In six of the thirteen misses that is all that is wrong. In the other seven, a and c are placed together and g is carried past them to the far end of the line, a larger error that starts from the same small one: once a and c cannot be told apart, the pairs involving g are explained about as well with g on either side of them. It never confuses g and t.

The line itself #

By 100 pairs the mean fitted line is the generator’s to within a few hundredths of a bit at every letter; at 25 pairs t is in place and c and g are pulled toward a. The pull is the misses of the previous plate: a seed that puts a and c level contributes nought for c, and a seed that swaps them a small negative value once the line is oriented, and the mean carries both. Without them, the 25-pair positions are close to the truth as well.

So the property is recoverable, which is what the proposal hoped. The corpus contains enough to locate four letters on a line from about a hundred aligned pairs, and the line it finds is the generator’s.

Predicting a fresh corpus #

The fitted positions predict a fresh corpus between the told sum and six free classes at every size, 0.29 excess bits a thousand columns at 200 pairs against 0.22 and 0.31, and reach the sum only at 1,600 pairs. The prediction placed them there, and for the right reason: once the order is found, the positions model is the sum with two more parameters, the three gaps free where the sum fixes their ratio. Two extra parameters cost what extra parameters cost.

Measured as data rather than bits, the proposal’s factor is about right for prediction. The told sum loses 0.63 bits a thousand columns at 50 pairs and the positions reach that between 50 and 100; the sum loses 0.14 at 400 and the positions 0.09 at 800. The positions need about twice the sum’s corpus to predict a fresh one as well, inside the four times the proposal allowed, and the factor shrinks as both approach the generator.

What is surprising is how close to six free classes they sit. Six classes have five free mismatch parameters, the positions four, the sum two. In excess bits the positions are almost all the way over at the six-class end at small sizes, 2.01 against 2.30 and 1.12 at 25 pairs. Most of what the told model gains is the ratio between the gaps, which the property fixes and the positions must estimate. The order alone is worth little; the spacing is worth a lot.

Aligning the test pairs #

For alignment the fitted positions are no better than six free classes until 800 pairs, and they match what the told sum does from 50 pairs only at 800: sixteen times the data, not four. At 50 pairs they align 181.9 test pairs of 200 optimally, six free classes 180.6, the told sum 191.3. At 800 the positions reach 195.0 and the sum is at 194.9.

Alignment is more demanding than likelihood here because it depends on the order of the costs, not on the probabilities. An alignment changes when one pair’s cost crosses another’s, and the four transversions’ costs in this generator lie within 1.2 bits of each other, the closest two a fifth of a bit apart. A model that has the order of the letters right but the gaps slightly wrong will rank two pairs the wrong way round, and every test pair whose best alignment depends on that ranking is lost. The told sum fixes the gaps in proportion to the property and has only their scale to learn. The positions model must learn each gap, and the small one, between a and c, is the last to settle.

The ties a rounded matrix makes measured this sensitivity directly: an alignment’s distance from a tie, the smallest change to one cost that makes another alignment win, predicted which alignments a refitted matrix would move, and a third of the test alignments sat close to a tie. The positions model’s errors in the gaps are small changes to costs, and they land on exactly those alignments. The grain a corpus chooses for itself found the same fragility from the other side: the two fitted costs that land closest set how fine a matrix’s rounding must be, and here the two closest are the costs of ac and cg, a fifth of a bit apart, a difference set by the a–c gap against the c–g gap, the two the positions model learns last.

This is the real price of not being told, and it is larger than the proposal’s arithmetic of parameters suggested. Two more parameters cost little in excess bits; for the decisions an aligner makes, they cost a sixteenfold larger corpus.

When there is no property #

On a generator with no graded property, the fitted positions lose to the chosen two-class partition at every size, 0.31 excess bits a thousand columns at 200 pairs against 0.14, and to the sum, which can set its property’s weight to nought, 0.19. The positions model always fits a line, and on these data the line is noise.

The told sum’s advantage here is that its one property term can switch off. With the wrong property it would also fit a small weight, but a single weight is one parameter of noise; the positions model fits three gaps of noise. The partition chosen by a growing penalty, which the classes held-out pairs cannot rule out found recovers a generator’s classes, recovers the two classes here and pays for nothing else.

The cost of the invented line is largest where corpora are small, which is where a model that does not need telling would be most wanted. At 25 pairs the positions lose 2.81 bits a thousand columns against the partition’s 1.24, more than twice as much; by 800 pairs the gap is five hundredths of a bit and by 3,200 two. A designer who does not know whether the letters have a graded property gains, by fitting a line, a large advantage when they do and pays a large penalty when they do not, both at the small sizes where the choice matters, and the fit itself gives no sign of which case it is in.

A line is always found #

With no property to find, the fitted line is 1.41 bits long at 25 pairs, as long as the real property’s, and still 0.40 bits at 200 pairs; it shrinks only as fast as the data rule it out. On 25 pairs a line that does not exist is indistinguishable by its length from one that does. On 200 pairs it is a quarter of the length, which is distinguishable only by comparing with a line one already knows.

One case needs saying because it is not noise but a confound. If the fitted order puts a beside g and c beside t, the purines and the pyrimidines, then the gap between the two pairs is crossed by exactly the transversions, and the line can carry the transversion term itself. The likelihood is then flat along a ridge where length and the transversion weight trade. On the generator with no property, two to five seeds in sixteen land in such an order at the largest sizes, which is why the plate uses the median. On the generator with a property, none ever does; its true order, a c g t, keeps the purines apart.

What the counts depend on #

A generator with one line in it. The costs are exactly a transversion term plus distances on one line. A real alphabet’s costs need not lie on any line, and a model of positions on a line would then be a different kind of wrong, one this source of data cannot show.

A line, not a metric. Costs from distances on a line obey the triangle inequality among the mismatches, which arbitrary fitted costs need not; a distance that is not a distance counted how often a fitted matrix breaks it and what that does to structures that prune by distance. The positions model cannot break it, which is a property of the model, not of the data, and on an alphabet whose real costs break it the model would be forced to misfit.

Every order fitted. Four letters have twelve orders, and fitting all of them is exact and cheap. Twenty letters have over a hundred quadrillion, and a fit would have to search; the search’s failures would add to the misses measured here.

Sixteen seeds for likelihood, eight for alignment. The excess bits are means of sixteen corpora, the alignment counts of eight, each on one fixed test set.

Gap costs held fixed. Every alignment uses the same gap cost, three bits a gap position, so only the substitution costs differ between models. The parameter plane has few answers found that the optimal alignment changes at only a few places as gap costs vary, so a different fixed gap cost would move the counts but probably not their order.

Still open: a line with a prior toward the classes #

The positions model learned the order quickly and the spacing slowly, and on a generator with no property it invented a line. Both failures are the same fact seen twice: the gaps are free, and nothing pulls them toward any value before the data does. A model could start from what the two-class partition already knows and let the line grow only when the data insist. Put a penalty on the line’s length, a cost in bits for every bit of distance, and fit the positions under it; at a large penalty the line collapses and the model is the transversion-only matrix, at nought it is the free line measured here.

The measurement that follows sets the penalty by a growing rule, as the partition’s penalty grows with the corpus, fits both generators at every size, and scores excess bits and alignments. The prediction is that on the generator with no property the penalised line collapses to nearly nought from 50 pairs and matches the chosen partition, and that on the generator with a property it costs the positions model a little at small sizes and nothing from 400 pairs on, so that it aligns as well as the free line everywhere and better than the partition from 200 pairs. It could fail at the small gap: a penalty strong enough to collapse a line of noise will also collapse the fifth of a bit between a and c, and then the model has the order wrong exactly where the free line had it right. The question is 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.