Method and apparatus for improved grammar checking using a stochastic parser

• US 7,184,950 B2
• Filed: 07/08/2005
• Issued: 02/27/2007
• Est. Priority Date: 07/12/2001
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Weise, David Neal
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): Han; Qi
• Application Number:
  US11/177,129
• Publication Number:
  US 20050246158A1
• Time in Patent Office: 599 Days
• Field of Search: 704 1- 10
• US Class Current: 704/9
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

A method and grammar checking system are provided that generate a stochastic score, or a statistical goodness measure, for each of an input string of text and one or more alternative strings of text. An alternative generator generates the alternative strings of text, and a ranking parser produces parse trees and corresponding statistical goodness measures for each of the strings. The string of text having the highest goodness measure is selected for recommendation to a user.

Claims

1. A method of grammar checking an input string of text, the method comprising:

generating alternative strings of text;

producing parse trees for the input string of text and for each of the alternative strings of text;

calculating separate parse scores for each of the parse trees generated for the input string of text and for each of the alternative strings of text, wherein calculating separate parse scores further comprises generating a statistical goodness measure for each of the parse trees by combining probabilities of each node in a particular parse tree, wherein the probabilities of each node are determined by the steps comprising;

receiving language-usage probabilities based upon appearances of instances of combinations of linguistic features within a training corpus, wherein the language-usage probabilities include predictive-parameter-and-rule probabilities and syntactic bigram probabilities; and

calculating the probabilities of each node based upon linguistic features of each node and the language-usage probabilities;

determining which one string of text, out of the input string of text and the alternative strings of text, has the highest stochastic parse score; and

selecting the one string of text which has the highest stochastic parse score.

2. The method of claim 1, wherein generating alternative strings of text further comprises generating the alternative strings of text such that each of the alternative strings of text corresponds to a different possible grammatical correction of the input string of text.

3. The method of claim 2, and further comprising recommending to a user the selected one string of text which has the highest stochastic parse score.

4. The method of claim 3, wherein if the selected one string of text is the input string of text, then recommending to the user the selected one string of text further comprises not recommending a grammar correction for the input string of text.

5. The method of claim 1, wherein the statistical goodness measure for each of the parse trees is an indicator of a likelihood that the particular parse tree represents the intended meaning of a human originating the text corresponding to the input string of text.

6. A computer-readable medium having computer-executable instructions for performing the grammar checking steps comprising:

receiving an input string of text;

generating alternative strings of text;

producing parse trees for the input string of text and for each of the alternative strings of text;

calculating separate parse scores for each of the parse trees generated for the input string of text and for each of the alternative strings of text by generating a separate statistical goodness measure for each of the strings of text using the corresponding parse tree, wherein a goodness measure of a parse for a particular parse tree is a probability of taking each transition within the particular parse tree;

determining which one string of text, out of the input string of text and the alternative strings of text, has the highest stochastic parse score; and

selecting the one string of text which has the highest stochastic parse score.

7. The computer readable medium of claim 6, wherein generating alternative strings of text further comprises generating the alternative strings of text such that each of the alternative strings of text corresponds to a different possible grammatical correction of the input string of text.

8. The computer readable medium of claim 7, and further having computer-executable instructions for performing the grammar checking step of recommending to a user the selected one string of text which has the highest stochastic parse score.

9. The computer readable medium of claim 8, wherein if the selected one string of text is the input string of text, then recommending to the user the selected one string of text further comprises not recommending a grammar correction for the input string of text.

10. The computer readable medium of claim 6, wherein the statistical goodness measure for each of the parse trees is an indicator of a likelihood that the particular parse tree represents the intended meaning of a human originating the text corresponding to the input string of text.

11. The computer readable medium of claim 10, wherein calculating the separate parse scores for each of the parse trees further comprises calculating the parse scores as functions of probabilities determined using a training corpus.

12. The computer readable medium of claim 11, wherein calculating separate parse scores further comprises generating a statistical goodness measure for each of the parse trees by combining probabilities of each node in a particular parse tree, wherein the probabilities of each node are determined by the steps comprising:

receiving language-usage probabilities based upon appearances of instances of combinations of linguistic features within the training corpus, wherein the language-usage probabilities include predictive-parameter-and-rule probabilities and syntactic bigram probabilities; and

calculating the probabilities of each node based upon linguistic features of each node and the language-usage probabilities.

13. A grammar checking system comprising:

an alternative generator configured to receive an input string of text, and in response, to generate alternative strings of text corresponding to different possible grammatical corrections of the input string of text;

a parse tree producer configured to generate parse trees for the input string of text and for each of the alternative strings of text;

a stochastic score generator configured to receive the parse trees for the input string of text and for each of the alternative strings of text and to generate separate parse scores for each of the strings of text from the corresponding parse tree by generating a separate statistical goodness measure for each of the strings of text using the corresponding parse tree, wherein a goodness measure of a parse for a particular parse tree is a probability of taking each transition within the particular parse tree; and

a string selector configured to determine which string of text, out of the input string of text and the alternative strings of text has a greatest parse score and to select the string of text having the highest parse score.

14. The grammar checking system of claim 13, wherein the statistical goodness measure for each of the parse trees is an indicator of a likelihood that the particular parse tree represents the intended meaning of a human originating the text corresponding to the input string of text.

15. The grammar checking system of claim 14, wherein the stochastic score generator is configured to generate the separate statistical goodness measure for each of the strings of text as functions of probabilities determined using a training corpus.

16. The grammar checking system of claim 15, wherein the stochastic score generator is configured to generate the separate statistical goodness measure for each of the strings of text by combining probabilities of each node in the corresponding parse tree, wherein the probabilities of each node are determined by the steps comprising:

receiving language-usage probabilities based upon appearances of instances of combinations of linguistic features within the training corpus; and

calculating the probabilities of each node based upon linguistic features of each node and the language-usage probabilities.