A second try before any feature

A trie fitted to its queries found that a stream of misspelt words knows something its vocabulary does not: how far the answers lie. A misspelling of a vocabulary word is always within two edits of the word it came from, and a nearest-word search told its answer’s distance in advance reads a fifth of the cells of one that discovers its bound as it goes — the price the bound the search finds for itself put on not knowing. The page learned one starting bound for the whole stream, the median of the last 200 answers, and found that one try at that bound, falling back to the discovering walk when nothing lay within it, never cost more than discovering. On a stream where a fifth of the queries were misspellings of words the vocabulary lacks, it read 13,028 cells a query against discovering’s 21,090.

Its closing section proposed the obvious refinement. One number for the whole stream ignores what each query says about itself. A long query with unfamiliar letters is more likely to be a word the vocabulary lacks, and a query whose first three letters are a real prefix in the trie is more likely a misspelling of a word it has. The proposal was a bound chosen per query from such features, with the first-three-letters test singled out as the one that should separate the two kinds of query.

This page measures that proposal. The test it singled out separates nothing. Two other features do predict distance, and a start chosen from them still buys almost nothing. What does buy something, more than any feature, is a second try.

The test that was proposed does not separate #

The setting is the earlier page’s exactly: the 2,424 distinct words of the collection’s fixed corpus of essays in a trie of 7,709 prefixes, 2,000 queries made by putting one or two random typing errors into vocabulary words, and 600 made the same way from words of a second fixed corpus that the vocabulary does not contain. The walk is the bounded walk the columns the candidates share built. It computes one edit-distance column per trie node, prunes a subtree when a column’s smallest value passes the bound, and tightens the bound whenever it reaches a word. Every cost below is cells of that table, every attempt charged. Every answer is checked against the discovering walk’s.

The first-three-letters test calls 58% of misspelt vocabulary words known and 53% of misspellings of words the vocabulary lacks. The two distributions of how far a query’s letters go down the trie are nearly the same shape. The test sends the two kinds of query to its two sides in almost the same proportions, so a bound keyed on it would be applied to nearly the same mixture either way.

Both halves of the prediction’s reasoning fail. A typing error falls anywhere in a word with equal chance, and for a short word the first three letters are much of it. A misspelling of code has an error in its first three letters most of the time, so a misspelt vocabulary word loses its known prefix 42% of the time. The other half fails because the words the vocabulary lacks are English words too. Instrumented, pretending and duration begin ins, pre and dur, and a vocabulary of a few thousand English words has all of those. An unfamiliar word is unfamiliar in its middle and its end, where its stem and its suffix are.

The earlier page found the test plausible because a misspelling “usually keeps a real prefix”. That claim is true of misspellings a person makes, which cluster late in a word and near the keyboard’s neighbours. It is not true of the uniformly placed errors every measurement of this search has used, and the distinction matters. A feature’s value depends on the process that made the queries, and the one proposed was reasoned from a different process than the one it would have been used on.

Two features that do predict a distance #

A query’s length and its letter-triples are different. The vocabulary’s letter-triples are a set of a few thousand, computed once. A query’s triples that are not in the set are evidence that the query is not a small edit of anything in the vocabulary, since one typing error breaks at most three triples.

Both features predict distance, and strongly for the queries that matter. A word the vocabulary lacks lies 1.9 edits from its nearest word when it is six letters or fewer and 6.2 when it is ten or more. The more letters it has, the more of them the vocabulary cannot match, and a long technical word often has no neighbour closer than a whole suffix away. With three or more unseen letter-triples its answer lies 5.5 edits away on average; with none, 2.0. Misspelt vocabulary words move much less, 1.1 to 1.8, because a word with two errors is at most two edits from its source whatever its length.

These are the features the proposal wanted. They are cheap: a length is free, and the triples are one pass over the query against a hash set. They are computed before the search reads a single cell. And they sort the stream into classes whose answer distances genuinely differ.

The obvious next step keeps the earlier page’s rule and applies it per class: learn the median of recent answers separately for each class, and give each query one try at its own class’s median.

What a feature buys once the stream is sorted into classes #

The measurement runs that rule for each feature on streams with 0%, 10%, 20% and 30% of queries from outside the vocabulary. It then asks a stronger question. For each class, what single starting bound would have been best, chosen knowing the whole stream in advance? No rule keyed on that feature can do better with one try. The same question is asked for schedules of more than one try, which the next sections come to.

The learned rule improves with the features: letter-triples take the single try from 13,009 cells a query to 11,626, 11% less. The prefix test makes it slightly worse, 13,254. That looks like the proposal half-vindicated, until the hindsight column is read beside it.

With no feature at all, the best single start in hindsight costs 11,083 cells. With the best feature, 10,950: 1.2% less. The hindsight optimum for no feature is a start of two for every query. For length it is two in every class. For letter-triples it is one for queries with no unseen triple and two for the rest; for length and triples crossed into twelve classes, one in the class of short queries with no unseen triple and two in the other eleven. A feature that predicts distance by a factor of three moves the best start by one step in a sliver of the stream.

So the 11% the letter-triples rule gained was not bought by the feature. The featureless median rule is simply a poor rule. On this stream the median answer is one edit, and 41% of misspelt vocabulary words lie at two, so a start at the median fails and falls back on nearly half the familiar queries. Splitting the stream into classes moved some classes’ medians to two, and two was the right start all along. The median was a constant somebody chose, of the kind the threshold somebody chose found in library sorts, and a single quantile set higher does the same thing with no feature: taking the 60th to 80th percentile of the last 200 answers instead of the median, the one-class rule reads 11,104 cells a query, within 0.2% of its hindsight optimum.

Why the start is two for almost everything #

The reason a feature buys so little is in what the walk costs at each bound.

A walk at a bound of two costs 4,865 cells on a misspelt vocabulary word and 6,171 on a word the vocabulary lacks. The discovering walk costs 17,621 and 35,306. One try at two is insurance, and the premium is a quarter to a sixth of the claim it covers. For a familiar query the try at two always succeeds. For an unfamiliar one it fails 56% of the time, and each failure wastes the walk — 6,862 cells on the queries that fail it — before a discovering walk that would have been paid anyway.

The asymmetry decides everything. If a class were known to hold only unfamiliar queries, the right policy would be to skip the try and discover at once, saving the premium on each. But a class that a feature can identify is never pure. The class with the most unfamiliar queries, ten letters or more with three or more unseen triples, holds 63 unfamiliar queries and 140 familiar ones on the 20% stream. Skipping the try there would save each of the 63 its walk at two, 6,943 cells on average, and cost each of the 140 the difference between discovering and a walk at two, which for these long familiar queries is 35,157 cells. The class would have to be more than five parts unfamiliar to one familiar before skipping paid, and no class a feature draws comes near that. The hindsight search picks two everywhere because the premium is small against the claim and every class contains some queries that claim.

This is what insurance against an estimate costs found for a query planner, seen from the other side. There the question was whether to buy cover against a wrong estimate; here it is whether an estimate can be good enough to cancel cover that is already cheap. A feature is worth something to a search only when it can identify queries for which the insurance is certainly wasted, and on a stream where most queries claim, a feature that shifts the odds by a factor of three still cannot.

A second try, which no feature beats #

The single try’s weakness is on the familiar queries, not the unfamiliar ones. A familiar query whose answer is at one edit pays 4,865 cells for a walk at two when a walk at one, at 1,083, would have found it. Starting at one and widening to two recovers that. The earlier page measured exactly this on a pure stream — widening one step at a time from one — and found it the best policy measured there and the worst once unfamiliar queries arrived. That was because it kept widening, one walk per step, all the way to answers twenty edits away.

The policy between the two takes two steps and then stops widening: a walk at one, a walk at two, and then the discovering walk.

One, then two, then discover reads 10,327 cells a query at 20% unfamiliar, against 13,009 for the earlier page’s single try at the median and 11,083 for the best single start any feature allows. On a stream with no unfamiliar queries it reads 3,726, exactly what widening read there, because every familiar answer lies within two. At every mixture measured it is below one try at two and below every feature’s hindsight optimum for a single try. Measured against the gap between the earlier page’s rule and a search told every answer’s distance, it closes 55% of that gap. The best features, chosen per class in hindsight on top of it, close a further 2.7%.

Its cost falls where it should. A familiar query at one edit pays 1,083 cells. One at two pays 7,563 on average: the failed walk at one, then the walk at two. An unfamiliar query whose answer lies past two pays both short walks before discovering, 7,985 cells of premium where one try at two paid 6,862, which is why on a stream of only unfamiliar queries this schedule reads 37,086 against one try’s 36,318. The walk at one is so cheap that paying it on every query costs less than the walks at two it saves on the familiar ones.

A third step does not pay. One, two, three, then discover reads 11,081 at 20%, 7% more than stopping at two. The walk at three costs 9,528 on a familiar query and 14,611 on an unfamiliar one, and on this stream only the unfamiliar queries ever reach it, where it fails 56% of the time. Doubling is worse still: one, two, four, then discover reads 11,158, and two, four, then discover 11,914. Doubling is the schedule a band as wide as the answer uses to find an edit distance between two strings, where the cost of a band grows linearly with its width and a geometric schedule wastes at most a constant factor. Here the cost of a bound grows much faster than linearly, and the answers pile up at two steps and then scatter over twenty. A schedule has to be fitted to where the answers are, and this stream’s answers are at one and two, or anywhere at all.

A schedule chosen from a price list, and the queries that pay it #

A fixed schedule was found by trying eight of them. The natural way to make that automatic is to price each schedule and pick the cheapest per query. The walk’s cost at each bound, by query length, is a property of the trie and can be measured once on a calibration stream. The chance that the answer lies past each bound can be read off the last 200 answers. The discovering walk’s cost can be learned from the fallbacks the search actually pays.

That rule reads 11,146 cells a query at 20% unfamiliar, 8% more than the fixed schedule it was meant to find. It chooses one, two, three, then discover for most queries, the schedule the measurement just showed is 7% dearer. Pricing the discovering walk by how far the answers that fell back had lain, rather than by the mean of all fallbacks, changes the result by less than 0.2%.

The price list is right about the average query and wrong about the queries that reach each step. A query reaches the walk at three only when its answer lies at three or beyond, and those are the queries for which every walk is dear. They are long and unfamiliar, and they keep their bounds loose for most of the trie. The walk at three costs them 19,254 cells, 52% more than the list’s 12,633. The discovering walk after three costs them 72,606, 76% more than the list’s 41,235. At the first step the list is right, because nearly every query reaches it. The error grows with every step, because each step selects a narrower and dearer set of queries.

That is selection, and a price list keyed on length cannot see it. Length is correlated with being unfamiliar, but the queries that fail at two are a far more selected set than the long ones. A rule that multiplies the chance of reaching a step by the average price of that step has assumed the two are independent, and here they are not. A budget split before the question arrives failed in the same way from a different direction: a textbook variance for a difference of sketches omitted a covariance, and a switch that believed it chose wrong on every draw. In both cases the formula was built from quantities that are each right on average, and the error is in their product.

The fixed schedule avoids the problem by not pricing anything. A rule that tried each schedule in turn and kept the cheapest measured one would avoid it too, since it would pay the real costs of the queries that reach each step. What cannot work is a model of the steps priced separately, because the cost of a step and the chance of reaching it are set by the same thing, the query’s distance from the vocabulary.

What was measured and what was not #

Uniform typing errors, one vocabulary. The queries have one or two errors placed uniformly in the word. Real errors cluster late in the word and near the keyboard’s neighbours, which would make the first-three-letters test better than it is here. On such a stream the prefix test might separate the two kinds of query, and the measurement says nothing either way.

One corpus of unfamiliar words. The words the vocabulary lacks are technical English, so they share its prefixes. Proper names, foreign words or random strings would share fewer, and a feature that separated them could pay. It would pay only in a class unfamiliar enough that skipping the insurance saves more than it costs the familiar queries in the class, and the price plate says how unfamiliar that is.

Features chosen in advance. Three features were tried, the three the earlier page proposed or that are nearly free. A learned classifier over many features might identify unfamiliar queries better, and there is a ceiling on what it could buy. A search that knew perfectly which kind each query was, and gave every familiar query one try at two and every unfamiliar one the discovering walk at once, would read 10,884 cells a query at 20% — 5% more than the fixed schedule, which identifies nothing. Given the schedule for its familiar queries instead, the perfect classifier reads 9,973, 3.4% under it. Perfect knowledge of which kind a query is buys less than a second walk at one bound.

Cells, not time. Every count is a cell of the edit-distance table, the earlier pages’ unit. A schedule of three walks restarts from the root three times. The count is not the time is the reminder that restarts and cells are priced differently by a machine, and that difference is unmeasured here.

Still open: the answer a checker can decline to give #

Every policy here ends in the discovering walk, which finds the nearest vocabulary word however far away it is. The selection plate says what that costs: the queries still unfound after a walk at two pay 52,737 cells each to discover, and they are 11% of the stream. For those queries, the answer found is almost never useful. A misspelt vocabulary word is always within two edits of its source, so every query that fails the walk at two is a query whose intended word the vocabulary does not have. The nearest vocabulary word to instrumnted is not what its writer meant, however carefully it is found.

That suggests a checker that declines. After the walk at two fails it reports “no suggestion within two edits” and stops, or it pays for one more walk at three and then stops. The filter that feeds the table refused candidates before they reached a table on a cheap test. This would refuse the answer after a cheap test, which is a different kind of economy, since it changes what the search promises rather than how it keeps the promise.

The measurement that follows sets a cap on the answer’s distance, from one to six and none, and counts two things at each: the cells a query and the share of queries whose intended word is among the suggestions returned. For misspelt vocabulary words the intended word is known. For misspellings of words the vocabulary lacks the right suggestion is none, and a suggestion at any distance counts as a false one. The prediction is that a cap at two keeps every useful suggestion on this stream and costs about a third of discovering, and that the false suggestions the uncapped search makes are almost all at three edits or more. The cap would then be worth more than any schedule, because it removes the most expensive walk rather than fitting the walks before it. It could fail in one way: if a large share of unfamiliar words have a vocabulary word within two edits that is a plausible suggestion — a plural, a tense, a word with a common suffix — then a cap at two keeps those false suggestions and saves only the far walks.