×

zbMATH — the first resource for mathematics

Learning Bayesian networks with local structure, mixed variables, and exact algorithms. (English) Zbl 07174633
Summary: Modern exact algorithms for structure learning in Bayesian networks first compute an exact local score of every candidate parent set, and then find a network structure by combinatorial optimization so as to maximize the global score. This approach assumes that each local score can be computed fast, which can be problematic when the scarcity of the data calls for structured local models or when there are both continuous and discrete variables, for these cases have lacked efficient-to-compute local scores. To address this challenge, we introduce a local score that is based on a class of classification and regression trees. We show that under modest restrictions on the possible branchings in the tree structure, it is feasible to find a structure that maximizes a Bayes score in a range of moderate-size problem instances. In particular, this enables global optimization of the Bayesian network structure, including the local structure. In addition, we introduce a related model class that extends ordinary conditional probability tables to continuous variables by employing an adaptive discretization approach. The two model classes are compared empirically by learning Bayesian networks from benchmark real-world and synthetic data sets. We discuss the relative strengths of the model classes in terms of their structure learning capability, predictive performance, and running time.
MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
Software:
bnlearn; UCI-ml
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Boutilier, C.; Friedman, N.; Goldszmidt, M.; Koller, D., Context-specific independence in Bayesian networks, (Proc. UAI (1996))
[2] Friedman, N.; Goldszmidt, M., Learning Bayesian networks with local structure, (Proc. UAI (1996))
[3] Chickering, D.; Heckerman, D.; Meek, C., A Bayesian approach to learning Bayesian networks with local structure, (Proc. UAI (1997))
[4] Koivisto, M.; Sood, K., Computational aspects of Bayesian partition models, (Proc. ICML (2005)), 433-440
[5] Chen, Y.; Wheeler, T.; Kochenderfer, M., Learning discrete Bayesian networks from continuous data, J. Artif. Intell. Res., 59, 103-132 (2017) · Zbl 1409.68229
[6] Koller, D.; Friedman, N., Probabilistic Graphical Models: Principles and Techniques (2009), MIT Press
[7] Romero, V.; Rumí, R.; Salmerón, A., Learning hybrid Bayesian networks using mixtures of truncated exponentials, Int. J. Approx. Reason., 42, 54-68 (2006) · Zbl 1096.68707
[8] Chickering, D. M., Learning Bayesian Networks Is NP-Complete, 121-130 (1996), Springer: Springer New York, NY
[9] Malone, B.; Kangas, K.; Järvisalo, M.; Koivisto, M.; Myllymäki, P., Empirical hardness of finding optimal Bayesian network structures: algorithm selection and runtime prediction, Mach. Learn., 107, 247-283 (2018) · Zbl 06855218
[10] Ott, S.; Miyano, S., Finding optimal gene networks using biological constraints, Genome Inform., 14, 124-133 (2003)
[11] Koivisto, M.; Sood, K., Exact Bayesian structure discovery in Bayesian networks, J. Mach. Learn. Res., 5, 549-573 (2004) · Zbl 1222.68234
[12] Singh, A. P.; Moore, A. W., Finding Optimal Bayesian Networks by Dynamic Programming (2005), Carnegie Mellon University, Technical Report CMU-CALD-05-106
[13] Silander, T.; Myllymäki, P., A simple approach for finding the globally optimal Bayesian network structure, (Proc. UAI (2006))
[14] Yuan, C.; Malone, B., Learning optimal Bayesian networks: a shortest path perspective, J. Artif. Intell. Res., 48, 23-65 (2013) · Zbl 1361.68182
[15] Bartlett, M.; Cussens, J., Integer linear programming for the Bayesian network structure learning problem, Artif. Intell., 244, 258-271 (2017) · Zbl 1404.68094
[16] van Beek, P.; Hoffmann, H., Machine learning of Bayesian networks using constraint programming, (Proc. CP. Proc. CP, Lecture Notes in Computer Science, vol. 9255 (2015), Springer), 429-445
[17] Malone, B.; Järvisalo, M.; Myllymäki, P., Impact of learning strategies on the quality of Bayesian networks: an empirical evaluation, (Proc. UAI (2015)), 562-571
[18] Breiman, L.; Friedman, J.; Olshen, R.; Stone, C., Classification and Regression Trees (1984), Wadsworth · Zbl 0541.62042
[19] Buntine, W., Learning classification trees, Stat. Comput., 2, 63-73 (1992)
[20] Denison, D.; Mallick, B.; Smith, A., A Bayesian CART algorithm, Biometrika, 85, 363-377 (1998) · Zbl 1048.62502
[21] Chipman, H.; George, E.; McCulloch, R., Bayesian CART model search, J. Am. Stat. Assoc., 93, 935-948 (1998)
[22] Donoho, D., CART and best-ortho-basis: a connection, Ann. Stat., 25, 1870-1911 (1997) · Zbl 0942.62044
[23] Scott, C.; Nowak, R., Minimax optimal classification with dyadic decision trees, IEEE Trans. Inf. Theory, 52, 1335-1353 (2006) · Zbl 1318.62216
[24] Blanchard, G.; Schäfer, C.; Rozenholc, Y.; Müller, K., Optimal dyadic decision trees, Mach. Learn., 66, 209-241 (2007)
[25] van der Pas, S.; Rockova, V., Bayesian dyadic trees and histograms for regression, (Advances in Neural Information Processing Systems (NIPS), vol. 30 (2017)), 2086-2096
[26] Talvitie, T.; Eggeling, R.; Koivisto, M., Finding optimal Bayesian networks with local structure, (Proc. PGM, vol. 72 (2018), PMLR), 451-462
[27] Angelopoulos, N.; Cussens, J., Bayesian learning of Bayesian networks with informative priors, Ann. Math. Artif. Intell., 54, 53-98 (2008) · Zbl 1178.68392
[28] Murphy, K., Conjugate Bayesian Analysis of the Gaussian Distribution (2007), University of British: University of British Columbia, Technical Report
[29] Friedman, N.; Koller, D., Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks, Mach. Learn., 50, 95-125 (2003) · Zbl 1033.68104
[30] Scutari, M., Learning Bayesian networks with the bnlearn R package, J. Stat. Softw., 35, 1-22 (2010)
[31] Lichman, M., UCI Machine Learning Repository (2013), University of California, School of Information and Computer Science: University of California, School of Information and Computer Science Irvine, CA
[32] Tsamardinos, I.; Brown, L.; Aliferis, C., The max-min hill-climbing Bayesian network structure learning algorithm, Mach. Learn., 65, 31-78 (2006)
[33] Eggeling, R.; Viinikka, J.; Vuoksenmaa, A.; Koivisto, M., On structure priors for learning Bayesian networks, (Proc. AISTATS, vol. 89 (2019), PMLR), 1687-1695
[34] Viinikka, J.; Eggeling, R.; Koivisto, M., Intersection-validation: a method for evaluating structure learning without ground truth, (Proc. AISTATS, vol. 84 (2018), PMLR), 1570-1578
[35] Wilcoxon, F., Individual comparisons by ranking methods, Biom. Bull., 1, 80-83 (1945)
[36] Eggeling, R.; Koivisto, M., Pruning Rules for Learning Parsimonious Context Trees, Proc. UAI, vol. 32, 152-161 (2016), AUAI Press
[37] Karra, K.; Mili, L., Hybrid copula Bayesian networks, (Proc. PGM, vol. 52 (2016), PMLR), 240-251
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.