Method and system for natural language parsing using podding

• US 5,926,784 A
• Filed: 07/17/1997
• Issued: 07/20/1999
• Est. Priority Date: 07/17/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jensen, Karen, Richardson, Steve
• Primary Examiner(s): Thomas, Joseph
• Application Number:
  US08/896,553
• Time in Patent Office: 733 Days
• Field of Search: 704/9, 704/10, 704/1, 707/531, 707/532, 707/104, 707/1, 707/2, 707/3, 707/4, 707/5, 707/6
• 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 method and system for determining the likelihood that a certain syntax rule when applied to a partial parse of an input will produce a node that will be part of the correct parse for the input. Each syntax rule indicates a higher-level syntactic construct that can be formed from one or more lower-level syntactic constructs. Each syntax rule has a probability which indicates the likelihood that the syntax rule will succeed and produce a node in the resulting parse tree. Each syntax rule also has a heuristic score formula indicating how to calculate a heuristically derived score for the higher-level syntactic construct created when the syntax rule is successfully applied. When a syntax rule is successfully applied while parsing the input sentence, the system calculates a probability for the higher-level syntactic construct produced by the syntax rule. The system then calculates a heuristic score for the higher-level syntactic construct produced by the syntax rule based on the heuristic score formula of the syntax rule and the calculated heuristic scores of the lower-level syntactic constructs to which the syntax rule was successfully applied. The system then combines the calculated probabilities and the calculated heuristic scores to guide the selecting of syntax rules to apply.

Claims

1. A method in a computer system for parsing input in a natural language, the computer system having syntax rules indicating how lower-level syntactic constructs in the language are combined to form higher-level syntactic constructs, the method comprising:

providing one or more heuristic score formulas for each syntax rule, the heuristic score formulas for each syntax rule indicating how to calculate a heuristic score when the syntax rule is to be applied to generate a node that may be part of the parse tree, the heuristic score indicating a likelihood that generate node will be part of the parse tree;

initializing a chart to contain one leaf node for each word of the input wherein the chart upon completion of the parse of the input contains a parse tree representing the parse;

applying syntax rules to the nodes of the chart so that higher-level nodes are generated and added to the chart in an order based on a heuristic score calculated in accordance with the heuristic score formulas for the applied syntax rules; and

when a termination condition is satisfied, selecting from the chart a set of spanning sub-trees that span each word of the input based on the parse of the input.

2. The method of claim 1 wherein the selected set of spanning sub-trees contains the smallest number of sub-trees.

3. The method of claim 1 wherein the heuristic scores are used to select the set of spanning sub-trees.

24. The method of claim 1 wherein the identifying and applying continue after a first parse tree is completed until a number of additional nodes are generated, the number being derived from the number of nodes that were created when generating the first parse tree.

4. A method in a computer system for parsing input in a natural language, the computer system having syntax rules indicating how lower-level syntactic constructs in the language are combined to form higher-level syntactic constructs, the method comprising:

providing one or more heuristic score formulas for each syntax rule, the heuristic score formulas for each syntax rule indicating how to calculate a heuristic score when the syntax rule is to be applied to generate a node that may be part of the parse tree, the heuristic score indicating a likelihood that the generated node will be part of the parse tree;

initializing a chart to contain one leaf node for each word of the input wherein the chart upon completion of the parse of the input contains a parse tree representing the parse;

pre-executing all syntax rules by applying them to the nodes of the chart, wherein each higher-level node that is generated is stored in an ordered list, awaiting introduction into the chart in the chart, each generated higher-level node having a heuristic score that is calculated in accordance with the heuristic score formulas for the syntax rule that generated the higher-level node;

adding a higher-level node generated from the pre-execution of syntax rules with the highest heuristic score to the chart; and

repeating the pre-executing and adding until the parsing is complete.

5. The method of claim 4 wherein only one higher-level node is added to the chart after each pre-execution of the syntax rules.

6. The method of claim 4 wherein multiple higher-level nodes are added to the chart after each pre-execution of the syntax rules.

7. The method of claim 4 wherein the pre-execution of syntax rules only applies those syntax rules that will apply to a higher-level node added to the chart since the last pre-execution of the syntax rules.

8. The method of claim 4 wherein each syntax rule has a probability and including combining the heuristic score from the application of a syntax rule with the probability of the syntax rule to generate a combined score and wherein the higher-level node added to the chart is the higher-level node with the highest combined score.

9. A method in a computer system for parsing an input sentence in a natural language, the input sentence having words, the computer system having syntax rules indicating how lower-level syntactic constructs in the natural language are combined to form higher-level syntactic constructs, each syntax rule having an associated probability, the parse of the input sentence to be represented by a parse tree with nodes, each node of the parse tree representing a syntactic construct that is part of the parse of the input sentence, the method comprising:

providing one or more heuristic score formulas for each syntax rule, the heuristic score formulas for each syntax rule indicating how to calculate a heuristic score when the syntax rule is to be applied to generate a node that may be part of the parse tree, the heuristic score indicating a likelihood that the generated node will be part of the parse tree;

initializing a chart to contain one leaf node for each word of the input sentence wherein the chart upon completion of the parse of the input sentence contains the parse tree; and

repeating the following until the parse tree of the input sentence is generated,

identifying a syntax rule that can be applied to the nodes of the chart to generate a higher-level node representing the higher-level syntactic construct of the identified syntax rule, the identified syntax rule being determined to be the syntax rule with the greatest likelihood that the resulting generated node will be part of the parse tree, the determination being made by combining a heuristic score calculated in accordance with the provided heuristic score formulas of the syntax rule and the probability of the syntax rule; and

applying the identified syntax rule to generate the higher-level node and to add the generated higher-level node to the chart.

10. The method of claim 9 including mapping a range of possible heuristic scores to a range of possible probabilities and wherein the combining of the calculated heuristic score and of the probability maps the calculated heuristic score to the range of possible probabilities.

11. The method of claim 10 wherein the heuristic scores are normalized to account for a number of words that would be encompassed by the application of the syntax rule.

12. The method of claim 11 wherein a probability distribution curve and an LNPS curve are generated and wherein the mapping is in accordance with the following:

##EQU6## where LNPS is a length normalized heuristic score, where max_-- p and min_-- p are maximum and minimum probabilities, where max_-- LNPS and min_-- LNPS are maximum and minimum length normalized heuristic scores, where A_p (x₁, x₂) is a function that returns the area under the probability curve between points x₁ and X₂, where A_LNPS (x₁, x₂) is a function that returns the area under the LNPS curve between points x₁ and x₂, and where A'"'"'_p (x₁, α

) is a function that returns a point that, together with point x₁, delineates the area α

under the probability curve.

13. The method of claim 9 wherein the calculated heuristic score and the probability are combined using weighted averaging so that when the heuristic score is high it is given a high weight and when the heuristic score is low it is given a low weight.

14. The method of claim 9 wherein the calculated heuristic score and the probability are combined in accordance with the following:

##EQU7## where f(LNPS) is the calculated heuristic score that is normalized based on number of words and that is mapped to the range of probabilities, where p is the probability, where max_-- p and min_-- p are maximum and minimum probabilities, and where max_-- LNPS and min_-- LNPS are maximum and minimum length normalized heuristic scores.

15. The method of claim 9 wherein the heuristic score formulas indicate how to calculate a numerical value to be assigned to the successful application of a syntax rule.

16. The method of claim 15 wherein the heuristic score rules indicate to combine scores of the lower-level syntactic constructs to which the syntax rule is to be applied.

17. The method of claim 9 wherein the identifying of a syntax rule includes pre-executing each syntax rule that could be applied to the current chart to generate a higher-level node which is not added to the chart and that has not yet been pre-executed and selecting as the identified syntax rule that pre-executed syntax rule with the highest combined score.

18. The method of claim 9 including before identifying a syntax rule, determining the combined score of each syntax rule that can be applied to the chart to generate a node and saving the determined combined scores to avoid re-determining the determined combined scores as higher-level nodes are added to the chart.

19. The method of claim 18 wherein the identifying of a syntax rule selects the syntax rule when the highest determined combined score.

20. The method of claim 9 wherein when a pre-determined termination condition is satisfied, generating the parse tree by selecting set of spanning sub-trees and combining the set of spanning sub-tree under a root node for the parse tree.

21. The method of claim 20 wherein the set of spanning sub-trees is selected based on the combine score for the root nodes of the sub-trees.

22. The method of claim 20 wherein the selected set of spanning sub-trees is the set with the minimum number of sub-trees.

23. The method of claim 22 wherein when two sets of spanning sub-trees have the same minimum number of sub-trees, then the set with the highest total combined score is selected.

25. A method in a computer system for determining a likelihood that a certain syntax rule when applied to a partial parse of an input will be part of the correct complete parse for the input, the computer system having syntax rules indicating a higher-level syntactic construct to be created from one or more lower-level syntactic constructs, each syntax rule having a probability, each syntax rule having a heuristic score formula indicating how to calculate a heuristically derived score for the higher-level syntactic construct when the syntax rule is applied, the method comprising:

for each syntax rule applied when parsing the input,

calculating a heuristic score for the higher-level syntactic construct of the syntax rule based on the heuristic score formula of the syntax rule; and

combining the probabilities and the calculated heuristic score to generate a combined score indicating the likelihood that the syntax rule when applied to the current partial parse of the input will be part of the correct parse for the input.

26. The method of claim 25 including mapping a range of possible heuristic scores to a range of possible probabilities and wherein the combining of the calculated heuristic score and of the probability maps the calculated heuristic score to the range of possible probabilities.

27. The method of claim 26 wherein the heuristic scores are normalized to account for a number of words that would be encompassed by the application of the syntax rule.

28. The method of claim 27 wherein a probability distribution curve and an LNPS curve are generated and wherein the mapping is in accordance with the following:

##EQU8## where LNPS is a length normalized heuristic score, where max_-- p and min_-- p are maximum and minimum probabilities, where max_-- LNPS and min_-- LNPS are maximum and minimum length normalized heuristic scores, where A_p (x₁, x₂) is a function that returns the area under the probability curve between points x₁ and x₂, where A_LNPS (x₁, x₂) is a function that returns the area under the LNPS curve between points x₁ and x₂, and where A'"'"'_p (x₁, α

) is a function that returns a point that, together with point x₁, delineates the area α

under the probability curve.

29. The method of claim 25 wherein the calculated heuristic score and the probability are combined using a weighted averaging so that when the heuristic score is high it is given a high weight and when the heuristic score is low it is given a low weight.

30. The method of claim 25 wherein the calculated heuristic score and the probability are combined in accordance with the following:

##EQU9## where f(LNPS) is the calculated heuristic score that is normalized based on number of words and that is mapped to the range of probabilities, where p is the calculated probability, where max_-- p and min_-- p are maximum and minimum probabilities, and where max_-- LNPS and min_-- LNPS are maximum and minimum length normalized heuristic scores.

31. The method of claim 25 wherein the heuristic score rules indicate how to calculate a numerical value to be assigned to the application of a syntax rule.

32. The method of claim 25 wherein the syntax rules are applied in an ordering so that the syntax rules resulting in the highest combined scores are applied first.

33. The method of claim 25 including pre-executing each syntax rule that could be applied to the partial parse to generate a higher-level syntactic construct which is not reflected in the partial parse and that has not yet been pre-executed and selecting that pre-executed syntax rule with the highest combined score to apply to the partial parse.

34. The method of claim 25 including determining the combined score of each syntax rule that can be successfully applied to the partial parse and saving the determined combined scores to avoid re-determining the determined combined scores as higher-level syntactic constructs are processed.

35. The method of claim 34 wherein the syntax rule with the highest determined combined score is applied to the partial parse.

36. A computer-readable medium containing instructions for causing a computer system to determine a likelihood that a certain syntax rule when applied to a partial parse of an input will be part of the correct parse for the input, the computer system having syntax rules indicating a higher-level syntactic construct to be created from one or more lower-level syntactic constructs, each syntax rule having a probability, each syntax rule having a heuristic score formula indicating how to calculate a heuristically derived score for the higher-level syntactic construct when the syntax rule is applied, by:

for each syntax rule applied when parsing the input,

calculating a heuristic score for the higher-level syntactic construct of the syntax rule based on the heuristic score formula of the syntax rule; and

combining the probabilities and the calculated heuristic score to generate a combined score indicating the likelihood that the syntax rule when applied to the current partial parse of the input will be part of the correct parse for the input.

37. The computer-readable medium of claim 36 including mapping a range of possible heuristic scores to a range of possible probabilities and wherein the combining of the calculated heuristic score and of the probability maps the calculated heuristic score to the range of possible probabilities.

38. The computer-readable medium of claim 37 wherein the heuristic scores are normalized to account for a number of words that would be encompassed by the application of the syntax rule.

39. The computer-readable medium of claim 38 wherein a probability distribution curve and an LNPS curve are generated and wherein the mapping is in accordance with the following:

##EQU10## where LNPS is a length normalized heuristic score, where max_-- p and min_-- p are maximum and minimum probabilities, where max_-- LNPS and min_-- LNPS are maximum and minimum length normalized heuristic scores, where A_p (x₁, x₂) is a function that returns the area under the probability curve between points x₁ and x₂, where A_LNPS (x₁, x₂) is a function that returns the area under the LNPS curve between points x₁ and x₂, and where A'"'"'_p (x₁, α

) is a function that returns a point that, together with point x₁, delineates the area α

under the probability curve.

40. The computer-readable medium of claim 36 wherein the calculated heuristic score and the probability are combined using a weighted averaging so that when the heuristic score is high it is given a high weight and when the heuristic score is low it is given a low weight.

41. The computer-readable medium of claim 36 wherein the calculated heuristic score and the probability are combined in accordance with the following:

##EQU11## where f(LNPS) is the calculated heuristic score that is normalized based on number of words and that is mapped to the range of probabilities, where p is the calculated probability, where max_-- p and min_-- p are maximum and minimum probabilities, and where max_-- LNPS and min_-- LNPS are maximum and minimum length normalized heuristic scores.

42. The computer-readable medium of claim 36 wherein the heuristic score formulas indicate how to calculate a numerical value to be assigned to the application of a syntax rule.

43. The computer-readable medium of claim 36 wherein the syntax rules are applied in an ordering so that the syntax rules resulting in the highest combined scores are applied first.

44. The computer-readable medium of claim 36 including pre-executing each syntax rule that could be applied to the partial parse to generate a higher-level syntactic instruct which is not reflected in the partial parse and that has not yet been pre-executed and selecting that pre-executed syntax rule with the highest combined score to apply to the partial parse.

45. The computer-readable medium of claim 36 including determining the combined score of each syntax rule that can be successfully applied to the partial parse and saving the determined combined scores to avoid re-determining the determined combined scores as higher-level syntactic constructs are processed.

46. The computer-readable medium of claim 45 wherein the syntax rule with the highest determined combined score is applied to the partial parse.