A Discriminative Model for Query Spelling Correction with Latent Structural SVM

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1511–1521, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics A Discriminative Model for Query Spelling Correction with Latent Structural SVM Huizhong Duan, Yanen Li, ChengXiang Zhai and Dan Roth University of Illinois at Urbana-Champaign 201 N Goodwin Ave Urbana, IL 61801 {duan9, yanenli2, czhai, danr}@illinois.edu Abstract Discriminative training in query spelling cor- rection is difficult due to the complex inter- nal structures of the data. Recent work on query spelling correction suggests a two stage approach a noisy channel model that is used to retrieve a number of candidate corrections, followed by discriminatively trained ranker applied to these candidates. The ranker, how- ever, suffers from the fact the low recall of the first, suboptimal, search stage. This paper proposes to directly optimize the search stage with a discriminative model based on latent structural SVM. In this model, we treat query spelling correction as a multi- class classification problem with structured in- put and output. The latent structural informa- tion is used to model the alignment of words in the spelling correction process. Experiment results show that as a standalone speller, our model outperforms all the baseline systems. It also attains a higher recall compared with the noisy channel model, and can therefore serve as a better filtering stage when combined with a ranker. 1 Introduction Query spelling correction has become a crucial com- ponent in modern information systems. Particularly, search engine users rely heavily on the query cor- rection mechanism to formulate effective queries. Given a user query q, which is potentially mis- spelled, the goal of query spelling correction is to find a correction of the query c that could lead to a better search experience. A typical query spelling correction system employs a noisy channel model (Kernighan et al., 1990). The model assumes that the correct query c is formed in the user’s mind be- fore entering the noisy channels, e.g., typing, and get misspelled. Formally, the model maximizes the posterior probability p(c|q): ˆc = arg max c p(c|q). (1) Applying Bayes rule, the formulation can be rewritten as: ˆc = arg max c p(q|c)p(c) = arg max c [log p(q|c) + log p(c)]. (2) The model uses two probabilities. The prior prob- ability p(c) represents how likely it is that c is the original correct query in the user’s mind. The prob- ability is usually modeled by a language model es- timated from a sizable corpus. The transformation probability p(q|c) measures how likely it is that q is the output given that c has been formed by the user. This probability can be either heuristic-based (edit distance) or learned from samples of well aligned corrections. One problem with the noisy channel model is that there is no weighting for the two kinds of probabilities, and since they are estimated from different sources, there are usually issues regarding their scale and comparability, resulting in subopti- mal …

Content truncated to 500 words