System and method of employing efficient operators for bayesian network search

• US 20030220906A1
• Filed: 05/16/2002
• Published: 11/27/2003
• Est. Priority Date: 05/16/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chickering, David Maxwell
• Granted Patent: US 7,324,981 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• 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 method for learning 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; and

searching though the representation by scoring the at least one operator locally with a decomposable scoring criteria.

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.

28. 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 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.

24. A method for learning 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 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, and

searching though 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.

25. The method of claim 24, 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 method 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 method 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.

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

30. A method for learning a Bayesian network, comprising:

providing an equivalence-class state representation corresponding to a class of Bayesian network structures in a search space; and

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.

31. The method of claim 30, 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.

32. The method of claim 31, 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.

33. The method of claim 32, 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.

34. The method of claim 32, 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.

35. The method of claim 34, 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.

36. The method of claim 34, 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.

37. The method of claim 36, 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.

38. The method of claim 37, 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}.

39. The method of claim 34, 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.

40. The method of claim 39, 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.

41. The method of claim 40, 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_incrcase=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}.

42. The method of claim 30, 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.

43. The method of claim 30, the at least one operator further comprising at least one Meek operator.

44. The method of claim 30, 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.

45. The method of claim 44, 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.

46. The method of claim 44, 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.

47. The method of claim 30, 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.

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

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

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

51. The method of claim 30, 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.

52. A computer-readable medium having computer-executable instructions for performing the method of claim 30.

53. A search system for learning a Bayesian network, comprising:

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.

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

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

56. The system of claim 53, 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.

57. The system of claim 53, 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.

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

59. The system of claim 57, 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.

60. The system of claim 53, 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.

61. The system of claim 53, the set of at least one operator further comprising at least one Meek operator.

62. The system of claim 53, 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.

63. The system of claim 62, 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.

64. The system of claim 53, 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.

65. The system of claim 64, 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.

66. The system of claim 65, 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}.

67. The system of claim 53, the current state representation comprising a completed partially directed acyclic graph PC 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.

68. The system of claim 67, 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.

69. The system of claim 68, 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}.