A checker told only what it showed

A spelling checker that answers a misspelling with the vocabulary words nearest to it has to decide how many to show. A second word judged by its own share found the best rule on short words drawn the way people make misspellings, by how often each word is used: show the second nearest word only when its share of everything within two edits is at least 0.15. On misspellings drawn evenly from the vocabulary a plain list of two was better, because prose counts are evidence about the source only when the source was drawn by them — the limit the counts only short words carry found for ranking by counts at all.

The stream a checker can read then let the checker find out which stream it is on. Told which word each reader accepted, it kept a statistic of the accepted words and switched between the two rules by it. The accepted word’s share of the neighbourhood averages 0.68 under use and 0.35 evenly, so a running mean against the midpoint between them held the right rule on every stream after twenty queries. A likelihood ratio needed no midpoint at all: under use the source is one of the nearest words in proportion to its count, under an even stream each is equally likely, and each accepted correction adds the logarithm of the ratio of those two probabilities. A window of the last hundred corrections let both switch within forty to eighty-five queries when the stream changed.

That essay’s closing section named what made it easy. The learners were told every accepted correction, including those for words the list never showed. A real checker sees only what happened to its own list: the reader took the first word, took the second when it was shown, or typed something else. The proposal was to restrict every learner to that, recompute the likelihood ratio over the words shown rather than all the nearest, and see whether the windowed ratio still switches within two hundred queries. It predicted that on the even stream the ratio would settle more slowly, after perhaps a hundred queries rather than fifty, and named the way it could fail outright: if the first word is accepted at nearly the same rate on both streams, the only informative corrections are those for second words, and those are shown mostly where the share rule already expects them.

What a checker is told #

The queries are the earlier essays’: misspellings of three or four letters with an answer within two edits, 704 drawn by use and 287 drawn evenly, resampled into forty seeded streams of a thousand queries each, and into streams that change pools after a thousand. Each query is answered by the share rule or by the list of two, whichever the learner currently holds, and is scored by the earlier essays’ lift over the coin’s line in points of the band.

A learner told everything is told the accepted word for every query whose source is among the nearest words, whatever was shown. A learner told what it showed is told the accepted word only when it was in the list this query’s rule displayed — the first word, or the second when the rule showed two. For the likelihood ratio the computation changes with it: given that the source is among the $k$ words shown, under use it is each shown word in proportion to its count, and under an even stream each with probability $1/k$. A correction from a list of one word therefore adds $\log(c/c) - \log 1 = 0$: whichever stream produced it, a single shown word was certain to be the one accepted.

The two learners measured are the earlier essay’s running mean, with the midpoint fitted on this band, and its windowed likelihood ratio over the last hundred corrections; the regret is the better fixed rule’s cumulative lift minus the learner’s, on the same queries.

Told everything, both learners hold the list of two on every seed from fifty queries of the even stream. Told only what it showed, the running mean never gets there: it holds the right rule on 38% of the seeds at ten queries, 40% at fifty, and 25% after a thousand. The windowed likelihood ratio does get there, slowly — 63% of seeds at fifty queries, 78% at a hundred, 85% at two hundred and 98% at five hundred.

So the prediction about the ratio holds in direction and misses in size. It settles more slowly than when told everything, and a hundred queries is not enough: the proposal’s “perhaps a hundred rather than fifty” is closer to five hundred. The running mean, which the proposal did not single out, fails entirely.

The mean confirms its own choice #

The plate shows the mechanism directly. A checker holding the share rule on the even stream shows a single word on most queries; when the source is that word the reader accepts it, and when the source is the second word the reader types it and the checker is told nothing. So the corrections it is told about are dominated by the first word, which is the common one — the word with the high share. Their mean share is 0.57, above the midpoint of 0.51. Every accepted correction on that stream, the sample the earlier essay’s learner saw, has a mean share of 0.35, well below it.

The running mean reads 0.57 and concludes that the stream is drawn by use, and so keeps the share rule, and so keeps seeing a sample that says use. Its choice decides its evidence and its evidence confirms its choice. Holding the list of two on the same stream, it would be told about second words too, and its sample’s mean falls to 0.49 — under the midpoint, but by little — so a learner that begins on the list of two can stay there, while one that begins on the share rule cannot leave. Every learner here begins on the share rule, which is why three quarters of the seeds end there.

That is the failure the proposal named, arriving in a different statistic. It expected the likelihood ratio to suffer from first words accepted at similar rates; instead the running mean suffers from first words accepted at all, because the mean is a statistic whose expected value depends on which rule produced the sample, and the ratio is not.

Some of the same plate is also the reason the ratio’s evidence is thin. Holding the share rule, 68% of the corrections it is told about on the even stream come from a list of one word and add nothing; on the use stream, 70%.

The use stream, and the evidence that points the wrong way #

On the use stream the running mean’s bias is harmless, because it points the way the stream does: told only what it showed, it holds the share rule on every seed from ten queries on. The likelihood ratio is the learner that struggles here, right on 83% of seeds after a thousand queries, where told everything it was right on all of them from a hundred.

The reason is in the evidence plate’s last column. Held throughout, the list of two collects evidence with the right sign on both streams: 0.057 a query in favour of use on the use stream, 0.165 a query against it on the even stream. The share rule collects almost none either way — −0.012 a query on the use stream and −0.008 on the even one. It is not merely weak; on the use stream it points, faintly, the wrong way.

That follows from when the share rule shows a second word: only when the second word’s share is at least 0.15, which is when the two nearest words’ counts are close. Under use, the source among two close words is the one with the larger count only a little more often than the other, and the model of use — the source in proportion to its count — is not quite right about these particular pairs. The share rule selects exactly the queries on which counts say least, and on those the counts’ small errors outweigh their signal. So a ratio learner holding the share rule on a use stream drifts slowly toward the list of two; once there, it collects strong evidence for use and returns. A sixth of the seeds are caught on the wrong side of that oscillation at any given time.

What the regret comes to #

In lift, the running mean told what it showed is 2.90 points behind the list of two after a thousand queries of the even stream — nearly the whole of what the list of two is worth there — and nothing behind on the use stream. The windowed ratio told what it showed is 0.38 behind on the even stream and 0.36 on the use stream; told everything it was 0.02 and 0.01.

So restricted to its own evidence, the ratio is the learner to use, at a cost: about a third of a point on either stream, against a few hundredths when it was told everything. The mean is the better learner on the stream its bias favours and nearly useless on the other, and a checker cannot know in advance which stream it is on, which was the whole point of learning.

When the stream changes #

The prediction’s central claim was that the windowed ratio still switches within two hundred queries in both directions, and it holds. When a use stream turns even, the windowed ratio told only what it showed switches a median of 57 queries after the change, against 40 told everything; when an even stream turns to use, 111, against 85. Every seed switches in both directions.

The running mean does not switch at all. It is on the share rule at the end of a use stream and never leaves it on the even stream that follows; on an even stream it is mostly on the share rule already, wrongly, and so is “right” from the moment the stream turns to use. In both directions its line is flat.

The four learners side by side make the division plain. Everything that is a mean of shares — the running mean, the mean of the last hundred — loses the ability to leave the share rule once it is told only what it showed. Everything that is a likelihood ratio keeps it, and slows by about a third: 40 to 57 and 85 to 111 for the windowed ratio, and the whole-stream ratio, which told everything took 489 queries to leave a use stream and never left an even one, is quicker in the first direction told only what it showed, 79 queries, and as stuck in the second.

Evidence a choice leaves #

The earlier essay asked whether a checker can learn which of its own statistics to trust from the evidence its own choices leave it, or only from evidence it did not choose. The plates answer that it can, if the statistic is the right kind, and say what the right kind is.

A statistic is safe to compute on self-selected evidence when its expected value under each hypothesis does not depend on the choice that selected the evidence. The likelihood ratio over the words shown is that kind by construction: it asks, of each correction it is told about, how probable that correction was under each stream given what was shown, so the selection is in the conditioning and not in the answer. A list of one word contributes zero rather than a misleading number. The mean of shares is the other kind: what it measures depends on which words were shown, and the rule chooses which words are shown.

The summary that has to forget met a related problem in streams that change, where a statistic accumulated over the whole stream answers about a stream that is no longer there; the windows here are its repair, and they work for the ratio and not for the mean, because a window of biased evidence is still biased. A list as long as the doubt chose a list’s length from the counts alone and never needed feedback; the learners here are what a checker needs once the counts cannot be trusted, and this essay is the price of the feedback being its own.

Where this leaves the checker #

The strand began with a checker that answers every query. A checker that stops at two edits capped the search and kept every useful correction; the triples a typo writes tried to tell a typo from a word the vocabulary lacks; the commonest word at the distance offered one word where the list had three or four and found how much of the list’s value the commonest carried. Each of those decisions was made once, offline, from the whole of a measured stream. The last three essays have been asking whether the decision about how many words to show can instead be made while the checker runs.

The answer the plates give is that it can, from the checker’s own evidence, with a likelihood ratio over the words it showed, for about a third of a point of the better rule’s lift and about a third more time to notice a change. It cannot be made with a running mean of what readers accept, and the reason is general rather than particular to spelling: the mean is a statistic of a sample the checker’s own choice draws, and every rule that shows fewer words draws a sample of commoner words.

What these streams leave out #

Readers who always accept a shown source. A correction is reported whenever the source was shown. A reader who overlooks the right word, or picks a wrong one, adds noise that the ratio would have to absorb and the measurement does not.

One length band. Every query is a misspelling of three or four letters; the midpoint, and therefore the running mean’s failure, is this band’s. The ratio needs no midpoint and should carry to other bands, which was not run.

Resampled pools. Streams are drawn with replacement from 704 and 287 misspellings, as in the earlier essay, so a stream of a thousand queries sees each misspelling more than once.

Two rules. The learners choose between the share rule and the list of two only. A third option that showed two words now and then whatever the rule says — a deliberate exploration — was not measured; the next section is about it.

Still open: a second word shown to find out #

The ratio is slow because its evidence comes almost entirely from lists of two words, and the share rule, which it holds most of the time, shows two words on only a third of queries. The obvious remedy is to show two words sometimes on purpose, not to help the reader but to learn: on a small share of the queries where the share rule would show one word, show the second as well, and count the correction that results in the ratio.

The measurement that follows adds that exploration, at shares of 2%, 5% and 10% of the share rule’s one-word queries, and charges it its lift — a second word shown where the share rule says not to is a slightly worse list on a use stream. The prediction is that at 5% the windowed ratio holds the right rule on nine seeds in ten after a hundred queries of either stream and switches within eighty queries of a change in both directions, for a cost under a tenth of a point on the use stream. It could fail on what the explored queries tell: they are queries where the second word’s share is under 0.15, so under use the source is the second word rarely and the evidence they add may be as thin as the share rule’s own. The question is whether a checker should pay for evidence it would not otherwise collect, or whether evidence chosen for its value to the checker is worth less than evidence that comes for free.