Score result reuse for Bayesian network structure learning

• US 20060112057A1
• Filed: 10/28/2004
• Published: 05/25/2006
• Est. Priority Date: 10/28/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Lai, Chunrong
• Granted Patent: US 7,627,537 B2
• Time in Patent Office: Days
• US Class Current: 706/47
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Reuse of intermediate statistical score computations. Learning a network structure may involve computationally intensive operations. In one embodiment a partial result may be computed and cached that will be used in computing the score of another network structure. A speculative determination whether to cache the partial result may be made.

Claims

1. A method for score computing of a Bayesian network, comprising:

computing an intermediate result for a score computation of a family structure including a child node;

caching the intermediate result; and

computing a score of the family structure with the intermediate result and an edge difference between a parent node of the family structure and the child node.

2. A method according to claim 1, wherein computing the intermediate result comprises computing a score of the family structure in conjunction with learning a structure of the Bayesian network.

3. A method according to claim 2, wherein computing the intermediate result comprises computing the score prior to performing a structure learning process to learn the structure of the Bayesian network.

4. A method according to claim 2, wherein learning the structure of the Bayesian network comprises executing a hill-climbing algorithm.

5. A method according to claim 1, wherein computing the intermediate result comprises calculating a partial displacement value of the family structure.

6. A method according to claim 5, wherein the partial displacement value comprises a displacement value of a family structure including the child node and excluding the parent node.

7. A method according to claim 5, wherein computing the score of the family structure with the edge difference comprises computing the displacement value of the family structure including the child node and the parent node.

8. A method according to claim 1, further comprising:

distributing the cached intermediate result among multiple computing components.

9. A method according to claim 8, wherein the multiple computing components comprise a single computing device.

10. A method according to claim 8, wherein the multiple computing components comprise an interconnected with a communication link.

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

computing an intermediate result for a score computation of a Bayesian network family structure including a child node;

caching the intermediate result; and

computing a score of the family structure with the intermediate result and an edge difference between a parent node of the family structure and the child node.

12. An article of manufacture according to claim 11, wherein the content to provide instructions to result in the machine computing the intermediate result comprises the content to provide instructions to result in the machine computing a score of the family structure in conjunction with learning a structure of the Bayesian network.

13. An article of manufacture according to claim 11, wherein the content to provide instructions to result in the machine computing the intermediate result comprises the content to provide instructions to result in the machine calculating a partial displacement value of the family structure, the partial displacement value including the child node and excluding the parent node.

14. An article of manufacture according to claim 13, wherein the content to provide instructions to result in the machine computing the score of the family structure with the edge difference comprises the content to provide instructions to result in the machine computing the displacement value of the family structure including the child node and the parent node.

15. An article of manufacture according to claim 11, further comprising the content to provide instructions to result in a computing device distributing the cached result to a different computing device.

16. An apparatus to perform directed graph structure learning, comprising:

a processor to execute instructions; and

a memory coupled to the processor having data to provide instructions to the processor to result in the processor performing operations including

calculating a matrix displacement offset of a network neighborhood, the neighborhood including a child node, matrix displacement offset excluding a first parent node of the neighborhood;

storing the matrix displacement offset in a memory; and

retrieving the matrix displacement offset from the memory to calculate a displacement result of the Bayesian network neighborhood including the child node and a second parent node, the displacement result calculated from the retrieved matrix displacement offset and the value of the second parent node.

17. An apparatus according to claim 16, the memory further having data to provide instructions to the processor to result in the processor indicating the matrix displacement offset to a computing core.

18. An apparatus according to claim 17, wherein the computing core comprises an additional processor, coupled to the memory, to execute instructions, and to receive the matrix displacement offset from the processor.

19. An apparatus according to claim 17, wherein the computing core comprises a computing core on a remote computing device.

20. A method for score computing in network structure learning, comprising:

preparing a score computation of a network neighborhood structure, the score computation having a logical computation order with a child node as the last dimension of the logical computation order;

speculating the network structure has one parent difference compared to a previously computed network neighborhood structure; and

re-ordering the logical computation order of the score computation to compute the score computation of the network neighborhood structure with the child node as the penultimate dimension and a parent node of the child node as the last dimension.

21. A method according to claim 20, wherein the neighborhood structure comprises a Bayesian network.

22. A method according to claim 20, wherein the previously computed network neighborhood structure comprises a last computed network neighborhood structure.

23. A method according to claim 20, further comprising computing and storing a partial displacement value, the partial displacement comprising a score computation according to the re-ordered logical computation order of the neighborhood structure including the state values of all dimensions up to and including the penultimate dimension, and excluding the last dimension.

24. An article of manufacture comprising a machine accessible medium having content that when accessed results in a machine performing operations including:

preparing a score computation of a network neighborhood structure, the score computation having a logical computation order with a child node as the last dimension of the logical computation order;

speculating the network structure has one parent difference compared to a previously computed network neighborhood structure; and

re-ordering the logical computation order of the score computation to compute the score computation of the network neighborhood structure with the child node as the penultimate dimension and a parent node of the child node as the last dimension.

25. An article of manufacture according to claim 24, wherein the neighborhood structure comprises a Bayesian network.

26. An article of manufacture according to claim 24, wherein the previously computed network neighborhood structure comprises a most recently computed network neighborhood structure.

27. An article of manufacture according to claim 24, the content when accessed further results in the machine computing and storing a partial displacement value, the partial displacement comprising a score computation according to the re-ordered logical computation order of the neighborhood structure including the state values of all dimensions up to and including the penultimate dimension, and excluding the last dimension.

28. An apparatus to perform Bayesian network structure learning, comprising:

a processor to execute instructions;

a memory coupled to the processor having data to provide instructions to the processor to result in the processor performing operations including

preparing a statistical score computation of a network neighborhood structure, the score computation having a logical computation order with a child node as the last dimension of the logical computation order;

speculating the network structure has one parent difference with respect to a most recently scored network neighborhood structure;

re-ordering the logical computation order of the score computation to compute the score computation of the network neighborhood structure with the child node as the penultimate dimension and a parent node of the child node as the last dimension; and

caching a score computation result according to the re-ordered logical computation order for state values of the neighborhood structure up to and including the child node, and excluding the parent node; and

a communication interface coupled with an external computing device to transmit the cached score computation result to the external computing device.

29. An apparatus according to claim 28, wherein caching the score computation result further comprises speculating that the score computation result will be re-used in other score computations.

30. An apparatus according to claim 28, wherein the communication interface comprises a system bus of a multi-core system, and wherein the external computing device comprises an additional core of the system.