Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
1998-12-23
2003-03-04
Starks, Jr., Wilbert L. (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S059000, C706S060000, C707S793000
Reexamination Certificate
active
06529891
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data processing systems and, more particularly, to the generation of Bayesian 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 the greatest possible accuracy. 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 Bayesian networks. A Bayesian network is a representation of the probabilistic relationships among distinctions about the world. Each distinction, sometimes called a variable, can take on one of a mutually exclusive and exhaustive set of possible states. A Bayesian 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 examplary Bayesian 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. This Bayesian network contains two arcs
104
and
108
. Associated with each variable in a Bayesian 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 Bayesian 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;). In the remainder of this specification, &xgr; is not specifically mentioned.
The arcs in a Bayesian network convey dependence between nodes. When there is an arc between two nodes, 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, nodes
102
and
106
are said to be conditionally dependent. Missing arcs in a Bayesian network convey conditional independencies. 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 lack of knowledge of the values (“states”) of the intermediate variables. Therefore, if the value for node
106
is known, node
102
and node
110
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, then X and Y are said to be conditionally dependent given Z.
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 or countable number of states, whereas a continuous variable is a variable that has an uncountably infinite number of states. All discrete variables considered in this specification have a finite 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 p(x) for a variable “x” and events “a” and “b” is defined as:
p
(
x
)
=
Lim
a
→
b
[
p
(
a
≤
x
≤
b
)
&LeftBracketingBar;
(
a
-
b
)
&RightBracketingBar;
]
where p(a≦x≦b) is the probability that x lies between a and b. Conventional systems for generating Bayesian networks cannot use continuous variables in their nodes.
FIG. 2
depicts an example Bayesian network for troubleshooting automobile problems. The Bayesian 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 Bayesian 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 dependent, and the nodes operation of the lights
216
and operation of the radio
214
are conditionally independent given battery power
212
. However, the operation of the radio
214
and the operation of the lights
216
are conditionally dependent. 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
given the battery power
212
. 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)=P(Lights|Battery Power). An example of a conditional dependence relationship is the probability of the lights working properly
216
given the battery power
212
which is not equivalent to the probability of the lights working properly given no information. That is, p(Lights|Battery Power)≠p(Lights).
There are two conventional approaches for constructing Bayesian 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
Amin & Turocy LLP
Microsoft Corporation
Starks, Jr. Wilbert L.
LandOfFree
Automatic determination of the number of clusters by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic determination of the number of clusters by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic determination of the number of clusters by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3042881