Learning Discretized Bayesian Networks with GOMEA

Damy M. F. Ha, Tanja Alderliesten, Peter A. N. Bosman

Introduction

Bayesian Networks (BNs) are a cornerstone of explainable artificial intelligence (XAI), providing a transparent, probabilistic framework for representing complex dependencies between variables. However, a significant hurdle in applying BNs to real-world data is the prevalence of continuous variables. While standard BN learning algorithms typically require discrete data, the process of discretization—partitioning continuous ranges into bins—is often treated as an independent preprocessing step.

This sequential approach creates a "chicken-and-egg" problem: the optimal discretization depends on the underlying network structure, yet the structure itself is inferred from the discretized data. To address this, researchers have introduced DBN-GOMEA, an evolutionary algorithm designed to simultaneously optimize both the network structure and the discretization parameters.

Methodology: The DBN-GOMEA Framework

The core innovation of DBN-GOMEA lies in its use of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA). Unlike standard genetic algorithms, GOMEA utilizes a hierarchical "linkage tree" to model dependencies between different components of the solution.

Joint Genotype and Linkage Learning

In DBN-GOMEA, a solution is represented by a joint genotype that encodes both the presence of edges in the directed acyclic graph (DAG) and the number of discretization bins for each continuous variable. By evolving these elements together, the algorithm can identify synergistic combinations of bins and edges. The linkage tree is particularly effective here, as it clusters discretization variables with the specific edges they influence, allowing the algorithm to preserve and propagate high-quality "building blocks" of the model.

A Bayesian Network (BN) represented as a Directed Acyclic Graph (DAG) alongside its genotype representation used by the algorithm.

Multi-Objective Optimization

To enhance the utility of BNs in expert-driven domains, the researchers developed MO-DBN-GOMEA. This variant frames the learning process as a multi-objective optimization problem, seeking to balance three often-conflicting goals:

  1. Accuracy: Maximizing the log-likelihood of the data.
  2. Complexity: Minimizing the number of parameters to prevent overfitting and maintain interpretability.
  3. Expert Alignment: Minimizing the Kullback-Leibler (KL) divergence from a network structure provided by a domain expert.

Experimental Results

The algorithm was evaluated using synthetic datasets generated from ground-truth BNs with varying levels of complexity and different discretization schemes (Equal-Width and Equal-Frequency).

Performance and Scalability

DBN-GOMEA demonstrated superior performance in retrieving the original ground-truth structures compared to existing methods like LDBN. Specifically, the version utilizing Equal-Frequency discretization (DBN-GOMEA-EF) showed robust accuracy across various sample sizes. While the algorithm scales well with the number of data points, memory constraints were noted for versions using more complex Bayesian Discretization (BD) schemes as the number of variables increased.

The multi-objective approach provides a 3D "approximation front" of candidate models. This visualization allows users to see the trade-offs between data fit, model simplicity, and adherence to prior knowledge. In many cases, the algorithm identified models that were more accurate than the expert's initial guess while remaining significantly simpler than a purely data-driven model.

A 3D visualization of the multi-objective approximation front, showing the trade-offs between density, complexity, and KL divergence.

Discussion and Future Directions

The success of DBN-GOMEA highlights the importance of joint optimization in probabilistic graphical modeling. By treating discretization as a first-class citizen in the learning process, the algorithm avoids the information loss inherent in static preprocessing.

Future work aims to refine the discretization process further by exploring mixed-integer approaches, where bin boundaries are optimized as real-valued parameters rather than just selecting the number of bins. Additionally, applying MO-DBN-GOMEA to real-world datasets in high-stakes fields like medicine will be crucial to validating its effectiveness as an "expert advisor" tool in XAI workflows.

Summary updated

BibTeX
@inproceedings{ha2024learning,
  author = {Damy M. F. Ha and Tanja Alderliesten and Peter A. N. Bosman},
  title = {{Learning Discretized Bayesian Networks with GOMEA}},
  booktitle = {PPSN},
  year = {2024},
  doi = {10.1007/978-3-031-70071-2\_22},
}
Figure