System and method of employing efficient operators for Bayesian network search

• US 7,324,981 B2
• Filed: 05/16/2002
• Issued: 01/29/2008
• Est. Priority Date: 05/16/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chickering, David Maxwell
• Primary Examiner(s): Starks, Jr.; Wilbert L
• Application Number:
  US10/147,620
• Publication Number:
  US 20030220906A1
• Time in Patent Office: 2,084 Days
• Field of Search: 706/45, 706/50, 435/6, 382/104, 707/3, 707/5, 701/50
• US Class Current: 706/45
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

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.

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.

2. The method of claim 1, the set of at least one operator comprising a plurality of operators, the method further comprising determining whether each operator in the set of operators is valid for the state representation based on whether the operator, if applied to the state representation, results in a non-empty equivalence class.

3. The method of claim 2, further comprising generating a set of at least one candidate operator from the set of operators based on whether the respective operators are valid for the state representation.

4. The method of claim 2, each operator in the set of operators having an associated validity condition that defines whether each respective operator is valid for the state representation.

5. The method of claim 2, the state representation comprising at least two nodes and the set of operators comprising a first insert operator for inserting an undirected edge between a pair of the at least two nodes, a first delete operator for deleting an undirected edge between a pair of the at least two nodes connected by an undirected edge, a second insert operator for inserting a directed edge between a pair of the at least two nodes, a second delete operator for deleting a directed edge between a pair of the at least two nodes connected by a directed edge, a reverse operator for reversing a directed edge between a pair of the at least two nodes connected by a directed edge, and a make-V operator for making a V-structure from a triple of nodes.

6. The method of claim 5, each of the operators in the set of operators having an associated validity condition.

7. The method of claim 2, the state representation comprising a completed partially directed acyclic graph P^c having at least two nodes X and Y, the set of operators further comprising an Insert(X, Y, T) operator for adding an edge between a pair of the at least two nodes, where T is a subset of at least one neighbor of Y not adjacent to X.

8. The method of claim 7, the Insert(X, Y, T) operator being valid if (a) NA_Y,X∪

T is a clique and (b) every semi-directed path from Y to X contains a node in NA_Y,X∪

T, where NA_Y,X corresponds to a set of nodes that are neighbors of node Y and are adjacent to node X in P^c.

9. The method of claim 8, the searching further comprising computing an increase in score Score_increase that results from applying the Insert(X, Y, T) operator to P^c, wherein

Score_increase=s(Y,NA_y,x∪

T∪

Pa_Y^+X)−

s(Y,NA_y,x∪

T∪

Pa_y),

where Pa_Y denotes parents of node Y in P^c; and

Pa_Y^+X denotes Pa_Y∪

{X}.

10. The method of claim 7, the set of operators further comprising a Delete(X, Y, H) operator for deleting an edge in P^c, where H is a subset of at least one neighbor of Y adjacent to X.

11. The method of claim 10, the Delete(X, Y, H) operator being valid for deleting an edge between X and Y if NA_Y,X\H is a clique, where NA_Y,X corresponds to a set of nodes that are neighbors of node Y and are adjacent to node X in P^c.

12. The method of claim 11, the searching further comprising computing an increase in score Score_increase that results from applying the Delete(X, Y, H) operator to P^c, wherein

Score_increase=s(Y, {NA_y,x\H}∪

Pa_Y<sup>−

X</sup>)−

s(Y, {NA_Y,X\H}∪

Pa_Y)

where Pa_Y denotes parents of node Y in P^c; and

Pa_Y<sup>−

X</sup> denotes Pa_Y\{X}.

13. The method of claim 1, the at least one operator further comprising an edge reversal operator that, when applied to a directed edge in the state representation, reverses the directed edge.

14. The method of claim 1, the at least one operator further comprising at least one Meek operator.

15. The method of claim 1, each operator in the set of at least one operator comprising a predetermined scoring function having a decomposable scoring criterion to compute a change in score associated with applying each respective operator to the state representation.

16. The method of claim 15, the scoring function being defined to enable the score to be computed without applying any operator to the state representation.

17. The method of claim 15, further comprising:

prior to computing the score for a respective operator, determining if the respective operator is valid for the state representation; and

using the predetermined scoring function to compute the score for the respective operator based on determining that the operator is valid.

18. The method of claim 1, further comprising selecting an operator from the set of at least one operator based on a score associated with the selected operator and applying the selected operator to change the representation to a next state representation.

19. The method of claim 1, the state representation comprising a completed partially directed acyclic graph (PDAG).

20. The method of claim 19, further comprising applying a selected operator locally to the state representation to provide a resulting PDAG having the same skeleton and v-structure.

21. The method of claim 20, further comprising converting the resulting PDAG representation into a completed PDAG.

22. The method of claim 1, the at least one operator comprising a plurality of operators, the method further comprising:

efficiently generating a set of valid operators from the plurality of operators based on validity conditions associated with each respective operator in the plurality of operators; and

using the set of valid operators in the searching.

23. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

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.

25. The medium of claim 24 further comprising instructions for applying a selected operator to the state representation based on a score associated therewith to generate the next state representation, and generating a list of candidate operators based on determining whether each operator in the set of at least one operator is valid for the next state representation.

26. The medium of claim 24, the state representation comprising at least two nodes and the set of operators comprising a first insert operator for inserting an undirected edge between a pair of the at least two nodes, a first delete operator for deleting an undirected edge between a pair of the at least two nodes connected by an undirected edge, a second insert operator for inserting a directed edge between a pair of the at least two nodes, a second delete operator for deleting a directed edge between a pair of the at least two nodes connected by a directed edge, a reverse operator for reversing a directed edge between a pair of the at least two nodes connected by a directed edge, and a make-v operator for making a v-structure from a triple of nodes.

27. The medium of claim 26, the determining further comprising testing the validity of each of the operators in the set of operators based on an associated validity condition.

28. The medium of claim 26, the state representation comprising a completed partially directed acyclic graph P^c having at least two nodes X and Y, the set of operators further comprising an Insert(X, Y, T) operator for adding an edge between a pair of the at least two nodes, where T is a subset of at least one neighbor of Y not adjacent to X and a Delete(X, Y, H) operator for deleting an edge in P^c, where H is a subset of at least one neighbor of Y adjacent to X.

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.

30. The method of claim 29, further comprising applying one of the plurality of operators based on the searching to cause the state representation to change to a next state representation.

31. The method of claim 30, further comprising determining whether a given operator is valid for the state representation by discerning whether the given operator, if applied to the state representation, would provide a next state representation of a non-empty equivalence class.

32. The method of claim 31, further comprising generating a set of at least one candidate operator from the set of operators based on whether the respective operators are valid for the state representation.

33. The method of claim 31, each of the operators having an associated validity condition that defines whether the at least one operator will be valid for a given application to the state representation.

34. The method of claim 33, the state representation comprising at least two nodes and the set of operators comprising a first insert operator for inserting an undirected edge between a pair of the at least two nodes, a first delete operator for deleting an undirected edge between a pair of the at least two nodes connected by an undirected edge, a second insert operator for inserting a directed edge between a pair of the at least two nodes, a second delete operator for deleting a directed edge between a pair of the at least two nodes connected by a directed edge, a reverse operator for reversing a directed edge between a pair of the at least two nodes connected by a directed edge, and a make-v operator for making a v-structure from a triple of nodes.

35. The method of claim 33, the state representation comprising a completed partially directed acyclic graph P^c having at least two nodes X and Y, the set of operators further comprising an Insert(X, Y, T) operator for adding an edge between a pair of the at least two nodes, where T is a subset of at least one neighbor of Y not adjacent to X.

36. The method of claim 35, the Insert(X, Y, T) operator being valid if (a) NA_Y,X∪

T is a clique and (b) every semi-directed path from Y to X contains a node in NA_Y,X∪

T, where NA_Y,X corresponds to a set of nodes that are neighbors of node Y and are adjacent to node X in P^c.

37. The method of claim 36, further comprising computing an increase in score Score_increase that results from applying the Insert(X, Y, T) operator to P^c, wherein

Score_increase=s(Y,NA_y,x∪

T∪

Pa^+X)−

s(Y,NA_Y,X∪

T∪

Pa_y),

where Pa_Y denotes parents of node Y in P^c; and

Pa_Y^+X denotes Pa_Y∪

{X}.

38. The method of claim 33, the set of operators further comprising a Delete(X, Y, H) operator for deleting an edge in P^c, where H is a subset of at least one neighbor of Y adjacent to X.

39. The method of claim 38, the Delete(X, Y, H) operator being valid for deleting an edge between X and Y if NA_Y,X\H is a clique, where NA_Y,X corresponds to a set of nodes that are neighbors of node Y and are adjacent to node X in P^c.

40. The method of claim 39, the searching further comprising computing an increase in score Score_increase that results from applying the Delete(X, Y, H) operator to P^c, wherein

Score_increase=s(Y, {NA_y,x\H}∪

Pa_Y<sup>−

X</sup>)−

s(Y, {NA_Y,X\H}∪

Pa_Y)

where Pa_Y denotes parents of node Y in P^c; and

Pa_Y<sup>−

X</sup> denotes Pa_Y\{X}.

41. The method of claim 29, the at least one operator further comprising an edge reversal operator that, when validly applied to a directed edge in the state representation, reverses the directed edge.

42. The method of claim 29, the at least one operator further comprising at least one Meek operator.

43. The method of claim 29, the searching further comprising employing a predetermined scoring function having a decomposable scoring criterion for each of the at least one operator in the search space to compute a change in score associated with applying the at least one operator to the state representation.

44. The method of claim 43, the scoring function being defined to enable the computation of the score to occur without applying the at least one operator to the state representation.

45. The method of claim 43, further comprising:

prior to computing the score for the at least one operator, determining if the respective operator is valid for the state representation; and

using the predetermined scoring function to compute the score for the respective operator based on determining that the operator is valid.

46. The method of claim 29, further comprising selecting an operator to apply to the state representation based on the score associated with the selected operator and applying the selected operator to change the representation to a next state representation corresponding to a non-empty equivalence class.

47. The method of claim 29, the state representation comprising a completed partially directed acyclic graph (PDAG).

48. The method of claim 47, further comprising applying a selected operator to the state representation to provide a resulting PDAG that defines a non-empty equivalence class.

49. The method of claim 48, further comprising converting the resulting PDAG representation into a completed PDAG.

50. The method of claim 29, the at least one operator comprising a plurality of operators, the method further comprising:

efficiently generating a set of valid operators from the plurality of operators based on validity conditions associated with each of the respective operator in the plurality of operators; and

using the set of valid operators in the searching.

51. A computer-readable medium having computer-executable instructions for performing the method of claim 29.

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.

53. The system of claim 52, further comprising a converter operative to convert the next state representation to another equivalence class representation thereof in the search space.

54. The system of claim 53, the current state representation comprising a completed partially directed acyclic graph (PDAG).

55. The system of claim 52, the next state representation corresponding to a resulting PDAG corresponding to a non-empty equivalence class, the converter being operative to convert the resulting PDAG into a completed PDAG.

56. The system of claim 52, the set of at least one operator further comprising a set of a plurality of operators, each of the plurality of operators being operative to transform the current state representation to a respective next state representation, each of the plurality of operators having an associated validity condition that defines whether each respective operator is valid for a given application to the current state representation.

57. The system of claim 56, the scoring system computing scores based on whether each respective operator is valid for a given application to the current state representation.

58. The system of claim 56, further comprising a validity system operative to ascertain the validity of each respective operator and generate a set of candidate operators for use by the scoring system based on the validity of the operators.

59. The system of claim 52, the set of at least one operator further comprising at least a reverse operator, the reverse operator being operative to reverse a directed edge in the current state representation, the reverse operator having an associated validity condition for controlling application to the current state representation.

60. The system of claim 52, the set of at least one operator further comprising at least one Meek operator.

61. The system of claim 52, the current state representation comprising at least two nodes and the set of at least one operator further comprising:

a first insert operator for inserting an undirected edge between a pair of the at least two nodes;

a first delete operator for deleting an undirected edge between a pair of the at least two nodes connected by an undirected edge;

a second insert operator for inserting a directed edge between a pair of the at least two nodes;

a second delete operator for deleting a directed edge between a pair of the at least two nodes connected by a directed edge;

a reverse operator for reversing a directed edge between a pair of the at least two nodes connected by a directed edge; and

a make-v operator for making a v-structure from a triple of nodes.

62. The system of claim 61, each of the operators in the set of operators having an associated validity condition that defines whether each respective operator is valid for a given application to the current state representation.

63. The system of claim 52, the current state representation comprising a completed partially directed acyclic graph P^c having at least two nodes X and Y, the set of operators further comprising an Insert(X, Y, T) operator for adding an edge between a pair of the at least two nodes, where T is a subset of at least one neighbor of Y not adjacent to X.

64. The system of claim 63, the Insert(X, Y, T) operator being valid if (a) NA_Y,X∪

T is a clique and (b) every semi-directed path from Y to X contains a node in NA_Y,X∪

T, where NA_Y,X corresponds to a set of nodes that are neighbors of node Y and are adjacent to node X in P^c.

65. The system of claim 64, the scoring function being operative to compute an increase in score Score_increase that results from applying the Insert(X, Y, T) operator to P^c, wherein

Score_increase=s(Y,NA_y,x∪

T∪

Pa^+X)−

s(Y,NA_y,x∪

T∪

Pa_y),

where Pa_Y denotes parents of node Y in P^c; and

Pa_Y^+X denotes Pa_Y∪

{X}.

66. The system of claim 52, the current state representation comprising a completed partially directed acyclic graph P^c having at least two nodes X and Y, and the set of at least one operator further comprising a Delete(X, Y, H) operator for deleting an edge in P^c, where H is a subset of at least one neighbor of Y adjacent to X.

67. The system of claim 66, the Delete(X, Y, H) operator being valid for deleting an edge between X and Y if NA_Y,X\H is a clique, where NA_Y,X corresponds to a set of nodes that are neighbors of node Y and are adjacent to node X in P^c.

68. The system of claim 67, the scoring function being operative to compute an increase in score Score_increase that results from applying the Delete(X, Y, H) operator to P^c, wherein

Score_increase=s(Y, {NA_y,x\H}∪

Pa_Y<sup>−

X</sup>)−

s(Y, {NA_Y,X\H}∪

Pa_Y)

where Pa_Y denotes parents of node Y in P^c; and

Pa_Y<sup>−

X</sup> denotes Pa_Y\{X}.