Design of Evolutionary Methods Applied to the Learning of Bayesian Network Structures

Thierry Brouard, Alain Delaplace, Muhammad Muzzamil Luqman, Hubert Cardot, Jean-Yves Ramel, Thierry, Muhammad MuzzamilSciyo 2010 · DOI · OpenAlex

Abstract

This paper presents three novel methods for learning the structure of a Bayesian network using genetic algorithms (GAs). The first method involves controlling the probability distribution of mutations (GA-AM). The second incorporates a penalty scheme to avoid redundant search areas through sequential niching (GA-SN). The third method utilizes a hybrid island model (GA-HN) to allow timely exchange among competing populations. Experimental results on large databases demonstrate that these algorithms, particularly the niching strategies, successfully navigate complex search spaces to find optimal network structures.

Introduction: The Complexity of Structure Learning

Bayesian Networks (BNs) are powerful tools for modeling conditional dependencies between variables. However, "learning" the right graph structure—the Directed Acyclic Graph (DAG)—from a raw database is an NP-hard problem. The search space for these graphs grows exponentially with the number of variables, making it a "needle in a haystack" challenge where algorithms easily get stuck in local optima.

An example of a Bayesian Network structure with its associated Conditional Probability Tables (CPTs).

Traditional methods often fall into two traps: constraint-based methods rely on independence tests that fail when data is scarce, while score-based methods often get trapped in sub-optimal solutions due to the jagged landscape of possible graphs. This research employs Evolutionary Methods to maintain genetic diversity and prevent premature convergence.

Methodology

The proposed framework features a unique Repair Operator that uses mutual information to break any cycles formed during crossover or mutation, ensuring every individual remains a valid DAG. Building on this, three specific strategies are introduced:

  • GA-AM (Adaptive Mutation): Instead of a fixed mutation rate, this scheme tracks successful mutation operations (adding, removing, or reversing arcs) and biases future mutations toward those successful strategies.
  • GA-SN (Sequential Niching): When the algorithm finds a local optimum (a Markov equivalence class of graphs), it records it in a penalty list. This forces the search to explore entirely new "niches" of the search space.
  • GA-HN (Hybrid Niching): This combines sequential niching with an Island Model. The population is split into isolated "islands" that evolve independently and occasionally swap individuals, providing both local exploitation and global exploration.

Experimental Evaluation

The researchers evaluated their methods using two "gold standard" Bayesian Network benchmarks: INSURANCE (27 variables, 52 arcs) and ALARM (37 variables, 46 arcs). They tested these against varying database sizes (250 to 2000 samples).

Key Results

  • Superior Accuracy: In the INSURANCE network tests, the GA variants consistently achieved better BIC scores than traditional greedy search (GS) and the PC algorithm.
  • Structural Fidelity: Using a "graphic distance" metric, the GA-SN and GA-HN models produced graphs much closer to the original gold standard networks than competing methods.
  • Efficiency: While GAs are often seen as slow, the GA-HN model found the best solutions in significantly fewer iterations than the standard GA. For the ALARM network, GA-HN was only three times slower than a simple greedy search—a small price to pay for a much higher chance of finding the global optimum.

Conclusion

A significant insight from this work is the use of Markov equivalence classes as niches. Penalizing an entire class prevents the GA from wasting time on redundant structures. While evolutionary methods require more computational overhead than simple heuristics, their robustness against local optima makes them superior for complex tasks, such as graphic symbol recognition. Future work will focus on scaling these spatial niching strategies to handle even larger search spaces involving hundreds of variables.

Summary updated

Abstract

We have presented three methods for learning the structure of a Bayesian network. The first one consists in the control of the probability distribution of mutation in the genetic algorithm. The second one is to incorporate a scheme penalty in the genetic algorithm so that it avoids certain areas of space research. The third method is to search through several competing populations and to allow timely exchange among these populations. We have shown experimentally that different algorithms behaved satisfactorily, in particular that they were proving to be successful on large databases. We also examined the behavior of proposed algorithms. Niching strategies are interesting, especially using the spatial one, which focuses quickly on the best solutions.
BibTeX
@inproceedings{brouard2010design,
  author = {Thierry Brouard and Alain Delaplace and Muhammad Muzzamil Luqman and Hubert Cardot and Jean-Yves RAMEL and Thierry and Muhammad Muzzamil},
  title = {{Design of Evolutionary Methods Applied to the Learning of Bayesian Network Structures}},
  booktitle = {Sciyo},
  year = {2010},
  doi = {10.5772/10078},
}
Figure