Estimation of Distribution Algorithms with Matrix Transpose in Bayesian Learning

Dae-Won Kim, Song Ko, Bo-Yeong KangarXiv 2024 · DOI · arXiv

Introduction

Learning the structure of a Bayesian network—identifying the directed dependencies among a set of variables—is a computationally intensive NP-hard problem. As the number of variables increases, the search space of possible structures grows exponentially. Researchers frequently employ Estimation of Distribution Algorithms (EDAs), a class of evolutionary algorithms, to navigate this space. However, standard EDAs often struggle with premature convergence to local optima and the generation of "illegal" structures (cycles) during mutation, which violate the Directed Acyclic Graph (DAG) requirement of Bayesian networks.

Methodology: Matrix Transpose Mutation

To address these challenges, this research introduces a specialized mutation operator based on matrix transposition designed to enhance structural search.

Network Representation

A Bayesian network is represented as an $n \times n$ binary adjacency matrix $M$. In this representation, a value of '1' at $M(i, j)$ indicates that variable $i$ is a parent of variable $j$.

Figure 2: Adjacency matrix representation of a directed acyclic graph.

The Transpose Operator

Traditional bitwise mutations often disrupt the structural validity of the network by randomly flipping bits. The proposed "transpose mutation" instead swaps $M(i, j)$ with $M(j, i)$ based on a defined mutation rate ($r$). This operation effectively tests the reversal of an existing arc (e.g., transforming $A \to B$ into $B \to A$).

This approach is more intuitive for Bayesian learning as it focuses on the most critical structural element: arc direction. Furthermore, it is a "closed operator" that is significantly less likely to introduce illegal cycles compared to random bit flipping. The authors integrated this operator into four EDA variants: Univariate Marginal Distribution Algorithm (UMDA), Population-Based Incremental Learning (PBIL), Mutual-Information-Maximizing Input Clustering (MIMIC), and the Bayesian Optimization Algorithm (BOA).

Experimental Evaluation

The proposed methods were evaluated using two benchmark datasets: Diabetes (medical dependencies) and Asia (synthetic lung disease diagnostics). These datasets serve as gold standards because their ground-truth structures are known, enabling precise measurement of algorithmic accuracy.

Performance Results

The integration of the transpose mutation (+T) yielded substantial improvements in precision across nearly all tested EDAs, outperforming both standard baselines and traditional bitwise mutation (+B).

Figure 3: Precision results comparing standard EDAs, bitwise mutation (+B), and transpose mutation (+T) across datasets.

Key findings include:

  • Significant Precision Gains: On the Diabetes dataset, PBIL+T achieved a precision of 79.9%, nearly doubling the 42.0% precision of the baseline PBIL.
  • Superiority over Bitwise Mutation: The transpose mutation consistently outperformed traditional bitwise mutation. In the Asia dataset, +T versions showed accuracy improvements ranging from 10% to 35% over standard baselines.
  • Reduction in Directional Errors: The operator was particularly effective at correcting "Reverse" arcs. In the Diabetes dataset, the occurrence of reversed arcs fell from 43.9% in standard EDAs to 26.4% with the transpose mutation.

Discussion and Conclusion

The success of the transpose mutation stems from its alignment with the problem's underlying geometry. By treating arcs as potentially bi-directional during the search phase, the algorithm can effectively "correct" identified relationships where the causal direction was initially misidentified.

While the results are promising, the effectiveness of the transpose operator may be linked to the specific probabilistic model used by the EDA, as seen in the varying performance of MIMIC+T. Future work should explore the scalability of this operator on larger networks and investigate optimal configurations for diverse Bayesian learning tasks.

Summary updated

Abstract

Estimation of distribution algorithms (EDAs) constitute a new branch of evolutionary optimization algorithms, providing effective and efficient optimization performance in a variety of research areas. Recent studies have proposed new EDAs that employ mutation operators in standard EDAs to increase the population diversity. We present a new mutation operator, a matrix transpose, specifically designed for Bayesian structure learning, and we evaluate its performance in Bayesian structure learning. The results indicate that EDAs with transpose mutation give markedly better performance than conventional EDAs.
BibTeX
@misc{kim2024estimation,
  author = {Dae-Won Kim and Song Ko and Bo-Yeong Kang},
  title = {{Estimation of Distribution Algorithms with Matrix Transpose in Bayesian Learning}},
  year = {2024},
  eprint = {2407.18257},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.18257},
}
Figure