Learning a Spelling Error Model from Search Query Logs

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 955–962, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Learning a Spelling Error Model from Search Query Logs Farooq Ahmad Department of Electrical and Computer Engineering University of Alberta Edmonton, Canada farooq@ualberta.ca Grzegorz Kondrak Department of Computing Science University of Alberta Edmonton, Canada kondrak@cs.ualberta.ca Abstract Applying the noisy channel model to search query spelling correction requires an error model and a language model. Typically, the error model relies on a weighted string edit distance measure. The weights can be learned from pairs of misspelled words and their corrections. This paper investigates using the Expec- tation Maximization algorithm to learn edit distance weights directly from search query logs, without relying on a corpus of paired words. 1 Introduction There are several sources of error in written lan- guage. Typing errors can be divided into two groups (Kucich, 1992): typographic errors and cog- nitive errors. Typographic errors are the result of mistyped keys and can be described in terms of key- board key proximity. Cognitive errors on the other hand, are caused by a misunderstanding of the cor- rect spelling of a word. They include phonetic er- rors, in which similar sounding letter sequences are substituted for the correct sequence; and homonym errors, in which a word is substituted for another word with the same pronunciation but a different meaning. Spelling errors can also be grouped into errors that result in another valid word, such as homonym errors, versus those errors that result in a non-word. Generally non-word errors are easier to detect and correct. In addition to its traditional use in word processing, spelling correction also has ap- plications in optical character recognition and hand- writing recognition. Spelling errors in this context are caused by inaccurate character recognition. Spelling correction is a well developed research problem in the field of computational linguistics. The first dictionary based approach to spelling cor- rection (Damerau, 1964) considers all words that can not be found in a dictionary as misspellings. The correct word is found by making a single edit op- eration (insertion, deletion, or substitution) on the misspelled word and re-checking the dictionary for the inclusion of the altered version. This method works well for correcting most typos, but often mis- spelled words are off by more than one character. A method of quantifying string-to-string distance is introduced in (Wagner and Fischer, 1974), allowing the consideration of multiple edit operations when determining candidate corrections. Each edit op- eration is assigned a fixed cost. Edit operations, though, can be more accurately modelled by consid- ering every possible insertion, deletion, and substitu- tion operation individually instead of having a fixed cost for each operation. For example, the applica- tion of probabilistic models to spelling correction is explored in (Kernighan, Church, and Gale, 1990), in which a confusion matrix describes the probabil- ity of each letter being substituted for another. The Bayesian noisy channel model is used to determine the …

Content truncated to 500 words