Ranking parser for a natural language processing system

• US 6,952,666 B1
• Filed: 07/20/2000
• Issued: 10/04/2005
• Est. Priority Date: 07/20/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Weise, David N.
• Primary Examiner(s): ABEBE, DANIEL DEMELASH
• Application Number:
  US09/620,745
• Time in Patent Office: 1,902 Days
• Field of Search: 704/9, 704/10, 704/257, 704/277
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

A natural language parse ranker of a natural language processing (NLP) system employs a goodness function to rank the possible grammatically valid parses of an utterance. The goodness function generates a statistical goodness measure (SGM) for each valid parse. The parse ranker orders the parses based upon their SGM values. It presents the parse with the greatest SGM values as the one that most likely represents the intended meaning of the speaker. The goodness function of this parse ranker is highly accurate in representing the intended meaning of a speaker. It also has reasonable training data requirements. With the parse ranker, the SGM of a particular parse is the combination of all of the probabilities of each node within the parse tree of such parse. The probability at a given node is the probability of taking a transition (“grammar rule”) at that point. The probability at a node is conditioned on highly predicative linguistic phenomena, such as “phrase levels,” “null transitions,” and “syntactic history”.

Claims

1. A method of determining language usage probabilities of a natural language based upon a training corpus, the method comprising:

examining a training corpus, wherein such corpus includes phrases parsed in accordance with a set of grammar rules;

computing probabilities of usage of combinations of linguistic features based upon empirical tracking of appearances of instances of such combinations in phrases within the training corpus;

wherein the combinations of linguistic features consist of;

(transition, headword, phrase level, syntactic history, segtype);

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword);

or

(transition, headword).

2. A computer-readable storage medium having computer-executable instructions that, when executed by a computer, performs the method as recited in claim 1.

3. A method of determining language usage probabilities of a natural language based upon a training corpus, the method comprising:

examining a training corpus, wherein such corpus includes phrases parsed in accordance with a set of grammar rules;

computing probabilities of usage of combinations of linguistic features based upon empirical tracking of appearances of instances of such combinations in phrases within the training corpus;

wherein the combinations of linguistic features comprises;

(transition, headword, phrase level, syntactic history, segtype);

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword); and

(transition, headword).

4. A method for determining a probability at a node in a parse tree, the method comprising:

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

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

wherein the combinations of linguistic features consist of;

(transition, headword, phrase level, syntactic history, segtype);

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword);

or

(transition, headword).

5. A computer-readable storage medium having computer-executable instructions that, when executed by a computer, performs the method as recited in claim 4.

6. A method for determining a probability at a node in a parse tree, the method comprising:

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

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

wherein the combinations of linguistic features comprises;

(transition, headword, phrase level, syntactic history, segtype);

s

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword); and

(transition, headword).

7. A method for determining a probability at a node in a parse tree, the method comprising:

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

calculating the probability at the node based upon linguistic features of the node and the language-usage probabilities, wherein the calculating comprises using PredParamRule Probability formula to calculate the probability at the node.

8. A method for determining a probability at a node in a parse tree, the method comprising:

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

calculating the probability at the node based upon linguistic features of the node and the language-usage probabilities, wherein the calculating comprises using both PredParamRule Probability and SynBigram Probability formulas to calculate the probability at the node.

9. A method for determining a statistical goodness measure (SGM) of a parse tree representing a parse of a phrase, the parse tree comprising one or more nodes, the method comprising:

combining probabilities of each node in the 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;

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

wherein the combinations of linguistic features comprises;

(transition, headword, phrase level, syntactic history, segtype);

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword); and

(transition, headword).

10. A computer-readable storage medium having computer-executable instructions that, when executed by a computer, performs the method as recited in claim 9.

11. A method for determining a statistical goodness measure (SGM) of a parse tree representing a parse of a phrase, the parse tree comprising one or more nodes, the method comprising:

combining probabilities of each node in the 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;

calculating the probabilities of each node based upon linguistic features of each node and the language-usage probabilities, wherein the calculating comprises using PredParamRule Probability formula to calculate the probability at the node.

12. A method for determining a statistical goodness measure (SGM) of a parse tree representing a parse of a phrase, the parse tree comprising one or more nodes, the method comprising:

combining probabilities of each node in the 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;

calculating the probabilities of each node based upon linguistic features of each node and the language-usage probabilities, wherein the calculating comprises using both PredParamRule Probability and SynBigram Probability formulas to calculate the probability at the node.

13. A method for determining statistical goodness measures (SGMs) of multiple parse trees, each tree representing a syntactically valid parse of a phrase, the method comprising determining a SGM of each parse tree a method comprising:

combining probabilities of each node in the 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;

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

14. A method for ranking multiple parse trees, each tree representing a syntactically valid parse of a phrase, the method comprising:

determining statistical goodness measures (SGMs) of each parse tree by a statistical goodness measure (SGM) method to get an SGM values associated with each tree;

organizing the trees in order of each tree'"'"'s associated SGM value;

the SGM method comprising;

combining probabilities of each node in the 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;

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

15. A method of parsing a phrase to facilitate processing of such phrase by a computer, the method comprising:

generating at least one parse tree representing a syntactically valid parse of the phrase, wherein the parse tree has hierarchical nodes;

dividing each node into one or more hierarchical phrase levels, wherein the phrase levels at a node represent a set of possible transitions from such node that are allowed by a set of grammar rules.

16. A method as recited in claim 15, wherein the set of possible transitions from each node consists of all possible transitions from such node that are allowed by a set of grammar rules.

17. A method as recited in claim 15, wherein the set of possible transitions from each node includes a null transition representing an application of none of the grammar rules.

18. A computer-readable storage medium having computer-executable instructions that, when executed by a computer, performs the method as recited in claim 15.

19. A computer-readable storage medium having computer-executable instructions that, when executed by a computer, perform a method to rank multiple parse trees, each tree representing a syntactically valid parse of a phrase, the method comprising:

generating at least one parse tree representing a syntactically valid parse of the phrase, wherein the parse tree has hierarchical nodes;

dividing each node into one or more hierarchical phrase levels, wherein the phrase levels at a node represent a set of possible transitions from such node that are allowed by a set of grammar rules.

20. An apparatus comprising:

a processor;

a natural-language-usage probability determiner executable on the processor to;

examine a training corpus, wherein such corpus includes phrases parsed in accordance with a set of grammar rules;

compute probabilities of usage of combinations of linguistic features based upon empirical tracking of appearances of instances of such combinations in phrases within the training corpus;

wherein the combinations of linguistic features consist of;

(transition, headword, phrase level, syntactic history, segtype);

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword);

or

(transition, headword).

21. An apparatus comprising:

a processor;

a natural-language-usage probability determiner executable on the processor to;

examine a training corpus, wherein such corpus includes phrases parsed in accordance with a set of grammar rules;

compute probabilities of usage of combinations of linguistic features based upon empirical tracking of appearances of instances of such combinations in phrases within the training corpus;

wherein the combinations of linguistic features comprises;

(transition, headword, phrase level, syntactic history, segtype);

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword); and

(transition, headword).

22. An apparatus comprising:

a processor;

a natural-language-usage probability determiner executable on the processor to;

receive language-usage probabilities based upon appearances of instances of combinations of linguistic features within a training corpus;

calculate a probability at a node in a parse tree based upon linguistic features of the node and the language-usage probabilities;

wherein the combinations of linguistic features consist of;

(transition, headword, phrase level, syntactic history, segtype);

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword);

or

(transition, headword).

23. An apparatus comprising:

a processor;

a natural-language-usage probability determiner executable on the processor to;

receive language-usage probabilities based upon appearances of instances of combinations of linguistic features within a training corpus;

calculate a probability at a node in a parse tree based upon linguistic features of the node and the language-usage probabilities;

wherein the combinations of linguistic features comprises;

(transition, headword, phrase level, syntactic history, segtype);

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword); and

(transition, headword).

24. An apparatus comprising:

a processor;

a natural-language-usage probability determiner executable on the processor to;

receive language-usage probabilities based upon appearances of instances of combinations of linguistic features within a training corpus;

calculate a probability at a node in a parse tree based upon linguistic features of the node and the language-usage probabilities;

wherein the determiner calculates the probability at the node by using PredParamRule Probability formula.

25. An apparatus comprising:

a processor;

a natural-language-usage probability determiner executable on the processor to;

receive language-usage probabilities based upon appearances of instances of combinations of linguistic features within a training corpus;

calculate a probability at a node in a parse tree based upon linguistic features of the node and the language-usage probabilities;

wherein the determiner calculates the probability at the node by using both PredParamRule Probability and SynBigram Probability formulas.

26. An apparatus comprising:

a processor;

a natural-language-usage parser executable on the processor to;

generate at least one parse tree representing a syntactically valid parse of the phrase, wherein the parse tree has hierarchical nodes;

divide each node into one or more hierarchical phase levels, wherein the phrase levels at a node represent a set of possible transitions from such node that are allowed by a set of grammar rules.

27. An apparatus as recited in claim 26, wherein the set of possible transitions from each node includes a null transition representing an application of none of the grammar rules.

28. A data structure for use with a computer having a processor and a memory, said structure comprising:

a corpus comprising one or more phrases in a natural language;

parse trees having hierarchical nodes, each tree representing at least one syntactically valid parse of each phrase in a subset of the corpus;

wherein each node has one or more hierarchical phrase levels, wherein the phrase levels at a node represent a set of possible transitions from such node that are allowed by a set of grammar rules.

29. The structure as recited in claim 28, wherein the subset of the corpus includes all phrases in the corpus.

30. A data structure for use with a computer having a processor and a memory, said structure comprising:

a corpus comprising one or more phrases in a natural language;

parse trees having hierarchical nodes, each tree representing at least one syntactically valid parse of each phrase in a subset of the corpus;

wherein each node as an associated probability, wherein the associated probability of a node is based upon linguistic features of such node and language-usage probabilities derived from appearances of instances of combinations of linguistic features within a training corpus;

wherein PredParamRule Probability formula is used to calculate a probability associated with a node.

31. A data structure for use with a computer having a processor and a memory, said structure comprising:

a corpus comprising one or more phrases in a natural language;

parse trees having hierarchical nodes, each tree representing at least one syntactically valid parse of each phrase in a subset of the corpus;

wherein each node as an associated probability, wherein the associated probability of a node is based upon linguistic features of such node and language-usage probabilities derived from appearances of instances of combinations of linguistic features within a training corpus;

wherein the combinations of linguistic features comprises;

(transition, headword, phrase level, syntactic history, segtype);

(headword, phrase level, syntactic history, segtype);

(modifying headword, transition, headword); and

(transition, headword).

32. A data structure for use with a computer having a processor and a memory, said structure comprising:

a corpus comprising one or more phrases in a natural language;

parse trees having hierarchical nodes, each tree representing at least one syntactically valid parse of each phrase in a subset of the corpus;

wherein each node as an associated probability, wherein the associated probability of a node is based upon linguistic features of such node and language-usage probabilities derived from appearances of instances of combinations of linguistic features within a training corpus;

wherein both PredParamRule Probability and SynBigram Probability formulas are used to calculate a probability associated with a node.

33. A program module for execution on a computing operating environment having a memory, the module comprising:

a natural language phrase parser configured to generate one or more syntactically valid parses for a phrase, each parse may be represented by a parse tree having hierarchical nodes;

a parse ranker configured to calculate a SGM for each parse of a phrase and to rank the parses to indicate a most probable parse;

wherein the parse ranker comprises;

data-acquisition device for receiving language-usage probabilities based upon appearances of instances of combinations of linguistic features within a training corpus;

probability calculator for calculating a probability at a node of a parse tree based upon linguistic features of the node and the language-usage probabilities.

34. A natural language processing system comprising a program module as recited in claim 33.

35. A grammar checking system comprising a program module as recited in claim 33.

36. A speech processing system comprising a program module as recited in claim 33.

37. A database query processing system comprising a program module as recited in claim 33.

38. An operating system comprising a program module as recited in claim 33.