Method for assisting in rendering a decision using improved belief networks

• US 5,696,884 A
• Filed: 10/30/1996
• Issued: 12/09/1997
• 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/739,201
• Time in Patent Office: 405 Days
• Field of Search: 395/50-51, 395/75-77, 395/12, 395/13, 395/10-11
• US Class Current: 706/61
• 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 of the preferred embodiment provides for the use of continuous variables in the generated belief network and missing data in the empirical data.

Claims

1. A method in a computer system having a belief network for assisting in rendering a decision, comprising the steps of:

determining whether the belief network is a complete belief network containing expert knowledge comprising variables with values that causally influence the decision, arcs indicating relationships between the variables and probabilities for each variable indicating strengths of the relationships between the variables, or an incomplete belief network having the variables and lacking the arcs;

receiving empirical data, the empirical data comprising cases of observed values for the variables;

when the belief network is an incomplete belief network,

calculating weights for each pair of variables in the belief network, each weight having a value;

determining a maximum weight spanning tree from the belief network such that a sum of the values of the calculated weights in the maximum weight spanning tree is a maximum value; and

modifying the maximum weight spanning tree utilizing the received empirical data; and

when the belief network is a complete belief network,

modifying the complete belief network utilizing the received empirical data.

2. The method of claim 1 wherein the step of calculating weights includes the steps of:

for each pair of variables in the incomplete belief network,

calculating a first subscore utilizing a first variable and a second variable in the pair of variables, the first subscore for indicating goodness of the first variable for rendering inferences when an arc connects the first variable to the second variable;

calculating a second subscore utilizing the first variable and an empty set, the second subscore for indicating goodness of the first variable for rendering inferences when the first variable is unconnected to the second variable;

calculating a first logarithm of the first subscore;

calculating a second logarithm of the second subscore; and

subtracting the second logarithm from the first logarithm to create a weight.

3. A computer-readable medium whose contents cause a computer system having a belief network for assisting in rendering a decision to modify the belief network, by performing the steps of:

determining whether the belief network is a complete belief network containing expert knowledge comprising variables with values that causally influence the decision, arcs indicating relationships between the variables and probabilities for each variable indicating strengths of the relationships between the variables, or an incomplete belief network having the variables and lacking the arcs;

receiving empirical data, the empirical data comprising cases of observed values for the variables;

when the belief network is an incomplete belief network,

calculating weights for each pair of variables in the belief network, each weight having a value;

determining a maximum weight spanning tree from the belief network such that a sum of the values of the calculated weights in the maximum weight spanning tree is a maximum value; and

modifying the maximum weight spanning tree utilizing the received empirical data; and

when the belief network is a complete belief network,

modifying the complete belief network utilizing the received empirical data.