When the algorithm is a table

A second word shown to find out

A spelling checker that learns which stream it is on from the corrections among the words it showed learns slowly, because the share rule it holds most of the time shows two words only when the two counts are close, and those lists say nothing. Showing the second word sometimes on purpose was proposed as the fix, with the risk that the explored queries — where the second word's share is small — would say little too. The risk is inverted: an explored query separates the two streams by 0.82 nats, more than twice what a list of two on any query does, because a small share is exactly where the counts disagree most. But such queries are rare, and the gain is modest: on the even stream exploring 5% of the share rule's one-word queries lifts the seeds holding the better rule after a hundred queries from 78% to 85%, not the nine in ten predicted; on the use stream the share rule's own lists push the checker the wrong way, and exploring overcomes the push only from about 18%.

A spelling checker answers a misspelling with the vocabulary words nearest to it — within two edits, the bound a checker that stops at two edits set — and has to decide how many to show. The commonest word at the distance offered one, and a list as long as the doubt let the list’s length follow how close the counts were. A second word judged by its own share found that on short words misspelt the way people misspell — in proportion to how often each word is used — the best rule shows 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 is better. The stream a checker can read let the checker learn which stream it is on from the corrections its readers accept, and a likelihood ratio over those corrections did it in a few dozen queries.

A checker told only what it showed took away the information a real checker does not have. Told only which of its shown words the reader took, or that the reader typed something else, the ratio’s evidence came almost entirely from lists of two — a list of one word says nothing about which stream drew the misspelling — and on the even stream the windowed ratio held the better rule on 78% of seeds after a hundred queries and 98% after five hundred. On the use stream it was pulled the wrong way, a little, by the share rule’s own evidence.

That essay’s closing section named the obvious remedy. Show the second word sometimes on purpose — not because the share rule wants it shown, but to learn — on a small share of the queries where the share rule would show one word, and count what results. The predictions: at 5%, the windowed ratio holds the better rule on nine seeds in ten after a hundred queries of either stream; it switches within eighty queries of a change in both directions; and the exploration costs under a tenth of a point of lift on the use stream, where the extra word makes a slightly worse list. The risk: the queries explored are those where the second word’s share is under 0.15, and under use the second word is then rarely the source, so the evidence they add may be as thin as the share rule’s own.

A word shown that the rule would not show

Everything is the earlier essays’. The answered misspellings of three or four letters, 704 drawn by use and 287 evenly; streams of queries drawn with replacement from one pool, forty seeds; the share rule at 0.15 against the list of two; the windowed likelihood ratio over the last hundred reported corrections; lift measured in points of the band against the coin’s line between one word and three, so that the fixed rules reproduce the earlier essays’ numbers. A correction is reported only when the source was among the words shown, and its evidence is formed over those words: under use the source is a shown word in proportion to its count, evenly each shown word is equally likely.

Exploring adds one decision. When the checker holds the share rule and the share rule would show one word of several, with probability ee it shows the first two instead, earns the list of two’s lift on that query, and counts the correction over two words. The draws for exploring come from a generator of their own, so every setting of ee sees the same stream of queries on each seed, and e=0e = 0 reproduces the earlier essay’s checker exactly. Of the use pool’s 704 queries, 216 are ones the share rule answers with one word of several; on the even pool, 75 of 287.

The hero plate is the even stream, where the earlier checker was slow. After a hundred queries it holds the better rule — the list of two — on 78% of seeds with no exploring, 85% exploring 5% and 93% exploring 20%. Nine in ten, predicted at 5%, takes about 10%. After five hundred queries every setting is at 98% or more.

The queries that say the most

The risk is inverted: a query explored where the share rule would show one word separates the two streams by 0.82 nats on average, the most informative list the checker ever shows, against 0.36 for a list of two on any query and -0.02 for the share rule's own two-word lists — which say nothing, because the share rule shows a second word only when the two counts are closeThe mean log-likelihood ratio (use against even) a query contributes, reported or not, on each stream, for three kinds of list: the share rule's two-word lists (199 use and 103 even queries), a list of two on every query with two candidates (415 and 178), and the queries exploration shows two words on — the share rule's one-word queries with a second candidate (216 and 75). share rule's own two-word lists: use -0.044, even -0.023, separation -0.021; a list of two, any query: use 0.097, even -0.266, separation 0.362; explored: a second word where the share rule shows one: use 0.229, even -0.594, separation 0.822.0drawn by usedrawn evenlyshare rule's own two-word lists-0.044-0.023a list of two, any query0.097-0.266explored0.229-0.594nats a query, use against evenby kind of list
Fig. 1 The mean log-likelihood ratio, use against even, that one query contributes on each stream, for the share rule’s own two-word lists, for a list of two on any query, and for the queries exploring would show two words on. Separation between the streams: −0.02, 0.36 and 0.82 nats.

The risk is inverted: a query explored where the share rule would show one word separates the two streams by 0.82 nats on average, the most informative list the checker ever shows, against 0.36 for a list of two on any query and −0.02 for the share rule’s own two-word lists, which say nothing. The proposal reasoned that a second word with a small share is rarely the source under use, so a list that adds it would rarely be answered with it. That is true, and it is the reason the query is informative. Under use the reader takes the first word nearly every time; evenly, the reader takes the second word about as often as the first; so whether the reader took the first word is a strong signal exactly where the counts disagree most.

The share rule’s own two-word lists are the opposite case, and the plate shows why the earlier checker learned so slowly. The share rule shows a second word only when its share is at least 0.15, which is when the two counts are close, and when the two counts are close the two streams predict nearly the same reader: under use the second word is taken in proportion to a count not much smaller than the first’s, evenly half the time. The evidence those lists carry is about nothing, −0.044 nats a query under use and −0.023 evenly, slightly the wrong way on both.

So the checker’s slowness was never a shortage of corrections. It was that the rule it held chose, for its own reasons, to show two words exactly where two words tell least. A list chosen for what it would teach shows two words where they tell most.

Why the use stream does not move

On the stream drawn by use, exploring hardly moves the checker: after a hundred queries it holds the better rule on 80% of seeds with no exploring, 85% exploring 5% and 83% exploring 20%, and after a thousand on 83%, 88% and 85% — under nine in ten at every point drawnMisspellings of three or four letters drawn by use, 40 seeds: the share of seeds on which the windowed likelihood-ratio checker, told only corrections among the words it showed, holds the better of the share rule and the list of two, at each number of queries, exploring a second word on none, 5% or 20% of the share rule's one-word queries. no exploring: 5 80%, 10 68%, 20 73%, 50 75%, 100 80%, 200 75%, 500 65%, 1000 83%; exploring 5%: 5 78%, 10 68%, 20 73%, 50 70%, 100 85%, 200 83%, 500 73%, 1000 88%; exploring 20%: 5 73%, 10 65%, 20 70%, 50 68%, 100 83%, 200 85%, 500 75%, 1000 85%.00.2500.5000.7501queries (log scale)share of seeds holding the better rule51020501002005001,000nine in tenexploring 5%exploring 20%no exploringdrawn by use, 40 seedswindowed ratio
Fig. 2 The share of seeds holding the better rule — the share rule — on the stream drawn by use, at each number of queries, exploring none, 5% or 20% of the share rule’s one-word queries. After a hundred queries: 80%, 85% and 83%. After a thousand: 83%, 88% and 85%.

On the stream drawn by use, exploring hardly moves the checker: after a hundred queries it holds the better rule on 80% of seeds with no exploring, 85% exploring 5% and 83% exploring 20%, and after a thousand on 83%, 88% and 85% — under nine in ten at every point drawn. The other half of the first prediction fails, and for a different reason from the even stream’s. Under use the checker wants to hold the share rule; while it does, its own two-word lists push its ratio slightly toward the even stream, and every so often the window tips and it switches to the list of two, where the evidence pulls it back. The curve does not climb because the checker keeps leaving the right rule and returning to it.

Exploring adds evidence in the right direction, but only on explored queries, and those are rare: 5% of the share rule’s one-word queries of several is 1.5% of all queries on the use stream. Each carries 0.23 nats toward use on average, so at 5% exploring adds 0.0035 nats a query, against the share rule’s own pull of 0.012 the other way. The next plate makes that arithmetic the whole picture.

The use stream at a thousand queries shows a small bump at 5%, 88% against 83% and 85% either side. With forty seeds the share of seeds right moves in steps of two and a half points, and the plate’s variation at the use stream is within a few such steps; it is not evidence of a best exploring rate.

A pull and a push

Why the use stream does not move: holding the share rule, the checker's own lists push its ratio 0.012 nats a query the wrong way, and exploring adds 0.070 nats a query for every unit of the share explored — so the evidence turns the right way only from about 18% explored, where 5% of all queries show a word the share rule would notOn the use stream, the mean log-likelihood ratio a query contributes while the share rule is held: from the share rule's own lists -0.012; from exploration, the share explored × the share of queries the share rule answers with one word of several (0.307) × an explored query's mean (0.229). Net, at each share explored: 0%: -0.012, 2%: -0.011, 5%: -0.009, 10%: -0.005, 20%: 0.002.0nats a query toward the right rule, while the share rule is heldno exploring-0.012exploring 2%-0.011exploring 5%-0.009exploring 10%-0.005exploring 20%0.002drawn by usenet evidence a query
Fig. 3 On the use stream, while the share rule is held, the net log-likelihood ratio a query contributes toward the better rule: the share rule’s own lists’ pull of −0.012 nats, plus exploring’s push of 0.070 nats a query for each unit of the share explored. Net turns positive from about 18% explored.

Holding the share rule on the use stream, the checker’s own lists push its ratio 0.012 nats a query the wrong way, and exploring adds 0.070 nats a query for every unit of the share explored — so the evidence turns the right way only from about 18% explored, where 5% of all queries show a word the share rule would not. The plate is the measurement’s account of the use stream in one line. Below 18% exploring slows the drift toward the wrong rule without reversing it; above it the checker would, in the long run, stay on the share rule. At 20% the net is barely positive, 0.002 nats a query, and the window of a hundred corrections still tips often.

What sets the 18% is the share rule’s pull, and that pull is a fact about the share rule, not about exploring. The share rule’s two-word lists are on average very slightly more consistent with an even stream than with use, because the share rule shows them when the counts are nearly equal, and an even reader takes the second word of a nearly equal pair as often as a reader by use. A ratio that simply ignored those lists would have no pull to overcome. That is the change the measurement points to, and it costs nothing to show.

On the even stream the arithmetic is kinder. There the checker should hold the list of two, which shows two words on every query and carries 0.165 nats a query toward the even stream on its own; exploring only matters while the checker is wrongly holding the share rule, and every explored query then pushes it the right way by 0.59 nats.

What exploring costs

What exploring costs over a thousand queries: on the use stream the lift lost to the better fixed rule rises from 0.363 points with no exploring to 0.419 at 5% — 0.056 points, inside the predicted tenth — and 0.542 at 20%; on the even stream it falls from 0.385 to 0.104, because there exploring shows the list the stream wantsRegret after a thousand queries — the better fixed rule's cumulative lift minus the checker's, a query, in points of the band — on each stream at each share explored, 40 seeds: drawn by use: 0% 0.363, 2% 0.374, 5% 0.419, 10% 0.435, 20% 0.542; drawn evenly: 0% 0.385, 2% 0.337, 5% 0.233, 10% 0.185, 20% 0.104.00.2000.4000.600share of the share rule's one-word queries exploredlift lost to the better rule, points0%2%5%10%20%drawn by usedrawn evenlya thousand queries, 40 seedspoints
Fig. 4 The lift lost to the better fixed rule over a thousand queries, in points of the band, on each stream at each share explored. Drawn by use: 0.363 with no exploring, 0.419 at 5%, 0.542 at 20%. Drawn evenly: 0.385 falling to 0.104.

Over a thousand queries, on the use stream the lift lost to the better fixed rule rises from 0.363 points with no exploring to 0.419 at 5% — 0.056 points, inside the predicted tenth — and 0.542 at 20%; on the even stream it falls from 0.385 to 0.104, because there exploring shows the list the stream wants. The third prediction holds. Under use an explored query shows a list of two where the share rule shows one word, and on that query the list of two earns less lift — the share rule was right to stop at one word — so each explored query costs a little; at 5% there are fifteen of them in a thousand queries.

On the even stream the same mechanism runs the other way. A checker wrongly holding the share rule there shows one word where the stream wants two; an explored query shows the two, earning the lift the checker should have had, and pushes it toward the right rule as well. Exploring is a pure gain on the stream where the checker most needs to learn, and a small loss on the stream where it already holds the right rule most of the time.

Taken over both streams equally, exploring pays: at 5% the two streams’ regrets sum to 0.652 points against 0.748 with none, and at 20% to 0.646. The checker cannot know which stream it is on — that is the point of learning — so the sum is the fair account, and on it exploring is worth about a tenth of a point at any setting from 5% to 20%.

What exploring does not touch

Exploring does not speed the switch: a median of 57, 63, 46, 54, 42 queries after use turns even, and 111, 110, 109, 110, 108 after even turns to use, at 0% to 20% explored — the second direction never moves, since a checker holding the list of two already shows two words and has nothing to exploreMedian queries after a change, over 40 seeds, until the windowed ratio holds the new better rule for fifty queries running, from use to even and from even to use, at each share explored: 0%: 57 and 111; 2%: 63 and 110; 5%: 46 and 109; 10%: 54 and 110; 20%: 42 and 108.use turns eveneven turns to use8080no exploring57111exploring 2%63110exploring 5%46109exploring 10%54110exploring 20%4210840 seeds, a thousand queries each waymedian queries to switch
Fig. 5 Median queries after a change, over forty seeds, until the checker holds the new better rule for fifty queries running, at each share explored. Use turning even: 57, 63, 46, 54 and 42. Even turning to use: 111, 110, 109, 110 and 108.

Exploring does not speed the switch: a median of 42 to 63 queries after use turns even, with no trend across the shares explored, and 108 to 111 after even turns to use — the second direction never moves, since a checker holding the list of two already shows two words and has nothing to explore. The second prediction fails in one direction by design. Exploring acts only while the share rule is held. After a change from even to use, the checker is holding the list of two, which it learned on the even stream; it now needs evidence that the stream has turned, and the list of two supplies it at its usual rate, 0.057 nats a query toward use. The window of a hundred corrections then has to fill with the new stream’s evidence before the sum turns, which is about a hundred queries whatever the share explored.

From use to even the switch is already within eighty queries at every setting, and exploring makes no consistent difference. There the checker is holding the share rule when the stream changes, explored queries push it toward the even stream at 0.59 nats each, and the share rule’s own lists push it the same way very slightly; but the window’s memory of the use stream is what the switch must outlast, and that does not depend on exploring.

Both delays are set by the window. A window of a hundred reported corrections forgets at a fixed pace, and any change in the evidence’s rate moves the delay only a little. The measurement leaves the window where the earlier essays put it.

Evidence chosen for its value

The question the proposal ended on was 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 free. On these streams it is worth more — more than twice as much a query as the evidence a list of two supplies anyway, and forty times as much as the share rule’s own two-word lists. The difficulty is not its quality but its quantity: the queries where it can be collected are a third of the use stream and a quarter of the even, and exploring a small share of them collects a little.

The essays before this one had treated evidence as a by-product of choosing lists for the reader. The plates here say the two purposes choose different lists. A list chosen for the reader shows a second word when the second word might be wanted, which is when the counts are close — the rule a second word judged by its own share arrived at; a list chosen to learn shows a second word when the counts are far apart, because that is when the reader’s choice discriminates. The counts only short words carry found that prose counts are evidence about a source only under use; this measurement finds that, under the share rule, the checker had been asking its readers mostly the questions whose answers the counts could not distinguish.

What the measurement leaves out

Two streams and two rules. A real stream is a mixture, and a checker with more than two rules would learn a different question.

A reader who takes the source whenever it is shown. The model’s reader never takes a wrong word; a reader who sometimes takes the first word out of habit would weaken exactly the evidence explored queries carry.

One window. A hundred reported corrections, as in the earlier essays; a shorter window would switch sooner and settle worse, and was not measured here.

Still open: a ratio that ignores the lists it chose

The plates point at a change that costs nothing to show: the share rule’s two-word lists carry no evidence about the stream and a slight bias against use, and the checker counts them anyway. A ratio that counted only the lists that discriminate — explored queries, and lists of two shown on every query by the list-of-two rule — and ignored the share rule’s own two-word lists would lose the pull that holds the use stream back, while losing almost no evidence, since those lists averaged −0.02 nats between the streams.

The measurement that follows runs that ratio, with and without exploring at 5% and 20%, on both streams and across both changes. The prediction is that with no exploring at all it holds the share rule on nine seeds in ten after a hundred queries of the use stream, since nothing then pushes it away, and that with 5% exploring both streams reach nine in ten after a hundred queries at the same cost on the use stream measured here. It could fail on the even stream: ignoring the share rule’s lists removes their small push toward the even stream as well, and a checker wrongly holding the share rule there would then learn only from explored queries. The question is whether a learner should discard evidence its own choices made worthless, or whether biased evidence is better than none when the stream is the one that needs the evidence most.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

CorpusEdit distanceExpected costMeasured countPredictionRankingWorkload