Query Expansion

Adding terms to a query that the searcher did not type. Interactive and automatic expansion, controlled vocabularies, thesauri and query logs, an association thesaurus built from Cranfield and used to expand every query, why global expansion barely helps there while local expansion with relevance models (RM3) helps substantially, and later methods based on embeddings and document expansion.

In the relevance feedback article, a searcher's judgments taught the system that Cranfield query 180, how does scale height vary with altitude in an atmosphere, is well served by orbit, perigee, satellite and density. Pseudo-relevance feedback learned most of the same words from the top-ranked abstracts alone. Both methods learn only after a first retrieval, from documents that the query happened to find. Could a system know in advance that satellite goes with orbit and perigee, and add such words to any query before it runs?

Query expansion is the general name for adding terms to a query that the searcher did not type. The methods differ in where the new terms come from. Global methods draw them from a resource prepared before any query is seen: a thesaurus built by editors, one computed from the whole collection, or a log of other searchers' queries. Local methods draw them from the documents retrieved for this query, as relevance feedback and pseudo-relevance feedback do (Xu and Croft, 1996). This article is the canonical home of the global methods. The local methods have their own articles, and here they reappear in the language modeling framework of language models for retrieval.

Here is the route. First we look at why queries need expansion and at the ways a system can offer it. Then we build an association thesaurus from Cranfield, read its neighbor lists, and expand every Cranfield query from it. Next we expand the same queries locally with relevance models, the version of pseudo-relevance feedback built on language models, and compare the two. Finally we survey later methods. The article assumes BM25 and query likelihood.

Why queries need more words

Searchers and authors often use different words for the same thing. The textbook cites an early experiment, from about 1960, in which only 11 of 23 documents properly indexed under the subject toxicity used any word containing the stem toxi (Manning, Raghavan, and Schütze, 2008, §9.3, after Swanson). Blair and Maron concluded that it is "impossibly difficult" for users to predict the words that all (or most) relevant documents use, and only (or primarily) they use (quoted in the same section). This is the problem of vocabulary mismatch. Stemming handles one small part of it, different forms of the same word, and normalization leaves synonyms alone on purpose.

Query expansion attacks the rest from the query side. Its usual effect is to raise recall: documents that use the new words are now matched. Its usual cost is precision: a new word can bring in documents about something else. The textbook's example is a query for interest rate expanded to interest rate fascinate evaluate, where a thesaurus has supplied synonyms for the wrong sense of each word (§9.2.3).

Interactive or automatic

A system can expand a query in two ways (Manning, Raghavan, and Schütze, 2008, §9.2.2):

  • Interactive expansion suggests terms or whole alternative queries and lets the searcher choose. The textbook's example is the related-query suggestions that the Yahoo! web search engine showed in 2006.
  • Automatic expansion rewrites the query without asking. The textbook's example is PubMed, which in 2008 mapped the query cancer to ("neoplasms"[TIAB] NOT Medline[SB]) OR "neoplasms"[MeSH Terms] OR cancer[Text Word]. A searcher who does not look at the submitted query may never know that expansion happened.

The textbook adds that expansion is "much more understandable to the system user" than relevance feedback, since the added words can be shown and judged directly.

Controlled vocabularies. Editors assign each concept a canonical term and record its synonyms. The Library of Congress Subject Headings are one example, and in medicine the Unified Medical Language System used with MEDLINE is another (Manning, Raghavan, and Schütze, 2008, §9.2.2). The PubMed mapping above uses MEDLINE's Medical Subject Headings (MeSH), and search in professional domains shows MeSH used by hand in a medical search.

Manual thesauri. Editors record synonyms, broader terms and narrower terms without choosing a canonical form. For general English, recent work almost always uses WordNet (§9.3). Voorhees (1994) expanded queries by following WordNet's synonym sets and typed links. Expansion made little difference when the original queries were already relatively complete descriptions, even when the concepts to expand were chosen by hand; less developed queries could be improved significantly by expanding hand-chosen concepts. General thesauri also cover specialist vocabulary poorly, so a domain-specific thesaurus is usually needed (§9.2.3).

Automatic thesauri. Statistics computed over the collection itself can suggest which words are related, at no editorial cost. This is the method built and tested below.

Query logs. Searchers reformulate. When many of them follow one query with a related one, the pair is evidence that the queries are interchangeable. Jones, Rey, Madani and Greiner (2006) generated query substitutions this way. Such methods need very large query volumes, which makes them suited to web search (§9.2.2).

Building a thesaurus from the collection

The simplest automatic thesaurus rests on co-occurrence: words that appear in the same documents are likely to be related (Manning, Raghavan, and Schütze, 2008, §9.2.3). Build a term-document matrix $A$ whose entry $A_{t,d}$ is a weight for term $t$ in document $d$, and normalize each row to length 1. Then

$$C = A A^{\mathsf{T}}, \qquad C_{u,v} = \sum_{d} A_{u,d} A_{v,d},$$

is the cosine similarity between the rows for terms $u$ and $v$. Two terms that occur in the same documents with similar weights score near 1, and two that never share a document score 0. A term's nearest neighbors under $C$ are its thesaurus entry.

For Cranfield, the weight used here is $1 + \log_{10} \mathit{tf}_{t,d}$ for every term that occurs in a document. An IDF factor would make no difference, because it multiplies a whole row and the row normalization removes it. Terms that occur in only one document are left out of the neighbor lists. Some entries, with cosines rounded to three decimals:

Term Document frequency Nearest neighbors
satellit 32 orbit 0.622, perige 0.509, atmospher 0.440, km 0.428, densiti 0.395, eccentr 0.363
nozzl 80 exit 0.466, jet 0.368, exhaust 0.365, diverg 0.324, throat 0.303, mach 0.270
heat 306 transfer 0.786, temperatur 0.589, rate 0.436, laminar 0.430, layer 0.409, boundari 0.407
flutter 56 panel 0.446, piston 0.326, midplan 0.314, aerodynam 0.274, bai 0.267, trend 0.265
model 177 test 0.404, tunnel 0.352, number 0.344, were 0.340, from 0.339, mach 0.332
studi 240 flow 0.362, made 0.359, effect 0.317, which 0.307, from 0.301, experiment 0.301

The first rows are what a thesaurus should offer. The neighbors of satellit include orbit and perige, the terms the searcher's judgments supplied for query 180, now found without any query at all. The neighbors of nozzl are the parts and flows of a nozzle.

The later rows show the method's weaknesses:

  • Generic words. Studi occurs in 240 abstracts, and its neighbors are words that occur everywhere: made, which, from. Cosine rewards frequent co-occurrence, and frequent words co-occur with everything.
  • One sense wins. In Cranfield, model almost always means a wind-tunnel model, so its neighbors are test and tunnel. A query about a mathematical model would be expanded toward wind tunnels. The textbook's version of this problem is a query for Apple computer expanded to Apple red fruit computer (§9.2.3).
  • Redundancy. Flutter and panel are each other's nearest neighbor, and they occur together in 20 abstracts. A neighbor that mostly occurs in documents the query already matches can reorder those documents but brings in few new ones. The textbook makes this point about automatic thesauri in general (§9.2.3).

Bai is the stem of bay, as in a panel bay, and midplan that of midplane. Both are real panel-flutter vocabulary.

Expanding a query as a whole

Expanding each query term separately inherits each term's ambiguity. Qiu and Frei (1993) chose expansion terms by their similarity to the query as a whole rather than to its individual terms. The experiments here apply the same idea to the cosine thesaurus: a candidate's score is its average similarity to the query's terms. A candidate that is related to only one of them, in a sense the other terms do not support, scores lower.

For query 185, experimental studies on panel flutter, the ten best candidates by this score are result, effect, number, investig, mach, made, from, pressur, were and theori. The generic words experiment and studi dominate the average. Multiplying each candidate's score by its BM25 IDF demotes the generic candidates and gives midplan, suscept, bai, psf, prone, unstress, aluminium, trend, transtabl and piston. These are much more specific to panel flutter.

Check your understanding. Each list is added to the query with weight 0.5, scored with BM25. Which list improves query 185's average precision, now 0.784?

The generic list. With it, average precision rises to 0.818; with the specific list, it falls to 0.721. Words such as pressur and mach occur in nearly all of the nine relevant abstracts (pressur in all nine), so they reinforce documents BM25 already ranked well. The specific words come from particular panel-flutter abstracts, and several of those abstracts are not among the nine judged relevant. A list that looks better to a reader is not necessarily better for a given query. That makes it hard to judge an expansion method from examples. It has to be measured on many queries.

Global expansion on all of Cranfield

The experiment expands every Cranfield query with the $n$ best candidates by similarity to the whole query, with and without the IDF factor. It scores documents with BM25 ($k_1 = 1.2$, $b = 0.75$), multiplying each added term's contribution by an expansion weight $w$. The setup matches comparing ranking models, where BM25 alone has a mean average precision (MAP) of 0.307. Results on all 225 queries, with $p$ from a paired randomization test against BM25 (see significance testing):

Candidates scored by Terms $n$ Weight $w$ MAP Improved Harmed $p$
similarity 10 0.25 0.309 104 102 0.50
similarity 20 0.5 0.287 83 129 0.001
similarity × IDF 5 0.25 0.317 108 101 0.032
similarity × IDF 10 0.25 0.320 121 92 0.006
similarity × IDF 10 0.5 0.317 113 102 0.14
similarity × IDF 20 0.5 0.307 107 112 1.00

Without the IDF factor, no setting helped, and adding many generic terms at a high weight did significant harm. With it, the best setting raised MAP from 0.307 to 0.320. Expanding each query term separately, with its own nearest neighbors, gave results like those of the plain similarity score (MAP 0.283 to 0.311, the script lists them).

The best row was picked from eighteen settings (the script also runs term-by-term expansion), on the same queries it is reported on. To choose fairly, the queries were split as in comparing ranking models into 112 development and 113 test queries. On the development queries, the best IDF-weighted setting ($n = 20$, $w = 0.25$) raised MAP from 0.316 to 0.341. On the test queries it gave 0.297, exactly BM25's 0.297 ($p = 0.93$). On held-out queries, global expansion from this thesaurus gained nothing.

The change in average precision for each of the 225 queries, sorted. Left: ten IDF-weighted thesaurus terms added to BM25 at weight 0.25. Right: RM3 (10 feedback documents, 10 terms, original query weight 0.5) against the query likelihood ranking it starts from. Notice that the left panel is nearly symmetric, with 92 queries harmed for 121 improved, while on the right the improvements dominate, 152 to 61.
The change in average precision for each of the 225 queries, sorted. Left: ten IDF-weighted thesaurus terms added to BM25 at weight 0.25. Right: RM3 (10 feedback documents, 10 terms, original query weight 0.5) against the query likelihood ranking it starts from. Notice that the left panel is nearly symmetric, with 92 queries harmed for 121 improved, while on the right the improvements dominate, 152 to 61.

Local expansion with relevance models

Pseudo-relevance feedback answers the thesaurus's main weakness: it draws terms from documents that the query itself retrieved, so the sense of each word is fixed by the query's context. The pseudo-relevance feedback article measured a term-based version on top of BM25. Here is the version built into the language modeling approach.

The relevance model

Here is the idea in one sentence. If the query words and the words of relevant documents were drawn from the same unknown distribution, then the probability that a word is drawn along with the query words estimates its probability in the relevant documents. Lavrenko and Croft (2001) called the estimated distribution a relevance model, and estimated it with no relevance judgments at all.

The formal version. Let $q_1, \dots, q_k$ be the query words, and let $D$ range over a set $\mathcal{R}$ of document language models, in practice those of the top-ranked documents. Suppose a document model $D$ is picked, and the query words and one more word $w$ are drawn from it independently. Then

$$P(w, q_1, \dots, q_k) = \sum_{D \in \mathcal{R}} P(D)\, P(w \mid D) \prod_{i=1}^{k} P(q_i \mid D).$$

The product is the query likelihood $P(q \mid D)$. With a uniform $P(D)$ and after dividing by $P(q_1, \dots, q_k)$, the relevance model is

$$P(w \mid R) = \sum_{D \in \mathcal{R}} P(w \mid D)\, \frac{P(q \mid D)}{\sum_{D' \in \mathcal{R}} P(q \mid D')},$$

an average of the top documents' word distributions, each weighted by its share of the query likelihood (the form used by Abdul-Jaleel et al., 2004, eq. 2). A document that matches the query strongly contributes most of its vocabulary.

The relevance model replaces the query entirely, so Lavrenko and Croft described it as "a massive query expansion technique." The variant called RM3 keeps the original query (Abdul-Jaleel et al., 2004, §3.1.4). It truncates the relevance model to its $m$ most probable words, renormalizes it, and mixes it with the query's own maximum likelihood model:

$$P(w \mid q') = \alpha\, P_{\mathrm{mle}}(w \mid q) + (1 - \alpha)\, P(w \mid R),$$

where $\alpha$ is the weight of the original query. Documents are then ranked by $\sum_w P(w \mid q') \log P(w \mid d)$, which is query likelihood with the query's words replaced by a weighted distribution. With the expanded model equal to the original query, it ranks exactly as query likelihood does.

Query 185 and query 180

The runs below use Dirichlet smoothing with $\mu = 200$, the setting chosen on the development queries in language models for retrieval, 10 feedback documents, 10 relevance-model terms and $\alpha = 0.5$. For query 185, the relevance model's ten most probable words, with probabilities rounded to four decimals, are panel (0.0421), flutter (0.0277), were (0.0225), effect (0.0146), buckl (0.0145), studi (0.0117), experiment (0.0114), mach (0.0108), 3 (0.0103) and us (0.0102).

The relevance model returns the query's own terms near the top and reorders them: panel and flutter now outweigh experiment and studi, because the top documents use them far more. It also adds buckl (buckling, a related failure of thin panels) and generic words. After mixing, the query model gives panel 0.245 and flutter 0.204, against 0.158 and 0.157 for studi and experiment. Average precision rises from 0.774 under query likelihood to 0.834.

For query 180, the relevance model's top words include h, height, equat, constant, orbit, perige and air, and average precision rises from 0.387 to 0.455. Here the local method finds orbit and perige the way the thesaurus did, but only because the query's top documents are about satellite orbits.

On all of Cranfield

Results on all 225 queries, against query likelihood ($\mu = 200$, MAP 0.284) and against BM25 (MAP 0.307):

Feedback documents Terms $m$ Original weight $\alpha$ MAP Improved / harmed vs. QL $p$ vs. BM25
10 10 0.5 0.330 152 / 61 < 0.001
10 20 0.5 0.333 165 / 50 < 0.001
5 10 0.5 0.331 155 / 60 < 0.001
10 10 0.7 0.321 163 / 49 0.019
10 10 0.3 0.323 139 / 77 0.054

Every setting improved on query likelihood by more than 0.035 ($p < 0.001$ in each case). The first setting, fixed in advance, takes query likelihood from below BM25 to above it, and above the 0.324 of term-based pseudo-relevance feedback in the pseudo-relevance feedback article. Chosen on the development queries ($m = 20$), RM3 reached 0.328 on the test queries, against 0.284 for query likelihood and 0.297 for BM25 ($p < 0.001$ for both). Unlike global expansion, the gain survives on held-out queries.

Check your understanding. Should RM3 replace query likelihood for every query?

Not without caution. Even the best setting harmed 50 of the 225 queries, and the figure shows losses as large as 0.2 in average precision. The query drift described in the pseudo-relevance feedback article applies to relevance models as well: if the top documents are about the wrong subject, so is the relevance model. RM3's gains are larger on average, not free of risk.

Why local beat global here

Xu and Croft (1996) compared the two families and concluded that, although global analysis has some advantages, local analysis is generally more effective. The Cranfield results agree, and the traces suggest reasons:

  • Context. A global neighbor list is the same for every query. It cannot tell that model in a query about mathematical models is not the model of a wind tunnel. Local feedback draws from documents that already match the query as a whole.
  • Generality. Cosine over documents ranks frequent words highly, and the IDF correction helps only in part. A relevance model weights words by how strongly the top documents match the query, so words common to the best-matching documents win.
  • Redundancy. Global neighbors tend to co-occur with the query terms in documents already retrieved, as flutter and panel do.

The textbook's overall judgment is consistent with this: query expansion with thesauri "is less successful than relevance feedback, though it may be as good as pseudo relevance feedback" (§9.2.3). Here, on one small collection, an automatic thesaurus did worse than pseudo-relevance feedback. A manual, domain-specific thesaurus, which Cranfield lacks, might do better. Global methods keep real advantages. The textbook notes that thesaurus-based expansion needs no input from the user and is easier for a searcher to understand. It also needs no first retrieval.

Later methods

Two lines of later work kept the problem and changed the source of related words.

  • Word embeddings. Dense word vectors, such as those of word2vec, place words with similar contexts close together, which makes them a natural automatic thesaurus. Diaz, Mitra and Craswell (2016) found that embeddings trained globally underperform embeddings trained on documents related to the query's topic for query expansion. Their result repeats the local-versus-global finding with a newer kind of thesaurus.
  • Document expansion. Instead of adding words to the query, words can be added to documents when they are indexed. Nogueira, Yang, Lin and Cho (2019) trained a sequence-to-sequence model to predict queries that a document is likely to answer, and appended the predicted queries to the document before indexing it. The expansion is paid for once, at indexing time, rather than on every query.

What we have learned

Query expansion adds words the searcher did not type, to reach documents that describe the same thing in other words. Global expansion takes them from a thesaurus. The one built from Cranfield's co-occurrences found orbit and perige for satellit, but also generic and wrong-sense neighbors, and on held-out queries it gained nothing over BM25. Local expansion with relevance models takes words from the query's own top documents, weighted by how well each matches. It raised query likelihood's MAP from 0.284 to 0.330 and kept its gain on held-out queries, while still harming about a quarter of the queries.

Every experiment in this unit, these included, has scored the Cranfield collection thousands of times. How is BM25 computed efficiently, and is every "BM25" the same formula? Implementing BM25 answers both.

References

  • Abdul-Jaleel, N., Allan, J., Croft, W. B., Diaz, F., Larkey, L., Li, X., Smucker, M. D., and Wade, C. (2004). UMass at TREC 2004: Novelty and HARD. In Proceedings of TREC 2004. record · 2 pages
  • Diaz, F., Mitra, B., and Craswell, N. (2016). Query expansion with locally-trained word embeddings. In Proceedings of ACL 2016, 367–377. record
  • Jones, R., Rey, B., Madani, O., and Greiner, W. (2006). Generating query substitutions. In Proceedings of WWW 2006, 387–396. record · 2 pages
  • Lavrenko, V., and Croft, W. B. (2001). Relevance-based language models. In Proceedings of SIGIR 2001, 120–127. record · 3 pages
  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 9. Cambridge University Press. record · 83 pages
  • Nogueira, R., Yang, W., Lin, J., and Cho, K. (2019). Document expansion by query prediction. arXiv:1904.08375. record
  • Qiu, Y., and Frei, H.-P. (1993). Concept based query expansion. In Proceedings of SIGIR 1993, 160–169. record
  • Voorhees, E. M. (1994). Query expansion using lexical-semantic relations. In Proceedings of SIGIR 1994, 61–69. record
  • Xu, J., and Croft, W. B. (1996). Query expansion using local and global document analysis. In Proceedings of SIGIR 1996, 4–11. record · 2 pages