Improved Local Search with Momentum for Bayesian Networks Structure Learning

Xiaohan Liu; Xiaoguang Gao; Zidong Wang; Xinxin Ru

doi:10.3390/e23060750

journal article Open Access Jun 15, 2021

Improved Local Search with Momentum for Bayesian Networks Structure Learning

Xiaohan Liu

Xiaoguang Gao

Zidong Wang

Xinxin Ru

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.

[18]

Approximate Learning of High Dimensional Bayesian Network Structures via Pruning of Candidate Parent Sets

Zhigao Guo, Anthony C. Constantinou

Entropy 10.3390/e22101142

[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

Authors

X

Xiaohan Liu

School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710129, China

X

Xiaoguang Gao

School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710129, China

Z

Zidong Wang

School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710129, China

X

Xinxin Ru

School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710129, China

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

Improved Local Search with Momentum for Bayesian Networks Structure Learning

You May Also Like