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.
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