The dial that has no setting

A model with one parameter, fitted to one collection, using two measurements. If the model were right there would be a setting where both agree.

The fit #

The generator makes k copies of a base text and replaces a fraction of each copy’s characters. Sweep that fraction from zero to sixty-four per cent and measure two things at each setting: runs of the transform per character, and phrases of the parse per character.

The real version history sits at 0.126 runs a character and 0.0668 phrases a character.

The run count asks for 2.32%. The phrase count asks for 3.24%. A factor of 1.40 apart, and neither setting reproduces the other measure.

That is a small discrepancy by the standards of model fitting and it is not nothing: at 2.32% the generated collection has 0.126 runs a character and 0.052 phrases, which is 22% short on the second; at 3.24% it has 0.153 runs, which is 21% over on the first.

The two settings are close enough that a reader might reasonably ask whether the difference is noise. It is not: both curves are monotone and smooth over the sweep, both are computed exactly rather than sampled, and the same measurement at nearly three times the corpus size gives the same two settings to within a few hundredths of a per cent. The disagreement is a property of the model.

Why two measures rather than one #

A one-parameter model fitted with one measurement always fits. That is not a property of the model; it is arithmetic. Any monotone curve crosses any horizontal line somewhere, and the crossing is the setting.

So a fit is only a test when there are more measurements than parameters, and this collection happens to have exactly the right two. The collection decides which index is small is the essay about them: runs of the Burrows-Wheeler transform and phrases of the Lempel-Ziv parse are both measures of repetition, they are not the same measure, and a text can be small on one and large on the other.

Two measures, one dial, and a 40% disagreement is what a one-parameter model looks like when it is asked to do two things. A limit is not a prediction is the general form of the same caution.

Why these two measures disagree at all #

It is worth understanding what the two are sensitive to, because the direction of the disagreement is informative.

The run count of a transform counts contexts that repeat. A scattered substitution breaks a context wherever it lands, so scattering k substitutions breaks about k contexts — the damage is proportional to the number of edits and nearly independent of where they are.

The phrase count of a parse counts places where copying has to restart. A scattered substitution forces a restart at each edit; a block of substitutions forces one restart for the whole block. So the damage is proportional to the number of edit sites, not to the number of edited characters.

The real collection has 20% of positions differing in blocks of 7.3, which is about 2.8% of positions as sites. The generated one at 2% has 2% of positions differing in blocks of 1, which is 2% as sites.

The two measures disagree because one counts characters and the other counts blocks, and the model has no blocks.

Where the model is wrong #

The disagreement says the model is wrong; it does not say how. The measurement that says how is about where the edits are rather than how many there are.

Take consecutive documents and compare them position by position over their common length. Count the positions that differ, and count the maximal runs of differing positions. A scattered substitution is a run of one, by definition; a rewritten paragraph is one long run.

The generated collection’s edits are runs of 1.04 characters, which is what “replace a fraction of the characters at random” means. Real edits are runs of 7.31.

The five pairs that changed nothing #

The table’s averages hide the shape, and the shape is the finding.

Of the nine consecutive pairs in the version history, five differ in nothing at all over their common prefix. The file simply grew — a few hundred characters appended — and everything that was there before is byte for byte identical.

The other four differ in 9%, 32%, 61% and 80% of their positions.

So a real version history is not “a few per cent changed each time”. It is nothing changed, nothing changed, a rewrite, nothing changed, nothing changed, a rewrite — and the generator has no setting that produces either half of that, because it changes exactly the same small fraction every time.

The dial is the wrong shape, not the wrong value. That is why no setting works, and it is the answer this essay is for.

The 80% that is an insertion #

One of those four numbers deserves unpicking, because it is an artefact of the comparison rather than of the data — and the artefact is itself the point.

A positional comparison can only see substitutions. Insert a paragraph into the middle of a file and every character after it is at a different offset, so a position-by-position comparison reports the whole tail as changed. That is what 80% is.

The generator only substitutes, so a positional comparison is exactly right for it and hopelessly wrong for the real thing. The measurement that says the model is wrong is a measurement the model’s own assumptions make.

That is worth stating plainly because it cuts both ways: the 20.3% in the table above is an over-count of how much real text changed, and the 7.31 characters a block is an under-count of how localised real edits are. Both errors run in the direction that makes the model look better.

The same failure, in a field that has met it #

This is not the first time in this collection that a one-parameter model has been asked to stand in for something with structure.

Sized for a rate that does not hold still records a summary sized for a stream whose arrival rate was assumed constant and was not. The formula everybody sizes filters with records a sizing formula whose assumption about independence is not met by the hash families anybody uses. And the boundary that hides the burst records a window model that reports a periodic stream as an even one.

In every case the model is a good instrument and a bad sample, and in every case the failure appears only when somebody measures the thing the model was standing in for. That is what this strand is: the measurement, taken late, on the one input every structure here has been fed.

What the model gets right #

It is worth being fair, because the disagreement is 40% and not a factor of ten.

The generated collection at 2% lands within 12% of the real version history on runs per character. On phrases it is 22% low. Those are the right order of magnitude, and no other setting of any parameter in this collection would have got that close by accident.

More importantly, it lands in the right regime. The version history is the repetitive case and the generator at a few per cent produces the repetitive case; the two agree that a compressed index on such a collection is several times smaller than the text, and they agree by how much to within a quarter.

Every structural conclusion in five strands is about that regime, and none of them turns on a quarter.

The measurement that is cheap and was not taken #

The edit-shape measurement is one pass over each pair of documents, comparing positions and counting runs. It costs nothing, it needs no structure, and it would have said the model was the wrong shape without any of the fitting above.

That is the third time in these five strands that a cheap measurement would have settled a question that was instead settled by building something. A break-even calculation would have said a run coder loses on a grid; a depth histogram would have said which caps are live; and a run-length comparison of two documents would have said that a substitution model does not describe an edit.

The pattern is worth naming: when a claim is about the shape of some data, measure the shape. It is nearly always one pass, and it nearly always answers the question the expensive apparatus was going to answer approximately.

What a model with two parameters would need #

The obvious repair is to give the generator an edit length as well as an edit rate: replace runs of L characters at a rate chosen so the total fraction matches. That is two parameters and it would fit both measures, because two parameters fitted with two measurements always fit.

Which is the problem. A two-parameter model fitted with two measurements is not tested by the fit, and the honest way to test it would be a third measure — the entropy at some order, or the depth profile of the parse, or the distribution of match lengths.

The value of the disagreement here is that it exists, and it exists because the model has fewer parameters than there are measurements. A better-fitting model would be less informative unless it were tested harder.

That is the general shape of the model has parameters, and it is the reason this essay does not end by proposing a better generator.

Free parameters, not parameters #

The argument against a two-parameter generator is that two parameters fitted with two measurements always fit, so the fit tests nothing. That is true and it is not an argument against the model — it is an argument against fitting it, and the distinction is worth separating because this essay has already produced the thing that removes the objection.

A fit tests a model when there are more measurements than free parameters. A parameter measured directly is not free. And the edit-shape measurement above measures one of the two: real edits arrive in blocks averaging 7.31 characters, which is exactly the length parameter a two-parameter generator would want, obtained in one pass over consecutive documents with no structure and no fitting.

So the honest version of the repair is not add a parameter and fit both. It is set the block length from the measurement and fit only the rate — one free parameter, two measurements, and the run count and the phrase count are still free to disagree. If they then agree, the model has passed a test it could have failed; if they disagree, the disagreement is again informative, and it is informative about something other than the edits being scattered, since the edits are no longer scattered.

That is a better use of the same two measures than either the current model or the fitted two-parameter one, and it costs a pass that has already been written.

It also states what would have to be measured for a third parameter, and so on: each new parameter needs its own direct measurement, not another curve to cross. A generator with an edit rate, a block length and an insertion rate is testable exactly as long as at least one of the two repetition measures is left over, and it stops being testable the moment the parameters are fitted rather than observed.

Which is fitting a class to measurements’s discipline arriving in a place it has not been applied here. There, a class is granted only if the measurements support it and the alternatives do not; the machinery’s whole value is that it can refuse. A model fitted with as many parameters as measurements cannot refuse, so it is decoration — and the fix is not fewer parameters, it is fewer free ones.

One caution belongs with the proposal, and this essay supplies it. The 7.31 comes from a positional comparison, and a positional comparison cannot see an insertion — so it over-reports how much changed and under-reports how localised the changes are. A block length taken from it is therefore biased in the direction that flatters a substitution model, which is exactly the wrong direction for a parameter that is supposed to test one. Getting an honest block length needs an alignment rather than a comparison, which is a real cost and is the reason the shortcut is not free.

So the sequence is: align, measure the block length, fix it, fit the rate, and read the disagreement between the two repetition measures as a result rather than as a residual. None of that is proposed as a better generator — a limit is not a prediction applies to models as much as to classes — but it is the arrangement under which a better generator could be shown to be one.

What the measures do not see #

One more thing worth recording, because it is a null result and it constrains what a better model would need.

Shuffle the version history’s documents into an order they were never in. Every document is kept, every character, every symbol. The run count moves by 0.06% and the phrase count by 0.4%.

So neither measure sees the order at all. A generator that produced the right documents in the wrong order would be indistinguishable, on these two measures, from one that got the order right — and a two-parameter model of edits is therefore not being asked to model a history at all. It is being asked to model a set of similar documents.

What a model is for #

It is worth being clear about the claim, because “the model is wrong” is too strong and “the model is fine” is too weak.

A generator in this collection has one job: to produce a collection with a stated, reproducible degree of repetition, so that a structure’s behaviour can be measured as a function of it. For that job the shape of the edits is irrelevant — what matters is that turning the dial moves the measures monotonically and that the same setting always gives the same collection.

It does both. Everything measured against it in five strands is measured against a controlled input, which is what a controlled input is for.

What it cannot do is stand in for a real collection when the question is what a real collection is like. The document strand asked exactly that question — how many documents, what alphabet, how uneven — and answered it from a generator, which is where documents that are not the same length finds something that does not survive.

A model is an instrument, not a sample. The failure is not in the generator; it is in the sentences that treated its output as data.

What this does to the five strands #

Nothing, directly, and that is worth saying before the essay that says it carefully.

Every conclusion in the repetition, index, phrase-index, grid and cap strands — from an index with z in its size onwards — is a statement about a structure’s behaviour as a function of a collection’s measures — how an index’s size follows the run count, how a query’s cost follows the phrase count. Those are relationships, and a collection that sits at a slightly different point of the same relationship does not disturb them.

What the disagreement does disturb is any conclusion of the form this is what a repetitive collection is like. There are a few of those, and what the generated collection was right about sorts them out.

What a reader with their own collection should do #

The transferable part of this essay is not the two settings. It is the procedure.

Measure two things, not one. A model with one parameter fitted with one measurement always fits, and the fit therefore says nothing. Runs of a transform and phrases of a parse are both one pass over the text and they are sensitive to different structure.

Measure the shape of the differences. Positions differing and characters per differing block, over consecutive documents. One pass, no structure, and it says immediately whether the collection’s changes are scattered or localised — which decides which of the two measures a model will get wrong.

And check the direction of every artefact. A positional comparison cannot see an insertion, so it over-reports change and under-reports localisation, and both errors flatter a substitution model. Knowing which way an instrument is wrong is most of what makes it usable.

None of that needs the generator, and all of it is available before deciding whether a compressed structure is worth building.

What is checked #

The sweep reaches the real values on both measures, which is what makes “the setting each asks for” a crossing rather than a nearest point. A sweep that never reached them would give two arbitrary numbers.

The two settings differ by more than a quarter — asserted, so that a change to the generator that made them agree would fail here rather than quietly removing this essay’s subject.

Real edits arrive in blocks more than three times longer than generated ones, which is the measurement that explains the disagreement rather than merely reporting it.

And two things must fail. A corpus cut to one length — the ordinary preparation step — loses 55.8% of the collection and moves both measures. A corpus with its characters shuffled multiplies the run count by 7.42 with its zero-order entropy unchanged, which is what makes both measures measures of repetition rather than of symbol frequencies.