Belief networks with decision graphs

• US 6,154,736 A
• Filed: 07/30/1997
• Issued: 11/28/2000
• Est. Priority Date: 07/30/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meek, Christopher A., Chickering, David Maxwell, Heckerman, David
• Primary Examiner(s): Stamber, Eric W.
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US08/902,759
• Time in Patent Office: 1,217 Days
• Field of Search: 706/12, 706/46, 706/59, 706/61, 706/45
• US Class Current: 706/59
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

An improved belief network is provided for assisting users in making decisions. The improved belief network utilizes a decision graph in each of its nodes to store the probabilities for that node. A decision graph is a much more flexible and efficient data structure for storing probabilities than either a tree or a table, because a decision graph can reflect any equivalence relationships between the probabilities and because leaf nodes having equivalent probabilities need not be duplicated. Additionally, by being able to reflect an equivalency relationship, multiple paths (or combinations of the parent values) refer to the same probability, which yields a more accurate probability.

Claims

1. A method for forming an enhanced version of a belief network for subsequent use in assisting a user, through computer-aided probabilistic inferences, in a decision-making process, the method being implemented in a computer system having a processor and a storage device connected to the processor, wherein the storage device stores computer executable instructions and a data structure, the data structure storing the enhanced version of the belief network, the method comprising the steps, implemented by the processor through execution of the instructions, of:

receiving an initial version of the belief network, the belief network probabilistically relating a plurality of different input variables to a plurality of different output decisions, the initial version of the belief network having network nodes each with a probability and each having a decision graph data structure with a graph node used for storing the probability;

for each network node in the initial belief network;

accessing a database containing cases of real-world instances of the decision-making process, each case containing a value for the graph node of the decision graph;

counting a number of values for the graph node contained in the cases;

for each graph node that is a leaf graph node in the graph data structure,

performing a complete split on the leaf graph node to generate a plurality of complete split decision graphs;

performing a binary split on the leaf graph node to generate a plurality of binary split decision graphs; and

performing a merge on the leaf graph node to generate a plurality of merge decision graphs;

scoring each of the complete split decision graphs, the binary split decision graphs, and the merge decision graphs for goodness at reflecting the cases using the counted number of values;

determining which among the complete split decision graphs, the binary split decision graphs, and the merge decision graphs is a graph with a greatest score and retaining the graph with the greatest score so as to define a retained graph;

determining which network node is a best network node having the retained graph with a best score among the retained graphs;

storing the retained graph of the best network node into the best network node for use in accessing the probability of the best network node; and

adjusting the initial version of the belief network responsive to storing the retained graph to create the enhanced version of the belief network for storage in the data structure in the storage device for subsequent use in assisting the user, through the computer-aided probabilistic inferences, with the decision-making process.

2. The method of claim 1 wherein the graph nodes in the best network node correspond to a plurality of the network nodes in the initial belief network and the method further comprises the steps of:

determining whether the retained graph for the best network node was generated such that a graph node was added to the retained graph in the best network node where the network node that corresponds to the added graph node is not a parent to the best network node in the belief network; and

when it is determined that the retained graph was generated such that the graph node was added to the retained graph in the best network node where the network node that corresponds to the added graph node is not a parent to the best network node in the belief network,

adding an arc in the belief network from the network node that corresponds to the added graph node to the best network node.

3. The method of claim 1 wherein the utilizing step includes performing web analysis.

4. The method of claim 1 wherein the adjusting step includes adding an arc such that a cycle is introduced into the enhanced version of the belief network.

5. A method for performing probabilistic inference in a computer system, the computer system having a processor and a storage device connected to the processor, wherein the storage device stores computer executable instructions and a data structure, the data structure storing a belief network, the belief network probabilistically relating a plurality of different input variables to a plurality of different output decisions, wherein the belief network comprises nodes and arcs indicating relationships between the nodes, a first of the nodes having a decision graph with leaf vertices containing probabilities, one of the leaf vertices being an equivalence vertex such that the decision graph has a plurality of paths to the equivalence vertex, comprising the steps, implemented by the processor through execution of the instructions, of:

receiving an observation for a second of the nodes of the belief network; and

accessing the decision graph of the first of the nodes to perform probabilistic inference, for a given one of the input variables, using the probability in the equivalence vertex of the decision graph in the first node and the observation so as to select one of the output decisions; and

providing the selected one decision as an output of the system.

6. The method of claim 5 wherein the receiving step includes receiving a characteristic of a user and wherein the accessing step accesses the decision graph of the first node to determine whether the user would likely like to visit a category of web sites based on the characteristic.

7. A computer-readable medium having computer executable instructions stored therein, said instructions being executed by a computer, for performing the steps of claim 6.

8. In a computer system having a processor and a storage device connected to the processor, wherein the storage device stores computer executable instructions and a data structure, the data structure storing a belief network, wherein the belief network probabilistically relates a plurality of different input variables to a plurality of different output decisions, a method for use in the system for scoring the belief network, wherein the belief network has nodes and arcs indicating relationships between the nodes, a plurality of the nodes having decision graphs containing probabilities for rendering inferences when given an observation for another node, and the belief network provides probabilistic based decision-support to a user of the system in a field of decision making, comprising the steps, implemented through the computer executable instructions, of:

accessing a database having observations for the nodes of the belief network representing instances of real-world decisions relevant to a predetermined field of decision making;

scoring the decision graph in each node for goodness at reflecting the observations in the accessed database, wherein the decision graph reflects relationships among the nodes of the belief network, one of the reflected relationships being an equivalency relationship where a plurality of paths through the decision graph refer to a common probability, and wherein the scoring is performed to determine whether the observations indicate that the decision graph should reflect additional relationships; and

combining the scores of the decision graphs to generate a score for the belief network, wherein the score reflects how accurately the belief network represents a decision making process between the input variables and the output decisions.

9. The method of claim 8 wherein the scoring step includes scoring the decision graphs based on expert data received from an expert in the field of the decision making.

10. The method of claim 8, further including the step of adjusting at least one of the decision graphs to improve the score of the at least one decision graph.

11. The method of claim 10, further including the step of adjusting the belief network when the at least one decision graph indicates that a relationship between the nodes of the belief network exists that is not reflected by the belief network.

12. The method of claim 11 wherein the step of adjusting the belief network includes adding an arc that introduces a cycle into the belief network to create a cyclic directed graph.

13. The method of claim 12, further including the step of performing probabilistic inference using the cyclic directed graph.

14. The method of claim 8 wherein the decision graph has vertices with a plurality of states, wherein a plurality of the vertices correspond to the nodes of the belief network, wherein a plurality of the vertices are leaf vertices, wherein the database contains observations for the states of the vertices, and wherein the scoring step includes the steps of:

for each node of the belief network,

for each leaf vertex of the decision graph for the node of the belief network,

dividing a first equivalent sample size for the vertex and the leaf vertex by a sum of a count of a number of times that the vertex and the leaf vertex are contained in the observations; and

for each state of the leaf vertex,

dividing a sum of a count of a number of times that the state of the leaf vertex of the decision graph of the node of the belief network appears in the observations and a second equivalent sample size for the state of the leaf vertex of the decision graph of the node of the belief network by the second equivalent sample size.

15. A computer-readable medium having executable instructions stored therein, said instructions being executed by a computer, for performing the steps of claim 8.

16. In a computer system having a processor and a storage device connected to the processor, wherein the storage device stores computer executable instructions and a data structure, the data structure storing a belief network, the belief network probabilistically relating a plurality of different input variables to a plurality of different output decisions, a method for use in the system for improving accuracy of the belief network, belief network having nodes and arcs indicating relationships between the nodes, each node having a decision graph containing probabilities for rendering inferences, comprising the steps, implemented by the processor through execution of the instructions, of:

scoring one of the decision graphs in one of the nodes of the belief network to determine goodness at rendering inferences; and

adjusting the scored decision graph to improve the score of the scored decision graph and to improve the accuracy of the belief network such that the adjustment creates a plurality of paths in the scored decision graph that refer to a common probability such that given one of the input variables, as an observation, probabilistic inference undertaken by the system and based on the stored belief network, will yield through enhanced accuracy, one of the output decisions.

17. The method of claim 16 wherein the nodes of the belief network have states, wherein the decision graph has a plurality of leaf nodes, wherein the adjusting step includes replacing one of the leaf nodes of the decision graph with a corresponding node that corresponds to one of the nodes of the belief network and creating a leaf node connected to the corresponding node for each of the states of the node of the belief network that corresponds to the corresponding node.

18. The method of claim 16 wherein the nodes of the belief network have states, wherein the decision graph has a plurality of leaf nodes, wherein the adjusting step includes replacing one of the leaf nodes of the decision graph with a corresponding node that corresponds to one of the nodes of the belief network and creating two leaf nodes that are each connected to the corresponding node, a first of the created leaf nodes representing one of the states of the node of the belief network that corresponds to the corresponding node and a second of the created leaf nodes representing remaining states of the node of the belief network that corresponds to the corresponding node.

19. The method of claim 16 wherein the decision graph contains a plurality of leaf nodes, and wherein the adjusting step includes merging two of the leaf nodes together to form a single leaf node.

20. The method of claim 16 wherein the decision graph has nodes corresponding to a plurality of the nodes of the belief network, the method further including the step of when the decision graph adjustment adds a node to the decision graph whose corresponding node in the belief network is not a parent to the at least one of the nodes in the belief network, updating the belief network to indicate that a value of the corresponding node causally influences the at least one of the nodes in the belief network.

21. The method of claim 20 wherein the update to the belief network introduces a cycle.

22. The method of claim 16 wherein the adjusting step includes adjusting the decision graph to generate a plurality of candidate decision graphs, scoring the generated decision graphs, determining which among the generated decision graphs has a best score, and selecting the decision graph having the best score for use in the one node of the belief network.

23. A computer-readable medium having computer executable instructions stored therein, said instructions being executed by a computer, for performing the steps of claim 16.

24. A computer-readable media containing a data structure for use, by a computer, in performing computer-implemented probabilistic inferences, to support decision-making by a user, the data structure storing a belief network that comprises nodes and arcs connecting the nodes, the nodes containing:

a decision graph with leaf nodes containing probabilities, wherein the decision graph has a path to each leaf node, wherein one of the leaf nodes more than one path to the one leaf node, the decision graph used for accessing the probabilities within the leaf nodes to perform probabilistic inference.

25. A computer system for making probabilistic inferences based on a belief network so as to assist a user in making a decision in a decision-making field, comprising:

a processor; and

a storage device, connected to the processor and storing computer executable instructions and a data structure, the data structure storing a belief network, the belief network probabilistically relating plurality of different input variables to a plurality of different output decisions;

wherein the storage device further stores;

expert knowledge comprising an initial belief network with nodes and a decision graph in each node containing probabilities, each decision graph having nodes corresponding to a plurality of the nodes of the belief network; and

a database containing cases of real-world instances of decisions made in the decision-making field;

wherein the processor, in response to execution of the instructions;

generates the stored belief network by receiving an initial version of the belief network, scoring each decision graph in the initial version of the belief network based on the cases in the database, adjusting at least one of the decision graphs to improve the score for the at least one of the decision graphs, and adjusting the initial version of the belief network so as to form an enhanced version of the belief network that reflects the adjustment to the at least one of the decision graphs when the adjustment indicates that a relationship in the enhanced version of the belief network exists that the initial belief network does not reflect, and for storing the enhanced version of the belief network as the stored belief network; and

receives an observation for at least one of the input variables in the belief network, and performs, using the stored belief network, probabilistic inference responsive to the observation so as to specify one of the output decisions to the user for assisting the user in making the decision.

26. The computer system of claim 25 wherein the processor, in response to the executable instructions, receives characteristics of the user and determines whether the user would likely visit a web site.

27. The computer system of claim 25 wherein the at least one of the decision graphs has a leaf node and wherein the processor, in response to the stored instructions, adjusts the at least one of the decision graphs by performing a complete split on the leaf node.

28. The computer system of claim 25 wherein the at least one of the decision graphs has a leaf node and wherein the processor, in response to the stored instructions, adjusts the at least one of the decision graphs by performing a binary split on the leaf node.

29. The computer system of claim 25 wherein the at least one of the decision graphs has a plurality of leaf nodes and wherein the processor, in response to the stored instructions, adjusts the at least one of the decision graphs by merging two of the leaf nodes.

30. The computer system of claim 25 wherein the processor, in response to the stored instructions, adjusts the initial version of the belief network such that a cycle is introduced into the enhanced version of the belief network.

31. In a computer having a processor and a storage device connected to the processor, wherein the storage device stores computer executable instructions and a data structure, the data structure storing a belief network, wherein the belief network probabilistically relates a plurality of different input variables to a plurality of different output decisions, a method for use in the system for assisting a user in making a decision, comprising the steps, implemented by the processor through execution of the instructions, of:

receiving the belief network having a graph data structure with nodes and arcs indicating relationships between the nodes, a plurality of the nodes and at least one of the arcs forming a cycle, each node having a probability;

receiving an observation for a first of the nodes; and

performing probabilistic inference with the received observation, using the stored belief network, by accessing the probability in a second of the nodes, the second of the nodes being part of the cycle in the graph data structure so as to select one of the output decisions and provide the one output decision as output to the user.

32. The method of claim 31 wherein the step of receiving an observation includes receiving a characteristic of a user, and wherein the step of performing probabilistic inference includes determining whether the user would likely visit a category of web sites.

33. The method of claim 31 wherein the nodes of the graph data structure have a plurality of states, wherein a plurality of the nodes are parent nodes and each parent node has an arc to a child node to indicate that the parent node influences the state of the child node, wherein the step of receiving an observation includes receiving an observation for the state of all of the parent nodes to perform probabilistic inference for one of the child nodes.

34. The method of claim 33 wherein the one child node has a probability for each combination of states of the parent nodes of the one child node, wherein the received observations reflect a combination of states of the parent nodes of the one child node, and wherein the step of performing probabilistic inference includes selecting the probability for the states of the parent nodes of the one child node reflected by the received observations.

35. A computer-readable medium having computer executable instructions stored therein, said instructions being executed by a computer, for performing the steps of claim 31.

37. The computer system of claim 35 wherein the directed acyclic graph is cyclic.

36. A computer system for making probabilistic inferences based on a belief network so as to assist a user making a decision in a predefined decision-making field, comprising:

a processor; and

a storage device, connected to the processor and storing computer executable instructions and a data structure, the data structure storing a belief network, the belief network probabilistically relating a plurality of different input variables to a plurality of different output decisions, the belief network having a directed acyclic graph with nodes and arcs reflecting relationships between the nodes, each node having a decision graph containing a probability, at least one of the decision graphs having a plurality of paths to the probability of the at least one decision graph;

wherein the processor, in response to the executable instructions;

receives a request containing a value for one of the nodes, and accesses the directed acyclic graph with the value of the one node to perform probabilistic inference so as to select one of the output decisions and provide the one output decision as output.

38. A method for forming an enhanced version of a belief network for subsequent use in assisting a user, through computer-aided probabilistic inferences, in a decision-making process, the method being implemented in a computer system having a processor and a storage device connected to the processor, wherein the storage device stores computer executable instructions and a data structure, the data structure storing the enhanced version of the belief network, the method comprising the steps, implemented by the processor through execution of the instructions, of:

receiving an initial version of the belief network with nodes and arcs indicating relationships between the nodes, each node containing a graph with probabilities;

adjusting one of the graphs to improve an ability of the one graph to perform probabilistic inference, the graph indicating a relationship among the nodes of the belief network that is not reflected in the initial version of the belief network; and

adjusting the initial version of the belief network to reflect the indicated relationship so as to generate the enhanced version of the belief network.

39. A computer-readable medium having computer executable instructions stored therein, said instructions being executed by a computer, for performing the steps of claim 38.

40. A method for forming an enhanced version of a belief network for subsequent use in assisting a user, through computer-aided probabilistic inferences, in a decision-making process, the method being implemented in a computer system having a processor and a storage device connected to the processor, wherein the storage device stores computer executable instructions and a data structure, the data structure storing the enhanced version of the belief network, the method comprising the steps, implemented by the processor through execution of the instructions, of:

receiving an initial version of the belief network with nodes and arcs indicating relationships between the nodes, each node having an associated graph containing probabilities;

for each of the nodes;

adjusting the associated graph to create candidate graphs;

scoring each candidate graph to determine goodness at performing probabilistic inference; and

identifying which one among the stored candidate graphs is a best graph with a greatest score among the stored candidate graphs; and

whenever the best graph contains a probabilistic relationship between the input variables and output decisions that does not exist in the initial version of the belief network, updating the initial version of the belief network by storing within each of the nodes in the initial version of the belief network the associated candidate graph that is the best graph for said each node so as to yield the enhanced version of the belief network.

41. A computer-readable medium having computer executable instructions stored therein, said instructions being executed by a computer, for performing the steps of claim 40.