Systems and methods for improving the efficiency of syntactic and semantic analysis in automated processes for natural language understanding using traveling features

• US 9,569,425 B2
• Filed: 03/03/2014
• Issued: 02/14/2017
• Est. Priority Date: 03/01/2013
• Status: Active Grant

• Current Assignee: The Software Shop, Inc.
• Original Assignee: The Software Shop, Inc.
• Inventors: Jackson, Jeffrey
• Primary Examiner(s): Godbold, Douglas
• Application Number:
  US14/195,529
• Publication Number:
  US 20140249803A1
• Time in Patent Office: 1,079 Days
• Field of Search: 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

A natural language understanding system may be given the capability to construct a semantically detailed parse tree for each acceptable interpretation of an input natural language expression (or fewer such parse trees than interpretations) by independently solving sub-trees corresponding to various series of post nominal modifiers and associating those partial solutions with corresponding nodes in the overall parse tree. The argument order in predicate calculus atomic formulas may be standardized in a manner that supports the use of a chart parser applied to a head-driven phase structure grammar and that permits a simplified more tractable grammar that in turn can be used as a domain general semantic grammar.

Claims

1. A method comprising:

using at least a processor and memory for;

receiving an identification of at least one first grammar rule element of a first grammar rule as an origin of a traveling feature;

receiving a traveling feature value calculating process associated with the at least one first grammar rule element;

associating, by the processor, a natural language expression part with one of the at least one first grammar rule element;

applying, by the processor, the traveling feature value calculating process to the one of the at least one first grammar rule element and to the natural language expression part for identifying any first values of the traveling feature; and

constructing, by the processor, a first node, based on the application of the traveling feature value calculating process,

thereby associating the natural language expression part with the at least one first grammar rule element to reduce construction, at the processor, of the first node and to thereby improve the efficiency of syntactic and semantic analysis, at the processor, of the natural language expression part.

2. The method of claim 1, further comprising determining a subset of the identified first values of the traveling feature to be associated with the first node, wherein the subset of the identified first values comprises any of the identified first values of the traveling feature.

3. The method of claim 2, wherein the subset of the identified first values further comprises excluding the identified first values of the traveling feature.

4. The method of claim 2, further comprising associating the determined identified first values of the traveling feature with the first node.

5. The method of claim 4, further comprising:

receiving an identification of at least one second grammar rule element of a second grammar rule;

receiving an identification of any existing second values of the traveling feature, wherein the any existing second values of the traveling feature are associated with the at least one first grammar rule element;

receiving an identification of any existing third values of the traveling feature, wherein the any third values of the traveling feature are associated with the at least one second grammar rule element; and

wherein constructing the first node further comprises;

determining a subset of the identified second values of the traveling feature to be associated with the first node, wherein the subset of the identified second values comprises any of the identified second values of the traveling feature and associating the determined identified second values of the traveling feature with the first node; and

determining a subset of the identified third values of the traveling feature to be associated with the first node, wherein the subset of the identified third values comprises any of the identified third values of the traveling feature and associating the determined identified third values of the traveling feature with the first node.

6. The method of claim 5, further comprising determining a final set of values of the traveling feature based on the identified first values, the identified second values and the identified third values of the traveling feature associated with the first node.

7. The method of claim 5, further comprises:

receiving an identification of at least one third grammar rule element of the first grammar rule or the second grammar rule;

constructing a second node;

associating the at least one third grammar rule element with the second node; and

wherein constructing the second node further comprises;

determining a subset of the identified first values of the traveling feature to be associated with the second node, wherein the subset of the identified first values comprises any of the identified first values of the traveling feature and associating the determined identified first values of the traveling feature with the second node;

determining a subset of the identified second values of the traveling feature to be associated with the second node, wherein the subset of the identified second values comprises any of the identified second values of the traveling feature and associating the determined identified second values of the traveling feature with the second node; and

determining a subset of the identified third values of the traveling feature to be associated with the second node, wherein the subset of the identified third values comprises any of the identified third values of the traveling feature and associating the determined identified third values of the traveling feature with the second node.

8. The method of claim 1, further comprising storing the constructed first node in a database.

9. The method of claim 1, further comprising identifying at least one first grammar rule element of the first grammar rule in a user interface.

10. A system comprising:

at least a processor;

a memory; and

a natural language parser, the natural language parser is configured to;

receive, by the processor, an identification of at least one first grammar rule element of a first grammar rule as an origin of a traveling feature;

receive, by the processor, a traveling feature value calculating process associated with the at least one first grammar rule element;

associate, by the natural language parser, a natural language expression part with one of the at least one first grammar rule element;

apply, by the processor and natural language parser, the traveling feature value calculating process to the one of the at least one first grammar rule element and to the natural language expression part for identifying any first values of the traveling feature; and

construct, by the processor, a first node, based on the application of the traveling feature value calculating process,

thereby associating the natural language expression part with the at least one first grammar rule element to reduce construction, at the processor, of the first node and to thereby improve the efficiency of syntactic and semantic analysis, at the processor and natural language parser, of the natural language expression part.

11. The system of claim 10, wherein the natural language parser is configured to determine a subset of the identified first values of the traveling feature to be associated with the first node, wherein the subset of the identified first values comprises any of the identified first values of the traveling feature.

12. The system of claim 11, wherein the subset of the identified first values comprises excluding the identified first values of the traveling feature.

13. The system of claim 11, wherein the natural language parser is configured to associate the determined identified first values of the traveling feature with the first node.

14. The system of claim 13, further configured to:

receive an identification of at least one third grammar rule element of the first grammar rule or the second grammar rule;

construct a second node;

associate the at least one third grammar rule element with the second node; and

wherein the construction of the second node further comprises a system further configured to;

determine a subset of the identified first values of the traveling feature to be associated with the second node, wherein the subset of the identified first values comprises any of the identified first values of the traveling feature and associating the determined identified first values of the traveling feature with the second node;

determine a subset of the identified second values of the traveling feature to be associated with the second node, wherein the subset of the identified second values comprises any of the identified second values of the traveling feature and associating the determined identified second values of the traveling feature with the second node; and

determine a subset of the identified third values of the traveling feature to be associated with the second node, wherein the subset of the identified third values comprises any of the identified third values of the traveling feature and associating the determined identified third values of the traveling feature with the second node.

15. The system of claim 11, wherein the natural language parser is further configured to:

receive an identification of at least one second grammar rule element of a second grammar rule;

receive an identification of any existing second values of the traveling feature, wherein the any existing second values of the traveling feature are associated with the at least one first grammar rule element; and

receive an identification of any existing third values of the traveling feature, wherein the any third values of the traveling feature are associated with the at least one second grammar rule element; and

wherein the construction of the first node by the natural language parser further comprises;

determine a subset of the identified second values of the traveling feature to be associated with the first node, wherein the subset of the identified second values comprises any of the identified second values of the traveling feature and associating the determined identified second values of the traveling feature with the first node; and

determine a subset of the identified third values of the traveling feature to be associated with the first node, wherein the subset of the identified third values comprises any of the identified third values of the traveling feature and associating the determined identified third values of the traveling feature with the first node.

16. The system of claim 15, wherein the natural language parser is further configured to determine a final set of values of the traveling feature based on the identified first values, the identified second values and the identified third values of the traveling feature associated with the first node.

17. The system of claim 10, wherein the natural language parser is further configured to store the constructed first node in a database.

18. The system of claim 10, wherein the natural language parser is further configured to identify at least one first grammar rule element of the first grammar rule in a user interface.

19. A computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computing device to cause the computing device to:

receive, by the computing device, an identification of at least one first grammar rule element of a first grammar rule as an origin of a traveling feature;

receive, by the computing device, a traveling feature value calculating process associated with the at least one first grammar rule element;

associate, by the computing device, a natural language expression part with one of the at least one first grammar rule element;

apply, by the computing device, the traveling feature value calculating process to the one of the at least one first grammar rule element and to the natural language expression part for identifying any first values of the traveling feature; and

construct, by the computing device, a first node, based on the application of the traveling feature value calculating process,

thereby associating the natural language expression part with the at least one first grammar rule element to reduce construction, at the processor, of the first node and to thereby improve the efficiency of syntactic and semantic analysis, at the computing device, of the natural language expression part.

20. The computer program product of claim 19, wherein the program instructions are executable by the computing device to cause the natural language parser to determine a subset of the identified first values of the traveling feature to be associated with the first node, wherein the subset of the identified first values comprises any of the identified first values of the traveling feature.

21. The computer program product of claim 20, wherein the program instructions are executable by the computing device, wherein the subset of the identified first values further comprises excluding the identified first values of the traveling feature.

22. The computer program product of claim 20, wherein the program instructions are executable by the computing device to cause the natural language parser to further associate the determined identified first values of the traveling feature with the first node.

23. The computer program product of claim 22, wherein the program instructions are executable by the computing device to cause the natural language parser to:

receive, by the computing device, an identification of at least one second grammar rule element of a second grammar rule;

receive, by the computing device, an identification of any existing second values of the traveling feature, wherein the any existing second values of the traveling feature are associated with the at least one first grammar rule element;

receive, by the computing device, an identification of any existing third values of the traveling feature, wherein the any third values of the traveling feature are associated with the at least one second grammar rule element; and

wherein the construction of the first node by the natural language parser further comprises;

determine, by the computing device, a subset of the identified second values of the traveling feature to be associated with the first node, wherein the subset of the identified second values comprises any of the identified second values of the traveling feature and associating the determined identified second values of the traveling feature with the first node; and

determine, by the computing device, a subset of the identified_third values of the traveling feature to be associated with the first node, wherein the subset of the identified third values comprises any of the identified third values of the traveling feature and associating the determined identified third values of the traveling feature with the first node.

24. The computer program product of claim 23, wherein the program instructions are executable by the computing device to cause the natural language parser to determine a final set of values of the traveling feature based on the identified first values, the identified second values and the identified third values of the traveling feature associated with the first node.

25. The computer program product of claim 23, wherein the program instructions are executable by the computing device to:

receive, by the computing device, an identification of at least one third grammar rule element of the first grammar rule or the second grammar rule;

construct, by the computing device, a second node;

associate, by the computing device, the at least one third grammar rule element with the second node; and

wherein the construction of the second node further comprises a computer program product further configured to;

determine, by the computing device, a subset of the identified first values of the traveling feature to be associated with the second node, wherein the subset of the identified first values comprises any of the identified first values of the traveling feature and associating the determined identified first values of the traveling feature with the second node;

determine, by the computing device, a subset of the identified second values of the traveling feature to be associated with the second node, wherein the subset of the identified second values comprises any of the identified second values of the traveling feature and associating the determined identified second values of the traveling feature with the second node; and

determine, by the computing device, a subset of the identified third values of the traveling feature to be associated with the second node, wherein the subset of the identified third values comprises any of the identified third values of the traveling feature and associating the determined identified third values of the traveling feature with the second node.

26. The computer program product of claim 19, wherein the program instructions are executable by the computing device to further cause the computing device to store the constructed first node in a database.

27. The computer program product of claim 19, wherein the program instructions are executable by the computing device to further cause the computing device to identify at least one first grammar rule element of the first grammar rule in a user interface.