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

6.4.1 A Hybrid Framework

In dependency analysis, it is assumed that a perfect map exists for a given
data set D. In particular, we assume the existence of a Bayesian network
G, which depicts every conditional independence relation as implied by D
(i.e., I(X, Z, Y )) through d-separation. To check the validity of a conditional
independence assertion I(X, Z, Y )ofanytwonodesX, Y and a conditioning
set Z, CI tests are often used. In the simplest sense, if the assertion I(X, Z, Y )
is valid, X and Y cannot be connected because this will violate that X and
Y are d-separated. In other words, neither the edge X

→ Y nor the edge

X Y will present in the resultant network G. In the SGS algorithm, the

same rationale is used to construct a Bayesian network in the initial steps,
where X—Y is removed from an undirected connected graph for each verified
assertion I(X, Z, Y ).
With such observations, we formulate a general hybrid framework for
Bayesian network learning that consists of two phases. In the first phase,
we conduct low-order CI tests so we know which edge can be removed. Note
that we limit ourselves to use only low-order CI tests because their results are
more reliable than higher order CI tests and the time complexity is bounded.
In the second phase, we use a search-and-score approach with the knowledge
obtained previously. In particular, we refine the search space by excluding
networks that contain the edges X

←

Y for every verified
assertion I(X, Z, Y ). Consequently, the search space is reduced that would
imply a speedup for the search process because we would not waste time
adding (or removing) potentially wrong edges. The proposed framework is
general in the sense that it does not necessitate a particular testing procedure
for the CI test phase or a particular search method in the search phase.
In our work, we propose using cooperative coevolution for searching be-
cause the problem contains certain characteristics that would benefit a mod-
ular decomposition technique. In Fig. 6.6, we provide an outline of the al-
gorithm. Because we use cooperative coevolution and genetic algorithms, we
call our new algorithm CCGA for short.

→ Y and X ←

6.4.2 CI Test Phase

Initially, we let the possible parent set of each node contain all other nodes.
Using the hybrid approach discussed before, we attempt to reduce the size
of the parent set of each node by discovering low-order CI relations. For ex-
ample, if the node X is found to be conditionally independent of node Y
in a test, X will be removed from Y 's parent set and vice versa. Alterna-
tively, it could be viewed as though the edges X Y are both

excluded for further consideration. Because higher-order CI tests may be un-
reliable, we only use order-0 and order-1 tests to discern possible conditional
independence relations.

← Y and X →