The stream a checker can read

A second word judged by its own share settled which spelling corrections to show on short words — on one stream. A checker that stops at two edits answers a misspelling with the vocabulary words nearest to it, and when there are several the question is how many to show. Showing the second word only when its share of everything within two edits is at least 0.15 lifted the checker 4.5 points above the coin’s line — the straight line a checker reaches by mixing one-word and three-word lists — on misspellings of three or four letters drawn the way people make them, by how often each word is used. Nothing else measured came close: a list as long as the doubt, which sized the list by the ratio of the top two counts, reached 2.5, and a plain list of two 3.1.

On misspellings drawn evenly from the vocabulary the order reversed. The share rule fell to 1.4 points and the list of two kept its 3.1, because the share is computed from prose counts and those 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.

A checker is not told which stream it is on. Its closing section proposed that it could find out. A checker that is told which correction the reader accepted sees, over many queries, whether the accepted words are the common ones the counts favour or a spread with no regard for the counts, and one number summarises it: the mean share the counts gave the accepted words. Keep that mean, switch to the list of two when it falls below a midpoint fitted on a separate stream, and back when it rises. It predicted coming within half a point of the better rule after about two hundred accepted corrections, and switching within another two hundred when the stream changes.

What an accepted correction says #

The vocabulary, the misspellings and the credit are the earlier essays’. A correction is accepted when the source is among the nearest words, so that a reader either picks it from the list or types it, and the checker is told which word it was; that happens on 83% of answered short misspellings drawn by use and 79% drawn evenly. Because the two pools are a few hundred misspellings each — 704 drawn by use, 287 drawn evenly — a stream here is a sequence drawn from one pool with replacement, seeded, and forty seeds are run of each.

On short words the accepted word’s share averages 0.679 under use and 0.350 evenly, with a standard deviation of about 0.34 on each. One accepted correction says little — the two distributions overlap almost entirely — but their means are a third of a share apart, and a mean of $k$ corrections has a deviation of $0.34/\sqrt{k}$. At $k = 16$ that is 0.085, and the midpoint, 0.515, is about two of those deviations from either mean. So the arithmetic says a checker should know its stream after a couple of dozen corrections, an order of magnitude sooner than predicted.

The plate also shows what the proposal’s “midpoint fitted on a separate stream” would do. On words of five or six letters the accepted word’s share is higher on both streams, 0.834 and 0.703, because a longer word’s neighbourhood is sparser and the nearest word holds more of it whatever the stream. Their midpoint is 0.769 — above the short words’ own mean under use. A short-word checker reading that midpoint would see its use stream’s mean, 0.68, and conclude it was on an even stream.

Twenty queries, not two hundred #

With the midpoint of its own band, the running mean holds the share rule on 90% of use streams after five queries and on all of them from twenty on, by which point it has seen about seventeen accepted corrections. On even streams it holds the list of two on 95% after twenty queries and all of them from fifty. That is the arithmetic’s couple of dozen, borne out.

With the midpoint fitted on longer words it is wrong in the way the first plate predicted. On use streams it starts on the share rule — every learner here starts there, having seen nothing — and is moved off it by its first few corrections: it holds the right rule on 45% of streams after five queries, 15% after twenty, and on none from a hundred on. On even streams it is right everywhere, because a midpoint that is too high sends every short stream to the list of two, and that is the right rule there. A checker built this way would look perfect on the stream nobody checks it against.

The third learner needs no midpoint at all. Under use, the source is one of the nearest words in proportion to its count; under an even stream, each nearest word is equally likely. So each accepted correction carries a likelihood ratio between the two streams: its count’s share of the nearest words’ counts, against one over how many nearest words there are. Its logarithm averages +0.28 per correction on the use stream and −0.60 on the even one, and the learner sums them and uses the share rule while the sum is positive. Nothing in it is fitted to a band; a misspelling’s own nearest words supply both hypotheses’ predictions. It is right on 98% of use streams after fifty queries and all even streams after twenty.

The price of learning #

Holding the right rule is not the same as earning what the right rule earns, because the queries before the learner settled were served by whichever rule it held then. The measure that settles it is regret: on each stream, the better fixed rule run on exactly the same queries, minus the learner’s cumulative lift.

On the use stream, the running mean with its own band’s midpoint is 0.20 points behind the share rule after ten queries and 0.03 after a hundred; the likelihood ratio is 0.20 behind after ten and 0.12 after a hundred. On the even stream both are about two points behind after ten queries — every learner starts on the share rule, and on this stream the share rule costs four points a query against the list of two — and inside half a point by fifty: 0.39 for the running mean, 0.45 for the likelihood ratio.

The prediction was half a point after two hundred accepted corrections. It is half a point after about forty, on the slower of the two streams. What the prediction got wrong was not the mechanism but the noise: it budgeted for a statistic hard to separate, and the two streams’ means are a full deviation apart.

The midpoint fitted on longer words has the opposite fate. On the even stream it is the best of the three early on, because it was never going to choose anything but the list of two. On the use stream it stays 1.28 points behind the share rule after a thousand queries and would stay there forever, having learned the wrong thing quickly and with complete confidence.

When the stream changes #

A checker’s stream can change — a new population of users, a new keyboard, a vocabulary that has drifted — and the proposal’s second prediction was a switch within two hundred accepted corrections. The plates run a thousand queries of one stream and then a thousand of the other, in both orders.

The running mean over the whole stream, as proposed, does not switch. After a thousand queries drawn by use it has seen about 830 accepted corrections with a mean near 0.68, and a thousand corrections drawn evenly move it only about halfway to 0.35; on most streams it has not crossed the midpoint when the second thousand ends. The likelihood ratio summed over the whole stream does switch, after a median of 489 queries, because a correction drawn evenly moves it by −0.60 against a correction drawn by use’s +0.28, so the even stream outvotes the history at about twice the rate.

Kept over the last hundred accepted corrections only, both statistics switch quickly: the windowed mean in a median of 67 queries and the windowed likelihood ratio in 40. That is inside the predicted two hundred, but it is a different rule from the one predicted. A statistic that is right on a stationary stream because it remembers everything is wrong on a changing one for the same reason — the problem the summary that has to forget set out for counters, here met by a decision rule.

In the other direction the asymmetry bites harder. The likelihood ratio over the whole stream has accumulated about −470 after the even thousand, and the use stream adds only +0.28 a correction, so it would need about 1,700 accepted corrections to come back — it never switches within the plate. The running mean over the whole stream again does not cross on most streams. The windowed learners switch in a median of 61 queries for the mean and 85 for the likelihood ratio, the latter slower here because each correction drawn by use moves it by less than each drawn evenly.

Where to start before anything is known #

Every learner here starts on the share rule, and the regret plate shows what that costs: on the even stream the first ten queries put every learner about two points behind, and on the use stream almost nothing. The asymmetry is in the two rules’ costs when wrong. On a use stream the list of two earns 3.12 points over the coin’s line against the share rule’s 4.48, so holding the wrong rule costs 1.36 points a query. On an even stream the share rule earns −0.84 against the list of two’s 3.07 — it is worse than the coin there — so holding the wrong rule costs 3.91 points a query, almost three times as much.

A checker that knows nothing should therefore start on the list of two. Its worst case is then 1.36 points a query for the few dozen queries it takes to learn a use stream, against 3.91 a query for the few dozen it takes to learn an even one. On a stream drawn by use the start costs it a little; on a stream drawn evenly the start is already right. That is the choice what insurance against an estimate costs priced for a decision taken on a count that might be wrong: when the two ways of being wrong cost different amounts, the default should be the one whose mistake is cheaper, and here the arithmetic is lopsided enough that no prior belief about which stream is commoner would reverse it unless it put use streams at about three in four.

The same asymmetry explains why the windowed learners switch at different speeds in the two directions. A switch from use to even is a switch away from the rule that costs most when wrong, and each correction drawn evenly moves the likelihood ratio by −0.60 against +0.28 for one drawn by use, so the evidence for leaving arrives faster than the evidence for coming back. A learner tuned for the stream that punishes it most is, by accident of the arithmetic, already tuned to leave it fastest.

A statistic, a midpoint and a memory #

Three separate things were folded into the proposal’s “running mean against a midpoint”, and the plates pull them apart.

The statistic is sound. One number per accepted correction separates the two streams after a couple of dozen corrections, far sooner than the closing section expected; the mean share and the likelihood ratio do it at about the same speed.

The midpoint is the fragile part. The accepted word’s share is not a property of the stream alone but of the stream and the word length together, because the share depends on how crowded the neighbourhood is, and a midpoint carried from one length to another is a midpoint for a different statistic. The likelihood ratio sidesteps it by asking each misspelling’s own neighbourhood what each stream predicts. That is the same move the commonest word at the distance made when it replaced a fixed preference for nearer words with a weight on how much less likely each extra edit is: put the model in the comparison, and the threshold falls out.

The memory decides behaviour under change, and it trades against noise. A window of a hundred corrections switches within a hundred queries; on a stream that does not change it pays for that with occasional wrong turns when a run of atypical corrections fills the window, which the plates’ stationary halves show as dips of a percent or two in the windowed curves. A mean over everything never makes that mistake and never adapts.

What the streams leave out #

Resampled pools. Each stream is drawn from a pool of a few hundred real misspellings with replacement, so a thousand-query stream repeats most of its pool several times. The statistic’s mean and spread are the pool’s; a stream of fresh misspellings would have the same mean and a slightly wider spread.

A told checker. The learners are told the accepted word whenever the source is among the nearest words. A real checker learns only what its reader does with the list — accepting a suggestion, or typing something else — and a typed correction it never showed may not be reported at all. A checker that learns only from shown words would see the second word’s acceptance on the queries where it showed one, which is the share rule’s own selection, and would learn more slowly on the list of two.

One kind of change. The changing streams switch abruptly between two pools. A drift — a population of readers changing slowly — would favour a longer window, and nothing here fits one.

Small differences. On a stationary stream the learners’ long-run lifts are within a few hundredths of a point of the fixed rule’s, smaller than the spread between seeds; a result the size of its own noise is the reason those are reported as regret on identical queries, and not as lifts on separate ones.

Still open: a checker that learns from what it showed #

The learners here are told every accepted correction, including those for words the list never showed. That is the most a checker could be told, and it makes the statistic’s two streams easy to separate. A real checker sees only what happened to its own list: whether the reader took the first word, took the second when it was shown, or typed something else.

The measurement that follows restricts every learner to that: an accepted correction is reported only when the source was among the words shown, and the likelihood ratio is recomputed over the words shown rather than all the nearest. The prediction is that the windowed likelihood ratio still switches within two hundred queries in both directions, but that on the even stream it settles more slowly than here, perhaps after a hundred queries rather than fifty, because the share rule shows one word on two thirds of queries and a one-word list tells the checker nothing about which stream produced its acceptance. It could fail outright on that point: 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. The question is 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.