Structural learning for Bayesian networks by testing complete separators in prime blocks. (English) Zbl 1271.62048
Summary: We consider how to recover the structure of a Bayesian network from a supporting graph. We present a more accurate characterization of supporting edges, based on which a complete subset (i.e., a separator) contained in the neighbor set of one vertex of the putative supporting edge in some prime block of the supporting graph can be chosen. This results in a set of separators needing to be searched generally smaller than the sets required by some existing algorithms. A so-called structure-finder algorithm is proposed for structural learning. The complexity analysis of the proposed algorithm is discussed and compared with those for several existing algorithms. We also demonstrate how to construct the supporting graph locally from, separately, the Markov blanket, domain knowledge and \(d\)-separation trees. Simulation studies are used to evaluate the performances of various strategies for structural learning. We also analyze a gene expression data set by using the structure-finder algorithm.
MSC:
| 62F15 | Bayesian inference |
| 68T35 | Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence |
| 65C60 | Computational problems in statistics (MSC2010) |
Keywords:
complete separator; conditional independence; supporting edge; prime block; structural learningReferences:
| [1] | Abramson, B.; Brown, J.; Murphy, A.; Winkler, R. L., Hailfinder: a Bayesian system for forecasting severe weather, International Journal of Forecasting, 12, 57-71 (1996) |
| [2] | Aliferis, C.F., Tsamardinos, I., Statnikov, A., 2003. Causal explorer: a probabilistic network learning toolkit for discovery. In: The 2003 International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences.; Aliferis, C.F., Tsamardinos, I., Statnikov, A., 2003. Causal explorer: a probabilistic network learning toolkit for discovery. In: The 2003 International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences. |
| [3] | Anderson, T. W., An Introduction to Multivariate Statistical Analysis (1984), Wiley · Zbl 0651.62041 |
| [4] | Andersson, S. A.; Madigan, D.; Perlman, M. D., A characterization of Markov equivalence classes for acyclic digraphs, Annals of Statistics, 24, 505-541 (1997) · Zbl 0876.60095 |
| [5] | Beinlich, I. A.; Suermondt, H. J.; Chavez, R. M.; Cooper, G. F., The ALARM monitoring system: a case study with two probabilistic inference techniques for belief networks, (Proceedings of the Second European Conference on Artificial Intelligence in Medicine (1989), Springer: Springer Berlin), 247-256 |
| [6] | Binder, J.; Koller, D.; Russell, S. J.; Kanazawa, K., Adaptive probabilistic networks with hidden variables, Machine Learning, 29, 213-244 (1997) · Zbl 0892.68079 |
| [7] | Cheng, J.; Greiner, R.; Kelly, J.; Bell, D.; Liu, W., Learning Bayesian networks from data: an information-theory based approach, Artificial Intelligence, 137, 43-90 (2002) · Zbl 0995.68114 |
| [8] | Chickering, D. M., Learning equivalence classes of Bayesian network structures, Journal of Machine Learning Research, 2, 445-498 (2002) · Zbl 1007.68179 |
| [9] | Cowell, R. G.; David, A. P.; Lauritzen, S. L.; Spiegelhalter, D. J., Probabilistic Networks and Expert Systems (1999), Springer: Springer New York · Zbl 0937.68121 |
| [10] | Geng, Z.; Wang, C.; Zhao, Q., Decomposition of search for \(v\)-structures in, DAGs. Journal of Multivariate Analysis, 96, 282-294 (2005) · Zbl 1137.62420 |
| [11] | Heckerman, D.; Geiger, D.; Chickering, D. M., Learning Bayesian networks: the combination of knowledge and statistical data, Machine Learning, 20, 197-243 (1995) · Zbl 0831.68096 |
| [12] | Jensen, F. V.; Nielsen, T. D., Bayesian Networks and Decision Graphs (2007), Springer-Verlag: Springer-Verlag Berlin · Zbl 1277.62007 |
| [13] | Lauritzen, S. L., Graphical Models (1996), Clarendon Press: Clarendon Press Oxford · Zbl 0907.62001 |
| [14] | Lauritzen, S. L.; Spiegelhalter, D. J., Local computations with probabilities on graphical structures and their application to expert systems (with discussion), Journal of the Royal Statistical Society, Series B, 50, 157-224 (1988) · Zbl 0684.68106 |
| [15] | Leimer, H. G., Optimal decomposition by cliques separators, Discrete Mathematics, 113, 99-123 (1993) · Zbl 0793.05128 |
| [16] | Liu, B. H.; Guo, J. H.; Jing, B. Y., A note on minimal \(d\)-separation trees for structure learning, Artificial Intelligence, 174, 442-448 (2010) · Zbl 1211.68290 |
| [17] | Ma, Z.; Xie, X.; Geng, Z., Structural learning of chain graphs via decomposition, Journal of Machine Learning Research, 9, 2847-2880 (2008) · Zbl 1225.68199 |
| [18] | Meek, C., Causal inference and causal explanation with background knowledge, (Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (1995), Morgan Kaufmann: Morgan Kaufmann San Francisco), 403-410 |
| [19] | Meinshausen, N.; Bühlmann, P., High-dimensional graphs and variable selection with the Lasso, Annals of Statistics, 34, 1436-1462 (2006) · Zbl 1113.62082 |
| [20] | Murphy, K., The Bayes net toolbox for Matlab, Computing Science and Statistics, 33, 331-350 (2001) |
| [21] | Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufman Publishers: Morgan Kaufman Publishers San Mateo, CA |
| [22] | Pearl, J., Causality (2000), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0959.68116 |
| [23] | Peña, J. M.; Nilsson, R.; Björkegren, J.; Tegnér, J., Towards scalable and data efficient learning of Markov boundaries, International Journal of Approximate Reasoning, 45, 211-232 (2007) · Zbl 1122.68136 |
| [24] | Spirtes, P.; Glymour, C., An algorithm for fast recovery of sparse causal graphs, Social Science Computer Review, 9, 62-72 (1991) |
| [25] | Spirtes, P.; Glymour, C.; Scheines, R., Causation, Prediction and Search (2000), MIT Press: MIT Press Cambridge · Zbl 0806.62001 |
| [26] | Tsamardinos, I., Aliferis, C.F., Statnikov, A., 2003. Algorithms for large scale Markov blanket discovery. In: Proceedings of the Sixteenth International Florida Artificial Intelligence Research Society Conference, pp. 376-380.; Tsamardinos, I., Aliferis, C.F., Statnikov, A., 2003. Algorithms for large scale Markov blanket discovery. In: Proceedings of the Sixteenth International Florida Artificial Intelligence Research Society Conference, pp. 376-380. |
| [27] | Tsamardinos, I.; Brown, L.; Aliferis, C., The max-min hill-climbing Bayesian network structure learning algorithm, Machine Learning, 65, 31-78 (2006) · Zbl 1470.68192 |
| [28] | Verma, T., Pearl, J., 1990. Equivalence and synthesis of causal models. In: Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, Cambridge, MA, pp. 220-227; Also in P. Bonissone, M. Henrion, L.N. Kanal and J.F. Lemmer (Eds.), Uncertainty in Artificial Intelligence 6, Elsevier Science Publishers, pp. 255-268, 1991.; Verma, T., Pearl, J., 1990. Equivalence and synthesis of causal models. In: Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, Cambridge, MA, pp. 220-227; Also in P. Bonissone, M. Henrion, L.N. Kanal and J.F. Lemmer (Eds.), Uncertainty in Artificial Intelligence 6, Elsevier Science Publishers, pp. 255-268, 1991. |
| [29] | Verma, T.; Pearl, J., An algorithm for deciding if a set of observed independencies has a causal explanation, (Proceedings of the Eighth Conference on Uncertainty in Artificial Intelligence (1992), Morgan Kaufmann: Morgan Kaufmann Stanford, CA), 323-330 |
| [30] | Whittaker, J., Graphical Models in Applied Multivariate Statistics (1990), John Wiley and Sons: John Wiley and Sons Chichester · Zbl 0732.62056 |
| [31] | Wille, A.; Zimmermann, P.; Vranova, E.; Fürholz, A.; Laule, O.; Bleuler, S.; Hennig, L.; Prelic, A.; von Rohr, P.; Thiele, L.; Zitzler, E.; Gruissem, W.; Bühlmann, P., Sparse graphical Gaussian modeling of the isoprenoid gene network in Arabidopsis thaliana, Genome Biology, 5, 11 (2004), R92, 1-13 |
| [32] | Xie, X.; Geng, Z., A recursive method for structural learning of directed acyclic graphs, Journal of Machine Learning Research, 9, 459-483 (2008) · Zbl 1225.68222 |
| [33] | Xie, X.; Geng, Z.; Zhao, Q., Decomposition of structural learning about directed acyclic graphs, Artificial Intelligence, 170, 422-439 (2006) · Zbl 1131.68510 |
| [34] | Xu, P.F., Guo, J.H., 2011. A new algorithm for decomposition of graphical models. Acta Mathematicae Applicatae Sinica, English Series (in press).; Xu, P.F., Guo, J.H., 2011. A new algorithm for decomposition of graphical models. Acta Mathematicae Applicatae Sinica, English Series (in press). |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
