Abstract
This paper presents the I-map hybrid algorithm for selecting, given a data sample, a linear Gaussian model whose structure is a directed graph. The algorithm performs a local search for a model that meets the following criteria: (1) The Markov blankets in the model should be consistent with dependency information from statistical tests. (2) Minimize the number of edges subject to the first constraint. (3) Maximize a given score function subject to the first two constraints. Our local search is based on Graph Equivalence Search (GES); we also apply the recently developed SIN statistical testing strategy to help avoid local minima. Simulation studies with GES search and the BIC score provide evidence that for nets with 10 or more variables, the hybrid method selects simpler graphs whose structure is closer to the target graph.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Beinlich, I., Suermondt, H., Chavez, R., Cooper, G.: The ALARM monitoring system. In: AIME 1989, pp. 247–256 (1989)
Benjamini, Y., Hochberg, Y.: Controllling the false discovery rate—a practical and powerful approach to multiple testing. Journal of the Royal Statistical Society 57(1), 289–300 (1995)
Binder, J., Koller, D., Russell, S., Kanazawa, K.: Adaptive probabilistic networks with hidden variables. Machine Learning 29 (1997)
Bouckaert, R.R.: Bayesian belief networks: from construction to inference. PhD thesis, Universiteit Utrecht (1995)
Chickering, D.: Optimal structure identification with greedy search. JMLR 3, 507–554 (2003)
The Tetrad project: Causal models and statistical data (2008), http://www.phil.cmu.edu/projects/tetrad/
Cooper, G.: An overview of the representation and discovery of causal relationships using Bayesian networks. In: Glymour, C., Cooper, G. (eds.) Computation, Causation, and Discovery, pp. 4–62. MIT, Cambridge (1999)
de Campos, L.: A scoring function for learning Bayesian networks based on mutual information and conditional independence tests. JMLR, 2149–2187 (2006)
Drton, Perlman: A SINful approach to Bayesian graphical model selection. Journal of Statistical Planning and Inference 138, 1179–1200 (2008)
Edwards, D.: Introduction to Graphical Modelling. Springer, New York (2000)
Friedman, N., Pe’er, D., Nachman, I.: Learning Bayesian network structure from massive datasets. In: UAI, pp. 206–215 (1999)
Hay, M., Fast, A., Jensen, D.: Understanding the effects of search constraints on structure learning. Technical Report 07-21, U Mass. Amherst CS (April)
Heckerman, D.: A tutorial on learning with Bayesian networks. In: NATO ASI on Learning in graphical models, pp. 301–354 (1998)
Klein, R.: Principles and practice of structural equation modeling. Guilford, New York (1998)
Margaritis, D., Thrun, S.: Bayes. net. induction via local neighbor. In: NIPS, pp. 505–511 (2000)
Meek, C.: Graphical Models: Selecting causal and statistical models. PhD thesis, CMU (1997)
Neapolitan, R.E.: Learning Bayesian Networks. Pearson Education, London (2004)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Francisco (1988)
Schmidt, M., Niculescu-Mizil, A., Murphy, K.: Learning graphical model structure using L1-regularization path. In: AAAI (2007)
Schulte, O., Frigo, G., Greiner, R., Khosravi, H.: The IMAP hybrid method for learning Gaussian Bayes nets: Full version, ftp://ftp.fas.sfu.ca/pub/cs/oschulte/imap/imap-linear.pdf
Schulte, O., Frigo, G., Greiner, R., Khosravi, H.: A new hybrid method for Bayesian network learning with dependency constraints. In: Proceedings IEEE CIDM Symposium, pp. 53–60 (2009)
Schulte, O., Luo, W., Greiner, R.: Mind change optimal learning of bayes net structure. In: Bshouty, N.H., Gentile, C. (eds.) COLT. LNCS (LNAI), vol. 4539, pp. 187–202. Springer, Heidelberg (2007)
Spirtes, P., Glymour, C., Scheines, R.: Causation, Prediction, and Search. MIT Press, Cambridge (2000)
Tsamardinos, I., Brown, L.E., Aliferis, C.F.: The max-min hill-climbing bayesian network structure learning algorithm. Machine Learning 65(1), 31–78 (2006)
van Allen, T., Greiner, R.: Model selection criteria for learning belief nets: An empirical comparison. In: ICML, pp. 1047–1054 (2000)
Witten, I.H., Frank, E.: Data Mining: Practical Machine Learning Tools and Techniques, 2nd edn. Morgan Kaufmann, San Francisco (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schulte, O., Frigo, G., Greiner, R., Khosravi, H. (2010). The IMAP Hybrid Method for Learning Gaussian Bayes Nets. In: Farzindar, A., Kešelj, V. (eds) Advances in Artificial Intelligence. Canadian AI 2010. Lecture Notes in Computer Science(), vol 6085. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13059-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-13059-5_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13058-8
Online ISBN: 978-3-642-13059-5
eBook Packages: Computer ScienceComputer Science (R0)