Automated error checking system and method

• US 7,113,950 B2
• Filed: 06/27/2002
• Issued: 09/26/2006
• Est. Priority Date: 06/27/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rounthwaite, Robert L., Brill, Eric D.
• Primary Examiner(s): Cottingham, John R.
• Assistant Examiner(s): Lu, Kuen S.
• Application Number:
  US10/183,214
• Publication Number:
  US 20040002994A1
• Time in Patent Office: 1,552 Days
• Field of Search: 707/2, 707/102, 707/6, 707/100, 707/7, 705/7
• US Class Current: 1/1
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

The present invention relates to a system and methodology to facilitate automated error correction of user input data via an analysis of the input data in accordance with an automatically generated and filtered database of processed structural groupings or formulations selected and filtered from past user activities. The filtered database provides a relevant foundation of potential phrases, topics, symbols, speech and/or colloquial structures of interest to users—which are automatically determined from previous user activity, and employed to facilitate automated error checking in accordance with the user'"'"'s current input, command and/or request for information.

Claims

1. A computer implemented error checking database, comprising:

a data subset derived in part from past user input data, the data subset is captured in a data log that records the past user input data from 1 to N users via at least one of a network and a local data source, N being a natural number;

a subset of expressions automatically filtered from the data subset, the subset of expressions employed as a reference to facilitate error checking in accordance with current user input data;

an automated mining component to determine 1 to M (X,Y) pairs of potential correct and incorrect expressions,

wherein X is expected to be an incorrect formulation of Y and M a natural number, the (X,Y) pairs are selected in part based upon a predetermined frequency threshold (F_T),

F_T describes a frequency of occurrence of at least one of the X and Y expressions, the automated mining component creates a right/wrong list denoted as (W,R) to describe hypothetical pairings of expressions such that W describes a potential incorrect expression and R describes a potential correct expression that has been associated with the W expression; and

an error model that is formulated from the right/wrong list of expressions such that the error model learns probabilities for different types of expression errors.

2. The system of claim 1, at least one of the past user input data and the current user input data includes an expression comprising at least one of a text input directing a query, an audio input derived from speech expressions, and a visual input capturing at least one of facial, symbolic, and bodily expressions.

3. The system of claim 2, at least one of the past user input data and the current user input data is directed to an application including at least one of a spell checker, a word processor, a browser, a language processor, an image processor, an audio processor, a search engine, a web service, a web site, an interface, and a multimedia application, the subset of expressions employed to facilitate error checking in accordance with the application.

4. The system of claim 1, the subset of expressions relate to at least one of topics, phrases, ideas, images, sounds, and queries of interest that have been directed from at least one user.

5. The system of claim 1, further comprising a trained model derived from learning processes of the error model that computes probabilities or estimates for a given (X,Y) pair describing how likely X is an incorrect expression of Y.

6. The system of claim 5, the trained model is employed to sample data log to determine if estimates of the trained model correlate to actual data appearing in the data log.

7. The system of claim 6, further comprising a database that is created by removing one or more X expressions from the data log to automatically form a filtered database composed of probabilistically determined expressions of Y.

8. The system of claim 6, further comprising at least one probability threshold that is configured to determine whether estimated data correlates to sampled data.

9. The system of claim 1, the subset of expressions are employed to automatically suggest at least one alternative query formulation in response to a user'"'"'s current query formulation.

10. The system of claim 1, the subset of expressions are periodically updated with current expressions.

11. The system of claim 1, the subset of expressions are iteratively processed at least one time to further refine the subset of expressions.

12. The system of claim 1, the subset of expressions are determined in part by chaining at least two intermediate expressions.

13. A computer-readable medium having computer-executable instructions stored thereon to perform data processing in accordance with claim 1.

14. A computer implemented automated error checking method, comprising:

modeling past user input data relating to at least one query;

automatically creating an error checking database by filtering the past user input data in accordance with the modeling;

automatically mining 1 to M (X,Y) pairs of potential correct and incorrect expressions,

wherein X is expected to be an incorrect formulation of Y and M is a natural number, the (X,Y) pairs are selected in part based upon a predetermined frequency threshold (F_T),

F_T describes a frequency of occurrence of at least one of the X and Y expressions;

creating a right/wrong list denoted as (W,R) to describe hypothetical pairings of expressions such that W describes a potential incorrect expression and R describes a potential correct expression that has been associated with the W expression; and

formulating from the right/wrong list of expressions such that probabilities for different types of expression errors can be learned.

15. The method of claim 14, further comprising comparing the error checking database with a current query and suggesting a corrective expression to the current query from the database.

16. The method of claim 14, further comprising at least one of:

processing a log of strings users have entered; and

generating a noisy list of strings by determining a frequency of occurrence of the strings.

17. The method of claim 14, further comprising estimating how likely it is that X is a misspelling of Y, by at least one of an edit distance between X and Y, a length of X and Y, and a relative frequency of X as compared to Y.

18. The method of claim 14, further comprising estimating at least one of bit-map differences, color differences, shape differences, intensity differences, gradients, tonal differences, inflection differences, phoneme differences, and phrasal differences.

19. The method of claim 14, further comprising automatically deriving a list of hypothesized (wrong, right) strings, wherein “

wrong”

is a misspelling of “

right”

.

20. The method of claim 14, further comprising determining for a given pair of strings X, Y, how likely X is a misspelling of Y by sampling unprocessed query logs to determine if modeled estimates are consistent with the logs.

21. The method of claim 14, further comprising processing an error chain having at least one other variable Z to determine if X is a misspelling of Y, and Y is a misspelling of Z, then it can be hypothesized/determined that both X and Y are misspellings of Z.

22. The method of claim 14, the modeling includes adapting at least one of a Support Vector Machine (SVM), a Naive Bayes, a Bayes Net, a decision tree, a similarity-based, a vector-based, and a Hidden Markov Models to perform the modeling.

23. The method of claim 14, the modeling includes adapting at least one function to determine at least one of a transposition error in a data set, a likelihood of letters being added, a likelihood of letters being deleted, a likelihood of words being at least one of dropped, added, transposed, inserted, and mis-entered.

24. The method of claim 14, further comprising iteratively processing the error checking database in order to refine associated contents therein.

25. A computer implemented automated error checking system, comprising:

means for at least one of accessing and processing past user input data;

means for modeling the past user input data;

means for determining current user input data;

means for providing at least one error suggestion in response to the current user input data based at least in part on the modeling of the past user input data;

means for automatically mining 1 to M (X,Y) pairs of potential correct and incorrect expressions,

wherein X is expected to be an incorrect formulation of Y and M is a natural number,

the (X,Y) pairs are selected in part based upon a predetermined frequency threshold (F_T),

F_T describes a frequency of occurrence of at least one of the X and Y expressions;

means for creating a right/wrong list denoted as (W,R) to describe hypothetical pairings of expressions such that W describes a potential incorrect expression and R describes a potential correct expression that has been associated with the W expression; and

means for formulating an error model from the right/wrong list of expressions such that the error model learns probabilities for different types of expression errors.

26. A computer-readable medium having stored thereon a data structure, comprising:

a first data field containing application data associated with a user interface;

a second data field containing error correction data derived from an error model that is trained in accordance with previous user inputs;

a third data field containing an automated mining component to determine 1 to M (X,Y) pairs of potential correct and incorrect expressions,

wherein X is expected to be an incorrect formulation of Y and M is a natural number,

the (X,Y) pairs are selected in part based upon a predetermined frequency threshold (F_T),

F_T describes a frequency of occurrence of at least one of the X and Y expressions,

the automated mining component creates a right/wrong list denoted as (W,R) to describe hypothetical pairings of expressions such that W describes a potential incorrect expression and R describes a potential correct expression that has been associated with the W expression; and

a fourth data field containing an error model that is formulated from the right/wrong list of expressions such that the error model learns probabilities for different types of expression errors.

27. The computer-readable medium of claim 26, the user interface further comprising at least one of an input location to receive present user inputs and an output location to provide suggestions in accordance with the error correction data.

28. The computer-readable medium of claim 26, the application includes at least one of a language processor, a word processor, a natural language processor, a search engine, an encyclopedia, a reference manual, a dictionary, an image processor, a speech recognition application, a browser, a GUI'"'"'s, a web page, a web service, a network interface, a menu, a help utility and a multimedia application.

29. The computer-readable medium of claim 26, the error correction data is tailored in accordance with at least one of a closed environment, an open environment, a user, and a subset of users.

30. A computer implemented method to automatically create a dictionary, comprising:

creating a dictionary having a structure wherein at least one correct string is marked as correct and at least one incorrect string is marked as incorrect, the correct and incorrect strings employable in a chain;

determining a subsequent string that points to at least one of another incorrect string in the chain and to another correct string at an end of the chain to facilitate error checking in accordance with the dictionary; and

determining that a string x is an error of string y and string y is an error of string z and if string z is correct, then performing at least one of the following;

pruning determined string x and determined string y from the dictionary;

maintaining pruned string x and pruned string y in the dictionary, but marking the pruned strings as errors;

maintaining pruned string x and pruned string y in the dictionary;

causing both maintained string x and maintained string y to point to determined string z; and

maintaining pruned string x and pruned string y in the dictionary and having pruned string x point to pruned string y and pruned string y point to determined string z.

31. The method of claim 30, further comprising at least one of:

inputting a string s;

checking if the input string s is in the dictionary;

determining if the checked string s is in the dictionary then;

if the checked string s is marked as a correct string, do nothing;

if the checked string s is marked as an incorrect string, return the correct string by at least one of;

following a chain to a termination point; and

proceeding to the correct string.

32. The method of claim 31, further comprising at least one of the following:

determining that the checked string s is not in the dictionary;

finding a closest string t in the dictionary according to an error model;

if the closest string t is marked as a correct string, then returning t;

if the closest string t is marked as incorrect, returning the correct string by at least one of;

following a chain to a termination point; and

proceeding to the correct string.