Data processing: artificial intelligence – Knowledge processing system
Reexamination Certificate
1996-10-30
2003-03-04
Starks, Jr., Wilbert L. (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
Reexamination Certificate
active
06529888
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data processing systems and, more particularly, to the generation of belief networks.
BACKGROUND OF THE INVENTION
The advent of artificial intelligence within computer science has brought an abundance of decision-support systems. Decision-support systems are computer systems in which decisions, typically rendered by humans, are recommended and sometimes made. In creating decision-support systems, computer scientists seek to provide decisions with as high of a level of accuracy as possible. Thus, computer scientists strive to create decision-support systems that are equivalent to or more accurate than a human expert Applications of decision-support systems include medical diagnosis, troubleshooting computer networks, or other systems wherein a decision is based upon identifiable criteria.
One of the most promising new areas for research in decision-support systems is belief networks. A belief network is a representation of the probabilistic relationships among states of a portion of the world. The states of the world in a belief network can change and are, therefore, called variables. A belief network is expressed as an acyclic-directed graph where the variables correspond to nodes and the relationships between the nodes correspond to arcs.
FIG. 1
depicts an example belief network
101
. In
FIG. 1
there are three variables, X
1
, X
2
, and X
3
, which are represented by nodes
102
,
106
and
110
, respectively. The example belief network contains two arcs
104
and
108
. Associated with each variable in a belief network is a set of probability distributions. Using conditional probability notation, the set of probability distributions for a variable can be denoted by p(x
i
|Π
i
,&xgr;), where “p” refers to the probability distribution, where “Π
i
” denotes the parents of variable X
i
and where “&xgr;” denotes the knowledge of the expert. The Greek letter “&xgr;” indicates that the belief network reflects the knowledge of an expert in a given field. Thus, this expression reads as follows: the probability distribution for variable X
i
given the parents of X
i
and the knowledge of the expert. For example, X
1
is the parent of X
2
. The probability distributions specify the strength of the relationships between variables. For instance, if X
1
has two states (true and false), then associated with X
1
is a single probability distribution p(x
1
|&xgr;) and associated with X
2
are two probability distributions p(x
2
|x
1
=t,&xgr;) and p(x
2
|x
1
=f,&xgr;).
The arcs in a belief network convey dependence between nodes. When there is an arc from a first node to a second node, the probability distribution of the first node depends upon the value of the second node when the direction of the arc points from the second node to the first node. For example, node
106
depends upon node
102
. Therefore, node
106
is said to be conditionally dependent. Missing arcs in a belief network convey conditional independence. For example, node
102
and node
110
are conditionally independent given node
106
. However, two variables indirectly connected through intermediate variables are conditionally dependent given knowledge of the values (“states”) of the intermediate variables. Therefore, if the value for X
2
is known, X
1
and X
3
are conditionally dependent.
In other words, sets of variables X and Y are said to be conditionally independent, given a set of variables Z, if the probability distribution for X given Z does not depend on Y. If Z is empty, however, X and Y are said to be “independent” as opposed to conditionally independent. If X and Y are not conditionally independent, given Z, X and Y are said to be conditionally dependent.
The variables used for each node may be of different types. Specifically, variables may be of two types: discrete or continuous. A discrete variable is a variable that has a finite number of states, whereas a continuous variable is a variable that has an uncountably infinite number of states. An example of a discrete variable is a Boolean variable. Such a variable can assume only one of two states: “true” or “false.” An example of a continuous variable is a variable that may assume any real value between −1 and 1. Discrete variables have an associated probability distribution. Continuous variables, however, have an associated probability density function (“density”). Where an event is a set of possible outcomes, the density &rgr;(x) for a variable “x” and events “a” and “b” is defined as:
ρ
(
x
)
=
Lim
a
->
b
[
ρ
(
a
≤
x
≤
b
)
&LeftBracketingBar;
(
a
-
b
)
&RightBracketingBar;
]
Where &rgr;(a≦x≦b) is the probability that x lies between a and b. Conventional systems for generating belief networks cannot use continuous variables in their nodes.
FIG. 2
depicts an example belief network for troubleshooting automobile problems. The belief network of
FIG. 2
contains many variables
202
,
204
,
206
,
208
,
210
,
212
,
214
,
216
,
218
,
220
,
222
,
224
,
226
,
228
,
230
,
232
, and
234
, relating to whether an automobile will work properly and arcs
236
,
238
,
240
,
242
,
244
,
246
,
248
,
250
,
252
,
254
,
256
,
258
,
260
,
262
,
264
,
268
. A few examples of the relationships between the variables follow. For the radio
214
to work properly, there must be battery power
212
(arc
246
). Battery power
212
, in turn, depends upon the battery working properly
208
and a charge
210
(arcs
242
and
244
). The battery working properly
208
depends upon the battery age
202
(arc
236
). The charge
210
of the battery depends upon the alternator
204
working properly (arc
238
) and the fan belt
206
being intact (arc
240
). The battery age variable
202
, whose values lie from zero to infinity, is an example of a continuous variable that can contain an infinite number of values. However, the battery variable
208
reflecting the correct operations of the battery is a discrete variable being either true or false.
The automobile troubleshooting belief network also provides a number of examples of conditional independence and conditional dependence. The nodes operation of the lights
216
and battery power
212
are conditionally dependent, and the nodes operation of the lights
216
and operation of the radio
214
are conditionally independent given operation of the lights
216
. However, the operation of the radio
214
and the operation of the lights
216
are conditionally dependent given the battery power
212
. The concept of conditional dependence and conditional independence can be expressed using conditional probability notation. For example, the operation of the lights
216
is conditionally dependent on battery power
212
and conditionally independent of the radio
214
. Therefore, the probability of the lights working properly
216
given both the battery power
212
and the radio
214
is equivalent to the probability of the lights working properly given the battery power alone, P(Lights|Battery Power, Radio, &xgr;)=P(Lights|Battery Power, &xgr;). An example of a conditional dependence relationship is the probability of the lights working properly
216
given the battery power
212
is not equivalent to the probability of the lights working properly given no information. That is, p(Lights|Battery Power, &xgr;)≠p(Lights|&xgr;).
There are two conventional approaches for constructing belief networks. Using the first approach (“the knowledge-based approach”), a person known as a knowledge engineer interviews an expert in a given field to obtain the knowledge of the expert about the field of expertise of the expert. The knowledge engineer and expert first determine the distinctions of the world that are important for decision making in the field of the expert. These distinctions correspond to the variables of the domain of the belief network. The “domain” of a belief network is the set of all variables in the belief
Chickering David M.
Geiger Dan
Heckerman David E.
Amin & Turocy LLP
Microsoft Corporation
Starks, Jr. Wilbert L.
LandOfFree
Generating improved belief networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generating improved belief networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating improved belief networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3020540