A Language Modeling Framework for Selective Query Expansion

Steve Cronen-Townsend, Yun Zhou, W. Bruce Croft2004 · DOI

TL;DR

Query expansion can significantly hurt retrieval performance for some queries. This paper introduces a method to predict when query expansion is likely to be detrimental by comparing language models of unexpanded and expanded search results. This allows for selective application of query expansion, improving overall retrieval reliability and effectiveness.

What Problem Does This Paper Address?

Query expansion is a common technique in information retrieval aimed at improving search results by adding related terms to a user's original query. While it can boost average retrieval performance across a large set of queries, it often degrades performance for specific queries, sometimes drastically. This inconsistency makes it difficult to deploy query expansion in operational systems, as the risk of harming a user's search experience is too high. The core problem this paper addresses is how to reliably identify when to use query expansion and, more importantly, when not to use it, to ensure consistent and improved retrieval performance.

Methods

The paper proposes a language modeling framework for selective query expansion. The core idea is to compare the language models derived from the ranked lists of documents produced by both unexpanded (baseline) and expanded retrieval.

  • Unexpanded Retrieval: This uses the standard query likelihood model, where each document is scored based on how likely it is to generate the query terms. Dirichlet smoothing is employed for document models.
  • Expanded Retrieval: This utilizes a relevance model, which is essentially a language model representing the likely terms of relevant documents for a query. This relevance model is estimated as a weighted average of document models from the top-ranked documents of the unexpanded retrieval.
  • Prediction Methods: Three methods are proposed to predict when expansion might hurt performance:
  • Clarity Method: This measures how "clear" or distinct a query's relevance model is compared to the overall collection model. High clarity suggests the query is specific, and expansion might be risky.
  • Overlap Method: This quantifies the overlap in document IDs between the top-ranked documents of the unexpanded and expanded retrieval lists. Low overlap suggests the expansion has significantly altered the retrieved set.
  • Model Comparison Method: This is the paper's most successful approach. It directly compares the language models of the unexpanded and expanded ranked lists. The comparison focuses on important terms in the unexpanded model, aiming to detect when the expanded retrieval deviates significantly from the original query's intent by using these important terms less frequently. This comparison is typically done using weighted relative entropy.

A key aspect is the development of an automatic thresholding mechanism for the model comparison method, based on sampling random one-term queries to estimate a distribution of comparison scores.

Datasets

The experiments were conducted on various TREC (Text REtrieval Conference) collections, including:

  • AP88-90
  • TREC 1+2+3
  • TREC 5, 6, 7, 8
  • TREC 9 Query Track aggregate

These collections are standard benchmarks in information retrieval research and provide diverse datasets for evaluating retrieval and expansion techniques. No new benchmarks were introduced; rather, existing TREC datasets were used to evaluate the proposed methods.

Key Insights and Ideas

  • Expansion is a Double-Edged Sword: The paper strongly emphasizes that query expansion, while beneficial on average, can be detrimental to individual queries. This is the fundamental motivation for selective expansion.
  • Language Models as Signposts: Comparing language models derived from ranked lists is a powerful way to detect when an expansion has "strayed" from the original query's semantic intent.
  • Model Comparison is King: The "model comparison" method, which directly contrasts the language models of unexpanded and expanded results, proved to be the most effective predictor of expansion performance.
  • Focus on Important Terms: The success of the model comparison method hinges on identifying and weighting the most important terms from the original query's context. This allows for a more nuanced comparison than simply looking at document IDs or overall model similarity.
  • Automatic Thresholding is Feasible: The paper demonstrates that it's possible to automatically set a decision threshold for when to apply expansion, making the approach practical for real-world systems.

Key Results

  • The Model Comparison method showed significantly better separation between scores for "good-to-expand" and "bad-to-expand" queries compared to the Clarity and Overlap methods.
  • For TREC 6 and TREC 8, using the model comparison method with an automatic thresholding strategy led to improved Mean Average Precision (MAP) compared to always using relevance model retrieval.
  • The automatic thresholding strategy, set to avoid expanding queries with scores in the top 5% of random one-term queries, reliably identified queries that performed poorly with expansion.
  • The paper highlights that while the method improves consistency, it doesn't always lead to dramatic increases in average precision, as its primary goal is to avoid significant performance degradation.

Limitations and Future Work

  • Sensitivity to Threshold: While automatic thresholding is demonstrated, the authors acknowledge that the optimal threshold might vary across collections and query types.
  • Model Comparison Nuances: The paper notes that the model comparison method isn't perfect. There were instances where bad-to-expand queries were not detected, particularly when the expansion model lost specific important terms by over-emphasizing other related terms.
  • Tuning Model Comparison: Future work is suggested to tune the model comparison parameters for optimal effectiveness on any given collection and query type.
  • Improving Ranked List Models: The authors suggest exploring ways to improve the ranked list models themselves, potentially by estimating document relevance at different ranks from training data.
  • Broader Application: The authors believe their framework for sensing when techniques stray from original intent could be applied to other query modification techniques beyond relevance models, such as user feedback.

Summary updated

Abstract

Query expansion is a well-known technique that has been shown to improve average retrieval performance. This technique has not been used in many operational systems because of the fact that it can greatly degrade the performance of some individual queries. We show how comparison between language models of the unexpanded and expanded retrieval results can be used to predict when the expanded retrieval has strayed from the original sense of the query. In these cases, the unexpanded results are used while the expanded results are used in the remaining cases (where such straying is not detected). We evaluate this method and others on a wide variety of TREC collections and show how to automatically compute a decision threshold for a collection. We demonstrate the ability of the method to enhance the effectiveness and reliability of the query expansion technique in information retrieval.
BibTeX
@misc{cronentownsend2004language,
  author = {Steve Cronen-Townsend and Yun Zhou and W. Bruce Croft},
  title = {{A Language Modeling Framework for Selective Query Expansion}},
  year = {2004},
  doi = {10.21236/ada477592},
}
Figure