×

zbMATH — the first resource for mathematics

Learning Bayesian networks from data: An information-theory based approach. (English) Zbl 0995.68114
This paper provides algorithms that use an information-theoretic analysis to learn Bayesian network structures from data. Based on our three-phase learning framework, we develop efficient algorithms that can effectively learn Bayesian networks, requiring only polynomial numbers of conditional independence tests in typical cases. We provide precise conditions that specify when these algorithms are guaranteed to be correct as well as empirical evidence (from real world applications and simulation tests) that demonstrates that these systems work efficiently and reliably in practice.

MSC:
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
Software:
BENEDICT; BUGS; CoCo; MIM; TETRAD
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Acid, S.; Campos, L.M., An algorithm for finding minimum d-separating sets in belief networks, ()
[2] Acid, S.; Campos, L.M., BENEDICT: an algorithm for learning probabilistic belief networks, () · Zbl 0983.68197
[3] Agresti, A., Categorical data analysis, (1990), Wiley New York · Zbl 0716.62001
[4] Badsberg, J., Model search in contingency tables in coco, (), 251-256
[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, (), 247-256
[6] Buntine, W., Operations for learning with graphical models, J. artificial intelligence res., 2, 159-225, (1994)
[7] Buntine, W., A guide to the literature on learning probabilistic networks from data, IEEE trans. knowledge data engrg., 8, 2, 195-210, (1996)
[8] Cheng, J.; Bell, D.A.; Liu, W., An algorithm for Bayesian belief network construction from data, (), 83-90
[9] Cheng, J.; Bell, D.A.; Liu, W., Learning belief networks from data: an information theory based approach, ()
[10] Cheng, J., Learning Bayesian networks from data: an information theory based approach, doctoral dissertation, (1998), Faculty of Informatics, University of Ulster UK
[11] Cheng, J.; Greiner, R., Comparing Bayesian network classifiers, ()
[12] Cheng, J.; Greiner, R., Learning Bayesian belief network classifiers: algorithms and system, () · Zbl 0984.68191
[13] Chickering, D.M.; Geiger, D.; Heckerman, D., Learning Bayesian networks is NP-hard, technical report MSR-TR-94-17, (1994), Microsoft Research, Microsoft Corporation
[14] Chickering, D.M., Learning equivalence classes of Bayesian network structures, () · Zbl 1007.68179
[15] Chow, C.K.; Liu, C.N., Approximating discrete probability distributions with dependence trees, IEEE trans. inform. theory, 14, 462-467, (1968) · Zbl 0165.22305
[16] Chrisman, L., A roadmap to research on Bayesian networks and other decomposable probabilistic models, technical report, (1996), School of Computer Science CMU, Pittsburgh, PA
[17] Cooper, G.F.; Herskovits, E., A Bayesian method for the induction of probabilistic networks from data, Machine learning, 9, 309-347, (1992) · Zbl 0766.68109
[18] Cowell, R.G., When learning Bayesian networks from data, using conditional independence tests is equivalent to a local scoring metric, ()
[19] C. Darken, Personal communication
[20] Dash, D.; Druzdzel, M., A hybrid anytime algorithm for the construction of causal models from sparse data, ()
[21] Edwards, D., Introduction to graphical modelling, (1995), Springer New York · Zbl 0856.62004
[22] Friedman, N., The Bayesian structural EM algorithm, ()
[23] Friedman, N.; Geiger, D.; Goldszmidt, M., Bayesian network classifiers, Machine learning, 29, 131-161, (1997) · Zbl 0892.68077
[24] Friedman, N.; Goldszmidt, M., Learning Bayesian networks with local structure, () · Zbl 0910.68176
[25] Fung, R.M.; Crawford, S.L., Constructor: A system for the induction of probabilistic models, ()
[26] Greiner, R.; Grove, A.; Schuurmans, D., Learning Bayesian nets that perform well, (), 198-207
[27] Greiner, R.; Darken, C.; Santoso, N.I., Efficient reasoning, Comput. surveys, 33, 1, 1-30, (2001)
[28] Heckerman, D., A tutorial on learning Bayesian networks, technical report MSR-TR-95-06, (1995), Microsoft Research
[29] Heckerman, D.; Geiger, D.; Chickering, D.M., Learning Bayesian networks: the combination of knowledge and statistical data, Machine learning, 20, 3, 197-243, (1995) · Zbl 0831.68096
[30] Henrion, M., Propagating uncertainty in Bayesian networks by probabilistic logic sampling, (), 149-163
[31] Herskovits, E.; Cooper, G., Kutato: an entropy-driven system for construction of probabilistic expert systems from databases, ()
[32] Hojsgaard, S.; Skjoth, F.; Thiesson, B., User’s guide to BIOFROST, technical report, (1994), Department of Mathematics and Computer Science Aalborg, Denmark
[33] Krause, P., Learning probabilistic networks, technical report, (1996), Philips Research Laboratories UK
[34] Kullback, S.; Leibler, R., On information and sufficiency, Ann. math. statist., 22, 76-86, (1951) · Zbl 0042.38403
[35] Lam, W.; Bacchus, F., Learning Bayesian belief networks: an approach based on the MDL principle, Comput. intelligence, 10, 4, 269-293, (1994)
[36] Madigan, D.; Raftery, A.E., Model selection and accounting for model uncertainty in graphical models using Occam’s window, J. amer. statist. assoc., 89, 1535-1546, (1994) · Zbl 0814.62030
[37] Madigan, D.; Raftery, A.E.; York, J.C.; Bradshaw, J.M.; Almond, G., Strategies for graphical model selection, () · Zbl 0828.62002
[38] Meek, C., Strong completeness and faithfulness in Bayesian networks, ()
[39] Page, D.; Hatzis, C., ACM SIGKDD cup 2001, 2001
[40] Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann San Mateo, CA
[41] Ramoni, M.; Sebastiani, P., Robust learing with missing data, technical report, KMI-TR-28, (1996), The Open University UK
[42] Ramoni, M.; Sebastiani, P., Discovering Bayesian networks in incomplete databases, technical report KMI-TR-46, (1997), Knowledge Media Institute, The Open University UK
[43] Rebane, G.; Pearl, J., The recovery of causal poly-tree from statistical data, ()
[44] Scheines, R.; Spirtes, P.; Glymour, C.; Meek, C., TETRAD II: tools for discovery, (1994), Lawrence Erlbaum Associates Hillsdale, NJ
[45] Singh, M., Learning Bayesian networks from incomplete data, Proc. AAAI-97, providence, RI, (1997)
[46] Singh, M.; Valtorta, M., Construction of Bayesian network structures from data: A brief survey and an efficient algorithm, Internat. J. approx. reason., 12, 111-131, (1995) · Zbl 0814.68115
[47] Spirtes, P.; Glymour, C.; Scheines, R., Causality from probability, Proceedings of advanced computing for the social sciences, williamsburgh, VA, (1990)
[48] Spirtes, P.; Glymour, C.; Scheines, R., An algorithm for fast recovery of sparse causal graphs, Social science computer review, 9, 62-72, (1991)
[49] Spirtes, P.; Glymour, C.; Scheines, R., Causation, prediction, and search, Lecture notes in statistics, (1993), Springer Berlin
[50] Spirtes, P.; Meek, C., Learning Bayesian networks with discrete variables from data, ()
[51] Spirtes, P.; Richardson, T.; Meek, C., Heuristic greedy search algorithms for latent variable models, (), 481-488
[52] Srinivas, S.; Russell, S.; Agogino, A., Automated construction of sparse Bayesian networks from unstructured probabilistic models and domain information, () · Zbl 0721.68078
[53] Suzuki, J., Learning Bayesian belief networks based on the MDL principle: an efficient algorithm using the branch and bound technique, ()
[54] Thomas, A.; Spiegelhalter, D.J.; Gilks, W.R., BUGS: A program to perform Bayesian inference using Gibbs sampling, (), 837-842
[55] Verma, T.S.; Pearl, J., Equivalence and synthesis of causal models, ()
[56] Verma, T.S.; Pearl, J., An algorithm for deciding if a set of observed independencies has a causal explanation, ()
[57] Wermuth, N.; Lauritzen, S., Graphical and recursive models for contingency tables, Biometrika, 72, 537-552, (1983) · Zbl 0541.62038
[58] Wong, S.K.M.; Xiang, Y., Construction of a Markov network from data for probabilistic inference, (), 562-569
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.