System and method of employing efficient operators for Bayesian network search
First Claim
Patent Images
1. A computer-implemented method for generating a Bayesian network, comprising:
- specifying a search space that provides for searching over equivalence classes of the Bayesian network;
employing a set of at least one operator relative to an equivalence class state representation in the search space upon determining whether the at least one operator is valid for the state representation;
searching through the representation by scoring the at least one operator locally with a decomposable scoring criteria; and
using results of the search to generate a maximum scoring Bayesian network structure stored in a computer readable medium, the structure models real-world data associated with one or more of costumers or products.
2 Assignments
0 Petitions
Accused Products
Abstract
Methods and systems are disclosed for learning Bayesian networks. The approach is based on specifying a search space that enables searching over equivalence classes of the Bayesian network. A set of one or more operators are applied to a representation of the equivalence class. A suitable search algorithm searches in the search space by scoring the operators locally with a decomposable scoring criteria. To facilitate application of the operators and associated scoring, validity tests can be performed to determine whether a given operator is valid relative to the current state representation.
-
Citations
68 Claims
-
1. A computer-implemented method for generating a Bayesian network, comprising:
-
specifying a search space that provides for searching over equivalence classes of the Bayesian network; employing a set of at least one operator relative to an equivalence class state representation in the search space upon determining whether the at least one operator is valid for the state representation; searching through the representation by scoring the at least one operator locally with a decomposable scoring criteria; and using results of the search to generate a maximum scoring Bayesian network structure stored in a computer readable medium, the structure models real-world data associated with one or more of costumers or products. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A computer-readable medium having stored thereon computer executable instructions for learning a Bayesian network that models a given data set, comprising:
-
specifying a search space that provides for searching over equivalence classes of the Bayesian network that models data associated with one or more of users or products; employing a set of at least one operator applicable to an equivalence class state representation in the search space; determining whether operators in the set of at least one operator can validly be applied to the state representation based on a validity condition associated with the respective operator; searching through the representation by scoring valid operators locally with a decomposable scoring criteria to determine which operator to apply to the state representation to implement a state change from the state representation to a next state representation corresponding to a non-empty equivalence class; determining and applying a highest scoring operator to transform the class state representation to a next representation; and learning a representation as ideally modeling the data associated with the one or more users or products based on results of the search. - View Dependent Claims (25, 26, 27, 28)
-
-
29. A computer-implemented method for learning a Bayesian network modeling data relating to at least one of customers or products for sale comprising:
-
providing an equivalence-class state representation corresponding to a class of Bayesian network structures in a search space; searching through the state representation by computing scores corresponding to changes in the state representation associated with a plurality of operators defined in the search space, each of the scores being computed as a local function on a set of adjacency nodes associated with applying a respective operator to the state representation; identifying a maximum scoring operator; and applying the maximum scoring operator to the current state representation in order to generate a Bayesian network structure that closely models the at least one of customer or product data upon conclusion of the search. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51)
-
-
52. A computer-implemented search system for generating a Bayesian network, comprising:
-
a model generator residing within a computer memory that generates and stores within the memory a highest-scoring Bayesian network structure by searching an E-space related to one or more of customer or product data, the network structure is produced by employing;
a current equivalence-class state representation corresponding to a class of Bayesian network structures in a search space; a set of at least one operator operative to transform the current state representation to a next state representation, the at least one operator having an associated validity condition that defines whether the at least one operator is valid for the current state representation; and a scoring function that computes a local score associated with the at least one operator relative to the current state representation by employing a score-equivalent and decomposable scoring criteria and identifies an operator from the set of at least one operator that results in a maximum score for the current state representation, the identified operator is applied in generating the highest scoring structure based on results associated with searching the E-space. - View Dependent Claims (53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68)
-
a model generator residing within a computer memory that generates and stores within the memory a highest-scoring Bayesian network structure by searching an E-space related to one or more of customer or product data, the network structure is produced by employing;
Specification