Improving Query Spelling Correction Using Web Search Results

Qing Chen, Mu Li, Ming ZhouEMNLP 2007

TL;DR

This paper tackles the challenge of correcting spelling errors in web search queries, which traditional lexicon-based methods fail at due to the sheer volume of web terms. They propose a novel approach that leverages the dynamic information found in web search results to significantly improve spelling correction accuracy, especially for rare or out-of-vocabulary terms.

What Problem Does This Paper Address?

Correcting spelling errors in user queries is crucial for search engines to return relevant results. Traditional spelling correction methods rely on pre-defined dictionaries (lexicons). However, the web is a vast and ever-evolving space, making it impossible to create a comprehensive lexicon that covers all possible terms users might search for. This is particularly problematic for web queries, where users might use slang, product names, or even misspell common words. While using query logs has shown promise, it struggles with "data sparseness" – meaning it doesn't have enough examples to accurately correct rarely used terms or misspellings. This paper aims to bridge this gap by using the rich, real-time information available in web search results themselves to enhance spelling correction.

Methods

The authors propose a feature-based approach using a Maximum Entropy (MaxEnt) model. The core innovation lies in the features they extract from web search results. They explore two main schemes:

  • Scheme 1 (M1): This scheme augments a baseline model (M0) with features derived solely from the search results of the input query itself. These features include the number of pages returned (indicating query popularity), the presence of candidate terms in URLs and snippets of search results, and patterns suggesting abbreviations.
  • Scheme 2 (M2): This scheme builds upon Scheme 1 by also incorporating information from the search results of the top-ranked correction candidate. This allows the model to compare the query and its potential correction based on their respective web presences, providing richer contextual evidence.

The MaxEnt model is well-suited for this task because it can naturally integrate diverse information sources (lexicon, query logs, and now web search results) to estimate the probability of a correction being correct.

Datasets

The experiments were conducted using a manually labeled dataset derived from real-world queries.

  • Training Set: 2,323 query-truth pairs.
  • Test Set: 991 query-truth pairs. These datasets were sampled from MSN's daily query logs. The paper notes that the web search results themselves were fetched from MSN's search engine.

Key Insights and Ideas

  • Web Search Results as a Dynamic Lexicon: The paper convincingly demonstrates that web search results act as a dynamic, comprehensive, and up-to-date source of information for spelling correction, overcoming the limitations of static lexicons.
  • Leveraging Search Result Features: Features like the number of matching pages, term occurrences in URLs and snippets, and abbreviation patterns are highly effective in distinguishing valid out-of-vocabulary (OOV) terms from misspellings.
  • Addressing Data Sparseness: The proposed methods, particularly by incorporating web search data, significantly improve the correction of rare or OOV terms, which are a major weakness of query log-based methods.
  • Two-Stage Refinement: Scheme 2, which uses search results for both the query and its top candidate, offers further improvements, suggesting that comparing the web presence of a query and its potential correction is beneficial.

Key Results

The proposed methods showed significant improvements over the baseline model (M0):

  • Scheme 1 (M1) vs. Baseline (M0): Achieved a 25.6% error rate reduction and a 23.6% improvement in precision.
  • Scheme 2 (M2) vs. Scheme 1 (M1): Further reduced errors by 13.1% and improved recall.
  • Overall: The paper reports a 16.9% relative F-measure improvement and a 35.4% overall error rate reduction compared to the baseline method.
  • OOV Terms: M1 and M2 showed particularly strong performance on out-of-vocabulary (OOV) terms, which constitute a significant portion of spelling errors.

Limitations and Future Work

  • Candidate Set Size: The paper acknowledges that the size of the candidate confusion set can become very large for multi-term queries, posing computational challenges. They use candidate pruning based on n-gram language models to manage this.
  • Web-Scale Processing: While their method is described as "light-weight," the underlying process of fetching and analyzing web search results for every query is inherently a web-scale data processing challenge.
  • Future Work: The authors suggest exploring page ranking information (trusted sites are less likely to have wrong spellings) and deeper analysis of term co-occurrence statistics within search result snippets.

Summary updated

Abstract

Traditional research on spelling correction in natural language processing and infor-mation retrieval literature mostly relies on pre-defined lexicons to detect spelling er-rors. But this method does not work well for web query spelling correction, because there is no lexicon that can cover the vast amount of terms occurring across the web. Recent work showed that using search query logs helps to solve this problem to some extent. However, such approaches cannot deal with rarely-used query terms well due to the data sparseness problem. In this paper, a novel method is proposed for use of web search results to improve the existing query spelling correction models solely based on query logs by leveraging the rich information on the web related to the query and its top-ranked candidate. Ex-periments are performed based on real-world queries randomly sampled from search engine’s daily logs, and the results show that our new method can achieve 16.9 % relative F-measure improvement and 35.4 % overall error rate reduction in comparison with the baseline method. 1
BibTeX
@inproceedings{chen2007improving,
  author = {Qing Chen and Mu Li and Ming Zhou},
  title = {{Improving Query Spelling Correction Using Web Search Results}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure