Method for knowledge acquisition for diagnostic bayesian networks

• US 6,456,622 B1
• Filed: 03/03/1999
• Issued: 09/24/2002
• Est. Priority Date: 03/03/1999
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Jensen, Finn V., Kjærulff, Udde, Skaanning, Claus
• Primary Examiner(s): TON, DANG T
• Application Number:
  US09/261,769
• Time in Patent Office: 1,301 Days
• Field of Search: 370/389, 370/397, 370/399, 370/400, 370/254, 370/252, 370/256, 370/257, 370/255, 370/401, 370/403, 370/406, 370/407, 370/408, 370/409, 370/241, 370/216, 370/360, 370/372, 370/370, 706/59, 706/45, 706/12, 706/61, 706/20, 706/18, 707/33, 707/51, 707/10, 707/4, 707/104, 707/100, 707/103, 707/200, 707/522, 704/256, 704/231, 704/232
• US Class Current: 370/389
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A Bayesian network includes a set of nodes representing discrete-valued variables. A plurality of arcs connect nodes from the set of nodes. The arcs represent the causal dependencies between the nodes. A prior marginal probability value is associated with each leaf node. The prior marginal probability values are calculated by first estimating conditional probabilities for nodes. For example, for each node with parent nodes, knowledge acquisition questions are developed which when answered will indicate the conditional probability of each parent node of the node. The questions and answer assume a single occurrence of a fault (the single-fault assumption). That is, it is assumed that one and only one variable represented by the plurality of parent nodes will be in its positive state (i.e., the fault will occur). Thus a sum of the conditional probabilities for all variables represented by all parent nodes for any particular node will always be equal to one. Constraint nodes are added to the Bayesian network to enforce the single occurrence assumption. In order to obtain a prior marginal probability for each leaf node, a conditional probability of the leaf node is multiplied with conditional probabilities for each node which is a descendent of the leaf node.

Claims

1. A method for efficient construction and use of a decision support system, the method comprising the following steps:

(a) storing in a memory of a computing system a Bayesian network as a tree structure having leaf nodes which have no parent nodes and other nodes which have parent nodes, each node for the tree structure representing a variable;

(b) for each node that has a plurality of parent nodes, developing knowledge acquisition questions that when answered will indicate conditional probability for each parent node given one of the plurality of parent nodes is in a positive state, including the following substeps;

(b.1) when developing knowledge acquisition questions, assuming that for each node one and only one variable represented by the plurality of parent nodes will be in a positive state,

(b.2) storing the knowledge acquisition questions along with the Bayesian network;

(c) obtaining answers to a subset of the knowledge acquisition questions, and

(d) calculating prior marginal probabilities for each leaf node based on conditional probabilities obtained from the answers to the subset of the knowledge acquisition questions, the answers being used in constructing the Bayesian network

(e) supporting, by the decision support system, decision making by a user, including the following substep;

using the Bayesian network by the decision support system when supporting decision making by the user.

2. A method as in claim 1 wherein step (d) includes the following substep:

in order to obtain a prior marginal probability for each leaf node, multiplying the conditional probabilities for each node which is a descendent of each leaf node.

3. A method as in claim 1 wherein in step (a), a root node for the tree structure represents a problem and parent nodes for the root node represent causes of the problem.

4. A method as in claim 1 wherein in step (a), a root node for the tree structure represents a problem, parent nodes for the root node represent causes of the problem, and any subsequent levels of nodes represent sub-causes.

5. A method as in claim 4 wherein in step (c) the answers are obtained from domain experts who have expertise in the problem, causes and subcauses of the problem.

6. Storage media that stores an executable program, the executable program including a Bayesian network, the Bayesian network comprising:

a set of nodes representing discrete-valued variables;

a plurality of arcs connecting nodes from the set of nodes, the arcs representing causal dependencies between the nodes; and

,

a set of prior marginal probability values, one prior marginal probability value associated with each leaf node;

wherein the prior marginal probability values are calculated as follows;

for each node A with a plurality of parent nodes, estimating a conditional probability for each parent node given node A is in a positive state so that a sum of conditional probabilities for all the parent nodes is equal to one, and

in order to find obtain a prior marginal probability for each leaf node, multiplying conditional probabilities for each node which is a descendent of the leaf node; and

,

wherein when executed the executable program acts as a decision support system that utilizes the Bayesian network.

7. Storage media as in claim 6 wherein the conditional probability for each parent node of node A is obtained by developing knowledge acquisition questions which when answered will indicate conditional probability of each parent node assuming that one and only one parent node of node A will be in a positive state.

8. Storage media as in claim 6, wherein the Bayesian network additionally comprises:

constraint variables associated with the set of nodes, the constraint variables enforcing a single-fault assumption between the nodes.

9. A method for constructing and utilizing a decision support system, the method comprising the following steps:

(a) performing efficient knowledge acquisition for a Bayesian network to be used within the decision support system, including the following substeps;

(a.1) estimating a conditional probability that there is a problem;

(a.2) for each potential cause of the problem, performing the following substep;

(a.2.1) estimating a conditional probability that the problem was caused by the potential cause of the problem, given that the problem is present; and

,

(a.3) for each potential cause which has subcauses, performing the following substep for each subcause;

(a.3.1) estimating a conditional probability that the subcause underlies the potential cause, given that the problem is caused by the potential cause; and

,

(b) utilizing the Bayesian network when performing decision support with the decision support system.

10. A method as in claim 9 wherein step (a) additionally includes the following substep performed recursively:

(a.4) for each subcause which has additional subcauses, performing the following substep for each additional subcause of the subcause;

(a.4.1) estimating a conditional probability that the additional subcause underlies the subcause, given that the problem is caused by the subcause.

11. A method as in claim 9 wherein estimates are performed by posing knowledge acquisition questions to domain experts.

12. A method as in claim 9 wherein step (a) additionally includes the following substep:

(a.4) for each cause and subcause of the Bayesian network which represents a leaf node of the Bayesian network, calculating a prior marginal probability for the leaf node by multiplying conditional probabilities of all nodes which descend from the leaf node.

13. A method as in claim 9 wherein step (a) additionally includes the following substep:

(a.4) adding constraint variables to the Bayesian network to enforce a single-fault assumption.

14. A method for constructing and using a Bayesian network, comprising the following substeps

(a) constructing a basic form for the Bayesian network using a single-fault assumption:

(b) performing knowledge acquisition for the Bayesian network, comprising the following substeps;

(b.1) estimating a conditional probability that there is a problem;

(b.2) for each potential cause of the problem, performing the following substep;

(b.2.1) estimating a conditional probability that the problem was caused by the potential cause of the problem, given that the problem is present; and

,

(b.3) for each potential cause which has subcauses, performing the following substep for each subcause;

(b.3.1) estimating a conditional probability that the subcause underlies the potential cause, given that the problem is caused by the potential cause;

(c) using the Bayesian network as part of a decision support system.

15. A method as in claim 14 wherein step (b) additionally comprises the following substep:

(b.4) for each subcause which has additional subcauses, performing the following substep for each additional subcause of the subcause;

(d.4.1) estimating a conditional probability that the additional subcause underlies the subcause, given that the problem is caused by the subcause.

16. A method as in claim 14 wherein in substep (b.1), substep (b.2.1) and substep (b.3.1), the estimates are performed by posing knowledge acquisition questions to domain experts.

17. A method as in claim 14 wherein step (b) additionally comprises the following substep:

(b.4) for each cause and subcause of the Bayesian network which represents a leaf node of the Bayesian network, calculating a prior marginal probability for the leaf node by multiplying conditional probabilities of all nodes which descend from the leaf node.

18. A method as in claim 14 additionally comprising the following step performed before step (c):

(d) adding constraint variables to the Bayesian network to enforce the single-fault assumption.

19. A method used for efficient construction of a Bayesian network, the method comprising the following steps:

(a) storing in a memory of a computing system an executable program that includes a representation of at least a portion of the Bayesian network as a tree structure having leaf nodes which have no parent nodes and other nodes which have parent nodes, each node for the tree structure representing a variable;

(b) for each node that has a plurality of parent nodes, developing knowledge acquisition questions that when answered will indicate conditional probability for each parent node given one of the plurality of parent nodes is in a positive state, including the following substeps;

(b.1) when developing knowledge acquisition questions, assuming that for each node one and only one variable represented by the plurality of parent nodes will be in a positive state,

(b.2) storing the knowledge acquisition questions along with the Bayesian network;

(c) executing the stored program, including the following substeps performed by the computing system as directed by the executing stored program;

(c.1) obtaining answers to a subset of the knowledge acquisition questions, and

(c.2) calculating prior marginal probabilities for each leaf node based on conditional probabilities obtained from the answers to the subset of the knowledge acquisition questions, the answers being used by the executable program in constructing the Bayesian network.

20. A method as in claim 19 wherein substep (c.2) includes the following substep:

in order to obtain a prior marginal probability for each leaf node, multiplying the conditional probabilities for each node which is a descendent of each leaf node.

21. A method as in claim 19 wherein in step (a), a root node for the tree structure represents a problem and parent nodes for the root node represent causes of the problem.

22. A method as in claim 19 wherein in step (a), a root node for the tree structure represents a problem, parent nodes for the root node represent causes of the problem, and any subsequent levels of nodes represent sub-causes.

23. A method as in claim 19 wherein in substep (c.19) the answers are obtained from domain experts who have expertise in the problem, causes and subcauses of the problem.