# US 8,751,433 B2 · Efficient probabilistic reasoning over semantic data > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,433 B2 - Document ID: US8751433B2 - Status: Granted - Kind: B2 - Application number: 12/968,289 - Filed: 2010-12-15 - Published: 2012-06-21 - Granted: 2014-06-10 - Earliest claimed: 2010-12-15 - Assignees: Microsoft Corporation - Applicants: Stuart M. Bowers; Thomas E. Jackson; Silvia C. Vega; Chris D. Karkanias; Allen L. Brown, Jr.; David G. Campbell; Brian S. Aust - Inventors: Stuart M. Bowers; Thomas E. Jackson; Silvia C. Vega; Chris D. Karkanias; Allen L. Brown, Jr.; David G. Campbell; Brian S. Aust - Web page: https://patentgrep.com/patent/US8751433B2 ## CPC - G06N 5/02: Knowledge representation; Symbolic representation - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) The method of claim 1, wherein the semantic graph and the query pertain to a health-related domain. ### Claim 9 (depends on 1) 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. ### Claim 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. ### Claim 11 (depends on 10) 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. ### Claim 12 (depends on 10) 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. ### Claim 13 (depends on 10) 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. ### Claim 14 (depends on 10) 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. ### Claim 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 15) 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. ### Claim 18 (depends on 17) 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. ### Claim 19 (depends on 15) 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. ### Claim 20 (depends on 15) 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.