Semantic graph traversal for recognition of inferred clauses within natural language inputs
Embodiments described herein provide a more flexible, effective, and computationally efficient means for determining multiple intents within a natural language input. Some methods rely on specifically trained machine learning classifiers to determine multiple intents within a natural language input. These classifiers require a large amount of labelled training data in order to work effectively, and are generally only applicable to determining specific types of intents (e.g., a specifically selected set of potential inputs). In contrast, the embodiments described herein avoid the use of specifically trained classifiers by determining inferred clauses from a semantic graph of the input. This allows the methods described herein to function more efficiently and over a wider variety of potential inputs.
1. A computer-implemented natural language processing method comprising:
obtaining a semantic graph representing semantic meaning of an initial set of words, the semantic graph comprising: a plurality of nodes, each node representing a span of one or more words taken from the initial set of words and having a corresponding shared semantic role within the initial set of words; and one or more edges, each edge connecting semantically linked nodes and each edge being labelled with a corresponding semantic relationship, wherein the semantic graph forms a tree having one or more root nodes and one or more leaf nodes;
for each root node within the semantic graph, forming a set of one or more inferred clauses for the root node by:
determining every possible combination of the root node and its descendants, wherein each combination is selected such that the nodes within the combination form a contiguous series of connected nodes within the semantic graph and wherein every possible descendent of the root node from the semantic graph is selected with the exception that, for each parent node that is a descendent of the root node, only one child node is selected for each type of semantic relationship that the parent node has with its one or more child nodes; and
forming the set of one or more inferred clauses for the root node by combining the spans for each determined combination;
setting the one or more inferred clauses for the one or more root nodes to be a set of one or more inferred clauses for the initial set of words;
determining a response to the initial set of words based on at least one of the one or more inferred clauses for the initial set of words; and
outputting the determined response.
2. The method of claim 1 , wherein forming a set of one or more inferred clauses for the root node includes:
for each leaf node that is a descendent of the respective root node, setting an inferred clause for that leaf node to include the span for that leaf node; and
for each parent node within the semantic graph, starting from the one or more parent nodes of the respective leaf nodes and moving up the semantic graph to the respective root node, determining a set of one or more inferred clauses for the respective parent node by:
determining each possible combination of the respective parent node and the one or more child nodes of the respective parent node, where only one child node is selected for each semantic relationship relative to the respective parent node; and
for each combination of the respective parent node and the one or more child nodes of the respective parent node, combining the spans for the combination to form an inferred clause for the respective parent node.
3. The method of claim 2 , wherein determining each possible combination of the respective parent node and the one or more child nodes of the respective parent node comprises grouping the respective parent node and the one or more child nodes according to their semantic role and determining the Cartesian product across the groups.
4. The method of claim 1 , wherein combining the spans for each determined combination comprises, for each determined combination, forming a span that includes each of the spans for each node within the combination.
5. The method of claim 1 , wherein determining a response to the initial set of words comprises:
for each inferred clause for the initial set of words, determining an input corresponding to the inferred clause; and
determining the response based on the determined inputs.
6. The method of claim 5 , wherein determining an input corresponding to the inferred clause comprises:
for each of a set of predefined inputs, determining a semantic similarity between the inferred clause and the predefined input; and
selecting a corresponding predefined input based on the determined semantic similarities for the inferred clause.
7. The method of claim 5 , wherein determining an input corresponding to the inferred clause comprises applying a classifier to the inferred clause and selecting the input based on an output of the classifier.
8. The method of claim 1 , wherein the semantic graph includes one or more semantic relationships wherein the subject of the relationship is not constrained to be a verb node and one or more semantic relationships wherein the object of the relationship may be a verb node.
9. The method of claim 1 , wherein the semantic graph represents one or more semantic relationships including one or more of:
a conjunction between two noun nodes or two argument modifier nodes;
a combination of an auxiliary verb and a corresponding main verb or a corresponding further auxiliary verb;
an argument modifier node being an argument modifier for a noun node; and
a chain of verb nodes.
10. The method of claim 9 , wherein the one or more semantic relationships include a conjunction between two noun nodes or two argument modifier nodes and wherein any edges representing conjunctions within the semantic graph are ignored when forming the set of one or more inferred clauses for the each root node.
11. A non-transitory computer-readable medium including instructions that, when executed by a processor, cause the processor to perform the method of claim 1 .
12. A system including a processor and a memory, the memory including instructions that, when executed by the processor, cause the processor to perform the method of claim 1 .