Query Understanding: Intent, Entities and Spelling

By the time a query reaches the index it has usually been rewritten four or five times. Every one of those rewrites is a decision that can be wrong, and most search bugs that get reported as “bad results” happened before the index was touched.

What runs before retrieval

A mature query pipeline is a sequence of small, individually testable stages. In roughly the order they run:

Each stage should be independently loggable. When somebody reports that a query is broken, the first question is which stage changed it, and a pipeline that cannot answer that turns every relevance bug into an afternoon of bisecting by hand.

Spelling correction as a wager

The standard formulation is the noisy channel model: assume the user intended some string c and a noisy typing process produced the observed query q. Pick the c that maximises the posterior:

c* = argmax over c of  P(c | q)
   = argmax over c of  P(q | c) * P(c)

  P(c)      the language model: how likely was anyone to mean c at all,
            estimated from query-log frequency
  P(q | c)  the error model: how likely is this particular corruption,
            estimated from edit distance and a confusion matrix

Candidate generation is a separate problem from candidate scoring. You need all strings within edit distance 1 or 2 of the query, fast; a BK-tree over the vocabulary or the SymSpell deletion-index trick both do it in sub-millisecond time. Use Damerau-Levenshtein rather than plain Levenshtein, because transposition is one of the most common typing errors and plain Levenshtein charges two edits for it.

Work an example. The user typed ihpone. Two candidates survive generation: iphone, reachable by one transposition, and phone, reachable by two edits. Assume an error model that assigns probability 0.10 to a distance-1 corruption and 0.01 to a distance-2 one, and take priors from a query log where iphone is 0.2% of queries and phone is 0.05%. Every one of those four numbers is an input you would estimate from your own logs:

iphone:  P(q|c) * P(c) = 0.10 * 0.0020 = 2.0e-4
phone:   P(q|c) * P(c) = 0.01 * 0.0005 = 5.0e-6

ratio = 40 : 1  ->  correct to "iphone"

The prior is doing most of the work, and that is correct: a correction to a string nobody ever searches for is almost never right, however close it is in edit distance. It also tells you where the correction model comes from — your own query log, weighted by whether the query led to a click, not a dictionary.

Entities and segmentation

In a vertical, query understanding is mostly attribute extraction. “red running shoes size 10” is not seven tokens to be matched; it is colour=red, category=running-shoes, size=10, and the ranking problem is almost trivial once that parse exists. The failure modes are specific and worth naming:

• Ambiguous units. “size 10” is US, UK and EU sizes that are all different shoes. Extraction without a locale is extraction of the wrong thing.
• Entity strings that are also common words. A brand called Apple, Gap, Next or Mango collides with ordinary vocabulary, and a naive dictionary tagger will structure “mango smoothie” as a brand query.
• Segmentation that changes meaning. In Chinese and Japanese there are no spaces, and a different valid segmentation is a different query. Character bigram indexing is the cheap fallback and it is not as bad as it sounds — see multilingual search.
• Over-extraction. If the parser is confident on everything, a query that mentions a colour in passing becomes a hard colour filter and recall collapses. Extracted attributes should usually be boosts, not filters, unless confidence is high.

Intent classification

Broder’s 1998 taxonomy — navigational, informational, transactional — is thirty years old and still the right first cut, because the three want different result pages. A navigational query wants one URL and nothing else; showing ten results is a failure even if all ten are relevant. An informational query wants breadth. A transactional query wants the thing that can be bought right now, which makes stock a ranking feature rather than a filter.

Classifying is not usually a modelling challenge. Query frequency plus click entropy over the historical result set gets most of the way: queries where nearly all clicks land on one result are navigational almost by definition. That same click-entropy statistic is the gate for whether personalisation should fire, and it is worth computing once and reusing.

When understanding does damage

Every stage in this pipeline is a bet that the user did not mean exactly what they typed, and the bet loses in predictable places.

• Correcting a valid rare string. Model numbers, brand names and part codes look exactly like typos to an edit-distance model. The rule that fixes this is not a better model: never correct a token that exists in your catalogue or entity dictionary, and gate correction on the original query returning too few results.
• Expanding a query that was already precise. Synonym expansion on a query containing a specific identifier dilutes it. Run expansion as a fallback tier, not unconditionally.
• Stemming that merges distinct concepts. Aggressive stemmers famously conflate unrelated words; lemmatisation costs more and does not. Check the pairs your stemmer merges on your own vocabulary before shipping it.
• Silent rewriting. If you changed the query, say so in the interface and offer the original as one click. This is the one piece of UI that converts a wrong rewrite from a dead end into a minor annoyance.