journal article Open Access Jun 15, 2021

Improved Local Search with Momentum for Bayesian Networks Structure Learning

Entropy Vol. 23 No. 6 pp. 750 · MDPI AG
View at Publisher Save 10.3390/e23060750
Abstract
Bayesian Networks structure learning (BNSL) is a troublesome problem that aims to search for an optimal structure. An exact search tends to sacrifice a significant amount of time and memory to promote accuracy, while the local search can tackle complex networks with thousands of variables but commonly gets stuck in a local optimum. In this paper, two novel and practical operators and a derived operator are proposed to perturb structures and maintain the acyclicity. Then, we design a framework, incorporating an influential perturbation factor integrated by three proposed operators, to escape current local optimal and improve the dilemma that outcomes trap in local optimal. The experimental results illustrate that our algorithm can output competitive results compared with the state-of-the-art constraint-based method in most cases. Meanwhile, our algorithm reaches an equivalent or better solution found by the state-of-the-art exact search and hybrid methods.
Topics

No keywords indexed for this article. Browse by subject →

References
41
[1]
Pearl, J. (2014). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Elsevier.
[2]
Nikovski "Constructing Bayesian networks for medical diagnosis from incomplete and partially correct statistics" IEEE Trans. Knowl. Data Eng. (2000) 10.1109/69.868904
[3]
Gestal "Exploring patterns of epigenetic information with data mining techniques" Curr. Pharm. Des. (2013) 10.2174/138161213804581936
[4]
Maas, R., Huemmer, C., Hofmann, C., and Kellermann, W. (2014, January 24–26). On Bayesian networks in speech signal processing. Proceedings of the Speech Communication; 11. ITG Symposium, Erlangen, Germany.
[5]
Sekmen "Assessment of adaptive human–robot interactions" Knowl.-Based Syst. (2013) 10.1016/j.knosys.2013.01.003
[6]
Su "Using Bayesian networks to discover relations between genes, environment, and disease" Biodata Min. (2013) 10.1186/1756-0381-6-6
[7]
Chickering "Large-sample learning of Bayesian networks is NP-hard" J. Mach. Learn. Res. (2004)
[8]
Spirtes, P., Glymour, C.N., Scheines, R., and Heckerman, D. (2000). Causation, Prediction, and Search, MIT Press. 10.7551/mitpress/1754.001.0001
[9]
Colombo "Order-independent constraint-based causal structure learning" J. Mach. Learn. Res. (2014)
[10]
The max-min hill-climbing Bayesian network structure learning algorithm

Ioannis Tsamardinos, Laura E. Brown, Constantin F. Aliferis

Machine Learning 2006 10.1007/s10994-006-6889-7
[11]
Scutari "Who learns better Bayesian network structures: Accuracy and speed of structure learning algorithms" Int. J. Approx. Reason. (2019) 10.1016/j.ijar.2019.10.003
[12]
Koivisto "Exact Bayesian structure discovery in Bayesian networks" J. Mach. Learn. Res. (2004)
[13]
Silander, T., and Myllymaki, P. (2012). A simple approach for finding the globally optimal Bayesian network structure. arXiv.
[14]
Wang "Learning Bayesian networks based on order graph with ancestral constraints" Knowl.-Based Syst. (2021) 10.1016/j.knosys.2020.106515
[15]
Ji "Efficient structure learning of Bayesian networks using constraints" J. Mach. Learn. Res. (2011)
[16]
Cussens, J. (2012). Bayesian network learning with cutting planes. arXiv.
[17]
Jaakkola, T., Sontag, D., Globerson, A., and Meila, M. (2010, January 13–15). Learning Bayesian network structure using LP relaxations. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, Sardinia, Italy.
[19]
Yuan, C., Malone, B., and Wu, X. (2011, January 16–22). Learning optimal Bayesian networks using A* search. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, Barcelona, Spain.
[20]
Malone, B., and Yuan, C. (2013). Evaluating anytime algorithms for learning optimal Bayesian networks. arXiv.
[21]
Tan "Bidirectional heuristic search to find the optimal Bayesian network structure" Neurocomputing (2021) 10.1016/j.neucom.2020.10.049
[22]
Heckerman, D. (2008). A tutorial on learning with Bayesian networks. Innovations in Bayesian Networks, Springer. 10.1007/978-3-540-85066-3_3
[23]
Chickering, D.M. (2013). A transformational characterization of equivalent Bayesian network structures. arXiv.
[24]
Puerta "Scaling up the greedy equivalence search algorithm by constraining the search space of equivalence classes" Int. J. Approx. Reason. (2013) 10.1016/j.ijar.2012.09.004
[25]
Teyssier, M., and Koller, D. (2012). Ordering-based search: A simple and effective algorithm for learning Bayesian networks. arXiv.
[26]
Scanagatta, M., Corani, G., and Zaffalon, M. (2017, January 20–22). Improved local search in Bayesian networks structure learning. Proceedings of the 3rd International Workshop on Advanced Methodologies for Bayesian Networks, Kyoto, Japan.
[27]
Hoos, H.H., and Stützle, T. (2004). Stochastic local search: Foundations and applications, Elsevier.
[28]
Lee, C., and van Beek, P. (2017). Metaheuristics for score-and-search Bayesian network structure learning. Canadian Conference on Artificial Intelligence, Springer. 10.1007/978-3-319-57351-9_17
[29]
Scanagatta, M., de Campos, C.P., Corani, G., and Zaffalon, M. (2015, January 7–12). Learning Bayesian Networks with Thousands of Variables. Proceedings of the 28th International Conference on Neural Information Processing Systems, Montreal, QC, Canada.
[30]
Koller, D., and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques, MIT Press.
[31]
Buntine, W. (1991). Theory refinement on Bayesian networks. Uncertainty Proceedings 1991, Elsevier. 10.1016/b978-1-55860-203-8.50010-3
[32]
Suzuki, J. (1993). A construction of Bayesian networks from databases based on an MDL principle. Uncertainty in Artificial Intelligence, Elsevier. 10.1016/b978-1-4832-1451-1.50037-8
[33]
Estimating the Dimension of a Model

Gideon Schwarz

The Annals of Statistics 1978 10.1214/aos/1176344136
[34]
Akaike, H. (1998). Information theory and an extension of the maximum likelihood. principle. Selected Papers of Hirotugu Akaike, Springer. 10.1007/978-1-4612-1694-0_15
[35]
Scutari, M., and Denis, J.B. (2014). Bayesian Networks: With Examples in R, CRC Press. 10.1201/b17065
[36]
Constantinou, A. (2019). Evaluating structure learning algorithms with a balanced scoring function. arXiv.
[37]
Scanagatta "A survey on Bayesian network structure learning from data" Prog. Artif. Intell. (2019) 10.1007/s13748-019-00194-y
[38]
Pena, J.M. (2008). Learning gaussian graphical models of gene networks with false discovery rate control. European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, Springer. 10.1007/978-3-540-78757-0_15
[39]
Gasse "A hybrid algorithm for Bayesian network structure learning with application to multi-label learning" Expert Syst. Appl. (2014) 10.1016/j.eswa.2014.04.032
[40]
Constantinou "Learning Bayesian networks with the Saiyan algorithm" ACM Trans. Knowl. Discov. Data (TKDD) (2020) 10.1145/3385655
[41]
Constantinou "Learning Bayesian Networks that enable full propagation of evidence" IEEE Access (2020) 10.1109/access.2020.3006472
Metrics
3
Citations
41
References
Details
Published
Jun 15, 2021
Vol/Issue
23(6)
Pages
750
License
View
Funding
National Nature Science Foundation of China Award: 61573285
Cite This Article
Xiaohan Liu, Xiaoguang Gao, Zidong Wang, et al. (2021). Improved Local Search with Momentum for Bayesian Networks Structure Learning. Entropy, 23(6), 750. https://doi.org/10.3390/e23060750
Related

You May Also Like

Explainable AI: A Review of Machine Learning Interpretability Methods

Pantelis Linardatos, Vasilis Papastefanopoulos · 2020

2,260 citations

Quantum Thermodynamics: A Dynamical Viewpoint

Ronnie Kosloff · 2013

678 citations

Approximate Entropy and Sample Entropy: A Comprehensive Tutorial

Alfonso Delgado-Bonal, Alexander Marshak · 2019

587 citations

The Quantum Harmonic Otto Cycle

Ronnie Kosloff, Yair Rezek · 2017

331 citations