A generalized hidden Markov model with discriminative training for query spelling correction

Yanen Li, Huizhong Duan, Chengxiang Zhai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Query spelling correction is a crucial component of modern search engines. Existing methods in the literature for search query spelling correction have two major drawbacks. First, they are unable to handle certain important types of spelling errors, such as concatenation and splitting. Second, they cannot efficiently evaluate all the candidate corrections due to the complex form of their scoring functions, and a heuristic filtering step must be applied to select a working set of top-K most promising candidates for final scoring, leading to non-optimal predictions. In this paper we address both limitations and propose a novel generalized Hidden Markov Model with discriminative training that can not only handle all the major types of spelling errors, including splitting and concatenation errors, in a single unified framework, but also efficiently evaluate all the candidate corrections to ensure the finding of a globally optimal correction. Experiments on two query spelling correction datasets demonstrate that the proposed generalized HMM is effective for correcting multiple types of spelling errors. The results also show that it significantly outperforms the current approach for generating top-K candidate corrections, making it a better first-stage filter to enable any other complex spelling correction algorithm to have access to a better working set of candidate corrections as well as to cover splitting and concatenation errors, which no existing method in academic literature can correct.

Original languageEnglish (US)
Title of host publicationSIGIR'12 - Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval
Pages611-620
Number of pages10
DOIs
StatePublished - 2012
Event35th Annual ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2012 - Portland, OR, United States
Duration: Aug 12 2012Aug 16 2012

Publication series

NameSIGIR'12 - Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval

Other

Other35th Annual ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2012
CountryUnited States
CityPortland, OR
Period8/12/128/16/12

Keywords

  • discriminative training for HMMS
  • generalized hidden Markov models
  • query spelling correction

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'A generalized hidden Markov model with discriminative training for query spelling correction'. Together they form a unique fingerprint.

Cite this