TL;DR
This paper tackles the challenge of spelling correction in search queries, which often contain non-dictionary words and are not grammatically complete. The authors propose a novel method to learn a weighted spelling error model directly from search query logs using the Expectation Maximization (EM) algorithm, bypassing the need for manually curated datasets of misspelled-correct word pairs. This approach allows for more accurate spelling correction in the dynamic and evolving landscape of web search.
What Problem Does This Paper Address?
Traditional spelling correction methods often rely on dictionaries and fixed edit distance costs. However, these approaches struggle with the unique characteristics of search queries. Search queries frequently include new words, proper names, product names, and even intentionally misspelled terms that aren't in standard dictionaries. Furthermore, search queries are typically short phrases rather than full sentences, making grammar-based approaches less effective. Existing methods that use weighted edit distances often require a corpus of known misspelled-correct word pairs, which can be difficult and expensive to obtain and maintain, especially for rapidly evolving online language. This paper addresses the need for a robust spelling error model that can be learned automatically from readily available search query logs.
Methods
The core of this paper is the application of the Expectation Maximization (EM) algorithm to learn a weighted spelling error model. This is framed within the noisy channel model for spelling correction, where a misspelled word ($v$) is considered a corrupted version of a correct word ($w$). The probability of a correction is given by $P(w|v) \propto P(v|w)P(w)$, where $P(v|w)$ is the error model and $P(w)$ is the language model.
Instead of using a fixed cost for edit operations (like insertion, deletion, substitution), the authors learn weighted edit distance probabilities. This is achieved by:
- Language Model: A unigram language model is built by tokenizing the search query logs and calculating the frequency of each token.
- Error Model Learning (EM Algorithm):
- Initialization: The edit distance table is initialized with high probabilities for correct character matches and lower, equally distributed probabilities for substitutions and deletions.
- E-Step (Expectation): For each query token, potential corrections are identified within a threshold of unweighted edit distance (K=3), and then a tighter threshold of weighted edit distance (T). The probability of each candidate correction being the intended word is calculated using the current error and language models.
- M-Step (Maximization): The edit frequencies are updated based on the probabilities calculated in the E-step. These frequencies are then used to re-estimate the edit probabilities, iteratively refining the error model.
- Relationship to Edit Distance: The learned edit probabilities are related to edit distances via the formula $ED(e) = -\log[P(e)]$, allowing the calculation of string-to-string edit probabilities.
Datasets
- Training Data: Approximately 580,000 search queries were extracted from the metaspy website over a five-day period in March 2005. This data was used to train both the language model and the error model via the EM algorithm.
- Evaluation Data: A test dataset of 547 misspelled words, paired with their best human-identified corrections, was used. Compound words were removed, leaving 508 misspellings. This dataset is described as being comprised of misspelled dictionary words.
Key Insights and Ideas
- Learning from Query Logs is Feasible: The paper demonstrates that valuable spelling error models can be learned directly from raw search query logs, without requiring curated datasets of misspelled-correct word pairs. This is a significant advantage for adapting to evolving language.
- EM for Weighted Edit Distance: The EM algorithm provides a principled way to learn the probabilities of individual edit operations, leading to a more nuanced error model than fixed-cost edit distances.
- Vowel-to-Vowel Substitutions are Common: The learned error model shows a strong tendency for vowels to be substituted for other vowels, suggesting cognitive or phonetic similarities play a role.
- Keyboard Proximity and Phonetic Similarity Matter: The learned probabilities also reflect common keyboard layouts (e.g., 'd' for 's') and phonetic similarities (e.g., 'c' for 'k' or 's').
- Pluralization is a Challenge: The high probability of 's' insertion is attributed to the common occurrence of both singular and plural forms in search queries, which can confuse the model.
Key Results
- The learned error model's edit probabilities were found to be similar to those derived from other methods.
- When tested on a dataset of misspelled dictionary words, the proposed EMBED system (using the learned error model and a simple word list as a language model) performed competitively with established spell checkers like Ispell and Aspell.
- EMBED performed better than Ispell for the top recommended correction.
- Aspell, which uses a phonetic algorithm, generally performed better, especially for misspellings with larger edit distances. However, Aspell's approach requires a manually derived pronunciation model.
Limitations and Future Work
- Corpus Size: While 580,000 queries were used, the authors suggest that increasing the corpus size could further improve accuracy, especially by including more correctly spelled words that might not have misspelled versions in the logs.
- Language Model: The current language model is unigram. The paper acknowledges that using n-gram language models (bigrams, trigrams) could provide context-sensitive spelling correction and significantly improve performance, especially for longer queries.
- Edit Operations: The current model primarily focuses on single-character edits. The authors note that many typos involve letter transpositions (e.g., "teh" for "the"), and suggest exploring more general models that can handle many-to-one and one-to-many character substitutions, as well as pronunciation modeling for improved performance.
- Handling New Words: The approach can handle continuously evolving vocabularies, which is a key advantage for web search.
- Cross-Lingual Application: The EM-based approach is noted as being learnable from unlabeled corpora and applicable to other languages without modification.
Summary updated