zbMATH — the first resource for mathematics

A conditional independence algorithm for learning undirected graphical models. (English) Zbl 1186.68356
Summary: When it comes to learning graphical models from data, approaches based on conditional independence tests are among the most popular methods. Since Bayesian networks dominate research in this field, these methods usually refer to directed graphs, and thus have to determine not only the set of edges, but also their direction. At least for a certain kind of possibilistic graphical models, however, undirected graphs are a much more natural basis. Hence, in this area, algorithms for learning undirected graphs are desirable, especially, since first learning a directed graph and then transforming it into an undirected one wastes resources and computation time. In this paper, I present a general algorithm for learning undirected graphical models, which is strongly inspired by the well-known Cheng-Bell-Liu algorithm for learning Bayesian networks from data. Its main advantage is that it needs fewer conditional independence tests, while it achieves results of comparable quality.

68T05 Learning and adaptive systems in artificial intelligence
68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
Full Text: DOI
[1] Agosta, J.M., Intel technol. J., 8, 4, 361-372, (2004), Intel Corporation, Santa Clara, CA, USA
[2] Borgelt, C.; Kruse, R., Evaluation measures for learning probabilistic and possibilistic networks, (), 1034-1038
[3] Borgelt, C.; Kruse, R., Efficient maximum projection of database-induced multivariate possibility distributions, (), (CD-ROM)
[4] Borgelt, C.; Kruse, R., Graphical models — methods for data analysis and mining, (2002), J. Wiley & Sons Chichester, United Kingdom · Zbl 1017.62002
[5] Castillo, G., Adaptive learning algorithms for Bayesian network classifiers, AI commun., 21, 1, 87-88, (2008), IOS Press, Amsterdam, Netherlands
[6] Charitos, T.; van der Gaag, L.C.; Visscher, S.; Schurink, K.A.M.; Lucas, P.J.F., A dynamic Bayesian network for diagnosing ventilator-associated pneumonia in ICU patients, Expert systems appl., 36, 2.1, 1249-1258, (2007), Elsevier, Amsterdam, Netherlands
[7] Chickering, D.M., Optimal structure identification with greedy search, J. Mach. learn. res., 3, 507-554, (2002), MIT Press, Cambridge, MA, USA · Zbl 1084.68519
[8] Cho, S.-J.; Kim, J.H., Bayesian network modeling of strokes and their relationship for on-line handwriting recognition, Pattern recogn., 37, 2, 253-264, (2003), Elsevier Science, Amsterdam, Netherlands · Zbl 1059.68103
[9] Cooper, G.F.; Herskovits, E., A Bayesian method for the induction of probabilistic networks from data, Mach. learn., 9, 309-347, (1992), Kluwer, Dordrecht, Netherlands · Zbl 0766.68109
[10] Cheng, J.; Bell, D.A.; Liu, W., Learning belief networks from data: an information theory based approach, (), 325-331
[11] Cheng, J.; Greiner, R.; Kelly, J.; Bell, D.A.; Liu, W., Learning Bayesian networks from data: an information theory based approach, Artificial intelligence, 137, 1-2, 43-90, (2002), Elsevier, Amsterdam, Netherlands · Zbl 0995.68114
[12] Buntine, W., Operations for learning with graphical models, J. artificial intelligence res., 2, 159-225, (1994), Morgan Kaufman, San Mateo, CA, USA
[13] de Campos, L.M.; Huete, J.F.; Moral, S., Independence in uncertainty theories and its application to learning belief networks, (), 391-434 · Zbl 0970.68133
[14] Castillo, E.; Gutierrez, J.M.; Hadi, A.S., Expert systems and probabilistic network models, (1997), Springer New York, NY, USA
[15] Chow, C.K.; Liu, C.N., Approximating discrete probability distributions with dependence trees, IEEE trans. inform. theory, 14, 3, 462-467, (1968), IEEE Press, Piscataway, NJ, USA · Zbl 0165.22305
[16] Frankel, J.; Webster, M.; King, S., Articulatory feature recognition using dynamic Bayesian networks, Comput. speech and lang., 21, 4, 620-640, (2007), Elsevier Science, Amsterdam, Netherlands
[17] Gamez, J.A.; Moral, S.; Salmeron, A., Advances in Bayesian networks, (2004), Springer Berlin, Germany
[18] J. Gebhardt, Learning from data: Possibilistic graphical models, Habilitation Thesis, University of Braunschweig, Germany, 1997 · Zbl 0970.68132
[19] Learning Bayesian network classifiers by maximizing conditional likelihood, (), 46
[20] Heckerman, D.; Geiger, D.; Chickering, D.M., Learning Bayesian networks: the combination of knowledge and statistical data, Mach. learn., 20, 197-243, (1995), Kluwer, Dordrecht, Netherlands · Zbl 0831.68096
[21] Jensen, F.V., Bayesian networks and decision graphs, (2001), Springer Berlin, Germany · Zbl 0973.62005
[22] ()
[23] Khanafar, R.M.; Solana, B.; Triola, J.; Barco, R.; Moltsen, L.; Altman, Z.; Lazaro, P., Automated diagnosis for UMTS networks using a Bayesian network approach, IEEE trans. veh. technol., 57, 4, 2451-2461, (2008), IEEE Press, Piscataway, NJ, USA
[24] Kim, S.; Imoto, S.; Miyano, S., Dynamic Bayesian network and nonparametric regression for nonlinear modeling of gene networks from time series gene expression data, Biosystems, 75, 1-3, 57-65, (2004), Elsevier Science, Amsterdam, Netherlands
[25] Lauritzen, S.L., Graphical models, (1996), Oxford University Press Oxford, United Kingdom · Zbl 0907.62001
[26] Neapolitan, R.E., Learning Bayesian networks, (2004), Prentice Hall Englewood Cliffs, NJ, USA
[27] Niculescu, R.S.; Mitchell, T.M.; Rao, R.B., Bayesian network learning with parameter constraints, J. Mach. learn. res., 7, 1357-1383, (2006), Microtome Publishing, Brookline, MA, USA · Zbl 1222.68275
[28] Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann San Mateo, CA, USA, (2nd edition, 1992)
[29] Pernkopf, F., Detection of surface defects on raw steel blocks using Bayesian network classifiers, Pattern anal. appl., 7, 3, 333-342, (2004), Springer, London, United Kingdom
[30] Rasmussen, L.K., Blood group determination of danish jersey cattle in the F-blood group system, Dina res. rep., vol. 8, (1992), Dina Foulum Tjele, Denmark
[31] Robles, V.; Larrañaga, R.; Pena, J.; Menasalvas, E.; Perez, M.; Herves, V.; Wasilewska, A., Bayesian network multi-classifiers for protein secondary structure identification, Artificial intelligence med., 31, 2, 117-136, (2004), Elsevier Science, Amsterdam, Netherlands
[32] Roos, T.; Wettig, H.; Grünwald, P.; Myllymäki, P.; Tirri, H., On discriminative Bayesian network classifiers and logistic regression, Mach. learn., 65, 1, 31-78, (2005), Springer, Amsterdam, Netherlands · Zbl 1101.68785
[33] Schneiderman, H., Learning a restricted Bayesian network for object recognition, (), 639-646
[34] Singh, M.; Valtorta, M., An algorithm for the construction of Bayesian network structures from data, (), 259-265
[35] Spirtes, P.; Glymour, C.; Scheines, R., Causation, prediction, and search, Lecture notes in statist., vol. 81, (1993), Springer New York, NY, USA · Zbl 0806.62001
[36] H. Steck, Constraint-based structural learning in Bayesian networks using finite data sets, PhD thesis, TU München, Germany, 2001
[37] Tsamardinos, I.; Brown, L.E.; Aliferis, C.F., The max – min Hill-climbing Bayesian network structure learning algorithm, Mach. learn., 65, 1, 31-78, (2006), Springer, Amsterdam, Netherlands
[38] Whittaker, J., Graphical models in applied multivariate statistics, (1990), J. Wiley & Sons Chichester, United Kingdom · Zbl 0732.62056
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.