Generating improved belief networks

• US 5,802,256 A
• Filed: 05/23/1997
• Issued: 09/01/1998
• Est. Priority Date: 05/09/1994
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chickering, David M., Heckerman, David E., Geiger, Dan
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/862,564
• Time in Patent Office: 466 Days
• Field of Search: 395/10-12, 395/50-51, 395/75-77, 395/900
• US Class Current: 706/59
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

An improved belief network generator is provided. A belief network is generated utilizing expert knowledge retrieved from an expert in a given field of expertise and empirical data reflecting observations made in the given field of the expert. In addition to utilizing expert knowledge and empirical data, the belief network generator provides for the use of continuous variables in the generated belief network and missing data in the empirical data.

Claims

1. A computer-based belief network generator comprising:

a scoring mechanism in memory for receiving empirical data and expert knowledge and for generating a score from the empirical data and the expert knowledge, the expert knowledge comprising a first belief network containing data received from an expert, the first belief network having nodes, each node being a state considered relevant to a decision making process by the expert, each node corresponding to a variable having a value for the state, one type of variable being a continuous type of variable having a value selected from a set of continuous values and one type of variable being a discrete type of variable having a value selected from a set of discrete values, the empirical data comprising a plurality of cases of observations of the nodes in the first belief network;

a network adjuster in memory for determining when to rescore the nodes to obtain a better score in the first belief network, for invoking the scoring mechanism to obtain a better score when the network adjuster determines to rescore the nodes and for creating a second belief network when the network adjuster determines not to rescore the nodes and a processor for executing the scoring mechanism and the network adjuster.

2. A computer-based belief network generator, comprising:

a memory for storing expert knowledge comprising an input belief network containing data received from an expert, the input belief network having an initial score and having nodes and arcs indicating a relationship between the nodes;

a network adjuster that when executed in memory by the processor manipulates arcs in the input belief network to generate an adjusted belief network; and

a scoring mechanism, that when executed in memory by a processor, receives the adjusted belief network empirical receives data containing a plurality of observations for each node in the adjusted belief network, and uses the empirical data to score the nodes of the adjusted belief network for goodness at rendering inferences so that an adjusted score is generated for the adjusted belief network,

wherein when the adjusted score is better that the initial score, the belief network generator designates the adjusted belief network as the generated belief network.

3. The belief network generator of claim 2 wherein the belief network generator is contained in a computer system.

4. The belief network generator of claim 2 wherein a plurality of the nodes contain discrete values and wherein the scoring mechanism scores the nodes containing the discrete values.

5. The belief network generator of claim 2 wherein a plurality of the nodes contain continuous values and wherein the scoring mechanism scores the nodes containing the continuous values.

6. The belief network generator of claim 2 wherein the network adjuster manipulates the arcs to generate a new belief network, and wherein the belief network generator repeatedly invokes the scoring mechanism and the network adjuster until a new belief network with a best score is generated.

7. The belief network generator of claim 2 wherein the empirical data contains a plurality of cases that store the observations, and wherein at least one of the plurality of cases is a missing data case that lacks an observation for at least one node in the belief network.

8. The belief network generator of claim 7 wherein the scoring mechanism approximates a value for the at least one node in the missing data case.

9. The belief network generator of claim 2 wherein the network adjuster stores both the belief network and the score before manipulating the arcs, wherein the network adjuster manipulates the arcs in the belief network to create a new belief network, wherein the scoring mechanism scores the new belief network to generate a new score, and wherein the network adjuster compares the new score to the score and outputs the belief network with a better score.

10. A computer system for generating an improved belief network, comprising:

a secondary storage device, further comprising;

an expert belief network reflecting expert knowledge with nodes and arcs connecting the nodes; and

empirical data comprising observations for the nodes in the expert belief network;

a memory, further comprising;

a scoring mechanism that receives an input belief network, that scores the input belief network for goodness at rendering inferences, and that outputs the score and the input belief network, wherein the input belief network is the expert belief network for a first invocation of the scoring mechanism, and wherein the input belief network is a test belief network upon subsequent invocations of the scoring mechanism; and

a network adjuster for receiving both the score and the input belief network from the scoring mechanism, for generating a test network from the input belief network by readjusting at least one of the arcs in the input belief network to improve the score, for sending the test network to the scoring mechanism to be scored, for receiving the score for the test network, for determining which among the input belief network and the test network has a better score, and for outputting the belief network with the better score as the improved belief network; and

a processor for running the scoring mechanism and the network adjuster.

11. The computer system of claim 10 wherein the network adjuster determines affected nodes that are attached to the at least one of the arcs and sends an indication of the affected nodes to the scoring mechanism, and wherein the scoring mechanism scores the affected nodes.

12. The computer system of claim 10 wherein a plurality of the nodes of the input belief network are discrete nodes with discrete values, and wherein the scoring mechanism scores the input belief network by scoring the discrete nodes.

13. The computer system of claim 10 wherein a plurality of the nodes of the input belief network are continuous nodes with continuous values, and wherein the scoring mechanism scores the input belief network by scoring the continuous nodes.

14. The computer system of claim 10 wherein the empirical data comprises cases that contain the observations and wherein at least one of the cases is a missing data case that lacks an observation for at least one of the nodes in the expert belief network.

15. The computer system of claim 14 wherein the scoring mechanism approximates a value for the at least one of the nodes in the missing data case.