Statistical Machine Translation Based Search Query Spelling Correction

• US 20130124492A1
• Filed: 11/15/2011
• Published: 05/16/2013
• Est. Priority Date: 11/15/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gao, Jianfeng, Huang, Xuedong D., Quirk, Christopher Brian, Wang, Zhenghao, Hwang, Mei-Yuh
• Granted Patent: US 10,176,168 B2
• Time in Patent Office: Days
• US Class Current: 707/706
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

Statistical Machine Translation (SMT) based search query spelling correction techniques are described herein. In one or more implementations, search data regarding searches performed by clients may be logged. The logged data includes query correction pairs that may be used to ascertain error patterns indicating how misspelled substrings may be translated to corrected substrings. The error patterns may be used to determine suggestions for an input query and to develop query correction models used to translate the input query to a corrected query. In one or more implementations, probabilistic features from multiple query correction models are combined to score different correction candidates. One or more top scoring correction candidates may then be exposed as suggestions for selection by a user and/or provided to a search engine to conduct a corresponding search using the corrected query version(s).

Claims

1. A method implemented by one or more computing devices, the method comprising:

logging search data regarding searches performed by clients;

ascertaining error patterns based on query correction pairs described by the logged search data;

developing query correction models based at least in part upon the ascertained error patterns; and

translating an input search query to a corrected search query using the query correction models.

2. A method as described in claim 1, wherein developing the query correction models comprises creating a translation model configured to encode spelling error patterns and translation probabilities indicated by the logged search data.

3. A method as described in claim 1, wherein developing the query correction models comprises creating one or more language models using correctly spelled queries from the logged search data.

4. A method as described in claim 3, wherein the one or more language models include a word-based language model configured to encode probabilities for a next word in a sequence given preceding words in the sequence.

5. A method as described in claim 4, wherein one or more language models include a character-based language model configured to encode probabilities for a next character in a sequence given preceding characters in the sequence.

6. A method as described in claim 1, wherein translating the input search query comprises ranking query candidates according to a weighted log-linear model that combines multiple features including at least some features derived from the query correction models.

7. A method as described in claim 6, wherein the log-linear model has the form of:

8. A method as described in claim 6, wherein the multiple features include:

one or more translation probabilities encoded in a translation model as indicated by the logged search data through character alignment of misspelled character strings with corrections of the misspelled character strings;

probabilities encoded in a word-based language model for a next word in a word sequence given preceding words in the word sequence; and

probabilities encoded in a character-based language model for a next character in a character sequence given preceding characters in the character sequence.

9. One or more computer-readable storage media storing instructions that, when executed via the one or more processors, implement a correction module to perform operations comprising:

parsing an input search query to obtain individual search terms;

generating query candidates corresponding to the input query using error patterns to find potential spelling corrections for the search terms;

ranking the query candidates one to another in accordance with one or more query correction models developed based on the error patterns;

picking one or more of the query candidates as suggestions according to the ranking; and

outputting the query candidates that are picked as suggestions for selection by a user.

10. One or more computer-readable storage media as described in claim 9, wherein the generating and ranking comprise using a left-to right beam search decoder configured to search for corrections for the input search query according to the one or more query correction models.

11. One or more computer-readable storage media as described in claim 9, wherein ranking the query candidates one to another comprises computing a score for each of the query candidates using a log-linear model that combines multiple features including at least some features derived from the one or more query correction models.

12. One or more computer-readable storage media as described in claim 11, wherein the multiple features include features derived from a translation model and one or more language models encompassed by the query correction models.

13. One or more computer-readable storage media as described in claim 11, wherein the multiple features include one or more features based upon character and word properties corresponding to the query candidates.

14. One or more computer-readable storage media as described in claim 9, wherein generating the query candidates comprises producing a list of the query candidates by translating substrings of the search terms to form the spelling corrections of the search terms by matching the substrings to the error patterns.

15. One or more computer-readable storage media as described in claim 9, wherein the error patterns are applied to derive the query candidates in lieu of using a pre-defined dictionary for at least some of the search terms.

16. A system comprising:

one or more processors;

one or more computer-readable storage media storing instructions that, when executed via the one or more processors, implement a correction module to perform operations to translate an input search query to a corrected query including;

receiving the input search query;

deriving candidates for the corrected query based on the input search query;

for each candidate that is derived, computing a score for the candidate as a weighted combination of multiples features including at least;

translation probabilities defined by a translation model according to character alignment of misspelled character strings with corrections of the misspelled character strings indicated by logged search data;

probabilities for a next word in a word sequence given a designated number of preceding words in the word sequence encoded in a word-based language model; and

probabilities for a next character in a character sequence given a designated number of preceding characters in the character sequence encoded in a character-based language model; and

designating one of the candidates as the corrected query based on a comparison of the computed scores one to another.

17. The system as described in claim 16, wherein:

the word-based language model is a trigram model for which the number of preceding words is designated as two; and

the character-based language model is a nine-gram model for which the number of preceding characters is designated as eight; and

18. The system as described in claim 16, wherein the multiple features combined to score the candidates further comprises one or more of character length, length in words, number of character-level translations, or number of word-level translations.

19. The system as described in claim 16, wherein the translation model and languages models are derived based upon a log of query correction pairs determined from user selections of suggested query corrections.

20. The system as described in claim 16, wherein the correction module is provided as a component of a web search engine.