Parallelization of Bayesian Network Structure Learning

• US 20080275827A1
• Filed: 12/31/2004
• Published: 11/06/2008
• Est. Priority Date: 12/31/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Hu, Wei, Li, Eric Q.
• Granted Patent: US 7,870,081 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A master computing node directs parallel structure learning with intelligent computational task distribution. The master computing node may determine what families are to be used to score neighbors in a neighbor scoring process, and determine if the families have scores in a score cache. Families to be scored for the score cache may be marked and distributed for calculation among nodes in the computing cluster. The score cache may be updated to include the scored families, and the cluster synchronized with the score cache data.

Claims

1. A method for network structure learning comprising:

determining whether a score cache includes a score for each of multiple network node families, the family scores to provide values with which to compute scores for multiple neighbors;

distributing for scoring among parallel computing devices node families for which the score cache does not include scores;

loading resulting scores from the parallel computing devices for the scored node families into the master score cache; and

synchronizing the parallel computing devices with the master score cache to make the resulting scores available to the parallel computing devices for scoring the neighbors.

2. A method according to claim 1, wherein the multiple network node families comprise family structures of a Bayesian network.

3. A method according to claim 1, further comprising placing in a queue node families determined to be missing from the master score cache and wherein distributing among the parallel computing device each node family to be scored comprises distributing a number of node families out of the queue to each parallel computing device to score.

4. A method according to claim 3, wherein distributing among the parallel computing devices the node families comprises distributing an integer value [M/N] of node families to each parallel computing device, where M is an integer representing the number of node families to score, N is an integer representing the number of parallel computing devices, and the integer value [M/N] does not include a fractional component, if M divided by N produces a remainder.

5. A method according to claim 1, wherein synchronizing the parallel computing devices comprises distributing the score cache loaded with the family scores.

6. A method according to claim 5, wherein scoring the neighbors comprises:

searching the score cache for a score for a node family associated with a neighbor;

if the searching results in a cache hit, loading the node family score; and

if the searching results in a cache miss, computing the node family score;

wherein the searching results in no cache misses.

7. A method according to claim 1, further comprising distributing to the parallel computing device the neighbors to be scored.

8. An article of manufacture comprising a machine accessible medium having content to provide instructions to result in a machine performing operations including:

identifying, for multiple neighbors to score, multiple network family structures associated with the neighbors;

determining for each identified family structure whether a score for the family structure is available in a score cache, and if not, queuing the family structure in a task queue to indicate the family is to be scored;

distributing for scoring among parallel computing devices the queued family structures;

updating the score cache with resulting computed scores of the family structures from the parallel computing devices; and

distributing the score cache to the parallel computing devices for use with scoring the neighbors.

9. An article of manufacture according to claim 8, wherein the multiple network family structures comprise structures of a Bayesian network.

10. An article of manufacture according to claim 8, wherein the content to provide instructions to result in the machine queuing the family structure in the task queue comprises the content to provide instructions to result in the machine generating an index referencing the family structure.

11. An article of manufacture according to claim 8, wherein the content to provide instructions to result in the machine distributing for scoring among parallel computing devices the queued family structures further comprises the content to provide instructions to result in a master computing node distributing the queued family structures to nodes in a cluster of computing nodes, including the master computing node.

12. An apparatus comprising:

a memory having data to define operations including searching a score cache for a Bayesian network family structure associated with neighbor scoring of a network structure learning algorithm, queuing for computation among parallel computing nodes the family structures missing from the score cache, distributing to the parallel computing nodes for scoring the missing family structures computing tasks to calculate the scores of the missing family structures, distributing resulting calculated scores and the score cache among the parallel computing nodes to provide the scores of the score cache and the resulting calculated scores to the parallel computing nodes for computation of scores of neighbors associated with the Bayesian network family structures, and distributing to the parallel computing nodes tasks to calculate scores for the neighbors; and

a processor coupled to the memory to execute instructions on the data in the memory to produce the operations.

13. An apparatus according to claim 12, wherein the memory having data defining queuing the family structures missing from the score cache comprises the memory having data defining generating indices for each missing family structure.

14. An apparatus according to claim 12, wherein the memory having data defining distributing the computing tasks comprises the memory having data defining distributing an integer number of computing tasks to each parallel computing node, each node to receive [M/N] computing tasks, where M is an integer representing the number of family structures missing from the score cache, N is an integer representing the number of parallel computing nodes, and the integer value [M/N] does not include a fractional component, if M divided by N produces a remainder.

15. An apparatus according to claim 12, wherein the memory having data defining distributing the resulting calculated scores and the score cache further comprises the memory having data defining receiving the calculated scores from the parallel computing nodes, updating the score cache with the calculated scores, and sending the updated score cache to each parallel computing node.

16. An apparatus according to claim 12, the memory further having data defining the processor as one of the parallel computing nodes, and wherein distributing to the parallel computing nodes comprises the processor receiving tasks to compute.

17. A system comprising:

a memory having data to define operations including searching a score cache for a Bayesian network family structure associated with neighbor scoring of a network structure learning algorithm, queuing for computation among parallel computing nodes the family structures missing from the score cache, distributing to the parallel computing nodes for scoring the missing family structures computing tasks to calculate the scores of the missing family structures, modifying the score cache to include the resulting calculated scores, distributing the modified score cache among the parallel computing nodes to provide the scores of the score cache and the resulting calculated scores to the parallel computing nodes for computation of scores of neighbors associated with the Bayesian network family structures, and distributing to the parallel computing nodes tasks to calculate scores for the neighbors;

a processor coupled to the memory to perform the operations defined in the data in the memory; and

a database coupled to the processor and to the memory to store the evidences from which the Bayesian network family structures are constructed.

18. A system according to claim 17, wherein the network structure learning algorithm comprises a hill-climbing algorithm.

19. A system according to claim 17, wherein queuing includes passing a handle to a family structure stored in the database.

20. A system according to claim 17, wherein distributing the computing tasks to calculate the scores of the missing family structures comprises distributing [M/N] computing tasks to each computing node, where M is an integer representing the number of family structures missing from the score cache, N is an integer representing the number of parallel computing nodes, and the integer value [M/N] does not include a fractional component, if M divided by N produces a remainder.