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

conflict such that X . 9 Hence, we differentiate

those edge additions that will create a conflict from those that will not. For
those that are not in conflict, they are incorporated directly to

← Y and X → Y coexist in S

S .

Y ) should be kept is equiva-
lent to determining the proper orientation of the undirected edge X—Y .For
this, we use the approach: When we know more about the rest of the net-
work, we would know how to orient the edge. Simply put, with the remaining
part of the network known and fixed, we try all possibilities of the unoriented
part. Finally, the best configuration is incorporated into S.
For the set of conflicting edges, related ones are first grouped together.
By related edges, we mean edges that share a common set of nodes, W. Next,
different configurations of orientating the group of related edges are tried
and evaluated. Because the MDL metric is node-decomposable, it su ces to
evaluate the total MDL score of W . Note that although the present configura-
tion is tried, the parent set of each node contains every other known parents.
Because each conflicting edge has two orientation possibilities, there are 2 m
configurations to try for a group of m edges (m is usually small). Finally,
the configuration that gives the best score is used to update

To determine which edge (X ← Y and X →

. This process
is then repeated for the other groups. Because the best configuration of a
group may contain cycles, the resultant

S

is repaired for cycles. Although it
is possible to check for cycles when trying different orientation possibilities,
we suggest avoiding it, as the involved cost will be great.
Update of the Best-So-Far Structure. To obtain the best structure dur-
ing the course of searching, we have maintained a best-so-far structure sepa-
rately. In each generation, we try to merge the currently best-so-far structure
with

S

may contain some good partial structures, it is expected
that a good solution can be obtained by accumulating the essential compo-
nents of

S . Because S

into the best-so-far structure. If a better structure is created, the
new structure will become the best-so-far structure.
To perform the recombination, we invent a heuristic that attempts to
exchange parent sets between the two network structures. Because the score
of a network structure is simply the summation of the scores of the parent
sets, it enables us to perform greedy operations so that better ones (i.e.,
parent sets) will substitute the worse. Furthermore, our heuristic algorithm
performs cycle checking for each substitution so that the outcome has a legal
structure.
9 To be specific, there are two cases of conflict. First, X → Y and Y → X are both
found on the list of update. Second, X → Y is found and there is no update for
node X and Y → X is contained in S.

S