Divide-and-Conquer Strategy for Large-Scale Dynamic Bayesian Network Structure Learning
Preprint
Abstract
Dynamic Bayesian Networks (DBNs), renowned for their interpretability, have become increasingly vital in representing complex stochastic processes in various domains such as gene expression analysis, healthcare, and traffic prediction. Structure learning of DBNs from data is challenging, particularly for datasets with thousands of variables. Most current algorithms for DBN structure learning are adaptations from those used in static Bayesian Networks (BNs), and are typically focused on small-scale problems. In order to solve large-scale problems while taking full advantage of existing algorithms, this paper introduces a novel divide-and-conquer strategy, originally developed for static BNs, and adapts it for large-scale DBN structure learning. In this work, we specifically concentrate on 2 Time-sliced Bayesian Networks (2-TBNs), a special class of DBNs. Furthermore, we leverage the prior knowledge of 2-TBNs to enhance the performance of the strategy we introduce. Our approach significantly improves the scalability and accuracy of 2-TBN structure learning. Experimental results demonstrate the effectiveness of our method, showing substantial improvements over existing algorithms in both computational efficiency and structure learning accuracy. On problem instances with more than 1,000 variables, our approach improves two accuracy metrics by 74.45% and 110.94% on average , respectively, while reducing runtime by 93.65% on average.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Less is More: Understanding Word-level Textual Adversarial Attack via n-gram Frequency Descend2024
- Dynamic Causal Graph Convolutional Network for Traffic Prediction2023
- A survey of Bayesian Network structure learningArtificial Intelligence Review, 2023
- Dynamic Bayesian Network Learning to Infer Sparse Models From Time Series Gene Expression DataIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2021
- Generative Adversarial Construction of Parallel PortfoliosIEEE Transactions on Cybernetics, 2020
- A million variables and more: the Fast Greedy Equivalence Search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance imagesInternational Journal of Data Science and Analytics, 2016
- The max-min hill-climbing Bayesian network structure learning algorithmMachine Learning, 2006
- Learning Bayesian network structures by searching for the best ordering with genetic algorithmsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 1996
- On the number of labeled acyclic digraphsDiscrete Mathematics, 1992
- A new look at the statistical model identificationIEEE Transactions on Automatic Control, 1974