 Structure Learning in Bayesian Networks Using Asexual Reproduction Optimization

Document Type : Research Article

Authors

1 Corresponding Author, A. R. Khanteymoori is with the Department of Computer Engineering and Information Technology, Amirkabir University of Technology, Tehran, Iran (e-mail: khanteymoori@aut.ac.ir).

2 M. M. Homayounpour is with the Department of Computer Engineering and Information Technology, Amirkabir University of Technology, Tehran, Iran (e-mail: hamayoun@aut.ac.ir).

3 M. B. Menhaj is with the Department of Electrical Engineering, Amirkabir University of Technology, Tehran, Iran (e-mail: mb.menhaj@aut.ac.ir).

Abstract

A new structure learning approach for Bayesian networks (BNs) based on asexual reproduction optimization (ARO) is proposed in this letter. ARO can be essentially considered as an evolutionary based algorithm that mathematically models the budding mechanism of asexual reproduction. In ARO, a parent produces a bud through a reproduction operator; thereafter the parent and its bud compete to survive according to a performance index obtained from the underlying objective function of the optimization problem; this leads to the fitter individual. The convergence measure of ARO is analyzed. The proposed method is applied to real-world and benchmark applications, while its effectiveness is demonstrated through computer simulations. Results of simulation show that ARO outperforms GA because ARO results in good structure and fast convergence rate in comparison with GA.

Keywords

References

[1]    J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA, 1988.
[2]    R. E. Neapolitan, Learning Bayesian Networks. Prentice Hall, Upper Saddle River (NJ), 2004.
[3]    S. Russell and P.  Norvig, Artificial Intelligence: A modern Approach. Prentice Hall, Upper Saddle River (NJ), Second Edition, 2003.
[4]    F. V. Jensen, “Introduction to Bayesian networks”, Technical Report IR 93–2003, Dept. of Mathematics and Computer Science, Univ. of Aalborg, Denmark, 1993.
[5]    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. Evolutionary Computing, vol.8, no.4, pp.378–404, Aug. 2004.
[6]    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.
[7]    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.
[8]    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.
[9]    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 Transaction on Pattern Analysis and Machine Intelligence, vol.18, no.9, pp.912–926, Sept. 1996.
[10]  G. F. Cooper and E. A. Herskovits, “A Bayesian method for the induction of probabilistic networks from data,” Machine  Learning, 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]  D. M. Chickering, “Learning Bayesian networks is NP-complete”, In Learning from Data, Artificial Intelligence and Statistics V. Springer Verlag, 1996.
[13]  http://en.wikipedia.org/wiki/Bayesian_network
[14]  D. Heckerman, D. Geiger, and D. M. Chickering, “Learning Bayesian networks”, The combination of knowledge and statistical data. Machine Learning, 20:197-243, 1995.
[15]  R. W. Robinson. , “Counting unlabeled acyclic digraphs”, In C. H. C. Little, Ed., Combinatorial Mathematics V, volume 622 of Lecture Notes in Mathematics, pp. 28–43, Berlin: Springer, 1977.
[16]  D. M. Chickering, “Optimal structure identification with greedy search”, Journal of Machine Learning Research, 3, 507–554, 2002.
[17]  C. Chow and C. Liu, “Approximating discrete probability distributions with dependence trees”, IEEE Transactions on Information Theory, 14(3), 462–467, 1968.
[18]  M. A. Faust, R. A. Gulledge, “Identifying harmful marine dinoflagellates”, Smithson. Contrib. U. S. Natl. Herb., 42, 1–144, 2002.
[19]  S. Willcox, N. A. Moltschaniwskyj and C. Crawford, “Asexual reproduction in scyphistomae of Aurelia sp.: Effects of temperature and salinity in an experimental study”, Journal of Experimental Marine Biology and ecology, Volume 353, Issue 1, pp. 107-114, 2007.
[20]  C. Zilberberg, A. M. Solé-Cava and M. Klautau, “The extent of asexual reproduction in sponges of the genus Chondrilla (Demospongiae: Chondrosida) from the Caribbean and the Brazilian coasts”, Journal of Experimental Marine Biology and Ecology, Volume 336, Issue 2, pp. 211-220, 2006.
[21]  K. Holmstrom and H. J. Jensen, “Who runs fastest in an adaptive landscape: sexual versus asexual reproduction”, Physica A: Statistical and Theoretical Physics, Volume 337, Issues 1-2, pp 185-195,  2004.
[22]  W. Song, “Morphogenesis of Cyrtohymena tetracirrata (Ciliophora, Hypotrichia, Oxytrichidae) during binary fission”, European Journal of  Protistology, Volume 40, Issue 3, pp 245-254, 2004.
[23]  K. Lee, P. Singh, W. C. Chung, J. Ash, T. S. Kim, L. Hang and S. Park, “Light regulation of asexual development in the rice blast fungus, Magnaporthe oryzae”,  Fungal Genetics and Biology, Volume 43, Issue 10, pp 694-706,  2006.
[24]  T. Yanagi, T. Yachi and N. Okuda, “Photoperiodic reaction of sexual and asexual reproduction in Fragaria chiloensis L. CHI-24-1 plants grown at various temperatures”, Scientia Horticulturae, Volume 110, Issue 2, pp. 187-191, 2006.
[25]  F. Prall and C. Ostwald, “High-degree tumor budding and podia-formation in sporadic colorectal carcinomas with K-ras gene mutations”, Hum Pathol, 38:1696-702, 2007.
[26]  A. V. Ramayya, J. H. Hamilton, J. K. Hwang, C. J. Beyer, G. M. Ter Akopian, A. V. Daniel, J. O. Rasmussen, S. C. Wu, R. Donangelo, J. Kormicki, X. Q. Zhang, A. Rodin, A. Formichev, J. Kliman, L. Krupa, Y. T. Oganessian, G. Chubaryan, D. Seweryniak, R. V. F. Janssens, W. C. Ma, et al, “Binary and ternary fission studies with 252Cf”, Progress in Particle and Nuclear Physics, Volume 46, Issue 1, pp. 221-229, 2001.
[27]  S. Stertz, M. Reichelt, M. Spiegel, T. Kuri, L. Martínez-Sobrido, A. García-Sastre, F. Weber and G. Kochs, “The intracellular sites of early replication and budding of SARS-coronavirus", Virology, Volume 361, Issue 2, pp 304-315,  2007.
[28]  R. F. Green and D. L. G. Noakes, “Is a little bit of sex as good as a lot?”, Journal of Theoretical Biology, Volume 174, Issue 1, pp. 87-96, 1995.
[29]  M. T. Ghiselin, “The evolution of sex: A history of competing points of view”, In: Michod, R.E. & Levin, B.R. (eds.), The evolution of sex: an examination of current ideas. Sinauer Associates Inc., Sunderland. pp. 7-23, 1988.
[30]  M. Clerc, J. Kennedy, “The particle swarm explosion, stability, and convergence in a multidimensional complex space”, IEEE Transaction on Evolutionary Computation 6, pp. 58–73, 2002.
[31]  M. Mitchel, An introduction to genetic algorithms, MIT Press, 1999.
[32]  M. Dorigo and T. Stützle, Ant Colony Optimization, Prentice-Hall of India, New Delli, 2005.
[33]  D. Gross, C. M. Harris, Fundamental of Queuing, 2th edition, Wiley, New York, 1984.
[34]   http://www.norsys.com/networklibrary.html
[35]  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.

Files

Share

How to cite

Statistics