Method and apparatus for embedding grammars in a natural language understanding (NLU) statistical parser

• US 6,983,239 B1
• Filed: 10/25/2000
• Issued: 01/03/2006
• Est. Priority Date: 10/25/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Epstein, Mark E.
• Primary Examiner(s): Young, W. R.
• Assistant Examiner(s): Opsasnick, Michael N.
• Application Number:
  US09/696,764
• Time in Patent Office: 1,896 Days
• Field of Search: 704/1, 704/9, 704/10, 704/257
• 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
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A method and system for use in a natural language understanding system for including grammars within a statistical parser. The method involves a series of steps. The invention receives a text input. The invention applies a first context free grammar to the text input to determine substrings and corresponding parse trees, wherein the substrings and corresponding parse trees further correspond to the first context free grammar. Additionally, the invention can examine each possible substring using an inventory of queries corresponding to the CFG.

Claims

1. In a natural language understanding (NLU) system, a method for including grammars in a statistical parser comprising:

receiving a text input; and

,

applying a first context free grammar (CFG) to said text input to determine substrings and corresponding parse trees, wherein said substrings and said corresponding parse trees further correspond to said first CFG; and

,

examining each said possible substring and corresponding parse tree using an inventory of ordered grammar-related queries corresponding to said CFG, wherein said queries are ordered training of the NLU system to form a decision tree, the ordering of the queries being a statistical ordering based on a minimization of conditional entropy or maximization of a likelihood that a resulting model predicts data used to train the NLU system.

2. The method of claim 1, wherein said inventory of queries further includes:

queries corresponding to a non-terminal within said first CFG.

3. The method of claim 1, wherein said inventory of queries further includes:

queries corresponding to a terminal within said first CFG.

4. The method of claim 1, wherein said inventory of queries has a hierarchy determined during training of the NLU system.

5. The method of claim 1, further comprising iteratively applying different CFGs using a different CFG during each iteration to determine additional substrings and corresponding parse trees relating to each said different CFG applied to said text input.

6. The method of claim 5, further comprising the step of:

examining each said additional substring determined by each said different CFG using said inventory of queries wherein said inventory of queries contains queries corresponding to each said different CFG.

7. The method of claim 6, wherein said inventory of queries further includes:

queries corresponding to a non-terminal within each said different CFG.

8. The method of claim 6, wherein said inventory of queries further includes:

queries corresponding to a terminal within each said different CFG.

9. The method of claim 1, further comprising:

comparing a probability value corresponding to each said substring to one or more threshold probability values, wherein said first CFG is a probabilistic CFG (PCFG).

10. The method of claim 9, wherein said inventory of queries further includes:

queries corresponding to a non-terminal within said first PCFG.

11. The method of claim 9, wherein said inventory of queries further includes:

queries corresponding to a terminal within said first PCFG.

12. The method of claim 9, further comprising iteratively applying different PCFGs using a different PCFG during each iteration to determine additional substrings and corresponding parse trees relating to each said different PCFG applied to said text input.

13. The method of claim 12, further comprising the step of:

examining each said additional substring determined by each said different PCFG using said inventory of queries wherein said inventory of queries contains queries corresponding to each said different PCFG.

14. The method of claim 13, wherein said inventory of queries further includes:

queries corresponding to a non-terminal within each said different PCFG.

15. The method of claim 13, wherein said inventory of queries further includes:

queries corresponding to a terminal within each said different PCFG.

16. A system for recognizing grammatical phrases in a text input comprising:

a text buffer for storing said text input;

at least one context-free grammar (CFG) for recognizing a particular grammatical phrase within said text input; and

,

an inventory of ordered grammar-related queries wherein each query within said inventory of queries corresponds to said at least one CFG;

wherein said queries are ordered during training of a corresponding natural language understanding (NLU) system to form a decision tree, the ordering of the queries being a statistical ordering based on a minimization of conditional entropy or maximization of a likelihood that a resulting model predicts data used to train the NLU system;

wherein said at least one CFG is applied to said text input in said text buffer to determine substrings and corresponding parse trees;

wherein said inventory of queries is further applied to said substrings to determine said particular grammatical phrase.

17. The system of claim 16, wherein said at least one CFG is a probabilistic CFG (PCFG) containing a probability value corresponding to each rule also within said at least one PCFG.

18. A system for recognizing grammatical phrases in a text input comprising:

a text buffer for storing said text input;

at least one context-free grammar (CFG) for recognizing a particular grammatical phrase within said text input; and

,

one or more weighted grammar-related features wherein each said feature corresponds to said at least one CFG;

wherein each said feature is weighted during training of a corresponding natural language understanding (NLU) system, each weight being determined based on a maximum entropy model;

wherein said at least one CFG is applied to said text input in said text buffer to determine substrings and corresponding parse trees;

wherein said features are further applied to said substrings to determine said particular grammatical phrase.

19. The system of claim 18, wherein said at least one CFG is a probabilistic CFG (PCFG) containing a probability value corresponding to each rule also within said at least one PCFG.

20. A machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform the steps of:

receiving a text input;

applying a first context free grammar (CFG) to said text input to determine substrings and corresponding parse trees, wherein said substrings and said corresponding parse trees further correspond to said first CFG; and

,

examining each said possible substring and corresponding parse tree using an inventory of ordered grammar-related queries corresponding to said CFG, wherein said queries are ordered during training of the NLU system to form a decision tree, the ordering of the queries being a statistical ordering based on a minimization of conditional entropy or maximization of a likelihood that a resulting model predicts data used to train a corresponding NLU system.

21. The machine readable storage of claim 20, further comprising iteratively applying different CFGs using a different CFG during each iteration to determine each possible substring and corresponding parse tree relating to each said different CFG applied to said text input.

22. The machine readable storage of claim 20, wherein said first CFG is a probabilistic CFG (PCFG) having one or more threshold probability values.

23. The machine readable storage of claim 20, said inventory of queries having a hierarchy determined during training of said NLU system.

24. In a natural language understanding (NLU) system, a method for including grammars in a statistical parser comprising:

receiving a text input; and

,

applying a first context free grammar (CFG) to said text input to determine substrings and corresponding parse trees, wherein said substrings and said corresponding parse trees further correspond to said first CFG; and

,

examining each said possible substring and corresponding parse tree using one or more weighted grammar-related features corresponding to said CFG, wherein each said feature is weighted during training of said NLU system, each weight being determined based on a maximum entropy model.

25. The method of claim 24, wherein said inventory of queries further includes:

features corresponding to a non-terminal within said first CFG.

26. The method of claim 24, wherein said inventory of queries further includes:

features corresponding to a terminal within said first CFG.

27. The method of claim 24, wherein each weight determined during training of said NLU system is determined based on a generalized iterative scaling algorithm.

28. The method of claim 24, further comprising iteratively applying different CFGs using a different CFG during each iteration to determine additional substrings and corresponding parse trees relating to each said different CFG applied to said text input.

29. The method of claim 28, further comprising the step of:

examining each said additional substring determined by each said different CFG using said features, wherein said features further correspond to each said different CFG.

30. The method of claim 29, wherein said features further include:

features corresponding to a non-terminal within each said different CFG.

31. The method of claim 29, wherein said features further include:

features corresponding to a terminal within each said different CFG.

32. The method of claim 24, further comprising comparing a probability value corresponding to each said substring to one or more threshold probability values, wherein said first CFG is a probabilistic CFG (PCFG).

33. The method of claim 32, wherein said features further include:

features corresponding to a non-terminal within said first PCFG.

34. The method of claim 32, wherein said features further include:

features corresponding to a terminal within said first PCFG.

35. The method of claim 32, further comprising iteratively applying different PCFGs using a different PCFG during each iteration to determine additional substrings and corresponding parse trees relating to each said different PCFG applied to said text input.

36. The method of claim 35, further comprising the step of:

examining each said additional substring determined by each said different PCFG using said features, wherein said features further correspond to each said different PCFG.

37. The method of claim 36, wherein said features farther include:

features corresponding to a non-terminal within each said different PCFG.

38. The method of claim 36, wherein said features further include:

features corresponding to a terminal within each said different PCFG.

39. A machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform the steps of:

receiving a text input;

applying a first context free grammar (CFG) to said text input to determine substrings and corresponding parse trees, wherein said substrings and said corresponding parse trees further correspond to said first CFG; and

,

examining each said possible substring and corresponding parse tree using one or more weighted grammar-related features corresponding to said CFG, wherein each said feature is weighted during training of a corresponding natural language understanding (NLU) system, each weight being determined based on a maximum entropy model.

40. The machine readable storage of claim 39, further comprising iteratively applying different CFGs using a different CFG during each iteration to determine additional substrings and corresponding parse trees relating to each said different CFG applied to said text input.

41. The machine readable storage of claim 39, wherein said first CFG is a probabilistic CFG (PCFG) having one or more threshold probability values.

42. The machine readable storage of claim 39, wherein each said weight determined during training of NLU system is determined based on a generalized iterative scaling algorithm.

43. In a natural language understanding (NLU) system, a direct channel method for determining a meaning for a text input comprising:

selectably applying a reusable context free grammar (CFG) to a text input;

identifying one or more substrings within said text input, each said substring corresponding to said reusable CFG;

examining each said possible substring and corresponding parse tree using an inventory of ordered grammar-related queries and a set of features corresponding to said CFG, wherein said queries are ordered during training of the NLU system to form a decision tree, the ordering of the queries being a statistical ordering based on a minimization of conditional entropy or maximization of a likelihood that a resulting model predicts data used to train the NLU system; and

,

determining a meaning for said text input based upon said identified substrings from possible meanings within said reusable CFG.

44. The method of claim 43, said determining step comprising:

applying features having weights corresponding to said substrings to said text input.

45. The method of claim 43, further comprising:

comparing a probability value corresponding to each said substring to one or more threshold probability values, wherein said first reusable CFG is a reusable probabilistic CFG (PCFG).

46. The method of claim 43, further comprising iteratively applying different selected CFGs to said text input.

47. The method of claim 46, further comprising iteratively applying different selected PCFGs to said text input.

48. A machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform the steps of:

selectably applying a reusable context free grammar (CFG) to a text input;

identifying one or more substrings within said text input, said substrings corresponding to said reusable CFG;

examining each said substring using at least one of an inventory of grammar-related queries and a set of features corresponding to said CFG, wherein said queries are ordered during training of a corresponding natural language understanding (NLU) system to form a decision tree, the ordering of the queries being a statistical ordering based on a minimization of conditional entropy or maximization of a likelihood that a resulting model predicts data used to train the NLU system; and

,

determining a meaning for said text input based upon said identified substrings from possible meanings within said reusable CFG.

49. The machine readable storage of claim 48, further comprising iteratively applying different selected CFGs to said text input.

50. The machine readable storage of claim 48, further comprising:

comparing a probability value corresponding to each said substring to one or more threshold probability values, wherein said first reusable CFG is a reusable probabilistic CFG (PCFG).

51. The machine readable storage of claim 50, further comprising iteratively applying different selected PCFGs to said text input.