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

• US 9,594,745 B2
• Filed: 03/03/2014
• Issued: 03/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): Neway, Samuel G
• Application Number:
  US14/195,556
• Publication Number:
  US 20140249804A1
• Time in Patent Office: 1,107 Days
• 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 a first natural language expression;

identifying, by the processor, at least one modifier natural language expression comprised within the first natural language expression;

identifying, by the processor, at least one candidate modifiee natural language expression comprised within the first natural language expression for each of the at least one modifier natural language expression using traveling features to identify respective syntactic positions of the at least one modifier natural language expression and the at least one candidate modifiee natural language expression consistent with at least one plausible modifier-modifiee relationship between the at least one modifier natural language expression and the at least one candidate modifiee natural language expression based on the identified respective syntactic positions,

wherein the traveling features represent a value calculation process applied to the at least one candidate modifiee natural language expression and the at least one modifier natural language expression that identifies the at least one candidate modifiee for each of the identified modifier natural language expression;

assigning at least one sense to the at least one candidate modifiee natural language expression and the at least one modifier natural language expression, wherein the at least one sense represents a partial meaning of a predicating expression; and

constructing, by the processor, at least one or more components of one or more parse trees based on the at least one plausible modifier-modifiee relationship and the at least one sense assigned to the at least one candidate modifiee natural language expression and the at least one modifier natural language expression corresponding to respective syntactic positions,

wherein identifying the at least one candidate modifiee natural language expression comprised within the first natural language expression for each of the at least one modifier natural language expression using the traveling features to identify the respective syntactic positions of the at least one modifier natural language expression and the at least one candidate modifiee natural language expression consistent with the at least one plausible modifier-modifiee relationship between the at least one modifier natural language expression and the at least one candidate modifiee natural language expression based on the identified respective syntactic positions, to reduce construction of the one or more parse trees and to thereby improve the efficiency of syntactic and semantic analysis, at the processor.

2. The method of claim 1, further comprising identifying, for at least one of the modifier natural language expression, at least one modifiee natural language expression comprised within the first natural language expression, wherein each one of the at least one modifiee natural language expression is permitted to be modified by the at least one modifier natural language expression.

3. The method of claim 2, further comprising:

determining at least one meaning for each of the at least one modifier natural language expression; and

determining at least one meaning for each of the at least one modifiee natural language expression.

4. The method of claim 2, further comprising associating at least one modifiee natural language expression syntactically permitted to be modified by the at least one modifier natural language expression with the at least one modifier natural language expression.

5. The method of claim 3, further comprising assigning the at least one determined meaning for each of the at least one modifier natural language expression to the at least one determined meaning for each of the at least one modifiee natural language expression, based on semantic criteria.

6. The method of claim 5, wherein the semantic criteria is mutual compatibility of the assigned determined meanings of the modifier natural language expression and the modifiee natural language expression.

7. The method of claim 1, further comprising using a processor for storing the identified at least one modifier natural language expression comprised within the first natural language expression in a database.

8. The method of claim 1, further comprising using a processor for receiving a first natural language expression in a user interface.

25. The method of claim 1, further comprising applying semantic composition rules to the one or more parse trees to identify candidate senses for each node in each parse tree.

26. The method of claim 25, wherein the candidate senses are identified for each node based on the identified candidate senses of the children of that node.

27. The method of claim 25, wherein the candidate senses are identified for each node based on the children of that node.

28. The method of claim 27, wherein the candidate senses are assigned bottom-up in each parse tree starting with predefined candidate senses of leaf nodes in the parse tree.

29. The method of claim 1, further comprising identifying candidate senses for the modifier and for the modifiee in each modifier-modifiee pair such that for each modifier and each modifiee in all the modifier-modifiee pairs that modifier or modifiee has the same sense or a non-conflicting sense for all modifier-modifiee pairs in which that modifier or modifiee occurs for producing a human-comprehensible interpretation of the received first natural language expression.

30. The method of claim 26, further comprising presenting to a user a human-comprehensible result based on the human-comprehensible interpretation.

31. The method of claim 26, wherein receiving a first natural language expression comprises receiving user input associated with the first natural language expression.

32. The method of claim 26, wherein receiving a first natural language expression comprises receiving a tangible representation of the first natural language expression.

9. A system configured to:

at least a processor and memory comprising a natural language parser, the natural language parser is configured to;

receive, by the processor, a first natural language expression;

identify, by the processor, at least one modifier natural language expression comprised within the first natural language expression;

identify, by the processor, at least one candidate modifiee natural language expression comprised within the first natural language expression for each of the at least one modifier natural language expression using traveling features to identify respective syntactic positions of the at least one modifier natural language expression and the at least one candidate modifiee natural language expression consistent with at least one plausible modifier-modifiee relationship between the at least one modifier natural language expression and the at least one candidate modifiee natural language expression based on the identified respective syntactic positions,

wherein the traveling features represent a value calculation process applied to the at least one candidate modifiee natural language expression and the at least one modifier natural language expression that identifies the at least one candidate modifiee for each of the identified modifier natural language expression;

assign at least one sense to the at least one candidate modifiee natural language expression and the at least one modifier natural language expression, wherein the at least one sense represents a partial meaning of a predicating expression;

and

construct, by the processor and natural language parser, one or more components of one or more parse trees based on the at least one plausible modifier-modifiee relationship and the at least one sense assigned to the at least one candidate modifiee natural language expression and the at least one modifier natural language expression corresponding to respective syntactic positions,

wherein the at least one candidate modifiee natural language expression comprised within the first natural language expression for each of the at least one modifier natural language expression using the traveling features to identify the respective syntactic positions of the at least one modifier natural language expression and the at least one candidate modifiee natural language expression consistent with the at least one plausible modifier-modifiee relationship between the at least one modifier natural language expression and the at least one candidate modifiee natural language expression based on the identified respective syntactic positions, reduces construction of the one or more parse trees and to thereby improve the efficiency of syntactic and semantic analysis, at the processor.

10. The system of claim 9, further configured to identify, for at least one of the modifier natural language expression, at least one modifiee natural language expression comprised within the first natural language expression, wherein each one of the at least one modifiee natural language expression is permitted to be modified by the at least one modifier natural language expression.

11. The system of claim 10, further configured to:

determine at least one meaning for each of the at least one modifier natural language expression; and

determine at least one meaning for each of the at east one modifiee natural language expression.

12. The system of claim 10, further configured to associate at least one modifiee natural language expression syntactically permitted to be modified by the at least one modifier natural language expression with the at least one modifier natural language expression.

13. The system of claim 11, further configured to assign the at least one determined meaning for each of the at least one modifier natural language expression to the at least one determined meaning for each of the at least one modifiee natural language expression, based on semantic criteria.

14. The system claim 13, wherein the semantic criteria is mutual compatibility of the assigned determined meanings of the modifier natural language expression and the modifiee natural language expression.

15. The system of claim 9, wherein the processor is further configured to store the identified at least one modifier natural language expression comprised within the first natural language expression in a database.

16. The system of claim 9, wherein the processor is further configured to receive a first natural language expression in a user interface.

17. A computer program product comprising a 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, a first natural language expression;

identify, by the computing device, at least one modifier natural language expression comprised within the first natural language expression;

identify, by the computing device, at least one candidate modifiee natural language expression comprised within the first natural language expression for each of the at least one modifier natural language expression using traveling features to identify respective syntactic positions of the at least one modifier natural language expression and the at least one candidate modifiee natural language expression consistent with at least one plausible modifier-modifiee relationship between the at least one modifier natural language expression and the at least one candidate modifiee natural language expression based on the identified respective syntactic positions,

wherein the traveling features represent a value calculation process applied to the at least one candidate modifiee natural language expression and the at least one modifier natural language expression that identifies the at least one candidate modifiee for each of the identified modifier natural language expression;

assign at least one sense to the at least one candidate modifiee natural language expression and the at least one modifier natural language expression, wherein the at least one sense represents a partial meaning of a predicating expression;

and

construct, by the computing device, one or more components of one or more parse trees based on the at least one plausible modifier-modifiee relationship and the at least one sense assigned to the at least one candidate modifiee natural language expression and the at least one modifier natural language expression corresponding to respective syntactic positions,

wherein the at least one candidate modifiee natural language expression comprised within the first natural language expression for each of the at least one modifier natural language expression using the traveling features to identify the respective syntactic positions of the at least one modifier natural language expression and the at least one candidate modifiee natural language expression consistent with the at least one plausible modifier-modifiee relationship between the at least one modifier natural language expression and the at least one candidate modifiee natural language expression based on the identified respective syntactic positions, reduces construction of the one or more parse trees and to thereby improve the efficiency of syntactic and semantic analysis, at the computing device.

18. The computer program product of claim 17, wherein the program instructions are executable by the computing device to cause the natural language parser to identify, by the computing device, for at least one of the modifier natural language expression, at least one modifiee natural language expression comprised within the first natural language expression, wherein each one of the at least one modifiee natural language expression is permitted to be modified by the at least one modifier natural language expression.

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

determine, by the computing device, at least one meaning for each of the at least one modifier natural language expression; and

determine, by the computing device, at least one meaning for each of the at least one modifiee natural language expression.

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 associate, by the computing device, at least one modifiee natural language expression syntactically permitted to be modified by the at least one modifier natural language expression with the at least one modifier natural language expression.

21. The computer program product of claim 19, wherein the program instructions are executable by the computing device to cause the natural language parser to assign, by the computing device, the at least one determined meaning for each of the at least one modifier natural language expression to the at least one determined meaning for each of the at least one modifiee natural language expression, based on semantic criteria.

22. The computer program product of claim 21, wherein the program instructions are executable by the computing device, wherein the semantic criteria is mutual compatibility of the assigned determined meanings of the modifier natural language expression and the modifiee natural language expression.

23. 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, by the computer program product, the identified at least one modifier natural language expression comprised within the first natural language expression in a database.

24. The computer program product of claim 19, wherein the program instructions are executable by the computing device to further cause the computing device to receive, by the computer program product, a first natural language expression in a user interface.