Automated error checking system and method

• US 20040002994A1
• Filed: 06/27/2002
• Published: 01/01/2004
• Est. Priority Date: 06/27/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rounthwaite, Robert L., Brill, Eric D.
• Granted Patent: US 7,113,950 B2
• Time in Patent Office: Days
• US Class Current: 707/104.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. An error checking database, comprising:

a data subset derived in part from past user input data; and

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.

2. The system of claim 1, the data subset is captured in a data log that records the past user input data from I to N users via at least one of a network and a local data source, N being an integer.

3. 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.

4. The system of claim 3, 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.

5. 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.

6. The system of claim 1, further comprising an automated mining component to determine I to M (X,Y) pairs of potential correct and incorrect expressions, wherein X is likely to be an incorrect formulation of Y and M is an integer.

7. The system of claim 6, the (X,Y) pairs are selected in part base upon a predetermined frequency threshold (FT), FT describes a frequency of occurrence of at least one of the X and Y expressions.

8. The system of claim 7, further comprising a right/wrong list denoted as (W,R), that is automatically created by the mining component 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.

9. The system of claim 8, further comprising 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.

10. The system of claim 9, 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.

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

12. The system of claim 11, 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.

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

14. 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.

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

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

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

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

19. An automated error checking method, comprising:

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

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

20. The method of claim 19, further comprising comparing the error checking database with a current query and suggesting a corrective expression to the current query from the database. MS 192077.1

21. The method of claim 19, 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.

22. The method of claim 21, further comprising automatically mining pairs of strings X, Y wherein X is likely to be a misspelling of Y.

23. The method of claim 22, 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.

24. The method of claim 22, 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.

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

wrong”

is a misspelling of “

right”

.

26. The method of claim 22, further comprising learning a probability of different spelling errors being made.

27. The method of claim 26, 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.

28. The method of claim 22, 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.

29. The method of claim 19, 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.

30. The method of claim 19, 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.

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

32. An 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; and

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.

33. A signal to communicate error-checking data between at least two nodes, comprising:

a data packet comprising;

a filtered data component derived from an error model trained from previous user data activities; and

a query data component reflecting current user data activities.

34. The signal of claim 33, the filtered data component is transmitted as a response to the query data component to facilitate error correction of the current user data activities.

35. The signal of claim 33, the filtered component is generated from at least one of a web site, a web service, and a remote SQL server.

36. The signal of claim 33, the filtered data component is formatted in accordance with at least one of XML, SQL, HTML, WML, and an applet.

37. The signal of claim 33, at least a portion of the filtered data component is at least one of downloaded and installed on a remote system to facilitate error checking in the remote system.

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

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

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

39. The computer-readable medium of claim 38, 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.

40. The computer-readable medium of claim 38, 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.

41. The computer-readable medium of claim 38, 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.

42. A 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; and

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.

43. The method of claim 42, further comprising:

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 string x and string y from the dictionary;

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

leaving string x and string y in the dictionary;

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

leaving string x and string y in the dictionary and having string x point to string y and string y point to string z.

44. The method of claim 43, further comprising at least one of:

inputting a string s;

checking if the string s is in the dictionary;

determining if the string s is in the dictionary then;

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

if the 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.

45. The method of claim 44, further comprising at least one of the following:

determining that the string s is not in the dictionary;

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

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

if 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.