Learning Phrase-Based Spelling Error Models from Clickthrough Data

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 266–274, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Learning Phrase-Based Spelling Error Models from Clickthrough Data Xu Sun∗ Dept. of Mathematical Informatics University of Tokyo, Tokyo, Japan xusun@mist.i.u-tokyo.ac.jp Jianfeng Gao Microsoft Research Redmond, WA, USA jfgao@microsoft.com Daniel Micol Microsoft Corporation Munich, Germany danielmi@microsoft.com Chris Quirk Microsoft Research Redmond, WA, USA chrisq@microsoft.com ∗ The work was done when Xu Sun was visiting Microsoft Research Redmond. Abstract This paper explores the use of clickthrough data for query spelling correction. First, large amounts of query-correction pairs are derived by analyzing users' query reformulation behavior encoded in the clickthrough data. Then, a phrase-based error model that accounts for the transformation probability between multi-term phrases is trained and integrated into a query speller system. Expe- riments are carried out on a human-labeled data set. Results show that the system using the phrase-based error model outperforms signifi- cantly its baseline systems. 1 Introduction Search queries present a particular challenge for traditional spelling correction methods for three main reasons (Ahmad and Kondrak, 2004). First, spelling errors are more common in search queries than in regular written text: roughly 10-15% of queries contain misspelled terms (Cucerzan and Brill, 2004). Second, most search queries consist of a few key words rather than grammatical sen- tences, making a grammar-based approach inap- propriate. Most importantly, many queries con- tain search terms, such as proper nouns and names, which are not well established in the language. For example, Chen et al. (2007) reported that 16.5% of valid search terms do not occur in their 200K-entry spelling lexicon. Therefore, recent research has focused on the use of Web corpora and query logs, rather than human-compiled lexicons, to infer knowledge about misspellings and word usage in search queries (e.g., Whitelaw et al., 2009). Another important data source that would be useful for this purpose is clickthrough data. Although it is well-known that clickthrough data contain rich information about users' search behavior, e.g., how a user (re-) formulates a query in order to find the relevant document, there has been little research on exploiting the data for the develop- ment of a query speller system. In this paper we present a novel method of extracting large amounts of query-correction pairs from the clickthrough data. These pairs, impli- citly judged by millions of users, are used to train a set of spelling error models. Among these models, the most effective one is a phrase-based error model that captures the probability of transforming one multi-term phrase into another multi-term phrase. Comparing to traditional error models that account for transformation probabili- ties between single characters (Kernighan et al., 1990) or sub-word strings (Brill and Moore, 2000), the phrase-based model is more powerful in that it captures some contextual information by retaining inter-term dependencies. We show that this information is crucial to detect the correction of a query term, because unlike in regular written text, any query word can be a valid search …

Content truncated to 500 words