Efficient probabilistic reasoning over semantic data

• US 8,751,433 B2
• Filed: 12/15/2010
• Issued: 06/10/2014
• Est. Priority Date: 12/15/2010
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bowers, Stuart M., Jackson, Thomas E., Vega, Silvia C., Karkanias, Chris D., Brown, Allen L. Jr., Campbell, David G., Aust, Brian S.
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): OLUDE AFOLABI, OLATOYOSI
• Application Number:
  US12/968,289
• Publication Number:
  US 20120158636A1
• Time in Patent Office: 1,273 Days
• Field of Search: 706/50, 726/1, 726/2, 707/100
• US Class Current: 706/50
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A semantic reasoning engine is described for performing probabilistic reasoning over a semantic graph in a time-efficient and viable manner. The semantic reasoning engine includes a data store that provides the semantic graph, where the semantic graph is formed by a plurality of concepts connected together via probabilistic assertions. The semantic reasoning engine operates by providing an answer to a query by recursively collapsing the semantic graph based on at least one collapsing rule.

Claims

1. A method for performing probabilistic reasoning over a semantic graph, the semantic graph formed by a plurality of concepts connected together via probabilistic assertions, the method comprising:

receiving a query at a computing device;

identifying, by the computing device, edges within the semantic graph that can be collapsed based on one or more collapsing rules, to provide identified edges, wherein;

the identified edges belong to at least one path through the semantic graph that addresses the query, and

said one or more collapsing rules include a series-type collapsing rule specifying that two edges can be combined if the two edges are connected in series in a manner that is independent of other edges in the semantic graph;

collapsing, by the computing device, the identified edges into a single edge having a resultant probability associated therewith;

repeating, by the computing device, said identifying and said collapsing until no additional collapsible edges are identified in the semantic graph, to provide a remaining graph; and

generating an answer to the query based on the remaining graph.

2. The method of claim 1, further comprising;

expressing, by the computing device, the query in a form which is a template for said at least one path through the semantic graph.

3. The method of claim 1, further comprising:

extracting, by the computing device, the semantic graph from a larger graph by removing extraneous semantic content from the larger graph that is not pertinent to the query.

4. The method of claim 1, wherein said one or more collapsing rules further include a parallel-type collapsing rule specifying that two edges can be combined if the two edges are connected in parallel in a manner that is independent of other edges in the semantic graph.

5. The method of claim 4, wherein said identifying comprises determining whether there are edges that satisfy the series-type collapsing rule, and if no edges are found that satisfy the series-type collapsing rule, determining whether there are edges that satisfy the parallel-type collapsing rule.

6. The method of claim 1, wherein the remaining graph has no non-collapsed edges, in which case the answer is provided by a probability associated with a final edge in the remaining graph.

7. The method of claim 1, wherein the remaining graph has non-collapsed edges, and wherein the method further comprises:

identifying, by the computing device, paths that can be taken through the remaining graph to reach the answer;

identifying, by the computing device, world states associated with the paths by enumerating different truth and false states associated with the paths;

identifying, by the computing device, total probabilities associated with the respective world states; and

summing, by the computing device, the probabilities to produce the answer.

8. The method of claim 1, wherein the semantic graph and the query pertain to a health-related domain.

9. The method of claim 1, further comprising:

receiving, by the computing device, semantic data from at least one source; and

updating, by the computing device, the semantic graph based on the semantic data.

10. A computing device for performing probabilistic reasoning over a semantic graph, the computing device comprising:

a processor configured to execute computer-executable instructions; and

memory storing computer-executable instructions for;

providing a semantic graph formed by a plurality of concepts connected together via probabilistic assertions;

receiving a query;

identifying edges within the semantic graph that can be collapsed based on one or more collapsing rules, to provide identified edges, wherein;

the identified edges belong to at least one path through the semantic graph that addresses the query, and

said one or more collapsing rules include a series-type collapsing rule specifying that two edges can be combined if the two edges are connected in series in a manner that is independent of other edges in the semantic graph;

collapsing the identified edges into a single edge having a resultant probability associated therewith;

repeating said identifying and said collapsing until no additional collapsible edges are identified in the semantic graph, to provide a remaining graph; and

generating an answer to the query based on the remaining graph.

11. The computing device of claim 10, wherein the memory further stores computer-executable instructions to express the query in a form which is a template of at least one path through the semantic graph that addresses the query.

12. The computing device of claim 10, wherein the memory further stores computer-executable instructions to extract the semantic graph from a larger graph by removing extraneous content from the larger graph that does not have a bearing on the query.

13. The computing device of claim 10, wherein said one or more collapsing rules further include a parallel-type collapsing rule specifying that two edges can be combined if the two edges are connected in parallel in a manner that is independent of other edges in the semantic graph.

14. The computing device of claim 10, wherein the remaining graph has non-collapsed edges, and wherein the memory further stores computer-executable instructions for:

identifying paths that can be taken through the remaining graph to reach the answer;

identifying world states associated with the paths by enumerating different truth and false states associated with the paths;

identifying total probabilities associated with the respective world states; and

summing the probabilities to produce the answer.

15. A computer-readable storage device storing computer-executable instructions that, when executed by one or more processing devices of a computing device, causes the computing device to perform a method comprising:

receiving a query;

providing a semantic graph formed by a plurality of concepts connected together via probabilistic assertions;

identifying edges within the semantic graph that can be collapsed based on one or more collapsing rules, to provide identified edges, wherein;

the identified edges belong to at least one path through the semantic graph that addresses the query, and

said one or more collapsing rules include a series-type collapsing rule specifying that two edges can be combined if the two edges are connected in series in a manner that is independent of other edges in the semantic graph;

collapsing the identified edges into a single edge having a resultant probability associated therewith,

repeating said identifying and said collapsing until no additional collapsible edges are identified in the semantic graph, to yield a remaining graph; and

generating an answer to the query based on a the remaining graph.

16. The computer-readable storage device of claim 15, wherein the remaining graph has non-collapsed edges, and further storing computer-executable instructions for:

identifying paths that can be taken through the remaining graph to reach the answer;

identifying world states associated with the paths by enumerating different truth and false states associated with the paths;

identifying total probabilities associated with the respective world states; and

summing the probabilities to produce the answer.

17. The computer-readable storage device of claim 15, wherein said one or more collapsing rules further include a parallel-type collapsing rule specifying that two edges can be combined if the two edges are connected in parallel in a manner that is independent of other edges in the semantic graph.

18. The computer-readable storage device of claim 17, wherein said identifying comprises determining whether there are edges that satisfy the series-type collapsing rule, and if no edges are found that satisfy the series-type collapsing rule, determining whether there are edges that satisfy the parallel-type collapsing rule.

19. The computer-readable storage device of claim 15, further storing computer-executable instructions for expressing the query in a form which is a template of at least one path through the semantic graph that addresses the query.

20. The computer-readable storage device of claim 15, further storing computer-executable instructions for extracting the semantic graph from a larger graph by removing extraneous content from the larger graph that does not have a bearing on the query.