Evaluation of bayesian network models for decision support

• US 20050091012A1
• Filed: 10/23/2003
• Published: 04/28/2005
• Est. Priority Date: 10/23/2003
• Status: Active Grant

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Dash, Denver, Przytula, Krzysztof W.
• Granted Patent: US 7,650,272 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

A method, apparatus, and computer program product are presented for automatically evaluating Bayesian network models. Operations performed comprise receiving a Bayesian Network (BN) model including evidence nodes and conclusion nodes that are linked with the evidence nodes by causal dependency links, and where the evidence nodes have evidence states and the conclusion nodes have conclusion states. The states of conclusion nodes are set to desired conclusion states and corresponding probabilities of occurrence of evidence states are determined by propagating these states down the causal dependency links. Thus, samples of most likely states of the evidence nodes are generated. Then, states of the evidence nodes are set corresponding to the samples of the evidence states. These states are propagated back up the causal dependency links to obtain probabilities of the resulting states of the conclusion nodes. Finally, a representation is outputted for the probabilities of the states of the conclusion nodes.

Claims

1. A method for automatically evaluating Bayesian network models for decision support comprising:

receiving a Bayesian Network (BN) model including evidence nodes and conclusion nodes, where the conclusion nodes are linked with the evidence nodes by causal dependency links, and where the evidence nodes have evidence states and the conclusion nodes have conclusion states;

setting the states of the conclusion nodes to desired conclusion states and determining, by propagating down the causal dependency links, a corresponding probability of occurrence of evidence states of the evidence nodes and producing, from the probability of occurrence, a plurality of samples of most likely states of the evidence nodes;

setting the states of the evidence nodes to states corresponding to the plurality of samples of the evidence states, and propagating the evidence states back up the causal dependency links to the conclusion nodes, to obtain a plurality of probabilities of the resulting states of the conclusion nodes; and

outputting a representation of the plurality of the probabilities of the states of the conclusion nodes.

2. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 1, wherein the BN model further includes at least one auxiliary node causally linked between at least one evidence node and at least one conclusion node.

3. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 2, wherein the sampling is performed by a Monte Carlo algorithm.

4. A method for automatically evaluating Bayesian network models for decision support, as set forth in claim 3, wherein the outputted representation is a complete representation of probabilities of states for all conclusions given a particular set of combinations of conclusion states.

5. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 4, wherein the outputted representation is a graphical representation.

6. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 4, wherein the outputted representation is a matrix of averages of probabilities of the conclusion states for implicated conclusions versus a selected set of combinations of conclusion states;

whereby a user can determine an accuracy of the BN model'"'"'s propensity to yield proper conclusions.

7. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 6, wherein the outputted representation is a graphical representation in the form of a two-dimensional intensity matrix and a three-dimensional bar chart.

8. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 7, wherein the conclusion nodes are weighted by weights representing their importance;

whereby the accuracy of the BN model'"'"'s propensity to yield proper conclusions may be weighted for particular conclusions based on their relative importance.

9. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 8, wherein the BN model models a diagnostic domain, with the conclusion nodes representing component failures or diseases, the evidence nodes representing recognizable symptoms of those failures or diseases, and the auxiliary nodes representing additional information useful, in conjunction with the evidence nodes and conclusion nodes.

10. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 1, wherein the BN model further includes at least one auxiliary node causally linked between at least one evidence node and at least one conclusion node.

11. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 1, wherein the sampling is performed by a Monte Carlo algorithm.

12. A method for automatically evaluating Bayesian network models for decision support, as set forth in claim 1, wherein the outputted representation is a complete representation of probabilities of states for all conclusions given a particular set of combinations of conclusion states.

13. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 1, wherein the outputted representation is a graphical representation.

14. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 1, wherein the outputted representation is a matrix of averages of probabilities of the conclusion states for implicated conclusions versus a selected set of combinations of conclusion states;

whereby a user can determine an accuracy of the BN model'"'"'s propensity to yield proper conclusions.

15. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 1, wherein the outputted representation is a graphical representation in the form of a two-dimensional intensity matrix and a three-dimensional bar chart.

16. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 1, wherein the conclusion nodes are weighted by weights representing their importance;

whereby an accuracy of the BN model'"'"'s propensity to yield proper conclusions may be weighted for particular conclusions based on their relative importance.

17. A method for automatically evaluating Bayesian network models for decision support as set forth in claim 1, wherein the BN model models a diagnostic domain, with the conclusion nodes representing component failures or diseases, the evidence nodes representing recognizable symptoms of those failures or diseases, and the auxiliary nodes representing additional information useful, in conjunction with the evidence nodes and conclusion nodes.

18. An apparatus for automatically evaluating Bayesian network models for decision support, the apparatus comprising a computer system including a processor, a memory coupled with the processor, an input coupled with the processor for receiving user input and data input, and an output coupled with the processor for outputting display data, wherein the computer system further comprises means, residing in its processor and memory, for:

receiving a Bayesian Network (BN) model including evidence nodes and conclusion nodes, where the conclusion nodes are linked with the evidence nodes by causal dependency links, and where the evidence nodes have evidence states and the conclusion nodes have conclusion states;

setting the states of the conclusion nodes to desired conclusion states and determining, by propagating down the causal dependency links, a corresponding probability of occurrence of evidence states of the evidence nodes and producing, from the probability of occurrence, a plurality of samples of most likely states of the evidence nodes;

setting the states of the evidence nodes to states corresponding to the plurality of samples of the evidence states, and propagating the evidence states back up the causal dependency links to the conclusion nodes, to obtain a plurality of probabilities of the resulting states of the conclusion nodes; and

outputting a representation of the plurality of the probabilities of the states of the conclusion nodes.

19. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 18, wherein the BN model further includes at least one auxiliary node causally linked between at least one evidence node and at least one conclusion node.

20. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 19, wherein the sampling is performed by a Monte Carlo algorithm.

21. An apparatus for automatically evaluating Bayesian network models for decision support, as set forth in claim 20, wherein the outputted representation is a complete representation of probabilities of states for all conclusions given a particular set of combinations of conclusion states.

22. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 21, wherein the outputted representation is a graphical representation.

23. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 21, wherein the outputted representation is a matrix of averages of probabilities of the conclusion states for implicated conclusions versus a selected set of combinations of conclusion states;

whereby a user can determine an accuracy of the BN model'"'"'s propensity to yield proper conclusions.

24. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 23, wherein the outputted representation is a graphical representation in the form of a two-dimensional intensity matrix and a three-dimensional bar chart.

25. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 24, wherein the conclusion nodes are weighted by weights representing their importance;

whereby the accuracy of the BN model'"'"'s propensity to yield proper conclusions may be weighted for particular conclusions based on their relative importance.

26. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 25, wherein the BN model models a diagnostic domain, with the conclusion nodes representing component failures or diseases, the evidence nodes representing recognizable symptoms of those failures or diseases, and the auxiliary nodes representing additional information useful, in conjunction with the evidence nodes and conclusion nodes.

27. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 18, wherein the BN model further includes at least one auxiliary node causally linked between at least one evidence node and at least one conclusion node.

28. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 18, wherein the sampling is performed by a Monte Carlo algorithm.

29. An apparatus for automatically evaluating Bayesian network models for decision support, as set forth in claim 18, wherein the outputted representation is a complete representation of probabilities of states for all conclusions given a particular set of combinations of conclusion states.

30. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 18, wherein the outputted representation is a graphical representation.

31. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 18, wherein the outputted representation is a matrix of averages of probabilities of the conclusion states for implicated conclusions versus a selected set of combinations of conclusion states;

whereby a user can determine the accuracy of the BN model'"'"'s propensity to yield proper conclusions.

32. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 18, wherein the outputted representation is a graphical representation in the form of a two-dimensional intensity matrix and a three-dimensional bar chart.

33. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 18, wherein the conclusion nodes are weighted by weights representing their importance;

whereby an accuracy of the BN model'"'"'s propensity to yield proper conclusions may be weighted for particular conclusions based on their relative importance.

34. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 18, wherein the BN model models a diagnostic domain, with the conclusion nodes representing component failures or diseases, the evidence nodes representing recognizable symptoms of those failures or diseases, and the auxiliary nodes representing additional information useful, in conjunction with the evidence nodes and conclusion nodes.

35. An apparatus for automatically evaluating Bayesian network models for decision support, the apparatus comprising a computer system including a processor, a memory coupled with the processor, an input coupled with the processor for receiving user input and data input, and an output coupled with the processor for outputting display data, wherein:

the input is configured for receiving a Bayesian Network (BN) model including evidence nodes and conclusion nodes, where the conclusion nodes are linked with the evidence nodes by causal dependency links, and where the evidence nodes have evidence states and the conclusion nodes have conclusion states;

the processor is configured for setting the states of the conclusion nodes to desired conclusion states and determining, by propagating down the causal dependency links, a corresponding probability of occurrence of evidence states of the evidence nodes and producing, from the probability of occurrence, a plurality of samples of most likely states of the evidence nodes; and

for setting the states of the evidence nodes to states corresponding to the plurality of samples of the evidence states, and propagating the evidence states back up the causal dependency links to the conclusion nodes, to obtain a plurality of probabilities of the resulting states of the conclusion nodes; and

the output is configured for outputting a representation of the plurality of the probabilities of the states of the conclusion nodes.

36. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 35, wherein the BN model further includes at least one auxiliary node causally linked between at least one evidence node and at least one conclusion node.

37. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 36, wherein the sampling is performed by a Monte Carlo algorithm.

38. An apparatus for automatically evaluating Bayesian network models for decision support, as set forth in claim 37, wherein the outputted representation is a complete representation of probabilities of states for all conclusions given a particular set of combinations of conclusion states.

39. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 38, wherein the outputted representation is a graphical representation.

40. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 38, wherein the outputted representation is a matrix of averages of probabilities of the conclusion states for implicated conclusions versus a selected set of combinations of conclusion states;

whereby a user can determine an accuracy of the BN model'"'"'s propensity to yield proper conclusions.

41. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 40, wherein the outputted representation is a graphical representation in the form of a two-dimensional intensity matrix and a three-dimensional bar chart.

42. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 41, wherein the conclusion nodes are weighted by weights representing their importance;

whereby the accuracy of the BN model'"'"'s propensity to yield proper conclusions may be weighted for particular conclusions based on their relative importance.

43. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 42, wherein the BN model models a diagnostic domain, with the conclusion nodes representing component failures or diseases, the evidence nodes representing recognizable symptoms of those failures or diseases, and the auxiliary nodes representing additional information useful, in conjunction with the evidence nodes and conclusion nodes.

44. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 35, wherein the BN model further includes at least one auxiliary node causally linked between at least one evidence node and at least one conclusion node.

45. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 35, wherein the sampling is performed by a Monte Carlo algorithm.

46. An apparatus for automatically evaluating Bayesian network models for decision support, as set forth in claim 35, wherein the outputted representation is a complete representation of probabilities of states for all conclusions given a particular set of combinations of conclusion states.

47. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 35, wherein the outputted representation is a graphical representation.

48. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 35, wherein the outputted representation is a matrix of averages of probabilities of the conclusion states for implicated conclusions versus a selected set of combinations of conclusion states;

whereby a user can determine an accuracy of the BN model'"'"'s propensity to yield proper conclusions.

49. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 35, wherein the outputted representation is a graphical representation in the form of a two-dimensional intensity matrix and a three-dimensional bar chart.

50. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 35, wherein the conclusion nodes are weighted by weights representing their importance;

whereby an accuracy of the BN model'"'"'s propensity to yield proper conclusions may be weighted for particular conclusions based on their relative importance.

51. An apparatus for automatically evaluating Bayesian network models for decision support as set forth in claim 35, wherein the BN model models a diagnostic domain, with the conclusion nodes representing component failures or diseases, the evidence nodes representing recognizable symptoms of those failures or diseases, and the auxiliary nodes representing additional information useful, in conjunction with the evidence nodes and conclusion nodes.

52. A computer program product for automatically evaluating Bayesian network models for decision support, the computer program product comprising means, encoded in a computer-readable medium for:

receiving a Bayesian Network (BN) model including evidence nodes and conclusion nodes, where the conclusion nodes are linked with the evidence nodes by causal dependency links, and where the evidence nodes have evidence states and the conclusion nodes have conclusion states;

setting the states of the conclusion nodes to desired conclusion states and determining, by propagating down the causal dependency links, a corresponding probability of occurrence of evidence states of the evidence nodes and producing, from the probability of occurrence, a plurality of samples of most likely states of the evidence nodes;

setting the states of the evidence nodes to states corresponding to the plurality of samples of the evidence states, and propagating the evidence states back up the causal dependency links to the conclusion nodes, to obtain a plurality of probabilities of the resulting states of the conclusion nodes; and

outputting a representation of the plurality of the probabilities of the states of the conclusion nodes.

53. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 52, wherein the BN model further includes at least one auxiliary node causally linked between at least one evidence node and at least one conclusion node.

54. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 53, wherein the sampling is performed by a Monte Carlo algorithm.

55. A computer program product for automatically evaluating Bayesian network models for decision support, as set forth in claim 54, wherein the outputted representation is a complete representation of probabilities of states for all conclusions given a particular set of combinations of conclusion states.

56. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 55, wherein the outputted representation is a graphical representation.

57. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 55, wherein the outputted representation is a matrix of averages of probabilities of the conclusion states for implicated conclusions versus a selected set of combinations of conclusion states;

whereby a user can determine an accuracy of the BN model'"'"'s propensity to yield proper conclusions.

58. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 57, wherein the outputted representation is a graphical representation in the form of a two-dimensional intensity matrix and a three-dimensional bar chart.

59. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 58, wherein the conclusion nodes are weighted by weights representing their importance;

whereby the accuracy of the BN model'"'"'s propensity to yield proper conclusions may be weighted for particular conclusions based on their relative importance.

60. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 59, wherein the BN model models a diagnostic domain, with the conclusion nodes representing component failures or diseases, the evidence nodes representing recognizable symptoms of those failures or diseases, and the auxiliary nodes representing additional information useful, in conjunction with the evidence nodes and conclusion nodes.

61. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 52, wherein the BN model further includes at least one auxiliary node causally linked between at least one evidence node and at least one conclusion node.

62. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 52, wherein the sampling is performed by a Monte Carlo algorithm.

63. A computer program product for automatically evaluating Bayesian network models for decision support, as set forth in claim 52, wherein the outputted representation is a complete representation of probabilities of states for all conclusions given a particular set of combinations of conclusion states.

64. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 52, wherein the outputted representation is a graphical representation.

65. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 52, wherein the outputted representation is a matrix of averages of probabilities of the conclusion states for implicated conclusions versus a selected set of combinations of conclusion states;

whereby a user can determine an accuracy of the BN model'"'"'s propensity to yield proper conclusions.

66. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 52, wherein the outputted representation is a graphical representation in the form of a two-dimensional intensity matrix and a three-dimensional bar chart.

67. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 52, wherein the conclusion nodes are weighted by weights representing their importance;

whereby the accuracy of the BN model'"'"'s propensity to yield proper conclusions may be weighted for particular conclusions based on their relative importance.

68. A computer program product for automatically evaluating Bayesian network models for decision support as set forth in claim 52, wherein the BN model models a diagnostic domain, with the conclusion nodes representing component failures or diseases, the evidence nodes representing recognizable symptoms of those failures or diseases, and the auxiliary nodes representing additional information useful, in conjunction with the evidence nodes and conclusion nodes.