Mixtures of bayesian networks with decision graphs

• US 6,408,290 B1
• Filed: 12/23/1998
• Issued: 06/18/2002
• Est. Priority Date: 12/04/1997
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meek, Christopher A., Chickering, David Maxwell, Heckerman, David Earl, Thiesson, Bo
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/220,200
• Time in Patent Office: 1,273 Days
• Field of Search: 706/10, 706/50, 706/52
• US Class Current: 706/52
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

One aspect of the invention is the construction of mixtures of Bayesian networks. Another aspect of the invention is the use of such mixtures of Bayesian networks to perform inferencing. A mixture of Bayesian networks (MBN) consists of plural hypothesis-specific Bayesian networks (HSBNs) having possibly hidden and observed variables. A common external hidden variable is associated with the MBN, but is not included in any of the HSBNs. The number of HSBNs in the MBN corresponds to the number of states of the common external hidden variable, and each HSBN is based upon the hypothesis that the common external hidden variable is in a corresponding one of those states. In one mode of the invention, the MBN having the highest MBN score is selected for use in performing inferencing. In another mode of the invention, some or all of the MBNs are retained as a collection of MBNs which perform inferencing in parallel, their outputs being weighted in accordance with the corresponding MBN scores and the MBN collection output being the weighted sum of all the MBN outputs. In one application of the invention, collaborative filtering may be performed by defining the observed variables to be choices made among a sample of users and the hidden variables to be the preferences of those users.

Claims

1. A method in a computer system for constructing a mixture of Bayesian networks (MBN), for use in assisting a user in a decision-making process based upon a set of observed data, said (MBN) comprising plural hypothesis-specific Bayesian networks, (HSBNs) having network nodes, each of said network nodes storing a set of probability parameters and structure representing probabilistic relationships among said network nodes, at least some of said network nodes having a decision graph data structure with multiple graph nodes encoding a probability distribution of the node given its parent nodes in the HSBN, said observed data comprising a database containing cases of instances of the decision-making process, each case containing a value for one of the graph nodes, said method comprising, for each one of said HSBNs:

conducting a parameter search for a set of changes in said probability parameters which improves the goodness of said one HSBN in predicting said observed data, and modifying the probability parameters of said one HSBN accordingly for each one of said HSBN;

conducting a structure search for a change in said structure which improves the goodness of said HSBN at predicting said observed data, and modifying the structure of said one HSBN accordingly, the step of conducting a structure search comprising, for each HSBN;

counting a number of values for said multiple graph nodes contained in the case of said observed data;

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;

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 node for use in accessing the probability of the best node.

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 HSBN, the method further including 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 where the network node that corresponds to the added graph node is not a parent to the best network node in the HSBN; and

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 HSBN,

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

3. The method of claim 1, wherein the step of scoring comprises:

computing from said observed data expected complete model sufficient statistics (ECMSS);

computing from said ECMSS sufficient statistics for said one HSBN;

computing a structure score from said sufficient statistics.

4. In a decision support system that receives, as an input on a signal-bearing medium, data representing observations, an apparatus for performing probabilistic inference in a computer system, comprising:

a processor;

a memory having executable instructions stored therein;

a belief network comprising a mixture of Bayesian networks (MBN), said MBN comprising plural hypothesis-specific Bayesian networks (HSBNs), said MBN modeling a case of a hidden variable having a number of states, each HSBN corresponding to a hypothesis that said hidden variable is in a corresponding one of said states, each HSBN having nodes and arcs indicating relationships between the nodes, a first of the nodes of each HSBN 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;

wherein said processor, in response to instructions stored in said memory;

for each HSBN, receives an observation on said signal-bearing medium for a second of the nodes of the HSBN; and

accesses the decision graph of the first of the nodes of the HSBN to perform probabilistic inference using the probability in the equivalence vertex of the decision graph in the first node and the observation.

5. The apparatus of claim 4 wherein said processor receives an observation for a second of the nodes of the HSBN, in that the processor receives a characteristic of a user and wherein said processor access the decision graph of the first of the nodes of the HSBN in that the processor 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.

6. In a decision support system that receives, on a signal-bearing medium, data representing observations, an apparatus for scoring a belief network comprising:

a processor;

a memory having executable instructions stored therein;

a mixture of Bayesian networks (MBN) stored in said memory and based upon a database comprising the observations received on the signal-bearing medium for the nodes of the belief network representing instances of real-world decisions made in the field of decision making, said MBN comprising plural hypothesis-specific Bayesian networks (HSBNs), said MBN modeling a case of a hidden variable having a number of states, each HSBN corresponding to a hypothesis that said hidden variable is in a corresponding one of said states, each HSBN having nodes and arcs indicating relationships between the nodes, a plurality of the nodes having decision graphs each encoding a probability distribution of the node given its parent nodes in the HSBN , the belief network for providing decision-support to a user in a field of decision making;

wherein said processor in response to said instructions, for each HSBN;

scores the decision graph in each node of the HSBN for goodness at reflecting the observations in the database, wherein the decision graph reflects relationships among the nodes of the HSBN, one of the reflected relationships being an equivalency relationship in which 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

combines the scores of the decision graphs to generate a score for the HSBN.

8. The apparatus of claim 6, wherein said processor further adjusts at least one of the decision graphs to improve the score of the at least one decision graph.

9. The apparatus of claim 8, wherein said processor further adjusts the HSBN when the at least one decision graph indicates that a relationship between the nodes of the HSBN exists that is not reflected by the HSBN.

10. The apparatus of claim 6 wherein the decision graph has vertices with a plurality of states, wherein a plurality of the vertices correspond to the nodes of the HSBN, wherein a plurality of the vertices are leaf vertices, wherein the database contains observations for the states of the vertices, and wherein said processor scores the decision graph in that the processor, for each node of the HSBN:

for each leaf vertex of the decision graph for the node of the belief network, divides 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, divides 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 HSBN 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 HSBN by the second equivalent sample size.

7. The apparatus of claim wherein said processor scores the decision graph in each node of the HSBN in that the processor scores the decision graphs based on expert data received from an expert in the field of the decision making.

11. In a decision support system that receives a set of observed data as an input on a signal-bearing medium, an apparatus for improving an accuracy of a belief network, the belief network comprising a mixture of Bayesian networks (MBN), said MBN comprising plural hypothesis-specific Bayesian networks (HSBNs), said MBN modeling a case of a hidden variable having a number of states, each HSBN corresponding to a hypothesis that said hidden variable is in a corresponding one of said states, each HSBN having network nodes and arcs indicating relationships between the network nodes, each node having a decision encoding a probability distribution of the node given its parent nodes in the HSBN, said apparatus comprising:

a processor;

a memory having executable instructions stored therein; and

wherein said processor, in response to instructions stored in memory, for each HSBN;

scores one of the decision graphs in one of the network nodes of the HSBN to determine goodness relative to said set of observed data at rendering inferences; and

adjusts the scored decision graph to improve the score of the scored decision graph and to improve the accuracy of the HSBN such that the adjustment creates a plurality of paths in the scored decision graph that refer to a common probability.

12. The apparatus of claim 11 wherein the nodes of the HSBN have states, wherein the decision graph has a plurality of leaf nodes, wherein said processor adjusts the scored decision graphs in that the processor replaces one of the leaf nodes of the decision graph with a leaf node that corresponds to one of the network nodes of the HSBN and creates a leaf node connected to the corresponding leaf node for each of the states of the network node of the HSBN that corresponds to the corresponding leaf node.

13. The apparatus of claim 12 wherein the nodes of the HSBN have states, wherein the decision graph has a plurality of leaf nodes, wherein said processor adjusts the scored decision graphs in that the processor replaces one of the leaf nodes of the decision graph with a leaf node that corresponds to one of the network nodes of the HSBN and creates two leaf nodes that are each connected to the corresponding leaf node, a first of the created leaf nodes representing one of the states of the network node of the HSBN that corresponds to the corresponding leaf node and a second of the created leaf nodes representing remaining states of the network node of the HSBN that corresponds to the corresponding leaf node.

14. The apparatus of claim 13 wherein the decision graph contains a plurality of leaf nodes, and wherein said processor adjusts the scored decision graphs in that the processor merges two of the leaf nodes together to form a single leaf node.

15. The apparatus of claim 11 wherein the decision graph has leaf nodes corresponding to a plurality of the network nodes of the HSBN, wherein the processor adjusts the scored decision graph in that the processor adds a leaf node to the decision graph whose corresponding network node in the HSBN is not a parent to the at least one of the network nodes in the HSBN, and updates the HSBN to indicate that a value of the corresponding network node causally influences the at least one of the network nodes in the HSBN.

16. The apparatus of claim 11 wherein said processor adjusts the decision graph in that the processor adjusts the decision graph to generate a plurality of candidate decision graphs, scores the generated decision graphs, determines which among the generated decision graphs has a best score, and selects the decision graph having the best score for use in the one node of the HSBN.

20. A computer-readable medium storing computer-executable instructions for carrying out the steps of claim 16.

17. In a decision support system that receives a set of observed data as an input on a signal-bearing medium, a method for constructing a mixture of Bayesian networks (MBN), for use in assisting a user in a decision-making process based upon the set of observed data, said MBN comprising plural hypothesis-specific Bayesian networks, (HSBNs) having network nodes, each of said network nodes storing a set of probability parameters and structure representing probabilistic relationships among said network nodes, at least some of said network nodes having a decision graph data structure with multiple graph nodes encoding a probability distribution of the node given its parent nodes in the HSBN, said observed data comprising a database containing cases of instances of the decision-making process, each case containing a value for one of the graph nodes, said method comprising:

performing a parameter search for a set of changes in said probability parameters which improves the goodness of said one HSBN in predicting said observed data, and modifying the probability parameters of said one HSBN accordingly for each one of said HSBNs;

conducting a structure search for a change in said structure which improves the goodness of said HSBN at predicting said observed data, and modifying the structure of said one HSBN accordingly, the conducting and modifying steps comprising;

counting a number of values for said multiple graph nodes contained in the cases of said observed data;

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;

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 node for use in accessing the probability of the best mode.

18. A computer readable medium storing computer-executable instructions for carrying out the steps of claim 17.

19. In a decision support system that receives, as an input on a signal-bearing medium, data representing observations, a method for performing probabilistic interference in a computer system, comprising:

creating a belief network comprising a mixture of Bayesian networks (MBN), said MBN comprising plural hypothesis-specific Bayesian networks (HSBNs), said MBN modeling a case of a hidden variable having a number of states, each HSBN corresponding to a hypothesis that said hidden variable is in a corresponding one of said states, each HSBN having nodes and arcs indicating relationships between the nodes, a first of the nodes of each HSBN 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;

for each HSBN, receiving an observation on said signal-bearing medium for a second of the nodes of the HSBN; and

accessing the decision graph of the first of the nodes of the HSBN to perform probabilistic interference using the probability in the equivalence vertex of the decision graph in the first node and the observation.