A Large Scale Ranker-Based System for Search Query Spelling Correction

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 358–366, Beijing, August 2010 A Large Scale Ranker-Based System for Search Query Spelling Correction Jianfeng Gao Microsoft Research, Redmond jfgao@microsoft.com Xiaolong Li Microsoft Corporation xiaolong.li@microsoft.com Daniel Micol Microsoft Corporation danielmi@microsoft.com Chris Quirk Microsoft Research, Redmond chrisq@microsoft.com Xu Sun University of Tokyo xusun@mist.i.u-tokyo.ac.jp Abstract This paper makes three significant extensions to a noisy channel speller designed for standard writ- ten text to target the challenging domain of search queries. First, the noisy channel model is sub- sumed by a more general ranker, which allows a variety of features to be easily incorporated. Se- cond, a distributed infrastructure is proposed for training and applying Web scale n-gram language models. Third, a new phrase-based error model is presented. This model places a probability distri- bution over transformations between multi-word phrases, and is estimated using large amounts of query-correction pairs derived from search logs. Experiments show that each of these extensions leads to significant improvements over the state- of-the-art baseline methods. 1 Introduction Search queries present a particular challenge for traditional spelling correction methods. New search queries emerge constantly. As a result, many queries contain valid search terms, such as proper nouns and names, which are not well es- tablished in the language. Therefore, recent re- search has focused on the use of Web corpora and search logs, rather than human-compiled lex- icons, to infer knowledge about spellings and word usages in search queries (e.g., Whitelaw et al., 2009; Cucerzan and Brill, 2004). The spelling correction problem is typically formulated under the framework of the noisy channel model. Given an input query , we want to find the best spelling correc- tion among all candidates: (1) Applying Bayes' Rule, we have (2) where the error model models the trans- formation probability from C to Q, and the lan- guage model (LM) models the likelihood that C is a correctly spelled query. This paper extends a noisy channel speller de- signed for regular text to search queries in three ways: using a ranker (Section 3), using Web scale LMs (Section 4), and using phrase-based error models (Section 5). First of all, we propose a ranker-based speller that covers the noisy channel model as a special case. Given an input query, the system first gen- erates a short list of candidate corrections using the noisy channel model. Then a feature vector is computed for each query and candidate correc- tion pair. Finally, a ranker maps the feature vec- tor to a real-valued score, indicating the likeli- hood that this candidate is a desirable correction. We will demonstrate that ranking provides a flex- ible modeling framework for incorporating a wide variety of features that would be difficult to model under the noisy channel framework. Second, we explore the use of Web scale LMs for query spelling correction. While traditional LM research focuses on how to make the model “smarter” via how to better estimate the probabil- ity of unseen words (Chen and Goodman, 1999); and …

Content truncated to 500 words