Using Cooperative Coevolution for Data Mining of Bayesian Networks - Advanced Techniques in Knowledge Discovery and Data Mining - page 155

Different methods of applying evolutionary computation to learn Bayesian
networks are presented in Section 6.3. In Section 6.4, we describe our algo-
rithm in detail. In Section 6.5, we present a comparison between the new
algorithm and another existing algorithm (MDLEP). We conclude the chap-
ter with Section 6.6.

6.2 Background

6.2.1 Bayesian NetworkLearning

It was not until Pearl's work [6.10] that Bayesian networks were given a
solid foundation. Basically, Bayesian networks are directed acyclic graphs
(DAG), which describe conditional independency relations. Each node in the
graph corresponds to a discrete random variable in the domain, U. Each edge
designates a parent-and-child relation. For a given node X

U, all of its
parents constitute the parent set of X, which is denoted by Π X . In addition
to the graphical structure, there are conditional probability tables (CPT)
specifying the conditional probability distribution of each domain variable
given its parent set.
Because Bayesian networks are founded on the notion of conditional in-
dependency, it is necessary to give a brief description of the subject. A con-
ditional independence relation is a three-place relationship among distinct
subsets of variables X, Y ,andZ, denoted by I(X, Z, Y ). Equivalently, we
say X and Y are conditionally independent given the conditioning set, Z.
Formally speaking, the following relationship holds [6.10]:

∈

P (x, y | z)=P (x | z) whenever P (y, z) > 0, (6.1)

where x, y,andz are any instantiations of the sets X, Y ,andZ, respectively,
and P is the probability distribution. A conditional independence relation is
characterized by its order, which is simply the size of the conditioning set Z.
By definition, a Bayesian network encodes the joint probability distribu-
tion of the domain variables U =

{ N 1 ,...,N n } :

P (N 1 ,...N n )=
i

P (N i | Π N i ). (6.2)

The Dependency Analysis Approach. As mentioned before, researchers
treat the network learning problem in two very different ways. The first
approach, called the dependency analysis approach, takes the view that
Bayesian networks depict conditional independence relations among the vari-
ables. Hence, the approach relies on discovering conditional independence
relations from the data for network construction. Work belonging to this cat-
egory include [6.5], [6.11], and [6.4]. Typically, the existence of a perfect map