Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Regular Section -- Papers -- Artificial Intelligence and Cognitive Science |
Structure Learning of Bayesian Networks Using Dual Genetic Algorithm*
1 The authors are with the CILAB, School of Electrical and Electronic Engineering, Yonsei University, 134, Shinchon-Dong, Sudaemun-ku, Seoul 120–749, Korea. E-mail: etkim{at}yonsei.ac.kr, 2 The author is with the School of Electrical and Electronic Engineering, Yonsei University, 134, Shinchon-Dong, Sudaemun-ku, Seoul 120–749, Korea.
A new structure learning approach for Bayesian networks (BNs) based on dual genetic algorithm (DGA) is proposed in this paper. An individual of the population is represented as a dual chromosome composed of two chromosomes. The first chromosome represents the ordering among the BN nodes and the second represents the conditional dependencies among the ordered BN nodes. It is rigorously shown that there is no BN structure that cannot be encoded by the proposed dual genetic encoding and the proposed encoding explores the entire solution space of the BN structures. In contrast with existing GA-based structure learning methods, the proposed method learns not only the topology of the BN nodes, but also the ordering among the BN nodes, thereby, exploring the wider solution space of a given problem than the existing method. The dual genetic operators are closed in the set of the admissible individuals. The proposed method is applied to real-world and benchmark applications, while its effectiveness is demonstrated through computer simulation.
Key Words: Bayesian network, genetic algorithms, structure learning, dual chromosomes
Manuscript received July 27, 2006. Manuscript revised June 25, 2007.
* This work was supported by the Ministry of Commerce, Industry and Energy of Korea (HISP).
Reference
[1] F.V. Jensen, "Introduction to Bayesian networks," Technical Report IR 93–2003, Dept. of Mathematics and Computer Science, Univ. of Aalborg, Denmark, 1993. [2] M.L. Wong and K.S. Leung, "An efficient data mining method for learning Bayesian networks using an evolutionary algorithm-based hybrid approach," IEEE Trans. Evol. Comput., vol.8, no.4, pp.378–404, Aug. 2004. [3] H. Wang, D. Dash, and M.J. Druzdzel, "A method for evaluating elicitation schemes for probabilistic models," IEEE Trans. Syst. Man Cybern. B, vol.32, no.1, pp.38–43, Feb. 2002. [4] S. Acid, L.M. De Campos, A. Gonzalez, R. Molina, and N. Perez de la Blanca, "Learning with CASTLE," in Symbolic and Quantitative Approaches to Uncertainty, ed. R. Kruse and P. Siegel, LNCS 548, Springer-Verlag, 1991. [5] D.M. Chickering, D. Geiger, and D. Heckerman, "Learning Bayesian networks: Search methods and experimental results," Fifth Int'l Workshop Artificial Intelligence and Statistics, pp.112–128, 1995. [6] G.M. Provan, "Model selection for diagnosis and treatment using temporal influence diagrams," Proc. Fourth Int'l Workshop Artificial Intelligence and Statistics, pp.469–480, 1995. [7] P. Larra naga, M. Poza, Y. Yurramendi, R. Murga, and C. Kuijpers, "Structure learning of Bayesian network by genetic algorithms: A performance analysis of control parameters," IEEE Trans. Pattern Analysis and Machine Intelligence, vol.18, no.9, pp.912–926, Sept. 1996. [8] R. Garza-Domínguez, M. Martínez-Morales, N. Cruz-Ramírez, J.L. Jiménez-Andrade and A.G. Hernández, "A method based on genetic algorithms and fuzzy logic to induce bayesian networks," Proc. Fifth Mexican International Conference in Computer Science (ENC2004), pp.176–180, Colima, Mexico, 2004. [9] L.M.d. Campos, J.A. Gámez, and S. Moral, "Partial abductive inference in Bayesian belief networks – An evolutionary computation approach by using problem-specific genetic operators," IEEE Trans. Evol. Comput., vol.6, no.2, pp.105–131, April 2002. [10] G.F. Cooper and E.A. Herskovits, "A Bayesian method for the induction of probabilistic networks from data," Mach. Learn., vol.9, no.4, pp.309–347, 1992 [11] X. Li, X. He, and S. Yuan, "Learning Bayesian networks structures from incomplete data based on extending evolutionary programming," Proc. 2005 International Conference Machine Learning and Cybernetics 2005, vol.4, pp.2039–2043, Aug. 2005. [12] S. Shetty and M. Song, "Structure learning of Bayesian networks using a semantic genetic algorithm-based approach," 3rd International Conference Information Technology: Research and Education 2005 (ITRE 2005), pp.454–458, June 2005. [13] W. Chung, Context-aware Application for Smart Home Based on Bayesian Network, Master Thesis, Yonsei University, 2006. [14] http://www.norsys.com/networklibrary.html [15] F.V. Jensen, Bayesian Networks and Decision Graphs, Springer, 2001. [16] S.Z. Zhang, Z.N. Zhang, N.H. Yang, J.Y. Zhang, and X.K. Wang, "An improved EM algorithm for Bayesian networks parameter learning," Mach. Learn. Cybern., vol.3, pp.1503–1508, Aug. 2004 [17] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, 1999. [18] P. Larra naga, C. Kuijpers, and R. Murga, "Learning Bayesian network structures by searching for the best ordering with genetic algorithms," IEEE Trans. Syst. Man Cybern. A, vol.26, no.4, pp.487–493, July 1996. [19] P. Korpipää, M. Koskinen, J. Peltola, S. Mäkelä, and T. Seppänen, "Bayesian approach to sensor-based context awareness," Personal and Ubiquitous Computing J., vol.7, no.4, pp.113–124, July 2003. [20] I.A. Beinlinch, H.J. Suermondt, R.M. Chavez, and G.F. Cooper, "The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks," Proc. Second European Conf. Artificial Intelligence in Medicine, pp.247–256, 1989. [21] K.B. Hwang and B.T. Zhang, "Bayesian model averaging of Bayesian network classifiers over multiple node-orders application to sparse datasets," IEEE Trans. Syst. Man Cybern. B, vol.35, no.6, pp.1302–1310, Dec. 2005.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by LEE, J.
Articles by KIM, E.
Search for Related Content
Social Bookmarking
What's this?