A second word judged by its own share

A checker that stops at two edits answers a misspelling with the vocabulary words at the least edit distance from it, two edits at most, and the commonest word at the distance asked which of those words to show when there are several. Showing only the one most used in prose kept 77% of the whole list’s corrections on words of three or four letters, when the misspellings were drawn the way people make them, by how often each word is used; the three commonest kept 96%. A list as long as the doubt tried the list between them: the commonest word alone when its count is at least $r$ times the next word’s, and the top three otherwise, so the list grows only where the counts are close.

The counts did know when the commonest word was right — it was the source in 36% of queries where it led by a ratio under two and in 91% where it led by over a hundred — yet the ratio was a poor guide to the list’s length. At its best ratio, ten, the checker lay 2.5 points above the coin’s line, the straight line a checker reaches by flipping a weighted coin between showing one word and showing three, and a plain list of two words sat higher, 3.1 points above the same line. On misspellings drawn evenly from the vocabulary, reading the ratio was worse than not.

That essay’s closing section noticed what the ratio measures. It is the first word’s dominance over the second, and the second word’s value does not follow it: a second word with a tenth of the first’s count is worth showing if nothing else is nearby, and worthless if the neighbourhood holds a dozen words more common than it. Under misspellings drawn by use, the chance that a word is the source is its count over the counts of every word the misspelling could have come from, and the walk that found the nearest words has already found those: every vocabulary word within two edits. The proposal was to show the second word whenever its share of that neighbourhood exceeds a threshold, and the third likewise. It predicted about five points over the coin’s line on short words drawn by use, twice the ratio’s lift, failure on the even stream as the ratio had failed, and named the risk: a two-edit word is less likely than a one-edit word by some factor, and a share computed at the wrong factor would be a ratio in disguise.

The neighbourhood, weighted #

The vocabulary, the streams and the credit are the earlier essays’. Each answered misspelling has its nearest words, ranked by their counts in prose, and a credit for each list length: one if the source is among the words shown, or the expected share of one when a tie at the list’s end is broken at random. Corrections are counted as a share of all the band’s misspellings, answered or not.

The share of a nearest word is its count over the sum of count times $\varepsilon^{d}$ across every vocabulary word within two edits of the misspelling, where $d$ is how many edits further than the nearest that word lies — nought for the nearest words themselves, one for a word one edit further. The weight $\varepsilon$ is how much less likely a typo of one more edit is; the commonest word at the distance found the noisy-channel choice needed it near a hundredth, and 0.1, 0.01 and 0.001 were run. The checker shows the commonest nearest word; the second if its share is at least $\theta$; and the third if the second was shown and its share is at least $\theta$ too. The threshold runs from one, where the list is always one word, to nought, where it is the three commonest.

Nearly twice the ratio #

On short words drawn by use, showing the second word only when its share of everything within two edits is at least 0.15 lifts the checker 4.5 points above the coin’s line between one word and three, at 1.32 words a query — where the ratio rule reached 2.5 and a plain list of two 3.1. One word corrects 63.9% of the band at one word a query and three words 79.7% at 1.98. At a threshold of 0.15 the share rule corrects 73.4% and shows a second word on a third of queries; a coin showing one word or three with the same mean length would correct 68.9%. At 0.1 it corrects 75.5% at 1.46 words, 4.3 points above the line. The best point is 1.8 times the ratio rule’s lift, and it is the first rule the essays have measured that beats the list of two, by 1.4 points, while showing about half as many extra words.

The comparison with the list of two can be made without the coin’s line at all. A list of two corrects 76.5% of the band at 1.59 words a query. The share rule at a threshold of 0.07 corrects 76.7% at 1.54 words: the same corrections for five fewer words in a hundred queries. At 0.1 it gives up one point of the list’s corrections, 75.5%, for thirteen fewer words in a hundred. The ratio rule never reached the list of two’s corrections at fewer words than the list shows, which is the earlier essay’s finding put the other way round: a rule that sizes the list must at least beat the rule that does not, and only the share does.

The prediction was five points and twice the ratio. It is 4.5 and 1.8 times: short of both, by about a tenth, and right about the shape. The plate’s share line also differs from the ratio line in a way the lifts do not show. The ratio rule’s points climb slowly from the one-word checker, because the first words it adds are added where the first word barely leads — and in a neighbourhood of many close words a narrow lead still means the source is often the first. The share rule’s first additions, at thresholds of 0.3 and 0.2, are made where the second word is a fifth or more of everything nearby, and every one of them is a query where it was plausible.

What the second word is worth, by its share #

Drawn by use, a second word whose share of the neighbourhood is under 0.01 is never the source and one over 0.1 is the source in about three queries of ten; drawn evenly, the second word adds more where its share is small than where it is large — 46.2 points a query between 0.03 and 0.1 against 21.8 between 0.1 and 0.2. The stream drawn by use is the stream on which the share means what it says. Below a share of a hundredth the second word is shown on 32 queries and is the source on none of them. Between 0.03 and 0.1 it is the source an eighth of the time, about what its share would predict once the first word’s own share is counted. From 0.1 up it is the source about three times in ten and the gain stops rising, because a second word’s share can reach a third or more only where the first word’s is not much larger, and the source is then split between them.

That flat top is why the threshold settles near 0.1 to 0.15. Lowering it further adds the queries between 0.03 and 0.1, which are worth an eighth of a correction each — less than the coin’s line pays for a word, which is about a sixth, 15.8 points over 0.98 extra words between one word and three. Raising it removes queries worth three tenths each. The share sorts the queries into those where the second word is cheap at the price and those where it is not, and the ratio could not, because two queries with the same ratio of top counts can have second words with shares a hundredfold apart.

The weight hardly matters #

The weight given a two-edit word moves the share rule’s best lift by about a tenth of a point — 4.6 at ε = 0.1, 4.5 at 0.01, 4.4 at 0.001, all at thresholds of 0.1 or 0.15 — so the risk the proposal named, a share computed at the wrong weight, does not arise on short words. The reason is in the neighbourhood itself. A misspelling of three or four letters has its nearest words at one edit almost always, and the words one edit further are at two; with $\varepsilon = 0.1$ they count a tenth, and at 0.001 they count for nothing. What changes between those weights is how much of the neighbourhood’s mass sits outside the nearest words, and the flat lines say that for short words little of it does; that share was not measured on its own.

The noisy-channel choice of the earlier essay was a different decision: which word to put first, comparing a nearer rare word with a farther common one. There the weight decided the answer, since a word a hundred times commoner one edit further wins at ε = 0.1 and only ties at 0.01. Here the first word is chosen by count among the nearest, as before, and the weight only scales the denominator of a share that is compared with a threshold. A factor of a hundred in the weight moves the denominator by a few per cent.

Two streams, two lengths #

The share rule is the best of the three wherever misspellings are drawn by use — 4.6 points over the coin on short words and 2.8 on words of five or six letters — and a plain list of two beats it wherever they are drawn evenly, 3.1 against 1.4. On longer words every lift is smaller because the lists are shorter: a misspelling of a six-letter word usually has one nearest word, and a rule about the second word has fewer queries to act on. The order of the rules holds there, the share rule 0.6 points over the ratio and a point over the list of two.

On the even stream the share is not merely weaker; it points the wrong way. The calibration plate shows the second word adding more where its share is small, and the reason is the stream: drawn evenly, the source is as likely to be a rare word as a common one, so a misspelling whose second-nearest word is rare is as likely to have come from it as from anything, and the counts the share is built from describe prose rather than this stream. The counts only short words carry found the same limit for ranking by counts at all: counts are evidence about the source only on a stream whose sources were drawn by them. The prediction expected the share to fail here as the ratio did, and it does, by the same mechanism.

A share against a ratio #

The ratio and the share use the same counts, and the difference between them is what they divide by. The ratio divides the first word’s count by the second’s, which compares two words with each other. The share divides the second word’s count by everything nearby, which compares it with all its rivals. A second word with a ratio of five against the first is in a neighbourhood of two if the first is its only rival, and has a share of a sixth; in a neighbourhood of a dozen common words it has a share of a fiftieth. The ratio gives both the same treatment, and the share separates them by a factor of eight.

That is the earlier essay’s question answered in its own terms: the reader’s doubt about a list is a property of everything the misspelling could have been, not of the list’s own words. The answer was already in the walk. A trie fitted to its queries and the triples a typo writes both priced the walk that finds the words within two edits, and the walk returns that neighbourhood whether the checker reads it or not; the share costs one sum over words already found, a few dozen additions a query beside the trie cells the walk itself has to visit to find them.

What the measurement does not say #

One vocabulary, one corpus. The counts are one prose corpus’s and the vocabulary its 1,024 commonest words. A larger vocabulary has denser neighbourhoods, where more of the mass sits in words the checker never shows, and the threshold’s best value would fall with it.

A stream drawn by the same counts. The stream drawn by use draws its sources from the same counts the share is computed from, which is the most favourable case possible: the share is then very nearly the source’s probability among the nearest words. Real misspellings are drawn by real use, which the corpus approximates, and the gap between the two is not measured here. A result the size of its own noise is the warning that applies: a lift of 4.5 points over the coin is a few dozen queries out of a few hundred in the band.

Credit, not a reader. A correction is counted when the source is among the words shown. Whether a reader finds the source faster in a list of one, two or three is not measured, and the coin’s line treats each extra word as costing the same.

The third word. The third word is shown only when the second is, and on the same threshold; most of the share rule’s lists are one or two words long, and a separate threshold for the third was not run.

What insurance against an estimate costs priced a decision taken on a count that might be wrong, and the share is a decision of that kind: on the stream drawn by use its count is right, and the decision pays; on the even stream it is wrong, and no threshold rescues it.

Still open: a threshold that reads the stream #

The share rule wins on misspellings drawn by use and loses to a plain list of two on misspellings drawn evenly, and a checker does not know which stream it is on. It can find out. A checker that is told which word the reader chose — or which correction was accepted — sees, over many queries, whether the sources it is told about are spread as the counts predict or spread evenly, and one number summarises it: the mean share the counts gave the accepted words. Under use it is high, and the share rule’s threshold is right; under an even stream it is near what a random word among the nearest would get, and a list of two is right.

The measurement that follows feeds the checker its accepted corrections one at a time, keeps that running mean, and switches between the share rule and a list of two when it crosses a midpoint fitted on a separate stream, then charges both streams and a stream that changes from one to the other halfway. The prediction is that on each pure stream it comes within half a point of the better rule after about two hundred accepted corrections, and that on the changing stream it switches within another two hundred. It could fail on the short band’s size: a few hundred answered misspellings a stream may be too few for a running mean to separate the two before the stream is over. The question is whether a checker can learn which of its own statistics to trust from the corrections it is given, or whether the stream must be known before the counts are worth reading.