×

An optimization-based approach for the design of Bayesian networks. (English) Zbl 1187.90086

Summary: Bayesian networks model conditional dependencies among the domain variables, and provide a way to deduce their interrelationships as well as a method for the classification of new instances. One of the most challenging problems in using Bayesian networks, in the absence of a domain expert who can dictate the model, is inducing the structure of the network from a large, multivariate data set. We propose a new methodology for the design of the structure of a Bayesian network based on concepts of graph theory and nonlinear integer optimization techniques.

MSC:

90B15 Stochastic network models in operations research
62H05 Characterization and structure theory for multivariate probability distributions; copulas
62K05 Optimal statistical designs

Software:

UCI-ml
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramson, B., The design of belief network-based systems for price forecasting, Computers and Electrical Engineering, 20, 163-180 (1994)
[2] Andrassen, S.; Jensen, F.; Olensen, K., Medical expert systems based on probabilistic causal networks, International Journal of Medical Computing, 28, 1-30 (1991)
[3] I.A. Beinlich, H.J. Suermondt, R.M. Chavez, G.F. Cooper, The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks, in: Proceedings of the Second European Conference on Artificial Intelligence in Medicine, 1989, pp. 247-256; I.A. Beinlich, H.J. Suermondt, R.M. Chavez, G.F. Cooper, The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks, in: Proceedings of the Second European Conference on Artificial Intelligence in Medicine, 1989, pp. 247-256
[4] J.R. Castelo, The discrete acyclic digraph Markov model in data mining, Ph.D. Thesis, University of Utrecht, 2002; J.R. Castelo, The discrete acyclic digraph Markov model in data mining, Ph.D. Thesis, University of Utrecht, 2002
[5] Chen, C. L.; Talukdar, S., Causal nets for diagnosis, (Proceedings of the Expert Systems Application to Power Systems IV (1993), CRL Publishing), 379-386
[6] J. Cheng, D.A. Bell, W. Liu, An algorithm for Bayesian belief network construction from data, in: Proceedings of the 6th International Workshop on Artificial Intelligence, 1997; J. Cheng, D.A. Bell, W. Liu, An algorithm for Bayesian belief network construction from data, in: Proceedings of the 6th International Workshop on Artificial Intelligence, 1997
[7] Cheng, J.; Greiner, R.; Kelly, J.; Bell, D.; Liu, W., Learning Bayesian networks from data: An efficient approach based on information theory, Artificial Intelligence, 137, 43-90 (2000)
[8] Chickering, D. M., A transformational characterization of equivalent Bayesian network structures, Uncertainty in Artificial Intelligence, 11, 87-98 (1995)
[9] Chickering, D. M., Learning equivalence classes of Bayesian networks structures, Journal of Machine Learning Research, 2, 445-498 (2002) · Zbl 1007.68179
[10] D.M. Chickering, D. Geiger, D. Heckerman, Learning Bayesian networks is NP-Hard, Technical Report MSR-TR-94-17, Microsoft Research, 1994; D.M. Chickering, D. Geiger, D. Heckerman, Learning Bayesian networks is NP-Hard, Technical Report MSR-TR-94-17, Microsoft Research, 1994 · Zbl 0831.68096
[11] Chickering, D. M.; Meek, C.; Heckerman, D., Large-sample learning of Bayesian networks is NP-hard, (Kjaerulff, U.; Meek., C., Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (2003), Morgan Kaufmann: Morgan Kaufmann Acapulco, Mexico), 124-133
[12] Chow, C.; Liu, C., Approximating discrete probability distributions with dependence trees, IEEE Transactions on Information Theory, 14, 462-467 (1968) · Zbl 0165.22305
[13] C. Conati, K. VanLehn, Probabilistic plan recognition for cognitive apprenticeship, in: Proceedings of the 18th Annual Conference of the Cognitive Science Society, 1996; C. Conati, K. VanLehn, Probabilistic plan recognition for cognitive apprenticeship, in: Proceedings of the 18th Annual Conference of the Cognitive Science Society, 1996
[14] Conover, W. J., Practical Nonparametric Statistics (1999), John WIley and Sons, Inc. · Zbl 0151.23503
[15] 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
[16] D. Dash, M.J. Druzdzel, A hybrid anytime algorithm for the construction of causal models from sparse data, in: Proceedings of the Proceedings of the Fifteenth Annual Conference on Uncertainty in Artificial Intelligence, 1999, pp. 142-149; D. Dash, M.J. Druzdzel, A hybrid anytime algorithm for the construction of causal models from sparse data, in: Proceedings of the Proceedings of the Fifteenth Annual Conference on Uncertainty in Artificial Intelligence, 1999, pp. 142-149
[17] J. Dougherty, R. Kohavi, M. Sahami, Supervised and unsupervised discretization of continuous features, in: Proceedings of the Proceedings of the Twelfth International Conference on Machine Learning, 1995, pp. 194-202; J. Dougherty, R. Kohavi, M. Sahami, Supervised and unsupervised discretization of continuous features, in: Proceedings of the Proceedings of the Twelfth International Conference on Machine Learning, 1995, pp. 194-202
[18] Friedman, N.; Linial, M.; Nachman, I.; Pe’er, D., Using Bayesian networks to analyze expression data, Journal of Computational Biology, 7, 601-620 (2000)
[19] D. Geiger, A. Paz, J. Pearl, Learning causal trees from dependence information, Technical Report R-149, Computer Science Department, University of California, 1990; D. Geiger, A. Paz, J. Pearl, Learning causal trees from dependence information, Technical Report R-149, Computer Science Department, University of California, 1990
[20] D. Grossmann, P. Domingos, Learning Bayesian network classifiers by maximizing conditional likelihood, in: Proceedings of the Twenty First International Conference on Machine Learning, Banff, Canada, 2004; D. Grossmann, P. Domingos, Learning Bayesian network classifiers by maximizing conditional likelihood, in: Proceedings of the Twenty First International Conference on Machine Learning, Banff, Canada, 2004
[21] Heckerman, D.; Geiger, D.; Chickering, D., Learning Bayesian networks: The combination of knowledge and statistical data, Machine Learning, 20, 197-243 (1995) · Zbl 0831.68096
[22] Henrion, M., Propagating uncertainty in Bayesian networks by probabilistic logic sampling, Uncertainty in Artificial Intelligence, 2, 149-163 (1988)
[23] Herskovits, E.; Cooper, G., Kutató: An entropy-driven system for construction of probabilistic expert systems from databases, Uncertainty in Artificial Intelligence, 6, 117-125 (1991)
[24] Kennett, R.; Korb, K.; Nicholson, A., Seabreeze prediction using Bayesian networks: A case of study, (Proceedings of the Proceedings of the 5th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (2001), Springer-Verlang: Springer-Verlang New York) · Zbl 0978.68688
[25] Larrañaga, P.; Poza, M. Y.; Y.; Murga, R. H.; Kuijpers, C., Structure learning of Bayesian networks by Genetic algorithms: A performance analysis of control parameters, IEEE Transactions on Pattern Analysis and Machine Intelligence, 18, 912-926 (1996)
[26] Lauritzen, S.; Spiegelhalter, D. J., Local computations with probabilities on graphical structures and their application on expert systems, Journal of the Royal Statistical Society, B 50, 157-224 (1988) · Zbl 0684.68106
[27] Mangasarian, O. L.; Wolberg, W. H., Cancer diagnosis via linear programming, SIAM News, 23, 1-18 (1990) · Zbl 0726.90096
[28] Mani, S.; McDermott, S.; Valtorta, M., Mentor: A Bayesian model for prediction of mental retardation in newborns, Research in Developmental Disabilities, 18, 303-318 (1997)
[29] D. Margaritis, C. Faloutsos, S. Thrun, NetCube: A scalable tool for fast data mining and compression, in: Proceedings of the 27th Conference on Very Large Databases, VLDB, Rome, Italy, 2001; D. Margaritis, C. Faloutsos, S. Thrun, NetCube: A scalable tool for fast data mining and compression, in: Proceedings of the 27th Conference on Very Large Databases, VLDB, Rome, Italy, 2001
[30] C. Meek, Graphical models: Selecting causal and statistical models, Ph.D. Thesis, Carnegie Mellon University, 1997; C. Meek, Graphical models: Selecting causal and statistical models, Ph.D. Thesis, Carnegie Mellon University, 1997
[31] A.W. Moore, W.-K. Wong, Optimal reinsertion: A new search operator for accelerated and more accurate Bayesian network structure learning, in: Proceedings of the Twentieth International Conference in Machine Learning, ICML-2003, Washington, DC, 2003; A.W. Moore, W.-K. Wong, Optimal reinsertion: A new search operator for accelerated and more accurate Bayesian network structure learning, in: Proceedings of the Twentieth International Conference in Machine Learning, ICML-2003, Washington, DC, 2003
[32] D.J. Newman, S. Hettich, C.L. Blake, C.J. Merz, UCI Repository of machine learning databases, Irvine, CA, Department of Information and Computer Science, University of California, 1998. http://www.ics.uci.edu/ mlearn/MLRepository.html; D.J. Newman, S. Hettich, C.L. Blake, C.J. Merz, UCI Repository of machine learning databases, Irvine, CA, Department of Information and Computer Science, University of California, 1998. http://www.ics.uci.edu/ mlearn/MLRepository.html
[33] J. Pearl, Bayesian networks, causal inference and knowledge discovery, Technical Report R-281, UCLA Cognitive Systems Laboratory, 2001; J. Pearl, Bayesian networks, causal inference and knowledge discovery, Technical Report R-281, UCLA Cognitive Systems Laboratory, 2001
[34] Robinson, R. W., Counting unlabeled acyclic digraphs, (Combinatorial Mathematics. Combinatorial Mathematics, Lectures Notes in Mathematics, vol. 622 (1997), Springer-Verlang: Springer-Verlang New-York), 28-43 · Zbl 0376.05031
[35] J. Royalty, R. Holland, J. Goldsmith, A. Dekhtyar, POET: The online preference elicitation tool, Technical Report WS-02-13, AAAI, 2002; J. Royalty, R. Holland, J. Goldsmith, A. Dekhtyar, POET: The online preference elicitation tool, Technical Report WS-02-13, AAAI, 2002
[36] Sarkar, S.; Murthy, I., Constructing efficient belief network structures with expert provided information, IEEE Transactions on Knowledge and Data Engineering, 89, 134-143 (1996)
[37] Sarkar, S.; Sriram, S., Bayesian models for early warning of bank failures, Management Science, 47, 11, 1457-1475 (2001) · Zbl 1232.91722
[38] Schwartz, S. M.; Baron, J.; Clarke, J. R., A causal Bayesian model for the diagnosis of appendicitis, Uncertainty in Artificial Intelligence, 2, 423-434 (1988) · Zbl 0709.68553
[39] A.P. Singh, A.W. Moore, Findign optimal Bayesian networks by dynamic programming, CMU-CALD-05-106, Pittsburgh, PA, School of computer science, Carnegie Mellon University, 2005. http://www.autonlab.org/autonweb/14757.html; A.P. Singh, A.W. Moore, Findign optimal Bayesian networks by dynamic programming, CMU-CALD-05-106, Pittsburgh, PA, School of computer science, Carnegie Mellon University, 2005. http://www.autonlab.org/autonweb/14757.html
[40] Spangler, W. E.; Mordechai, G.-O.; May, J. H., Using data mining to profile TV viewers, Communications of the ACM, 46, 12, 66-72 (2003)
[41] J.G. Torres-Toledano, L. Sucar, Bayesian networks for reliability analysis of complex systems, Progress in Artificial Intelligence, IBERAMIA, 1998; J.G. Torres-Toledano, L. Sucar, Bayesian networks for reliability analysis of complex systems, Progress in Artificial Intelligence, IBERAMIA, 1998
[42] Valadares, J.; Ramalho, G.; Ladeira, M., Modeling complex management games with Bayesian networks: The FutSim case of study, (Proceedings of the Agents in Computer Games (2002), Edmonton: Edmonton Canada)
[43] W.-K. Wong, A.W. Moore, G. Cooper, M. Wagner, Bayesian network anomaly pattern detection for disease outbreaks, in: Proceedings of the Twentieth International Conference on Machine Learning, ICML-2003. Washington, DC, 2003; W.-K. Wong, A.W. Moore, G. Cooper, M. Wagner, Bayesian network anomaly pattern detection for disease outbreaks, in: Proceedings of the Twentieth International Conference on Machine Learning, ICML-2003. Washington, DC, 2003
[44] Yigun, G.; Peiris, D.; Crawford, J.; NcNicol, J.; Marshall, B.; Jefferies, R., An Application of Belief Networks to Future Crop Production (1994), IEEE Comput. Soc. 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.