Mixtures of bayesian networks with decision graphs
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3)
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. - View Dependent Claims (5)
-
-
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. - View Dependent Claims (8, 9, 10)
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. - View Dependent Claims (12, 13, 14, 15, 16, 20)
-
-
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. - View Dependent Claims (18)
-
-
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.
-
Specification