AUTOMATED ERROR CHECKING SYSTEM AND METHOD

• US 20070016616A1
• Filed: 09/20/2006
• Published: 01/18/2007
• Est. Priority Date: 06/27/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rounthwaite, Robert, Brill, Eric
• Granted Patent: US 7,660,806 B2
• Time in Patent Office: Days
• 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. An 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 (N being an integer);

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;

a trained model derived from learning processes of an error model that computes probabilities or estimates for a given (X,Y) pair describing how likely X is an incorrect expression of Y, 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; and

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.

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 at least one probability threshold that is configured to determine whether estimated data correlates to sampled data.

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

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

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

9. An 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;

computing probabilities or estimates for a given (X,Y) pair describing how likely X is an incorrect expression of Y;

sampling a data log to determine if estimates of a trained model correlate to actual data appearing in the data log; and

removing one or more X expressions from the data log to automatically form a filtered database composed of probabilistically determined expressions of Y.

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

11. The method of claim 9, 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.

12. The method of claim 9, 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.

13. The method of claim 9, 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.

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

wrong”

is a misspelling of “

right”

.

15. The method of claim 9, 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.

16. The method of claim 9, 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.

17. The method of claim 9, 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.

18. The method of claim 9, 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.

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

20. An automated error checking system, comprising:

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

means for computing probabilities or estimates for a given (X,Y) pair describing how likely X is an incorrect expression of Y;

means for sampling a data log to determine if estimates of a trained model correlate to actual data appearing in the data log; and

means for removing one or more X expressions from the data log to automatically form a filtered database composed of probabilistically determined expressions of Y; and

means for configuring a probability threshold to determine whether estimated data correlates to sampled data.