UTILIZING LARGE-SCALE KNOWLEDGE GRAPHS TO SUPPORT INFERENCE AT SCALE AND EXPLANATION GENERATION

• US 20150379414A1
• Filed: 11/24/2014
• Published: 12/31/2015
• Est. Priority Date: 06/27/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Yeh, Peter Zei-Chan, Ratnaparkhi, Adwait, Douglas, Benjamin Birch, Jarrold, William Lawrence
• Granted Patent: US 10,402,453 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

Aspects discussed herein present a solution for utilizing large-scale knowledge graphs for inference at scale and generating explanations for the conclusions. In some embodiments, aspects discussed herein learn inference paths from a knowledge graph and determine a confidence score for each inference path. Aspects discussed herein may apply the inference paths to the knowledge graph to improve database lookup, keyword searches, inferences, etc. Aspects discussed herein may generate a natural language explanation for each conclusion or result from one or more inference paths that led to that conclusion or result. Aspects discussed herein may present the best conclusions or results to the user based on selection strategies. The presented results or conclusions may include generated natural language explanations rather than links to documents with word occurrences highlighted.

Claims

1. An apparatus comprising:

a processor;

a memory for storing computer readable instructions that, when executed by the processor, cause the apparatus to;

traverse a knowledge graph using a plurality of start instances and a plurality of associated end instances to produce an initial set of instance-level paths, wherein each traversal of the knowledge graph begins at a start instance, of the plurality of start instances, and ends at an associated end instance of the plurality of ending instances;

activate a subset of the initial set of instance-level paths;

iteratively generate a plurality of subsequent sets of instance-level paths respectively using a previously activated subset of instance-level paths of a plurality of activated subsets of instance-level paths, wherein a first subsequent set of instance-level paths is activated using the activated subset of the initial set of instance-level paths, wherein the activated subset of the initial set of instance-level paths is one of the plurality of activated subsets of instance-level paths;

generalize an inference path from a plurality of activated instance-level paths from one or more of the plurality of activated subsets of instance-level paths; and

associate a natural language explanation template with the inference path.

2. The apparatus of claim 1, wherein the knowledge graph comprises a plurality of nodes connected by a plurality of relations.

3. The apparatus of claim 1, wherein the traversal of the knowledge graph comprises a depth-bounded breadth-first traversal of the knowledge graph.

4. The apparatus of claim 1, wherein the computer readable instructions, when executed, further causes the apparatus to:

generate a score for each instance-level path of the initial set of instance-level paths based on a measure of strength of association between consecutive edges of a respective instance-level path of the initial set of instance-level paths, a frequency of an edge sequence of the respective instance-level path, and a path length of the respective instance-level path.

5. The apparatus of claim 4, wherein each score reflects a preference for stronger associations between the consecutive edges, a higher frequency of the edge sequence, and a shorter path length.

6. The apparatus of claim 5, wherein the computer readable instructions, when executed, further causes the apparatus to:

select one or more instance-level paths of the initial set of instance-level paths for activation based on a respective Z-score of each of the one or more instance-level paths of the initial set of instance-level paths being greater than or equal to a threshold, wherein the respective Z-score accounts for the score of the respective instance-level path.

7. The apparatus of claim 1,

wherein the generation of the first subsequent set of instance-level paths using the activated subset of the initial set of instance-level paths is based on a first set of instances of the knowledge graph that are associated with a first type and a second set of instances of the knowledge graph that are associated with a second type,

wherein the plurality of start instances, of the activated subset of the initial set of instance-level paths, are associated with the first type and the plurality of associated end instances, of the activated subset of the initial set of instance-level paths, are associated with the second type, and

wherein the first set of instances and the second set of instances have not been previously used to generate instance-level paths.

8. The apparatus of claim 1, wherein the computer readable instructions, when executed, further causes the apparatus to:

determine an activation score for each instance-level path of the first subsequent set of instance-level paths based on one or more of a measure of strength of association between consecutive edges of a corresponding instance-level path of the first subsequent set of instance-level paths, a frequency of edge sequence of the corresponding instance-level path, a path length of the corresponding instance-level path, a measure of similarity of the corresponding instance-level path with each instance-level path of the initial set of instance-level paths, and a measure of entropy of the corresponding instance-level path with one or more activated instance-level paths of the activated subset of the initial set of instance-level paths.

9. The apparatus of claim 8, wherein the computer readable instructions, when executed, further causes the apparatus to:

activate a subset of the first subsequent set of instance-level paths based on a Z-score of a respective instance-level path of the first subsequent set of instance-level paths being greater than or equal to a threshold modified by an inverse decay, wherein the Z-score accounts for the activation score of the respective instance-level path of the first subsequent set of the instance-level paths.

10. The apparatus of claim 9, wherein the computer readable instructions that, when executed, cause the apparatus to iteratively generate the plurality of subsequent sets of instance-level paths further cause the apparatus to:

generate a second subsequent set of instance-level paths using the activated subset of the first subsequent set of instance-level paths;

activate a subset of the second subsequent set of instance-level paths; and

generate a third subsequent set of instance-level paths using the activated subset of the second subsequent set of instance level paths.

11. The apparatus of claim 1, wherein the computer readable instructions, when executed, further cause the apparatus to:

activate a subset of the first subsequent set of instance-level paths,

group at least one instance-level path of the activated subset of the initial set of instance-level paths that comprises an edge sequence and at least one instance-level path of the activated subset of the first subsequent set of instance-level paths that comprises the edge sequence.

12. The apparatus of claim 1,

wherein a type of a first instance of one activated instance-level path, of the plurality of activated instance-level paths, matches a type of a first instance of each other activated instance-level path of the plurality of activated instance-level paths;

and

wherein a type of an end instance of the one activated instance-level path, of the plurality of activated instance-level paths, matches a type of an end instance of each of the other activated instance-level paths of the plurality of activated instance-level paths.

13. An apparatus comprising:

a processor;

a memory for storing computer readable instructions that, when executed by the processor, cause the apparatus to;

generate a first set of instance-level paths by applying training examples to a knowledge graph;

generate a second set of instance-level paths using an activated subset of the first set of instance-level paths;

grouping a first activated instance-level path of the activated subset of the first set of instance-level paths and a second activated instance-level path of the second set of instance-level paths into a group, wherein the first activated instance-level path comprises an edge sequence and the second activated instance-level path comprises the edge sequence; and

producing an inference path for the group.

14. The apparatus of claim 13, wherein the computer readable instructions, when executed, further causes the apparatus to:

generate a first activation score for the first activated instance-level path and a second activation score for the second activated instance-level path; and

generate a group score based on a standard deviation of at least the first activation score and the second activation score.

15. The apparatus of claim 13,

wherein a type of a start instance of the first activated instance-level path matches a type of a start instance of the second activated instance-level path, and

wherein a type of an end instance of the first activated instance-level path matches a type of an end instance of the second activated instance-level path.

16. The apparatus of claim 13, wherein the computer readable instructions, when executed, further causes the apparatus to:

determining an activation score for an instance-level path of the second set of instance-level paths based on one or more of a measure of strength of association between consecutive edges of the instance-level path, a frequency of edge sequence of the instance-level path, a path length of the instance-level path, a measure of similarity of the instance-level path with the activated subset of the first set of instance-level paths, and a measure of entropy of the instance-level path with the activated subset of the first set of instance-level paths.

activating the instance-level path to produce the second activated instance-level path based on a Z-score filter that uses the activation score as input.

17. An apparatus comprising:

a processor;

a memory for storing computer readable instructions that, when executed by the processor, cause the apparatus to;

monitor an input utterance for a plurality of inference triggers respectively associated with a plurality of inference paths;

determine that an inference trigger of the plurality of inference triggers have been found in the input utterance;

traverse a knowledge graph comprising a plurality nodes connected by a plurality of relations using the inference path associated with the inference trigger; and

in response to a determination that an instance of the knowledge graph has a type that matches a type of an end node of the inference path, recording the instance as a conclusion of applying the inference path to the knowledge graph.

18. The apparatus of claim 17, wherein the computer readable instructions, when executed, further causes the apparatus to:

recording each instance of the knowledge graph traversed using the inference path.

19. The apparatus of claim 18, wherein the computer readable instructions, when executed, further causes the apparatus to:

determine a natural language template for the inference path;

instantiate the inference path with the recorded instances; and

instantiate the natural language template with the instantiated inference path to generate an explanation.

20. The apparatus of claim 19, wherein the computer readable instructions, when executed, further causes the apparatus to:

displaying the explanation to a user without showing highlighted word occurrences.